張 華，劉玉良，單海校

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

傳感器節(jié)點(diǎn)自定位就是根據(jù)少數(shù)已知位置的節(jié)點(diǎn)，按照某種定位機(jī)制確定自身的位置。在無線傳感器網(wǎng)絡(luò)各種應(yīng)用中，應(yīng)當(dāng)知曉監(jiān)測目標(biāo)的具體位置，沒有確切監(jiān)測消息的位置沒有任何意義[1]。根據(jù)節(jié)點(diǎn)是否知道自身的位置信息，把傳感器節(jié)點(diǎn)分為信標(biāo)節(jié)點(diǎn)和未知節(jié)點(diǎn)；按照定位過程中是否需要測量節(jié)點(diǎn)之間的實(shí)際距離，把定位算法分為基于距離的定位算法和距離無關(guān)的定位算法。無須測距的定位機(jī)制僅僅依靠網(wǎng)絡(luò)的連通性等參數(shù)進(jìn)行定位，主要定位機(jī)制包括質(zhì)心算法、DV-Hop算法、Amorphous算法、APIT算法等。距離無關(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)的密度和分布。許多人針對質(zhì)心算法提出了改進(jìn)思路，文獻(xiàn)[2]提出一種密度自適應(yīng)的HEAP算法，通過在信標(biāo)節(jié)點(diǎn)密度低的區(qū)域增加新標(biāo)節(jié)點(diǎn)，以提高定位的精度；文獻(xiàn)[3]中提對距離無關(guān)的幾種定位機(jī)制進(jìn)行了比較，信標(biāo)節(jié)點(diǎn)密度的大小影響了定位精度的高低，還有一些文獻(xiàn)通過對信標(biāo)節(jié)點(diǎn)與未知節(jié)點(diǎn)的距離的研究，如采用時間差或以距離作為權(quán)值參數(shù)來討論定位的精度問題?？紤]在不增加信標(biāo)節(jié)點(diǎn)密度的情況下以節(jié)點(diǎn)間的距離作為約束，探討通信半徑和節(jié)點(diǎn)數(shù)對節(jié)點(diǎn)定位精度的影響，采用極大似然估計法對函數(shù)進(jìn)行優(yōu)化，改進(jìn)節(jié)點(diǎn)自定位的精度。

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

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

質(zhì)心算法僅基于網(wǎng)絡(luò)節(jié)點(diǎn)連通性，思想是：信標(biāo)節(jié)點(diǎn)每隔一段時間，向鄰居節(jié)點(diǎn)廣播一個信標(biāo)信號，信號中包含自身ID和位置信息。當(dāng)未知節(jié)點(diǎn)接收到來自不同信標(biāo)節(jié)點(diǎn)的信標(biāo)信號數(shù)量超過某一個預(yù)設(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個信標(biāo)節(jié)點(diǎn)建立聯(lián)系，各信標(biāo)節(jié)點(diǎn)的坐標(biāo)分別為（x1，y1），（x2，y2），（x3，y4）…（xn，yn），按以上假設(shè)可以在二維空間中對問題進(jìn)行探討，按照質(zhì)心算法的思路，未知節(jié)點(diǎn)對自身的估算坐標(biāo)P（xcen，ycen）為，

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

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

質(zhì)心算法完全基于網(wǎng)絡(luò)的連通性，受分布密度、分布模型、信號傳輸模型等影響，使得定位誤差較大[2,5]，從數(shù)學(xué)角度來說，質(zhì)心坐標(biāo)僅僅依賴于信標(biāo)節(jié)點(diǎn)的坐標(biāo)，沒有受到其他條件的約束，本文考慮保留質(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ìn)而通過線性方程求出未知節(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)在相互之間通信過程中，受噪聲干擾影響，節(jié)點(diǎn)分布密度，節(jié)點(diǎn)間距離測量誤差以及節(jié)點(diǎn)自身計算能力不足引起的計算誤差等[5,6]，將使得公式2不會全部成立，假設(shè)各信標(biāo)節(jié)點(diǎn)與未知節(jié)點(diǎn)p之間的測距誤差分別為δ1，δ2，…，δn

3 算法步驟設(shè)計

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

算法設(shè)計如下：

①在100×100單位中，按均勻分布方式布置100個節(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)；

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

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

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

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

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

在不同的通信半徑，不同的未知節(jié)點(diǎn)數(shù)目的優(yōu)化分布圖形如下，其中通信半徑分別取50單位和30單位，信標(biāo)節(jié)點(diǎn)取均勻分布100個，未知節(jié)點(diǎn)分別取50個，20個。圖中藍(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ī)在matlab7.0.1環(huán)境下進(jìn)行仿真。

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

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

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

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

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

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

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

圖8 信標(biāo)節(jié)點(diǎn)個數(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)與其所對應(yīng)的質(zhì)心點(diǎn)；圖3、圖5、圖7表示各未知節(jié)點(diǎn)的測量誤差值分布。圖8表示信標(biāo)節(jié)點(diǎn)與誤差值的變化關(guān)系。

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

②從圖4和圖6可以看出質(zhì)心坐標(biāo)有趨向中心分布，圖4的通信半徑為30單位，而圖6為50單位，表明通信半徑越大，質(zhì)心坐標(biāo)越向中心分布，此時誤差值也越大（誤差可對比圖5和圖7）；對比圖2和圖4，可以觀察相同的通信半徑下，節(jié)點(diǎn)數(shù)目越大，對應(yīng)的誤差值要越小。回到傳感器網(wǎng)絡(luò)實(shí)際狀況，給定信標(biāo)節(jié)點(diǎn)的位置是均勻分布，且密度較高，當(dāng)通信半徑在擴(kuò)大時，表明某個未知節(jié)點(diǎn)周圍與其通信的信標(biāo)節(jié)點(diǎn)在增加，均勻分布的信標(biāo)節(jié)點(diǎn)的質(zhì)心位置一定會趨向于整個坐標(biāo)中心位置，實(shí)際上，對應(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]就是論證了通過在信標(biāo)節(jié)點(diǎn)密度低的區(qū)域增加新標(biāo)節(jié)點(diǎn)，以提高定位的精度。

5 結(jié)束語

仿真結(jié)果表明，采用極大似然估計法情況下，在信標(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ù)目一定時，未知節(jié)點(diǎn)越多，誤差越大，定位精度越低。

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

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