王 磊，劉晶晶，齊俊艷，賀軍義

(河南理工大學計算機科學與技術(shù)學院，河南焦作 454000)

0 引言

無線傳感器網(wǎng)絡(luò)(wireless sensor network，WSN)是由大量節(jié)點組成的自組織網(wǎng)絡(luò)，通過相互協(xié)作，節(jié)點可以實現(xiàn)對指定監(jiān)控區(qū)域?qū)ο蟮臄?shù)據(jù)感知、采集和處理，并將數(shù)據(jù)傳輸給用戶[1]，具有快速部署、安全可靠的良好性能，有著廣闊的應(yīng)用前景。無線傳感器網(wǎng)絡(luò)在工業(yè)控制、環(huán)境監(jiān)測等領(lǐng)域顯示出巨大的潛力和應(yīng)用價值[2]。無線傳感器網(wǎng)絡(luò)在一些應(yīng)用領(lǐng)域需要掌握節(jié)點的位置信息。比如森林火災(zāi)監(jiān)測，天然氣管道泄漏。針對這類事件的發(fā)生，首先需要確定的是傳感器節(jié)點的地理位置信息。因此，無線傳感器節(jié)點的定位具有重要的意義。

目前經(jīng)常用的定位算法可以分為基于測距的定位算法和無測距的定位算法。常用的測距技術(shù)有TOA[3]、TDOA[4]、RSSI[5]以及AOA[6]等。常用非測距定位技術(shù)主要有APIT[7]法、質(zhì)心法[8]、DV-HOP[9]和凸規(guī)劃[10]等。在實現(xiàn)基于測距的定位算法之前，需要計算節(jié)點間的距離。在實際應(yīng)用中，需要額外的硬件，且能耗和成本較高，不能廣泛應(yīng)用于特定環(huán)境，無需測距的定位技術(shù)利用節(jié)點間的連通性實現(xiàn)定位。無需額外硬件的支持，可以節(jié)約成本，降低能耗。因此，無需測距定位方法在實際應(yīng)用中得到更廣泛的應(yīng)用[11-12]。DV-HOP定位算法是一種典型的無測距定位方法。它具有硬件要求低、實現(xiàn)簡單等優(yōu)點，受到了國內(nèi)外研究者的廣泛關(guān)注。然而，也存在定位誤差大、定位精度低等問題，因此研究者做了大量的研究。

現(xiàn)有DV-HOP定位算法從修正最小跳數(shù)或平均跳距、選擇最優(yōu)信標節(jié)點、優(yōu)化坐標等方面進行了改進。文獻[13]提出了一種基于RSSI跳數(shù)量化與誤差修正的DV-HOP定位算法。從跳數(shù)量化、修正平均距離和未知節(jié)點坐標等方面對DV-HOP定位算法進行改進，但是RSSI測量技術(shù)需要額外硬件支持，增加了成本。為了修正節(jié)點間的最小跳數(shù)，文獻[14]提出了雙通信半徑改進節(jié)點最小跳數(shù)。雖然算法的精確度得到改善，但是算法復(fù)雜度高。在此基礎(chǔ)上，文獻[15]中提出一種改進多通信半徑的DV-HOP定位算法，在多個通信半徑定位的基礎(chǔ)上利用余弦定理修正最小跳數(shù)和估計距離，解決了節(jié)點分布不均勻時存在的誤差。通信半徑越多，定位誤差越小，網(wǎng)絡(luò)的開銷越大。文獻[16]將DV-HOP算法與半測量加權(quán)質(zhì)心相結(jié)合，信標節(jié)點通過質(zhì)心算法進行自身定位，并將定位精度作為未知節(jié)點的權(quán)重，修改未知節(jié)點和信標節(jié)點之間的跳距，減少DV-HOP算法的誤差，但算法復(fù)雜度高且難以實現(xiàn)。文獻[17]采用相似路徑匹配法校正信標節(jié)點與未知節(jié)點之間的距離，并采用改進灰狼優(yōu)化算法優(yōu)化節(jié)點坐標。定位誤差減小，定位精度提高，但是沒有考慮節(jié)點稀疏、相似度不高的環(huán)境。文獻[18]提出基于DV-HOP測距修正的動態(tài)調(diào)參差分進化算法，利用多通信半徑和節(jié)點遠近度修正測距值，通過動態(tài)調(diào)整差分進化參數(shù)進行尋優(yōu)搜索，在算法精度提高的同時也加大了網(wǎng)絡(luò)的開銷和算法復(fù)雜度。為了更好地提高算法的精確度，本文提出了一種基于鯨魚優(yōu)化改進的DV-HOP定位算法。在估計距離階段，通過添加修正因子和權(quán)重，以提高未知節(jié)點估計距離的精度，在定位階段，引入改進WOA算法優(yōu)化定位結(jié)果，從而減小節(jié)點定位誤差。

