無線傳感器網(wǎng)絡中AOA節(jié)點定位改進算法研究

王梓有，周憲英

（1.海軍航空工程學院 山東 煙臺 264001；2.92941部隊 遼寧 葫蘆島 125001）

近年來，隨著無線通信、集成電路、傳感器以及微電系統(tǒng)等技術的飛速發(fā)展和日益成熟，被譽為全球未來三大高科技產(chǎn)業(yè)之一的無線傳感器網(wǎng)絡（WSN，Wireless Sensor Network）引起了全世界范圍的廣泛關注[1]。隨著物聯(lián)網(wǎng)概念的提出，作為其關鍵技術的傳感器技術成為人們研究核心，隨著無線傳感器網(wǎng)絡的應用逐漸深入到人們生活的方方面面，其核心支撐的節(jié)點定位技術也得到不斷的改進、推廣。

在WSN中，傳感器節(jié)點隨機分布在監(jiān)測區(qū)域內(nèi)，其中部分節(jié)點能夠通過攜帶自身定位設備或人工部署的方式獲得自身的精確位置，此類節(jié)點被稱為錨節(jié)點（anchor node）；其他未知節(jié)點（unknown node）只能根據(jù)錨節(jié)點位置按照某種定位機制估算出自身位置[2]。錨節(jié)點所占的比例直接影響到傳感器網(wǎng)絡的造價。根據(jù)是否需要測距，節(jié)點定位算法分為兩類：基于測距（range-based）的定位算法和無需測距（range-free）的定位算法[3]。Range-free算法僅僅依靠網(wǎng)絡連通性等信息就能夠?qū)崿F(xiàn)定位，其主要代表算法[4]有質(zhì)心算法（Centroid）、DVHop （Distance Vector-Hop）、 凸 規(guī) 劃 （Convex） 和 APIT（Approximate Perfect Point In Tri-angulation Test）等，無需測距的定位算法對硬件的要求不高，但通常定位精度不高[5]；基于測距的定位算法在定位過程中需要對節(jié)點間的角度信息或者距離等進行測量，其典型算法有接收信號強度法（RSSI，Received Signal Strength Indicator）、 信號傳輸時間法（TOA，Time of Arrival）、信號到達角法（AOA，Arrival of Angle）等，通過測量未知節(jié)點與錨節(jié)點之間的距離或角度信息，再運用三邊測量法、三角測量法或最大似然估計法計算未知節(jié)點的位置信息[6]。Range-based算法定位精度較高，但對無線傳感器網(wǎng)絡節(jié)點的硬件、成本有一定的要求[7]，未來研究趨勢是低成本、高能效的角度或距離測量技術及相關的定位算法。

基于信號到達角度的定位算法是一種典型的基于測距的定位算法，通過某些硬件設備感知發(fā)射節(jié)點信號的到達方向，計算接收節(jié)點和錨節(jié)點之間的相對方位或角度，然后再利用三角測量法或其他方式計算出未知節(jié)點的位置。本文首先介紹了典型的基于信號到達角度的節(jié)點定位算法，在此基礎上，提出了一種改進的算法，即在對定位結果進行求精校正的階段，通過選擇過濾誤差較大的估計位置，提高系統(tǒng)的定位精度，使最后的定位結果更加有效。

1 理論分析

1.1 基于信號到達角度的定位算法

算法第一步為測量階段，即未知節(jié)點通過特殊設備測量得到在通信范圍內(nèi)的錨節(jié)點的信號到達角度信息。

第二步利用夾角射線原則解方程，計算未知節(jié)點的估計位置，假設未知節(jié)點 P（x，y），測量 A（x1，y1）、B（x2，y2）兩個錨節(jié)點的信號到達角度信息為α、β，解方程：

可得未知節(jié)點P的坐標

第3部進行求精校正。當未知節(jié)點通信半徑內(nèi)有多個錨節(jié)點時，將兩個錨節(jié)點作為一組分成不同排列組合，其結果會有多個估計位置，將多個估計位置組成的幾何圖形的質(zhì)心作為未知節(jié)點的最終估計位置。

算法的一般流程圖如圖1所示。

圖1 算法流程圖Fig.1 Flow chart of algorithm

1.2 估計位置過濾

