基于DV-HOP無線傳感器的網(wǎng)絡(luò)節(jié)點(diǎn)定位算法

文/胡鵬莎

1 引言

1.1 無線傳感器網(wǎng)絡(luò)概述

無線傳感器網(wǎng)絡(luò)的全稱為Wireless Sensor Network，其能夠通過目標(biāo)區(qū)域內(nèi)分布的許多非常小的傳感器節(jié)點(diǎn)實(shí)現(xiàn)研究對象相關(guān)信息的感知、采集和處理，這一過程需要得到無線電通信的多跳自組織網(wǎng)絡(luò)支持，而由于無線傳感器體積較小、重量較輕，其也被稱為“智能塵埃”，使用者只需要將其散落在目標(biāo)區(qū)域內(nèi)，無線傳感器便能夠?qū)崟r(shí)感知物理世界發(fā)生的變化。總的來說，無線傳感器網(wǎng)絡(luò)具備密度高、規(guī)模大、動(dòng)態(tài)性強(qiáng)、微型化、小型化、成本低、通信能力有限、計(jì)算和存儲能力有限等特點(diǎn)，這使得其在我國軍事、醫(yī)療、農(nóng)業(yè)、智能家居等領(lǐng)域具備較高應(yīng)用潛力。

表1：人工魚群參數(shù)初始值

表2：無線傳感器網(wǎng)絡(luò)參數(shù)值

1.2 無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位技術(shù)研究

無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位涉及一系列專業(yè)術(shù)語，如信標(biāo)節(jié)點(diǎn)、鄰居節(jié)點(diǎn)、未知節(jié)點(diǎn)、跳數(shù)、連通度、到達(dá)時(shí)間、到達(dá)時(shí)間差、到達(dá)角度、接收信號強(qiáng)度、視線關(guān)系、非視線關(guān)系，跳數(shù)統(tǒng)計(jì)原理、鄰近關(guān)系原理則屬于該技術(shù)涉及的基本原理。長期以來國內(nèi)外學(xué)界均圍繞無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位技術(shù)開展了大量研究，2000年Nimpama Bulusu教授等人提出的質(zhì)心算法、Tian He在2003年提出的APIT算法、馬震在2008年提出的MDS-MAP算法、蘆捷飛在2015年提出的RSSI與DV-Hop結(jié)合算法均屬于其中代表，如何保證無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位技術(shù)更好為人們服務(wù)屬于相關(guān)研究的最終目的。

圖1：人工魚群算法流程

圖2：改進(jìn)后的人工魚群算法流程

圖3：通信半徑20m（左）、25m（右）的網(wǎng)絡(luò)拓?fù)鋱D

圖4：通信半徑20m（左）、25m（右）仿真波形

1.3 經(jīng)典無線傳感器網(wǎng)絡(luò)定位算法

經(jīng)典的無線傳感器網(wǎng)絡(luò)定位算法可細(xì)分為兩類，這種劃分以測距和非測距為依據(jù)，基于測距的定位算法主要包括RSSI定位算法、TOA定位算法、TDOA定位算法、AOA定位算法，基于非測距的定位算法則主要有質(zhì)心定位算法、APIT算法、凸規(guī)劃算法、以及本文研究的DV-Hop算法。DV-Hop算法的定位需要通過已經(jīng)確定自身位置的節(jié)點(diǎn)與無法確定自身位置的節(jié)點(diǎn)建立通信聯(lián)系實(shí)現(xiàn)，根據(jù)泛洪通信方式，算法需要結(jié)合網(wǎng)絡(luò)中錨節(jié)點(diǎn)之間距離估算每跳平均跳距、以及節(jié)點(diǎn)獲得的與錨節(jié)點(diǎn)之間最小跳數(shù)，與錨節(jié)點(diǎn)之間的距離可通過平均跳距乘以最小跳數(shù)求得，坐標(biāo)的計(jì)算則需要使用極大似然值法或三邊定位法，這使得其具備成本低廉、應(yīng)用廣泛特點(diǎn)。

1.4 定位算法性能的評價(jià)標(biāo)準(zhǔn)

