【正文】 間向鄰居節(jié)點廣播一個信標信號，信號中包含有錨節(jié)點自身的 ID 和位置信息。當未知節(jié)點在一段偵聽時間內接收到來自錨節(jié)點的信標信號數(shù)量超過某一個預設的門限后，該節(jié)點認為與此錨節(jié)點連通，并將自身位置確定為所有與之連通的錨節(jié)點所組成的多邊形的質心。質心定位算法的最大優(yōu)點是它非常簡單，計算量小，完全基于網(wǎng)絡的連通性，但是需要較多的錨節(jié)點。 DVHop 算法：DVHop 算法是由 和 等人提出的。該算法的原理與經(jīng)典的距離矢量路由算法比較相似。在 DVHop 算法中，錨節(jié)點向網(wǎng)絡廣播一個信標，信標中包含有此錨節(jié)點的位置信息和一個初始值為 1 的表示跳數(shù)的參數(shù)。此信標在網(wǎng)絡中被以泛洪的方式傳播出去，信標每次被轉發(fā)時跳數(shù)都增加 1。接收節(jié)點在它收到的關于某一個錨節(jié)點的所有信標中保存具有最小跳數(shù)值的信標，丟棄具有較大跳數(shù)值的同一錨節(jié)點的信標。通過這一機制，網(wǎng)絡中所有節(jié)點(包括其他錨節(jié)點)都獲得了到每一個錨節(jié)點的最小跳數(shù)值。為了將跳數(shù)值轉換成物理距離，系統(tǒng)需要估計網(wǎng)絡中平均每跳的距離。錨節(jié)點具有到網(wǎng)絡內部其他錨節(jié)點的跳數(shù)值以及這些錨節(jié)點的位置信息，因此錨節(jié)點可以通過計算得到與其他錨節(jié)點的實際距離。經(jīng)過計算，一個錨節(jié)點得到網(wǎng)絡的平均每跳距離，并將此估計值廣播到網(wǎng)絡中，稱作校正值，任何節(jié)點一旦接收到此校正值，就可以估計自己到這個錨節(jié)點的距離。 DVHop 算法與基于測距算法具有相似之處，就是都需要獲得未知節(jié)點到錨節(jié)點的距離，但是DVHop 獲得距離的方法是通過網(wǎng)絡中拓撲結構信息的計算而不是通過無線電波信號的測量。Amorphous 算法：該算法與 DVHop 算法類似。首先，采用與 DVHop 算法類似的方法獲得距錨節(jié)點的跳數(shù)，稱為梯度值。未知節(jié)點收集鄰居節(jié)點的梯度值，計算關于某個錨節(jié)點的局部梯度平均值。與 DVHop 算法不同的是：Amorphous 算法假定預先知道網(wǎng)絡的密度，然后離線計算網(wǎng)絡的平均每跳距離，最后當獲得 3 個或更多錨節(jié)基于復合定位的無線傳感器網(wǎng)絡層次路由協(xié)議設計與實現(xiàn)26點的梯度值后，未知節(jié)點計算與每個錨節(jié)點的距離，并使用三邊測量法和最大似然估計法估算自身位置。APIT 算法：在 APIT 算法中，一個未知節(jié)點從它所有能夠與之通信的錨節(jié)點中選擇 3 個節(jié)點，測試它自身是在這 3 個錨節(jié)點所組成的三角形內部還是在其外部；然后再選擇另外 3 個錨節(jié)點進行同樣的測試，直到窮盡所有的組合或者達到所需的精度。如果未知節(jié)點在某三角形內部，稱此三角形包含未知節(jié)點；最后，未知節(jié)點將包含自己的所有三角形的相交區(qū)域的質心作為自己的估計位置。APIT 算法最關鍵的步驟是測試未知節(jié)點是在 3 個錨節(jié)點所組成的三角形內部還是外部，這一測試的理論基礎是三角形內的點(PIT)測試。原理及過程詳見文獻 [35]。3．2　改進的節(jié)點定位機制正如在前面提到過的，不管采用何種定位方式，無線傳感器網(wǎng)絡的節(jié)點定位通常都是利用傳感器網(wǎng)絡中少量已知位置的節(jié)點來獲得其他未知位置節(jié)點的位置信息，錨節(jié)點位置的布置和選擇將會影響到定位的精度及覆蓋率。當在定位技術中一旦用到錨節(jié)點，那么一個重要的問題就是要設置多少錨節(jié)點以及在什么區(qū)域布置錨節(jié)點。雖然目前已經(jīng)提出各種各樣的技術以期達到錨節(jié)點的最優(yōu)布置，但在大多數(shù)情況下，都會因不可預料的自然環(huán)境影響就引起這樣或那樣的問題，這就要求在節(jié)點定位系統(tǒng)要有必須要有能根據(jù)具體環(huán)境動態(tài)的、自適應的調整定位算法的能力，為此本文提出了基于測距與不測距復合定位方法。3．2．1 問題的提出在基于測距的定位系統(tǒng)中，如果為每個節(jié)點安裝用于發(fā)射測距信號的硬件無疑會增加節(jié)點成本和能源消耗，因此考慮利用基站為所有節(jié)點發(fā)射測距信號，這就要求節(jié)點必須處于基站的測距信號發(fā)射范圍之內。同時，在無線傳感器網(wǎng)絡的應用中，因為地形地貌等環(huán)境因素的影響，不可避免地有部分節(jié)點可能處于測距信號不可達區(qū)域，但節(jié)點仍能通過多跳路由采集數(shù)據(jù)，如果放棄這部分節(jié)點，無疑會縮小探測范圍，如果不放棄這部分節(jié)點，也會因為缺少位置信息造成數(shù)據(jù)的不完整，降低所采集數(shù)據(jù)的可用性。鑒于此，本文提出了基于測距與不測距的復合定位機制。3．2．2 復合定位法在下文提出的復合定位法中，基于測距的定位部分采用了時間差測距法，它的主要思想是：對基站的測距信號范圍之內的節(jié)點，接收由基站發(fā)射兩種速度不一的信號，然后各自計算出自己的位置；對于處于測距范圍之外的節(jié)點，則采用類似 DVHop 的南京航空航天大學碩士學位論文27定位法，通過計算跳數(shù)來確定節(jié)點位置。3．2．2．1　基于測距的定位實現(xiàn)在 3．1．1 一節(jié)中已經(jīng)提到了用于節(jié)點定位的時間差測距方法。為測算未知節(jié)點的位置，至少需要設置三個錨點信源，通過這三個錨點依次向網(wǎng)絡中所有節(jié)點同時發(fā)送兩種速度不一的信號，其中第一個信號為同步起始標識（速度為 V1） ，第二個可為速度較慢的聲波或超聲波（速度為 V2） 。節(jié)點記錄兩個信號到達的時間差值 t，通過公式：Ri＝ (V1V2t)/(V1?V2) ①其中 Ri（i=1,2,3）分別表示三個錨點到該點的距離。通過時間差測距法獲得三個錨點到未知節(jié)點的距離之后，就可對節(jié)點進行目標定位。本文采用常用的三邊(trilateration) 定位。它通過三個以上的點與目標之間的距離來計算目標的坐標位置。在二維空間中，最少需要三個參考點才能唯一確定一點的坐標。如圖 31 所示，節(jié)點 X 的坐標未知，參考點的坐標以及它們到 X 的距離已知。若從 X 到 A、B、C 的距離分別為 RR2 、R3，則 X 位置就是可確定的。圖 31 定位原理圖設錨點坐標分別為：A(x 1,y1),B(x2,y2),C(x3,y3)， (x,y)為目標點 X 的坐標，通過解方程組：　　　　　　　　 (x 1?x)2 +　(y 1?y)2　 =R12(x2?x)2 +　(y 2?y)2　 =R22(x3?x)2 +　(y 3?y)2　 =R32可以得到目標節(jié)點坐標值，為了便于路由計算，將直角坐標轉換成相對于基站的極坐標（ρ, θ） 。為提高測距信號利用率和減少節(jié)點接收信號的能量消耗，在基站廣播的測距信號基于復合定位的無線傳感器網(wǎng)絡層次路由協(xié)議設計與實現(xiàn)28中，已經(jīng)包含了發(fā)射源的位置信息，其數(shù)據(jù)包結構如下：測距起始標識 發(fā)射源 ID 發(fā)射源坐標 發(fā)射時間傳感器節(jié)點在未完成自身定位之前，一直處于偵聽接收狀態(tài)，在收到基站測距的同步起始標識后，打開記時器，同時開啟接收速度較慢的聲波或超聲波信號，在收到聲波或超聲波信號后，計時器停止記時，利用公式①計算出與信源的距離 Ri (i = 3)，然后將 Ri 代入方程組中求解得出節(jié)點的具體位置 （ρ, θ） 。定位過程可分為兩個階段，即信息廣播過程和節(jié)點應答過程。信息廣播過程：信息廣播源為基站中三個位置各異的信號發(fā)射器，各發(fā)射器分別以足夠覆蓋全部節(jié)點的功率發(fā)送一個信息包（速度為 V1）和一測距信號（速度為V2） ，各節(jié)點收到信息包后開始記時，收到測距信號則停止記時，得到時間差值 t。此時間差 t 將通過應答信息包返回到基站?；精@取此數(shù)據(jù)后利用前面提到的定位原理和算法可得到各節(jié)點的具體位置。節(jié)點應答過程：由于節(jié)點的通信能力受限，只有信號有效半徑之內的節(jié)點能收到應答信息包，因此數(shù)據(jù)包需經(jīng)多級傳遞才能到達基站。在一定時間延遲后（確保所有節(jié)點都接收到廣播信息） ，各節(jié)點組織應答信息包的發(fā)送。應答信息包格式為：節(jié)點ID+節(jié)點位置+ 當前節(jié)點能量剩余量(power)＋轉發(fā)信息（子節(jié)點信息） 。為確保最外圍的節(jié)點首先開始發(fā)送應答信息包，為每個節(jié)點設置一個發(fā)送應答信息包的時間延遲值：β－t ，這可保證外圍節(jié)點首先發(fā)送（β 為一常數(shù)） 。鄰接表建立流程如圖 32 所示：　　　開始應答 觸發(fā)器 ＝ 0 ？有應答信息包 ？此信息包是來自外圍節(jié)點 ？將此節(jié)點插入到本節(jié)點鄰接表與發(fā)送緩沖區(qū)中此信息包是來自外圍節(jié)點 ？組織本節(jié)點信息進行信息發(fā)送信道空閑設置隨機退避值退避時間 ＝ 0 ？結束Y e sY e sY e sY e sY e sY e sN oN oN oN oN oN o圖 32　鄰接表建立流程南京航空航天大學碩士學位論文293．2．2．2　基于不測距定位的改進方法對于測距信號輻射區(qū)域外的節(jié)點，采取與 DVHop 算法類似的定位算法。不同于DVHop 算法的是，節(jié)點定位不是從錨節(jié)點開始，而是由未定位節(jié)點以洪泛方式向網(wǎng)絡廣播查找錨節(jié)點的信標，收到信標的非錨節(jié)點記錄此廣播的發(fā)布節(jié)點，繼續(xù)轉發(fā)此信標，直至找到錨節(jié)點。經(jīng)過一段時間的信標轉發(fā)過程，所有與邊緣區(qū)域相鄰的錨節(jié)點均會收到一個或多個查找錨節(jié)點的信標。錨節(jié)點對定位請求作出應答，應答信號中包含錨節(jié)點位置和網(wǎng)絡平均每跳距離，每個未定位節(jié)點在收到兩個以上錨節(jié)點的應答信號后就可給自身定位，確定自身位置后，標記自己為錨節(jié)點，然后再對未定位節(jié)點作出應答。如圖 33 所示，在圖中處于陰影區(qū)域的節(jié)點(F、G、H)是已經(jīng)通過測距定位過程獲ABCDEFGH洪泛消息應答消息圖 33　基于不測距定位示意圖知自身位置的節(jié)點，在陰影區(qū)域外的節(jié)點 A、B、C、D、E 是需進行不測距定位的節(jié)點。節(jié)點 F、G 收到節(jié)點 D 的定位請求后，向 D 發(fā)送攜帶自身位置的應答信號，D 的位置即可確定為以 FG 為底邊，以網(wǎng)內平均每跳距離為邊長的等腰三角形的頂點。以此類推，在 D 與 E 的位置確定之后，可繼續(xù)對 D、E 外圍節(jié)點進行定位。兩點說明：1)從非錨節(jié)點開始發(fā)動定位請求的主要原因是：在本文假設的應用環(huán)境中，大部分節(jié)點已經(jīng)通過測距定位方式獲知自身位置，但這些節(jié)點不能確定自己是否與那些位置仍未確定的節(jié)點相鄰，如果仍從這些位置已經(jīng)確定的錨節(jié)點開始啟動此定位過程，會因為大量數(shù)據(jù)傳輸造成額外的能量消耗?；趶秃隙ㄎ坏臒o線傳感器網(wǎng)絡層次路由協(xié)議設計與實現(xiàn)302)平均每跳的距離是這樣得到的：假設網(wǎng)絡節(jié)點在布置時是服從一樣的分布密度，因此在基于測距定位過程中得到的平均每跳距離同樣也適合于這些位置還未確定的節(jié)點，此距離參數(shù)可由基站根據(jù)已定位節(jié)點位置計算得到。這樣獲得的平均每跳距離可避免由各節(jié)點分別計算每跳距離帶來的誤差和由交換每跳距離帶來的能量損耗，同時可減少由于通信引起的時延，提高組網(wǎng)速度。3．2．2．3 兩種定位算法的融合控制 混合定位法的一個關鍵問題是如何確定哪些節(jié)點是通過測距法來定位，哪些節(jié)點又是通過不測距的方法定位，如果控制不當，網(wǎng)絡節(jié)點不能選擇合適的定位方法，會造成節(jié)點定位和組網(wǎng)失敗?；旌隙ㄎ环鞒倘鐖D 34 所示：南京航空航天大學碩士學位論文31 開始收到測距信標保持一段時間的休眠偵聽狀態(tài)啟動計時器獲取時間差值計算節(jié)點位置信道是否空閑接收其他節(jié)點的位置數(shù)據(jù)發(fā)送接收到的其他節(jié)點和本節(jié)點位置數(shù)據(jù)延時 T 到與否 ( T 是與節(jié)點位置相關的變量 )休眠時間結束進入休眠狀態(tài)信道是否空閑廣播查找錨節(jié)點的信標保持偵聽接收狀態(tài)保存同一節(jié)點跳數(shù)最小的數(shù)據(jù)包本節(jié)點查找錨節(jié)點信標是否發(fā)出等待錨節(jié)點答信號根據(jù)錨節(jié)點位置計算本節(jié)點位置標記自己為錨節(jié)點有查找錨節(jié)點請求發(fā)送帶本節(jié)點位置的應答數(shù)據(jù)包結束Y E SN OY E SY E SY E SY E SY E SN ON ON ON ON ON OY E S發(fā)送攜帶自己位置的應答包有未應答的定位請求嗎Y E SN O圖 34 混合定位算法流程圖 在采用混合定位機制的傳感器網(wǎng)絡中，各節(jié)點均可選擇采取兩種定位方式中的一種，選擇何種定位方式取決于節(jié)點被拋撒到目的地后的地理位置。節(jié)點首先啟動延時觸發(fā)器，在第一個觸發(fā)時間到來時，所有節(jié)點啟動基于測距的定位程序，此時節(jié)點保持對基站測距信號的偵聽狀態(tài)，如果收到基站測距信標則啟動基于測距的定位程序。如果在約定的時間段內不能收到基站測距信標，則表明本節(jié)點處于基站測距范圍之外，需要進行二次定位，即啟動基于不測距的定位程序。二次定位的一個限定條件是在發(fā)動第二次定位之前，必須要有足夠的時間延遲，以確保處于基于測距定位邊緣的節(jié)點(注：與基于不測距的定位節(jié)點相鄰的節(jié)點)位置已經(jīng)確定，否則，基于不測距定位過基于復合定位的無線傳感器網(wǎng)絡層次路由協(xié)議設計與實現(xiàn)32程將會因為找不到錨節(jié)點而失敗。3．3　本章小節(jié)本章對節(jié)點定位的兩大類型作了簡要介紹，并對其中一些定位算法作了分析比較，從算法分析中可以看出，基于測距(Rangebased) 的定位算法能實現(xiàn)相對精確的定位功能，但是大都需要額外地增加硬件開銷，不適用于常規(guī)傳感器網(wǎng)絡的應用場景。而基于不測距(Rangefree)的定位機制則是在無需測量節(jié)點間的絕對距離或方位的情況下能夠提供一般精度要求的位置估計，該技術降低了對節(jié)點硬件的要求，在成本方面比基于測距技術的定位機制具有優(yōu)勢。但不適合于特殊場合（如軍事上對打擊目標的定位等） 。為提高定位系統(tǒng)的適應能力，提出了基于測距與不測距的混合定位方法，此方法可以在保證節(jié)點定位精度的前提下，根據(jù)需要動態(tài)的調整定位算法。南京航空航天大學碩士學位論文33第四章 路由算法分析與改進4．1　無線傳感器網(wǎng)絡路由的特點與要求無線傳感器網(wǎng)絡中，由于網(wǎng)絡內節(jié)點資源有限，數(shù)據(jù)包的傳送需要通過多跳通信方式到達目的地，因此路由選擇算法是網(wǎng)絡層設計的一個主要任務。分析第一章提到的