移動(dòng)信標(biāo)改進(jìn)的DV－Hop算法

陳志國，傅 毅，2，須文波，孫 俊

（1.江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院 輕工過程先進(jìn)控制教育部重點(diǎn)實(shí)驗(yàn)室，江蘇 無錫214122 2.無錫環(huán)境科學(xué)與工程研究中心，江蘇 無錫214063）

0 引 言

目前無線傳感器網(wǎng)絡(luò) （wireless sensor network，WSN）由于靈活性大、容錯(cuò)性強(qiáng)等特點(diǎn)廣泛應(yīng)用于醫(yī)療、交通、軍事等領(lǐng)域[1]。WSN的應(yīng)用以數(shù)據(jù)采集為前提，但 WSN的節(jié)點(diǎn)布設(shè)隨機(jī)性強(qiáng)，所以節(jié)點(diǎn)如何知道自身位置成為問題的關(guān)鍵和目前的研究熱點(diǎn)[2]。

WSN的節(jié)點(diǎn)定位一般分為基于測(cè)距的 （range－based）定位和無需測(cè)距的 （range－free）定位兩大類，由于無需額外的硬件，因此實(shí)際應(yīng)用中以后者為主，其中DV－Hop算法備受關(guān)注[3]。DV－Hop算法是基于跳數(shù)原理的距離無關(guān)定位算法，由于后期采用的三邊測(cè)量法會(huì)產(chǎn)生一定的誤差，因此一些智能算法逐漸被引入以降低誤差，如遺傳算法[4]、PSO算法[5]和 QPSO[6]算法改進(jìn)的 DV－Hop算法。本文將采用一種改進(jìn)的QPSO算法來降低DV－Hop算法的定位誤差。定位精度是WSN的一項(xiàng)重要指標(biāo)，但節(jié)點(diǎn)開銷也不容忽視，采用移動(dòng)信標(biāo)可以大大降低成本，因此本文還提出了一種基于虛擬力的信標(biāo)移動(dòng)新方法來降低系統(tǒng)開銷。

1 DV－Hop算法模型

DV－Hop算法的基本原理是先通過計(jì)算跳數(shù)獲得網(wǎng)絡(luò)拓?fù)湫畔?，然后用三邊定位法獲得未知節(jié)點(diǎn)信息[7]。跳數(shù)計(jì)算過程如下:①每個(gè)信標(biāo)節(jié)點(diǎn)將自己的位置信息包向外進(jìn)行廣播，初始時(shí)跳數(shù)為0，收到信息包的節(jié)點(diǎn)更新自己的信息表；②繼續(xù)上一次的廣播過程，信息包每轉(zhuǎn)發(fā)一次跳數(shù)就加1；③節(jié)點(diǎn)收到新信息包時(shí)先查看自己的信息表里是否已有該信息包的標(biāo)識(shí)，若有且新信息包的跳數(shù)值更小，就更新跳數(shù)值；否則新數(shù)據(jù)包被忽略，停止轉(zhuǎn)發(fā)。

按照這種規(guī)則進(jìn)行全網(wǎng)內(nèi)跳數(shù)廣播，便得到錨節(jié)點(diǎn)到其他所有錨節(jié)點(diǎn)的跳數(shù)和位置。根據(jù)位置坐標(biāo)，錨節(jié)點(diǎn)i可以計(jì)算出他們之間的距離，然后每一個(gè)錨節(jié)點(diǎn)按公式 （1）計(jì)算平均每跳距離

其中 （xi，yi）是錨節(jié)點(diǎn)i的坐標(biāo)，（xj，yj）是除錨節(jié)點(diǎn)i之外的錨節(jié)點(diǎn)坐標(biāo)，hi，j是錨節(jié)點(diǎn)i到錨節(jié)點(diǎn)j之間的跳數(shù)，n是錨節(jié)點(diǎn)總數(shù)。然后錨節(jié)點(diǎn)i向鄰居節(jié)點(diǎn)廣播平均每跳距離，由于數(shù)據(jù)包里含有錨節(jié)點(diǎn)自身標(biāo)識(shí)和平均每跳距離，其他節(jié)點(diǎn)收到該數(shù)據(jù)包時(shí)先比對(duì)標(biāo)識(shí)，若標(biāo)識(shí)不重復(fù)就向鄰居節(jié)點(diǎn)繼續(xù)廣播，否則丟棄該數(shù)據(jù)包。這樣網(wǎng)絡(luò)中的每一個(gè)節(jié)點(diǎn)都知道了所有n個(gè)錨節(jié)點(diǎn)計(jì)算出的平均每跳距離，對(duì)這些平均每跳距離取平均值作為自己的每跳平均距離。

