基于DV-hop定位的誤差加權(quán)改進(jìn)算法

(太原理工大學(xué)信息工程學(xué)院,山西 太原 030024)

0 引言

無線傳感器網(wǎng)絡(luò)(wireless sensor network，WSN)是部署大量低廉的智能傳感器節(jié)點(diǎn)，并以自組織、多跳方式構(gòu)成的無線網(wǎng)絡(luò)系統(tǒng)。在傳感器監(jiān)測區(qū)域內(nèi),傳感器將采集的數(shù)據(jù)進(jìn)行傳輸和處理，實(shí)現(xiàn)對該目標(biāo)區(qū)域的監(jiān)測。無線傳感器網(wǎng)絡(luò)(WSN)具有無線自組織、高容錯(cuò)性、動態(tài)性強(qiáng)的特點(diǎn)，被廣泛應(yīng)用于軍事、環(huán)境監(jiān)測、農(nóng)業(yè)生產(chǎn)、醫(yī)療衛(wèi)生等領(lǐng)域[1-2]。節(jié)點(diǎn)定位是網(wǎng)絡(luò)重構(gòu)、檢測和定位必不可少的研究基礎(chǔ)。

按照是否要測量傳感器節(jié)點(diǎn)之間的距離，現(xiàn)有的傳感器定位算法可分為基于測距算法(range-based)和距離無關(guān)定位算法(range-free)兩類[3]。距離相關(guān)的定位是指網(wǎng)絡(luò)錨節(jié)點(diǎn)具有測量自身到鄰居節(jié)點(diǎn)的距離、信號的角度和強(qiáng)度的能力，然后通過三邊測量法、極大似然估計(jì)法等算法得出未知節(jié)點(diǎn)的坐標(biāo)。傳感器距離定位包括到達(dá)時(shí)間法(time of arrival, TOA)、到達(dá)角度法(angle-of-arrival,AOA)、到達(dá)時(shí)間差法(time difference of arrival,TDOA)和接收信號強(qiáng)度指示法(received signal strength indication,RSSI)等方法。這些方法定位精度較高，但對硬件的要求高。距離無關(guān)的定位是通過節(jié)點(diǎn)間相互網(wǎng)絡(luò)連通度和通信半徑等，利用三邊測量法、極大似然估計(jì)法等算法得出未知節(jié)點(diǎn)的坐標(biāo)。定位方法包括質(zhì)心算法、APIT算法、DV-hop算法[4]等。距離無關(guān)定位算法不需要測量距離或角度的硬件，能耗較低，應(yīng)用前景廣泛。

1 DV-hop算法

1.1 DV-hop算法流程

DV-hop算法是由Niculescu等學(xué)者提出的免于測距的算法，它的算法定位過程分為以下3個(gè)階段。

① 計(jì)算未知節(jié)點(diǎn)與每個(gè)錨節(jié)點(diǎn)的最小跳數(shù)

錨節(jié)點(diǎn)通過向傳感器網(wǎng)絡(luò)的鄰居節(jié)點(diǎn)發(fā)送自身的信息分組，每個(gè)節(jié)點(diǎn)維護(hù)1個(gè)數(shù)據(jù)表{i,(xi,yi),hi}。其中，(xi,yi)為結(jié)點(diǎn)i的二維坐標(biāo)，hi為起始節(jié)點(diǎn)到節(jié)點(diǎn)i的跳數(shù)，初始化時(shí)設(shè)置為0。鄰居節(jié)點(diǎn)收到錨節(jié)點(diǎn)i的數(shù)據(jù)包后，將跳數(shù)hi加1，然后向鄰居節(jié)點(diǎn)廣播該數(shù)據(jù)包。接收節(jié)點(diǎn)保存每個(gè)錨節(jié)點(diǎn)的最小跳數(shù)，對于同一錨節(jié)點(diǎn)的較大的跳數(shù)則釋放。

② 校正值的計(jì)算和廣播

錨節(jié)點(diǎn)i記錄的信息包括其他錨節(jié)點(diǎn)j的坐標(biāo)信息和跳數(shù)信息。所有錨節(jié)點(diǎn)的平均每跳距離Ci的計(jì)算式為：

(1)

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

將錨節(jié)點(diǎn)的平均每跳距離廣播至傳感器網(wǎng)絡(luò)中，未知節(jié)點(diǎn)僅接收第一個(gè)錨節(jié)點(diǎn)的每跳距離，并將其作為自身傳播的每跳距離，則可得出節(jié)點(diǎn)k與錨節(jié)點(diǎn)i的距離為Cik=Cihik。