1 DV-HOP定位算法及誤差分析

1.1 DV-HOP定位算法

DV-HOP(distance vector-hop)算法是Niculescu等人基于矢量路由原理提出的一種無需測距的定位算法，DV-HOP定位算法可以分為以下3個階段。

1.1.1 計算未知節(jié)點與每個信標節(jié)點的最小跳數(shù)

每一個信標節(jié)點發(fā)出1個包含其自身位置信息、跳數(shù)和地址的包，跳數(shù)的初始值為0。在從信標節(jié)點接收到該數(shù)據(jù)包后，鄰近的其他節(jié)點檢查自身的跳數(shù)是否小于之前從信標節(jié)點接收到的跳數(shù)。如果是，在數(shù)據(jù)加1后廣播包。最后，網(wǎng)絡(luò)中所有未知節(jié)點都能知道到信標節(jié)點的最小跳數(shù)。

1.1.2 計算未知節(jié)點與信標節(jié)點之間的距離

根據(jù)信標節(jié)點自身獲得的其他信標節(jié)點的坐標信息和跳數(shù)，利用式(1)計算信標節(jié)點每跳的平均跳距并向全網(wǎng)廣播，根據(jù)式(2)計算未知節(jié)點m與信標節(jié)點i之間的估計距離。

(1)

dmi=HopSizei×hmi

(2)

式中：(xi、yi)、(xj，yj)為信標節(jié)點i，j的坐標；hij是信標節(jié)點i與j(i≠j)之間的最小跳數(shù)；dmi為未知節(jié)點m與信標節(jié)點i之間的估計距離；hmi為未知節(jié)點m與信標節(jié)點i之間的最小跳數(shù)。

1.1.3 計算未知節(jié)點坐標

未知節(jié)點收到3個或更多信標節(jié)點的距離，根據(jù)式(3)進行自身位置的計算。

(3)

式中：(xm,ym)為未知節(jié)點m的坐標；(xi,yi)為信標節(jié)點i的坐標，i=1,2,3,…，n。

將式(3)中的前n-1個方程分別減去第n個方程并用矩陣AX=B的形式表示，其中A、X和B可由式(4)表示：

(4)

利用最小二乘法計算未知節(jié)點的估計坐標，由式(5)表示:

X=(ATA)-1ATB

(5)

1.2 DV-HOP定位算法誤差分析

在WSN的實際應(yīng)用中，節(jié)點是隨機部署在環(huán)境中的，不能保證節(jié)點的均勻性。而DV-HOP的定位過程要基于矢量信息和拓撲結(jié)構(gòu)的連通性。當節(jié)點分布不均勻時，會存在較大的誤差。定位算法主要誤差來源有：

(1)DV-HOP定位算法的定位過程依賴于信標節(jié)點的平均跳距，當節(jié)點分布不均勻時，節(jié)點之間的最小跳數(shù)往往是折線，當用折線代替直線求節(jié)點間的距離時就會產(chǎn)生誤差。

(2)WSN的網(wǎng)絡(luò)結(jié)構(gòu)具有多樣性，采用未知節(jié)點最近的信標節(jié)點的平均跳距對未知節(jié)點的距離進行估計時，具有單一性和偶然性，將對定位的精度產(chǎn)生影響。

(3)在DV-HOP的最后1個階段，利用最小二乘法求未知節(jié)點的坐標時，用前n-1個方程分別減去第n個方程，會造成誤差積累。

2 改進定位算法

2.1 信標節(jié)點平均跳距的修正

(6)

(7)

利用實際距離與估計距離之間的差值求修正因子ei,如式(8)所示。然后通過式(9)修正信標節(jié)點的平均跳距。

(8)

(9)

2.2 未知節(jié)點平均跳距的修正

DV-HOP定位算法，在第2階段求未知節(jié)點到信標節(jié)點的距離時，采用靠近未知節(jié)點的信標節(jié)點的平均跳距值，由于無線傳感網(wǎng)絡(luò)中節(jié)點的分布具有隨機性，未知節(jié)點到每個信標節(jié)點的平均跳距值并不相同，這會導(dǎo)致距離估計值的誤差較大。因此本文考慮未知節(jié)點接收到的其他信標節(jié)點跳距值，根據(jù)未知節(jié)點到各個信標節(jié)點的跳數(shù)信息引入權(quán)重因子，并利用2.1節(jié)中修正后的信標節(jié)點的平均跳距值修正未知節(jié)點的平均跳距，假設(shè)未知節(jié)點m共收到n個信標節(jié)點的平均跳距，權(quán)重因子wi可用式(10)表示。

