基于距離和角度信息的無線傳感網(wǎng)節(jié)點定位問題研究.pdf

1、無線傳感器網(wǎng)絡(luò)(wirelesssensornetwork，WSN)節(jié)點定位通常是指在給定或獲取足夠多的鄰節(jié)點之間信息基礎(chǔ)上，準(zhǔn)確地分布式地估算出未知節(jié)點的位置坐標(biāo)。該課題近幾年來一直是WSN的研究熱點，一方面由于節(jié)點位置信息是絕大多數(shù)應(yīng)用所必需的，另一方面，節(jié)點位置信息也是不少網(wǎng)絡(luò)協(xié)議和算法設(shè)計中的支撐信息。雖然已有不少二維平面(2D)中的具體定位方法被提出，但是這一課題的研究進展也存在著明顯的薄弱環(huán)節(jié)。一是缺乏WSN系統(tǒng)可定位性數(shù)學(xué)

2、理論基礎(chǔ)，在實現(xiàn)定位之前節(jié)點的唯一可定位性研究不足，尤其三維空間(3D)的成果就更少;二是還沒有針對無錨節(jié)點環(huán)境狀況下的物理位置定位方法;三是3D中WSN定位方法很有限。為此，本論文利用鄰節(jié)點之間的距離信息和方位角信息，結(jié)合剛性圖理論、組合最優(yōu)化理論和圖形變換理論，對WSN節(jié)點唯一精確定位問題進行較為全面深入地研究，并提出2D和3D的實現(xiàn)算法。
　　 首先，將WSN唯一定位問題轉(zhuǎn)化為對應(yīng)圖的框架的全局剛性判定問題，分析可定位性。

3、從剛性圖的角度，一個無線傳感網(wǎng)可以唯一定位的充分必要條件是，它所對應(yīng)的圖G的映射框架是全局剛性的。全局剛性的弱化情形是剛性，因此在距離約束條件下，首先討論并示例了多種剛性和全局剛性判定定理。由于在3D中全局剛性判定是NP-難的，所以分析了角度約束的優(yōu)點和平行剛性判定定理。進而把距離約束和角度約束聯(lián)合考慮，研究混合框架剛性判定定理。最后通過具體反例，驗證了在3D中Laman條件加3-連通僅是框架剛性的必要條件，而不是充分條件。并在“完全聯(lián)

4、合約束”條件下，提出了全局剛性判定命題，來推進3D中的WSN唯一定位問題研究。
　　 其次，在可定位性分析與判定的啟發(fā)下，利用鄰節(jié)點之間的距離信息和角度信息，設(shè)計分布式輕量級定位算法。具體實現(xiàn)分為四個步驟，包括若干子算法，執(zhí)行流程為先進行系統(tǒng)初始化，再建立節(jié)點本地坐標(biāo)系，然后計算節(jié)點本地坐標(biāo)，最后將局部的本地坐標(biāo)轉(zhuǎn)換為全網(wǎng)唯一的全局坐標(biāo)。2D中的算法稱為uniqueanchor-freelocalizationalgorithm

5、(UAFL)，是不需要錨節(jié)點支持且能物理定位的精細類定位算法。UAFL在本地坐標(biāo)系建立階段，利用角度信息有效地解決了反轉(zhuǎn)分歧（flipambiguilty，F(xiàn)A）。本地坐標(biāo)計算階段，充分考慮了24種不同的拓撲結(jié)構(gòu)，使得待定位節(jié)點只需有1個額外鄰節(jié)點就能進行計算。全局坐標(biāo)轉(zhuǎn)換是重點和難點，采用齊次坐標(biāo)系統(tǒng)一了平移變換和旋轉(zhuǎn)變換矩陣表達形式，并求解了鄰節(jié)點坐標(biāo)系轉(zhuǎn)換矩陣，實現(xiàn)了全局坐標(biāo)計算。在把sink節(jié)點設(shè)定為全局坐標(biāo)系參考原點時，就在無

6、錨節(jié)點輔助情況下實現(xiàn)了物理位置定位。通過數(shù)值計算實例，驗證了UAFL的有效。仿真結(jié)果表明，UAFL在同類算法中具有較好的定位覆蓋率、定位精度等性能。從節(jié)點定位角度看，當(dāng)網(wǎng)絡(luò)密度為9～12時，可以獲得WSN工程部署的最優(yōu)性價比。
　　 注意到很多2D中的定位技術(shù)實際上并不能拓展到3D，總體上3D定位方法很有限，本文根據(jù)UAFL的思路，進一步提出了threedimensionalanchor-freelocalizationalgo

7、rithm(3D-AFL)。從幀格式層面設(shè)計了鄰節(jié)點發(fā)現(xiàn)和本地坐標(biāo)系建立等子算法，利用方位角信息解決了3D中的FA問題。局部坐標(biāo)到全局坐標(biāo)的轉(zhuǎn)換同樣也是3D中的重點和難點，為此，深入分析并求解了鄰接轉(zhuǎn)換矩陣?？梢钥闯?，本文提出的定位方法避免了復(fù)雜計算，屬于輕量級算法實現(xiàn)，完全符合WSN的特性要求。通過仿真，檢驗了3D-AFL的性能，并得出工程部署時比較好的參數(shù)范圍為網(wǎng)絡(luò)密度為11～13。同時發(fā)現(xiàn)，3D定位實現(xiàn)與可定位性判定一樣，具有很大

8、的研究開發(fā)空間，比如采用分簇機制，在全局坐標(biāo)計算環(huán)節(jié)減少轉(zhuǎn)換次數(shù)（跳數(shù)），探索增強網(wǎng)絡(luò)擴展性的方法。
　　 最后，根據(jù)跨層設(shè)計思想，提出了路由-定位聯(lián)合優(yōu)化協(xié)議。由于全局坐標(biāo)轉(zhuǎn)換的目標(biāo)節(jié)點是唯一的sink節(jié)點，并且數(shù)據(jù)匯聚(datagathering)過程中的目標(biāo)節(jié)點也是sink節(jié)點，必然涉及報文路由，因此將跳數(shù)作為路徑長短評價指標(biāo)，設(shè)計跨層優(yōu)化協(xié)議。在不產(chǎn)生廣播風(fēng)暴的情況下，在各節(jié)點建立下一跳綁定表，既是可選的路由機制，又優(yōu)化