③ 未知節(jié)點(diǎn)位置的計(jì)算

假設(shè)未知節(jié)點(diǎn)的二維坐標(biāo)為(x,y)，錨節(jié)點(diǎn)i的坐標(biāo)為(xi,yi)，而未知節(jié)點(diǎn)與網(wǎng)絡(luò)錨節(jié)點(diǎn)i的估算距離為di,則可得出以下公式：

(2)

設(shè):

(3)

(4)

(5)

由最小二乘法,可得p=(ATA)-1ATB。

DV-hop算法在實(shí)際應(yīng)用中存在以下不足。

① 算法中的每個(gè)節(jié)點(diǎn)要接收和轉(zhuǎn)發(fā)所有錨節(jié)點(diǎn)的數(shù)據(jù)包結(jié)構(gòu)，這些節(jié)點(diǎn)處于活動狀態(tài)，需要較長時(shí)間等待數(shù)據(jù)包，網(wǎng)絡(luò)中的通信開銷和能量消耗隨之增加。

② 錨節(jié)點(diǎn)所占的比例不同，平均跳段距離也就不同。比例越高，平均跳段距離就越精確。當(dāng)比例增加到一定程度時(shí)，距離保持穩(wěn)定，但費(fèi)用隨之增加。

根據(jù)試驗(yàn)發(fā)現(xiàn)，未知節(jié)點(diǎn)與錨節(jié)點(diǎn)的估算距離影響了節(jié)點(diǎn)的定位精度。當(dāng)未知節(jié)點(diǎn)與錨節(jié)點(diǎn)間距為一跳段時(shí)，測得的距離約為準(zhǔn)確距離的1.2倍。隨著節(jié)點(diǎn)之間間距的增大，估算誤差也隨之增加。因此，使用全部錨節(jié)點(diǎn)反而降低了節(jié)點(diǎn)的定位精度。

1.2 粒子群算法在DV-hop中的應(yīng)用

粒子群算法是對DV-hop算法中三邊測量法或最大似然估計(jì)法的未知節(jié)點(diǎn)坐標(biāo)的誤差進(jìn)行修正和優(yōu)化，是非線性方程求解的有效解決方案。每個(gè)可行解相當(dāng)于粒子群中的一個(gè)粒子，粒子通過個(gè)體最優(yōu)解P和全局最優(yōu)解G，利用式(6)更新下一個(gè)節(jié)點(diǎn)的個(gè)體最優(yōu)解的位置和速度信息數(shù)據(jù)；然后在這個(gè)空間中改變位置和速度，向最優(yōu)解靠攏。

(6)

式中：i為第i個(gè)粒子；t為粒子群的迭代次數(shù)；c1、c2為學(xué)習(xí)因子，以平衡局部搜索和全局搜索能力；xi為粒子i的位置信息。

粒子群初始化時(shí)要設(shè)置粒子位置信息的上下限xmax和xmin、粒子速度信息的上下限vmax和vmin、最大迭代次數(shù)[5-7]。

1.3 典型DV-hop改進(jìn)算法

2 改進(jìn)的DV-hop算法

本文對傳統(tǒng)的DV-hop算法進(jìn)行了適當(dāng)?shù)母倪M(jìn)。改進(jìn)算法主要體現(xiàn)在以下3個(gè)方面：第一階段采用限定數(shù)據(jù)包的廣播范圍；第二階段采用了基于誤差修正加權(quán)和跳距估計(jì)算法；第三階段采用了基于粒子群的定位算法。粒子群算法通過不斷舍棄最遠(yuǎn)節(jié)點(diǎn)而降低算法的復(fù)雜度。

DV-hop算法屬于無需測距的定位算法，硬件要求簡單，但網(wǎng)絡(luò)中錨節(jié)點(diǎn)與未知節(jié)點(diǎn)的排列方式并非成直線排列，所以節(jié)點(diǎn)之間跳數(shù)越多，估算平均每跳距離的誤差越大。改進(jìn)的算法采用在錨節(jié)點(diǎn)向網(wǎng)絡(luò)中廣播的數(shù)據(jù)包結(jié)構(gòu)中增加一個(gè)生存周期數(shù)據(jù)data，所以改進(jìn)算法中的錨節(jié)點(diǎn)數(shù)據(jù)包中包括4個(gè)字段，分別為錨節(jié)點(diǎn)的標(biāo)志i、錨節(jié)點(diǎn)的二維位置坐標(biāo)(xi,yi)、跳數(shù)hi和data數(shù)據(jù)段。data數(shù)據(jù)表示錨節(jié)點(diǎn)能夠傳輸?shù)淖畲髠鞑ヌ鴶?shù)，用于限定錨節(jié)點(diǎn)數(shù)據(jù)包傳輸?shù)淖畲蠓秶６ㄎ凰惴ǜ鶕?jù)錨節(jié)點(diǎn)在無線傳感器網(wǎng)絡(luò)中的比例和網(wǎng)絡(luò)的規(guī)模來設(shè)置不同的data值。

