基于線性回歸的無線傳感器網絡加權質心定位算法

胡 彧,姚維照

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

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

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

1 加權質心定位算法

1.1 基于跳數的加權質心定位算法

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

式中：N為信標節點數目;wi為信標節點i的權值因子;p i為信標節點i與未知節點之間的跳數。

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

1.2 位置估計中心化

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

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

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

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

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

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

2 基于線性回歸的加權質心定位算法

2.1 基于線性回歸的加權質心定位算法

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

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

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

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

2.2 仿真結果

IWCLA算法的定位流程可總結如下。

1)各個未知節點搜索自己范圍內的鄰節點,獲得網絡中所有信標節點的位置信息以及與它們的跳數關系。

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

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

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

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

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

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

在2.2節設定的網絡環境下,對WCLA算法、IWCLA算法及LWCLA算法進行仿真對比。

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

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

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

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

3 結論

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

[1] 王福豹,史 龍,任豐源.無線傳感器網絡中的自身定位系統和算法[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的無線傳感器網絡加權質心定位算法[J].武漢理工大學學報,2006,30(2)：265-268.

[5] 白進京,嚴新平,張存保.基于加權質心和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] 安恂,蔣挺,周正.一種用于無線傳感器網絡的質心定位算法[J].計算機工程與應用,2007,43(20)：136-138.

[8] 李兆斌,魏占禎,徐風麟.無線傳感器網絡增強的質心定位算法及性能分析[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] 費業泰,陳曉才,秦 嵐,陳林才.誤差理論與數據處理[M].北京：機械工業出版社,2007：120-155.