胡 彧,姚維照

(太原理工大學測控技術研究所,太原030024)

在傳感器網(wǎng)絡中,位置信息對傳感器網(wǎng)絡的監(jiān)測活動至關重要,傳感器網(wǎng)絡節(jié)點所采集到的數(shù)據(jù)必須結(jié)合其在測量坐標系內(nèi)的位置信息才有意義。對此,傳感器節(jié)點必須首先知道自身的地理位置信息,這是進一步采取措施和做出決策的基礎。因此采用一定的機制與算法實現(xiàn)無線傳感器網(wǎng)絡的自身定位是很有必要的[1]。

筆者主要研究不基于測距的粗精度質(zhì)心定位算法[2-3](Centroid Localization Algorithm,CLA)。CLA算法簡單易于實現(xiàn),計算速度快,平等地對待各個信標節(jié)點,但定位誤差大,對信標節(jié)點的密度依賴性強。為了降低CLA算法的定位誤差以及對信標節(jié)點較強的依賴性,本文對CLA算法進行多跳加權(quán)、誤差擴大、線性回歸校正及校正位置修正改進,提出了一種基于線性回歸的加權(quán)質(zhì)心定位算法(Liner Weighted Centroid Localization Algorithm,LWCLA)。改進算法降低了網(wǎng)絡的平均定位誤差,提高了節(jié)點定位比率,算法定位性能更加優(yōu)越。

1 加權(quán)質(zhì)心定位算法

1.1 基于跳數(shù)的加權(quán)質(zhì)心定位算法

對CLA算法中的每個信標節(jié)點進行加權(quán)因子約束,分別體現(xiàn)它們對未知節(jié)點估計位置決定權(quán)的大小,就形成了加權(quán)質(zhì)心定位算法(Weighted Centroid Localization Algorithm,WCLA)。其表達式通常如式(1),(2)的第一步[4]所示。目前WCLA算法有很多改進方案,基本上都是在測距模型的基礎上改進權(quán)值因子[5,6]。本文的加權(quán)改進方案則基于測距無關模型,通過未知節(jié)點與信標節(jié)點之間的跳數(shù)關系來體現(xiàn)信標節(jié)點對未知節(jié)點坐標決定權(quán)的大小,如下所示：

式中：N為信標節(jié)點數(shù)目;wi為信標節(jié)點i的權(quán)值因子;p i為信標節(jié)點i與未知節(jié)點之間的跳數(shù)。

網(wǎng)絡中的每個未知節(jié)點都可以根據(jù)自己與信標節(jié)點之間的跳數(shù)信息利用WCLA算法計算自身的估計位置,所以無論網(wǎng)絡中信標節(jié)點分布多少,網(wǎng)絡中的所有未知節(jié)點都可以實現(xiàn)定位,從而使定位比率提高至接近1。圖1第一列的三組圖形是基于跳數(shù)信息的WCLA算法定位效果圖,從圖中可以看出改進后的算法的定位誤差依然很大,并且未知節(jié)點的估計位置都不同程度的偏向于信標節(jié)點中心(所有信標節(jié)點位置取均值),此現(xiàn)象為中心化效應[7]。此現(xiàn)象也在預料之中,因為對于小型的網(wǎng)絡分布,節(jié)點的跳數(shù)信息差別不大,與節(jié)點的實際距離相差很大,所以基于跳數(shù)信息的WCLA算法在改進CLA算法的同時,也保留了CLA算法定位誤差大的缺陷;而且在改進方案中由于所有的信標節(jié)點都參與節(jié)點位置的計算,因此基于跳數(shù)信息的WCLA算法出現(xiàn)了中心化的效應。

1.2 位置估計中心化

基于跳數(shù)信息的WCLA算法在降低誤差方面的效果不是很明顯。但基于它本身中心化的特點,本文在WCLA算法的基礎上進行加強中心化的改進[8](Improved Weighted Centroid Localization Algorithm,IWCLA),將基于跳數(shù)WCLA算法的定位誤差擴大化,使位置估計中心化的效果更加明顯清晰,找到節(jié)點定位誤差之間的內(nèi)在關系。其中心化的思路為：當未知節(jié)點根據(jù)加權(quán)質(zhì)心算法獲得自身的估計位置后,將此位置記錄為自己的初次估計位置;當所有節(jié)點的初次估計位置都記錄完畢,未知節(jié)點再與其通信范圍內(nèi)的所有鄰未知節(jié)點交換信息,獲得其他未知節(jié)點的初次估計位置,并將自己以及所有鄰未知節(jié)點的初次估計位置取平均值記錄為自己的最終估計位置。IWCLA算法的二次計算通過未知節(jié)點周圍的鄰節(jié)點來計算自身位置,該種方式以加法的方式擴大了未知節(jié)點與信標節(jié)點跳數(shù)信息的影響。因此,相對于WCLA算法,網(wǎng)絡中未知節(jié)點的估計位置更加偏向于信標節(jié)點的中心,中心化的效果將更加明顯,誤差的規(guī)律性也將更加顯著。

