基于改進(jìn)DV-Hop 的水質(zhì)WSN 節(jié)點(diǎn)定位算法研究

陳柄全，郭星鋒，黃元峰，楊明潤(rùn)

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

0 引言

隨著現(xiàn)代工業(yè)化的高速發(fā)展，各種化工廠的污水處理不當(dāng)使得水環(huán)境污染問(wèn)題日益嚴(yán)重，因此有必要對(duì)相關(guān)水域進(jìn)行水質(zhì)節(jié)點(diǎn)檢測(cè)后定位，以便水環(huán)保工作者對(duì)具體污染源位置進(jìn)行精確處理[1]。無(wú)線傳感器網(wǎng)絡(luò)水質(zhì)檢測(cè)系統(tǒng)由分布在水質(zhì)檢測(cè)區(qū)域的大量水質(zhì)檢測(cè)節(jié)點(diǎn)通過(guò)無(wú)線網(wǎng)絡(luò)方式連接到PC端而組成，由于多數(shù)水質(zhì)檢測(cè)節(jié)點(diǎn)不具有GPS 定位功能，因此水質(zhì)檢測(cè)節(jié)點(diǎn)采集到的數(shù)據(jù)信息不包含自身位置信息[2]。如果水質(zhì)傳感器節(jié)點(diǎn)采集到了大量的水質(zhì)數(shù)據(jù)卻不能將自身的位置信息傳送給相關(guān)工作人員，那么水質(zhì)檢測(cè)后的數(shù)據(jù)信息將變得毫無(wú)意義?；诖?，研究水質(zhì)無(wú)線傳感器節(jié)點(diǎn)定位具有一定的實(shí)際應(yīng)用價(jià)值。

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

1 DV-Hop 算法概述

傳統(tǒng)DV-Hop 節(jié)點(diǎn)定位算法由NICULESCU 等人[10]提出，算法原理分析如下。通過(guò)廣播搜集每個(gè)節(jié)點(diǎn)的最小跳數(shù)信息并保存，計(jì)算任意信標(biāo)節(jié)點(diǎn)i的平均跳距Hi：

式中：hij表示信標(biāo)節(jié)點(diǎn)i與j的最小跳數(shù)。

利用式（1）計(jì)算出的結(jié)果，即可求解任意未知節(jié)點(diǎn)u與信標(biāo)節(jié)點(diǎn)j之間的距離，即：

計(jì)算出距離后，即可估算未知節(jié)點(diǎn)坐標(biāo)。

傳統(tǒng)DV-Hop 節(jié)點(diǎn)定位誤差的來(lái)源主要有兩個(gè)方面，分別是計(jì)算平均跳距帶來(lái)的誤差和最小二乘法計(jì)算節(jié)點(diǎn)坐標(biāo)時(shí)產(chǎn)生的誤差[11]。本文針對(duì)DV-Hop這兩個(gè)誤差進(jìn)行改進(jìn)，以提高其定位精度。

2 基于灰狼算法改進(jìn)的DV-Hop 水質(zhì)WSN 節(jié)點(diǎn)定位算法

通過(guò)對(duì)DV-Hop 的誤差分析，本文根據(jù)數(shù)學(xué)原理推導(dǎo)出修正任意節(jié)點(diǎn)的修正因子通式，利用平均跳距修正因子修正傳統(tǒng)DV-Hop 中的平均跳距值。此外，引入改進(jìn)的灰狼算法對(duì)傳統(tǒng)DV-Hop 算法估計(jì)出的未知節(jié)點(diǎn)初始坐標(biāo)進(jìn)行優(yōu)化。改進(jìn)算法流程如圖1 所示。

圖1 基于灰狼算法改進(jìn)的DV-Hop 定位算法流程

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

式中：hab表示節(jié)點(diǎn)a和b之間的跳數(shù)。

a和b之間的實(shí)際距離為：

利用式（3）和式（4）可以推出信標(biāo)節(jié)點(diǎn)a和b之間實(shí)際距離與計(jì)算距離的偏差為：

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

利用定義的修正因子ci即可推導(dǎo)出修正距離和修正后跳數(shù)hit的關(guān)系為：

將灰狼算法與DV-Hop 相結(jié)合，首先需要將后者的輸出信息轉(zhuǎn)變?yōu)榍罢叩妮斎胄畔?，其次通過(guò)灰狼算法進(jìn)行自身內(nèi)部迭代尋優(yōu)，最后輸出最優(yōu)未知節(jié)點(diǎn)坐標(biāo)。通過(guò)分析灰狼算法的原理，將未知節(jié)點(diǎn)信息比作獵物坐標(biāo)信息，這樣就可以利用灰狼算法搜索出獵物的坐標(biāo)，滿足一定條件后作為未知節(jié)點(diǎn)坐標(biāo)輸出。

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

