肖麗萍，劉曉紅

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

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

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

1 DV-Hop算法描述及存在的問(wèn)題

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

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

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

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

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

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

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

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

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

2 DV-Hop定位算法的改進(jìn)

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

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

針對(duì)以上問(wèn)題，本文提出了一種新的計(jì)算跳數(shù)的方法來(lái)降低由跳數(shù)引入的誤差。為了說(shuō)明本文的改進(jìn)算法，首先定義幾個(gè)參數(shù)。

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

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

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

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

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

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

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

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

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

2.2 未知節(jié)點(diǎn)到錨節(jié)點(diǎn)間跳數(shù)的改進(jìn)

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

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

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

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

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

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

3 改進(jìn)后的算法步驟

改進(jìn)后的DV-Hop算法如下:

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

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

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

4 實(shí)驗(yàn)仿真及結(jié)果分析

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語(yǔ)

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

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

［2］王福豹，史龍，任豐原.無(wú)線傳感器網(wǎng)絡(luò)中的自身定位系統(tǒng)和算法［J］.軟件學(xué)報(bào)，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ú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)迭代定位算法［J］.通信學(xué)報(bào)，2009，30(10):107－113.

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

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

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

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

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

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