若網(wǎng)絡(luò)中總的錨節(jié)點(diǎn)數(shù)有M個(gè)，則錨節(jié)點(diǎn)i的平均每跳距離誤差值εi為：

(7)

某一錨節(jié)點(diǎn)i的距離誤差值越小，越能準(zhǔn)確地估計(jì)出錨節(jié)點(diǎn)i的平均每跳距離。因此，誤差值越小，權(quán)值應(yīng)該越大。

假設(shè)網(wǎng)絡(luò)中未知節(jié)點(diǎn)收到n個(gè)錨節(jié)點(diǎn)的數(shù)據(jù)報(bào)信息，錨節(jié)點(diǎn)i的平均每跳距離對應(yīng)的加權(quán)值為：

(8)

圖1 改進(jìn)的粒子群優(yōu)化算法流程圖

3 算法仿真及試驗(yàn)分析

為了驗(yàn)證本文所提改進(jìn)算法在應(yīng)用中的有效性和可行性，采用Matlab對本文提出的算法和DV-hop算法進(jìn)行仿真和分析。試驗(yàn)中將仿真節(jié)點(diǎn)隨機(jī)分布在二維平面上，在區(qū)域100 m×100 m 的范圍內(nèi)隨機(jī)布置100個(gè)節(jié)點(diǎn)，仿真次數(shù)為200次。改進(jìn)算法中的生存周期Hmax設(shè)置為6，學(xué)習(xí)因子c1=c2=2，粒子群的最大迭代次數(shù)為20。

平均定位誤差定義為：

(9)

歸一化的節(jié)點(diǎn)定位誤差定義為：

(10)

式中：xi,yi為節(jié)點(diǎn)i的估算距離；x,y為節(jié)點(diǎn)i的實(shí)際距離；R為節(jié)點(diǎn)通信半徑；m為網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)，錨節(jié)點(diǎn)的個(gè)數(shù)按5、10、15、20、25、30、35、40依次增加。

3.1 錨節(jié)點(diǎn)對定位誤差的影響

仿真通過設(shè)置網(wǎng)絡(luò)中不同的錨節(jié)點(diǎn)數(shù)量，采用平均定位誤差對DV-hop算法和本文的算法進(jìn)行比較。本文取網(wǎng)絡(luò)節(jié)點(diǎn)的數(shù)量為100，網(wǎng)絡(luò)節(jié)點(diǎn)通信半徑為20 m。在無線傳感器網(wǎng)絡(luò)中，錨節(jié)點(diǎn)的數(shù)量對節(jié)點(diǎn)的定位精度有一定的影響。當(dāng)節(jié)點(diǎn)間通信半徑R=20 m時(shí)，不同的錨節(jié)點(diǎn)數(shù)量對DV-hop算法和本文算法的定位精度的比較如圖2所示。從圖2可以看出，隨著錨節(jié)點(diǎn)數(shù)的增加，兩種算法中節(jié)點(diǎn)能夠獲取的信息越多，節(jié)點(diǎn)獲得的定位距離信息越精確，定位精度呈現(xiàn)上升的趨勢。

圖2 平均定位誤差曲線

當(dāng)錨節(jié)點(diǎn)數(shù)增加到20時(shí)，本文提出的定位誤差有了明顯的改善；當(dāng)錨節(jié)點(diǎn)數(shù)增加到30時(shí)，本文提出的算法相比于DV-hop算法,定位精度達(dá)到了3.4。從總體上來看，本文提出的算法比傳統(tǒng)的定位算法在定位精度上有了明顯的改善。

3.2 不同通信半徑對本文算法的影響

當(dāng)錨節(jié)點(diǎn)按比例增加時(shí)，在節(jié)點(diǎn)間通信半徑為15 m、20 m、25 m、30 m這4種不同情況下，本文提出的改進(jìn)算法的歸一化定位誤差的比較情況如圖3所示。從圖3可以看出，在4種不同通信半徑下，網(wǎng)絡(luò)的定位精度都隨著網(wǎng)絡(luò)中錨節(jié)點(diǎn)數(shù)的增加而更加精確。當(dāng)錨節(jié)點(diǎn)達(dá)到一定比例時(shí)，定位精度趨于平穩(wěn)。

