【正文】 (4)節(jié)點(diǎn)間的測(cè)量距離通過(guò)RSSI、AOA、TOA、TDOA等技術(shù)測(cè)量所得的傳感器節(jié)點(diǎn)間的距離，稱為節(jié)點(diǎn)。(2)網(wǎng)絡(luò)節(jié)點(diǎn)密度在無(wú)線傳感器網(wǎng)絡(luò)中，網(wǎng)絡(luò)的節(jié)點(diǎn)密度是表示單位面積中的傳感器節(jié)點(diǎn)數(shù)量。所以在進(jìn)行實(shí)驗(yàn)前設(shè)置好以下幾個(gè)網(wǎng)絡(luò)參數(shù)即可，在這里先介紹一下幾個(gè)網(wǎng)絡(luò)參數(shù)的定義。它的典型應(yīng)用包括數(shù)據(jù)分析與可視化、數(shù)學(xué)計(jì)算、建模與仿真、科學(xué)及工程繪圖、算法設(shè)計(jì)和應(yīng)用開(kāi)發(fā)等。隨著技術(shù)的不斷發(fā)展，MATLAB能夠方便地用來(lái)解決大部分的的工程及科學(xué)計(jì)算等各方面的問(wèn)題。經(jīng)過(guò)Math Works公司的不斷完善，其功能越來(lái)越強(qiáng)。而仿真軟件中符合這個(gè)特點(diǎn)且簡(jiǎn)單容易實(shí)現(xiàn)的就是數(shù)學(xué)領(lǐng)域常用的功能強(qiáng)大的MATLAB仿真工具，因此，本文就選擇該仿真平臺(tái)對(duì)其算法的性能進(jìn)行分析驗(yàn)證。而本文主要研究的是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é)果即可。如今，已有很多成熟的平臺(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ú)線傳感器網(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)證。最后，為了提高算法的收斂速度，引入了最速下降法對(duì)局部代價(jià)函數(shù)進(jìn)行優(yōu)化。因此，為了使得算法不僅適用于密集型、分布均勻及拓?fù)湟?guī)則的網(wǎng)絡(luò)，而且也適用于稀疏、分布不均、拓?fù)洳灰?guī)則的網(wǎng)絡(luò)，本章主要對(duì)這兩方面提出了改進(jìn)方案。(15) End for(16)Until .End 本章小結(jié)本章重點(diǎn)探討了分布式加權(quán)多維標(biāo)度定位算法通過(guò)分析算法的不足之處提出了改進(jìn)方案。(13) Compute 。(11) Compute from (45)。(6)Repeat:(7) (8) For to (9) Compute the relative location Error 。(4)Change relative map into absolute map to get the initial coordinates。輸入：，；/*為節(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。第五步 ，通過(guò)利用最速下降法對(duì)局部代價(jià)函數(shù)進(jìn)行優(yōu)化，得出各個(gè)局部代價(jià)函數(shù)取最小值時(shí)的相應(yīng)未知節(jié)點(diǎn)的位置坐標(biāo)。第三步 根據(jù)傳感器網(wǎng)絡(luò)中的信標(biāo)節(jié)點(diǎn)的坐標(biāo)信息，將初始化的全局相對(duì)坐標(biāo)轉(zhuǎn)換為絕對(duì)坐標(biāo)。 改進(jìn)算法的定位過(guò)程改進(jìn)算法定位的具體過(guò)程分為以下幾步：第一步 每個(gè)節(jié)點(diǎn)先采用經(jīng)典MDS算法構(gòu)建初始的局部坐標(biāo)系，由于在上一章中已經(jīng)對(duì)經(jīng)典MDS基本原理作了詳細(xì)的介紹，此處就不做具體的介紹了。 (411)式中 (412) (413) (414)本文采用二次插值的方式進(jìn)行線性搜索，設(shè)在，處的函數(shù)值分別為，利用二次插值可求得式(415)。選擇迭代步長(zhǎng)的方法就是使得目標(biāo)函數(shù)最小，計(jì)算公式見(jiàn)式(413)。由于是最小化目標(biāo)函數(shù)，則需以負(fù)梯度方向作為優(yōu)化算法的下降方向，其表達(dá)式見(jiàn)式(411)。在數(shù)值分析中，迭代優(yōu)化方法的基本思想是：給定初始點(diǎn)，得到一系列的點(diǎn)，當(dāng)時(shí)，為式(48)取最小值時(shí)的最優(yōu)解，迭代公式見(jiàn)式(410)。 (49)由上述關(guān)系式可以看出，當(dāng)每個(gè)取最小值時(shí)，就會(huì)取得最小值，則可以通過(guò)最小化每個(gè)未知節(jié)點(diǎn)的局部代價(jià)函數(shù)還獲取相應(yīng)未知節(jié)點(diǎn)的位置坐標(biāo)。 (47)其中是與節(jié)點(diǎn)坐標(biāo)無(wú)關(guān)的常量，為每個(gè)未知節(jié)點(diǎn)的局部代價(jià)函數(shù)，其表達(dá)式見(jiàn)式(48)。 (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ì)算公式如下：。 (45)式中 ——采用鄰居加權(quán)機(jī)制選擇出的未知節(jié)點(diǎn)的鄰居節(jié)點(diǎn)的個(gè)數(shù)——節(jié)點(diǎn)相對(duì)節(jié)點(diǎn)的誤差?；谶@一點(diǎn)，可以看出權(quán)值應(yīng)該與相對(duì)誤差成反比，于是本文將按式(45)對(duì)相對(duì)誤差的倒數(shù)作歸一化處理后的值作為權(quán)值。 (44)步驟3 將相對(duì)誤差大于預(yù)設(shè)的相對(duì)誤差的門限值的鄰居節(jié)點(diǎn)去除，使用剩余的可信度較高的鄰居節(jié)點(diǎn)參與定位計(jì)算。(2) 使用式(43)將定位誤差歸一化處理。自適應(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ì)上述分布式加權(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)化。此外，分布式加權(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)定位。因?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ò)散。其中，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)。(6) 對(duì)初始的全局絕對(duì)坐標(biāo)作為迭代的初始值進(jìn)行迭代優(yōu)化，以獲得最終的全局絕對(duì)坐標(biāo)。(4) 根據(jù)網(wǎng)絡(luò)的局部屬性，讓未知節(jié)點(diǎn)選取其真正的1跳鄰居節(jié)點(diǎn)來(lái)參與定位求解。(2) 利用增量貪婪法將所有節(jié)點(diǎn)的初始局部坐標(biāo)轉(zhuǎn)換為全局相對(duì)坐標(biāo)。(4) 由于只是1跳鄰居節(jié)點(diǎn)參與定位，因此適用于拓?fù)浣Y(jié)構(gòu)規(guī)則的密集型網(wǎng)絡(luò)。(2) 利用自適應(yīng)2步鄰居選擇機(jī)制，使得受測(cè)距粗差影響的鄰居選擇的負(fù)偏效應(yīng)減小。 分布式加權(quán)多維標(biāo)度算法 分布式加權(quán)多維標(biāo)度算法概述2005年，美國(guó)Michigan University的JOSE MDS定位算法僅使用0和1兩個(gè)離散權(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)。為了使得其在密度分布不均勻、稀疏或拓?fù)浣Y(jié)構(gòu)不規(guī)則的網(wǎng)絡(luò)中仍有較高的定位精度，本章提出了一種改進(jìn)方案。因?yàn)榫嚯x近的節(jié)點(diǎn)很有可能其定位誤差較大，這樣則會(huì)造成距離近的節(jié)點(diǎn)的定位誤差在網(wǎng)絡(luò)中不斷擴(kuò)散。為了滿足大規(guī)模、拓?fù)浣Y(jié)構(gòu)不規(guī)則的網(wǎng)絡(luò)的需求，先后又提出MDSMAP(P)算法、Local MDS算法和dwMDS算法等分布式定位算法。到目前為止，在保證滿足提高定位精度要求的前提下，只能針對(duì)不同類型的網(wǎng)絡(luò)進(jìn)行研究。與此同時(shí)，改進(jìn)算法也有一定的局限性，由于HopEuclidean算法有一定的假設(shè)條件，所以該算法只有在相應(yīng)的假設(shè)條件下，其定位精度才會(huì)有明顯的提高。此外，MDSMAP算法使用的是經(jīng)典的MDS解法，通常距離矩陣都比較龐大，則會(huì)導(dǎo)致其計(jì)算復(fù)雜度較大，且當(dāng)節(jié)點(diǎn)增加或移動(dòng)時(shí)，需要重新求解，這將會(huì)嚴(yán)重阻礙網(wǎng)絡(luò)的擴(kuò)展。該算法采用距離矢量路由技術(shù)與Euclidean算法相結(jié)合的方法替代經(jīng)典MDSMAP算法中使用最短路徑算法進(jìn)行估計(jì)節(jié)點(diǎn)間的距離。步驟4 當(dāng)網(wǎng)絡(luò)中有足夠的信標(biāo)節(jié)點(diǎn)時(shí)，前一步執(zhí)行完后，可以得到每個(gè)信標(biāo)節(jié)點(diǎn)通過(guò)MDS技術(shù)估算出的相對(duì)坐標(biāo)，根據(jù)估算出的信標(biāo)節(jié)點(diǎn)坐標(biāo)與原本已知的坐標(biāo)關(guān)系，能夠找到一個(gè)線性變換關(guān)系式，然后利用該線性變換關(guān)系式將相對(duì)坐標(biāo)系統(tǒng)轉(zhuǎn)化為絕對(duì)坐標(biāo)系統(tǒng)。步驟2 在各個(gè)局部網(wǎng)絡(luò)中采用HopEuclidean方法求出局部網(wǎng)絡(luò)中各節(jié)點(diǎn)間的距離，然后由各簇頭節(jié)點(diǎn)利用所得的節(jié)點(diǎn)間距離，通過(guò)執(zhí)行MDS定位算法計(jì)算局部網(wǎng)絡(luò)中節(jié)點(diǎn)的相對(duì)坐標(biāo)。在定位過(guò)程中，節(jié)點(diǎn)執(zhí)行基于HopEuclidean的MDSMAP(D)定位算法，算法步驟如下：步驟1 節(jié)點(diǎn)首先執(zhí)行分簇算法把網(wǎng)絡(luò)劃分成多個(gè)簇，每個(gè)簇稱為一個(gè)局部網(wǎng)絡(luò)。如果跳數(shù)計(jì)數(shù)器的值為2，則將接收到的信息存儲(chǔ)到其鄰居節(jié)點(diǎn)鏈表中，并丟棄該消息。 基于HopEuclidean的MDSMAP(D)算法定位過(guò)程在將傳感器節(jié)點(diǎn)部署完成后，讓所有傳感器節(jié)點(diǎn)廣播一個(gè)消息，該消息是一個(gè)三元組，其中ID為自身ID，Location為自身位置信息，若是未知節(jié)點(diǎn)則置為。由計(jì)算矩陣 (313)計(jì)算出的最大特征值對(duì)應(yīng)的特征向量 (314)則旋轉(zhuǎn)變換矩陣可由下式計(jì)算 (315)那么平移變換因子為 (316)由式(39)、式(311)、式(315)、式(316)，就可以把轉(zhuǎn)換為在中的坐標(biāo)矩陣。 (310)設(shè)，則可通過(guò)式(311)計(jì)算得出。首先將與中節(jié)點(diǎn)的坐標(biāo)擴(kuò)展到三維空間，并且設(shè)第三維的坐標(biāo)值全部為l。設(shè)為中的節(jié)點(diǎn)在中的坐標(biāo)矩陣(每行一個(gè)節(jié)點(diǎn))，其第個(gè)節(jié)點(diǎn)的行向量用表示；為中的節(jié)點(diǎn)在中的坐標(biāo)矩陣，為第個(gè)節(jié)點(diǎn)的行向量；為屬于局部網(wǎng)絡(luò)但不屬于即中的節(jié)點(diǎn)在中的坐標(biāo)矩陣。由此可見(jiàn)，只要求出、和三個(gè)因子的值，就可以將中的節(jié)點(diǎn)坐標(biāo)轉(zhuǎn)換為在的坐標(biāo)。設(shè),，為三個(gè)局部網(wǎng)絡(luò)，其中擁有的節(jié)點(diǎn)最多即其連通度最大，比更靠近，表示局部網(wǎng)絡(luò)中的節(jié)點(diǎn)，如果包含3個(gè)以上的節(jié)點(diǎn)，使用式(39)的變換把中的節(jié)點(diǎn)坐標(biāo)變換到的坐標(biāo)系統(tǒng)中去。 (36)由公式(36)可以看出是對(duì)稱的正半定矩陣，則可以通過(guò)奇異值分解法將其分解為的形式，將其特征值從大到小排列后組成對(duì)角線矩陣，而是列向量為特征向量的正交矩陣，取前個(gè)特征值構(gòu)成，V中前個(gè)特征向量構(gòu)成，可以表示成： (37)由式(36)和式(37)可得維主軸坐標(biāo)解見(jiàn)(38)； (38)式(38)中就是整個(gè)無(wú)線傳感器網(wǎng)絡(luò)的相對(duì)坐標(biāo)系統(tǒng)，到此為止也就計(jì)算出了局部相對(duì)坐標(biāo)系統(tǒng)中的坐標(biāo)矩陣X。 (35)式中 ——節(jié)點(diǎn)與節(jié)點(diǎn)之間的距離。HopEuclidean算法的具體流程圖如圖32所示。 (23) end if(24) end if(25) end ifEnd經(jīng)過(guò)上述算法，未知節(jié)點(diǎn)就可獲得與它相隔兩跳內(nèi)的所有信標(biāo)節(jié)點(diǎn)的相關(guān)信息。(18) Broadcast MSG to neighbour。amp。 (10) end if(11) if hop==2,then(12) discard MSG。 anchor==ture then(7) if hop==1 then(8) MNode←i,hop++。/*ID表示自身ID，location表示自身位置，hop表示跳計(jì)數(shù)器，Mnode表示中間節(jié)點(diǎn)ID，TTL表示生命周期域*/(6)if node accept this MSG amp。Begin(1)if neighbour(i)3 then(2) orphan←ture。：HopEuclidean算法。在下面的介紹中將劃分后的簇統(tǒng)稱為局部網(wǎng)絡(luò)。如圖31 b)所示，簇2中的所有節(jié)點(diǎn)都分別屬于簇1和簇3，如節(jié)點(diǎn)113既在簇1中又在簇2中，節(jié)點(diǎn)111115既在簇2中又在簇3中，如果按正常的處理方式，這9個(gè)節(jié)點(diǎn)都需進(jìn)行兩次定位，這樣就會(huì)造成的重復(fù)定位，既浪費(fèi)時(shí)間又浪費(fèi)能量，像這樣的情況簇2完全可以取消。如圖31 a)所示，簇2中的所有節(jié)點(diǎn)都分別屬于簇1和簇3，如節(jié)點(diǎn)113既在簇1中又在簇2中，節(jié)點(diǎn)1115既在簇2中又在簇3中，如果按正常的處理方式，這九個(gè)節(jié)點(diǎn)都得進(jìn)行兩次定位，這樣就會(huì)造成的重復(fù)定位，既浪費(fèi)時(shí)間又浪費(fèi)能量，從表面上看此時(shí)的簇頭節(jié)點(diǎn)2可以取消，但是由于簇1與簇3沒(méi)有重疊的部分，所以此時(shí)的簇2還必須保留，只是定位時(shí)，如果重疊度大于5，則從重疊的節(jié)點(diǎn)中選擇2個(gè)在兩個(gè)簇中都進(jìn)行局部定位以便最后一步參與融合算法。第二步 劃分簇由于本文計(jì)算簇內(nèi)節(jié)點(diǎn)間的距離時(shí)所采用的方法可以直接計(jì)算出相隔兩跳的節(jié)點(diǎn)間的距離，而且考慮到后面通過(guò)局部定位求出的局部坐標(biāo)需要通過(guò)融合算法轉(zhuǎn)換為全局坐標(biāo)，所以相鄰簇之間應(yīng)擁有相應(yīng)的重疊度，因此為了提高本章定位算法的性能，將上一步選擇出的簇頭節(jié)點(diǎn)的兩跳鄰居節(jié)點(diǎn)作為其從節(jié)點(diǎn)來(lái)進(jìn)行劃分簇，且相鄰簇