(10)

式中：wi為權(quán)重因子；hmi為未知節(jié)點m到信標節(jié)點i的最小跳數(shù)。

未知節(jié)點的平均跳距可用式(11)表示。

(11)

2.3 改進鯨魚算法優(yōu)化定位結(jié)果

2.3.1 標準鯨魚優(yōu)化算法

鯨魚優(yōu)化算法(WOA)是澳大利亞學者Mirjalili和Lewis等人提出的群智能優(yōu)化算法[19]。它的思想是通過模擬座頭鯨的獨特搜索方法和環(huán)繞狩獵機制尋找最優(yōu)解，具有原理簡單、參數(shù)設(shè)置少、搜索能力強等優(yōu)點。包括包圍獵物、泡泡網(wǎng)攻擊和搜索獵物3個階段。

2.3.1.1 包圍獵物

鯨魚在覓食時通過確定獵物的位置包圍和捕食獵物。最佳搜索代理假設(shè)當前最佳候選解決方案是獵物或靠近目標的位置。其他鯨魚根據(jù)最佳候選解決方案更新自己位置。該行為可以用式(12)表示：

(12)

式中：t為當前迭代次數(shù)；X*(t)為t代中最優(yōu)解的位置；X(t)為第t代當前解的位置；D為最優(yōu)解與當前個體差距；A和C為系數(shù)；r為[0,1]區(qū)間的隨機數(shù)；a隨著迭代次數(shù)的增加從2到0線性遞減；t_max為最大迭代次數(shù)。

2.3.1.2 泡泡網(wǎng)攻擊策略(利用階段)

鯨魚的泡泡網(wǎng)攻擊策略包括兩種機制。第一種是收縮包圍機制，通過降低收斂因子a來實現(xiàn)。a隨著迭代次數(shù)增加逐漸減小，A為[-a,a]區(qū)間上的隨機數(shù)。當|A|≤1時，鯨魚以收縮包圍的方式更新位置。第二種是螺旋更新位置機制，當座頭鯨發(fā)現(xiàn)獵物且隨機概率大于0.5，以螺旋狀移向獵物?？捎墒?13)表示：

X(t+1)=D′·ebl·cos(2πd)+X*(t)

(13)

式中：b為常數(shù)；l為[-1,1]區(qū)間上的隨機數(shù)；D′為第i只鯨魚與當前最優(yōu)解(獵物)的距離，D′=|X*(t)-X(t)|。

鯨魚收縮包圍獵物的同時沿螺旋型路徑游動。為描述兩者的同步行為，假設(shè)鯨魚在兩者方式之間更新位置的可能性為50%。由式(14)表示

(14)

式中p為[0,1]之間的隨機數(shù)。

2.3.1.3 搜索獵物機制(探索階段)

在探索階段，當|A|>1時，鯨魚個體會遠離本來的目標獵物。算法不再會根據(jù)目標獵物的位置更新自己的位置，而是隨機選擇1個搜索代理替換目標獵物。其數(shù)學模型用式(15)表示：

(15)

式中Xrand表示當前種群隨機一個搜索代理的位置。

2.3.2 改進鯨魚優(yōu)化算法

2.3.2.1 Tent混沌映射初始化種群

鯨魚優(yōu)化算法具有參數(shù)少、模型簡單、容易實現(xiàn)等優(yōu)點，標準鯨魚優(yōu)化算法在搜索空間中隨機產(chǎn)生初始種群，會造成搜索空間中的種群分布不均勻，為使種群在初始空間中均勻分布，引入Tent混沌映射初始化種群。Tent混沌映射的隨機性和遍歷性可以使算法在一定范圍內(nèi)不重復(fù)的遍歷所有狀態(tài)，保證種群均勻分布在解空間內(nèi)。Tent混沌映射方程如式(16)所示：

(16)

式中xn為[0,1]區(qū)間的一個隨機數(shù)。

2.3.2.2 非線性收斂因子與自適應(yīng)慣性權(quán)重策略

在優(yōu)化過程中，WOA算法會出現(xiàn)全局搜索和局部開發(fā)不平衡的現(xiàn)象。但是全局搜索和局部開發(fā)都受參數(shù)A的影響，參數(shù)A的變化依賴于收斂因子a。在標準鯨魚優(yōu)化算法中，迭代過程中的收斂因子a從2線性下降到0，不能滿足實際情況。本文對收斂因子a進行了改進。用式(17)表示收斂因子a的變化。

