基于AOA降維和同心圓定位的三維傳感器網(wǎng)絡(luò)節(jié)點(diǎn)自定位方法*

蔣 鵬，覃 添，陳歲生

(1.杭州電子科技大學(xué)信息與控制研究所，杭州310018;2.杭州職業(yè)技術(shù)學(xué)院友嘉機(jī)電學(xué)院，杭州310018)

無線傳感器網(wǎng)絡(luò)自20世紀(jì)90年代起源并應(yīng)用于軍事以來，在軍事、環(huán)境監(jiān)測(cè)、智能家居、工業(yè)控制及救災(zāi)搶險(xiǎn)領(lǐng)域均有良好應(yīng)用[1]。無線傳感器網(wǎng)絡(luò)系統(tǒng)依靠監(jiān)測(cè)區(qū)域內(nèi)大規(guī)模的傳感器節(jié)點(diǎn)以無線通信方式傳回的信息來進(jìn)行工作，在傳感器節(jié)點(diǎn)所傳回的信息中，無線傳感器網(wǎng)絡(luò)系統(tǒng)將節(jié)點(diǎn)監(jiān)測(cè)信息打上地理標(biāo)簽來實(shí)現(xiàn)虛擬無線網(wǎng)絡(luò)與現(xiàn)實(shí)物理的位置連接。因此，節(jié)點(diǎn)的定位信息是整個(gè)傳感器網(wǎng)絡(luò)的關(guān)鍵信息。

傳感器節(jié)點(diǎn)自定位方法一直是傳感器網(wǎng)絡(luò)的重點(diǎn)研究方向。監(jiān)測(cè)區(qū)域中分布著大量的傳感器節(jié)點(diǎn)，無線傳感器網(wǎng)絡(luò)系統(tǒng)依靠這些傳感器節(jié)點(diǎn)的初始位置、移動(dòng)方式、信號(hào)強(qiáng)度及網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)等多方面推斷各未知節(jié)點(diǎn)的位置信息[2－3]。雖然無線傳感器網(wǎng)絡(luò)在二維平面內(nèi)已有多種成熟的定位方法，但三維空間中傳感器節(jié)點(diǎn)的相對(duì)位置、移動(dòng)方式、網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)對(duì)比二維空間均發(fā)生改變，因此現(xiàn)有的二維平面定位方法難以直接應(yīng)用于三維空間中[4－5]。

目前二維平面的定位方法多依靠測(cè)距信息與非測(cè)距信息定位。在基于測(cè)距信息中的定位方法，傳感器節(jié)點(diǎn)傳播的信息為可直接測(cè)量距離的信號(hào)，如基于信號(hào)強(qiáng)度的RSSI信息，基于信號(hào)到達(dá)時(shí)間的TOA信息，基于信號(hào)到達(dá)時(shí)間差的TDOA信息及基于節(jié)點(diǎn)間角度的AOA信息，上述技術(shù)需要硬件支持，具有網(wǎng)絡(luò)通信簡(jiǎn)單、錨節(jié)點(diǎn)密度需求低等優(yōu)點(diǎn)。而非測(cè)距信息中傳感器節(jié)點(diǎn)傳播的信息均為不可直接測(cè)距的信息，未知節(jié)點(diǎn)的位置依靠錨節(jié)點(diǎn)與未知節(jié)點(diǎn)間相對(duì)位置信息得出，如DV-Hop算法、APIT算法、MDS算法及質(zhì)心算法等[1]。該類技術(shù)不需要特殊的硬件支持，傳感器節(jié)點(diǎn)成本較低，但其網(wǎng)絡(luò)通信具有一定復(fù)雜度。將二維平面定位方法拓展至三維空間是現(xiàn)有三維空間定位方法的來源之一，如王丹提出的3D-DV-Hop算法、3D-APIT算法及3DCentroid[6]，這些三維算法原理與相應(yīng)二維算法基本相同，在此不在贅述。文獻(xiàn)[7]中提出了一種二維的同心圓算法，簡(jiǎn)稱CAB算法，該文獻(xiàn)通過對(duì)無線信號(hào)傳播模型的分析證明了CAB的可行性，闡述了同心圓定位兩種基本思路，一種為同等區(qū)域方法簡(jiǎn)稱為CAB-EA算法，一種為同等寬度方法簡(jiǎn)稱為CAB-EW算法，這兩種算法的仿真結(jié)果表明，在相同空間模型中CAB-EA與CAB-EW的定位誤差均小于APIT算法與質(zhì)心算法的定位誤差，其中CAB-EW的定位誤差最小。朱紅霞提出的DRFP-3D定位算法[8]，該算法是由二維平面的同心圓算法延伸至三維空間的三維同心圓定位算法，DRFP-3D算法提出了一種基于最小正方體投票機(jī)制，即先將監(jiān)測(cè)區(qū)域離散成有唯一編號(hào)的小正方體，再利用同心圓定位信息對(duì)小正方體進(jìn)行編號(hào)，最后由投票機(jī)制算出未知節(jié)點(diǎn)的位置信息。在現(xiàn)有的三維傳感器網(wǎng)絡(luò)定位技術(shù)中，也有許多以三維空間特性為研究基礎(chǔ)的定位方法，如C.Tian提出了一種水下環(huán)境的三維節(jié)點(diǎn)定位方法[9]，該算法利用聲波在水下傳輸?shù)奶匦蕴岢隽艘环N水下TDOA算法，該算法對(duì)聲波在水中的傳播模型及無線信號(hào)傳播模型進(jìn)行了分析。王懌針對(duì)水下環(huán)境中無線信號(hào)傳播的高延遲及水下環(huán)境中可能存在的異形空間提出了一種基于水下環(huán)境的傳感器節(jié)點(diǎn)定位方法[10]。M.Talha Isik也提出了一種水下環(huán)境無線傳感器節(jié)點(diǎn)定位方法[11]，該方法中錨節(jié)點(diǎn)為浮標(biāo)節(jié)點(diǎn)可自主調(diào)節(jié)自身水下深度并利用錨節(jié)點(diǎn)與未知節(jié)點(diǎn)間AOA信息進(jìn)行定位。Liqiang Zhang提出了Landscape-3D算法[12]，該方法中利用功能強(qiáng)大的飛行錨節(jié)點(diǎn)周期性廣播自身位置并接收未知節(jié)點(diǎn)的相對(duì)位置信息來定位。Chia-Ho Ou提出的Ou-3D算法[13]同樣使用了功能強(qiáng)大的飛行錨節(jié)點(diǎn)，利用飛行錨節(jié)點(diǎn)在未知節(jié)點(diǎn)通訊范圍內(nèi)臨界信標(biāo)信息進(jìn)行定位。E.Guerrero提出了一種基于方位角的區(qū)域定位算法(Azimuthally Defined Area Localization Algorithm，3D-ADAL 算法)[14]，該算法中也使用了功能強(qiáng)大的無人機(jī)錨節(jié)點(diǎn)同時(shí)無人機(jī)上自帶定向無線天線可以設(shè)定角度廣播無線信息。