對于無線傳感器網(wǎng)絡(luò)定位算法來說，評價(jià)標(biāo)準(zhǔn)主要包括定位精度、節(jié)點(diǎn)密度、錨節(jié)點(diǎn)密度、覆蓋率、代價(jià)，定位精度使用定位誤差和通信半徑表示。假設(shè)節(jié)點(diǎn)通信半徑R為50m、算法的計(jì)算誤差為10m，定位精度為0.2，單個(gè)節(jié)點(diǎn)、整體平均定位誤差的計(jì)算公式如式（1）、式（2）所示，式（1）中的rest、rreal、R分別為測量的位置、實(shí)際的位置、通信半徑，式（2）中的n、m、分別為節(jié)點(diǎn)全部個(gè)數(shù)、錨節(jié)點(diǎn)全部個(gè)數(shù)、第i個(gè)節(jié)點(diǎn)測量位置、第i個(gè)節(jié)點(diǎn)實(shí)際位置。

2 基于人工魚群算法的DV-HOP定位算法

2.1 人工魚群算法

人工魚群算法由我國學(xué)者李曉磊等人提出 于 2002年，全稱為 Artifical Fish Swarm Algorithm，屬于一種基于動(dòng)物行為的群體智能優(yōu)化算法，一般情況下水域內(nèi)的魚聚集在食物含量高的地方屬于該算法的基本理念，而通過模仿魚群的特點(diǎn)，人工云群算法得以具備較高的魯棒性，且擁有較強(qiáng)的自適應(yīng)能力、善于突破局部最優(yōu)解（實(shí)現(xiàn)全局最優(yōu)解），人工魚群算法的流程如圖1所示，該算法涉及的變量包括N、Xi、Yi、dik、Step、delta、Visual、TryNum、gen、Maxgen，分別代表人工魚群中人工魚總數(shù)量、第i條人工魚位置、第i條魚所處食物濃度、第k條與第i條魚距離、人工魚游動(dòng)步長最大值、水域擁擠度、人工魚目視距離最大值、搜尋食物嘗試次數(shù)最大值、算法迭代次數(shù)、算法迭代最大值。

2.2 基于人工魚群算法的DV-HOP定位算法

本文開展的DV-HOP定位算法改進(jìn)研究首先改進(jìn)了原始算法的三個(gè)定位步驟，通過修正最小跳數(shù)、未知節(jié)點(diǎn)優(yōu)先節(jié)點(diǎn)定位、改進(jìn)平均跳距，即可將DV-HOP定位算法從解定位問題轉(zhuǎn)化為優(yōu)化問題，而為了保證人工魚群算法較好服務(wù)于未知節(jié)點(diǎn)坐標(biāo)的求解，必須對該算法進(jìn)行改進(jìn)，改進(jìn)主要圍繞人工魚分段尋優(yōu)、動(dòng)態(tài)修改參數(shù)值、改進(jìn)覓食行為展開，具體改進(jìn)內(nèi)容如下：

（1）人工魚分段尋優(yōu)。為提高算法的收斂速度，需要設(shè)法淘汰始終在食物濃度較低地方搜尋的人工魚，設(shè)算法前期迭代次數(shù)為k且 k<ɑMaxgen，而當(dāng) k>ɑMaxgen后，則需要在每次迭代過程中淘汰一條人工魚，直到k=Maxgen，即可確定最優(yōu)結(jié)果。

（2）動(dòng)態(tài)修改參數(shù)值。如Visual值較大，人工魚視野較廣且具備全局搜索能力，同時(shí)隨機(jī)行為和覓食較為頻繁，如Step值較大，人工魚則因視野參數(shù)小具備較強(qiáng)的局部搜索能力，同時(shí)存在追尾頻繁特點(diǎn)。因此，算法前期應(yīng)保證Visual、Step值較大，并隨著尋優(yōu)的進(jìn)行不斷縮小Visual、Step，因此二者參數(shù)需動(dòng)態(tài)設(shè)定為式（3）、（4），式中的ɑ、β為常數(shù)（均取1/2），Visual0、Step0分別為賦予視野、步長的初值。

