胡 偉，徐福緣

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

0 引 言

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

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

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

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

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

式中：i∈ ［1，］。給定一個未知節(jié)點，利用上述方法可以分別求出每個信標(biāo)節(jié)點組的貢獻因子，記為Contr1、Contr2、…、Contri。比較個貢獻因子的大小，將最大的貢獻因子求出來，記為Contrmax，根據(jù)Contrmax可推出最優(yōu)的信標(biāo)節(jié)點組為 ｛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é)點分布均勻時，節(jié)點間的直線距離可以近似的用平均每跳距離乘以跳數(shù)來取代［14］。當(dāng)網(wǎng)絡(luò)為稀疏網(wǎng)絡(luò)且不均勻時，那么在計算平均每跳距離時就會存在誤差，待定位節(jié)點與信標(biāo)節(jié)點之間的距離也會存在誤差。在DV－h(huán)op算法中定位過程中的信息以波的形式從中心向網(wǎng)絡(luò)四周擴散，誤差隨著擴散過程將不斷累積和放大。

2.1 平均跳距

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

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

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

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

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

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

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

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

2.2 位置估計

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

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

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

用α、β對 （x，y）進行修正

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

2.3 ConDV－Hop算法描述

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

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

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

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

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

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

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

3 仿真實驗及性能分析

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

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

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

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

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

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

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

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

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

從圖3和圖4可以看出，無論是在均勻網(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é)點總數(shù)變化的情況下，在均勻網(wǎng)絡(luò)和非均勻網(wǎng)絡(luò)中節(jié)點的平均定位誤差變化圖。在實驗中，節(jié)點總數(shù)分別為200、250、300、350、400、450，節(jié)點通信半徑為15m，信標(biāo)節(jié)點的比例使終保持10%。橫坐標(biāo)表示節(jié)點的總個數(shù)，縱坐標(biāo)表示平均定位誤差。

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

4 結(jié)束語

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

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

［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ǎng)絡(luò)中的自身定位系統(tǒng)和算法 ［J］.軟件學(xué)報，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ǎ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.