肖麗萍，劉曉紅

(燕山大學信息科學與工程學院，河北秦皇島 066004)

無線傳感器網(wǎng)絡WSN(Wireless Sensor Networks)是由部署在監(jiān)測區(qū)域內(nèi)的大量廉價微型傳感器節(jié)點通過無線通信方式形成的一個多跳的自組織的網(wǎng)絡系統(tǒng)［1］，其中節(jié)點定位技術(shù)是其關(guān)鍵技術(shù)之一。節(jié)點定位是根據(jù)本網(wǎng)絡內(nèi)少數(shù)位置已知的節(jié)點(稱為錨節(jié)點)，按照某種定位機制來確定其它未知節(jié)點位置的過程。根據(jù)定位機制可將現(xiàn)有的無線傳感器網(wǎng)絡定位算法大致分為基于測距(Range-Based)的定位算法和無需測距(Range-Free)的定位算法［2］。前者定位精度相對較高，但需要測量相鄰節(jié)點之間的絕對距離或方位，且對網(wǎng)絡的硬件設施要求也比較高，后者僅根據(jù)網(wǎng)絡連通性等信息即可實現(xiàn)定位，因此無需測距的定位技術(shù)以其低功耗，低成本的優(yōu)勢受到了越來越多的關(guān)注。

典型的無需測距的定位算法包括質(zhì)心算法［3］、DV-Hop 算法［4－5］、APIT 算法［6］和 MDS-MAP［7］算法等，其中DV-hop算法巧妙地將網(wǎng)絡的連通信息和距離矢量信息轉(zhuǎn)化為近似的距離測量，是目前研究最廣泛的算法之一。文獻［8－12］都對該算法進行了不同程度的改進，但是仍然存在較大的定位誤差，因此本文提出了一種基于跳數(shù)修正的定位算法。

1 DV-Hop算法描述及存在的問題

DV-Hop算法是一種基于距離矢量的分布式定位算法，該算法的實現(xiàn)大致分為3個階段:

第1階段 網(wǎng)絡中的各錨節(jié)點通過典型的距離矢量交換協(xié)議向鄰居節(jié)點廣播自身位置信息分組，使得網(wǎng)絡中的所有節(jié)點獲得距錨節(jié)點的最小跳數(shù)信息。

第2階段 每個錨節(jié)點在獲得其它錨節(jié)點的位置和相隔的最小跳數(shù)信息后，根據(jù)下式計算錨節(jié)點i自身的平均每跳距離Ci:

式中，(xi，yi)、(xj，yj)為錨節(jié)點i與j的實際坐標，dij為錨節(jié)點i到其他錨節(jié)點的直線距離，且

hopsij為錨節(jié)點i與j之間的最小跳數(shù)(i≠j)。每個錨節(jié)點將計算得到的平均每跳距離以洪泛的方式廣播到網(wǎng)絡中，未知節(jié)點僅記錄接收到的第1個平均每跳距離(之后收到的丟棄)，并對該平均每跳距離立即轉(zhuǎn)發(fā)，再結(jié)合第1階段記錄的最小跳數(shù)可近似計算得到與各錨節(jié)點的距離。

第3階段 未知節(jié)點得到3個或3個以上錨節(jié)點的距離后，再利用三邊測量法或極大似然估計算法計算出自身的位置坐標，從而完成定位。

圖1 DV-Hop定位算法示意圖

假設p為待定位節(jié)點，p到錨節(jié)點i、j、k的最小跳數(shù)分別為hopspi、hopspj和hopspk，其中p與錨節(jié)點i之間的距離最短，因此p從錨節(jié)點i處獲得平均每跳距離值，即Cp=Ci，再結(jié)合第1階段記錄的最小跳數(shù)便可得到未知節(jié)點p到各錨節(jié)點的估計距離分別為:Cphopspi、Cphopspj、Cphopspk。然后運用三邊測量法計算節(jié)點p的位置坐標。