當未知節(jié)點的通信半徑內(nèi)有多個錨節(jié)點時，對于任意不共線的兩個錨節(jié)點都能確定一個估計位置，由于錨節(jié)點的選擇問題，估計位置可能存在某些誤差較大的點，將這些估計位置排除，會提高系統(tǒng)的定位精度。

過濾誤差較大的估計位置的方法：假設有A（xa，ya），B（xb，yb），C（xc，yc），D（xd，yd），E（xe，ye）5 個估計位置，首先計算任意兩個估計位置間的距離為 Sij（如表1所示），Sij=

表1 估計位置之間的距離Tab.1 Distance of the estimated location

設定一個距離閾值d，且節(jié)點與自身的距離取為∞，當表中存在某一行的距離值均大于d時，認為該點為不可靠位置，不參與計算。若A、B、C、D為可靠位置，則將4個位置構點的最終估計位置。

基于上述思想，對原有算法最后一步進行了求精，即求多個估計位置的平均值時，排除了誤差較大的位置，對算法進行了改進，為了陳述上的統(tǒng)一，對于改進后的算法稱為基于信號到達角度的改進定位算法（Improved AOA Localization Algorithm for Wireless Sensor Network，IAOA）。

算法的適用條件：

1）無線傳感器網(wǎng)絡節(jié)點部署在二維平面內(nèi)，傳感器節(jié)點都搭載有特殊硬件，可測得在通信半徑內(nèi)的鄰居錨節(jié)點的信號到達的角度值。

2）只有當估計位置個數(shù)大于等于3個時，才進行估計位置的過濾。對于只有兩個估計位置的，直接取兩個點的中點作為節(jié)點的最后估計位置。當只有一個估計位置時，該位置則為節(jié)點的最終估計位置。

2 仿真分析

為檢驗改進算法的性能，用MATLAB仿真工具對基于信號到達角度的定位算法（AOA）和本文提出的算法（IAOA）進行仿真實驗。

2.1 仿真環(huán)境設置

在100 m×100 m的監(jiān)測區(qū)域內(nèi)，隨機部署傳感器節(jié)點。傳感器節(jié)點數(shù)目為N，錨節(jié)點數(shù)目為n，傳感器節(jié)點的通信半徑r，角度測量偏差Δ。

定位誤差：節(jié)點實際位置和估計位置之間的距離。

定位覆蓋率：能夠進行定位的未知節(jié)點數(shù)與總的未知節(jié)點個數(shù)之比。

為了保證實驗的準確性，針對不同情況，本文分別進行了多次仿真，觀察、統(tǒng)計仿真結果，對多次結果求平均作為最后的評價結果。

取 N=50，n=10，r=50，Δ=3°（基于射頻的到達信號的角度測量標準偏差值在 3°左右[8]），d=0.08r，未知節(jié)點的定位誤差如圖2所示。

可見，IAOA的平均定位誤差較小，算法的定位精度有了一定的提升。

2.2 節(jié)點通信半徑對定位結果的影響

節(jié)點通信半徑是直接影響算法定位效果的重要因素，節(jié)點的通信半徑越大，覆蓋的監(jiān)測區(qū)域越大，未知節(jié)點的鄰居錨節(jié)點數(shù)目就越多，定位的覆蓋率和定位精度可能就越高，圖3分別給出了節(jié)點通信半徑在10～50時，兩種算法的定位精度與定位覆蓋率的情況。

圖2 未知節(jié)點的定位誤差圖Fig.2 Localization error of unknown nodes

圖3 通信半徑對定位結果的影響Fig.3 Communication radius influences on positioning accuracy

從圖3（a）可以看出，隨著節(jié)點通信半徑的增大，兩種算法的定位誤差都在逐漸下降，當r=30時，改進算法的定位精度明顯高于原有算法。繼續(xù)增大節(jié)點的通信半徑，定位精度提升的效果不是很明顯。圖3（b）表明，改進算法的定位覆蓋率與原算法基本一致，沒有多少改進，由于必須有多個估計位置時，算法才對結果進行排除求精，所以算法僅僅是對定位精度進行了提升，并沒有解決不能定位的盲區(qū)問題。因此，下文中將只針對定位精度對兩種算法進行比較。

2.3 錨節(jié)點個數(shù)對定位精度的影響

