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