基于空間角度傳遞的多跳AOA三維定位算法研究與在地形建模上的應用*

夏 明，毛科技，何文秀，趙小敏，方碩瑾，陳慶章

(浙江工業大學計算機科學與技術學院，杭州 310023)

無線傳感器網絡(Wireless Sensor Network，WSN)技術是隨著經濟和社會發展而誕生的產物，是本世紀最具有影響力和改變人類未來生活方式的高技術領域四大支柱產業之一［1］。網絡中大部分節點的位置是未知的［2］，而節點的隨機分布和感知信息對位置的依賴，使得節點自身的準確定位是一個極其重要的條件。隨著物聯網的發展，把地形建模的能力加入傳感器節點中，以輔助構建部署環境的地形模型，將對WSN的應用價值起到至關重要的作用。不管是軍事應用環境，還是易發生自然災害或遭受自然災害破壞且人員無法到達的環境，如果能夠利用節點位置信息進行地形建模，將有效地幫助相關工作的順利開展。因此，研究三維定位并將此應用于地形建模上是有必要的、有價值的。

1 研究背景

現階段，科研工作人員已經提出了一些三維定位 算 法，如 DCP3D［3］、Landscape-3D［4］、APIT-3D［5］、基于 SVM 的三維定位［6］、DFP 聲源定位［7］等。常見的定位方法主要分為基于距離的定位和距離無關的定位兩種。一般情況下［8］，基于距離的定位技術在定位精確度上要優于距離無關的定位技術，雖然需在節點上額外配備硬件設備，增加了成本和能耗，但定位精度一般要高很多。而在基于距離的定位技術中，采用測角技術得到的數據要比測距技術更準確，穩定性更好。因此，本文將在基于AOA(Angle Of Arrival，信號到達角度)定位的基礎上進行研究。

DV-Hop定位算法［9］是由D Niculescu和B Nath等人提出的一個基于距離無關的多跳定位算法。DV-Hop三維定位算法是DV-Hop在三維場景中的自然運用，只需用三維坐標代替二維坐標即可。該算法思想比較簡單，且容易實現，但是它采用區域的質心作為節點的位置坐標，必將導致定位精度不理想，且隨著跳數的增大，造成的誤差將變大。

Hady S.Abdel Salam和Stephan Olariu利用基于可升降式天線的信標節點和RSSI測距技術提出了一種具有地形建模能力的三維定位算法［10］。它的關鍵在于每個信標節點都配備了一個帶有可移動的全向天線，必要的時候，天線可以上升或者下降幾米的距離。該算法的優點是利用信標節點升降式天線的特性，巧妙地計算了節點的高度和二維坐標，算法整體復雜度相對較低。但存在的缺點是對信標節點的要求較高，需要具備升降功能的天線，提高了成本，且在某些特定的應用中并不適用，如在室內三維傳感器網絡、水下傳感器網絡中等。因此，該算法的適用范圍比較小。

1.1 三維定位問題

針對不同的應用問題，國內外學者提出了各種二維定位算法，如D Niculescu和B Nath的APS自組網定位算法［11］，Srdjan Capkum 等人的 SPA算法［12］等。然而傳感器節點往往被部署在三維空間中，因此確定其空間位置的過程就是無線傳感器網絡節點的三維定位。目前針對三維空間節點定位的研究還比較少，但對它的需求卻日益迫切，是發展物聯網亟待研究的重要課題之一，也是WSN領域的核心問題之一［13］。較二維定位而言，三維空間節點定位必然有一定的區別，主要包括以下幾點:

(1)定位所需的信標節點增加。通常情況下，一個未知節點的二維定位需要三個信標節點，而三維定位則需要四個或者以上的信標節點才能實現。

(2)地形障礙對傳輸信號產生的影響。在三維空間中，地形障礙將帶來非視距傳輸對信號造成的影響。

(3)不能滿足特殊應用的需求。針對特殊應用場合的節點三維定位，如易發生地震的區域、易發生雪崩的雪山、地質活動較活躍的火山口等，定位結果必須能夠準確反映出節點所處的位置，以幫助工作人員更好地了解這些危險地帶正在發生的狀況。

2 基于空間角度傳遞的多跳AOA三維定位算法的設計