本文基于同心圓定位方法[7－8]與 AOA角度測(cè)量方法[15]，提出了一種基于AOA降維和同心圓定位的三維傳感器網(wǎng)絡(luò)節(jié)點(diǎn)自定位方法(AOA and Concentric Algorithm based three dimensional reduction node self-localization scheme，AC-RL)。該方法創(chuàng)新地引入AOA技術(shù)將節(jié)點(diǎn)坐標(biāo)信息中z軸信息轉(zhuǎn)化為角度信息，該算法與文獻(xiàn)[2]所提出DRFP-3D算法相比優(yōu)化了錨節(jié)點(diǎn)的分布區(qū)域，錨節(jié)點(diǎn)只需分布在同一水平面算法即可進(jìn)行，同時(shí)AOA技術(shù)得引入使AC-RL方法只需更少的錨節(jié)點(diǎn)即可達(dá)到與三維同心圓算法相同的定位誤差，從而降低了錨節(jié)點(diǎn)密度。在求出角度信息后用同心圓定位方法在二維平面內(nèi)求出節(jié)點(diǎn)坐標(biāo)信息中x軸與y軸信息，此步驟與三維同心圓算法相比減少了在三維定位空間中的算法復(fù)雜度。

本文以下第1部分將會(huì)對(duì)兩種算法進(jìn)行詳細(xì)的介紹，包括AC-RL算法的數(shù)學(xué)原理與算法流程。第2部分對(duì)兩種定位方法的相對(duì)定位誤差及通訊能耗兩方面進(jìn)行了比較，并從錨節(jié)點(diǎn)數(shù)目、信號(hào)發(fā)射級(jí)別、錨節(jié)點(diǎn)運(yùn)動(dòng)狀態(tài)三方面對(duì)算法的相對(duì)定位誤差進(jìn)行了分析。最后對(duì)全文進(jìn)行了總結(jié)。

1 算法原理與算法描述

1.1 三維同心圓定位

三維同心圓定位首先確定絕對(duì)坐標(biāo)系，并將整個(gè)監(jiān)測(cè)區(qū)域離散成若干個(gè)獨(dú)立的小立方體，如傳感器網(wǎng)絡(luò)所在的區(qū)域?yàn)?0 m×50 m×50 m的立方體，將立方體分為12 500個(gè)獨(dú)立的小立方體，每個(gè)小立方體有獨(dú)立且唯一的編號(hào)Ui(x，y，z)，小立方體的邊長(zhǎng)稱為空間最小分辨率(Minimum space resolution，MRC)，網(wǎng)絡(luò)建立時(shí)對(duì)監(jiān)測(cè)區(qū)域的離散。然后，錨節(jié)點(diǎn)開始廣播信息，在同心圓定位方法中，錨節(jié)點(diǎn)具有控制自身發(fā)射功率的能力，在自由傳播環(huán)境中，信號(hào)的發(fā)射功率與信號(hào)所覆蓋的區(qū)域半徑之間的關(guān)系可用式(1)描述:

其中，Ps為信號(hào)發(fā)射功率，Pr為信號(hào)被接收時(shí)的功率，f為發(fā)射頻率，c為光速，d為信號(hào)發(fā)射處到信號(hào)接收處之間的距離，由式(1)可以看出，當(dāng)信號(hào)的接收功率一定時(shí)，信號(hào)的傳播距離與信號(hào)發(fā)射功率成正比。三維同心圓定位正是利用了這一特點(diǎn)，將發(fā)射功率設(shè)置成不同的級(jí)別，對(duì)應(yīng)信號(hào)不同的發(fā)射級(jí)別I(I的級(jí)別由低到高依次為I1、I2…In)，I越高，信號(hào)的發(fā)射功率也就越大信號(hào)傳播的范圍就越遠(yuǎn)。將信號(hào)發(fā)射級(jí)別細(xì)分后，信號(hào)覆蓋范圍同時(shí)也被劃分，每一發(fā)射級(jí)別I對(duì)應(yīng)其極限傳播距離d，信號(hào)的傳播范圍便被分為數(shù)個(gè)以錨節(jié)點(diǎn)坐標(biāo)為圓心，Ri－1為內(nèi)徑、Ri為外徑的球殼型區(qū)域。當(dāng)錨節(jié)點(diǎn)開始廣播自身信息之后，未知節(jié)點(diǎn)開始接收錨節(jié)點(diǎn)信息，每個(gè)未知節(jié)點(diǎn)監(jiān)聽多個(gè)錨節(jié)點(diǎn)的廣播信息，當(dāng)監(jiān)聽到的錨節(jié)點(diǎn)數(shù)超過預(yù)先設(shè)定的閾值N時(shí)算法開始運(yùn)行，在多次仿真下得出當(dāng)N取3時(shí)各節(jié)點(diǎn)就可開始計(jì)算，根據(jù)錨節(jié)點(diǎn)廣播的數(shù)據(jù)，可以得出未知節(jié)點(diǎn)的坐標(biāo)范圍為:

式(2)中，(xi，yi，zi)為相應(yīng)錨節(jié)點(diǎn)坐標(biāo)、半徑范圍(ri，ri+1)(i=a，b，、、，e，、)為該錨節(jié)點(diǎn)的通信覆蓋范圍。得出坐標(biāo)范圍后，只需將最先離散出的12500個(gè)小立方體代入式(2)中，得出滿足式(2)的點(diǎn)集，再對(duì)點(diǎn)集求質(zhì)心，可確定未知節(jié)點(diǎn)坐標(biāo)。

從上述算法原理可以看出，三維同心圓算法由各未知節(jié)點(diǎn)獨(dú)立執(zhí)行，未知節(jié)點(diǎn)間的定位互不干擾，當(dāng)前網(wǎng)絡(luò)部署發(fā)生變動(dòng)時(shí)，只需對(duì)變動(dòng)節(jié)點(diǎn)重新定位即可，同時(shí)定位過程簡(jiǎn)單，網(wǎng)絡(luò)組網(wǎng)完成后錨節(jié)點(diǎn)部署完畢即可開始執(zhí)行算法。然而該算法也存在一些缺點(diǎn)，三維同心圓算法在開始時(shí)需選擇最小分辨率然后離散化整個(gè)監(jiān)測(cè)區(qū)域，此步驟導(dǎo)致算法時(shí)間復(fù)雜度為O(n3)，n為監(jiān)測(cè)區(qū)域立方體邊長(zhǎng)與最小分辨率的比值，當(dāng)監(jiān)測(cè)區(qū)域立方體邊長(zhǎng)為50 m及最小分辨率為1 m時(shí)算法時(shí)間復(fù)雜度為O(12 500)，若立方體邊長(zhǎng)變?yōu)?00 m且最小分辨率不變時(shí)，時(shí)間復(fù)雜度為O(1 000 000)，若監(jiān)測(cè)區(qū)域立方體邊長(zhǎng)繼續(xù)增大，算法時(shí)間復(fù)雜度O則繼續(xù)以立方倍增長(zhǎng)，從而使算法計(jì)算量過大，進(jìn)而影響到系統(tǒng)的響應(yīng)時(shí)間及數(shù)據(jù)精度;若監(jiān)測(cè)區(qū)域立方體邊長(zhǎng)繼續(xù)增大且最小分辨率亦增大時(shí)，最小分辨率的增大將導(dǎo)致三維同心圓算法中參與投票的小立方增大，進(jìn)而影響到算法的定位精度。本文針對(duì)這此點(diǎn)對(duì)三維同心圓算法進(jìn)行改進(jìn)提出AC-RL算法，下文將詳細(xì)說明AC-RL算法原理。

1.2 AC-RL 定位

AC-RL定位方法分為三個(gè)階段。首先獲取未知節(jié)點(diǎn)與相應(yīng)錨節(jié)點(diǎn)之間的角度信息[10];然后對(duì)三維信息降維處理，最后利用同心圓算法定位未知節(jié)點(diǎn)。

首先錨節(jié)點(diǎn)需測(cè)出未知節(jié)點(diǎn)和錨節(jié)點(diǎn)的連線與錨節(jié)點(diǎn)所在水平面之間的夾角，錨節(jié)點(diǎn)的內(nèi)部構(gòu)成如圖1所示。

圖1 三維AOA原理圖

錨節(jié)點(diǎn)S由5個(gè)發(fā)射節(jié)點(diǎn)P0至P4構(gòu)成，P1P2與P3P4的長(zhǎng)度為一定值L，L一般取固定值，P1P2與P3P4的夾角成90°，P0位于兩線段的中點(diǎn)。

