無線傳感器網(wǎng)絡(luò)中Dv-Hop定位算法的改進(jìn)

金 純，葉 誠，韓志斌，韓 剛，周曉軍

(1.重慶郵電大學(xué)通信與信息工程學(xué)院，重慶400065;2.重慶金甌科技發(fā)展有限責(zé)任公司，重慶400041;3.重慶廣通實業(yè)發(fā)展有限責(zé)任公司，重慶400039;4.重慶市旭鼎科技有限公司，重慶400065)

0 引言

無線傳感器網(wǎng)絡(luò)是由大量無線傳感器節(jié)點以Ad-Hoc的組網(wǎng)方式構(gòu)成的無線網(wǎng)絡(luò)，其目的是感知、采集和處理其覆蓋區(qū)域中感知對象的信息［1-2］。無線傳感器網(wǎng)絡(luò)具有較高的應(yīng)用前景，現(xiàn)已廣泛應(yīng)用于軍事、環(huán)境、醫(yī)療等領(lǐng)域［3-4］。定位技術(shù)是無線傳感器網(wǎng)絡(luò)中多種應(yīng)用的基礎(chǔ)，隨著無線傳感器網(wǎng)絡(luò)的蓬勃發(fā)展，與其息息相關(guān)的定位技術(shù)受到了人們較大的關(guān)注。

在無線傳感器網(wǎng)絡(luò)中，最簡單的定位方法是采用GPS定位系統(tǒng)，在傳感器節(jié)點內(nèi)安裝GPS接收機，通過GPS接收機與衛(wèi)星的通信，實現(xiàn)GPS接收機的定位功能。但是在實際應(yīng)用中，無線傳感器網(wǎng)絡(luò)要求節(jié)點價格低廉，功耗和體積小，在這種限制下，通常只會將GPS接收機安裝于少數(shù)傳感器節(jié)點，這些傳感器節(jié)點稱為錨節(jié)點。無線傳感器網(wǎng)絡(luò)中的定位算法就是未知節(jié)點借助這些錨節(jié)點的坐標(biāo)信息來實現(xiàn)節(jié)點自身的定位［2］。無線傳感器網(wǎng)絡(luò)中的定位算法分類標(biāo)準(zhǔn)有很多，使用較多的是依據(jù)是否需要測量節(jié)點間距離或角度等信息來分類，依照這種劃分，可以把定位算法分為基于距離的定位［5］和與距離無關(guān)的定位［6］?；诰嚯x的定位機制一般定位精度相對較高，對節(jié)點的硬件通常也提出了較高要求，基于距離定位機制常用測距方法有RSSI(received signal strength indicator)、TOA(time of arrival)、TDOA(time difference on arrival)、AOA(angle of arrival)。與距離無關(guān)的定位機制無需實際測量節(jié)點間的絕對距離或方位，對節(jié)點硬件的要求低，使得節(jié)點成本更適合于大規(guī)模網(wǎng)絡(luò)。與距離無關(guān)的定位算法主要有質(zhì)心算法、Dv-Hop算法、APIT算法、MDS-MAP算法等，現(xiàn)有技術(shù)中通常使用的是Dv-Hop(distance vector-hop)算法。近幾年，國內(nèi)外學(xué)者主要圍繞上述經(jīng)典算法，提出了許多的改進(jìn)算法，進(jìn)一步提高定位性能，使傳感器網(wǎng)絡(luò)能更好的應(yīng)用于實際。本文主要是針對Dv-Hop算法的不足提出改進(jìn)，并借助仿真工具加以驗證，得出了較優(yōu)的性能。

1 Dv-Hop算法

Niculescu等人提出的Dv-Hop算法主要是利用典型的距離路由協(xié)議，得到所有節(jié)點之間的最小跳數(shù)，然后根據(jù)錨節(jié)點間的最小跳數(shù)估算平均每跳距離，再利用未知節(jié)點和錨節(jié)點的最小跳數(shù)與估算的平均每跳距離乘積代替未知節(jié)點與錨節(jié)點間的距離，最后利用三邊測量法或最小二乘法求未知節(jié)點的坐標(biāo)，完成定位。

1.1 Dv-Hop算法的定位過程

Dv-Hop定位算法主要可以分為以下3個階段:

(1)計算未知節(jié)點與錨節(jié)點的最小跳數(shù)。

借助典型的距離矢量交換協(xié)議，錨節(jié)點向鄰居節(jié)點廣播自身位置的信息分組，其中包括跳數(shù)字段，初始化為0，接收節(jié)點記錄到每個錨節(jié)點的最小跳數(shù)，忽略來自同一錨節(jié)點的較大跳數(shù)的信息分組，將跳數(shù)加1再轉(zhuǎn)發(fā)給它的鄰居節(jié)點。通過這種方式使網(wǎng)絡(luò)中所有節(jié)點獲得它到其他節(jié)點的最小跳數(shù)。

