基于信標(biāo)優(yōu)化的無(wú)線(xiàn)傳感網(wǎng)絡(luò)定位算法研究

胡 偉，徐福緣

（1.上海理工大學(xué) 管理學(xué)院，上海200093；2.綿陽(yáng)師范學(xué)院 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，四川 綿陽(yáng)621000）

0 引 言

現(xiàn)代無(wú)線(xiàn)技術(shù)、電子通信技術(shù)的快速發(fā)展促進(jìn)了無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的產(chǎn)生［1］。無(wú)線(xiàn)傳感網(wǎng)是由部署在監(jiān)測(cè)區(qū)域內(nèi)大量的廉價(jià)微型并裝備有低能耗收發(fā)器和有限數(shù)據(jù)處理能力的傳感器節(jié)點(diǎn)通過(guò)無(wú)線(xiàn)通信方式形成的一個(gè)多跳自組織網(wǎng)絡(luò)［2－3］，其中定位技術(shù)是實(shí)現(xiàn)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)各種應(yīng)用的前提和基礎(chǔ)［4］。如果無(wú)線(xiàn)傳感器網(wǎng)絡(luò)節(jié)點(diǎn)所感知到的外部信息缺乏位置數(shù)據(jù)，則此信息是無(wú)意義的信息，因此對(duì)無(wú)線(xiàn)傳感器網(wǎng)絡(luò) 中的節(jié)點(diǎn)定位技術(shù)進(jìn)行研究具有重要的意義。

目前研究者已經(jīng)提出了許多節(jié)點(diǎn)定位算法，一般可分為基于測(cè)距和免測(cè)距兩種類(lèi)型。基于測(cè)距的定位技術(shù)一般定位精度較高，但是對(duì)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的硬件要求也比較高。對(duì)于免測(cè)距的定位算法其代表性的研究成果包括Cricket定位系統(tǒng)［5］、SPA［6］、凸規(guī)劃定位算法［7］、APIT算法［8］、Bounding Box算法［9］、DV－h(huán)op算法［10］、Amorphoous算法［11］、Euclidean 算 法［12］和 Robust Position 算法［13］等。免測(cè)距的定位方案由于其實(shí)現(xiàn)簡(jiǎn)單、對(duì)硬件要求低，所以受到業(yè)界的重視。但是基于免測(cè)距的定位算法在定位精度和節(jié)點(diǎn)能耗方面都不是很理想，要么定位精度提高得不夠明顯，要么需要用較大的通信開(kāi)銷(xiāo)或計(jì)算量才能獲得較高的定位精度，網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)對(duì)算法的性能影響非常大?；谝陨显?，本文提出了一種基于信標(biāo)優(yōu)化的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)定位算法ConDV－Hop，該算法采用貢獻(xiàn)因子Contri對(duì)信標(biāo)節(jié)點(diǎn)進(jìn)行優(yōu)化選擇，用最優(yōu)的3個(gè)信標(biāo)節(jié)點(diǎn)組對(duì)待定位節(jié)點(diǎn)的位置進(jìn)行初步估算；然后利用反饋思想引入修正系數(shù)α和β，用貢獻(xiàn)因子次之的信標(biāo)節(jié)點(diǎn)組去估算貢獻(xiàn)因子最大的信標(biāo)節(jié)點(diǎn)組的坐標(biāo)，進(jìn)而用計(jì)算出的位置修正系數(shù)α、β分別對(duì)待定位節(jié)點(diǎn)估算位置中的x和y進(jìn)行修正，使網(wǎng)絡(luò)中的累積誤差減小。仿真實(shí)驗(yàn)結(jié)果表明，本文所提出的算法在定位精度、能耗和適應(yīng)性方面都有明顯的優(yōu)勢(shì)。

1 信標(biāo)優(yōu)化選擇

傳統(tǒng)的DV－Hop算法在節(jié)點(diǎn)分布的密集網(wǎng)絡(luò)中性能表現(xiàn)良好，但是在非均勻網(wǎng)絡(luò)中其定位效果和精度會(huì)急劇下降，網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)對(duì)DV－Hop算法的性能起著至關(guān)重要的作用。為了克服網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)對(duì)DV－Hop算法的影響，在未知節(jié)點(diǎn)進(jìn)行定位時(shí)，我們采取優(yōu)化選擇信標(biāo)節(jié)點(diǎn)的策略，用貢獻(xiàn)因子對(duì)鄰近的信標(biāo)節(jié)點(diǎn)組 （3個(gè)信標(biāo)節(jié)點(diǎn)為一組）進(jìn)行評(píng)價(jià)，將最優(yōu)的信標(biāo)節(jié)點(diǎn)組挑選出來(lái)。具體實(shí)現(xiàn)方法如下：

