無線傳感器網絡改進質心算法的節點自定位

張 華，劉玉良，單海校

（浙江海洋學院機電工程學院，浙江舟山 316000）

傳感器節點自定位就是根據少數已知位置的節點，按照某種定位機制確定自身的位置。在無線傳感器網絡各種應用中，應當知曉監測目標的具體位置，沒有確切監測消息的位置沒有任何意義[1]。根據節點是否知道自身的位置信息，把傳感器節點分為信標節點和未知節點；按照定位過程中是否需要測量節點之間的實際距離，把定位算法分為基于距離的定位算法和距離無關的定位算法。無須測距的定位機制僅僅依靠網絡的連通性等參數進行定位，主要定位機制包括質心算法、DV-Hop算法、Amorphous算法、APIT算法等。距離無關的定位機制定位性能受環境因素的影響小，雖然定位的誤差相應有所增加，但定位精度能夠滿足多數傳感器網絡的應用要求，是目前大家普遍重點關注的定位機制[1-7]。

質心算法是南加州大學的Nirupama Bulusu等提出了一種僅基于網絡節點連通性的定位算法，這種估算的精度取決于信標節點的密度和分布。許多人針對質心算法提出了改進思路，文獻[2]提出一種密度自適應的HEAP算法，通過在信標節點密度低的區域增加新標節點，以提高定位的精度；文獻[3]中提對距離無關的幾種定位機制進行了比較，信標節點密度的大小影響了定位精度的高低，還有一些文獻通過對信標節點與未知節點的距離的研究，如采用時間差或以距離作為權值參數來討論定位的精度問題。考慮在不增加信標節點密度的情況下以節點間的距離作為約束，探討通信半徑和節點數對節點定位精度的影響，采用極大似然估計法對函數進行優化，改進節點自定位的精度。

1 傳統質心算法

從現有的文獻[4]和研究結果來看，對于以隨機拋灑形式分布的，以自組織構建而成的無線傳感器網絡而言，節點一般有如下分布：均勻分布、高斯分布、瑞利分布等，其中以高斯分布模型最為常見。為研究問題方便，假定所有節點都布撒于同一個平面體系中，且各節點的通信模型選取圓形通信模型。

質心算法僅基于網絡節點連通性，思想是：信標節點每隔一段時間，向鄰居節點廣播一個信標信號，信號中包含自身ID和位置信息。當未知節點接收到來自不同信標節點的信標信號數量超過某一個預設門限或接收一定時間后，該節點就確定自身位置為這些信標節點所組成的多邊形的質心。

在傳感器網絡節點布置后，信標節點將周期性向周圍發布自身信息。設有一未知節點p與周圍n個信標節點建立聯系，各信標節點的坐標分別為（x1，y1），（x2，y2），（x3，y4）…（xn，yn），按以上假設可以在二維空間中對問題進行探討，按照質心算法的思路，未知節點對自身的估算坐標P（xcen，ycen）為，

然而試驗表明，用質心坐標作未知節點的坐標，由于受到節點分布密度、節點分布模型、信號傳輸環境噪聲，節點自身性能等影響，大約有90%未知節點定位精度低于信標節點間距的1/3[1,4]。

2 極大似然估計法的改進模型

質心算法完全基于網絡的連通性，受分布密度、分布模型、信號傳輸模型等影響，使得定位誤差較大[2,5]，從數學角度來說，質心坐標僅僅依賴于信標節點的坐標，沒有受到其他條件的約束，本文考慮保留質心算法的定位優越性，以信標節點與未知節點之間的距離作約束，以提高定位精度。

假設該未知節點p與其通信的各信標節點間的距離分別為d1，d2，d3，…dn，按照解析幾何原理建立信標節點與未知節點p間的距離方程組，其中，未知節點的坐標為估算坐標p（xest，yest），如下

極大似然估計法采用對上式各等式相減，變形并采用矩陣形式，進而通過線性方程求出未知節點坐標。將信標節點的坐標（x1，y1），（x2，y2），…，（xn，yn）看成 X1，X2，…，Xn的樣本值，樣本函數 P｛ X = Xi｝=p（（xi，y）i，θ），其中（xi，y）i∈D，θ∈D；D代表所設定的區域取值范圍，傳感器網絡節點在相互之間通信過程中，受噪聲干擾影響，節點分布密度，節點間距離測量誤差以及節點自身計算能力不足引起的計算誤差等[5,6]，將使得公式2不會全部成立，假設各信標節點與未知節點p之間的測距誤差分別為δ1，δ2，…，δn

3 算法步驟設計

假設信標節點和未知節點可以分開進行布撒，首先將信標節點進行均勻分布，在100×100單位面積中，均勻布撒100個信標節點，信標節點通過GPS或者向周圍發布自身信息等方式構建成網絡，此時各信標節點都已經獲知自身各種信息，然后再將未知節點隨機布撒，設通信半徑為R。節點初始分布圖如圖1所示。

算法設計如下：

①在100×100單位中，按均勻分布方式布置100個節點，作為信標節點，各信標節點都已知道自身信息；

②在該區域內，隨機布撒若干節點，即為未知節點；各未知節點向周圍發送信息，搜索自身通信范圍內的信標節點；

③測算該未知節點與信標節點的距離；

④每個未知節點按照公式1計算出與其通信的信標節點的質心坐標；質心坐標作為該未知節點的初次估算位置；

