無(wú)線傳感器網(wǎng)絡(luò)改進(jìn)質(zhì)心算法的節(jié)點(diǎn)自定位

張 華，劉玉良，單海校

（浙江海洋學(xué)院機(jī)電工程學(xué)院，浙江舟山 316000）

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

質(zhì)心算法是南加州大學(xué)的Nirupama Bulusu等提出了一種僅基于網(wǎng)絡(luò)節(jié)點(diǎn)連通性的定位算法，這種估算的精度取決于信標(biāo)節(jié)點(diǎn)的密度和分布。許多人針對(duì)質(zhì)心算法提出了改進(jìn)思路，文獻(xiàn)[2]提出一種密度自適應(yīng)的HEAP算法，通過(guò)在信標(biāo)節(jié)點(diǎn)密度低的區(qū)域增加新標(biāo)節(jié)點(diǎn)，以提高定位的精度；文獻(xiàn)[3]中提對(duì)距離無(wú)關(guān)的幾種定位機(jī)制進(jìn)行了比較，信標(biāo)節(jié)點(diǎn)密度的大小影響了定位精度的高低，還有一些文獻(xiàn)通過(guò)對(duì)信標(biāo)節(jié)點(diǎn)與未知節(jié)點(diǎn)的距離的研究，如采用時(shí)間差或以距離作為權(quán)值參數(shù)來(lái)討論定位的精度問(wèn)題?？紤]在不增加信標(biāo)節(jié)點(diǎn)密度的情況下以節(jié)點(diǎn)間的距離作為約束，探討通信半徑和節(jié)點(diǎn)數(shù)對(duì)節(jié)點(diǎn)定位精度的影響，采用極大似然估計(jì)法對(duì)函數(shù)進(jìn)行優(yōu)化，改進(jìn)節(jié)點(diǎn)自定位的精度。

1 傳統(tǒng)質(zhì)心算法

從現(xiàn)有的文獻(xiàn)[4]和研究結(jié)果來(lái)看，對(duì)于以隨機(jī)拋灑形式分布的，以自組織構(gòu)建而成的無(wú)線傳感器網(wǎng)絡(luò)而言，節(jié)點(diǎn)一般有如下分布：均勻分布、高斯分布、瑞利分布等，其中以高斯分布模型最為常見(jiàn)。為研究問(wèn)題方便，假定所有節(jié)點(diǎn)都布撒于同一個(gè)平面體系中，且各節(jié)點(diǎn)的通信模型選取圓形通信模型。

質(zhì)心算法僅基于網(wǎng)絡(luò)節(jié)點(diǎn)連通性，思想是：信標(biāo)節(jié)點(diǎn)每隔一段時(shí)間，向鄰居節(jié)點(diǎn)廣播一個(gè)信標(biāo)信號(hào)，信號(hào)中包含自身ID和位置信息。當(dāng)未知節(jié)點(diǎn)接收到來(lái)自不同信標(biāo)節(jié)點(diǎn)的信標(biāo)信號(hào)數(shù)量超過(guò)某一個(gè)預(yù)設(shè)門限或接收一定時(shí)間后，該節(jié)點(diǎn)就確定自身位置為這些信標(biāo)節(jié)點(diǎn)所組成的多邊形的質(zhì)心。

在傳感器網(wǎng)絡(luò)節(jié)點(diǎn)布置后，信標(biāo)節(jié)點(diǎn)將周期性向周圍發(fā)布自身信息。設(shè)有一未知節(jié)點(diǎn)p與周圍n個(gè)信標(biāo)節(jié)點(diǎn)建立聯(lián)系，各信標(biāo)節(jié)點(diǎn)的坐標(biāo)分別為（x1，y1），（x2，y2），（x3，y4）…（xn，yn），按以上假設(shè)可以在二維空間中對(duì)問(wèn)題進(jìn)行探討，按照質(zhì)心算法的思路，未知節(jié)點(diǎn)對(duì)自身的估算坐標(biāo)P（xcen，ycen）為，

然而試驗(yàn)表明，用質(zhì)心坐標(biāo)作未知節(jié)點(diǎn)的坐標(biāo)，由于受到節(jié)點(diǎn)分布密度、節(jié)點(diǎn)分布模型、信號(hào)傳輸環(huán)境噪聲，節(jié)點(diǎn)自身性能等影響，大約有90%未知節(jié)點(diǎn)定位精度低于信標(biāo)節(jié)點(diǎn)間距的1/3[1,4]。

2 極大似然估計(jì)法的改進(jìn)模型

