無(wú)線傳感器網(wǎng)絡(luò)質(zhì)心和DV-Hop混合定位算法研究

張 悅，梁建國(guó)，張 浩，花 嶸，馮魯彬

(山東科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，山東青島 266590)

0 引言

物聯(lián)網(wǎng)技術(shù)使互聯(lián)網(wǎng)領(lǐng)域得到充分?jǐn)U展，改變了人類(lèi)社會(huì)的生活方式[1]，而在物聯(lián)網(wǎng)中最重要的組成部分是無(wú)線傳感器網(wǎng)絡(luò)(wireless sensor networks，WSN)。節(jié)點(diǎn)定位技術(shù)是無(wú)線傳感器網(wǎng)絡(luò)的重要技術(shù)支撐，對(duì)無(wú)線傳感器網(wǎng)絡(luò)應(yīng)用的有效性起著至關(guān)重要的作用[2]。目前無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位分為基于測(cè)距定位和無(wú)需測(cè)距定位[3]。基于測(cè)距的定位精度比較高，但是對(duì)于硬件依賴(lài)性較高，不適用于功耗和成本較低的無(wú)線傳感器網(wǎng)絡(luò)應(yīng)用領(lǐng)域[4-5]。無(wú)需測(cè)距的定位雖定位精度比較低，但是對(duì)于節(jié)點(diǎn)的硬件要求不高，可以滿足大多數(shù)無(wú)線傳感器網(wǎng)絡(luò)的定位需求[6]，目前此定位方法更受大家青睞。無(wú)需測(cè)距的定位算法有質(zhì)心定位算法[7]、DV-Hop定位算法[8]等。質(zhì)心定位算法和DV-Hop定位算法在定位過(guò)程中完全依靠網(wǎng)絡(luò)連通度來(lái)實(shí)現(xiàn)節(jié)點(diǎn)定位，無(wú)需外界任何硬件手段[9-11]。然而，這兩種算法定位精確度與錨節(jié)點(diǎn)的個(gè)數(shù)、節(jié)點(diǎn)通信半徑以及節(jié)點(diǎn)總數(shù)等有非常大的關(guān)系。質(zhì)心定位算法在錨節(jié)點(diǎn)分布密度較高的情況下定位性能較高，在錨節(jié)點(diǎn)分布密度較低的情況下，其定位效果比較差，而對(duì)于DV-Hop定位算法而言，在稀疏的錨節(jié)點(diǎn)個(gè)數(shù)下仍能對(duì)節(jié)點(diǎn)進(jìn)行定位，但其定位效果卻不理想[12-15]。

綜上所述，本文針對(duì)質(zhì)心定位算法和DV-Hop定位算法在定位性能上存在問(wèn)題，從3個(gè)方面對(duì)其進(jìn)行了改進(jìn)。在質(zhì)心定位算法和DV-Hop定位算法實(shí)現(xiàn)有機(jī)結(jié)合、優(yōu)勢(shì)互補(bǔ)的基礎(chǔ)上，提出了一種質(zhì)心和DV-Hop混合定位算法(mixed centroid and DV-Hop algorithm，MCDA)，以提高定位的性能。

1 技術(shù)思路

本文通過(guò)引入TTL值設(shè)定限定錨節(jié)點(diǎn)廣播數(shù)據(jù)包的范圍、提高鄰居錨節(jié)點(diǎn)的比例以及改進(jìn)質(zhì)心定位算法3方面對(duì)定位性能進(jìn)行改進(jìn)。

1.1 引入TTL值以改進(jìn)DV-Hop定位算法通信開(kāi)銷(xiāo)大的問(wèn)題

DV-Hop定位算法由2次泛洪組成，第1次泛洪中節(jié)點(diǎn)獲得錨節(jié)點(diǎn)的位置信息和距離錨節(jié)點(diǎn)的最小跳數(shù)，在第2次泛洪中將跳數(shù)信息轉(zhuǎn)換為距離信息(數(shù)據(jù)包結(jié)構(gòu)如圖1所示)。

(a)第1次泛洪

(b)第2次泛洪圖1 DV-Hop定位算法2次泛洪的數(shù)據(jù)包結(jié)構(gòu)

