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

(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］。基于距離的定位機制一般定位精度相對較高，對節(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)典算法，提出了許多的改進算法，進一步提高定位性能，使傳感器網(wǎng)絡(luò)能更好的應(yīng)用于實際。本文主要是針對Dv-Hop算法的不足提出改進，并借助仿真工具加以驗證，得出了較優(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算法的改進

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ù)RSSI算出對應(yīng)的距離d。文獻(xiàn)［7］對基于RSSI的測距進行了分析，其結(jié)論表明，在15米以內(nèi)，RSSI測距有較高的精度。在15米以內(nèi)用RSSI測距獲得的數(shù)據(jù)比原算法估算的數(shù)據(jù)更精確。

2.2 改進后的Dv-Hop算法

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

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

3 仿真與分析

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

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

絕對定位誤差定義為

相對定位誤差定義為

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

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

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

圖1 兩種算法下誤差對比

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

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

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

從圖2中可以看出，不完整改進算法在通信半徑較小時候相對原算法能較大幅度的提高定位精度，但在R超過65后，不完整改進算法已不能提高算法性能。這是因為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 不同通信半徑下算法性能比較

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

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

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

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

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

4 結(jié)束語

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

［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］.計算機科學(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.］