之后，未知節(jié)點(diǎn)得到了其距離所有n個(gè)錨節(jié)點(diǎn)的每跳平均距離矩陣和跳數(shù)矩陣。對(duì)某一個(gè)錨節(jié)點(diǎn)的跳數(shù)與每跳平均距離的乘積就是該節(jié)點(diǎn)到錨節(jié)點(diǎn)的距離[9]，通常采用三邊測(cè)量法或多邊測(cè)量法。然后根據(jù)最小二乘法原理，求出未知節(jié)點(diǎn)的最小二乘位置估計(jì)。

由于上述DV－Hop算法采用的三邊或多邊測(cè)量方法會(huì)產(chǎn)生較大的誤差，為了進(jìn)一步提高定位精度，這里將引入一種改進(jìn)的QPSO智能算法對(duì)Dv－Hop算法的測(cè)量結(jié)果進(jìn)行優(yōu)化，以提高節(jié)點(diǎn)的定位精度。

2 BDQPSO改進(jìn)DV－Hop節(jié)點(diǎn)定位算法

2.1 BDQPSO算法的提出

QPSO算法是J.Sun等人提出的一種改進(jìn)的粒子群優(yōu)化 （particle swarm optimization，PSO）算法[10]，該算法從量子力學(xué)的角度出發(fā)對(duì)PSO算法的缺點(diǎn)進(jìn)行改進(jìn)，具有較好的優(yōu)化結(jié)果，獲得了廣泛應(yīng)用。為了進(jìn)一步提高QPSO算法的收斂精度和全局搜索能力，這里提出一種最佳維改進(jìn)的 QPSO 算 法:BDQPSO （best dimension quantum－behaved particle swarm optimization）算法。雖然QPSO算法的收斂速度較快，但后期收斂速度會(huì)明顯變慢，當(dāng)接近全局最優(yōu)位置時(shí)可能導(dǎo)致粒子停滯在局部最優(yōu)位置。這里提出一種新的方法，最佳維 （best－dimension，BD）擾動(dòng)技術(shù)，它可以在QPSO迭代時(shí)找到最佳維來執(zhí)行擾動(dòng)。具體的BD算法流程描述如下:

（2）在選定粒子位置矢量中隨機(jī)選擇s維進(jìn)行變異，產(chǎn)生s個(gè)變異的粒子XM＝（XM1，XM2，…，XMs），其中minX）＋minX；

（3）從s個(gè)變異粒子XM和父代粒子Xit中，選出最好適應(yīng)度的粒子，計(jì)算最好適應(yīng)度值

為了測(cè)試BDQPSO算法性能，用表1的標(biāo)準(zhǔn)測(cè)試函數(shù)對(duì)算法進(jìn)行分析，同時(shí)與QPSO算法進(jìn)行對(duì)比。測(cè)試過程中，粒子群數(shù)量設(shè)定為50，維數(shù)設(shè)定為10、20、50和80，迭代次數(shù)設(shè)定為200、500、1000、2000，算法每次獨(dú)立運(yùn)行100次，結(jié)果見表2。實(shí)驗(yàn)環(huán)境為:Pentium E5300 2.6 GHZ，2G內(nèi)存，MATLAB7.04，操作系統(tǒng)為Win7 32位。從表2可見，BDQPSO算法比QPSO算法具有更好的收斂精度，因此更適合于對(duì)DV－Hop算法的定位結(jié)果進(jìn)行優(yōu)化。

表1 標(biāo)準(zhǔn)測(cè)試函數(shù)

2.2 基于BDQPSO改進(jìn)的DV－Hop算法