在無(wú)線傳感器網(wǎng)絡(luò)中，未知節(jié)點(diǎn)和錨節(jié)點(diǎn)隨機(jī)分布，且數(shù)量較大，因此在廣播數(shù)據(jù)包和節(jié)點(diǎn)傳遞過(guò)程中，很難避免發(fā)生數(shù)據(jù)包的沖突或碰撞[16]。如若沖突發(fā)生，不僅會(huì)導(dǎo)致信息的缺失，從而使得節(jié)點(diǎn)間的最小跳數(shù)產(chǎn)生偏差，進(jìn)而影響正常的節(jié)點(diǎn)定位；還會(huì)導(dǎo)致數(shù)據(jù)包的重傳，使網(wǎng)絡(luò)開(kāi)銷(xiāo)增大，進(jìn)而拖延整個(gè)定位過(guò)程，導(dǎo)致網(wǎng)絡(luò)能量消耗過(guò)多[17-18]。

因此，需要找到一種有效的方法，在一定程度上減少節(jié)點(diǎn)間的傳播跳數(shù)，從而減小定位誤差，并降低網(wǎng)絡(luò)的整體開(kāi)銷(xiāo)，以達(dá)到節(jié)約能量的目的。

本文通過(guò)為數(shù)據(jù)包設(shè)置一個(gè)TTL生存周期域來(lái)減少通信量(改進(jìn)的數(shù)據(jù)包格式如圖2所示)。

(a)第1次泛洪

(b)第2次泛洪圖2 改進(jìn)后2次泛洪的數(shù)據(jù)包結(jié)構(gòu)

基于TTL值的設(shè)定，可以控制廣播包僅在TTL值規(guī)定的范圍內(nèi)進(jìn)行數(shù)據(jù)傳輸，避免了泛洪數(shù)據(jù)包過(guò)程中的沖突或碰撞，降低數(shù)據(jù)傳輸失誤的概率以及數(shù)據(jù)包重傳造成的網(wǎng)絡(luò)負(fù)擔(dān)。還可以降低定位過(guò)程中基礎(chǔ)性問(wèn)題出錯(cuò)的概率，緩解網(wǎng)絡(luò)高速超負(fù)荷數(shù)據(jù)包分組轉(zhuǎn)發(fā)的壓力，使網(wǎng)絡(luò)的整體開(kāi)銷(xiāo)較小，能量分配更加有效。

1.2 提高鄰居錨節(jié)點(diǎn)的比例以解決質(zhì)心定位算法中錨節(jié)點(diǎn)少定位率低的問(wèn)題

在質(zhì)心定位算法中，若周?chē)鷽](méi)有錨節(jié)點(diǎn)，未知節(jié)點(diǎn)將無(wú)法實(shí)現(xiàn)定位。本文通過(guò)提高未知節(jié)點(diǎn)中鄰居錨節(jié)點(diǎn)的比例來(lái)提高節(jié)點(diǎn)的定位率。

在質(zhì)心定位算法中，未知節(jié)點(diǎn)只把節(jié)點(diǎn)通信范圍內(nèi)的錨節(jié)點(diǎn)作為鄰居節(jié)點(diǎn)，通過(guò)鄰居錨節(jié)點(diǎn)所圍成多邊形的質(zhì)心定位為自己的坐標(biāo)。但在實(shí)驗(yàn)過(guò)程中發(fā)現(xiàn)，有些節(jié)點(diǎn)雖然不在未知節(jié)點(diǎn)的通信范圍之內(nèi)，但它還是可以作為鄰居錨節(jié)點(diǎn)(如圖3所示)，錨節(jié)點(diǎn)B在節(jié)點(diǎn)通信半徑r內(nèi)被視作鄰居錨節(jié)點(diǎn)，但錨節(jié)點(diǎn)C不在通信范圍內(nèi)，故不能視作鄰居錨節(jié)點(diǎn)，實(shí)際上錨節(jié)點(diǎn)C與錨節(jié)點(diǎn)B間的距離相差很小，在一定程度上可以升級(jí)為未知節(jié)點(diǎn)C的鄰居錨節(jié)點(diǎn)。

