基于DV-HOP無線傳感器的網絡節點定位算法

文/胡鵬莎

1 引言

1.1 無線傳感器網絡概述

無線傳感器網絡的全稱為Wireless Sensor Network，其能夠通過目標區域內分布的許多非常小的傳感器節點實現研究對象相關信息的感知、采集和處理，這一過程需要得到無線電通信的多跳自組織網絡支持，而由于無線傳感器體積較小、重量較輕，其也被稱為“智能塵?！?，使用者只需要將其散落在目標區域內，無線傳感器便能夠實時感知物理世界發生的變化?？偟膩碚f，無線傳感器網絡具備密度高、規模大、動態性強、微型化、小型化、成本低、通信能力有限、計算和存儲能力有限等特點，這使得其在我國軍事、醫療、農業、智能家居等領域具備較高應用潛力。

表1：人工魚群參數初始值

表2：無線傳感器網絡參數值

1.2 無線傳感器網絡節點定位技術研究

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

圖1：人工魚群算法流程

圖2：改進后的人工魚群算法流程

圖3：通信半徑20m（左）、25m（右）的網絡拓撲圖

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

1.3 經典無線傳感器網絡定位算法

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

1.4 定位算法性能的評價標準

對于無線傳感器網絡定位算法來說，評價標準主要包括定位精度、節點密度、錨節點密度、覆蓋率、代價，定位精度使用定位誤差和通信半徑表示。假設節點通信半徑R為50m、算法的計算誤差為10m，定位精度為0.2，單個節點、整體平均定位誤差的計算公式如式（1）、式（2）所示，式（1）中的rest、rreal、R分別為測量的位置、實際的位置、通信半徑，式（2）中的n、m、分別為節點全部個數、錨節點全部個數、第i個節點測量位置、第i個節點實際位置。

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

2.1 人工魚群算法

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

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

本文開展的DV-HOP定位算法改進研究首先改進了原始算法的三個定位步驟，通過修正最小跳數、未知節點優先節點定位、改進平均跳距，即可將DV-HOP定位算法從解定位問題轉化為優化問題，而為了保證人工魚群算法較好服務于未知節點坐標的求解，必須對該算法進行改進，改進主要圍繞人工魚分段尋優、動態修改參數值、改進覓食行為展開，具體改進內容如下：

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

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

（3）覓食行為改進。為防止個體最優解退化，采用最優個體保留機制改進覓食行為，以極小值為例，任意選擇某一個地方Xn（視距Visual范圍內），如目標函數Yn

2.2.1 改進的算法原理

改進后的人工魚群算法流程如圖2所示，該流程涉及的距離方程、目標函數如下：

2.2.2 改進的算法流程

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

3 仿真結果與分析

3.1 仿真參數設置

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

3.2 仿真結果及分析

圖3為通信半徑20m、25m的網絡拓撲圖，圖4為通信半徑20m、25m仿真波形，圖5為通信半徑30m、35m的網絡拓撲圖，圖6為通信半徑30m、35m仿真波形，圖7為不同通信半徑仿真波形，由此可直觀發現改進后算法可有效減少對錨節點數目的依賴，并能夠有效減小定位誤差，定位的成本也因此大大下降。

圖5：通信半徑30m（左）、35m（右）的網絡拓撲圖

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

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

圖8：改進算法與DV-Hop算法單個節點誤差比照圖

圖8為改進算法與DV-Hop算法單個節點誤差比照圖，由此可更直觀了解改進算法具備的較高實用價值。

4 結論

綜上所述，基于人工魚群算法的DV-HOP定位算法可較好服務于無線傳感器網絡節點定位，本文求得的仿真結果也能夠證明這一認知，而為了更好推動無線傳感器網絡節點定位算法發展，本文研究的算法的實際應用驗證將成為筆者的下一步研究方向。