簡單的節(jié)點(diǎn)定位過程只需要兩個(gè)步驟，即確定未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的距離和計(jì)算未知節(jié)點(diǎn)位置。在第二步中，由于現(xiàn)實(shí)環(huán)境的不確定性，三邊測(cè)量或者多邊測(cè)量方法會(huì)產(chǎn)生一定的誤差，為了提高定位精度，本文用收斂性更好的BDQPSO算法對(duì)DV－Hop算法進(jìn)行改進(jìn)。

適應(yīng)度函數(shù)值是評(píng)價(jià)算法得到的解的優(yōu)劣程度的標(biāo)準(zhǔn)，這里評(píng)價(jià)未知節(jié)點(diǎn)定位精度的標(biāo)準(zhǔn)是該節(jié)點(diǎn)與其他所有錨節(jié)點(diǎn)的距離與第一步中由DV－Hop算法得到的距離的累計(jì)誤差，該誤差越小則定位精度越高，該適應(yīng)度函數(shù)表示如下

其中Pi是錨節(jié)點(diǎn)位置坐標(biāo)，n為錨節(jié)點(diǎn)數(shù)量，xj是未知節(jié)點(diǎn)的位置坐標(biāo)，D（j，i）為未知節(jié)點(diǎn)j到錨節(jié)點(diǎn)i的距離。f（xj）代表未知節(jié)點(diǎn)到所有n個(gè)錨節(jié)點(diǎn)的距離的累計(jì)誤差。

表2 標(biāo)準(zhǔn)測(cè)試函數(shù)測(cè)試結(jié)果

對(duì)DV－Hop算法的改進(jìn)分為三部分:第一部分用DV－h(huán)op算法計(jì)算節(jié)點(diǎn)間距離；第二部分用多邊測(cè)量法對(duì)第一個(gè)模塊得到距離計(jì)算未知節(jié)點(diǎn)的位置坐標(biāo)；第三部分用BDQPSO算法對(duì)第二個(gè)模塊得到的位置坐標(biāo)進(jìn)行迭代優(yōu)化。改進(jìn)的DV－Hop算法的步驟如下:

步驟1 每個(gè)信標(biāo)節(jié)點(diǎn)將位置信息包 （節(jié)點(diǎn)ID、位置坐標(biāo) （xi，yi）和跳數(shù)hi）進(jìn)行廣播，以獲得其它所有錨節(jié)點(diǎn)的坐標(biāo)及跳數(shù)距離，然后用式 （1）計(jì)算出全網(wǎng)平均每跳距離；

步驟2 每個(gè)錨節(jié)點(diǎn)廣播其計(jì)算的平均每跳距離，數(shù)據(jù)轉(zhuǎn)發(fā)過程中也進(jìn)行跳數(shù)計(jì)數(shù)，各個(gè)節(jié)點(diǎn)通過上述信息計(jì)算出該節(jié)點(diǎn)到各個(gè)錨節(jié)點(diǎn)的距離；

步驟3 利用多邊測(cè)量法計(jì)算出未知節(jié)點(diǎn)的位置坐標(biāo)；

步驟4 將步驟3得到的位置坐標(biāo)設(shè)為BDQPSO算法的初始解，然后開始進(jìn)行適應(yīng)度值計(jì)算和迭代優(yōu)化，最終得出更好的結(jié)果。

2.3 算法性能分析

為了測(cè)試算法性能，擬在100×100的標(biāo)準(zhǔn)矩形區(qū)域內(nèi)，隨機(jī)布設(shè)300個(gè)節(jié)點(diǎn)，其中30個(gè)是錨節(jié)點(diǎn)。首先設(shè)置節(jié)點(diǎn)通信半徑為10，錨節(jié)點(diǎn)GPS定位誤差為0，此時(shí)網(wǎng)絡(luò)的平均連通度為9.0741，網(wǎng)絡(luò)的鄰居錨節(jié)點(diǎn)平均數(shù)目為0.94276。