改進(jìn)具體實(shí)現(xiàn)為：在原來(lái)的質(zhì)心定位算法中只用1跳范圍內(nèi)的錨節(jié)點(diǎn)進(jìn)行定位，現(xiàn)將節(jié)點(diǎn)通信范圍擴(kuò)大到2跳范圍，使用2跳范圍內(nèi)的錨節(jié)點(diǎn)定位。

(a)鄰居錨節(jié)點(diǎn)

(b)錨節(jié)點(diǎn)

1.3 減小定位誤差

擴(kuò)大通信范圍在很大程度上可以提高鄰居錨節(jié)點(diǎn)的比例，但其定位誤差也會(huì)隨之增大，因此，需要改進(jìn)質(zhì)心定位算法以減小定位誤差，具體改進(jìn)步驟如下。

步驟1：在用上述方法找到未知節(jié)點(diǎn)鄰居錨節(jié)點(diǎn)的基礎(chǔ)上，對(duì)鄰居錨節(jié)點(diǎn)進(jìn)一步選擇，判斷1跳范圍內(nèi)是否存在錨節(jié)點(diǎn)，若存在則選擇1跳范圍內(nèi)的鄰居錨節(jié)點(diǎn)進(jìn)行定位，否則選擇大于1跳小于2跳范圍內(nèi)的鄰居錨節(jié)點(diǎn)。選定后，對(duì)其范圍內(nèi)的錨節(jié)點(diǎn)進(jìn)一步取舍，首先用DV-Hop定位算法計(jì)算得出錨節(jié)點(diǎn)每跳的平均距離，錨節(jié)點(diǎn)每跳的平均距離再乘以未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的跳數(shù)作為未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的距離，判斷該距離是否在1.5倍通信范圍內(nèi)，如果在其范圍內(nèi)，則升級(jí)為錨節(jié)點(diǎn)，否則拋棄。

(1)

式中：n是錨節(jié)點(diǎn)的總數(shù)；(xi,yi)、(xj,yj)分別為錨節(jié)點(diǎn)i和j的坐標(biāo)；hij是錨節(jié)點(diǎn)i和j之間的跳數(shù)。

如圖3所示，未知節(jié)點(diǎn)A的鄰居錨節(jié)點(diǎn)有B、C、D、E，由于1跳范圍內(nèi)有錨節(jié)點(diǎn)B、C、D，則選擇它們進(jìn)行定位，錨節(jié)點(diǎn)E將被拋棄，若A在1跳范圍內(nèi)無(wú)錨節(jié)點(diǎn)，則判斷錨節(jié)點(diǎn)E是否在1.5倍通信范圍內(nèi)，若在其范圍內(nèi)則選擇，否則拋棄。

步驟2：用傳統(tǒng)質(zhì)心定位算法對(duì)未知節(jié)點(diǎn)定位。

步驟3：在以上2步的基礎(chǔ)上，進(jìn)行節(jié)點(diǎn)的定位計(jì)算，在圖4中，U、U′分別為未知節(jié)點(diǎn)和傳統(tǒng)質(zhì)心定位算法估算出的U的位置，A、B、C、D、E、F為未知節(jié)點(diǎn)U的鄰居錨節(jié)點(diǎn)。首先分別計(jì)算每個(gè)鄰居錨節(jié)點(diǎn)到U′的距離；其次根據(jù)計(jì)算的距離為每個(gè)鄰居錨節(jié)點(diǎn)賦予不同的權(quán)重，使距離U′遠(yuǎn)的鄰居錨節(jié)點(diǎn)獲得較小的權(quán)重，較近的鄰居錨節(jié)點(diǎn)獲得較大的權(quán)重；最后重新計(jì)算未知節(jié)點(diǎn)U的坐標(biāo)，經(jīng)過(guò)多次迭代，使未知節(jié)點(diǎn)U的坐標(biāo)更加準(zhǔn)確。

圖4 改進(jìn)質(zhì)心定位算法示意圖

計(jì)算錨節(jié)點(diǎn)與其他錨節(jié)點(diǎn)的距離的公式為

(2)

式中：dk為錨節(jié)點(diǎn)與其他錨節(jié)點(diǎn)的距離；(xi,yi)、(xk,yk)為錨節(jié)點(diǎn)的坐標(biāo)。

計(jì)算權(quán)重系數(shù)的公式為

(3)