一般來說，錨節(jié)點個數(shù)越多，未知節(jié)點監(jiān)測到的錨節(jié)點數(shù)越多，定位覆蓋率就越高，定位誤差相對較小，定位性能就越好。但是，錨節(jié)點數(shù)量增多勢必會增加網(wǎng)絡的成本，兩者之間的矛盾是不可避免的，實際情況下，在能夠滿足定位需求的前提下，錨節(jié)點數(shù)目應盡可能的少。下面將觀察錨節(jié)點數(shù)量對算法定位精度的影響。

由圖4可見，隨著錨節(jié)點個數(shù)的增加，算法的定位精度都有所提升，但是改進算法下降較快，定位精度較高；當錨節(jié)點個數(shù)達到20時，改進算法其定位精度趨于平緩。

2.4 節(jié)點密度對定位精度的影響

單位面積上部署的節(jié)點數(shù)量，稱為節(jié)點密度。對于一定的監(jiān)測區(qū)域，當節(jié)點密度高時，在通信半徑相同的情況下，未知節(jié)點更容易被更多的錨節(jié)點監(jiān)測到，定位精度相對較高。

圖4 錨節(jié)點數(shù)目對定位精度的影響Fig.4 Anchor node number influences on positioning accuracy

實驗中，節(jié)點的通信半徑r固定不變，錨節(jié)點密度（錨節(jié)點與所有節(jié)點的比例）為10%，改變節(jié)點數(shù)量，觀察實驗結果。

圖5表明，當網(wǎng)絡監(jiān)測區(qū)域不變時，隨著網(wǎng)絡中節(jié)點數(shù)目的增多，節(jié)點密度增大時，算法的定位精度都在提高，且改進算法依舊能有較好的定位精度，但是節(jié)點數(shù)目的增加勢必會增大節(jié)點間的通信量，能耗也隨之增加，因此，節(jié)點數(shù)目的選擇應綜合考慮，達到所需要的定位精度即可。

圖5 節(jié)點數(shù)目對定位精度的影響Fig.5 Node number influences on positioning accuracy

3 結 論

文中提出的算法對基于信號到達角度的定位算法進行了改進，對最后的估計位置進行了選擇濾除，仿真實驗表明，本算法在定位精度方面與改進前方法有較大的提高，應用范圍也更加廣泛。但是改進算法對錨節(jié)點的密度有局限性，即網(wǎng)絡內(nèi)未知節(jié)點的鄰居錨節(jié)點平均數(shù)目大于3時，算法才能體現(xiàn)出其優(yōu)越性，所以改進算法不能有效解決網(wǎng)絡中錨節(jié)點密度較低時，定位覆蓋率低的問題，網(wǎng)絡中不能定位的盲區(qū)問題還有待進一步研究。

[1]王殊，閻毓杰，胡富平，等.無線傳感器網(wǎng)絡的理論及應用[M].北京：北京航空航天大學出版社，2007.

[2]YIXiao，LIUYu.Anovel environmentself-adaptivelocalization algorithm based on RSSI for wireless sensor network[C]//The 2010 IEEE International Conference on Wireless Communications， Networking and Information Security （IEEE WCNIS 2010）.Beijing.China:IEEEComputer Society，2010:360-363.

[3]宋文，王兵.無線傳感器網(wǎng)絡技術與應用[M].北京：電子工業(yè)出版社，2007.

[4]HE Tian，HUANG Cheng-du， Brain M Blum， et al.Rangefree Localization Schemesfor Large Scale Sensor Networks[C]//Proceedings of the 9th Annual International Conference on Mobile Computing and Networking （MobiCom）， San Diego，California， September， USA:ACM Press，2003:81-95.

[5]衣曉，劉瑜.無線傳感器網(wǎng)絡Range-free自身定位算法仿真分析[J].海軍航空工程學院學報，2009，24（4）:369-375.YI Xiao，LIU Yu.Wireless sensor network range-free localization algorithm simulation analysis[J].Journal of Naval Aeronautical and Astronautical University，2009，24 （4）:369-375.

[6]孫利民，李建中.無線傳感器網(wǎng)絡[M].北京：清華大學出版社，2005.

[7]Langendoen K，Reijers N.Distributed localization in wireless sensor networks:Aquantitativecomparison The Int’l[J].Journal of Computer and Telecommunications Networking，2003，43（4）:499-518.

[8]Collier S L，Wilson D K.Performance bounds for passive sensor arrays operating in a turbulent medium：plane-wave analysis[J].Acoust Soc America，2003，113（5）:2704-2718.