從P1到A之間的距離L1由RSSI測(cè)距測(cè)出，同理分別測(cè)得P2到A的距離L2，P3到A的距離L3，P4到A的距離L4。利用余弦定理可以求出，所得結(jié)果為。又因?yàn)镻為兩線段中點(diǎn)，可求出AP00的長(zhǎng) 度，由此可求得AP0在坐標(biāo)系中與 X軸夾角即 AP0與P1P2的夾角∠AP0P2(θ)，cosθ=，AP0在坐標(biāo)系中與Y軸夾角即AP0與P3P4的夾角，則可求得 AP0在平面 P1P2P3P4內(nèi)的投影 P0N長(zhǎng)度為，將上述公式化簡(jiǎn)可得AP0與平面 P1P2P3P4的夾角

發(fā)射節(jié)點(diǎn)P0廣播同心圓定位信息，廣播的信息如表1所示。

表1 錨節(jié)點(diǎn)廣播信息

當(dāng)未知節(jié)點(diǎn)監(jiān)聽到的錨節(jié)點(diǎn)數(shù)目達(dá)到3個(gè)以上時(shí)，未知節(jié)點(diǎn)開始對(duì)錨節(jié)點(diǎn)的廣播信息進(jìn)行降維處理，由于三維空間中AOA投影圖較復(fù)雜，本文用二維空間中AOA投影圖代替。

圖2 AOA投影圖

如圖2所示，O為信號(hào)傳播范圍的圓心即錨節(jié)點(diǎn)所在位置，線段Ri－1Ri為未知節(jié)點(diǎn)可能所處的范圍，若未知節(jié)點(diǎn)與錨節(jié)點(diǎn)O的連線與X軸所成角度γ已知，則未知節(jié)點(diǎn)在x軸的投影范圍為:di－1di=Ri－1Ri·cosγ。

同理根據(jù)未知節(jié)點(diǎn)與錨節(jié)點(diǎn)的連線與錨節(jié)點(diǎn)所在水平面所成的夾角γ，信標(biāo)信息的覆蓋范圍(Ri－1，Ri)，便可得出三維空間中未知節(jié)點(diǎn)在水平面上的投影圓環(huán)范圍為:

式(3)中(xi、yi)為錨節(jié)點(diǎn)在X與Y軸上的坐標(biāo)，未知節(jié)點(diǎn)將監(jiān)聽到多個(gè)錨節(jié)點(diǎn)信息，由式(2)，(3)可得出未知節(jié)點(diǎn)在水平面上投影點(diǎn)的大致區(qū)域，對(duì)所得區(qū)域求質(zhì)心便可得到未知節(jié)點(diǎn)在水平面上的投影點(diǎn)D(xN，yN)，利用三角定理求出未知節(jié)點(diǎn)在z軸的坐標(biāo)(γSi為未知節(jié)點(diǎn)和錨節(jié)點(diǎn)Si的連線與錨節(jié)點(diǎn)所在水平面的夾角)，即未知節(jié)點(diǎn)坐標(biāo)全部求出。

從AC-RL算法原理中看到，引入了AOA技術(shù)后，算法將未知節(jié)點(diǎn)的z坐標(biāo)信息保存在角度信息中，使得三維空間中的定位轉(zhuǎn)化為二維平面上的定位，因此避免了監(jiān)測(cè)空間離散化在三維空間中進(jìn)行，而二維平面中離散區(qū)域?yàn)槠矫?，此時(shí)算法基于時(shí)間復(fù)雜度為O(n2)，這樣就避免了DRFP-3D算法中由監(jiān)測(cè)區(qū)域的擴(kuò)大而導(dǎo)致的算法時(shí)間復(fù)雜度的大幅增加。同時(shí)三維定位空間定位轉(zhuǎn)化為二維平面定位后，影響定位精度的信息變由X軸、Y軸及Z軸變?yōu)閄軸、Y軸信息及AOA角度信息，在后續(xù)的算例仿真表明角度信息精度取3%之內(nèi)時(shí)AC-RL算法比DRFP-3D算法提供了更精確的z坐標(biāo)信息。

1.3 算法流程

錨節(jié)點(diǎn)隨機(jī)分布在水平面上，未知節(jié)點(diǎn)隨機(jī)分布在監(jiān)控區(qū)域中，錨節(jié)點(diǎn)組編號(hào)為 S1、S2、S3…Sn，每個(gè)錨節(jié)點(diǎn)由P0至P4五個(gè)發(fā)射節(jié)點(diǎn)組成，未知節(jié)點(diǎn)編號(hào)為 A1、A2、A2…Am，且任一未知節(jié)點(diǎn) Aj(1≤j≤m)能接收到k(1≤k≤n)個(gè)錨節(jié)點(diǎn)的信息。

算法步驟如下:①選取任意一未知節(jié)點(diǎn)Aj(1≤j≤m);②錨節(jié)點(diǎn)Si(1≤i≤n)的P1至P4四個(gè)發(fā)射節(jié)點(diǎn)周期性地廣播測(cè)距信息。P0發(fā)射節(jié)點(diǎn)周期性地廣播同心圓信息，信息類容如表1所示，錨節(jié)點(diǎn)組成如圖1所示;③未知節(jié)點(diǎn)Aj(j初始值為1)接收到Si中P1至P4的測(cè)距信息，計(jì)算出Si與A1的AOA信息tanγS1，同時(shí)Aj接收到Si中P0廣播的同心圓信息，將功率級(jí)別I最低的信息判定為真。將二者信息存入Aj的信息表中;④未知節(jié)點(diǎn)Aj(j初始值為1)接收錨節(jié)點(diǎn)Si+1到Sk(i≤k≤n)的信標(biāo)信息復(fù)步驟②與③;⑤當(dāng)Aj接收完Si至Sk的錨節(jié)點(diǎn)信息后，若未知節(jié)點(diǎn)監(jiān)聽到的錨節(jié)點(diǎn)數(shù)大于等于3開始計(jì)算未知節(jié)點(diǎn)在水平面上投影可能存在的范圍后，用同心圓算法求出投影點(diǎn)位置信息。若未知節(jié)點(diǎn)監(jiān)聽到的錨節(jié)點(diǎn)數(shù)小于3則跳過⑥步驟，且A'j取空集;⑥結(jié)合未知節(jié)點(diǎn)Aj對(duì)應(yīng)錨節(jié)點(diǎn)Si的AOA信息tanγSi可得出未知節(jié)點(diǎn)坐標(biāo)A'j;⑦重復(fù)①至⑥直到未知節(jié)點(diǎn)坐標(biāo)均被求出。