假設網絡中所有節點都存在一個表示自身正方向的主軸，通常為節點上兩個接收機連線的中垂線。利用主軸可估計鄰居節點相對于自身的方位角，即鄰居節點發送數據的方向。這樣就可以使用兩個信標節點和它們分別與待定位節點形成的方位角即可獲得待定位節點的平面位置信息。同理，如果假設信標節點不僅具有測定在x-y平面上信號到達角度的能力，同時還擁有測定信號到達俯仰角度的能力，則可通過這一新增加的變量實現在三維空間中對未知節點的定位。本文稱該方法為簡單AOA三維定位算法，并在此基礎上，根據提高節點定位覆蓋率的要求，提出了基于空間角度傳遞的多跳AOA三維定位算法MSAT3D AOA(Multi-hop Three Dimensional AOA With Space-based Angle Transmission)。

2.1 角度傳遞的原理

基于AOA的多跳定位思想最早是由D Niculescu和B Nath為解決Ad-Hoc網絡路由算法需要對節點進行定位所提出的［15］，其核心技術是使待定位節點通過其它相鄰節點角度傳遞的方式，獲得在其直接通訊范圍之外信標節點方位角信息的能力。如圖1所示，L是信標節點，A，B，C均為相鄰的未知節點且均有測量信號到達角度的能力。假設節點B和C均已測得其與節點L間的方位信息，同時也互相測得對方的方位信息及節點A分別與B，C之間的方位信息，則ΔABC和ΔLBC的所有內角便均可計算并確定，四邊形ABCL的形狀及其對角線與各邊所形成的夾角也能確定，則節點A最終可通過這些角度信息并利用正弦定理等數學方法獲得節點L與其主軸所形成的夾角，即確定了節點A和在其直接通信范圍外的節點L之間的方位角信息。

圖1 角度傳遞示意圖

2.1.1 三維空間中的角度傳遞定義

由于本文涉及的定位是在三維立體空間中進行的，因此，節點間角度傳遞也需要在同樣的條件下進行。角度傳遞分為x-y平面上所形成的平面角和相對與x-y平面所形成的俯仰角兩部分。其中，平面角取值范圍為0°～360°，以x軸正方向為基準方向；俯仰角則為－90°～90°，以與x-y平面平行為基準方向。

如圖2，A，B，C為具備三維空間中信號到達角度測量能力、自身位置未知且兩兩相鄰(可直接通信)的未知節點，L為只裝備了全向天線(不具備信號到達角測量能力)的信標節點，其中A為待定位節點。

圖2 三維空間圖

2.1.2 三維空間中X-Y平面上的角度傳遞

圖2 中，A'，B'，C'，L'分別為A，B，C，L在x-y平面上的投影位置，其投影所形成的各點關系如圖3所示。在圖3中，可以由節點上的測角設備直接測出角度大小的角為∠B1，∠B2，∠C1，∠C2和∠B'A'C'。另外我們還定義∠A'為∠B'A'C'，∠B'為∠A'B'L'，∠C'為∠A'C'L'。

圖3 節點在x-y平面上的投影

求解式(1)即可得到∠A1和∠A2。通過∠A1或∠A2與A'B'或A'C'的方位角信息相加減即可得到A'L'與絕對參考方向所成的方位角，即節點A得到了與其直接通信范圍之外的節點L的方位角信息。由于在空間中這4個節點的位置關系不同，因此其在x-y平面上投影的位置關系除圖3所示情況外還有5種，這里不再介紹。各節點處于不同位置關系時，各個角度之間的關系也會發生變化，而這也決定了如何通過測量和計算出來的角度來推出未知節點A與其直接通信范圍之外的信標節點L的方位角信息。

2.1.3 三維空間中俯仰角度的傳遞

圖4為圖2中節點在由ALL'三點所組成的平面上的投影，由空間解析幾何知識可以證明，該平面垂直于x-y平面。在圖4中，我們定義B'和C'分別為節點B和節點C在ALL'平面上的投影點。

圖4 節點在ALL'所在平面上的投影

