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

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

0 引言

無線傳感器網(wǎng)絡(luò)是由大量無線傳感器節(jié)點(diǎn)以Ad-Hoc的組網(wǎng)方式構(gòu)成的無線網(wǎng)絡(luò)，其目的是感知、采集和處理其覆蓋區(qū)域中感知對(duì)象的信息［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é)點(diǎn)內(nèi)安裝GPS接收機(jī)，通過GPS接收機(jī)與衛(wèi)星的通信，實(shí)現(xiàn)GPS接收機(jī)的定位功能。但是在實(shí)際應(yīng)用中，無線傳感器網(wǎng)絡(luò)要求節(jié)點(diǎn)價(jià)格低廉，功耗和體積小，在這種限制下，通常只會(huì)將GPS接收機(jī)安裝于少數(shù)傳感器節(jié)點(diǎn)，這些傳感器節(jié)點(diǎn)稱為錨節(jié)點(diǎn)。無線傳感器網(wǎng)絡(luò)中的定位算法就是未知節(jié)點(diǎn)借助這些錨節(jié)點(diǎn)的坐標(biāo)信息來實(shí)現(xiàn)節(jié)點(diǎn)自身的定位［2］。無線傳感器網(wǎng)絡(luò)中的定位算法分類標(biāo)準(zhǔn)有很多，使用較多的是依據(jù)是否需要測量節(jié)點(diǎn)間距離或角度等信息來分類，依照這種劃分，可以把定位算法分為基于距離的定位［5］和與距離無關(guān)的定位［6］?；诰嚯x的定位機(jī)制一般定位精度相對(duì)較高，對(duì)節(jié)點(diǎn)的硬件通常也提出了較高要求，基于距離定位機(jī)制常用測距方法有RSSI(received signal strength indicator)、TOA(time of arrival)、TDOA(time difference on arrival)、AOA(angle of arrival)。與距離無關(guān)的定位機(jī)制無需實(shí)際測量節(jié)點(diǎn)間的絕對(duì)距離或方位，對(duì)節(jié)點(diǎn)硬件的要求低，使得節(jié)點(diǎn)成本更適合于大規(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)用于實(shí)際。本文主要是針對(duì)Dv-Hop算法的不足提出改進(jìn)，并借助仿真工具加以驗(yàn)證，得出了較優(yōu)的性能。

1 Dv-Hop算法

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

1.1 Dv-Hop算法的定位過程

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

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

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

(2)計(jì)算未知節(jié)點(diǎn)到錨節(jié)點(diǎn)間的距離。

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

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

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

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

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

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

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

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

X可以由式 (6)求出。

其中

1.2 Dv-Hop算法的誤差分析

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

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

2.1 RRSI測距技術(shù)

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

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

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

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

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

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

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

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

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

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

3 仿真與分析

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

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

絕對(duì)定位誤差定義為

相對(duì)定位誤差定義為

3.1 同一場景下，兩算法性能對(duì)比

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

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

圖1 兩種算法下誤差對(duì)比

3.2 不同通信半徑下，算法性能對(duì)比

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

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

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

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

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

3.3 不同錨節(jié)點(diǎn)個(gè)數(shù)，算法性能對(duì)比

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

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

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

4 結(jié)束語

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

［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é)報(bào)，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］.計(jì)算機(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］.計(jì)算機(jī)應(yīng)用，2010，30(2):323-326.］