圖3 歸一化平均定位誤差曲線

4 結(jié)束語

本文分析了DV-hop算法[10-14]的3個(gè)階段，闡述了兩種典型的改進(jìn)算法，提出了基于DV-hop定位的誤差加權(quán)改進(jìn)算法。

通過設(shè)定最大傳輸距離，減小了節(jié)點(diǎn)之間的傳播跳數(shù)，提高了未知節(jié)點(diǎn)的定位精度，降低了網(wǎng)絡(luò)的能耗開銷。同時(shí)對接收到的k個(gè)錨節(jié)點(diǎn)的平均每跳距離誤差加權(quán)和處理，使未知節(jié)點(diǎn)算出的平均每跳距離相比DV-hop更為準(zhǔn)確，改善了無線傳感器網(wǎng)絡(luò)中的定位精度。改進(jìn)的粒子群算法通過適應(yīng)度函數(shù)減小了迭代的粒子數(shù)，縮短了不必要的迭代過程，從而有效改善了定位精度，減少了無線傳感器網(wǎng)絡(luò)定位的計(jì)算復(fù)雜度和計(jì)算時(shí)間，降低了定位誤差。仿真試驗(yàn)驗(yàn)證了本文提出的DV-hop定位改進(jìn)算法的可行性。

[1] He T,Huang C D,Blum B M,et al.Range-free localization schemes in large scale sensor networks[C]//Proceedings of the 9th Annual International Conference on Mobile Computing and Networking.New York:ACM Press,2003:70-95.

[2] Cenedese A,Ortolan G,Bertinato M.Low-density wireless sensor networks for localization and tracking in critical environments[J].IEEE Transactions on Vehicular Technology,2010,59(6):2951-2962.

[3] 于弘毅，李鷗，張效義.無線傳感器網(wǎng)絡(luò)理論、技術(shù)與實(shí)現(xiàn)[M].北京：國防工業(yè)出版社,2008:143.

[4] Liu W Y,Wang E S,Chen Z J,et al.An improved DV-Hop localization algorithm based on selection of beacon nodes[J].Journal of Convergence Information Technology,2010,5(9):157-164.

[5] Kulkarni R V,Venayagamoorthy G k.Particle swarm optimization in wireless sensor networks:a brief survey[J].IEEE Transaction on Systems Man and Cybernetics,2011,41(2):262-267.

[6] Low K S,Nguyen H A,Guo H.A particle swarm optimization approach for the localization of a wireless sensor networks[C]//Proceedings of IEEE International Symposium on Industrial Electronic,2008:1820-1825.

[7] 黃艷，臧傳治，于海斌.基于改進(jìn)粒子群優(yōu)化的無線傳感器網(wǎng)絡(luò)定位算法[J].控制與決策，2012,27(1)：156-160.

[8] 朱紅松，孫利民.無線傳感器網(wǎng)絡(luò)技術(shù)發(fā)展現(xiàn)狀[J].中興通訊技術(shù)，2009,15(8):35-38.

[9] 肖美華，周之平.無線傳感器節(jié)點(diǎn)加權(quán)平均跳距定位算法[J].計(jì)算機(jī)工程與設(shè)計(jì)，2010,31(1)：78-81.

[10]劉凱，余君君，譚力雄.跳數(shù)加權(quán)DV-Hop定位算法[J].傳感技術(shù)學(xué)報(bào)，2012,25(11):1539-1542.

[11]趙林鎧,洪志全.基于無線傳感器網(wǎng)絡(luò)的DV-Hop定位算法的改進(jìn)[J].計(jì)算機(jī)應(yīng)用，2011,31(5):1189-1192.

[12]張愛平,賴欣.在JSP中調(diào)用JavaBean實(shí)現(xiàn)Web數(shù)據(jù)庫訪問[J].計(jì)算機(jī)時(shí)代,2007(1):15-18.

[13]仲偉和.基于JSP網(wǎng)頁自動生成工具的設(shè)計(jì)與實(shí)現(xiàn)[J].科技信息,2007(15):21-23.

[14]Lin C R, Gerla M.Adaptive clustering for mobile wireless networks[J].IEEE Journal on Selected Areas Communications, 1997,15 (7) :1265-1275.