設(shè)A、B、C分別表示某一未知節(jié)點(diǎn)通信半徑內(nèi)的任意3個(gè)信標(biāo)節(jié)點(diǎn)組成的三角形的內(nèi)角，Nb為未知節(jié)點(diǎn)附近鄰居信標(biāo)節(jié)點(diǎn)的個(gè)數(shù)，組合數(shù)為未知節(jié)點(diǎn)可以選擇的信標(biāo)節(jié)點(diǎn)組的數(shù)目，NCi＝Max｛cosiA，cosiB，cosiC｝，其中i∈ ［1，］，NCi的取值范圍為0.5到1之間。那么貢獻(xiàn)因子Contri可表示為

式中：i∈ ［1，］。給定一個(gè)未知節(jié)點(diǎn)，利用上述方法可以分別求出每個(gè)信標(biāo)節(jié)點(diǎn)組的貢獻(xiàn)因子，記為Contr1、Contr2、…、Contri。比較個(gè)貢獻(xiàn)因子的大小，將最大的貢獻(xiàn)因子求出來(lái)，記為Contrmax，根據(jù)Contrmax可推出最優(yōu)的信標(biāo)節(jié)點(diǎn)組為 ｛NA、NB、NC｝，它們的坐標(biāo)分別為（XA，YA）、（XB，YB）和 （XC，YC）。

2 基于信標(biāo)優(yōu)化選擇的定位算法

傳統(tǒng)DV－Hop算法比較適合于均勻網(wǎng)絡(luò)，當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)分布均勻時(shí)，節(jié)點(diǎn)間的直線(xiàn)距離可以近似的用平均每跳距離乘以跳數(shù)來(lái)取代［14］。當(dāng)網(wǎng)絡(luò)為稀疏網(wǎng)絡(luò)且不均勻時(shí)，那么在計(jì)算平均每跳距離時(shí)就會(huì)存在誤差，待定位節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)之間的距離也會(huì)存在誤差。在DV－h(huán)op算法中定位過(guò)程中的信息以波的形式從中心向網(wǎng)絡(luò)四周擴(kuò)散，誤差隨著擴(kuò)散過(guò)程將不斷累積和放大。

2.1 平均跳距

傳統(tǒng)DV－Hop算法主要分為以下3個(gè)步驟［15］：

（1）信標(biāo)節(jié)點(diǎn)在全網(wǎng)中洪泛分組信息，網(wǎng)絡(luò)中的節(jié)點(diǎn)可以獲得相應(yīng)路數(shù)信息和信標(biāo)節(jié)點(diǎn)的位置信息。

（2）信標(biāo)節(jié)點(diǎn)之間利用如下公式計(jì)算平均每跳距離［16］

式中： （xi，yi）、 （xj，yj）——信標(biāo)節(jié)點(diǎn)i和j的坐標(biāo)，hij——信標(biāo)節(jié)點(diǎn)i和j之間的跳數(shù)。然后將Hopsizei作為一個(gè)校正值廣播至網(wǎng)絡(luò)中。

（3）當(dāng)待定位節(jié)點(diǎn)獲得足夠的信息后，利用三邊或多邊測(cè)量定位法進(jìn)行定位。

為了克服DV－Hop算法的缺陷，我們引入貢獻(xiàn)因子，優(yōu)化待定位節(jié)點(diǎn)用于定位的信標(biāo)節(jié)點(diǎn)。設(shè)待定位節(jié)點(diǎn)的坐標(biāo)為 （x，y），通過(guò)本文上面的方法將其鄰近的3個(gè)信標(biāo)節(jié)點(diǎn)組求出來(lái)，求出的最優(yōu)信標(biāo)節(jié)點(diǎn)組為NA、NB和NC，它們的坐標(biāo)分別為 （XA，YA）、（XB，YB）和 （XC，YC），則

此時(shí)NA、NB和NC之間的跳數(shù)分別為hAB、hBC和hAC，所以平均跳距為

引入貢獻(xiàn)因子Contri，更新后的平均跳距可表示為

2.2 位置估計(jì)

待定位節(jié)點(diǎn)到NA、NB和NC的修正距離，可用dA、dB和dC表示，那么