實(shí)驗(yàn)過程將錨節(jié)點(diǎn)比例從1%開始，以2%的增幅增至19%，圖1是原DV－Hop算法、PSO改進(jìn)算法、QPSO改進(jìn)算法和BDQPSO改進(jìn)算法的節(jié)點(diǎn)定位誤差比較結(jié)果，實(shí)驗(yàn)環(huán)境與2.1相同。從圖1中可見，隨著錨節(jié)點(diǎn)比例的增加，BDQPSO改進(jìn)的DV－Hop算法的定位精度不斷提高，定位誤差可以達(dá)到10%左右，這一結(jié)果優(yōu)于DV－Hop算法和其他幾種改進(jìn)算法。由此可見，在上述3個(gè)算法中，提出的BDQPSO改進(jìn)的DV－Hop算法效果最好，性能最穩(wěn)定。

圖1 錨節(jié)點(diǎn)比例與節(jié)點(diǎn)定位誤差關(guān)系

3 改進(jìn)的移動(dòng)信標(biāo)算法

信標(biāo)節(jié)點(diǎn)通過向鄰居節(jié)點(diǎn)廣播自身位置使其他節(jié)點(diǎn)完成定位，信標(biāo)節(jié)點(diǎn)的比例越大定位精度越高，開銷也越大，為了降低系統(tǒng)開銷需要引入移動(dòng)信標(biāo) （mobile beacon）。

移動(dòng)信標(biāo)在待檢測(cè)區(qū)域 （region of interest，ROI）內(nèi)以特定的規(guī)則移動(dòng)并向鄰居節(jié)點(diǎn)廣播自身位置，未知節(jié)點(diǎn)據(jù)此計(jì)算自身位置，移動(dòng)方法可采用靜態(tài)或動(dòng)態(tài)方法[11]。

由于WSN傳感器節(jié)點(diǎn)分布的隨機(jī)性，這里提出一種靜態(tài)路徑和動(dòng)態(tài)路徑相結(jié)合的新方法:首先讓第一個(gè)信標(biāo)以靜態(tài)路徑在ROI中進(jìn)行一遍信號(hào)覆蓋，然后讓第二個(gè)信標(biāo)以虛擬力動(dòng)態(tài)路徑[12]進(jìn)行移動(dòng)，這樣既發(fā)揮了靜態(tài)路徑的優(yōu)勢(shì)，又可以靈活地對(duì)剩下的節(jié)點(diǎn)進(jìn)行遍歷，提高信號(hào)覆蓋率。該方法步驟如下:

步驟1 第一個(gè)移動(dòng)信標(biāo)參考等距三重優(yōu)化模型以預(yù)先確定好的發(fā)射位置移動(dòng)；

步驟2 應(yīng)用虛擬力，第二個(gè)信標(biāo)進(jìn)入ROI進(jìn)行移動(dòng):

（1）第二個(gè)信標(biāo)節(jié)點(diǎn)以第一個(gè)信標(biāo)節(jié)點(diǎn)的相同位置進(jìn)入ROI，到達(dá)m位置時(shí)候向鄰居節(jié)點(diǎn)發(fā)射位置信息；

（2）在m位置發(fā)射半徑內(nèi)的未知節(jié)點(diǎn)收到信息包后，用RSSI算法將損耗功率轉(zhuǎn)化為距離矩陣；

（3）根據(jù)人工勢(shì)場(chǎng)理論[13]，第二個(gè)信標(biāo)節(jié)點(diǎn)在收到反饋信息后，在m位置計(jì)算虛擬力，確定下一個(gè)移動(dòng)位置。

在此過程中有兩種情況需要處理:

1）如果第二個(gè)信標(biāo)節(jié)點(diǎn)沒有收到反饋信息或者受到的虛擬力為0，則信標(biāo)節(jié)點(diǎn)向任意方向移動(dòng)R／2作為新位置；如果連續(xù)移動(dòng)5次以上受到的虛擬力還是0，則跳出程序；

2）如果計(jì)算出的第m＋1個(gè)發(fā)射位置的坐標(biāo)如果超出了邊界范圍，則坐標(biāo)回退到第m個(gè)位置并向任意方向前進(jìn)R／4作為第m＋1個(gè)發(fā)射位置的坐標(biāo)。

算法的流程圖如圖2所示。