節點感知信號三維到達角度的能力來自其所能測量的相對與x-y平面的俯仰角，但單獨使用兩個信號到達方位的俯仰角是無法判斷這兩個角在ALL'平面上的投影所形成的夾角的，所以本文在此處采用§2.1.2中所述x-y平面上對應投影角度關系，對投影在ALL'平面上的俯仰角進行分類。下面以節點A，B和C之間的位置關系為例說明如何采用此種方法對俯仰角度進行分類并計算在ALL'平面上的投影俯仰角間形成的夾角。

完成以上工作后，則可開始計算圖4中各已知角和各節點測得俯仰角的關系如式(2)所示。至此，節點A便能通過上述方法，利用節點B和C與自身和節點L的角度關系，獲得節點L關于自身的三維方位角。需特別指出的是，節點A，B，C，L在平面ALL'上的投影理論上也存在和x-y平面的投影一樣，有6種角度位置關系，由于平面ALL'上的A，L點并非投影點，而是節點本身的位置，因此線段AL的長度即為兩個節點間的實際距離，又由于投影在ALL'平面上的其它線段，其投影前本身的真實距離必定大于其投影線段的距離，因此在ALL'平面上凡是有可能出現有比AL長的其它線段的情況即為不可能出現之情況。

2.2 算法描述

MSAT3D AOA的核心思想是根據兩個信標節點與待定位節點之間形成的兩個方位角，及方位角與信標節點分別構成的兩條直線方程來確定待定位節點坐標的，并在此基礎上，融合了角度傳遞思想，通過獲取無線射頻范圍外的信標節點相對于自身的方位角，實現了待定位節點利用通信范圍外的信標節點進行定位的方法。

MSAT3D AOA分為參數配置和實際操作兩部分。定位運行過程中需要使用的一些相關參數，必須預先寫入所有節點，包括:(1)跳數閾值HopMax，指待定位節點通過角度傳遞獲取若干跳數外信標節點信息時所能使用的最大值，可視網絡規模、節點密度等情況而定；(2)手動設置或GPS獲取信標節點坐標；(3)初始化未知節點，通過自身電子羅盤確定主軸方向與絕對參考方向(如正北方向)所成的角度關系，便于在全局坐標系中對節點位置進行計算，本文假設該坐標的x軸所指方向為正北方向，z軸正方向指向地心的相反方向。

根據MSAT3D AOA的操作順序，可將定位過程歸納為以下5個步驟:

步驟1，初始化網絡中的節點信息。所有節點都向鄰居節點廣播發送信息包，通過節點間信息的交換，建立“鄰居信標節點信息表”和“鄰居節點信息表”。

步驟2，滿足條件的未知節點定位。若未知節點“鄰居信標節點信息表”內記錄數大于等于2，則用簡單AOA三維定位算法進行定位，并將結果報給網絡中的信標節點或匯聚節點，然后執行步驟3，若記錄數小于2則直接執行步驟3。

步驟3，跳數閾值HopMax的判斷。首先將存儲在節點上的HopMax減1，若HopMax小于等于0，則停止，并將未知節點轉入休眠狀態，否則執行步驟4。

步驟4，未知節點間信標節點信息的互換。對于“鄰居信標節點信息表”中記錄數小于2的未知節點而言，已知條件無法滿足自身的定位需求，必須通過向網絡中鄰居節點請求更多有用的信息。發出“信標節點信息”請求數據包的未知節點接收到各鄰居節點發送過來的信息后，將這些信息存入“鄰居節點的鄰居信標節點信息表”中。

步驟5，分析“鄰居節點的鄰居信標節點信息表”。未知節點依次檢查表中出現的信標節點，若某一信標節點記錄數小于2，則放棄，并檢查，否則，執行步驟6。如果所有信標節點均已處理，則返回步驟2。

步驟6，獲取直接通信范圍外的信標節點信息。對“鄰居節點的鄰居信標節點信息表”中所有具有同一個信標節點記錄中的鄰居節點排列組合，并選擇其中兩條記錄，發送至數據分組中指定的兩個鄰居節點，鄰居節點接收到該數據分組后，首先檢查分組中另一個鄰居節點是否存在于自身的“鄰居節點信息表”中，若不存在，則返回“數據無效”信號給該數據分組的未知節點。然后未知節點執行排列組合中的下一個組合。如果所有組合都產生“數據無效”信號，則返回步驟5。若存在，則返回“數據有效”信號。然后未知節點對未知節點、兩個鄰居節點和它們共同的鄰居信標節點使用角度傳遞，確定該信標節點對應于未知節點的方位角和俯仰角，并將該信標節點標識號、三維坐標及角度信息存入“鄰居信標節點信息表”。