根據(jù)上面的已知數(shù)據(jù)，可以得到如下的方程

上述二元二次方程可以用標(biāo)準(zhǔn)的最小二乘法求解，可計(jì)算出待定位節(jié)點(diǎn)的估算位置 （x，y）。下面利用反饋思想對(duì)待定位節(jié)點(diǎn)的估算位置進(jìn)行修正。用貢獻(xiàn)因子次之的信標(biāo)節(jié)點(diǎn)組去估算貢獻(xiàn)因子最大的信標(biāo)節(jié)點(diǎn)組的坐標(biāo)，得出的貢獻(xiàn)因子最大信標(biāo)節(jié)點(diǎn)組的估算坐標(biāo)分別為 （x′A，y′A）、 （x′B，y′B）和 （x′C，y′C），設(shè)α、β為估算位置的修正系數(shù)，則

用α、β對(duì) （x，y）進(jìn)行修正

此時(shí)，（x′，y′）即為修正后的待定位節(jié)點(diǎn)的坐標(biāo)。

2.3 ConDV－Hop算法描述

基于信標(biāo)優(yōu)化選擇的無(wú)線(xiàn)傳感網(wǎng)絡(luò)定位算法ConDVHop描述如下：

步驟1 初始化。將待定位節(jié)點(diǎn)和信標(biāo)節(jié)點(diǎn)隨機(jī)布署在傳感區(qū)域中，設(shè)置好信標(biāo)節(jié)點(diǎn)的比例及節(jié)點(diǎn)的通信半徑。

步驟2 跳數(shù)的計(jì)算。信標(biāo)節(jié)點(diǎn)將自身的位置信息進(jìn)行全網(wǎng)洪泛，使網(wǎng)絡(luò)中的所有節(jié)點(diǎn)獲得相應(yīng)的跳數(shù)信息。

步驟3 信標(biāo)優(yōu)化選擇。采取優(yōu)化選擇信標(biāo)節(jié)點(diǎn)的策略，用貢獻(xiàn)因子Contri對(duì)待定位節(jié)點(diǎn)鄰近的信標(biāo)節(jié)點(diǎn)組進(jìn)行評(píng)價(jià)，將Contri按大小進(jìn)行排列，并且將最大的和次大的信標(biāo)節(jié)點(diǎn)組保存起來(lái)。

步驟4 平均跳距的計(jì)算。利用步驟3中求出的信標(biāo)節(jié)點(diǎn)估算平均跳距Hopsize，并用貢獻(xiàn)因子對(duì)Hopsize進(jìn)行更新，更新后的平均跳距為Hopsize′。

步驟5 估算位置。待定位節(jié)點(diǎn)根據(jù)更新后的跳距Hopsize′和hA、hB及hC的大小，分別計(jì)算出到3個(gè)最優(yōu)信標(biāo)節(jié)點(diǎn)的距離dA、dB和dC。然后利用最小二乘法求解出待定位節(jié)點(diǎn)的估算位置 （x，y）。

步驟6 位置修正。用位置修正系數(shù)α、β分別對(duì)待定位節(jié)點(diǎn)估算位置中的x和y進(jìn)行修正，得出的新坐標(biāo)為（x′，y′）。

3 仿真實(shí)驗(yàn)及性能分析

為了檢驗(yàn)ConDV－Hop算法的性能，本文在MATLAB平臺(tái)上進(jìn)行了仿真，并分析了算法的性能，和傳統(tǒng)的DVHop算法進(jìn)行了對(duì)比。仿真環(huán)境配置及一些概念如下：

（1）仿真區(qū)域：所有傳感器節(jié)點(diǎn)隨機(jī)分布在100×100m的正方形區(qū)域內(nèi)。

（2）通信半徑R：在無(wú)線(xiàn)傳感器網(wǎng)絡(luò)里，節(jié)點(diǎn)通信半徑最開(kāi)始設(shè)為15m。

（3）單個(gè)節(jié)點(diǎn)定位誤差ES：設(shè)rest為未知節(jié)點(diǎn)的估計(jì)位置，rreal為未知節(jié)點(diǎn)的真實(shí)位置，則

（4）總平均定位誤差Et：設(shè)m為網(wǎng)絡(luò)中信標(biāo)節(jié)點(diǎn)的數(shù)目，n為網(wǎng)絡(luò)中所有節(jié)點(diǎn)的數(shù)目；為第i個(gè)未知節(jié)點(diǎn)的估計(jì)位置，為為第i個(gè)未知節(jié)點(diǎn)的實(shí)際位置，則