(17)

式中：t表示當前迭代次數(shù)；t_max表示最大迭代次數(shù)。

鯨魚優(yōu)化算法在迭代過程中獵物引導(dǎo)鯨魚進行位置更新時會存在差異，為了充分利用最優(yōu)解，提高算法的尋優(yōu)精度。在WOA算法更新公式中，引入自適應(yīng)參數(shù)作為慣性權(quán)重。

自適應(yīng)權(quán)重表達式如式(18)所示：

(18)

式中：μmax=1；μmin=0。

改進后的鯨魚算法更新公式為：

(19)

X(t+1)=μXrand-AD

(20)

2.3.2.3 差分變異操作

在WOA算法中，當前最優(yōu)個體會靠近全局最優(yōu)個體，如果當前最優(yōu)個體位置不是全局最優(yōu)，那么隨著迭代次數(shù)的增加，種群中的個體會向局部最優(yōu)聚集。結(jié)果導(dǎo)致種群中多樣性降低，算法收斂早，尋優(yōu)精度低。為此，本文中引入差分變異策略，將隨機選擇的個體和當前最優(yōu)的個體與當前個體進行隨機差分生成新個體。增加種群個體多樣性，避免算法因早熟收斂而陷入局部最優(yōu)。隨機差分變異策略如式(21)所示：

X(t+1)=r1(X*(t)-X(t))+r2(X′(t)-X(t))

(21)

式中：r1和r2為[0,1]的隨機數(shù)；X′(t)為種群隨機選取的個體。

2.4 設(shè)置適應(yīng)度函數(shù)

在無線傳感網(wǎng)絡(luò)中，求估計距離的方法影響定位精度。為了減小定位誤差的影響。本文利用改進的WOA優(yōu)化算法進行優(yōu)化。適應(yīng)度函數(shù)如式(22)所示：

(22)

式中：(xm,ym)為未知節(jié)點m的坐標；(xi,yi)為信標節(jié)點i的坐標；dmi為未知節(jié)點m和信標接地點i的估計距離。

2.5 改進DV-HOP定位算法流程

為解決DV-HOP算法中定位誤差的問題，本文提出了基于誤差修正和改進WOA的DV-HOP的定位算法。改進后的DV-HOP定位算法流程如下：

(1)初始化網(wǎng)絡(luò)區(qū)域大小以及網(wǎng)絡(luò)中的節(jié)點數(shù)，信標節(jié)點發(fā)送數(shù)據(jù)包，其他節(jié)點通過接收到的數(shù)據(jù)包計算節(jié)點間的最小跳數(shù)。

(2)通過式(6)～式(11)對未知節(jié)點的平均跳距進行改進，并將最小跳數(shù)和改進后的平均跳距的乘積作為未知節(jié)點到信標節(jié)點的估計距離。

(3)設(shè)置相關(guān)參數(shù)，主要有鯨魚規(guī)模N，最大迭代次數(shù)t_max。

(4)利用tent混沌映射初始化種群。

(5)根據(jù)式(22)計算種群個體適應(yīng)度值。利用改進的更新式(19)和式(20)對個體位置進行更新。根據(jù)式(21)執(zhí)行隨機差分變異擾動。

(6)如果滿足迭代終止條件，則終止算法的執(zhí)行并輸出全局最優(yōu)解;否則返回步驟(5)繼續(xù)迭代優(yōu)化。

(7)重復(fù)步驟(4)～步驟(6)，直到輸出所有未知節(jié)點的估計坐標。

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

為了驗證本文改進算法的性能，利用仿真平臺，對傳統(tǒng)DV-HOP、文獻[20]算法(ABCDV-HOP)、文獻[21]算法(DEDV-HOP)以及本文提出的算法進行了仿真比較，如圖1所示，設(shè)置100 m×100 m的矩形仿真區(qū)域，把100個傳感器節(jié)點隨機分布在仿真區(qū)域中，鯨魚的種群個體設(shè)置為30，迭代300次。為了避免實驗結(jié)果的偶然性，實驗結(jié)果取50次實驗的平均值。本文用歸一化定位誤差比較算法的定位性能。歸一化定位誤差如式(23)所示：

圖1 節(jié)點隨機部署區(qū)域圖

(23)

3.1 信標節(jié)點對定位精度的影響