質(zhì)心算法完全基于網(wǎng)絡(luò)的連通性，受分布密度、分布模型、信號(hào)傳輸模型等影響，使得定位誤差較大[2,5]，從數(shù)學(xué)角度來(lái)說(shuō)，質(zhì)心坐標(biāo)僅僅依賴于信標(biāo)節(jié)點(diǎn)的坐標(biāo)，沒(méi)有受到其他條件的約束，本文考慮保留質(zhì)心算法的定位優(yōu)越性，以信標(biāo)節(jié)點(diǎn)與未知節(jié)點(diǎn)之間的距離作約束，以提高定位精度。

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

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

3 算法步驟設(shè)計(jì)

假設(shè)信標(biāo)節(jié)點(diǎn)和未知節(jié)點(diǎn)可以分開(kāi)進(jìn)行布撒，首先將信標(biāo)節(jié)點(diǎn)進(jìn)行均勻分布，在100×100單位面積中，均勻布撒100個(gè)信標(biāo)節(jié)點(diǎn)，信標(biāo)節(jié)點(diǎn)通過(guò)GPS或者向周圍發(fā)布自身信息等方式構(gòu)建成網(wǎng)絡(luò)，此時(shí)各信標(biāo)節(jié)點(diǎn)都已經(jīng)獲知自身各種信息，然后再將未知節(jié)點(diǎn)隨機(jī)布撒，設(shè)通信半徑為R。節(jié)點(diǎn)初始分布圖如圖1所示。

算法設(shè)計(jì)如下：

①在100×100單位中，按均勻分布方式布置100個(gè)節(jié)點(diǎn)，作為信標(biāo)節(jié)點(diǎn)，各信標(biāo)節(jié)點(diǎn)都已知道自身信息；

②在該區(qū)域內(nèi)，隨機(jī)布撒若干節(jié)點(diǎn)，即為未知節(jié)點(diǎn)；各未知節(jié)點(diǎn)向周圍發(fā)送信息，搜索自身通信范圍內(nèi)的信標(biāo)節(jié)點(diǎn)；

③測(cè)算該未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)的距離；

④每個(gè)未知節(jié)點(diǎn)按照公式1計(jì)算出與其通信的信標(biāo)節(jié)點(diǎn)的質(zhì)心坐標(biāo)；質(zhì)心坐標(biāo)作為該未知節(jié)點(diǎn)的初次估算位置；

⑤在圖中標(biāo)出該未知節(jié)點(diǎn)對(duì)應(yīng)的質(zhì)心坐標(biāo)，并將質(zhì)心與該未知節(jié)點(diǎn)用線畫出；

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

4 仿真結(jié)果及分析

在不同的通信半徑，不同的未知節(jié)點(diǎn)數(shù)目的優(yōu)化分布圖形如下，其中通信半徑分別取50單位和30單位，信標(biāo)節(jié)點(diǎn)取均勻分布100個(gè)，未知節(jié)點(diǎn)分別取50個(gè)，20個(gè)。圖中藍(lán)色圓點(diǎn)表示信標(biāo)節(jié)點(diǎn)，各坐標(biāo)取值范圍是0≤x≤100；0≤y≤100；紅色“*”表示未知節(jié)點(diǎn)，藍(lán)色“o”表示質(zhì)心坐標(biāo)位置，紅色的短線表示某未知節(jié)點(diǎn)通信范圍內(nèi)的信標(biāo)節(jié)點(diǎn)的質(zhì)心與該未知節(jié)點(diǎn)的連線。采用主頻為3G的計(jì)算機(jī)在matlab7.0.1環(huán)境下進(jìn)行仿真。

圖1 各節(jié)點(diǎn)初始化分布Fig.1 Distribution of each node initialization

圖2 50個(gè)未知節(jié)點(diǎn)，通信半徑30時(shí)節(jié)點(diǎn)分布Fig.2 50 unknown nodes,the nodes distribution when communication radius is 30

圖3 50個(gè)節(jié)點(diǎn)，半徑30時(shí)誤差分布Fig.3 Error distribution 50 unknown nodes,communication radius of 30

圖4 20個(gè)未知節(jié)點(diǎn)，通信半徑30時(shí)節(jié)點(diǎn)分布Fig.4 The nodes distribution 20 unknown nodes,communication radius of 30

圖5 20個(gè)節(jié)點(diǎn)，通信半徑30誤差分布Fig.5 Error distribution 20 unknown nodes,communication radius of 30

圖6 20個(gè)未知節(jié)點(diǎn)，通信半徑50時(shí)節(jié)點(diǎn)分布Fig.6 The nodes distribution 20 unknown nodes,communication radius of 50