我們比較了在均勻網(wǎng)絡(luò)和非均勻網(wǎng)絡(luò)中，ConDV－Hop算法與DV－Hop算法在信標(biāo)節(jié)點(diǎn)比例、總節(jié)點(diǎn)數(shù)目和通信半徑大小變化的情況下網(wǎng)絡(luò)的平均定位誤差變化情況。

圖1和圖2表示在信標(biāo)節(jié)點(diǎn)比例變化的情況下，在均勻網(wǎng)絡(luò)和非均勻網(wǎng)絡(luò)中節(jié)點(diǎn)的平均定位誤差變化圖。在實(shí)驗(yàn)中，節(jié)點(diǎn)總個(gè)數(shù)為200，信標(biāo)節(jié)點(diǎn)的比例分別是10%、15%、20%、25%、30%、35%，其中橫坐標(biāo)表示信標(biāo)節(jié)點(diǎn)所占的比例，縱坐標(biāo)表示節(jié)點(diǎn)的平均定位誤差。

從圖1和圖2可以看出，兩種算法在均勻網(wǎng)絡(luò)的定位誤差要低于在非均勻網(wǎng)絡(luò)中的定位誤差，其中傳統(tǒng)DVHop算法的變化最為明顯，網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)對(duì)DV－Hop算法的性能影響非常大，而對(duì)ConDV－Hop算法的影響要小于對(duì)DV－Hop算法的影響，說(shuō)明本文提出的ConDV－Hop算法其適應(yīng)性更強(qiáng)。在均勻網(wǎng)絡(luò)和非均勻網(wǎng)絡(luò)中，ConDV－Hop算法平均定位誤差分別為19.4%和32.4%，而傳統(tǒng)的DV－Hop算法平均定位誤差分別約為26.5%和41.8%。

圖3和圖4表示在節(jié)點(diǎn)通信半徑變化的情況下，在均勻網(wǎng)絡(luò)和非均勻網(wǎng)絡(luò)中節(jié)點(diǎn)的平均定位誤差變化圖。在實(shí)驗(yàn)中，節(jié)點(diǎn)總個(gè)數(shù)為200，信標(biāo)節(jié)點(diǎn)的比例為10%，節(jié)點(diǎn)的通信半徑從最初的15m逐漸增大，分別為15m、20m、25m、30m、35m和40m。

從圖3和圖4可以看出，無(wú)論是在均勻網(wǎng)絡(luò)還是在非均勻網(wǎng)絡(luò)中，ConDV－Hop算法比傳統(tǒng)的DV－Hop算法定位精度都有明顯的提高。在均勻網(wǎng)絡(luò)中，ConDV－Hop算法比傳統(tǒng)的DV－Hop算法平均定位誤差降低6.1%；在非均勻網(wǎng)絡(luò)中，ConDV－Hop算法比傳統(tǒng)的DV－Hop算法平均定位誤差降低約10.9%。

圖5和圖6表示在節(jié)點(diǎn)總數(shù)變化的情況下，在均勻網(wǎng)絡(luò)和非均勻網(wǎng)絡(luò)中節(jié)點(diǎn)的平均定位誤差變化圖。在實(shí)驗(yàn)中，節(jié)點(diǎn)總數(shù)分別為200、250、300、350、400、450，節(jié)點(diǎn)通信半徑為15m，信標(biāo)節(jié)點(diǎn)的比例使終保持10%。橫坐標(biāo)表示節(jié)點(diǎn)的總個(gè)數(shù)，縱坐標(biāo)表示平均定位誤差。

從圖5和圖6可以看出，在均勻網(wǎng)絡(luò)和非均勻網(wǎng)絡(luò)中，隨著總節(jié)點(diǎn)數(shù)的增加，兩種算法的平均定位誤差都在減少，ConDV－Hop算法的平均定位誤差比傳統(tǒng)的DV－Hop算法分別降低約7.2%和10.5%，其性能要優(yōu)于傳統(tǒng)的DV－Hop算法。

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