3 仿真實驗與分析

本文在MATLAB下仿真實驗，并與DV-Hop三維定位算法進行比較。假設在一個100 m×100 m×100 m的三維區域內隨機部署100個節點。為使實驗結果更加精確，本文采用統計的方法，對相同網絡參數設置的實驗仿真50次并取平均。對同一網絡參數設置的不同算法的實驗，均采用節點部署情況相同的數據進行比較。主要的性能指標有:(1)定位誤差率，指可定位節點估算坐標與真實坐標的距離誤差平均值；(2)定位覆蓋率，指可定位節點在所有未知節點中的百分比；(3)不良節點比例，指不良節點占所有可定位節點的百分比，其定位誤差大于節點通信的節點。

3.1.1 算法本身性能的實驗結果與分析

本實驗分別測試在不同跳數閾值和通信半徑下MSAT3D AOA的各種性能。節點通信半徑(Range)設定為35m，信標節點比例在5% ～30%間變化，分別測量跳數閾值為3和5的情況和通信半徑為30、35和40且跳數閾值為3的情況下未知節點定位誤差率、定位覆蓋率、不良節點比例的變化情況。

圖5(a)中定位誤差率均隨信標節點比例增加而大幅下降，這是由于未知節點獲得直接信標節點比例和小跳數范圍內信標節點比例隨信標節點比例大大增加，而跳數閾值變化過大會導致更多誤差被引入，造成定位精度下降，所以未知節點獲得直接信標節點比例和小跳數范圍內信標節點比例的增加能夠顯著提高定位精度，進而減少定位誤差率。整體上看，所有節點的平均定位誤差增加了，但是幅度在可控范圍內，不會導致算法整體性能的大幅下降。圖5(d)中定位誤差率并沒有隨節點通信半徑的減小而大幅增加。Range為30時，在信標節點比例較低時都只比30和35的情況高5%左右，而當信標節點比例增加后，其差別也越來越小。由此得出通信半徑在部署區域和節點總數一定的情況下與節點密度成正比，通信半徑越小，相當于節點密度下降，此時多跳定位占總定位比例不斷提高。因此，在節點密度下降時定位誤差率不會有顯著的上升。

定位覆蓋率上，如圖5(b)，受信標節點比例和跳數閾值的影響并不大，均能使之維持在較高的水平。圖5(e)中，定位覆蓋率隨通信半徑的增加得到了顯著的提高，即使在Range為30時，也能達到60%以上，由此得到算法在低節點密度(即低通信半徑的條件下)依然擁有非常好的定位覆蓋率，且通信半徑的小幅度提高即能大幅度的提高定位覆蓋率。同時可以看到，在Range達到35以上后有非常好的定位覆蓋率指標，且信標節點比例可以維持在一個較小水平上。

圖5(c)和圖5(f)中，不良節點比例均維持在一個較低水平。由于產生不良節點的原因很多，而在仿真環境下主要是因為隨機噪聲的加入使得算法在處理一些邊界情況時發生了難以預料的狀況而導致的，而此類節點的定位誤差一般都會遠遠大于算法整體的平均定位誤差，由此可以得出正常定位的節點的誤差相對整體的平均誤差要更小，定位的精度要更好。同時，隨著通信半徑的減小，不良節點率并未發生顯著上升，因此，也證明了算法在小通信半徑條件下依然具有良好的定位精度。

圖5 MSAT3D AOA算法仿真實驗結果圖

在定位誤差率上，如圖6(a)，本文提出的測距有關的MSAT3D AOA遠好于距離無關的DV-HOP。另外，MSAT3D AOA在信標節點比例為5%時的定位誤差率要領先DV-HOP中比例為30%時的定位誤差率達10個百分點以上。因此，從定位誤差或定位精確度的角度上說，MSAT3D AOA比DV-HOP表現得更好。