式中：ρk為權(quán)重系數(shù)；d0為一個(gè)很小可以忽略不計(jì)的值。

計(jì)算未知節(jié)點(diǎn)U坐標(biāo)(x,y)的公式：

(4)

式中：(x,y)為重新計(jì)算未知節(jié)點(diǎn)U的坐標(biāo)；ρk為權(quán)重系數(shù)。

2 質(zhì)心和DV-Hop混合定位算法的提出

綜合上述內(nèi)容，本文提出了一種質(zhì)心和DV-Hop混合定位算法，即MCDA定位算法。

MCDA定位算法分為4個(gè)階段：

(1)未知節(jié)點(diǎn)計(jì)算與每個(gè)錨節(jié)點(diǎn)的最小跳數(shù)與DV-Hop定位算法類(lèi)似，不同的是在錨節(jié)點(diǎn)的廣播數(shù)據(jù)包中包含了TTL值來(lái)限定廣播包傳輸?shù)奶鴶?shù)；

(2)計(jì)算每個(gè)錨節(jié)點(diǎn)每跳的平均距離，公式如下

(5)

式中：ci為計(jì)算所得每個(gè)錨節(jié)點(diǎn)每跳的平均距離；Dij為錨節(jié)點(diǎn)i和j之間的距離；hij為錨節(jié)點(diǎn)i和j之間的跳數(shù)。

(3)選擇2跳范圍內(nèi)的錨節(jié)點(diǎn)作為未知節(jié)點(diǎn)的鄰居錨節(jié)點(diǎn)；

(4)利用改進(jìn)質(zhì)心定位算法計(jì)算未知節(jié)點(diǎn)位置。

3 仿真實(shí)驗(yàn)及分析

為了能夠更客觀、準(zhǔn)確地模擬出MCDA定位算法的真實(shí)性能，在MATLAB平臺(tái)實(shí)驗(yàn)仿真時(shí)，所有節(jié)點(diǎn)包括錨節(jié)點(diǎn)和未知節(jié)點(diǎn)均在網(wǎng)絡(luò)區(qū)域中隨機(jī)生成。仿真參數(shù)的設(shè)置如表1所示。

表1 仿真參數(shù)設(shè)置

由表1可知，所有數(shù)據(jù)的產(chǎn)生都是對(duì)網(wǎng)絡(luò)運(yùn)行仿真100次求得結(jié)果的平均值。MCDA定位算法中生存周期TTL值為15，即限制錨節(jié)點(diǎn)數(shù)據(jù)包僅傳播15跳，定位性能仿真過(guò)程中，使用平均定位誤差和定位率作為定位算法定位性能的衡量指標(biāo)。

圖5為WSN網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)圖，網(wǎng)絡(luò)區(qū)域范圍是100 m×100 m，網(wǎng)絡(luò)中所有節(jié)點(diǎn)隨機(jī)分布，圓圈表示未知節(jié)點(diǎn)，星型表示錨節(jié)點(diǎn)。

圖5 WSN網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)圖

3.1 錨節(jié)點(diǎn)個(gè)數(shù)對(duì)定位性能的影響

圖6為錨節(jié)點(diǎn)數(shù)量從3變化到30時(shí)，質(zhì)心定位算法、DV-Hop定位算法以及本文提出的MCDA定位算法定位性能的變化圖，選擇錨節(jié)點(diǎn)總個(gè)數(shù)為100個(gè)，節(jié)點(diǎn)通信半徑為25 m。當(dāng)節(jié)點(diǎn)總數(shù)與節(jié)點(diǎn)通信半徑不變時(shí)，3種定位算法平均定位誤差都隨著錨節(jié)點(diǎn)數(shù)量的增加而減小，當(dāng)錨節(jié)點(diǎn)的數(shù)量增加到15以上時(shí)，3種定位算法的平均定位誤差變化較小。在錨節(jié)點(diǎn)數(shù)量從3變化到10時(shí)，MCDA定位算法平均定位誤差比DV-Hop定位算法平均定位誤差低，同時(shí)比質(zhì)心定位算法平均定位誤差高，但是當(dāng)錨節(jié)點(diǎn)數(shù)量從10逐漸開(kāi)始增加后，MCDA定位算法的定位誤差變得最低，而且它的定位率比質(zhì)心定位算法高，但比DV-Hop定位算法的定位率低。