(2)計算未知節(jié)點到錨節(jié)點間的距離。

錨節(jié)點根據(jù)第一階段獲得到其他錨節(jié)點間的最小跳數(shù)跟位置信息，利用式 (1)，可以獲得平均每跳距離

式 中:(xi，yi)，(xj，yj)——錨 節(jié) 點 i 和 j 的 坐 標(biāo)，HopSizei——錨節(jié)點i的平均每跳距離。然后錨節(jié)點將這個平均每跳距離利用帶有生存限制的分組廣播至網(wǎng)絡(luò)中，使得離它較近的未知節(jié)點獲得相應(yīng)的HopSizei，利用式 (2)就可以計算出未知節(jié)點到距離較近的幾個錨節(jié)點距離

式中:i——錨節(jié)點，j——未知節(jié)點，hopij—— i和 j的最小跳數(shù)。

(3)計算出未知節(jié)點的坐標(biāo)，完成定位。

通過第2階段得到的未知節(jié)點到錨節(jié)點的距離，再利用極大似然估計法求出未知節(jié)點坐標(biāo)。

假設(shè)未知節(jié)點的坐標(biāo)為(x，y)，錨節(jié)點i的坐標(biāo)為(xi，yi)(i=1，2，…，n)，未知節(jié)點與錨節(jié)點間的距離 di(i=1，2，…，n)由式 (3)計算出

對于式 (3)從第一個方程開始分別減去最后一個方程，可得

式 (4)的線性表達(dá)式為

X可以由式 (6)求出。

其中

1.2 Dv-Hop算法的誤差分析

無線傳感器網(wǎng)絡(luò)中，節(jié)點隨機分布，各節(jié)點之間的距離長短不一，節(jié)點密度分布也稀疏不同。而Dv-Hop算法中利用錨節(jié)點間計算得出的平均每跳距離，來代替網(wǎng)絡(luò)中未知節(jié)點到錨節(jié)點間的每跳距離，用其乘以跳數(shù)得出的值來作為未知節(jié)點到錨節(jié)點間的距離，顯然計算出的距離將會與真實距離存在較大的誤差，這種誤差是算法機制所帶來的，需要采取某些措施來減小定位誤差，提高定位精度。而未知節(jié)點與錨節(jié)點之間誤差的大小通常與估算的平均每跳值、未知節(jié)點到錨節(jié)點跳數(shù)多少等有關(guān)。一方面，跳數(shù)越多，未知節(jié)點與錨節(jié)點之間路徑偏離兩點直線連線的可能性越大，計算出的未知節(jié)點與錨節(jié)點距離與真實距離誤差越大。另一方面，用原本不精確的平均跳距乘以跳數(shù)得到的估算距離將隨跳數(shù)的增加，誤差也會累計增加。總的來說，在絕大多數(shù)情況下，未知節(jié)點與錨節(jié)點之間估算誤差的大小會隨著跳數(shù)的增加而增大。

2 Dv-Hop算法的改進(jìn)

2.1 RRSI測距技術(shù)

RSSI是接收到信號強度大小的指示器，是一種利用信號的衰減來推測距離的測距技術(shù)［7］

式 (7)是目前使用較多的一種理論模型，Pr(d)是距離發(fā)射處d米接受到的信號功率，Pr(d0)是距離發(fā)射處d0米接收到的信號功率，n是路徑衰減因子，Xσ是均值為0、標(biāo)準(zhǔn)差為σ的高斯分布，實際計算中，d0通常取1米，Pr(d0)也取1米處的信號強度。而在目前常用的TI公司芯片CC2430中，有以下關(guān)系成立

借助于以上公式，可以得出如下公式

其中A=Pr(1)+RSSI_OFFEST。系數(shù)A跟n可以通過采集數(shù)據(jù)，進(jìn)行擬合來得到，這樣就可以根據(jù)RSSI算出對應(yīng)的距離d。文獻(xiàn)［7］對基于RSSI的測距進(jìn)行了分析，其結(jié)論表明，在15米以內(nèi)，RSSI測距有較高的精度。在15米以內(nèi)用RSSI測距獲得的數(shù)據(jù)比原算法估算的數(shù)據(jù)更精確。

2.2 改進(jìn)后的Dv-Hop算法