2 仿真算例

本節(jié)在DRFP-3D算法與AC-RL算法在參數(shù)配置相同的情況下進(jìn)行了相對(duì)定位誤差與總能耗的對(duì)比，另從錨節(jié)點(diǎn)個(gè)數(shù)、信號(hào)發(fā)射級(jí)別I及錨節(jié)點(diǎn)移動(dòng)三個(gè)方面對(duì)相對(duì)定位誤差的影響進(jìn)行了比較。

仿真參數(shù)配置:監(jiān)測(cè)區(qū)域?yàn)?0 m×50 m×50 m的立方體，最小分辨率MRC=1 m，錨節(jié)點(diǎn)極限通訊距離為50 m，信號(hào)發(fā)射級(jí)別I分為5級(jí)，每一級(jí)對(duì)應(yīng)應(yīng)10 m的通訊距離，定位判決門限值DT為3，仿真開始前，配置以上所有參數(shù)，錨節(jié)點(diǎn)個(gè)數(shù)為AH，未知節(jié)點(diǎn)個(gè)數(shù)為UN，AOA角度信息取自文獻(xiàn)[10]，誤差設(shè)定為3%。相對(duì)定位誤差公式為:，A'i為未知節(jié)點(diǎn)估算坐標(biāo)，Ai為未知節(jié)點(diǎn)實(shí)際坐標(biāo)，|A'i－Ai|為未知節(jié)點(diǎn)與其估算位置之間的距離，d為錨節(jié)點(diǎn)最大通信半徑。

圖3所示算例中AH=27，UN=200，錨節(jié)點(diǎn)隨機(jī)分布在水平面，未知節(jié)點(diǎn)隨機(jī)分布在監(jiān)測(cè)區(qū)域，信號(hào)發(fā)射級(jí)別I=5。從圖3中可得，AC-RL定位方法的相對(duì)定位誤差有著明顯的降低。且通過20次獨(dú)立實(shí)驗(yàn)得出AC-RL定位方法的平均相對(duì)誤差在5.4%～7.2%之間，而三維同心圓定位方法的平均相對(duì)誤差在13.8% ～19.7%之間。該數(shù)據(jù)表明引入AOA技術(shù)后AC-RL算法的相對(duì)定位誤差有較大降低。原因在于利用同心圓算法處理三維定位問題時(shí)未知節(jié)點(diǎn)在X軸、Y軸及Z軸上的位置信息均相互影響。而AC-RL定位方法利用AOA技術(shù)將Z軸信息轉(zhuǎn)化為角度信息保存下來，使三維定位問題的處理轉(zhuǎn)化為二維定位問題的處理，則影響定位精度的信息變成了X軸、Y軸信息及AOA角度信息，即AC-RL算法中X軸與Y軸間相互影響變小，且角度信息精度在3%之內(nèi)時(shí)提供了更精確的z坐標(biāo)信息。

圖3 DRFP-3D算法與AC-RL算法相對(duì)誤差圖

圖4對(duì)比當(dāng)錨節(jié)點(diǎn)數(shù)量變化時(shí)對(duì)DRFP-3D算法與AC-RL算法中相對(duì)定位誤差變化趨勢(shì)的影響。仿真算例參數(shù)配置為UN=400，錨節(jié)點(diǎn)隨機(jī)分布在水平面，未知節(jié)點(diǎn)隨機(jī)分布在監(jiān)測(cè)區(qū)域，信號(hào)發(fā)射級(jí)別I=5。從圖4中可知當(dāng)AH≤15時(shí)AC-RL算法相對(duì)誤差較大，AH≤25時(shí)三維同心圓算法相對(duì)誤差較大，但是相同錨節(jié)點(diǎn)數(shù)目下AC-RL定位方法的相對(duì)定位誤差依舊低于DRFP-3D算法的相對(duì)定位誤差，隨著錨節(jié)點(diǎn)的數(shù)目增多，定位誤差以很快的趨勢(shì)下降，當(dāng)錨節(jié)點(diǎn)增多到一定值時(shí)，錨節(jié)點(diǎn)數(shù)目對(duì)定位誤差的影響開始降低。AC-RL算法與DRFP-3D算法均為典型的分布式算法，即網(wǎng)絡(luò)內(nèi)各未知節(jié)點(diǎn)的定位互不影響，根據(jù)錨節(jié)點(diǎn)位置信息即可定位。錨節(jié)點(diǎn)位置信息在兩種算法中為影響定位結(jié)果的重要指標(biāo)，當(dāng)錨節(jié)點(diǎn)數(shù)量上升時(shí)，未知節(jié)點(diǎn)可獲得更多有效的定位信息，所以DRFP-3D算法與AC-RL算法的定位誤差均有降低，而AC-RL算法中引入了AOA技術(shù)使得未知節(jié)點(diǎn)z軸坐標(biāo)信息轉(zhuǎn)化為角度信息，使AC-RL算法與DRFP-3D算法相比只需更少的錨節(jié)點(diǎn)數(shù)目即可完成定位。

