王梓有，周憲英

（1.海軍航空工程學(xué)院 山東 煙臺(tái) 264001；2.92941部隊(duì) 遼寧 葫蘆島 125001）

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

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

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

1 理論分析

1.1 基于信號(hào)到達(dá)角度的定位算法

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

第二步利用夾角射線(xiàn)原則解方程，計(jì)算未知節(jié)點(diǎn)的估計(jì)位置，假設(shè)未知節(jié)點(diǎn) P（x，y），測(cè)量 A（x1，y1）、B（x2，y2）兩個(gè)錨節(jié)點(diǎn)的信號(hào)到達(dá)角度信息為α、β，解方程：

可得未知節(jié)點(diǎn)P的坐標(biāo)

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

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

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

1.2 估計(jì)位置過(guò)濾

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

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

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

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

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

算法的適用條件：

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

2）只有當(dāng)估計(jì)位置個(gè)數(shù)大于等于3個(gè)時(shí)，才進(jìn)行估計(jì)位置的過(guò)濾。對(duì)于只有兩個(gè)估計(jì)位置的，直接取兩個(gè)點(diǎn)的中點(diǎn)作為節(jié)點(diǎn)的最后估計(jì)位置。當(dāng)只有一個(gè)估計(jì)位置時(shí)，該位置則為節(jié)點(diǎn)的最終估計(jì)位置。

2 仿真分析

為檢驗(yàn)改進(jìn)算法的性能，用MATLAB仿真工具對(duì)基于信號(hào)到達(dá)角度的定位算法（AOA）和本文提出的算法（IAOA）進(jìn)行仿真實(shí)驗(yàn)。

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

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

定位誤差：節(jié)點(diǎn)實(shí)際位置和估計(jì)位置之間的距離。

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

為了保證實(shí)驗(yàn)的準(zhǔn)確性，針對(duì)不同情況，本文分別進(jìn)行了多次仿真，觀(guān)察、統(tǒng)計(jì)仿真結(jié)果，對(duì)多次結(jié)果求平均作為最后的評(píng)價(jià)結(jié)果。

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

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

2.2 節(jié)點(diǎn)通信半徑對(duì)定位結(jié)果的影響

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

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

圖3 通信半徑對(duì)定位結(jié)果的影響Fig.3 Communication radius influences on positioning accuracy

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

2.3 錨節(jié)點(diǎn)個(gè)數(shù)對(duì)定位精度的影響

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

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

2.4 節(jié)點(diǎn)密度對(duì)定位精度的影響

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

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

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

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

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

3 結(jié) 論

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

[1]王殊，閻毓杰，胡富平，等.無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的理論及應(yīng)用[M].北京：北京航空航天大學(xué)出版社，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ú)線(xiàn)傳感器網(wǎng)絡(luò)技術(shù)與應(yī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ú)線(xiàn)傳感器網(wǎng)絡(luò)Range-free自身定位算法仿真分析[J].海軍航空工程學(xué)院學(xué)報(bào)，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ú)線(xiàn)傳感器網(wǎng)絡(luò)[M].北京：清華大學(xué)出版社，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.