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