目前，已有很多學(xué)者和研究人員提出對Dv-Hop算法的改進(jìn)策略［8-10］。文獻(xiàn)［8］中將錨節(jié)點分成圓形或者半圓形后再進(jìn)行定位。文獻(xiàn)［9］中采用未知節(jié)點附近多個錨節(jié)點的加權(quán)平均跳距代替原算法中的平均跳距減少了跳距帶來的定位誤差。文獻(xiàn)［10］針對錨節(jié)點與未知節(jié)點之間的估計距離做出了修正，該修正值由多跳的校正者和錨節(jié)點平均每跳距離誤差所組成，由此提高定位精度。大部分改進(jìn)都是針對Dv-Hop算法中第一二階段所進(jìn)行的，通過修正未知節(jié)點與錨節(jié)點之間的距離，提高定位精度。

在算法第三階段中，用最小二乘法式 (3)計算時，每個方程都將減去最后一個方程，可見最后一個方程中估算的距離dn與真實距離之間誤差的大小將對計算出的未知節(jié)點坐標(biāo)有很大的影響，如果最后的一組數(shù)據(jù)誤差很大，前面的(n－1)組數(shù)據(jù)再怎么精確，也會讓算出的結(jié)果跟真實位置之間存在很大的誤差。因此，本文的改進(jìn)思路是基于選取一組誤差最小的數(shù)據(jù)構(gòu)建第n個方程。

基于以上研究，本文做出如下改進(jìn):

(1)RSSI在15米以內(nèi)，有較高的精確度，當(dāng)未知節(jié)點與錨節(jié)點在15米以內(nèi)時候采用RSSI算得的距離比原算法估算的距離誤差更小。因此，錨節(jié)點發(fā)起廣播信息時，在一跳范圍內(nèi)的未知節(jié)點將根據(jù)RSSI計算它們之間的距離，如果計算出的值在15米以內(nèi)，將直接用這個值作為它們之間的估算距離。

(2)對未知節(jié)點于錨節(jié)點之間的估算距離n(i=1，2，…，n)進(jìn)行排序，選擇它們之間距離，最小的一組數(shù)據(jù)，來構(gòu)建式 (3)中第n個方程。

3 仿真與分析

為了驗證改進(jìn)后算法的性能，使用了matlab對Dv-Hop算法和改進(jìn)后的Dv-Hop算法性能進(jìn)行了仿真對比，并對結(jié)果進(jìn)行了分析。

假設(shè)某未知節(jié)點實際坐標(biāo)為 (xr，yr)，估計坐標(biāo)為(xe，ye)，通信半徑為R。

絕對定位誤差定義為

相對定位誤差定義為

3.1 同一場景下，兩算法性能對比

為了最直觀的比較兩種算法的性能，在同一網(wǎng)絡(luò)場景下用兩種算法定位，分別給出了每個點在每種算法下的絕對誤差。如圖1所示，是在100*100的網(wǎng)絡(luò)環(huán)境下進(jìn)行仿真實驗，節(jié)點總數(shù)200個，錨節(jié)點20，通信半徑R為15。

從圖1可看出改進(jìn)后的Dv-Hop算法絕大部分節(jié)點絕對定位誤差比原算法小，而且改進(jìn)后算法的方差也比原算法小。相對于原算法，改進(jìn)后的Dv-Hop算法能有效的提高定位性能。

圖1 兩種算法下誤差對比

3.2 不同通信半徑下，算法性能對比

為了更全面的分析、評價改進(jìn)后算法的性能。將節(jié)點通信半徑依次改變，比較算法在不同通信半徑下的性能。

圖2所示，也是在100*100的網(wǎng)絡(luò)環(huán)境下進(jìn)行仿真實驗，節(jié)點總數(shù)200個，錨節(jié)點20，但通信半徑R由15依次累加，每個數(shù)據(jù)都是程序獨立運行500次后取的平均值。為了更好分析引入RSSI的作用，特意也將改進(jìn)算法中引入RSSI的相關(guān)部分剔除作為一種新的算法對比，稱之為不完整改進(jìn)算法以示區(qū)別。

從圖2中可以看出，不完整改進(jìn)算法在通信半徑較小時候相對原算法能較大幅度的提高定位精度，但在R超過65后，不完整改進(jìn)算法已不能提高算法性能。這是因為R較小時候，算法的平均每跳距離也較小，待定位節(jié)點一跳范圍內(nèi)錨節(jié)點很少，甚至沒有，此時選擇離待定節(jié)點最近的錨節(jié)點，能保證未知節(jié)點與錨節(jié)點之間估算誤差較小。然而隨著R的增大，網(wǎng)絡(luò)平均每跳距離變大，待定節(jié)點一跳范圍內(nèi)錨節(jié)點越來越多，因為一跳內(nèi)的錨節(jié)點到待定節(jié)點的估計距離都由網(wǎng)絡(luò)平均每跳距離決定，此時只有距離跟網(wǎng)絡(luò)平均每跳距離數(shù)值越接近誤差才會越小，顯而易見再選擇離待定位節(jié)點較近的點已不能保證它們誤差最小，算法的性能亦不能得到提高。