（3）覓食行為改進(jìn)。為防止個(gè)體最優(yōu)解退化，采用最優(yōu)個(gè)體保留機(jī)制改進(jìn)覓食行為，以極小值為例，任意選擇某一個(gè)地方Xn（視距Visual范圍內(nèi)），如目標(biāo)函數(shù)Yn

2.2.1 改進(jìn)的算法原理

改進(jìn)后的人工魚群算法流程如圖2所示，該流程涉及的距離方程、目標(biāo)函數(shù)如下：

2.2.2 改進(jìn)的算法流程

基于人工魚群算法的DV-HOP定位算法流程可概括為：“開始→錨節(jié)點(diǎn)分別以R、2R/3、R/3向網(wǎng)絡(luò)中廣播信息→錨節(jié)點(diǎn)周圍鄰居節(jié)點(diǎn)接收信息→保留最小跳數(shù)，R廣播完畢后，接收節(jié)點(diǎn)轉(zhuǎn)發(fā)→未知節(jié)點(diǎn)滿足優(yōu)先定位→估算錨節(jié)點(diǎn)與未直接點(diǎn)距離→定位滿足條件的未知節(jié)點(diǎn)→優(yōu)先定位的未知節(jié)點(diǎn)升級為錨節(jié)點(diǎn)→錨節(jié)點(diǎn)向網(wǎng)絡(luò)廣播信息→其他未知節(jié)點(diǎn)接收廣播信息→接收過錨節(jié)點(diǎn)信息→比較并保存最小跳數(shù)信息→廣播結(jié)束→未知節(jié)點(diǎn)收到三個(gè)或以上錨節(jié)點(diǎn)信息→錨節(jié)點(diǎn)計(jì)算與其他錨節(jié)點(diǎn)距離→錨節(jié)點(diǎn)估算平均跳距及誤差→未知節(jié)點(diǎn)加權(quán)處理接收到的各錨節(jié)點(diǎn)平均跳距→未知節(jié)點(diǎn)估算自己數(shù)據(jù)分組中各錨節(jié)點(diǎn)距離→使用改進(jìn)人工魚群算法計(jì)算未知節(jié)點(diǎn)坐標(biāo)→結(jié)束”，改進(jìn)人工魚群算法的應(yīng)用可有效優(yōu)化未知節(jié)點(diǎn)的位置。

3 仿真結(jié)果與分析

3.1 仿真參數(shù)設(shè)置

使用Matlab2014a軟件、經(jīng)典DV-Hop算法、改進(jìn)后算法開展仿真，人工魚群參數(shù)的初始值如表1所示，無線傳感器網(wǎng)絡(luò)參數(shù)值如表2所示，其中δ為擁擠度初值，采用歸一化平均定位誤差。

3.2 仿真結(jié)果及分析

圖3為通信半徑20m、25m的網(wǎng)絡(luò)拓?fù)鋱D，圖4為通信半徑20m、25m仿真波形，圖5為通信半徑30m、35m的網(wǎng)絡(luò)拓?fù)鋱D，圖6為通信半徑30m、35m仿真波形，圖7為不同通信半徑仿真波形，由此可直觀發(fā)現(xiàn)改進(jìn)后算法可有效減少對錨節(jié)點(diǎn)數(shù)目的依賴，并能夠有效減小定位誤差，定位的成本也因此大大下降。

圖5：通信半徑30m（左）、35m（右）的網(wǎng)絡(luò)拓?fù)鋱D

圖6：通信半徑30m（左）、35m（右）仿真波形

圖7：不同通信半徑仿真波形

圖8：改進(jìn)算法與DV-Hop算法單個(gè)節(jié)點(diǎn)誤差比照圖

圖8為改進(jìn)算法與DV-Hop算法單個(gè)節(jié)點(diǎn)誤差比照圖，由此可更直觀了解改進(jìn)算法具備的較高實(shí)用價(jià)值。

4 結(jié)論

綜上所述，基于人工魚群算法的DV-HOP定位算法可較好服務(wù)于無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位，本文求得的仿真結(jié)果也能夠證明這一認(rèn)知，而為了更好推動(dòng)無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法發(fā)展，本文研究的算法的實(shí)際應(yīng)用驗(yàn)證將成為筆者的下一步研究方向。