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

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

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

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

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é)點(diǎn)上額外配備硬件設(shè)備，增加了成本和能耗，但定位精度一般要高很多。而在基于距離的定位技術(shù)中，采用測角技術(shù)得到的數(shù)據(jù)要比測距技術(shù)更準(zhǔn)確，穩(wěn)定性更好。因此，本文將在基于AOA(Angle Of Arrival，信號(hào)到達(dá)角度)定位的基礎(chǔ)上進(jìn)行研究。

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

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

1.1 三維定位問題

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

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

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

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

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

假設(shè)網(wǎng)絡(luò)中所有節(jié)點(diǎn)都存在一個(gè)表示自身正方向的主軸，通常為節(jié)點(diǎn)上兩個(gè)接收機(jī)連線的中垂線。利用主軸可估計(jì)鄰居節(jié)點(diǎn)相對(duì)于自身的方位角，即鄰居節(jié)點(diǎn)發(fā)送數(shù)據(jù)的方向。這樣就可以使用兩個(gè)信標(biāo)節(jié)點(diǎn)和它們分別與待定位節(jié)點(diǎn)形成的方位角即可獲得待定位節(jié)點(diǎn)的平面位置信息。同理，如果假設(shè)信標(biāo)節(jié)點(diǎn)不僅具有測定在x-y平面上信號(hào)到達(dá)角度的能力，同時(shí)還擁有測定信號(hào)到達(dá)俯仰角度的能力，則可通過這一新增加的變量實(shí)現(xiàn)在三維空間中對(duì)未知節(jié)點(diǎn)的定位。本文稱該方法為簡單AOA三維定位算法，并在此基礎(chǔ)上，根據(jù)提高節(jié)點(diǎn)定位覆蓋率的要求，提出了基于空間角度傳遞的多跳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ò)路由算法需要對(duì)節(jié)點(diǎn)進(jìn)行定位所提出的［15］，其核心技術(shù)是使待定位節(jié)點(diǎn)通過其它相鄰節(jié)點(diǎn)角度傳遞的方式，獲得在其直接通訊范圍之外信標(biāo)節(jié)點(diǎn)方位角信息的能力。如圖1所示，L是信標(biāo)節(jié)點(diǎn)，A，B，C均為相鄰的未知節(jié)點(diǎn)且均有測量信號(hào)到達(dá)角度的能力。假設(shè)節(jié)點(diǎn)B和C均已測得其與節(jié)點(diǎn)L間的方位信息，同時(shí)也互相測得對(duì)方的方位信息及節(jié)點(diǎn)A分別與B，C之間的方位信息，則ΔABC和ΔLBC的所有內(nèi)角便均可計(jì)算并確定，四邊形ABCL的形狀及其對(duì)角線與各邊所形成的夾角也能確定，則節(jié)點(diǎn)A最終可通過這些角度信息并利用正弦定理等數(shù)學(xué)方法獲得節(jié)點(diǎn)L與其主軸所形成的夾角，即確定了節(jié)點(diǎn)A和在其直接通信范圍外的節(jié)點(diǎn)L之間的方位角信息。

圖1 角度傳遞示意圖

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

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

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

圖2 三維空間圖

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

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

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

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

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

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

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

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

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

2.2 算法描述

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

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

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

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

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

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

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

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

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

3 仿真實(shí)驗(yàn)與分析

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

3.1.1 算法本身性能的實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

圖5 MSAT3D AOA算法仿真實(shí)驗(yàn)結(jié)果圖

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

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

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

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

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

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

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

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

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

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

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

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

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

圖9 地形建模誤差比較

5 總結(jié)

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