圖4 相對(duì)定位誤差隨錨節(jié)點(diǎn)數(shù)AH變化的關(guān)系圖

圖5，圖6以錨節(jié)點(diǎn)通訊級(jí)別I變化的角度來比較DRFP-3D算法與AC-RL算法中的可定位節(jié)點(diǎn)比例與定位精度。仿真算例參數(shù)配置為AH=27，UN=400，錨節(jié)點(diǎn)隨機(jī)分布在水平面，未知節(jié)點(diǎn)隨機(jī)分布在監(jiān)測(cè)區(qū)域，信號(hào)發(fā)射級(jí)別I從1至5逐步變化。由圖5可以看出，當(dāng)I從1變化至4時(shí)，DRFP-3D算法與AC-RL算法的仿真算例中可定位節(jié)點(diǎn)比例都呈上升趨勢(shì)，但DRFP-3D算法的可定位節(jié)點(diǎn)比例始終高于AC-RL定位方法的可定位節(jié)點(diǎn)比例。其原因在于，圖5中監(jiān)測(cè)區(qū)域?yàn)?0 m×50 m×50 m的立方體，信號(hào)發(fā)射級(jí)別I由1至5逐步變化時(shí)錨節(jié)點(diǎn)通信范圍對(duì)應(yīng)10 m至50 m逐步變化，在變化初始階段錨節(jié)點(diǎn)的通信范圍無法完全覆蓋整個(gè)通信區(qū)域，則區(qū)域內(nèi)會(huì)存在某塊區(qū)域未被三個(gè)錨節(jié)點(diǎn)或更少個(gè)錨節(jié)點(diǎn)覆蓋，此時(shí)未知節(jié)點(diǎn)所監(jiān)聽到的錨節(jié)點(diǎn)數(shù)目不能滿足門限值DT=3的要求，即不能觸發(fā)執(zhí)行定位算法，則在該區(qū)域內(nèi)所存在的未知節(jié)點(diǎn)為不可定位節(jié)點(diǎn)。而DRFP-3D算法中錨節(jié)點(diǎn)是隨機(jī)分布在監(jiān)測(cè)區(qū)域內(nèi)，AC-RL定位方法中錨節(jié)點(diǎn)卻是分布在監(jiān)測(cè)區(qū)域底層水平面上，當(dāng)錨節(jié)點(diǎn)數(shù)目一定且通信半徑較短時(shí)，AC-RL定位方法中錨節(jié)點(diǎn)信息所覆蓋的區(qū)域要小于DRFP-3D算法中錨節(jié)點(diǎn)信息所覆蓋的區(qū)域，而I級(jí)別較高時(shí)，即I大于5時(shí)，兩種定位方法中的可定位節(jié)點(diǎn)比例均為100%。

圖5 可定位節(jié)點(diǎn)比例隨信號(hào)發(fā)射級(jí)別I變化的關(guān)系圖

圖6 相對(duì)定位誤差隨信號(hào)發(fā)射級(jí)別I變化的關(guān)系圖

圖6所示算例參數(shù)配置為AH=50，UN=400，I由1至5逐步變化。從圖6可看出，在I為1時(shí)，DRFP-3D算法與AC-RL算法的定位精度相差不大，可近似于相等。隨著I的增大，當(dāng)I=2時(shí)DRFP-3D算法與AC-RL算法的相對(duì)定位誤差均開始下降。當(dāng)I由2增大至5時(shí)，DRFP-3D算法的相對(duì)定位誤差開始緩慢下降，下降趨勢(shì)不如I由1增大至2時(shí)明顯，此時(shí)AC-RL算法的相對(duì)定位誤差依舊保持著之前的下降趨勢(shì)。I由4增大至5時(shí)三維同心算法的定位誤差還有著明顯下降，但AC-RL定位方法的定位誤差此時(shí)已無明顯下降趨勢(shì)。其原因在于，當(dāng)I=1時(shí)兩種定位方法的錨節(jié)點(diǎn)通訊半徑均為10 m而監(jiān)測(cè)空間為50 m3，存在許多區(qū)域未能被多個(gè)錨節(jié)點(diǎn)覆蓋，即使有些未知節(jié)點(diǎn)處于被多個(gè)錨節(jié)點(diǎn)覆蓋的區(qū)域，此時(shí)通訊半徑只有I=1一個(gè)級(jí)別，同心圓算法中同心圓分級(jí)概念無法成立，算法計(jì)算方式為質(zhì)心算法，此時(shí)定位絕對(duì)誤差均在3.5 m左右。當(dāng)I為2時(shí)，兩種定位方法的定位絕對(duì)誤差在4 m至5 m之間，但相對(duì)定位誤差還是下降了。DRFP-3D算法中定位誤差大幅下降是因?yàn)橥ㄓ嵃霃椒旨?jí)后，可利用半徑分級(jí)的信息將未知節(jié)點(diǎn)可能存在區(qū)域進(jìn)一步細(xì)分，從而減少了相對(duì)定位誤差。當(dāng)I由2變化至4時(shí)，三維同心圓算法的定位誤差下降緩慢，這是因?yàn)樵贗由1變化至2時(shí)，該算法等同于三維質(zhì)心算法朝三維同心圓算法變化的過程，而由2變化至5時(shí)才體現(xiàn)出三維同心圓算法由于通訊半徑的增加引起的定位誤差變化。在I由1增大至2時(shí)，AC-RL算法中，也因利用半徑分級(jí)的信息區(qū)分出未知節(jié)點(diǎn)最可能存在的區(qū)域使未知節(jié)點(diǎn)相對(duì)定位誤差下降，在I繼續(xù)增大后由于AC-RL定位方法引入AOA測(cè)距技術(shù)，使得在半徑持續(xù)增大時(shí)將三維球殼信息簡(jiǎn)化為二維圓環(huán)信息，使得Z軸坐標(biāo)信息得以較精確保存，使該定位方法相對(duì)誤差下降的趨勢(shì)得以保持。而在I=4時(shí)，AC-RL定位方法中相對(duì)定位誤差的極限值，所以在由4變化至5的過程中無明顯變化。

