【正文】 自由空間電波傳播模型，節(jié)點(diǎn)之間的通信能力是對(duì)稱的，而且所有的消息都可以被正確接收。(5) 部分節(jié)點(diǎn)的位置信息已經(jīng)通過(guò)安裝GPS接收器或人工部署的方式確定(即信標(biāo)節(jié)點(diǎn))；(6) 無(wú)線傳感器網(wǎng)絡(luò)的全局時(shí)間是統(tǒng)一的，每個(gè)傳感器節(jié)點(diǎn)都裝備著定時(shí)器。 分簇算法分簇算法可將一個(gè)大型的WSN劃分成多個(gè)區(qū)域并選出各個(gè)區(qū)域中負(fù)責(zé)數(shù)據(jù)的路由轉(zhuǎn)發(fā)同時(shí)管理其簇內(nèi)節(jié)點(diǎn)的簇頭節(jié)點(diǎn)，這樣既能夠保證原有覆蓋范圍內(nèi)的書(shū)籍通信，又在很大程度上節(jié)省了節(jié)點(diǎn)的能量。為了提高本章提出的定位算法的定位性能，在本節(jié)提出了一種適用于本章定位算法的分簇算法。分簇算法分為以下兩大步：第一步 選擇簇頭節(jié)點(diǎn)假定簇內(nèi)各節(jié)點(diǎn)與簇頭節(jié)點(diǎn)間的通信是選擇最短的路徑進(jìn)行的，然而距離簇頭節(jié)點(diǎn)近的節(jié)點(diǎn)除了要將自身的相關(guān)信息傳播給簇頭節(jié)點(diǎn)，點(diǎn)信息轉(zhuǎn)發(fā)給簇頭節(jié)點(diǎn)。假設(shè)簇頭節(jié)點(diǎn)的鄰居節(jié)點(diǎn)平均轉(zhuǎn)發(fā)數(shù)據(jù)總流量為，簇頭的連通度為，簇頭節(jié)點(diǎn)的鄰居節(jié)點(diǎn)平均轉(zhuǎn)發(fā)的數(shù)據(jù)流量：與成反比。由于簇頭節(jié)點(diǎn)既要將簇內(nèi)節(jié)點(diǎn)的相關(guān)信息存儲(chǔ)起來(lái)，又要管理其簇內(nèi)節(jié)點(diǎn)，因此，其通信量及計(jì)算量都會(huì)遠(yuǎn)大于其簇內(nèi)節(jié)點(diǎn)，故簇頭節(jié)點(diǎn)應(yīng)比簇內(nèi)節(jié)點(diǎn)具有更高的能量。于是本文把連通度和殘存能量信息作為選擇簇頭的兩個(gè)主要參數(shù)，首先根據(jù)實(shí)際應(yīng)用預(yù)先設(shè)定節(jié)點(diǎn)能量門限值為，連通度門限值為，假定需要選擇個(gè)簇頭節(jié)點(diǎn)，則具體選擇過(guò)程分以下幾種情況：第一種情況 能量值大于其門限值，且連通度大于門限值作為初選簇頭節(jié)點(diǎn)，如果其數(shù)量大于所需的簇頭節(jié)點(diǎn)數(shù)量，則根據(jù)公式(34)計(jì)算出初選簇頭節(jié)點(diǎn)的綜合性能值，將初選簇頭節(jié)點(diǎn)按照其綜合性能值的大小進(jìn)行從大到小排序。 (34)式中 、——權(quán)值，具體怎么取根據(jù)實(shí)際情況設(shè)定，只要滿足即可。最后選擇其中的前個(gè)節(jié)點(diǎn)作為最終的簇頭節(jié)點(diǎn)。第二種情況 初選簇頭節(jié)點(diǎn)個(gè)數(shù)等于所需的簇頭節(jié)點(diǎn)數(shù)量，則無(wú)需再計(jì)算其綜合性能值，初選簇頭節(jié)點(diǎn)都是最終的簇頭節(jié)點(diǎn)。第三種情況 初選簇頭節(jié)點(diǎn)個(gè)數(shù)為小于所需簇頭節(jié)點(diǎn)數(shù)量，則其余的個(gè)簇頭節(jié)點(diǎn)需則根據(jù)公式(34)計(jì)算出剩余節(jié)點(diǎn)的綜合性能值，將剩余節(jié)點(diǎn)按照其綜合性能值的大小進(jìn)行從大到小排序，選擇其中的前個(gè)節(jié)點(diǎn)作為最終的簇頭節(jié)點(diǎ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)行劃分簇，且相鄰簇間的重疊度為大于2且小于5，因?yàn)槿绻丿B度較大，一個(gè)節(jié)點(diǎn)會(huì)屬于多個(gè)簇，在這些個(gè)簇內(nèi)都需要對(duì)其進(jìn)行定位即需要重復(fù)定位的節(jié)點(diǎn)會(huì)增多，這樣不僅會(huì)降低算法的定位效率，還會(huì)消耗更多珍貴的能量。接下來(lái)闡述上述問(wèn)題的解決方案，為了更直觀些，通過(guò)下面例子進(jìn)行分析。如圖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)行局部定位以便最后一步參與融合算法。對(duì)于剩余的重疊節(jié)點(diǎn)，先比較所屬簇的簇頭節(jié)點(diǎn)的殘余能量的大小，在殘余能量大的簇頭節(jié)點(diǎn)所在簇中進(jìn)行局部定位即可。如圖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完全可以取消。a) 其他兩簇沒(méi)有重疊部分b) 其他兩簇有重疊部分圖31一個(gè)簇中的節(jié)點(diǎn)分別屬于其他兩簇分簇結(jié)束后，同時(shí)屬于多個(gè)簇的節(jié)點(diǎn)起到了簇頭間的連接及求解坐標(biāo)轉(zhuǎn)換參數(shù)的作用。在下面的介紹中將劃分后的簇統(tǒng)稱為局部網(wǎng)絡(luò)。 局部定位分簇完成后，先由成為簇頭的節(jié)點(diǎn)通過(guò)執(zhí)行HopEuclidean算法(該算法是采用距離矢量路由技術(shù)與Euclidean算法相結(jié)合的方法求解節(jié)點(diǎn)間的距離)，獲得簇內(nèi)節(jié)點(diǎn)之間的距離。：HopEuclidean算法。設(shè)節(jié)點(diǎn)的ID為，輸入：由信標(biāo)節(jié)點(diǎn)向所有節(jié)點(diǎn)廣播一個(gè)四元組的消息(自身ID，自身位置信息，初始值為1的跳數(shù)計(jì)數(shù)器，中間節(jié)點(diǎn)ID)；輸出：與節(jié)點(diǎn)本身相隔兩跳內(nèi)的所有信標(biāo)節(jié)點(diǎn)的相關(guān)信息。Begin(1)if neighbour(i)3 then(2) orphan←ture。/*orphan表示是否為孤立的節(jié)點(diǎn)，如果是設(shè)改標(biāo)記為true，否則為false*/(3) end if(4)if anchor==ture then/* anchor表示是否為信標(biāo)節(jié)點(diǎn)，如果是設(shè)該標(biāo)記位為true，否則為false*/(5) Broadcast MSG(ID←i,location←(x1,x2,…xm),hop←1,MNode←,TTL←2)。/*ID表示自身ID，location表示自身位置，hop表示跳計(jì)數(shù)器，Mnode表示中間節(jié)點(diǎn)ID，TTL表示生命周期域*/(6)if node accept this MSG amp。amp。 anchor==ture then(7) if hop==1 then(8) MNode←i,hop++。(9) Broadcast MSG to neighbour。 (10) end if(11) if hop==2,then(12) discard MSG。(13) end if(14) end if(15)if node accept this MSG amp。amp。 anchor==false then(16) if MNode== then(17) Mnode←i,hop++。(18) Broadcast MSG to neighbour。(19) end if(20) if MNode≠ then(21) if node accept this MSG by MNode then(22) discard MSG。 (23) end if(24) end if(25) end ifEnd經(jīng)過(guò)上述算法，未知節(jié)點(diǎn)就可獲得與它相隔兩跳內(nèi)的所有信標(biāo)節(jié)點(diǎn)的相關(guān)信息。通過(guò)式(21)、式(22)、式(23)直接計(jì)算出自身與該信標(biāo)節(jié)點(diǎn)的距離。HopEuclidean算法的具體流程圖如圖32所示。圖32 HopEuclidean算法流程圖根據(jù)上面計(jì)算出的節(jié)點(diǎn)間的距離，建立相對(duì)應(yīng)的MDS所需節(jié)點(diǎn)的距離矩陣，如果網(wǎng)絡(luò)中布設(shè)個(gè)節(jié)點(diǎn)，定義距離矩陣如式(35)所示。 (35)式中 ——節(jié)點(diǎn)與節(jié)點(diǎn)之間的距離。假設(shè)WSN中的傳感器節(jié)點(diǎn)被分布在維空間中，則第個(gè)節(jié)點(diǎn)的待求坐標(biāo)為，那么該網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)的待求坐標(biāo)矩陣為，節(jié)點(diǎn)之間的距離矩陣與之間的關(guān)系可用公式(36)表示。 (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。 求解全局坐標(biāo)上面已經(jīng)求出各節(jié)點(diǎn)在其所在簇即局部網(wǎng)絡(luò)中的相對(duì)坐標(biāo)系統(tǒng)，接下來(lái)根據(jù)下面的坐標(biāo)轉(zhuǎ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)中去。 (39)式中 ——縮放因子；——旋轉(zhuǎn)變換；——平移變換。由此可見(jiàn)，只要求出、和三個(gè)因子的值，就可以將中的節(jié)點(diǎn)坐標(biāo)轉(zhuǎn)換為在的坐標(biāo)。下面根據(jù)局部網(wǎng)絡(luò),重疊的節(jié)點(diǎn)在中的坐標(biāo)與在中的坐標(biāo)進(jìn)行求解、和的值。設(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)矩陣。假設(shè)與中分別有個(gè)節(jié)點(diǎn)。首先將與中節(jié)點(diǎn)的坐標(biāo)擴(kuò)展到三維空間，并且設(shè)第三維的坐標(biāo)值全部為l。令與的中心點(diǎn)分別為、計(jì)算公式見(jiàn)式(310)。 (310)設(shè)，則可通過(guò)式(311)計(jì)算得出。 (311)與的協(xié)方差矩陣可表示為 (312)式中。由計(jì)算矩陣 (313)計(jì)算出的最大特征值對(duì)應(yīng)的特征向量 (314)則旋轉(zhuǎn)變換矩陣可由下式計(jì)算 (315)那么平移變換因子為 (316)由式(39)、式(311)、式(315)、式(316)，就可以把轉(zhuǎn)換為在中的坐標(biāo)矩陣。通過(guò)上面的坐標(biāo)轉(zhuǎn)換方法將離較遠(yuǎn)的局部網(wǎng)絡(luò)中的坐標(biāo)逐漸轉(zhuǎn)換為更靠近的局部網(wǎng)絡(luò)中的坐標(biāo)，這樣以此類推，會(huì)將其他局部網(wǎng)絡(luò)中的坐標(biāo)逐步轉(zhuǎn)換為在局部網(wǎng)絡(luò)中的坐標(biāo)，則最終所有節(jié)點(diǎn)在自身所在局部網(wǎng)絡(luò)的坐標(biāo)都轉(zhuǎn)換為局部網(wǎng)絡(luò)中的坐標(biāo)，該坐標(biāo)就是各節(jié)點(diǎn)的全局坐標(biāo)。 基于HopEuclidean的MDSMAP(D)算法定位過(guò)程在將傳感器節(jié)點(diǎn)部署完成后，讓所有傳感器節(jié)點(diǎn)廣播一個(gè)消息，該消息是一個(gè)三元組，其中ID為自身ID，Location為自身位置信息，若是未知節(jié)點(diǎn)則置為。收到該消息的節(jié)點(diǎn)，首先判斷其跳數(shù)計(jì)數(shù)器的值是否為1，如果是，根據(jù)接收到的信息存儲(chǔ)到其鄰居節(jié)點(diǎn)鏈表中，并將自身的跳數(shù)計(jì)數(shù)器的值加1。如果跳數(shù)計(jì)數(shù)器的值為2，則將接收到的信息存儲(chǔ)到其鄰居節(jié)點(diǎn)鏈表中，并丟棄該消息。這樣通過(guò)發(fā)送和接收該消息，使相隔距離小于兩跳的鄰據(jù)節(jié)點(diǎn)都相互發(fā)現(xiàn)并生成其鄰居節(jié)點(diǎn)鏈表。在定位過(guò)程中，節(jié)點(diǎn)執(zhí)行基于HopEuclidean的MDSMAP(D)定位算法，算法步驟如下：步驟1 節(jié)點(diǎn)首先執(zhí)行分簇算法把網(wǎng)絡(luò)劃分成多個(gè)簇，每個(gè)簇稱為一個(gè)局部網(wǎng)絡(luò)。簇內(nèi)節(jié)點(diǎn)至簇頭的跳數(shù)不超過(guò)2跳。步驟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)。步驟3 根據(jù)坐標(biāo)轉(zhuǎn)換的方法將其局部坐標(biāo)轉(zhuǎn)換為全局坐標(biāo)。步驟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)。 本章小結(jié)本章針對(duì)經(jīng)典MDSMAP算法在計(jì)算未知節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)距離的不足和隨著網(wǎng)絡(luò)規(guī)模的增大，計(jì)算復(fù)雜度及定位誤差的大幅度增加，提出了一種基于HopEuclidean的MDSMAP(D)定位算法。該算法采用距離矢量路由技術(shù)與Euclidean算法相結(jié)合的方法替代經(jīng)典MDSMAP算法中使用最短路徑算法進(jìn)行估計(jì)節(jié)點(diǎn)間的距離。而知道節(jié)點(diǎn)間的最短路徑距離與節(jié)點(diǎn)間的實(shí)際幾何距離是有差別的。此外，MDSMAP算法使用的是經(jīng)典的MDS解法，通常距離矩陣都比較龐大，則會(huì)導(dǎo)致其計(jì)算復(fù)雜度較大，且當(dāng)節(jié)點(diǎn)增加或移動(dòng)時(shí)，需要重新求解，這將會(huì)嚴(yán)重阻礙網(wǎng)絡(luò)的擴(kuò)展。為此，改進(jìn)算法就利用分簇算法將大規(guī)模網(wǎng)絡(luò)進(jìn)行分簇，先進(jìn)行簇內(nèi)節(jié)點(diǎn)的局部定位，然后再利用線性轉(zhuǎn)換的方法將其局部坐標(biāo)轉(zhuǎn)化為全局坐標(biāo)。與此同時(shí)，改進(jìn)算法也有一定的局限性，由于HopEuclidean算法有一定的假設(shè)條件，所以該算法只有在相應(yīng)的假設(shè)條件下，其定位精度才會(huì)有明顯的提高。第4章 分布式加權(quán)多維標(biāo)度算法的改進(jìn)第4章 分布式加權(quán)多維標(biāo)度算法的改進(jìn) 引言近年來(lái)，自多維標(biāo)度技術(shù)應(yīng)用于傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位技術(shù)中以來(lái)，國(guó)內(nèi)大批的研究者都致力于如何提高基于多維標(biāo)度技術(shù)的定位算法在不同規(guī)模、不同的節(jié)點(diǎn)分布密度、不同的拓?fù)浣Y(jié)構(gòu)的網(wǎng)絡(luò)中的定位精度。到目前為止，在保證滿足提高定位精度要求的前提下，只能針對(duì)不同類型的網(wǎng)絡(luò)進(jìn)行研究。比如經(jīng)典的MDSMAP定位算法只適合于規(guī)模較小、節(jié)點(diǎn)分布均勻的傳感器網(wǎng)絡(luò)。為了滿足大規(guī)模、拓?fù)浣Y(jié)構(gòu)不規(guī)則的網(wǎng)絡(luò)的需求，先后又提出MDSMAP(P)算法、Local MDS算法和dwMDS算法等分布式定位算法。但是這些算法仍存在一定的局限性，例如，dwMDS(G)定位算法由于采用的加權(quán)方法是僅與測(cè)距大小相關(guān)的高斯核加權(quán)機(jī)制，則會(huì)受到測(cè)距誤差及網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的影響。因?yàn)榫嚯x近的節(jié)點(diǎn)很有可能其定位誤差較大，這樣則會(huì)造成距離近的節(jié)點(diǎn)的定位誤差在網(wǎng)絡(luò)中不斷擴(kuò)散。該擴(kuò)散現(xiàn)象在網(wǎng)絡(luò)密度分布不均、稀疏及拓?fù)浣Y(jié)構(gòu)不規(guī)則的網(wǎng)絡(luò)中表現(xiàn)更為明顯，從而使得其定位精度下降。為了使得其在密度分布不均勻、稀疏或拓?fù)浣Y(jié)構(gòu)不規(guī)則的網(wǎng)絡(luò)中仍有較高的定位精度，本章提出了一種改進(jìn)方案。不僅對(duì)原有算法中的鄰居選擇機(jī)制與加權(quán)機(jī)制作了修正，而且在原有算法的基礎(chǔ)上引入了最速下降法對(duì)其目標(biāo)代價(jià)函數(shù)進(jìn)行優(yōu)化。 分布式加權(quán)多維標(biāo)度算法 分布式加權(quán)多維標(biāo)度算法概述2005年，美國(guó)Michigan University的JOSE MDS定位算法僅使用0和1兩個(gè)離