圖6 不同錨節(jié)點(diǎn)數(shù)下的平均定位誤差對(duì)比

圖7為錨節(jié)點(diǎn)數(shù)量為從3變化到30，節(jié)點(diǎn)通信半徑分別為20，25，30時(shí)，本文提出的MCDA定位算法定位性能的變化圖?？梢钥闯?，隨著錨節(jié)點(diǎn)的增加，MCDA定位算法定位誤差不斷減小，定位率不斷增加；但隨著節(jié)點(diǎn)通信半徑的增加，其定位誤差不斷增加，其定位率也在變大，這一特性與質(zhì)心定位算法相似。

3.2 節(jié)點(diǎn)通信半徑對(duì)定位性能的影響

圖8(a)、圖8(b)和圖8(c)給出了節(jié)點(diǎn)通信半徑從20變化到40，錨節(jié)點(diǎn)數(shù)分別為5、10和20時(shí)，3種算法定位性能的比較。

圖7 不同錨節(jié)點(diǎn)下MCDA算法的定位性能比較

(a)錨節(jié)點(diǎn)數(shù)為5

(b)錨節(jié)點(diǎn)數(shù)為10

(c)錨節(jié)點(diǎn)數(shù)為20圖8 不同節(jié)點(diǎn)通信半徑下定位性能比較

由圖8可知，當(dāng)DV-Hop定位算法在錨節(jié)點(diǎn)數(shù)量為5，定位誤差非常大，MCDA定位算法定位誤差較小，MCDA的平均定位誤差與DV-Hop相比降低了53.7%，質(zhì)心定位算法誤差最小，但MCDA的定位率也比質(zhì)心定位算法要高；當(dāng)錨節(jié)點(diǎn)數(shù)量變?yōu)?0和20，DV-Hop定位算法的定位誤差迅速減小，質(zhì)心定位算法和MCDA定位算法有所下降，下降幅度不大；隨節(jié)點(diǎn)通信半徑的增加，DV-Hop定位算法的定位誤差先減小后增加，質(zhì)心定位算法和MCDA定位算法的定位誤差均持續(xù)遞增；當(dāng)節(jié)點(diǎn)數(shù)變?yōu)?0和20時(shí)，MCDA的平均定位率比質(zhì)心定位算法提高了28.5%和14.2%。MCDA定位率趨近于1的速度比質(zhì)心定位算法快，當(dāng)兩者定位率都達(dá)到1時(shí)，前者定位誤差要比后者小，說(shuō)明改進(jìn)的質(zhì)心定位算法獲得了一定效果。

綜上所述，MCDA定位算法在錨節(jié)點(diǎn)數(shù)量較低時(shí)，其定位誤差比質(zhì)心定位算法高，比DV-Hop定位算法的定位誤差低，但其定位率要高于質(zhì)心定位算法，且低于DV-Hop定位算法的定位率。

4 結(jié)論

本文在分析質(zhì)心定位算法和DV-Hop定位算法的基礎(chǔ)上，從3個(gè)方面進(jìn)行改進(jìn)：首先通過(guò)引入TTL值設(shè)定限定錨節(jié)點(diǎn)廣播數(shù)據(jù)包的范圍以減小DV-Hop定位算法通信開(kāi)銷(xiāo)的問(wèn)題；其次提高鄰居錨節(jié)點(diǎn)的比例改進(jìn)了質(zhì)心定位算法錨節(jié)點(diǎn)低時(shí)定位率低的問(wèn)題；最后改進(jìn)質(zhì)心定位算法減小了定位誤差，進(jìn)而提出了MCDA定位算法。仿真結(jié)果表明，MCDA定位算法在無(wú)需額外增加硬件設(shè)施開(kāi)銷(xiāo)的條件下，較好地解決了在錨節(jié)點(diǎn)較低的情況下質(zhì)心定位算法定位誤差小但定位率低以及DV-Hop定位算法定位率高但定位誤差大的問(wèn)題。盡管MCDA定位算法與其他兩種算法相比在減少定位誤差和提高定位率方面取得了一定的效果，但隨著錨節(jié)點(diǎn)數(shù)量的增加，仍需研究如何提高定位率的同時(shí)并減少定位誤差。