傳統(tǒng)的DV-Hop算法不需要直接測量節(jié)點之間的距離或角度信息，而是依賴于節(jié)點間的跳數(shù)。對于各向同性的密集網(wǎng)絡，各節(jié)點可以得到合理的平均每跳距離，從而達到較高的定位精度，但對于拓撲不規(guī)則的網(wǎng)絡，定位精度會明顯下降。這主要是因為實際應用中WSN的節(jié)點一般是隨機分布的，錨節(jié)點和未知節(jié)點之間往往不是直線路徑，且節(jié)點間實際每跳長度也不盡相同，因此運用相同的平均跳距去估計節(jié)點間的距離必定會產(chǎn)生較大的誤差。針對上述問題，學者們對其進行了不同的改進，如文獻［8］采用最小均方誤差法對平均跳距進行修正，并進行了迭代求精；文獻［9］引入多維平均跳距的概念來修正平均跳距；文獻［10］中對最小二乘法進行了加權(quán)；文獻［11］利用夾角對平均每跳距離修正；文獻［12］用所有錨節(jié)點的平均跳距對每個跳距進行修正，同時對不良節(jié)點進行了簡單處理，這些改進算法在一定程度上都起到了提高定位精度的作用，但仍有不足，本文重點對節(jié)點間的跳數(shù)進行修正。

2 DV-Hop定位算法的改進

傳統(tǒng)DV-Hop定位算法在計算節(jié)點間跳數(shù)時，在通信范圍內(nèi)無論其相距多遠，都將其跳數(shù)估計為一跳，而每跳的距離不同，利用公式Cphopspi計算時，必然偏離實際距離，造成節(jié)點定位出現(xiàn)較大的誤差。如圖2中的錨節(jié)點L1與錨節(jié)點L2之間的最短路徑，其中每跳的長度都不同，只有最后一跳的長度接近于實際值，即節(jié)點的通信半徑，但用傳統(tǒng)DVHop定位算法計算錨節(jié)點間的最小跳數(shù)時仍然記為4跳，這必定會給最后的定位引入較大的誤差。

圖2 兩錨節(jié)點間的最短路徑

針對以上問題，本文提出了一種新的計算跳數(shù)的方法來降低由跳數(shù)引入的誤差。為了說明本文的改進算法，首先定義幾個參數(shù)。

定義1兩錨節(jié)點i與j之間的實際距離與所有節(jié)點的通信半徑R之比定義為理想跳數(shù)，用Hij表示，即:

定義2節(jié)點間實際跳數(shù)與理想跳數(shù)的相對誤差定義為偏離因子，用αij表示，即:

其中，hopsij為錨節(jié)點i與j之間的實際跳數(shù)值。偏離因子反映了節(jié)點間平均每一跳偏離理想跳數(shù)的程度，αij越大，表明實際跳數(shù)偏離理想跳數(shù)的程度越大，用此實際跳數(shù)代替理想跳數(shù)時引入的誤差就越大。

定義3假設錨節(jié)點i與j之間的實際跳數(shù)為hopsij，偏離因子為αij，定義跳數(shù)修正系數(shù)wij為:

其中n取正整數(shù)，當n=2時，定位效果最佳，下面給出本文的跳數(shù)修正算法。

2.1 錨節(jié)點間跳數(shù)

為了盡可能使實際跳數(shù)接近理想值，按下式對錨節(jié)點間跳數(shù)進行修正:

其中，hops'ij為錨節(jié)點間修正后的跳數(shù)，hopsij為錨節(jié)點間的實際跳數(shù)。

改進后的跳數(shù)與理想跳數(shù)的偏差為:

2.2 未知節(jié)點到錨節(jié)點間跳數(shù)的改進

傳統(tǒng)DV-Hop定位算法中未知節(jié)點計算距離錨節(jié)點的距離時采用距離矢量交換協(xié)議得到的是整數(shù)跳數(shù)，實際的跳數(shù)并非都是整數(shù)，因此由整數(shù)跳數(shù)計算未知節(jié)點到各錨節(jié)點的距離的必然存在誤差。針對這一不足本文對未知節(jié)點與錨節(jié)點間的跳數(shù)進行了修正。

①未知節(jié)點計算距其最近錨節(jié)點的跳數(shù)

假設未知節(jié)點p與錨節(jié)點i之間的實際跳數(shù)為hopspi，錨節(jié)點數(shù)為n，本文利用如式(7)進行修正，修正后的跳數(shù)為:

②未知節(jié)點計算距其它錨節(jié)點的跳數(shù)

未知節(jié)點p計算距其它錨節(jié)點的跳數(shù)時運用如式(8)進行修正:

式中wij由式(5)得到，hopspj為未知節(jié)點與其它錨節(jié)點間的實際跳數(shù)。在實際網(wǎng)絡中大多數(shù)未知節(jié)點到任兩錨節(jié)點的路徑會有部分重疊［13］，因此用兩錨節(jié)點間的偏離因子更能體現(xiàn)未知節(jié)點距離其它錨節(jié)點跳數(shù)偏離程度。

3 改進后的算法步驟

改進后的DV-Hop算法如下:

第1階段:與傳統(tǒng)算法相同，所有節(jié)點獲得到各錨節(jié)點的距離和跳數(shù)信息。

第2階段:各錨節(jié)點首先運用式(6)修正錨節(jié)點間的跳數(shù)，然后用修正后的跳數(shù)根據(jù)式(1)計算每個錨節(jié)點的平均每跳距離。

第3階段:未知節(jié)點分別運用式(7)、式(8)修正距其最近錨節(jié)點和其它錨節(jié)點的跳數(shù)，然后結(jié)合與其最近錨節(jié)點的平均每跳距離計算距離個錨節(jié)點的距離。最后對計算出的距離采用二維雙曲線定位算法［14］得到未知節(jié)點的位置估計坐標。

4 實驗仿真及結(jié)果分析

為了對改進算法進行驗證，本文首先對提出的跳數(shù)修正系數(shù)中的n取不同正整數(shù)值時的性能進行了仿真，并對傳統(tǒng)的DV-Hop算法、文獻［9］和本文的改進算法進行了仿真對比。仿真的網(wǎng)絡環(huán)境如下:傳感器節(jié)點隨機分布在100 m×100 m的正方形區(qū)域內(nèi)(假設所有節(jié)點的通信半徑R都相同)，分別研究在不同的錨節(jié)點比例、不同節(jié)點個數(shù)和不同的通信半徑的條件下傳統(tǒng)算法和改進算法的定位誤差。

在無線傳感器網(wǎng)絡中，定義平均定位誤差error為所有未知節(jié)點的估計值與實際值的差值的平均值:

式中(x'i，y'i)和(xi，yi)分別為未知節(jié)點的估計位置和實際位置，K為仿真次數(shù)，un為未知節(jié)點總數(shù)。為了消除由于節(jié)點隨機分布造成的誤差的不穩(wěn)定性，在相同的網(wǎng)絡環(huán)境下分別進行500次仿真實驗，然后取平均值。

定義歸一化平均定位誤差為平均定位誤差error與通信半徑R(單位:m)的比值:

圖3給出了改進算法在取不同跳數(shù)修正系數(shù)的情況下，定位誤差隨錨節(jié)點比例的變化曲線。從圖中可以看出，當跳數(shù)修正因子中n=2時，定位精度最優(yōu)，所以本文算法中n都取2。

圖3 不同修正系數(shù)下的定位誤差

圖4給出了總節(jié)點數(shù)為100，通信半徑為20 m的情況下節(jié)點歸一化平均定位誤差與錨節(jié)點比例的關(guān)系曲線，由仿真結(jié)果可以看出，3種定位算法的歸一化平均定位誤差都隨錨節(jié)點比例的增加而減小，并逐漸趨于穩(wěn)定，但本文改進算法的歸一化平均定位誤差較傳統(tǒng)DV-Hop算法降低了約10% ～15%，較文獻［9］降低了約4% ～8%。

圖4 節(jié)點歸一化平均定位誤差與錨節(jié)點比例的關(guān)系

圖5給出了錨節(jié)點比例為10%，節(jié)點通信半徑為20 m的情況下節(jié)點歸一化平均定位誤差與總節(jié)點個數(shù)的關(guān)系曲線，由仿真結(jié)果可以看出，3種算法的歸一化平均定位誤差都隨總節(jié)點數(shù)量的增加減小，并逐漸趨于穩(wěn)定。這是因為節(jié)點所在區(qū)域不變的情況下，節(jié)點總數(shù)的增加將會使網(wǎng)絡中節(jié)點密度增大，從而提高了定位精度。同樣，本文算法的誤差小于傳統(tǒng)DV-Hop算法和文獻［9］的算法，而且這種優(yōu)勢在總節(jié)點數(shù)較少的時候更加突出。