圖7為DRFP-3D算法與AC-RL算法的通信能耗比較，該算例配置為UN=500，AH由小到大變化，推導(dǎo)公式如下。

無線信號(hào)在三維空間的傳播過程中運(yùn)行發(fā)送器或接受器的無線花費(fèi)為:

圖7 通信能耗隨錨節(jié)點(diǎn)個(gè)數(shù)AH變化的關(guān)系圖

發(fā)送放大器實(shí)現(xiàn)容許放大倍率的無線花費(fèi)為:

三維空間內(nèi)傳感器節(jié)點(diǎn)i、j間的距離為:

若節(jié)點(diǎn)i向j發(fā)送長(zhǎng)度為kbit的數(shù)據(jù)包，則節(jié)點(diǎn)i能耗為:

節(jié)點(diǎn)j接收此數(shù)據(jù)包的能耗為:

在DRFP-3D算法中，每個(gè)錨節(jié)點(diǎn)均要按自身發(fā)射級(jí)別I(I=5)廣播5次信息，每次廣播的數(shù)據(jù)包長(zhǎng)度均為k，則耗能為:

若每個(gè)未知節(jié)點(diǎn)可監(jiān)聽到n個(gè)錨節(jié)點(diǎn)，則每個(gè)未知節(jié)點(diǎn)的接收能耗為:

Ii為相應(yīng)錨節(jié)點(diǎn)自身發(fā)射級(jí)別，Erx(k)為單個(gè)節(jié)點(diǎn)接受數(shù)據(jù)能耗。

則DRFP-3D算法總能耗應(yīng)為:

在AC-RL算法中，每個(gè)錨節(jié)點(diǎn)先需發(fā)射4個(gè)測(cè)距信息，再將自身信息按發(fā)射級(jí)別I(I=5)廣播5次，則每個(gè)錨節(jié)點(diǎn)的發(fā)射能耗為:

同理，若每個(gè)未知節(jié)點(diǎn)可監(jiān)聽到n個(gè)錨節(jié)點(diǎn)，則每個(gè)未知節(jié)點(diǎn)的接收能耗為:

AC-RL算法的通信總能耗為

在錨節(jié)點(diǎn)實(shí)際工作中廣播信息長(zhǎng)度一般為一定值，即在AC-RL定位方法中測(cè)距信息信標(biāo)長(zhǎng)度k與同心圓信息信標(biāo)長(zhǎng)度k相等，則可得出圖7。

如式(11)與式(14)所示，AC-RL算法中錨節(jié)點(diǎn)的通訊方式比其在DRFP-3D算法中多出4組測(cè)距信息。式中的n為相應(yīng)錨節(jié)點(diǎn)可監(jiān)聽到的n個(gè)未知節(jié)點(diǎn)，其具體數(shù)值由仿真中節(jié)點(diǎn)具體分布情況決定。實(shí)際計(jì)算得出在相同網(wǎng)絡(luò)規(guī)模下，AC-RL算法將比DRFP-3D算法消耗更多能量，能耗大致為原算法的2.5倍 ～3倍。