圖6 仿真結果對比圖

在定位覆蓋率上，如圖6(b)，MSAT3D AOA雖然略低于DV-HOP，但是基本都處于90%以上，已經達到了非常優秀的水平。此外，通過比較信標節點比例在10%以下的情況可以看到，MSAT3D AOA的定位覆蓋率要稍優于DV-HOP，即在信標節點比例非常低的情況下也能達到較好的定位覆蓋率。

在不良節點比例上，如圖6(c)，與DV-HOP相比，MSAT3D AOA在信標節點比例較低的情況下表現的非常優異，且不會隨信標節點比例的減少而顯著增加。由此可知，DV-HOP在信標節點比例較少時具有非常高的不良節點比例是因為在多跳定位過程中多次估計所造成的誤差積累非常大，導致最終的定位結果偏離真實位置的量也隨之增大。而MSAT3D AOA產生不良節點的原因雖然也有多跳定位產生誤差積累的因素存在，但其主要原因還是噪聲的加入使得算法在處理一些邊界情況時發生了難以預料的狀況而導致的，而這種情況出現的概率非常低。因此，MSAT3D AOA在信標節點比例低的情況下也能有非常低的不良節點比例。

4 算法在地形建模中的應用

4.1 基于Delaunay三角剖分的地形建模

本文使用Delaunay三角剖分構建三角網實現基于WSN的部署環境地形建模。Delaunay三角剖分算法包括逐點插入法、分治法和三角網生長法3類。在數據量不是特別大時，一般使用最簡單的、占用內存少的逐點插入法建立Delaunay三角網。逐點插入法［16］的基本步驟:(1)假設一個初始凸多邊形，使其能包含點集中的所有點，如傳感器節點；(2)在該凸多邊形中構建Delaunay三角網，重復步驟3和步驟4，一次增加一個點，直到遍歷整個點集；(3)計算包含新插入點N的外接圓對應的三角形，稱為影響三角形；(4)將影響三角形的公共邊刪除，并把點N與所有影響三角形的頂點相連，實現點N的插入并保證生成的是Delaunay三角形。

4.2 算法應用于地形建模的結果分析與比較

定位完成后，利用節點x-y坐標值形成在三維空間中x-y平面上的點，使用Delaunay逐點插入法構建連續的三角形網，并以此為基礎對所處環境地形建模。當在三角形的每一個頂點加入節點的z坐標值后，三角形網中每一個三角形便代表了空間中的一個面片，而這些面片所組成的圖形即為該無線傳感器網絡部署環境的地形模型。圖7是一個WSN部署環境的地形模型。假設在一個100 m×100 m×100 m立方體空間內部署500個節點，其中信標節點比例5% ～30%，通信范圍為40 m，使用式(3)表示自然的地形形狀數學模型。

為模擬圖7，本文在MATLAB下實驗。首先部署未知節點和信標節點，并使用MSAT3D AOA定位。然后，使用Delaunay三角剖分構建三角形網，如圖8所示。對于地形建模誤差TME(Terrain Modeling Error)，可以用式(4)表示，其中，zi是節點i的實際高度，z'i為節點i的估計高度。

圖9為MSAT3D AOA與基于RSSI三維定位算法在上述地形環境與條件下的地形建模誤差。可以看到，在信標節點較少的情況下MSAT3D AOA的建模誤差要略大于RSSI三維定位算法，但是需特別指出的是，在信標節點比例較小的情況下，本文所提算法依然能夠保證對大多數節點的定位，這一點在仿真結果中已能證明，而RSSI三維定位算法是一種基于單跳的定位算法，在信標節點比例小的情況下覆蓋率可以想見是肯定不會非常理想的。當信標節點比例不斷提高后，本文所提算法在地形建模誤差上迅速下降，這得益于隨著信標節點比例的增加，使得算法中多跳定位所占比例減少，定位精度提高，而對于RSSI三維定位算法，由于信標節點的增加只是增加了未知節點能夠獲取信息的信標節點數，從而減少了由噪聲產生的距離誤差，這一變化無論從數量還是比例上來說都不會非常大，因此，其精度的提高也是有限的。

圖7 部署環境地形模型