圖7 20個(gè)節(jié)點(diǎn)，通信半徑50誤差分布Fig.7 Error distribution 20 unknown nodes,communication radius of 50

圖8 信標(biāo)節(jié)點(diǎn)個(gè)數(shù)與誤差值Fig.8 The number of beacon nodes and error

圖1為節(jié)點(diǎn)初始分布圖，表示信標(biāo)節(jié)點(diǎn)均勻分布，未知節(jié)點(diǎn)隨機(jī)分布，其中信標(biāo)節(jié)點(diǎn)數(shù)目為100，未知節(jié)點(diǎn)數(shù)目為20。圖2、圖4、圖6，表示未知節(jié)點(diǎn)與其所對(duì)應(yīng)的質(zhì)心點(diǎn)；圖3、圖5、圖7表示各未知節(jié)點(diǎn)的測(cè)量誤差值分布。圖8表示信標(biāo)節(jié)點(diǎn)與誤差值的變化關(guān)系。

①?gòu)膱D2～圖7可以看出，未知節(jié)點(diǎn)分布是非均勻分布，誤差值跟節(jié)點(diǎn)數(shù)目有關(guān)；數(shù)目越大，誤差越??；由于信標(biāo)節(jié)點(diǎn)已經(jīng)處于均勻分布狀態(tài)，未知節(jié)點(diǎn)的數(shù)目也能對(duì)定位產(chǎn)生較大影響?？紤]到實(shí)際情況，信標(biāo)節(jié)點(diǎn)在完成部署以后，不間斷的向周圍傳播自身信息，當(dāng)其中有些未知節(jié)點(diǎn)在經(jīng)過(guò)算法迭代完成自身定位后，也加入到不間斷傳播自己位置信息的行列，而這些未知節(jié)點(diǎn)自身的位置信息本身精度就不高，誤差經(jīng)過(guò)不斷的迭代疊加，從而使得整體定位精度不夠高。

②從圖4和圖6可以看出質(zhì)心坐標(biāo)有趨向中心分布，圖4的通信半徑為30單位，而圖6為50單位，表明通信半徑越大，質(zhì)心坐標(biāo)越向中心分布，此時(shí)誤差值也越大（誤差可對(duì)比圖5和圖7）；對(duì)比圖2和圖4，可以觀察相同的通信半徑下，節(jié)點(diǎn)數(shù)目越大，對(duì)應(yīng)的誤差值要越小?；氐絺鞲衅骶W(wǎng)絡(luò)實(shí)際狀況，給定信標(biāo)節(jié)點(diǎn)的位置是均勻分布，且密度較高，當(dāng)通信半徑在擴(kuò)大時(shí)，表明某個(gè)未知節(jié)點(diǎn)周圍與其通信的信標(biāo)節(jié)點(diǎn)在增加，均勻分布的信標(biāo)節(jié)點(diǎn)的質(zhì)心位置一定會(huì)趨向于整個(gè)坐標(biāo)中心位置，實(shí)際上，對(duì)應(yīng)的未知節(jié)點(diǎn)卻可能分布在邊緣，這樣使得誤差值要明顯偏大，如圖6分布。

③從圖8可以觀察到信標(biāo)節(jié)點(diǎn)與誤差值的關(guān)系，表明在未知節(jié)點(diǎn)數(shù)目一定，通信半徑一定的情況下，信標(biāo)節(jié)點(diǎn)越多，所產(chǎn)生的誤差值越小。文獻(xiàn)[3]就是論證了通過(guò)在信標(biāo)節(jié)點(diǎn)密度低的區(qū)域增加新標(biāo)節(jié)點(diǎn)，以提高定位的精度。

5 結(jié)束語(yǔ)

仿真結(jié)果表明，采用極大似然估計(jì)法情況下，在信標(biāo)節(jié)點(diǎn)均勻分布而未知節(jié)點(diǎn)隨機(jī)分布的傳感器網(wǎng)絡(luò)中，節(jié)點(diǎn)的通信半徑越大，誤差越大，定位精度越低；信標(biāo)節(jié)點(diǎn)的數(shù)目越多，誤差越小，定位精度越高；當(dāng)信標(biāo)節(jié)點(diǎn)數(shù)目一定時(shí)，未知節(jié)點(diǎn)越多，誤差越大，定位精度越低。

[1]孫利民,李建中,陳 渝,等.無(wú)線傳感器網(wǎng)絡(luò)[M].北京:清華大學(xué)出版社,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]田金鵬.無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位技術(shù)研究[D].上海:上海大學(xué),2009.

[6]江 冰,吳元忠,謝冬梅.無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)自定位算法的研究[J].傳感技術(shù)學(xué)報(bào),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.