通過公式(3)可以計算節(jié)點的定位精度[9],由公式(3)可以看出,節(jié)點的平均定位誤差和定位精度成正比,平均定位誤差越小,定位精度就越小,算法的定位性能也就越好。

式中：L為節(jié)點定位精度;LE為平均定位誤差;R為節(jié)點通信半徑;n est為網(wǎng)絡中可獲得位置的節(jié)點數(shù)目;N為信標節(jié)點數(shù)目;n為網(wǎng)絡節(jié)點總數(shù);(x,y)為節(jié)點實際位置,(xest,yest)為節(jié)點估計位置。

在MATLAB仿真平臺上,一般設定115個傳感器節(jié)點隨機均勻地分布在100 m×100 m的正方形區(qū)域內(nèi),網(wǎng)絡中的信標節(jié)點數(shù)目N=15,通信半徑R=50 m。分別對WCLA算法和IWCLA算法進行仿真對比,如圖1所示。

圖1 中的仿真結(jié)果證實了理論分析的正確性。其中黑色的點代表可以通過二次計算的方式來增強基于跳數(shù)WCLA算法的中心化效應,使估計位置的分布更具有規(guī)律性。表1中記錄的是兩種算法的L值,可以看出,IWCLA算法的平均定位誤差較大,相對WCLA算法,IWCLA算法的定位性能降低了30%左右。但 IWCLA算法的中心化效應非常顯著。中心化效應增大誤差的同時,誤差的分布更具有規(guī)律性,可借此規(guī)律盡可能減小誤差。

表1 WCLA算法與IWCLA算法L對比表

2 基于線性回歸的加權(quán)質(zhì)心定位算法

2.1 基于線性回歸的加權(quán)質(zhì)心定位算法

圖1中,由IWCLA算法計算得到的估計位置都集中在信標節(jié)點的中心位置附近。將未知節(jié)點的估計位置與實際位置分別減去信標節(jié)點中心位置的坐標值后可得到如圖2所示的關系分布圖。從圖2可看出,利用IWCLA算法定位未知節(jié)點的估計位置與實際位置存在一定的線性關系。利用線性回歸的數(shù)學模型[10]確定該線性圖像的關系系數(shù),據(jù)此本文給出了位置校正公式如(4)—(6)所示,通過LWCLA算法獲得位置的未知節(jié)點將按照此公式來校正自己的位置?？煞Q此過程為去中心化過程,也可稱為邊緣化過程(未知節(jié)點的估計位置趨向于網(wǎng)絡邊緣)。

圖2 未知節(jié)點的估計位置與實際位置的關系曲線圖

由圖3可以看出,網(wǎng)絡中通訊半徑R=15與節(jié)點總數(shù)n=115,經(jīng)過1 000輪的仿真實驗,校正系數(shù)ax,bx,ay,by的值波動不大。在本文中校正系數(shù)ax,bx,ay,by取1 000輪仿真實驗的均值。還應考慮到由于網(wǎng)絡節(jié)點的分布不同,校正系數(shù)ax,bx,ay,by的值如圖3所示是波動的,并且圖2所示的關系曲線表明節(jié)點的坐標關系并不呈嚴格的線性關系,針對所有的未知節(jié)點采用相同的校正系數(shù),會出現(xiàn)去中心化太過,導致邊緣化效應非常顯著,使定位出現(xiàn)失真的情況。因此,為了合理估計待定位節(jié)點的位置,本文將邊緣化、中心化及質(zhì)心化(直接通過CLA算法計算得到的估計位置)三種位置估計按照本文所給出的公式(7),(8)進行修正。式中的修正系數(shù)a,b,c隨著R與n數(shù)值的變化而發(fā)生變化,因此在利用此公式之前,應針對特定網(wǎng)絡環(huán)境,在仿真實驗上調(diào)節(jié)修正系數(shù)a,b,c,使定位誤差達到最小。

式中：(xestc,yestc)為CLA算法估計位置坐標值;)為IWCLA算法估計位置坐標值;(x estl,y estl為LWCLA算法估計位置坐標值,a,b,c為修正系數(shù),三者之和等于1。

2.2 仿真結(jié)果

IWCLA算法的定位流程可總結(jié)如下。

1)各個未知節(jié)點搜索自己范圍內(nèi)的鄰節(jié)點,獲得網(wǎng)絡中所有信標節(jié)點的位置信息以及與它們的跳數(shù)關系。

圖3 N=100,n=15,R=50時a x,bx,ay,by的關系圖

