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

(浙江工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院，杭州 310023)

無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network，WSN)技術(shù)是隨著經(jīng)濟和社會發(fā)展而誕生的產(chǎn)物，是本世紀(jì)最具有影響力和改變?nèi)祟愇磥砩罘绞降母呒夹g(shù)領(lǐng)域四大支柱產(chǎn)業(yè)之一［1］。網(wǎng)絡(luò)中大部分節(jié)點的位置是未知的［2］，而節(jié)點的隨機分布和感知信息對位置的依賴，使得節(jié)點自身的準(zhǔn)確定位是一個極其重要的條件。隨著物聯(lián)網(wǎng)的發(fā)展，把地形建模的能力加入傳感器節(jié)點中，以輔助構(gòu)建部署環(huán)境的地形模型，將對WSN的應(yīng)用價值起到至關(guān)重要的作用。不管是軍事應(yīng)用環(huán)境，還是易發(fā)生自然災(zāi)害或遭受自然災(zāi)害破壞且人員無法到達(dá)的環(huán)境，如果能夠利用節(jié)點位置信息進行地形建模，將有效地幫助相關(guān)工作的順利開展。因此，研究三維定位并將此應(yīng)用于地形建模上是有必要的、有價值的。

1 研究背景

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

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

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

1.1 三維定位問題

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

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

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

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

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

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

2.1 角度傳遞的原理

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

圖1 角度傳遞示意圖

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

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

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

圖2 三維空間圖

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

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

圖3 節(jié)點在x-y平面上的投影

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

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

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

圖4 節(jié)點在ALL'所在平面上的投影

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

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

2.2 算法描述

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

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

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

步驟1，初始化網(wǎng)絡(luò)中的節(jié)點信息。所有節(jié)點都向鄰居節(jié)點廣播發(fā)送信息包，通過節(jié)點間信息的交換，建立“鄰居信標(biāo)節(jié)點信息表”和“鄰居節(jié)點信息表”。

步驟2，滿足條件的未知節(jié)點定位。若未知節(jié)點“鄰居信標(biāo)節(jié)點信息表”內(nèi)記錄數(shù)大于等于2，則用簡單AOA三維定位算法進行定位，并將結(jié)果報給網(wǎng)絡(luò)中的信標(biāo)節(jié)點或匯聚節(jié)點，然后執(zhí)行步驟3，若記錄數(shù)小于2則直接執(zhí)行步驟3。

步驟3，跳數(shù)閾值HopMax的判斷。首先將存儲在節(jié)點上的HopMax減1，若HopMax小于等于0，則停止，并將未知節(jié)點轉(zhuǎn)入休眠狀態(tài)，否則執(zhí)行步驟4。

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

步驟5，分析“鄰居節(jié)點的鄰居信標(biāo)節(jié)點信息表”。未知節(jié)點依次檢查表中出現(xiàn)的信標(biāo)節(jié)點，若某一信標(biāo)節(jié)點記錄數(shù)小于2，則放棄，并檢查，否則，執(zhí)行步驟6。如果所有信標(biāo)節(jié)點均已處理，則返回步驟2。

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

3 仿真實驗與分析

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

3.1.1 算法本身性能的實驗結(jié)果與分析

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

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

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

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

圖5 MSAT3D AOA算法仿真實驗結(jié)果圖

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

圖6 仿真結(jié)果對比圖

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

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

4 算法在地形建模中的應(yīng)用

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

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

4.2 算法應(yīng)用于地形建模的結(jié)果分析與比較

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

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

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

圖7 部署環(huán)境地形模型

圖8 傳感器節(jié)點Delaunay三角剖分

圖9 地形建模誤差比較

5 總結(jié)

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

［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］毛科技，趙小敏，邵奔，等.無線傳感網(wǎng)絡(luò)中基于共面度的三維定位算法研究與設(shè)計［J］.傳感技術(shù)學(xué)報，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］劉玉恒，蒲菊華，赫陽，等.無線傳感器網(wǎng)絡(luò)三維自身定位方法［J］.北京航空航天大學(xué)學(xué)報，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的無線傳感器網(wǎng)絡(luò)聲源目標(biāo)定位算法［J］.傳感技術(shù)學(xué)報，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的三維無線傳感器網(wǎng)絡(luò)節(jié)點定位算法［J］.自動化與儀表，2008，12:1－9.

［14］孫利民，李建中，陳渝.無線傳感器網(wǎng)絡(luò)［M］.北京:清華大學(xué)出版社，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.