圖5 節(jié)點歸一化平均定位誤差與總節(jié)點個數(shù)的關(guān)系

圖6給出了錨節(jié)點比例為10%時節(jié)點平均定位誤差與通信半徑的關(guān)系曲線，由仿真結(jié)果可以看出，3種定位算法的平均定位誤差都隨節(jié)點通信半徑的增加而增大，這是因為通信半徑的增大導致了節(jié)點間跳數(shù)的誤差增大，從而使節(jié)點平均跳距誤差增大，而傳統(tǒng)算法和改進算法都是通過跳數(shù)和平均跳距來估計未知節(jié)點位置的，所以節(jié)點的平均定位誤差隨著節(jié)點通信半徑的增大而增大。但在相同的通信半徑情況下，本文算法的平均定位誤差低于傳統(tǒng)DV-hop方法和文獻［9］的定位誤差。

圖6 節(jié)點平均定位誤差與通信半徑的關(guān)系

5 結(jié)束語

本文針對傳統(tǒng)DV-Hop定位算法在隨機分布網(wǎng)絡環(huán)境中的局限性進行了改進。首先對錨節(jié)點間的最短跳數(shù)進行了修正，之后對未知節(jié)點與錨節(jié)點間的跳數(shù)進行了修正，仿真表明，該改進算法的定位誤差明顯優(yōu)于傳統(tǒng)算法。該算法并沒有改變傳統(tǒng)DVHop算法的基本定位過程，且無需額外的硬件支持，具有較好的實用價值。

［1］孫利明，李建中，陳瑜，等.無線傳感器網(wǎng)絡［M］.北京:清華大學出版社，2005:149－151.

［2］王福豹，史龍，任豐原.無線傳感器網(wǎng)絡中的自身定位系統(tǒng)和算法［J］.軟件學報，2005，5(16):857－868.

［3］Bulusu N，Heidemann J，Estrin D.GPS-Less Low Cost Outdoor Localization for Very Small Devices［J］.IEEE Personal Communications Magazine，2000，7(5):28－34.

［4］Niculescu D，Nath B.DV Based Positioning in Ad Hoc Networks［J］.Telecommunication Systems，2003，22(1－4):267－280.

［5］Niculescu D，Nath B.Ad-Hoc Positioning System(AP-S)［C］//Proc of the 2001 IEEE Global Telecommunications Conf.San Antonio:IEEE Communications Society，2001，2926－2931.

［6］He T，Huang C D，Blum B M，et al.Range-Free Localization Schemes for Large Scale Sensor Networks［C］//Proc of the 9th Annual Int’1 Conf on Mobile Computingand Networking.San Diego:ACM Press，2003，81－95.

［7］Shang Y，Ruml W，Zhang Y，et al.Localization from Mere Connectivity［C］//Proc of the 4th ACM Int’1 Symp on Mobile Ad Hoc Networking＆ Computing.Annapolis:ACM Press，2003，201－212.

［8］林金朝，陳曉冰，劉海波.基于平均跳距修正的無線傳感器網(wǎng)絡節(jié)點迭代定位算法［J］.通信學報，2009，30(10):107－113.

［9］胡蜂松，孟湘琴.多維平均跳距值的DV-Hop定位算法研究［J］.計算機工程與應用，2011，47(28):42－44，68.

［10］朱敏，劉昊霖，張志宏，等.一種基于DV-Hop改進的無線傳感器網(wǎng)絡定位算法［J］.四川大學學報(工程科學版)，2012，44(1):93－98.

［11］王新生，趙衍靜，李海濤.基于DV-Hop定位算法的改進研究［J］.計算機科學，2011，38(2):76－78，90.

［12］李輝，熊盛武，劉毅，等.無線傳感器網(wǎng)絡DV-HOP定位算法的改進［J］.傳感技術(shù)學報，2011，24(1):1782－1785.

［13］沈明玉，張寅.基于改進的平均跳距和估計距離的DV-Hop定位算法［J］.計算機應用研究，2011，28(2):648－650.

［14］石為人，賈傳江，梁煥煥.一種改進的無線傳感器網(wǎng)絡DV-Hop定位算法［J］.傳感技術(shù)學報，2011，24(1):83－87.