圖8為當(dāng)AC-RL算法中錨節(jié)點(diǎn)為移動(dòng)狀態(tài)時(shí)相對(duì)定位誤差的比較，在該算例中AH=9分布在監(jiān)測(cè)區(qū)域水平面上并以0.5 m/s速度在水平面上隨機(jī)移動(dòng)，每隔10 s傳感器網(wǎng)絡(luò)進(jìn)行一次節(jié)點(diǎn)定位，UN=200隨機(jī)分布在監(jiān)測(cè)區(qū)域內(nèi)，I由1至5逐步變化。t1為錨節(jié)點(diǎn)初始狀態(tài)時(shí)未知節(jié)點(diǎn)相對(duì)定位誤差，t2為錨節(jié)點(diǎn)移動(dòng)一次后未知節(jié)點(diǎn)相對(duì)定位誤差，t3為錨節(jié)點(diǎn)第二次移動(dòng)后未知節(jié)點(diǎn)相對(duì)定位誤差。在t1時(shí)傳感器網(wǎng)絡(luò)中錨節(jié)點(diǎn)還未開始移動(dòng)，整個(gè)網(wǎng)絡(luò)中只有9個(gè)錨節(jié)點(diǎn)位置信息可以用于定位方法，t2時(shí)錨節(jié)點(diǎn)已隨機(jī)移動(dòng)5 m相當(dāng)于網(wǎng)絡(luò)中錨節(jié)點(diǎn)位置重新分布，但由于未知節(jié)點(diǎn)位置未發(fā)生改變則t1時(shí)刻的錨節(jié)點(diǎn)位置信息同樣為有效信息，即在t2時(shí)刻網(wǎng)絡(luò)中有效錨節(jié)點(diǎn)位置信息變?yōu)榱?8個(gè)，這導(dǎo)致t2時(shí)刻定位方法中相對(duì)定位誤差大幅下降。同理t3時(shí)刻時(shí)，網(wǎng)絡(luò)中有效錨節(jié)點(diǎn)信息變?yōu)?7個(gè)，此時(shí)未知節(jié)點(diǎn)平均定位誤差在3%左右已接近AC-RL算法中相對(duì)定位誤差的極限值。

圖8 AC-RL算法中相對(duì)定位誤差隨錨節(jié)點(diǎn)移動(dòng)次數(shù)變化關(guān)系圖

3 結(jié)語(yǔ)

本文基于無線傳感網(wǎng)絡(luò)中的DRFP-3D算法，提出了一種AC-RL定位方法，該算法根據(jù)未知節(jié)點(diǎn)與錨節(jié)點(diǎn)所在水平面的角度信息，對(duì)錨節(jié)點(diǎn)與未知節(jié)點(diǎn)間的距離信息進(jìn)行降維處理，使三維定位的需求轉(zhuǎn)變?yōu)槎S定位，使得在相同參數(shù)配置下AC-RL定位方法的定位精度有著明顯提高，且在相同定位精度的情況下，AC-RL定位方法降低了對(duì)錨節(jié)點(diǎn)數(shù)量的需求。

[1]于寧，萬江文，吳銀鋒.無線傳感器網(wǎng)絡(luò)定位算法研究[J].傳感技術(shù)學(xué)報(bào)，2007，20(1):187－192.

[2]Priyantha N B，Balakrishnan H，Demaine E D，et all.Mobile-Assisted Localization in Wireless Sensor Networks[C]//Infcom 2005.24th Annual Joint Conference of the IEEE Computer and Communications Societies，13－17 March 2005，1:172－183.

[3]Baggio Aline，Langendoen Koen.Monte-Carlo Localization for Mobile Wireless Sensor Networks[J].Lecture Notes in Computer Science，2006，4325:317－328.

[4]Yadav Vibha，Mishra Manas Kumar，Sngh A K，et all.Localization Scheme for Three Dimensional Wireless Sensor Networks Using GPS Enabled Mobile Sensor Nodes[J].International Journal of Next-Generation Networks，December 2009，1(1):60－72.

[5]Ou Chia-Ho.Range-Free Node Localization for Mobile Wireless Sensor Networks[C]//Wireless Pervasive Computing，7－9 May 2008，535－539.

[6]王丹.三維無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)自定位算法研究[D]:碩士學(xué)位論文，西南交通大學(xué)，2007.

[7]Vivekanandan V，Wong V W S.Concentric Anchor Beacon Localization Algorithm for Wireless Sensor Networks[J].IEEE Transactions on Vehicular Technology，2007，56(5):2733－2744.

[8]朱紅霞.一種新的基于非測(cè)距的無線傳感器網(wǎng)絡(luò)三維定位算法[J].傳感技術(shù)學(xué)報(bào)，2009，22(11):1655－1660.

[9]Tian C，Liu W，Jin J，et all.Localization and Synchronization for 3D Underwater Acoustic Sensor Networks[J].Ubiquitous Intelligence and Computing，2007，4611:622－631.

[10]王懌.水下傳感器網(wǎng)時(shí)間同步與節(jié)點(diǎn)定位研究[D].華中科技大學(xué)，2009.

[11]Isik M T，Akan O B.A Three Dimensional Localization Algorithm for Underwater Acoustic Sensor Networks[J].IEEE Transactions on Wireless Communications，September 2009，8(9):4457－4463.

[12]Zhang Liqiang，Zhou Xiaobo，Cheng Qiang.Landscape-3D:A Robust Localization Scheme for Sensor Networks over Complex 3D Terrains[C]//Local Computer Networks Proceedings，2006 31st IEEE Conference，2006，239－246.

[13]Ou Chia-Ho，Ssu Kuo-Feng.Sensor Position Determination with Flying Anchors in Three-Dimensional Wireless Sensor Networks[J].IEEE Transactions on Mobile Computing，2008，7(9):1084－1097.

[14]Guerrero E，Alvarez J，Rivero L.3D-ADAL:A Three-Dimensional Distributed Range-Free Localization Algorithm for Wireless Sensor Networks Based on Unmanned Aerial Vehicles[C]//Digital Information Management(ICDIM)，210 Fth Inrnational Cference on，5－8 July 2010，332－338.

[15]Hui Tian，Shuang Wang，Xie Huaiyao.Localization Using Cooperative AOA Approach[C]//Shanghai.International Conference on Wireless Communications，Networking and Mobile Computing，21－25 Sept.2007:2416－2419.