圖2 移動(dòng)信標(biāo)算法流程

為了測(cè)試算法性能，現(xiàn)在二維空間中進(jìn)行3組節(jié)點(diǎn)定位實(shí)驗(yàn):

第一組是一個(gè)移動(dòng)信標(biāo)配有GPS定位裝置，以靜態(tài)路徑方式移動(dòng)；

第二組是一個(gè)移動(dòng)信標(biāo)配有GPS定位裝置和一個(gè)定向天線陣列，按照虛擬力的引導(dǎo)進(jìn)行動(dòng)態(tài)路徑規(guī)劃；

第三組有兩個(gè)移動(dòng)信標(biāo)，一個(gè)用第一組中的靜態(tài)路徑移動(dòng)，另一個(gè)用第二組中的動(dòng)態(tài)路徑移動(dòng)，假定信標(biāo)的移動(dòng)速度不變。

實(shí)驗(yàn)條件如下:在100×100的標(biāo)準(zhǔn)矩形區(qū)域內(nèi)，隨機(jī)部署50個(gè)節(jié)點(diǎn)，普通節(jié)點(diǎn)發(fā)射半徑為10，循環(huán)次數(shù)都為15次。這3種方法將在信號(hào)覆蓋率、發(fā)射位置數(shù)量以及移動(dòng)路徑長度方面進(jìn)行比較。

圖3顯示了3組實(shí)驗(yàn)中沒有被覆蓋的節(jié)點(diǎn)數(shù)量比較圖，第一組實(shí)驗(yàn)結(jié)果較好，未得到3個(gè)非共線錨節(jié)點(diǎn)信號(hào)的未知節(jié)點(diǎn)數(shù)量較少。第二組和第三組實(shí)驗(yàn)得到的結(jié)果差別不太大，但第三組得到的信號(hào)未完成覆蓋的節(jié)點(diǎn)數(shù)相對(duì)來說最少。

圖3 信號(hào)未完全覆蓋節(jié)點(diǎn)數(shù)量對(duì)比

圖4 顯示了發(fā)射位置數(shù)量的對(duì)比圖，只要ROI區(qū)域的長度和寬度確定，第一組靜態(tài)路徑實(shí)驗(yàn)的發(fā)射位置數(shù)量就是固定不變的；第三組是第二個(gè)移動(dòng)信標(biāo)的發(fā)射位置數(shù)量圖，相對(duì)來說發(fā)射位置最少，效果最好。

圖4 發(fā)射位置數(shù)量對(duì)比

圖5 是3組實(shí)驗(yàn)中每個(gè)信標(biāo)節(jié)點(diǎn)的移動(dòng)路徑對(duì)比圖，從圖中可知，第一組實(shí)驗(yàn)曲線的走勢(shì)基本上與圖4中的趨勢(shì)一致。第三組實(shí)驗(yàn)也是第二個(gè)移動(dòng)信標(biāo)的路徑長度，所以該信標(biāo)的開銷最小，效果也最好。

4 結(jié)束語

圖5 路徑長度對(duì)比

國內(nèi)外學(xué)者對(duì)DV－Hop算法提出了許多的改進(jìn)，大部分都是以降低三邊測(cè)量或多邊測(cè)量的誤差為出發(fā)點(diǎn)，很少有人關(guān)注將定位誤差和系統(tǒng)開銷結(jié)合起來進(jìn)行分析。本文不僅用群體智能算法對(duì)DV－Hop算法的定位誤差進(jìn)行改進(jìn)，同時(shí)還用新的移動(dòng)信標(biāo)算法降低系統(tǒng)開銷。從實(shí)驗(yàn)結(jié)果可見改進(jìn)的DV－Hop算法提高了節(jié)點(diǎn)的定位精度，取得了較好的定位效果；提出的兩個(gè)移動(dòng)信標(biāo)基于虛擬力的方法，效果比純粹的靜態(tài)路徑或者動(dòng)態(tài)路徑具有更好的穩(wěn)定性、靈活性和信號(hào)覆蓋率，降低了系統(tǒng)開銷。雖然增加的移動(dòng)信標(biāo)增加了少許系統(tǒng)成本，但換來的是系統(tǒng)定位質(zhì)量的較大提高，因此具有一定的應(yīng)用價(jià)值和較好的應(yīng)用前景。