⑤在圖中標出該未知節點對應的質心坐標，并將質心與該未知節點用線畫出；

⑥按照公式5計算出計算極大似然值，若是最大值則輸出，若不是則返回③，繼續搜索，尋求直到滿足要求。

4 仿真結果及分析

在不同的通信半徑，不同的未知節點數目的優化分布圖形如下，其中通信半徑分別取50單位和30單位，信標節點取均勻分布100個，未知節點分別取50個，20個。圖中藍色圓點表示信標節點，各坐標取值范圍是0≤x≤100；0≤y≤100；紅色“*”表示未知節點，藍色“o”表示質心坐標位置，紅色的短線表示某未知節點通信范圍內的信標節點的質心與該未知節點的連線。采用主頻為3G的計算機在matlab7.0.1環境下進行仿真。

圖1 各節點初始化分布Fig.1 Distribution of each node initialization

圖2 50個未知節點，通信半徑30時節點分布Fig.2 50 unknown nodes,the nodes distribution when communication radius is 30

圖3 50個節點，半徑30時誤差分布Fig.3 Error distribution 50 unknown nodes,communication radius of 30

圖4 20個未知節點，通信半徑30時節點分布Fig.4 The nodes distribution 20 unknown nodes,communication radius of 30

圖5 20個節點，通信半徑30誤差分布Fig.5 Error distribution 20 unknown nodes,communication radius of 30

圖6 20個未知節點，通信半徑50時節點分布Fig.6 The nodes distribution 20 unknown nodes,communication radius of 50

圖7 20個節點，通信半徑50誤差分布Fig.7 Error distribution 20 unknown nodes,communication radius of 50

圖8 信標節點個數與誤差值Fig.8 The number of beacon nodes and error

圖1為節點初始分布圖，表示信標節點均勻分布，未知節點隨機分布，其中信標節點數目為100，未知節點數目為20。圖2、圖4、圖6，表示未知節點與其所對應的質心點；圖3、圖5、圖7表示各未知節點的測量誤差值分布。圖8表示信標節點與誤差值的變化關系。

①從圖2～圖7可以看出，未知節點分布是非均勻分布，誤差值跟節點數目有關；數目越大，誤差越小；由于信標節點已經處于均勻分布狀態，未知節點的數目也能對定位產生較大影響。考慮到實際情況，信標節點在完成部署以后，不間斷的向周圍傳播自身信息，當其中有些未知節點在經過算法迭代完成自身定位后，也加入到不間斷傳播自己位置信息的行列，而這些未知節點自身的位置信息本身精度就不高，誤差經過不斷的迭代疊加，從而使得整體定位精度不夠高。

②從圖4和圖6可以看出質心坐標有趨向中心分布，圖4的通信半徑為30單位，而圖6為50單位，表明通信半徑越大，質心坐標越向中心分布，此時誤差值也越大（誤差可對比圖5和圖7）；對比圖2和圖4，可以觀察相同的通信半徑下，節點數目越大，對應的誤差值要越小。回到傳感器網絡實際狀況，給定信標節點的位置是均勻分布，且密度較高，當通信半徑在擴大時，表明某個未知節點周圍與其通信的信標節點在增加，均勻分布的信標節點的質心位置一定會趨向于整個坐標中心位置，實際上，對應的未知節點卻可能分布在邊緣，這樣使得誤差值要明顯偏大，如圖6分布。

③從圖8可以觀察到信標節點與誤差值的關系，表明在未知節點數目一定，通信半徑一定的情況下，信標節點越多，所產生的誤差值越小。文獻[3]就是論證了通過在信標節點密度低的區域增加新標節點，以提高定位的精度。

5 結束語

仿真結果表明，采用極大似然估計法情況下，在信標節點均勻分布而未知節點隨機分布的傳感器網絡中，節點的通信半徑越大，誤差越大，定位精度越低；信標節點的數目越多，誤差越小，定位精度越高；當信標節點數目一定時，未知節點越多，誤差越大，定位精度越低。

[1]孫利民,李建中,陳 渝,等.無線傳感器網絡[M].北京:清華大學出版社,2005.

[2]BULUSU N,HEIDEMANN J,ESTRIN D.Density adaptive algorithms for beacon placement in wireless sensor networks[C]//IEEE ICDCS’01,Phoenix,AZ.April 2001.

[3]HE Tian,HUANG Chengdu,BLUM Brian M,et al.Range-Free Localization Schemes in Large Scale Sensor Networks[C]//Proceedings of the 9th Annual Inter2 National Conference on Mobile Computing and Networking(MobiCom),San Diego,California,USA:ACM Press,2003:81-95.

[4]JOURDAN D B,DE WECK O L.Multi-objective genetic algorithm for the automated planning of a wireless sensor network to monitor a critical facility,2004:Citeseer.http://74.125.155.132/scholar?q=cache:Bcn_4LwctagJ:scholar.google.com/&hl=zh-CN&as_sdt=0

[5]田金鵬.無線傳感器網絡節點定位技術研究[D].上海:上海大學,2009.

[6]江 冰,吳元忠,謝冬梅.無線傳感器網絡節點自定位算法的研究[J].傳感技術學報,2007,20(6):1 381-1 385.

[7]SHENG X,HU Y H.Maximum likelihood multiple-source localization using acoustic energy measurements with wireless sensor networks[C]//Signal Processing,IEEE Transactions on2005,53(1):44-53.