基于改進DV-Hop 的水質WSN 節點定位算法研究

陳柄全，郭星鋒，黃元峰，楊明潤

（武漢工程大學 電氣信息學院，湖北 武漢 430205）

0 引言

隨著現代工業化的高速發展，各種化工廠的污水處理不當使得水環境污染問題日益嚴重，因此有必要對相關水域進行水質節點檢測后定位，以便水環保工作者對具體污染源位置進行精確處理[1]。無線傳感器網絡水質檢測系統由分布在水質檢測區域的大量水質檢測節點通過無線網絡方式連接到PC端而組成，由于多數水質檢測節點不具有GPS 定位功能，因此水質檢測節點采集到的數據信息不包含自身位置信息[2]。如果水質傳感器節點采集到了大量的水質數據卻不能將自身的位置信息傳送給相關工作人員，那么水質檢測后的數據信息將變得毫無意義。基于此，研究水質無線傳感器節點定位具有一定的實際應用價值。

通過大量的文獻閱讀，結合無線傳感器網絡水質檢測系統的實際應用環境，發現非測距定位算法中的DV-Hop 節點定位算法更適合應用在大面積的水質檢測場景[3]。傳統DV-Hop 算法復雜度低且易實現，但存在平均跳距計算誤差和最小二乘法計算節點坐標誤差等問題。針對傳統DV-Hop 算法存在的問題，相關研究工作者提出了很多改進的方式。例如：SHI 等人[4]提出了一種路徑匹配算法來尋找最優錨點-錨點最短路徑；SHI 等人[5]采用改進的余弦相似度參數來度量路徑對之間的相似度；程等人[6]提出了基于誤差與距離的權值處理錨節點間的平均單位跳距，然后利用遺傳算法取代最小二乘法輸出未知節點坐標；LI 等人[7]提出了一種新的啟發式算法并行緊湊型優化算法；石等人[8]、孫等人[9]則引進了灰狼算法對DV-Hop 進行改進。但是，以上改進算法仍存在定位精度不足、通信開銷變大、算法復雜度增大等問題。針對上述問題，本文將DV-Hop 節點定位算法作為基本算法并進行改進，以提高水質檢測節點的定位精度。

1 DV-Hop 算法概述

傳統DV-Hop 節點定位算法由NICULESCU 等人[10]提出，算法原理分析如下。通過廣播搜集每個節點的最小跳數信息并保存，計算任意信標節點i的平均跳距Hi：

式中：hij表示信標節點i與j的最小跳數。

利用式（1）計算出的結果，即可求解任意未知節點u與信標節點j之間的距離，即：

計算出距離后，即可估算未知節點坐標。

傳統DV-Hop 節點定位誤差的來源主要有兩個方面，分別是計算平均跳距帶來的誤差和最小二乘法計算節點坐標時產生的誤差[11]。本文針對DV-Hop這兩個誤差進行改進，以提高其定位精度。

2 基于灰狼算法改進的DV-Hop 水質WSN 節點定位算法

通過對DV-Hop 的誤差分析，本文根據數學原理推導出修正任意節點的修正因子通式，利用平均跳距修正因子修正傳統DV-Hop 中的平均跳距值。此外，引入改進的灰狼算法對傳統DV-Hop 算法估計出的未知節點初始坐標進行優化。改進算法流程如圖1 所示。

圖1 基于灰狼算法改進的DV-Hop 定位算法流程

由于無線傳感器網絡節點定位中存在節點分布不均勻的問題，因此會產生計算誤差。一般規定節點之間的最小跳數為單位跳數，如果存在節點隨機分布不均勻的情況，就會造成平均跳距計算誤差。根據式（1）可知，計算平均跳距時需要用到跳數。如果兩個節點之間的跳數在單位跳數范圍內，則計算平均跳距時視兩節點的跳數為1，然而實際情況是小于1 跳，從而導致平均跳距計算誤差。通過上述問題描述，可假設信標節點a和b的坐標分別為(ax,ay)和(bx,by)，則a和b之間的距離為：

式中：hab表示節點a和b之間的跳數。

a和b之間的實際距離為：

利用式（3）和式（4）可以推出信標節點a和b之間實際距離與計算距離的偏差為：

根據式（3），（4），（5）推出本文所提出的平均跳距修正因子為：