圖8 傳感器節點Delaunay三角剖分

圖9 地形建模誤差比較

5 總結

本文從三維定位存在的問題入手，分析了三維定位技術的研究現狀，考慮在室外環境的運用場景下，在簡單AOA三維定位的基礎上，結合三維空間角度傳遞的思想，提出了基于空間角度傳遞的多跳AOA三維定位算法MSAT3D AOA，使得鄰居信標節點少于兩個的待定位節點可以利用兩個鄰居節點的共同鄰居信標節點，以獲得距離一跳范圍之外的信標節點的位置信息，再結合簡單AOA三維定位就能夠較好地減少不可定位節點的數量，提高算法的定位覆蓋率。然后將MSAT3D AOA運用于地形建模中，使節點具有地形建模的能力，以輔助構建部署環境的地形模型，并將該算法運用到地形建模上，進一步驗證了算法的可行性。

［1］Chong C Y，Kumar S.Sensor Networks:Evolution，Opportunities，and Challenges［A］.Proc of the IEEE，2003，91(8):1247－1256.

［2］Guoqiang Mao，Baris Fidan，Brian D O Anderson.Wireless Sensor Network Localization Techniques［J］.Computer Networks，2007，51，2529－2553.

［3］毛科技，趙小敏，邵奔，等.無線傳感網絡中基于共面度的三維定位算法研究與設計［J］.傳感技術學報，2011，24(10):1481－1488.

［4］Liqiang Zhang，Xiaobo Zhou，Qiang Cheng.Landscape-3D:A Robust Localization Scheme for Sensor Networks over Complex 3D Terrains［C］//Proc of 2006 IEEE Conf on Local Computer Networks，2006:239－246.

［5］劉玉恒，蒲菊華，赫陽，等.無線傳感器網絡三維自身定位方法［J］.北京航空航天大學學報，2008，34(6):647－651.

［6］Ruohong Huan，Qingzhang Chen，Keji Mao，et al.A Three-Dimension Localization Algorithm for Wireless Sensor Network Nodes Based on SVM［C］//The 1st International Conf on Green Csircuits and Systems(ICGCS)，2010，651－654.

［7］劉立陽，張金成，吳中林，等.基于RSSI＆DFP的無線傳感器網絡聲源目標定位算法［J］.傳感技術學報，2011，24(10):1464－1468.

［8］Roy S，Chatterjee S，Bandyopadhyay S，et al.Neighborhood Tracking and Location Estimation of Nodes in Ad Hoc Networks Using Directional Antenna:A Testbed Implementation［C］//IEEE Proc of the Int Conf on Wireless Networks，Communications and Mobile Computing，2005，1－6.

［9］Niculescu D，Nath B.DV Based Positioning in Ad Hoc Networks［J］.Journal of Telecommunication Systems，2003，22(1/4):267－280.

［10］Hady S Abdel Salam，Stephan Olariu.A 3D-Localization and Terrain Modeling Technique for Wireless Sensor Networks［C］//Proc of 2nd ACM International Workshop on Foundations of Wireless Ad Hoc and Sensor Networking and Computing，2009，37－45.

［11］Niculescu D，Nath B.Ad Hoc Positioning System［J］.IEEE Globecom，2001，5:2926－2931.

［12］Capkun S，Hamdi M，Hubaux J P.GPS-Free Positioning in Mobile Ad-hoc Networks［A］.Proc of the 34th Annual Hawaii Int’l Conf on System Sciences［C］//USA:IEEE Computer Society，2001，3481－3490.

［13］王行甫，戴富泉，苗付友.基于TOA的三維無線傳感器網絡節點定位算法［J］.自動化與儀表，2008，12:1－9.

［14］孫利民，李建中，陳渝.無線傳感器網絡［M］.北京:清華大學出版社，2008:140－155.

［15］Niculescu D，Nath B.Ad Hoc Positioning System(APS)Using AOA［J］.Proc 22nd Annual Joint Conf of the IEEE Computer and Com-munication Societies(INFOCOM 2003)，2003，3:1734－1743.

［16］Anglada M V.An Improved Incremental Algorithm for Constructing Restricted Delaunay Triangulations［J］.Computer and Graphics，1997，21(2):215－223.