圖2 不同通信半徑下算法性能比較

改進(jìn)后的Dv-Hop算法，在引入較高精確度的RSSI測距，一跳范圍15米以內(nèi)的點，其距離將不再依靠網(wǎng)絡(luò)平均每跳距離估算，直接RSSI測量，在用二乘法定位中采用此組數(shù)據(jù)構(gòu)建第n個方程，對半徑的改變并沒有那么敏感。在R較小時候，改進(jìn)算法雖然跟不完整改進(jìn)算法差距不大，但隨著R的增加，改進(jìn)算法性能提高較為明顯。

3.3 不同錨節(jié)點個數(shù)，算法性能對比

依舊在100*100的網(wǎng)絡(luò)環(huán)境下進(jìn)行仿真實驗，節(jié)點總數(shù)200個，通信半徑為20，改變網(wǎng)絡(luò)中錨節(jié)點的個數(shù)，仿真算法在不同數(shù)目錨節(jié)點下的性能。

圖3所示仿真結(jié)果，隨著錨節(jié)點數(shù)目的提高，原算法和改進(jìn)算法的性能都得到很大的提高。當(dāng)錨節(jié)點達(dá)到一定比例，再提高錨節(jié)點數(shù)目，算法性能提高較緩慢，但改進(jìn)后的Dv-Hop算法性能始終優(yōu)于原算法。

圖3 不同錨節(jié)點數(shù)目下算法性能比較

4 結(jié)束語

國內(nèi)外學(xué)者針對Dv-Hop算法的不足提出了許多改進(jìn)算法，基本上都是圍繞如何減小節(jié)點間的估算距離誤差做出改進(jìn)，但是卻很少有人關(guān)注到這種誤差對最后使用最小二乘法定位的影響。本文正是為了減小這種影響而提出的改進(jìn)算法，通過借助RSSI測距，排序等手段對算法做出改進(jìn)，減小節(jié)點估算距離誤差對最后定位的影響。仿真實驗證明，改進(jìn)后的算法在沒有增加計算量和額外硬件的情況下，相對于原算法，顯著提高了定位性能。

［1］KIM S，KO JG，YOON J，et al.Multiple-objective metric for placing multiple base station in wireless sensor network［C］//Proceeding of the 2rd International Symposium on Wireless Pervasive Computing.Korea，2007:627-631.

［2］Jennifer Yick，Biswannath Mukherjee，Dipak Ghosal.Wireless sensor network survey ［J］.Computer Networks，2008，52(12):2292-2230.

［3］Mizugaki K，F(xiàn)ujiwara R，Nakagawa T，et al.Accurate wireless location/communication system with 22-cm error using UWB-IR［C］//Radio and Wireless Symposium.Washington，DC:IEEE，2007:455-458.

［4］Guoqiang MaoBaris，F(xiàn)idan Localization.Algorithms and strategies for wireless sensor networks［M］.Information Science Reference，Release Date，2009.

［5］XIAO Jun，REN Lirong，TAN Jingdong.Research of TDOA based self-localization approach in wireless sensor network［C］//International Conference on Intelligent Robots and Systems.China，2006:2035-2040.

［6］LI M，LIU Y H.Rendered path:Range-free localization in anisotropic sensor networks with holes［J］.IEEE/ACM Transactions on Networking，2010，18(1):320-332.

［7］FANG Zheng，ZHAO Zhan.Ranging analysis based on RSSI［J］.Chinese Journal of Sensors and Actuators，2007，22(11):2526-2530(in Chinese).［方震，趙湛.基于RSSI測距分析 ［J］.傳感技術(shù)學(xué)報，2007，22(11):2526-2530.］

［8］Yassine F，Safa h.A hybrid Dv-Hop for localization in large scale wireless sensor network［C］//Proceeding of the 6th International Conference on Mobile Technology，Application and Systems.New York:ACM，2009:1-6.

［9］WAN Xinsheng，ZHAO Yanjing，LI Haitao.Research on improvement of algorithm Dv-Hop ［J］.Computer Science，2011，38(2):76-78(in Chinese).［王新生，趙衍靜，李海濤.基于Dv-Hop算法的改進(jìn)研究 ［J］.計算機科學(xué)，2011，38(2):76-78.］

［10］ZHANG Jia，WU Yanhai，SHI Feng，et al.Positioning algorithm based on Dv-Hop wireless sensor net work［J］.Computer Application，2010，30(2):323-326(in Chinese).［張佳，吳延海，石峰，等.基于Dv-Hop無線傳感器網(wǎng)絡(luò)定位算法［J］.計算機應(yīng)用，2010，30(2):323-326.］