利用定義的修正因子ci即可推導出修正距離和修正后跳數hit的關系為：

將灰狼算法與DV-Hop 相結合，首先需要將后者的輸出信息轉變為前者的輸入信息，其次通過灰狼算法進行自身內部迭代尋優，最后輸出最優未知節點坐標。通過分析灰狼算法的原理，將未知節點信息比作獵物坐標信息，這樣就可以利用灰狼算法搜索出獵物的坐標，滿足一定條件后作為未知節點坐標輸出。

利用排序函數將DV-Hop 運算出的未知節點與信標節點的距離進行升序排序并保存，然后選出距離最小的5 個進行保存，同時記錄其序號。初始化灰狼個體，設灰狼個體的位置坐標為(x,y)，將保存的5 個最小距離記為{d1,d2,d3,d4,d5}。將最近5 個信標節點坐標{(x1,y1),(x2,y2),(x3,y3),(x4,y4),(x5,y5)}作為灰狼算法中適應度函數的輸入信息，計算適應度函數值并比較每次循環后的適應度值，找出最小的值保存，通過灰狼算法內部循環迭代找出最佳的狼的位置。當達到算法迭代條件時，輸出適應度值對應的灰狼個體坐標作為未知節點坐標輸出，否則繼續下一步。其中，適應度函數為：

計算所有個體的適應度值后，從中選出新的狼群個體位置信息作為初始值重新迭代尋優。利用算法迭代完成后，即可將最優個體狼的位置信息作為未知節點的坐標輸出。

3 仿真實驗

仿真軟件為Matlab 2016b，通過分別改變水質檢測信標節點數、水質檢測節點數以及水質檢測節點之間的通信半徑大小，對比本文所提算法與傳統DV-Hop 算法、黃等人[12]所提基于粒子群算法改進的DV-Hop 算法、易等人[13]所提基于加權雙曲線改進的DV-Hop 算法（Improved DV-Hop location algorithm based on weighted hyperbola，WH-DVHop）的定位精度。首先在Matlab 上編寫4 種對比算法的程序并作為Function 函數，其次編寫主函數，最后利用主函數調用4 個算法編寫的Function 函數得出最終的節點定位仿真對比結果。

在Matlab 上模擬水質節點分布區域，隨機生成N個水質傳感器未知節點(xi,yi)和m個已知坐標信息的水質傳感器節點，所有水質傳感器節點通信半徑均設置為R。假設未知節點的估計坐標為對水質節點定位精度進行歸一化處理：

為了驗證水質傳感器信標節點數量對節點定位算法的定位精度影響，控制水質傳感器節點數量和水質傳感器節點之間的通信半徑大小不變。設置水質傳感器節點數為100 個、水質傳感器之間的通信半徑為15 m，通過改變信標節點數來仿真對比不同節點定位算法的定位精度，結果如圖2 所示。

圖2 水質傳感器信標節點數對定位性能的影響

為了驗證水質傳感器節點數量對節點定位的影響，控制水質傳感器信標節點數和水質傳感器節點之間的通信半徑不變。設置水質傳感器信標節點數為15 個、水質傳感器之間的通信半徑為15 m，通過改變水質傳感器節點數量來仿真對比本文算法和其他3 種算法的定位精度，結果如圖3 所示。

圖3 水質傳感器節點數對定位性能的影響

為了驗證水質傳感器節點之間的通信半徑大小對不同節點定位算法的定位精度影響，控制水質傳感器信標節點數和水質傳感器節點數不變。設置水質傳感器信標節點數為15 個、水質傳感器節點數為100 個，通過改變水質傳感器之間的通信半徑大小來進行仿真對比實驗，結果如圖4 所示。

圖4 通信半徑對定位性能的影響

綜合分析上述仿真結果，任意改變一個變量時，本文所提算法的定位精度都比另外3 種算法高，性能較優，具有一定的可行性。

4 結語

本文基于DV-Hop 的兩個誤差來源分析，提出基于灰狼算法改進的DV-Hop 水質檢測節點定位算法。實驗結果表明，該改進方法能很好地提高水質檢測節點的定位精度。由于引入了平均跳距修正系數，在一定程度上增加了算法的計算時間，因此后期將繼續深入研究如何降低算法計算時間。