[1]Bartholdy Sanson J，Rodrigues Gomes N，Machado R，et al.Optimization of wireless sensor network using network coding algorithm[C]／／Seville，Spain:The Twelfth International Conference on Networks，2013:21－24.

[2]ZHANG Xinping.A research on localization technique of wireless sensor networks[J].Guangzhou:South China University of Technology，2012（in Chinese）.[張新平.無線傳感器網(wǎng)絡(luò)中的定位技術(shù)及應(yīng)用研究[D].廣州:華南理工大學(xué)，2012.]

[3]JIAO Binliang，ZHANG Ke.Localization algorithm based on stochastic proximity embedding in wireless sensor networks[J].Journal of Chinese Computer Systems，2013，34 （2）:269－271（in Chinese）.[焦斌亮，張可.基于SPE的無線傳感器網(wǎng)絡(luò)定位算法[J].小型微型計(jì)算機(jī)系統(tǒng)，2013，34（2）:269－271.]

[4]Li Wenwen，Zhou Wuneng.Genetic algorithm－base localization algorithm for wireless sensor networks[C]／／Seventh International Conference on Natural computation，2011:2096－2099.

[5]CHEN Xingzhou，LIAO Minghong，LIN Jianhua.Improvement of node localization in wireless sensor network based on particle swarm optimization[J].Journal of Computer Applications，2010，30 （7）:1736－1738（in Chinese）.[陳星舟，廖明宏，林建華.基于粒子群優(yōu)化的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位改進(jìn)[J].計(jì)算機(jī)應(yīng)用，2010，30 （7）:1736－1738.]

[6]Zhao J，F(xiàn)u Y，Wang H B.Localization technology based on quantum－behaved particle swarm optimization algorithm for wireless sensor network[J].Applied Mechanics and Materials，2012，220:1852－1856.

[7]Yu C B，Yu L，Tan J，et al.DV－Hop localization algorithm in wsn based on weighted of correction in hop distance[J].Applied Mechanics and Materials，2013，303:143－148.

[8]Luo X，Liu Y，Long C，et al.Range－free localization algorithms in wireless sensor networks[C]／／Fifth International Conference on Machine Vision Algorithms，Pattern Recognition，and Basic Technologies，2013:42－49.

[9]FU Tao.Study on the hybrid localization algorithm of wireless sensor networks[D].Lanzhou:Lanzhou University，2012（in Chinese）.[傅濤.無線傳感器網(wǎng)絡(luò)混合定位算法研究[D].蘭州:蘭州大學(xué)，2012.]

[10]SUN Jun，WU Xiaojun，F(xiàn)ANG Wei，et al.Quantum－behaved particle swarm optimization:Theory and application[M].Beijing:Tsinghua University Press，2011 （in Chinese）.[孫俊，吳小俊，方偉，等.量子行為粒子群優(yōu)化:原理及其應(yīng)用[M].北京:清華大學(xué)出版社，2011.]

[11]Zhou W，Shi W，Gao P，et al.Localization using a mobile beacon in wireless sensor networks[J].Information Technology Journal，2013 （12）:323－330.

[12]LI Shijian，XU Congfu，YANG Yang，et al.Getting mobile beacon path for sensor localization[J].Journal of Software，2008，19 （2）:455－467（in Chinese）.[李石堅(jiān)，徐從富，楊旸，等.面向傳感器節(jié)點(diǎn)定位的移動(dòng)信標(biāo)路徑獲取[J].軟件學(xué)報(bào)，2008，19 （2）:455－467.]

[13]JIA Qingxuan，ZHANG Qianru，GAO Xin，et al.Dynamic obstacle avoidance algorithm for redundant robots with pre－selected minimum distance index[J].Robot，2013，35 （1）:17－22（in Chinese）.[賈慶軒，張倩茹，高欣，等.預(yù)選擇最小距離指標(biāo)的冗余機(jī)器人動(dòng)態(tài)避障算法[J].機(jī)器人，2013，35 （1）:17－22.]