如圖2所示，為研究信標節(jié)點對定位精度的影響，傳感器節(jié)點的數(shù)量設(shè)置為100，信標節(jié)點的數(shù)量由5逐漸增加到40，通信半徑設(shè)置為25。當信標節(jié)點的數(shù)量逐漸增加時，4種算法的性能分析比較的仿真結(jié)果表明，隨著信標數(shù)量的增加，四種算法的待定位誤差逐漸減小。在數(shù)量達到25后定位誤差的變化都逐漸穩(wěn)定。其中本文提出的WOADV-HOP算法，定位誤差始終最小，比DV-HOP，ABCDV-HOP和DEDV-HOP算法的平均誤差分別減小52%，46%，27.6%。

3.2 通信半徑對定位精度的影響

如圖3所示，為通信半徑對定位精度的影響，圖中，傳感器節(jié)點設(shè)置為100，節(jié)點的通信半徑從15到40逐漸增加。仿真結(jié)果顯示，4種算法的節(jié)點定位誤差隨著通信半徑的增加而減小。當通信半徑到達30后，定位誤差減小變慢。這是由于節(jié)點通信半徑的大小會影響網(wǎng)絡(luò)的連通性，從而影響算法的準確性。從圖3中可以看出，WOADV-HOP的定位算法優(yōu)于其他3種，WOADV-HOP算法的定位誤差比DV-HOP減少了49%，比ABCDV-HOP減少了40%，和DEDV-HOP相比減少了21%。

圖3 通信半徑對定位精度影響對比圖

3.3 節(jié)點總數(shù)對定位精度的影響

如圖4所示，為節(jié)點總數(shù)對定位的精度影響對比圖。設(shè)置通信半徑為30，信標節(jié)點占節(jié)點總數(shù)的10%。節(jié)點的總數(shù)量從100逐漸增加到400。仿真結(jié)果顯示，4種算法的定位誤差隨著節(jié)點數(shù)量的增加逐漸減小。當節(jié)點總數(shù)大于300時，誤差趨于穩(wěn)定。通過對比分析可知，在其他條件相同的情況下，本文提出的WOADV-HOP定位算法定位誤差低于其他算法，WOADV-HOP算法的定位誤差相比DEDV-HOP和ABCDV-HOP分別減少了25%、21%，相比于傳統(tǒng)DV-HOP減少了39%。

圖4 節(jié)點總數(shù)對定位精度影響對比圖

3.4 定位算法耗時對比

設(shè)置節(jié)點通信半徑為30，信標節(jié)點比例為10%,節(jié)點總數(shù)分別取100、150、200、250時，算法運行時間取20次運行時耗的平均值。4種算法的仿真時間如表1所示，隨著節(jié)點數(shù)量的增加，算法的計算時間增加。由表1可以看出，4種算法中傳統(tǒng)DV-HOP算法用時最短，在提高優(yōu)化算法精度的同時，增加了算法的復(fù)雜度和運行時間。文獻[20](ABCDV-HOP)只利用蜂群優(yōu)化算法優(yōu)化了定位階段，因此算法的計算時間相比于傳統(tǒng)DV-HOP增加較少。本文算法和文獻[21](DEDV-HOP)算法既優(yōu)化了測距階段又優(yōu)化了定位階段，算法計算時間比傳統(tǒng)DV-HOP增加較多。本文算法計算時間雖然有所增加，但是計算時間比DEDV-HOP短，精度在4種算法中最高。

表1 不同節(jié)點數(shù)量下算法平均計算時間對比表 s

4 結(jié)論

在無線傳感器網(wǎng)絡(luò)中，大多數(shù)應(yīng)用需要知道傳感器節(jié)點的確切位置。本文通過分析傳統(tǒng)DV-HOP定位誤差來源，提出了基于測距修正及鯨魚優(yōu)化改進的DV-HOP定位算法。該算法通過添加修正因子和慣性權(quán)重修改測距值，利用改進鯨魚優(yōu)化算法代替最小二乘法求待定位節(jié)點的坐標。在改進的鯨魚算法中，采用Tent混沌映射提高算法的收斂速度和算法的遍歷性，利用非線性收斂因子和慣性權(quán)重提高算法的全局開發(fā)和局部探索能力。最后通過差分變異策略防止算法過早收斂陷入局部最優(yōu)。實驗結(jié)果表明，與傳統(tǒng)DV-HOP算法、文獻[20]算法和文獻[21]算法相比，本文算法提高了算法的定位精度，擁有較好的穩(wěn)定性。由于算法對平均跳距進行了修正，坐標進行了優(yōu)化，增加了算法的復(fù)雜度。在后期的工作中，將降低算法的復(fù)雜度，進一步研究高精度低能耗的定位算法。