本文在繼承傳統(tǒng)DV－Hop定位算法優(yōu)點(diǎn)的基礎(chǔ)上，提出了一種新的算法ConDV－Hop。該算法采取優(yōu)化選擇信標(biāo)節(jié)點(diǎn)的策略，克服了網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)對(duì)DV－Hop算法的影響；利用反饋思想引入修正系數(shù)，對(duì)待定位節(jié)點(diǎn)的估算位置進(jìn)行修正，提高了節(jié)點(diǎn)的定位精度。仿真實(shí)驗(yàn)結(jié)果表明，相比于傳統(tǒng)的經(jīng)典算法DV－Hop，本文所提出的算法在定位精度、能耗及適應(yīng)性方面都有明顯的優(yōu)勢(shì)。

由于無(wú)線(xiàn)傳感器網(wǎng)絡(luò)節(jié)點(diǎn)存在資源有限、隨機(jī)部署、對(duì)環(huán)境依賴(lài)性過(guò)高等特性，因此如何使定位方案在滿(mǎn)足自組織性、健壯性、能量高效和分布式計(jì)算等要求的前提下，具有低費(fèi)用、低能耗和高適應(yīng)性等性能成為下一步將要研究的重點(diǎn)。

［1］WANG Fubao，SHI Long.Self－localization systems and algorithms for wireless sensor networks ［J］.Journal of Software，2005，16 （5）：857－868 （in Chinese）. ［王福豹，史龍.無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中的自身定位系統(tǒng)和算法 ［J］.軟件學(xué)報(bào)，2005，16 （5）：857－868.］

［2］SUN L M，LI J Z.Wireless sensor network ［M］.Beijing：Tsinghua University Publisher，2005：1－3.

［3］SONG W，WANG B，ZHOU Y B.Technology and application of wireless sensor network ［M］.Beijing：Electronics Industrial Publisher，2007：2－6.

［4］SUN Limin，LI Jianzhong，CHEN Yu，et al.Wireless sensor network ［M］.Beijing：Tsinghua University Press，2005：141－146（in Chinese）.［孫利民，李建中，陳渝，等.無(wú)線(xiàn)傳感器網(wǎng)絡(luò) ［M］.北京：清華大學(xué)出版社，2005：141－146.］

［5］YU K G.3Dlocalization error analysis in wireless networks［J］.IEEE Transaction on Wireless Communication，2007，6（10）：3473－3481.

［6］LI Z，Trappe W，ZHANG Y，et al.Robust statistical methods for securing wireless localization in sensor networks［C］.Los Angeles，CA，USA：Proc of International on Confabulation Process Sensor Networks，2005：91－98.

［7］Pradip De，LIU Yonghe，Sajal K Das.Modeling node compromise spread in wireless sensor networks using epidemic theory［C］.Proceedings of the International Symposium on a World of Wireless，Mobile and Multimedia Networks，2006：237－243.

［8］SHAN Z L，YUM TA，KSHIN G P.Precise localization with smart antennas in Ad Hoc networks［C］.Proceedings of IEEE GLOBECOM.Iscataway，NJ，USA：IEEE，2007：1053－1057.

［9］Kout sonilas D，Das S M，HU Y Charlie.Path planning of mobile landmarks for localization in wireless sensor networks ［J］.Computer Communication，2007，30 （13）：2577－2592.

［10］Peter Corke，Ron Peterson，Daniel a Rus.Localization and navigation assisted by cooperating networked sensors and robots［J］.International Journal of Robotics Research，2005，24 （9）：771－786.

［11］Aline Baggio，Koen Langendoen.Monte Carlo localization for mobile wireless sensor networks ［G］.LNCS 4325：2nd Int Conference on Mobile Ad－h(huán)oc and Sensor Networks，2006：317－328.

［12］Dil B，Dulman S，Havinga P J M.Range based localization in mobile sensor networks［G］.LNCS 3868：Proc of 3rd European Workshop on Wireless Sensor Networks，2006：164－179.

［13］Line Baggio A，Koen Langendoen.Monte Carlo localization for mobile wireless sensor networks ［J］.Ad Hoc Networks，2008，6 （5）：718－733.

［14］WANG W D，ZHU Q X.RSS based Monte Carlo localization for mobile sensor networks［J］.IET Communications，2008，2 （5）：673－681.

［15］Kuo Feng Ssu，Chia Ho Ou，Hewijin Christine Jiau.Localization with mobile anchor points in w ireless sensor networks［J］.IEEE Transactions on Vehicular Technology，2005，54（3）：1187－1197.

［16］PAN J J F，YANG Q，CHANG H，et al.A manifold regularization approach to calibration reduction for sensor－network based tracking ［C］.Proc of the American Association for Artificial Intelligence.Boston：AAAI Press，2006：988－993.