計(jì)算所有個(gè)體的適應(yīng)度值后，從中選出新的狼群個(gè)體位置信息作為初始值重新迭代尋優(yōu)。利用算法迭代完成后，即可將最優(yōu)個(gè)體狼的位置信息作為未知節(jié)點(diǎn)的坐標(biāo)輸出。

3 仿真實(shí)驗(yàn)

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

在Matlab 上模擬水質(zhì)節(jié)點(diǎn)分布區(qū)域，隨機(jī)生成N個(gè)水質(zhì)傳感器未知節(jié)點(diǎn)(xi,yi)和m個(gè)已知坐標(biāo)信息的水質(zhì)傳感器節(jié)點(diǎn)，所有水質(zhì)傳感器節(jié)點(diǎn)通信半徑均設(shè)置為R。假設(shè)未知節(jié)點(diǎn)的估計(jì)坐標(biāo)為對(duì)水質(zhì)節(jié)點(diǎn)定位精度進(jìn)行歸一化處理：

為了驗(yàn)證水質(zhì)傳感器信標(biāo)節(jié)點(diǎn)數(shù)量對(duì)節(jié)點(diǎn)定位算法的定位精度影響，控制水質(zhì)傳感器節(jié)點(diǎn)數(shù)量和水質(zhì)傳感器節(jié)點(diǎn)之間的通信半徑大小不變。設(shè)置水質(zhì)傳感器節(jié)點(diǎn)數(shù)為100 個(gè)、水質(zhì)傳感器之間的通信半徑為15 m，通過(guò)改變信標(biāo)節(jié)點(diǎn)數(shù)來(lái)仿真對(duì)比不同節(jié)點(diǎn)定位算法的定位精度，結(jié)果如圖2 所示。

圖2 水質(zhì)傳感器信標(biāo)節(jié)點(diǎn)數(shù)對(duì)定位性能的影響

為了驗(yàn)證水質(zhì)傳感器節(jié)點(diǎn)數(shù)量對(duì)節(jié)點(diǎn)定位的影響，控制水質(zhì)傳感器信標(biāo)節(jié)點(diǎn)數(shù)和水質(zhì)傳感器節(jié)點(diǎn)之間的通信半徑不變。設(shè)置水質(zhì)傳感器信標(biāo)節(jié)點(diǎn)數(shù)為15 個(gè)、水質(zhì)傳感器之間的通信半徑為15 m，通過(guò)改變水質(zhì)傳感器節(jié)點(diǎn)數(shù)量來(lái)仿真對(duì)比本文算法和其他3 種算法的定位精度，結(jié)果如圖3 所示。

圖3 水質(zhì)傳感器節(jié)點(diǎn)數(shù)對(duì)定位性能的影響

為了驗(yàn)證水質(zhì)傳感器節(jié)點(diǎn)之間的通信半徑大小對(duì)不同節(jié)點(diǎn)定位算法的定位精度影響，控制水質(zhì)傳感器信標(biāo)節(jié)點(diǎn)數(shù)和水質(zhì)傳感器節(jié)點(diǎn)數(shù)不變。設(shè)置水質(zhì)傳感器信標(biāo)節(jié)點(diǎn)數(shù)為15 個(gè)、水質(zhì)傳感器節(jié)點(diǎn)數(shù)為100 個(gè)，通過(guò)改變水質(zhì)傳感器之間的通信半徑大小來(lái)進(jìn)行仿真對(duì)比實(shí)驗(yàn)，結(jié)果如圖4 所示。

圖4 通信半徑對(duì)定位性能的影響

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

4 結(jié)語(yǔ)

本文基于DV-Hop 的兩個(gè)誤差來(lái)源分析，提出基于灰狼算法改進(jìn)的DV-Hop 水質(zhì)檢測(cè)節(jié)點(diǎn)定位算法。實(shí)驗(yàn)結(jié)果表明，該改進(jìn)方法能很好地提高水質(zhì)檢測(cè)節(jié)點(diǎn)的定位精度。由于引入了平均跳距修正系數(shù)，在一定程度上增加了算法的計(jì)算時(shí)間，因此后期將繼續(xù)深入研究如何降低算法計(jì)算時(shí)間。