【正文】 散權(quán)值等同看待同一跳段的鄰居，而沒(méi)有抑制測(cè)距誤差大的影響的不足提出分布式多維標(biāo)度定位算法dwMDS(G)(Distributed WeightedMultidimensional Scaling),該定位算法是一種基于高斯核加權(quán)機(jī)制的分布式定位算法，采用的是高斯核加權(quán)機(jī)制，根據(jù)與未知節(jié)點(diǎn)距離的大小賦予權(quán)值，而且采用自適應(yīng)2步鄰居選擇機(jī)制避免了測(cè)距粗差對(duì)鄰居選擇的負(fù)偏效應(yīng)。dwMDS(G)定位算法的特點(diǎn)是：(1) 加權(quán)機(jī)制是與未知節(jié)點(diǎn)的距離有關(guān)的加權(quán)函數(shù)，權(quán)值可取任意非負(fù)整數(shù)，不是只能取0和1，而是根據(jù)與未知節(jié)點(diǎn)間的距離遠(yuǎn)近賦予大小不同的權(quán)值來(lái)避免定位誤差的擴(kuò)散。(2) 利用自適應(yīng)2步鄰居選擇機(jī)制，使得受測(cè)距粗差影響的鄰居選擇的負(fù)偏效應(yīng)減小。(3) 采用循環(huán)迭代優(yōu)化的方法，使得求解最小代價(jià)函數(shù)時(shí)的迭代次數(shù)降低。(4) 由于只是1跳鄰居節(jié)點(diǎn)參與定位，因此適用于拓?fù)浣Y(jié)構(gòu)規(guī)則的密集型網(wǎng)絡(luò)。 dwMDS(G)算法定位過(guò)程dwMDS(G)算法的具體定位過(guò)程分為以下幾個(gè)階段：(1) 每個(gè)節(jié)點(diǎn)先采用經(jīng)典MDS算法構(gòu)建初始的局部坐標(biāo)系，由于在上一章中已經(jīng)對(duì)經(jīng)典MDS基本原理作了詳細(xì)的介紹，此處就不做具體的介紹了。(2) 利用增量貪婪法將所有節(jié)點(diǎn)的初始局部坐標(biāo)轉(zhuǎn)換為全局相對(duì)坐標(biāo)。(3) 根據(jù)傳感器網(wǎng)絡(luò)中的信標(biāo)節(jié)點(diǎn)的坐標(biāo)信息，將全局相對(duì)坐標(biāo)轉(zhuǎn)換為初始化的全局絕對(duì)坐標(biāo)系。(4) 根據(jù)網(wǎng)絡(luò)的局部屬性，讓未知節(jié)點(diǎn)選取其真正的1跳鄰居節(jié)點(diǎn)來(lái)參與定位求解。(5) 使用高斯核加權(quán)機(jī)制計(jì)算出權(quán)值： (41)式中 ——節(jié)點(diǎn)與節(jié)點(diǎn)間的測(cè)量距離(m)；——節(jié)點(diǎn)測(cè)量距離的最大值。(6) 對(duì)初始的全局絕對(duì)坐標(biāo)作為迭代的初始值進(jìn)行迭代優(yōu)化，以獲得最終的全局絕對(duì)坐標(biāo)。 dwMDS(G)算法的改進(jìn) 改進(jìn)算法的相關(guān)研究工作集中式MDS定位算法不適合大規(guī)模網(wǎng)絡(luò)、擴(kuò)展性差，針對(duì)此不足，人們陸續(xù)提出分布式MDS定位算法。其中，Local MDS算法使用的加權(quán)值僅是0和1，即同一跳段內(nèi)鄰居節(jié)點(diǎn)的權(quán)重是一樣的；MDSMAP(P/R)算法對(duì)參與定位的鄰居節(jié)點(diǎn)沒(méi)有進(jìn)行選擇(即所有鄰居節(jié)點(diǎn)都參與)，沒(méi)有抑制較大測(cè)距誤差的擴(kuò)散，從而導(dǎo)致該算法抗差性能差；dwMDS(G)定位算法對(duì)上述兩種算法的加權(quán)方法做了改進(jìn)。但是由于dwMDS(G)算法采用的加權(quán)函數(shù)僅與測(cè)距大小相關(guān)，因此該算法的定位精度受測(cè)距誤差及拓?fù)浣Y(jié)構(gòu)等因素的影響。因?yàn)榫嚯x未知節(jié)點(diǎn)近的節(jié)點(diǎn)，其定位誤差有可能比距離遠(yuǎn)的節(jié)點(diǎn)的定位誤差大，所以若賦予距離未知節(jié)點(diǎn)近的節(jié)點(diǎn)較大的權(quán)值，這樣就會(huì)造成距離未知節(jié)點(diǎn)近的定位誤差在網(wǎng)絡(luò)中不斷擴(kuò)散。這種擴(kuò)散效應(yīng)在網(wǎng)絡(luò)密度分布不均勻或網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)不規(guī)則的稀疏網(wǎng)絡(luò)中更為明顯，因此該算法不適合于這樣的網(wǎng)絡(luò)。此外，分布式加權(quán)多維標(biāo)度定位算法采用的是自適應(yīng)2步鄰居選擇機(jī)制，該選擇機(jī)制僅選擇1跳鄰居節(jié)點(diǎn)參與定位，由于在網(wǎng)絡(luò)稀疏和節(jié)點(diǎn)分布不均的情況下，部分未知節(jié)點(diǎn)的1跳鄰居節(jié)點(diǎn)很少，這樣參與該未知節(jié)點(diǎn)定位的鄰居節(jié)點(diǎn)就會(huì)很少，從而會(huì)增加其定位誤差，有的甚至無(wú)法實(shí)現(xiàn)定位。因此該算法只適用于節(jié)點(diǎn)分布密集且拓?fù)浣Y(jié)構(gòu)規(guī)則的無(wú)線傳感器網(wǎng)絡(luò)中。針對(duì)上述分布式加權(quán)多維標(biāo)度定位算法的不足，本文提出了一種改進(jìn)方案：(1)對(duì)其鄰居選擇機(jī)制作了修正；(2)對(duì)其加權(quán)機(jī)制進(jìn)行了修正；(3)在原有算法的基礎(chǔ)上引入了最速下降法對(duì)其局部代價(jià)函數(shù)進(jìn)行優(yōu)化。 鄰居選擇機(jī)制本文提出的與節(jié)點(diǎn)定位相對(duì)誤差相關(guān)的鄰居選擇機(jī)制，綜合考慮了未知節(jié)點(diǎn)所在局部網(wǎng)絡(luò)中節(jié)點(diǎn)分布的變化、定位誤差及與未知節(jié)點(diǎn)之間的距離，根據(jù)真正的1跳鄰居節(jié)點(diǎn)數(shù)量自適應(yīng)判斷是否讓2跳鄰居節(jié)點(diǎn)參與定位，同時(shí)計(jì)算出所選的鄰居節(jié)點(diǎn)的定位相對(duì)誤差，根據(jù)其是否小于預(yù)設(shè)的相對(duì)誤差的門限值來(lái)選取最終參與未知節(jié)點(diǎn)定位的鄰居節(jié)點(diǎn)。自適應(yīng)鄰居選擇的具體步驟為以下幾步：步驟1 未知節(jié)點(diǎn)首先判斷其1跳鄰居節(jié)點(diǎn)是否小于預(yù)設(shè)的參與定位的鄰居節(jié)點(diǎn)數(shù)量，如果小于則選擇2跳鄰居節(jié)點(diǎn)，否則只選擇1跳鄰居節(jié)點(diǎn)；步驟2 計(jì)算出第一步選出的鄰居節(jié)點(diǎn)定位的相對(duì)誤差，然后將其按照從小到大的順序排列。對(duì)于2跳鄰居將到未知節(jié)點(diǎn)的最短路徑長(zhǎng)度當(dāng)作其與未知節(jié)點(diǎn)之間的距離；計(jì)算節(jié)點(diǎn)定位相對(duì)誤差的具體過(guò)程：(1) 每次迭代之前，先根據(jù)式(42)計(jì)算出節(jié)點(diǎn)的平均定位誤差 (42)式中 ——參與節(jié)點(diǎn)定位時(shí)的鄰居節(jié)點(diǎn)數(shù)；——節(jié)點(diǎn)與鄰居節(jié)點(diǎn)之間的歐氏距離；——節(jié)點(diǎn)與鄰居節(jié)點(diǎn)之間的測(cè)距或最短路徑距離。(2) 使用式(43)將定位誤差歸一化處理。 (43)(3) 綜合考慮未知節(jié)點(diǎn)的鄰居節(jié)點(diǎn)的自身定位誤差和與之間的測(cè)距所引入的誤差，根據(jù)式(44)可以計(jì)算出節(jié)點(diǎn)相對(duì)節(jié)點(diǎn)的相對(duì)誤差。 (44)步驟3 將相對(duì)誤差大于預(yù)設(shè)的相對(duì)誤差的門限值的鄰居節(jié)點(diǎn)去除，使用剩余的可信度較高的鄰居節(jié)點(diǎn)參與定位計(jì)算。 加權(quán)機(jī)制受測(cè)距誤差及網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)不規(guī)則的影響，與未知節(jié)點(diǎn)之間距離近的鄰居節(jié)點(diǎn)的定位誤差有可能比較大，因此，計(jì)算權(quán)值時(shí)需要考慮鄰居節(jié)點(diǎn)的測(cè)距誤差及定位誤差，使得綜合性能好的鄰居節(jié)點(diǎn)在未知節(jié)點(diǎn)定位有更大的貢獻(xiàn)?；谶@一點(diǎn)，可以看出權(quán)值應(yīng)該與相對(duì)誤差成反比，于是本文將按式(45)對(duì)相對(duì)誤差的倒數(shù)作歸一化處理后的值作為權(quán)值?？梢灾苯永蒙弦还?jié)中的式(44)計(jì)算出的相對(duì)誤差來(lái)進(jìn)行計(jì)算。 (45)式中 ——采用鄰居加權(quán)機(jī)制選擇出的未知節(jié)點(diǎn)的鄰居節(jié)點(diǎn)的個(gè)數(shù)——節(jié)點(diǎn)相對(duì)節(jié)點(diǎn)的誤差。 優(yōu)化目標(biāo)代價(jià)函數(shù)借鑒經(jīng)典的度量多維標(biāo)度技術(shù)定位是通過(guò)最小化脅強(qiáng)系數(shù)對(duì)未知節(jié)點(diǎn)定位的方式，本文將其脅強(qiáng)系數(shù)轉(zhuǎn)化為目標(biāo)代價(jià)函數(shù)如式(46)所示，通過(guò)求解使得目標(biāo)代價(jià)函數(shù)最小化的條件對(duì)未知節(jié)點(diǎn)進(jìn)行定位。 (46)式中 ——傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)(個(gè))；——未知節(jié)點(diǎn)數(shù)(個(gè))；——節(jié)點(diǎn)與節(jié)點(diǎn)之間的測(cè)量距離；——上一步計(jì)算出的加權(quán)值(當(dāng)節(jié)點(diǎn)與節(jié)點(diǎn)之間無(wú)距離測(cè)量值或節(jié)點(diǎn)與節(jié)點(diǎn)不是鄰居節(jié)點(diǎn)時(shí)，或不存在)；——表示節(jié)點(diǎn)與節(jié)點(diǎn)估計(jì)位置之間的距離計(jì)算公式如下：。經(jīng)過(guò)簡(jiǎn)單的運(yùn)算后，代價(jià)函數(shù)可變?yōu)槭?47)。 (47)其中是與節(jié)點(diǎn)坐標(biāo)無(wú)關(guān)的常量，為每個(gè)未知節(jié)點(diǎn)的局部代價(jià)函數(shù)，其表達(dá)式見(jiàn)式(48)。 (48)當(dāng)沒(méi)有信標(biāo)節(jié)點(diǎn)即時(shí)，與存在的關(guān)系式間式(49)。 (49)由上述關(guān)系式可以看出，當(dāng)每個(gè)取最小值時(shí)，就會(huì)取得最小值，則可以通過(guò)最小化每個(gè)未知節(jié)點(diǎn)的局部代價(jià)函數(shù)還獲取相應(yīng)未知節(jié)點(diǎn)的位置坐標(biāo)。接下來(lái)采用無(wú)約束優(yōu)化方法中最簡(jiǎn)單快速的方法——最速下降法對(duì)其局部代價(jià)函數(shù)進(jìn)行優(yōu)化求解。在數(shù)值分析中，迭代優(yōu)化方法的基本思想是：給定初始點(diǎn)，得到一系列的點(diǎn)，當(dāng)時(shí)，為式(48)取最小值時(shí)的最優(yōu)解，迭代公式見(jiàn)式(410)。 (410)其中表示第次循環(huán)迭代的次數(shù)，為第次的迭代結(jié)果，為第次迭代的步長(zhǎng)，為搜索的方向。由于是最小化目標(biāo)函數(shù)，則需以負(fù)梯度方向作為優(yōu)化算法的下降方向，其表達(dá)式見(jiàn)式(411)。令，則根據(jù)式(410)節(jié)點(diǎn)的坐標(biāo)滿足式(412)。選擇迭代步長(zhǎng)的方法就是使得目標(biāo)函數(shù)最小，計(jì)算公式見(jiàn)式(413)。由一維線性搜索求迭代步長(zhǎng)因子使得式(413)成立，從而將多維目標(biāo)函數(shù)轉(zhuǎn)換成一維目標(biāo)函數(shù)，表達(dá)式見(jiàn)式(414)。 (411)式中 (412) (413) (414)本文采用二次插值的方式進(jìn)行線性搜索，設(shè)在，處的函數(shù)值分別為，，利用二次插值可求得式(415)。 (415)算出，再?gòu)?，中去掉?duì)應(yīng)函數(shù)值最大的點(diǎn)，將新點(diǎn)代入得到新的三個(gè)點(diǎn)，循環(huán)迭代執(zhí)行上述計(jì)算過(guò)程直到滿足要求的精度為止。 改進(jìn)算法的定位過(guò)程改進(jìn)算法定位的具體過(guò)程分為以下幾步：第一步 每個(gè)節(jié)點(diǎn)先采用經(jīng)典MDS算法構(gòu)建初始的局部坐標(biāo)系，由于在上一章中已經(jīng)對(duì)經(jīng)典MDS基本原理作了詳細(xì)的介紹，此處就不做具體的介紹了。第二步 。第三步 根據(jù)傳感器網(wǎng)絡(luò)中的信標(biāo)節(jié)點(diǎn)的坐標(biāo)信息，將初始化的全局相對(duì)坐標(biāo)轉(zhuǎn)換為絕對(duì)坐標(biāo)。第四步 。第五步 ，通過(guò)利用最速下降法對(duì)局部代價(jià)函數(shù)進(jìn)行優(yōu)化，得出各個(gè)局部代價(jià)函數(shù)取最小值時(shí)的相應(yīng)未知節(jié)點(diǎn)的位置坐標(biāo)。：改進(jìn)的dwMDS算法。輸入：，；/*為節(jié)點(diǎn)與節(jié)點(diǎn)之間的測(cè)量距離，為信標(biāo)節(jié)點(diǎn)個(gè)數(shù)，為要求滿足的精度*/輸出：，/*節(jié)點(diǎn)的橫縱坐標(biāo)*/Begin(1)Inputs：，；(2)Bulid local map with MDS。(3)Change local maps into the global relative map。(4)Change relative map into absolute map to get the initial coordinates。(5)Initialize:,pute from (411)。(6)Repeat:(7) (8) For to (9) Compute the relative location Error 。(10) Select neiborhood to participate location。(11) Compute from (45)。(12) Search step factor and calculate from (412)。(13) Compute 。(14) 。(15) End for(16)Until .End 本章小結(jié)本章重點(diǎn)探討了分布式加權(quán)多維標(biāo)度定位算法通過(guò)分析算法的不足之處提出了改進(jìn)方案。分布式加權(quán)多維標(biāo)度定位算法采用的是僅與到未知節(jié)點(diǎn)的測(cè)距大小有關(guān)的加權(quán)機(jī)制和其采用的自適應(yīng)2步鄰居選擇機(jī)制即只有1跳鄰居節(jié)點(diǎn)參與節(jié)點(diǎn)定位，如果網(wǎng)絡(luò)稀疏或分布不均時(shí)，這兩種機(jī)制都會(huì)導(dǎo)致未知節(jié)點(diǎn)的定位誤差加大或甚至無(wú)法定位。因此，為了使得算法不僅適用于密集型、分布均勻及拓?fù)湟?guī)則的網(wǎng)絡(luò)，而且也適用于稀疏、分布不均、拓?fù)洳灰?guī)則的網(wǎng)絡(luò)，本章主要對(duì)這兩方面提出了改進(jìn)方案。其一，讓其權(quán)值由與未知節(jié)點(diǎn)的距離遠(yuǎn)近和節(jié)點(diǎn)的相對(duì)定位誤差兩個(gè)因素決定；其二，引入節(jié)點(diǎn)相對(duì)誤差及預(yù)設(shè)的相對(duì)誤差門限值來(lái)進(jìn)行選擇參與未知節(jié)點(diǎn)定位的鄰居節(jié)點(diǎn)。最后，為了提高算法的收斂速度，引入了最速下降法對(duì)局部代價(jià)函數(shù)進(jìn)行優(yōu)化。第5章 仿真實(shí)驗(yàn)與性能分析第5章 仿真實(shí)驗(yàn)與性能分析 仿真平臺(tái)介紹對(duì)無(wú)線傳感器網(wǎng)絡(luò)進(jìn)行分析和研究的方法目前主要有三種：分析方法、實(shí)驗(yàn)方法和仿真模擬方法。由于研究的無(wú)線傳感器網(wǎng)絡(luò)造價(jià)比較昂貴、實(shí)驗(yàn)的危險(xiǎn)性比較大、算法比較復(fù)雜等因素的制約，采用分析方法和實(shí)驗(yàn)方法使得實(shí)際應(yīng)用的需求很難得到滿足，因而一般采用仿真模擬方法對(duì)無(wú)線傳感器網(wǎng)絡(luò)的定位算法進(jìn)行仿真驗(yàn)證。網(wǎng)絡(luò)仿真是一種很實(shí)用的網(wǎng)絡(luò)研究工具或平臺(tái)，仿真方法與數(shù)學(xué)分析方法相比，抽象化程度較低，且耗費(fèi)的時(shí)間少同時(shí)成本低，這些都是其他傳統(tǒng)方法無(wú)可代替的，因此網(wǎng)絡(luò)仿真的應(yīng)用越來(lái)越廣泛，大量的網(wǎng)絡(luò)仿真軟件應(yīng)運(yùn)而生。如今，已有很多成熟的平臺(tái)應(yīng)用在WSN中，但是不同仿真平臺(tái)的側(cè)重點(diǎn)和適用范圍不同，實(shí)現(xiàn)的機(jī)制也有所不同，例如常用的NS2仿真軟件是專門用來(lái)模擬網(wǎng)絡(luò)(包括傳統(tǒng)的網(wǎng)絡(luò)、無(wú)線Mesh網(wǎng)絡(luò)等)的一種面向?qū)ο蟆⒛軌驅(qū)φ麄€(gè)網(wǎng)絡(luò)環(huán)境進(jìn)行完整的模擬的仿真工具；而OPNET仿真軟件是由MIL3公司開(kāi)發(fā)的一款商用的網(wǎng)絡(luò)仿真軟件，可以通過(guò)各款路由器和交換機(jī)來(lái)搭建網(wǎng)絡(luò)。雖然這些專門的網(wǎng)絡(luò)仿真軟件功能比較強(qiáng)大，也有很多優(yōu)點(diǎn)，但是它們的適用范圍大多數(shù)是有關(guān)協(xié)議的模擬。而本文主要研究的是WSN的定位算法，更關(guān)心算法本身的性能，暫不考慮WNS的其他特性，只需將傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的測(cè)距誤差、通信半徑等參數(shù)信息設(shè)置好作為算法的輸入信息，將相應(yīng)的算法在仿真平臺(tái)上實(shí)現(xiàn)后得出相應(yīng)的實(shí)驗(yàn)結(jié)果即可。然而只要選擇一款擁有較強(qiáng)仿真功能的同時(shí)有快速的數(shù)值計(jì)算能力就可以提供定位算法的仿真。而仿真軟件中符合這個(gè)特點(diǎn)且簡(jiǎn)單容易實(shí)現(xiàn)的就是數(shù)學(xué)領(lǐng)域常用的功能強(qiáng)大的MATLAB仿真工具，因此，本文就選擇該仿真平臺(tái)對(duì)其算法的性能進(jìn)行分析驗(yàn)證。MATLAB是一種用于科學(xué)工程計(jì)算的高效率高級(jí)語(yǔ)言。經(jīng)過(guò)Math Works公司的不斷完善，其功能越來(lái)越強(qiáng)。目前，MATALB已經(jīng)發(fā)展成為一款適用于多學(xué)科、多種工作平臺(tái)的常用軟件。隨著技術(shù)的不斷發(fā)展，MATLAB能夠方便地用來(lái)解決大部分的的工程及科學(xué)計(jì)算等各方面的問(wèn)題。MATLAB之所以能得到如此迅速的普及，顯示出強(qiáng)大的生命力廣泛的應(yīng)用，是因?yàn)樗哂衅渌呒?jí)語(yǔ)言不可比擬的優(yōu)勢(shì)，有豐富的函數(shù)資源，使得編程人員從煩瑣的程序代碼中解放出來(lái)。它的典型應(yīng)用包括數(shù)據(jù)分析與可視化、數(shù)學(xué)計(jì)算、建模與仿真、科學(xué)及工程繪圖、算法設(shè)計(jì)和應(yīng)用開(kāi)發(fā)等。 網(wǎng)絡(luò)部署由于對(duì)WSN定位算法的仿真只在網(wǎng)絡(luò)層面進(jìn)行分析、驗(yàn)證，就可滿足實(shí)驗(yàn)的要求，因此不需要涉及硬件層面的功能設(shè)置。所以在進(jìn)行實(shí)驗(yàn)前設(shè)置好以下幾個(gè)網(wǎng)絡(luò)參數(shù)即可，在這里先介紹一下幾個(gè)網(wǎng)絡(luò)參數(shù)的定義。(1)節(jié)點(diǎn)位置的表示在本文的實(shí)驗(yàn)仿真中，為了提高實(shí)驗(yàn)的高效性，將WSN建立在二維空間基礎(chǔ)上進(jìn)行，則節(jié)點(diǎn)的位置直接用二維空間中的坐標(biāo)值來(lái)表示即可，形如(28,56)。(2)網(wǎng)絡(luò)節(jié)點(diǎn)密度在無(wú)線傳感器網(wǎng)絡(luò)中，網(wǎng)絡(luò)的節(jié)點(diǎn)密度是表示單位面積中的傳感器節(jié)點(diǎn)數(shù)量。如果在面積為的區(qū)域中部署個(gè)傳感器節(jié)點(diǎn)，則網(wǎng)絡(luò)節(jié)點(diǎn)密度見(jiàn)(51)： (51)(3)網(wǎng)絡(luò)連通度在WSN中，全部傳感器節(jié)點(diǎn)的鄰居節(jié)點(diǎn)數(shù)的平均值稱為該WSN的網(wǎng)絡(luò)連通度。(4)節(jié)點(diǎn)間的測(cè)量距離通過(guò)RSSI、AOA、TOA、TDOA等技術(shù)測(cè)量所得的傳感器節(jié)點(diǎn)間的距離，稱為節(jié)