2)各個未知節(jié)點根據(jù)收集到的信息,按照WCLA算法公式(1),(2)計算自身的估計位置。

3)各個未知節(jié)點與其通信范圍內(nèi)的鄰未知節(jié)點交換信息,獲得它們的估計位置,并將其自身以及所有鄰未知節(jié)點的估計位置取平均值記錄為自己的估計位置。

5)按照公式(4)—(6)及步驟4計算得到的校正系數(shù)校正自身的估計位置。

6)將步驟1,3,5所得的估計位置按照公式(7),(8)及由步驟4選擇的修正系數(shù)對節(jié)點的位置最后進行修正。

7)按照公式(3)計算整個網(wǎng)絡的定位精度,網(wǎng)絡的定位誤差越小,定位精度就越小,算法定位性能也就越好。

在2.2節(jié)設定的網(wǎng)絡環(huán)境下,對WCLA算法、IWCLA算法及LWCLA算法進行仿真對比。

圖4 三種算法定位精度對比圖

從表2所記錄的三種算法的L數(shù)值可以分析出,相對于WCLA算法,IWCLA算法的定位性能降低了31.46%,而 LWCLA算法的性能提高了62.58%。由此LWCLA算法在不基于距離信息的情況下使WCLA算法的定位誤差下降了60%以上,改進效果非常明顯。

表2 三種算法定位精度對比表

圖4代表三種算法的定位精度隨著網(wǎng)絡中信標節(jié)點的增多而降低的關系圖。三種算法的平均定位誤差都隨著網(wǎng)絡中信標節(jié)點數(shù)目的增多而不斷下降,但 LWCLA算法的平均定位誤差始終低于WCLA算法、IWCLA算法。取三種算法的平均定位精度LE作為對比指標,分析表2可以得出,與原始質(zhì)心算法相比,LWCLA算法的L E下降了62.43%,也就意味著算法的平均定位誤差下降了62.43%,定位性能提高了62.43%;并且LWCLA算法通過多跳加權(quán)及算法增強兩方面的改進,在信標節(jié)點密度較低的情況下,使節(jié)點的定位比率提高至接近1。

3 結(jié)論

CLA算法簡單易于實現(xiàn),功耗低,對硬件設備要求不高,算法運行速度快,但其定位誤差較大,僅能作為對未知節(jié)點實際位置的估計。本文提出的LWCLA算法在質(zhì)心算法的基礎上進行加權(quán)、中心化及利用線性回歸的數(shù)學模型對節(jié)點位置進行校正,最后又對校正位置進行了修正。仿真結(jié)果表明,LWCLA算法簡單易于實現(xiàn),算法復雜度低,使CLA算法的定位誤差降低了60%以上,在信標節(jié)點密度較低的情況下,還可使節(jié)點的定位比率提高至接近1,取得了良好的算法性能改善結(jié)果。

[1] 王福豹,史 龍,任豐源.無線傳感器網(wǎng)絡中的自身定位系統(tǒng)和算法[J].軟件學報,2005,16(15)：857-868.

[2] Nirupama Bulusu,John Heiemann,Deborah Estrin.GPS-less Low Cost Our-Door Locaization for Very Small Devices[J].IEEEPersonal Communications,2000,7(5)：28-34.

[3] Deng B D,Huang G M,Zhang L.Improved centroid localization algorithm in WSNs[C]∥The 3rd International Conference on Intelligent System and Knowledge Engineering,2008：1260-1264.

[4] 陳維克,李文鋒.基于RSSI的無線傳感器網(wǎng)絡加權(quán)質(zhì)心定位算法[J].武漢理工大學學報,2006,30(2)：265-268.

[5] 白進京,嚴新平,張存保.基于加權(quán)質(zhì)心和DV-Hop混合算法WSN定位方法研究[J].計算機應用研究,2009,26(6)：2248-2250.

[6] Gao Lipeng,Zhu Meidong,Yang Dan.Simulation and Implement of Weighted Centroid Localization Algorithm Based on Zig-Bee[J].Chinese Journal of Sensors and Aciuators,2010,23(1)：149-152.

[7] 安恂,蔣挺,周正.一種用于無線傳感器網(wǎng)絡的質(zhì)心定位算法[J].計算機工程與應用,2007,43(20)：136-138.

[8] 李兆斌,魏占禎,徐風麟.無線傳感器網(wǎng)絡增強的質(zhì)心定位算法及性能分析[J].傳感技術學報,2009,22(4)：563-566.

[9] Kerem Kucuk,Adnan Kavak.Scalable location estimation using smart antennas in wireless sensor networks[J].Ad Hoc Network,2010,8：889-903.

[10] 費業(yè)泰,陳曉才,秦 嵐,陳林才.誤差理論與數(shù)據(jù)處理[M].北京：機械工業(yè)出版社,2007：120-155.