基于二階段差分演化的WSN節(jié)點(diǎn)定位優(yōu)化

(廣東工程職業(yè)技術(shù)學(xué)院 信息工程學(xué)院, 廣州 510520)

0 引言

無線傳感器網(wǎng)絡(luò)(wireless sensor networks, WSN)作為物聯(lián)網(wǎng)應(yīng)用技術(shù)的核心組成部分，通過節(jié)點(diǎn)的自組織，具有無中心性、動(dòng)態(tài)性，成本低、功耗低、節(jié)點(diǎn)設(shè)置靈活、大規(guī)模、自適應(yīng)能力強(qiáng)、可擴(kuò)展性好的特點(diǎn)[1]，使信息的傳播、處理及應(yīng)用形成了新的模式，實(shí)現(xiàn)了物聯(lián)網(wǎng)技術(shù)與真實(shí)物理世界的結(jié)合。隨著物聯(lián)網(wǎng)技術(shù)的快速發(fā)展和應(yīng)用領(lǐng)域的不斷擴(kuò)大，已廣泛應(yīng)用于國(guó)防部署戰(zhàn)場(chǎng)監(jiān)測(cè)、地質(zhì)監(jiān)測(cè)及勘查、車輛跟蹤交通整治、應(yīng)急救援人員營(yíng)救等具有特殊需要的通信環(huán)境中[2]。WSN自組織地通過傳感器收集數(shù)據(jù)，通過無線電波隨機(jī)地相互通信。由于傳感器節(jié)點(diǎn)分布的環(huán)境很復(fù)雜，常分布在數(shù)據(jù)不方便收集與傳輸?shù)膹?fù)雜環(huán)境，或者目標(biāo)位置會(huì)不斷移動(dòng)的區(qū)域，例如水下，火災(zāi)，火山，動(dòng)物棲息地或戰(zhàn)場(chǎng)等，而使用全球定位系統(tǒng)(GPS)成本高昂且在室內(nèi)不可行，所以需要通過無線電協(xié)作方式收集、傳播以及處理目標(biāo)區(qū)域的數(shù)據(jù)信息，因此WSN中的節(jié)點(diǎn)位置信息成為重要內(nèi)容。如何使節(jié)點(diǎn)的位置計(jì)算更接近實(shí)際已成為目前無線傳感器網(wǎng)絡(luò)定位研究的熱點(diǎn)，無線傳感器網(wǎng)絡(luò)應(yīng)用關(guān)鍵技術(shù)之一的WSN自定位技術(shù)近年成為學(xué)界研究的關(guān)注熱點(diǎn)[3]。

定位算法分為基于測(cè)距和基于免測(cè)距兩種，基于測(cè)距的定位算法由于使用了測(cè)量設(shè)備，所以定位精度很高而得到廣泛應(yīng)用[4-7]，但此方法也受到周邊復(fù)雜環(huán)境的影響，定位精度會(huì)出現(xiàn)較大誤差，RSSI算法是這類算法的典型，定位正確率非常高，但缺點(diǎn)是要增加額外設(shè)備，并且實(shí)際使用中會(huì)發(fā)生測(cè)量信號(hào)損耗，總體來說這類算法代價(jià)高?；诿鉁y(cè)距的定位算法不需要測(cè)量，不需要額外增加設(shè)備，實(shí)現(xiàn)較簡(jiǎn)單，但往往定位誤差更大[8-10]，典型的是DV-Hop算法，實(shí)現(xiàn)較簡(jiǎn)單，應(yīng)用很廣泛，但誤差較大，精度有待提高。

在DV-Hop算法依賴整個(gè)網(wǎng)絡(luò)的連通度，根據(jù)節(jié)點(diǎn)間的平均跳距和跳數(shù)來定位，雖然近年有學(xué)者采用各種方法對(duì)結(jié)果進(jìn)行修正，但最后修改結(jié)果誤差還是偏大，在30%左右。近年有不少學(xué)者針對(duì)DV-Hop算法存在的不足，為提高節(jié)點(diǎn)的定位精度，采用遺傳算法、模擬退火算法、粒子群優(yōu)化算法等對(duì)DV-Hop進(jìn)行優(yōu)化，特別是遺傳算法和粒子群優(yōu)化算法成了研究熱點(diǎn)，取得不少研究成果[11-16]，但這些優(yōu)化算法存在迭代次數(shù)相對(duì)過大，節(jié)點(diǎn)耗能相對(duì)較高的缺點(diǎn)，為解決這問題，本研究提出一種基于二階段優(yōu)化的的差分演化算法，在DV-Hop定位的基礎(chǔ)上，采用差分演化算法進(jìn)行第二階段定位優(yōu)化的方法，通過仿真驗(yàn)證，證明了該算法在很低的迭代次數(shù)(能耗很低)就能獲得較高的定位精度，為WSN定位研究探索一個(gè)新思路。

1 DV-Hop無線傳感器節(jié)點(diǎn)定位算法

DV-Hop算法作為一種典型的免測(cè)距算法，應(yīng)用廣泛，其工作過程為：

1)類似距離矢量交換協(xié)議，首先，信標(biāo)節(jié)點(diǎn)用無線電信號(hào)向相鄰節(jié)點(diǎn)廣播包括自己位置及跳數(shù)的數(shù)據(jù)，并設(shè)初始跳數(shù)為零。通信范圍內(nèi)的節(jié)點(diǎn)接收到數(shù)據(jù)后保存這個(gè)信標(biāo)節(jié)點(diǎn)坐標(biāo)并把這個(gè)信標(biāo)節(jié)點(diǎn)發(fā)送過來的跳數(shù)值增加1，按照最小跳數(shù)原則更新自己的路由表，之后再向自己相鄰的其他節(jié)點(diǎn)發(fā)送信息，如此重復(fù)上述步驟，經(jīng)過一輪洪泛廣播，除了一些無法獲得廣播數(shù)據(jù)包的邊緣節(jié)點(diǎn)和孤立節(jié)點(diǎn)外，整個(gè)WSN節(jié)點(diǎn)都將獲得距離信標(biāo)節(jié)點(diǎn)的最小跳數(shù)值。這樣，每個(gè)節(jié)點(diǎn)都記錄了到所有信標(biāo)節(jié)點(diǎn)的最小跳數(shù)。

2)計(jì)算平均跳距。平均跳距是根據(jù)信標(biāo)節(jié)點(diǎn)之間的跳數(shù)-距離關(guān)系推導(dǎo)出來的。根據(jù)上一步驟，每個(gè)信標(biāo)節(jié)點(diǎn)獲取了能夠與之通信的其他信標(biāo)節(jié)點(diǎn)的位置坐標(biāo)和最小跳數(shù)，假如信標(biāo)節(jié)點(diǎn)i和信標(biāo)節(jié)點(diǎn)j的實(shí)際坐標(biāo)分別是(xi,yi)和(xj,yj)，上一步驟已經(jīng)得到了這兩者之間的最小跳數(shù)hopsij，則可以根據(jù)式(1)計(jì)算平均每跳的距離值[9]。

(1)

每個(gè)信標(biāo)節(jié)點(diǎn)將自身對(duì)應(yīng)的Ci廣播到整個(gè)WSN中，未知節(jié)點(diǎn)只保留距離自己近的信標(biāo)節(jié)點(diǎn)的平均每跳距離值Ci，其他全部舍棄，并將其發(fā)送到附近的節(jié)點(diǎn)。如果未知節(jié)點(diǎn)m到信標(biāo)節(jié)點(diǎn)i的最小跳數(shù)hopmi，則未知節(jié)點(diǎn)m到信標(biāo)節(jié)點(diǎn)i的估計(jì)距離如式(2)所示：

dmi=Ci×hopmi

(2)

3)計(jì)算未知節(jié)點(diǎn)坐標(biāo)。經(jīng)過以上兩個(gè)階段，未知節(jié)點(diǎn)利用式(2)可以獲得到多個(gè)信標(biāo)節(jié)點(diǎn)的估計(jì)距離(需要三個(gè)或以上)，用三邊測(cè)量法確定未知節(jié)點(diǎn)的定位。設(shè)第i個(gè)信標(biāo)節(jié)點(diǎn)坐標(biāo)為(xi,yi)，待定位的未知節(jié)點(diǎn)坐標(biāo)為(x,y)，待定位的未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)i之間的距離為di，根據(jù)上述已知數(shù)據(jù)，可建立方程組如式(3)所示:

(3)

對(duì)方程組(3)采用極大似然估計(jì)法進(jìn)行求解，得到方程組(4)：

(4)

將方程組(4)用矩陣形式表示：AX=B。

其中：

(5)

(6)

(7)

使用最小二乘法，可得到未知節(jié)點(diǎn)坐標(biāo)如式(8)所示:

X=(ATA)-1ATB

(8)

設(shè)待定位的未知節(jié)點(diǎn)(x,y)與信標(biāo)節(jié)點(diǎn)(xi,yi)的實(shí)際距離是ri，測(cè)距誤差為εi，可知ri-di<εi。

則待定位的未知節(jié)點(diǎn)坐標(biāo)(x,y)應(yīng)滿足式(9)的約束條件：

(9)

求解(x,y)，得：

(10)

綜上所述，未知節(jié)點(diǎn)定位問題可以轉(zhuǎn)化為一個(gè)多約束優(yōu)化問題，式(10)是一個(gè)非線性優(yōu)化問題，數(shù)學(xué)上難以精確求解，因此研究利用差分演化算法進(jìn)行二階段精確求解。

2 基于差分演化的二階段定位優(yōu)化算法

2.1 差分演化算法

差分演化(Differential Evolution,DE)是由 Storn 和 Price 科學(xué)家在 1995 年提出的一種啟發(fā)式隨機(jī)搜索算法，跟遺傳算法、粒子群算法一樣屬于群體智能仿生算法，具有結(jié)構(gòu)簡(jiǎn)單、容易實(shí)現(xiàn)、收斂速度快、魯棒性強(qiáng)等優(yōu)點(diǎn)[11]，該算法具有極強(qiáng)全局搜索能力的演化算法，因其在第一屆IEEE 演化大賽中的超群表現(xiàn)引起了國(guó)內(nèi)外學(xué)者的極大關(guān)注，近年成為研究熱點(diǎn)，已被廣泛應(yīng)用到各種優(yōu)化領(lǐng)域中，該算法適合用到WSN定位優(yōu)化領(lǐng)域。

差分演化是一種在遺傳算法等進(jìn)化思想的基礎(chǔ)上，基于群體差異的啟發(fā)式隨機(jī)搜索算法，與其他進(jìn)化算法大體上流程大致相同，也包含了種群初始化、變異、交叉、選擇等操作。不同之處在于，差分演化算法是的核心是變異操作，將多個(gè)向量的差分信息作為基向量的擾動(dòng)量，先從群體里隨機(jī)選兩個(gè)個(gè)體向量進(jìn)行差分和縮放，再與該群體中隨機(jī)選定的第三個(gè)個(gè)體向量相加，得到一個(gè)新的變異個(gè)體向量，然后這個(gè)新的變異個(gè)體向量與父?jìng)€(gè)體向量進(jìn)行雜交，形成了一個(gè)備選個(gè)體向量，最后比較備選個(gè)體和父?jìng)€(gè)體的適應(yīng)值，采用貪心策略，總是選擇較優(yōu)者保存到下一代群體中。這樣，差分演化算法利用差分變異、雜交和選擇等算子對(duì)群體不斷進(jìn)行演化，直到達(dá)到終止條件為止。

經(jīng)過多年的發(fā)展，DE有多種不同的進(jìn)化模式，差別體現(xiàn)在算子的變異方法不同，這里采用DE/rand/1模式。而作為個(gè)體優(yōu)劣評(píng)價(jià)的函數(shù)將采用式(11)：

(11)

2.1.1 變異操作

采用DE/rand/1模式，設(shè)向量D為維數(shù)，本文為無線傳感器網(wǎng)絡(luò)中的未知節(jié)點(diǎn)坐標(biāo)值。從種群中隨機(jī)選擇3個(gè)Vi(t+1)=(Vi1,Vi2,…,ViD)染色體Xr1,Xr2,Xr3，且i≠r1≠r2≠r3，則：

Vij=Xr1j+F×(Xr2j-Xr3j)

(12)

其中:Vi為變異向量；Xr2-Xr3為分差向量；F∈[0,1]為縮放因子；t為當(dāng)前演化代數(shù)。

2.1.2 雜交操作

雜交算子對(duì)變異向量Vi和父?jìng)€(gè)體向量Xi進(jìn)行雜交，操作如式(13)所示：

(13)

其中，randrealj是(0,1)之間的隨機(jī)小數(shù)，jrand是[1,D]之間的一個(gè)隨機(jī)整數(shù)；CR∈(0,1)是交叉概率。這種雜交策略保證向量Ui至少有一維來自變異向量Vij，避免與父代個(gè)體向量Xi相同而過早停止了進(jìn)化。

2.1.2 選擇操作

采用貪婪策略，總是選擇較優(yōu)者保存入下一代群體里，如式(14)所示:

(14)

其中，f為適應(yīng)函數(shù)，i=1,2,…,NP，NP為種群規(guī)模。

2.2 二階段定位算法

近年學(xué)界利用各種智能算法比如遺傳算法、粒子群優(yōu)化算法對(duì)無線傳感器網(wǎng)絡(luò)定位進(jìn)行優(yōu)化[1-11]，采得不少成果，定位誤差由30%提高到5%左右，效果良好，但是也存在優(yōu)化迭代代數(shù)過高的明顯缺點(diǎn)，這些優(yōu)化算法普通都在迭代1000代以上，最少也要500代以上，將耗費(fèi)較大的能量，在能量存儲(chǔ)不大的各無線傳感器節(jié)點(diǎn)的實(shí)際應(yīng)用中，追求高精度的同時(shí)，也要追求低能耗，所以尋找更少迭代次數(shù)(即更低能耗)算法成了當(dāng)務(wù)之急。

為了提高定位精高的同時(shí)更低能耗(更少迭代次數(shù))，本文研究了二階段定位算法，第一階段用DV-Hop無線傳感器節(jié)點(diǎn)定位方法找出未知節(jié)點(diǎn)坐標(biāo)(xest,yest)，第二階段用差分演化算法在坐標(biāo)(xest,yest)附近尋找最優(yōu)坐標(biāo)(x,y)，即為最終定位的坐標(biāo)。

具體步驟如下：

Step1:DV-Hop無線傳感器節(jié)點(diǎn)定位，利用式(1)～(8)計(jì)算出未知節(jié)點(diǎn)的坐標(biāo)(xest,yest)。此為第一階段；

Step2:第二階段：利用差分演化處算法尋找未知節(jié)點(diǎn)的最終坐標(biāo)(x,y)：

Step2.1 初始化種群。二階段定位法區(qū)分其他定位法在于，種群一開始的位置不是完全隨機(jī)，而是基于第一階段定位結(jié)果來作種群的初始隨機(jī)位置，即在坐標(biāo)(xest,yest)附近以通信半徑r范圍內(nèi)的區(qū)域作為種群的初始隨機(jī)位置。

Step2.2 采用式(11)作為個(gè)體適應(yīng)度函數(shù)值進(jìn)行計(jì)算，經(jīng)過式(12)～(14)進(jìn)行變異、雜交、選擇操作。

Step2.3 達(dá)到最大迭代數(shù)G，停止演化，否則返回Step2.2繼續(xù)演化。

Step2.4 根據(jù)最優(yōu)個(gè)體的位置確定未知節(jié)點(diǎn)的最終坐標(biāo)。

Step2.5 每個(gè)未知節(jié)點(diǎn)都經(jīng)過上述Step2.1-4的計(jì)算，最終得出所有未知節(jié)點(diǎn)的坐標(biāo)。

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

3.1 實(shí)驗(yàn)設(shè)計(jì)

為了驗(yàn)證本研究的節(jié)點(diǎn)定位算法性能優(yōu)劣，在Widnows 7操作系統(tǒng)下，用Matlab 2016b進(jìn)行仿真。在100 m×100 m正方形的區(qū)域內(nèi)，隨機(jī)分布無線傳感器節(jié)點(diǎn)100個(gè)，如圖1所示，鄰居連接如圖2所示，DV-Hop定位誤差如圖3所示。

考慮到了為了體現(xiàn)更低能耗(更低迭代數(shù))，本研究將只迭代10代。為了使本研究的算法有可比性，除了本研究的二階段DM算法外，還采用了基本DV-Hop算法、傳統(tǒng)差分演化算法Origin_DM、傳統(tǒng)粒子群優(yōu)化算法PSO進(jìn)行對(duì)比，取5次實(shí)驗(yàn)平均值作為最終結(jié)果。

3.2 結(jié)果與分析

3.2.1 定位誤差與信標(biāo)節(jié)點(diǎn)數(shù)量關(guān)系

實(shí)驗(yàn)結(jié)果如圖4所示，分析：

1)相對(duì)于DV-Hop算法，三種智能優(yōu)化算法都對(duì)定位精度有明顯的提高，特別是信標(biāo)節(jié)點(diǎn)數(shù)量20個(gè)以上(信標(biāo)比例大于等于20%)時(shí)，DV-Hop算法定位誤差率都在30%以上，而三種智能優(yōu)化算法定位誤差率都在10%以下，智能優(yōu)化算法對(duì)定位精度提高具有非常明顯的效果。

圖1 節(jié)點(diǎn)分布圖(以通徑半徑30米，100個(gè)節(jié)點(diǎn)，信標(biāo)節(jié)點(diǎn)30%為例)

圖2 鄰居關(guān)系圖(以通徑半徑30米，100個(gè)節(jié)點(diǎn)，信標(biāo)節(jié)點(diǎn)30%為例)

圖3 定位誤差圖(以通徑半徑30米，100節(jié)點(diǎn)，信標(biāo)節(jié)點(diǎn)30%，DV-Hop算法為例)

圖4 定位誤差與信標(biāo)節(jié)點(diǎn)關(guān)系

2)在較少信標(biāo)節(jié)點(diǎn)(信標(biāo)數(shù)量小于20，即信標(biāo)比例低于20%)時(shí)，作對(duì)比的兩種智能優(yōu)化算法定位精度不理解，在極端情況下(信標(biāo)節(jié)點(diǎn)小于15，即信標(biāo)比例低于15%)時(shí)甚至出現(xiàn)定位誤差比DV-Hop更差的情況，原因在于傳統(tǒng)智能搜索的優(yōu)化算法在極度缺少信標(biāo)節(jié)點(diǎn)的信息時(shí)，出現(xiàn)無法進(jìn)一步搜索優(yōu)化的現(xiàn)象。

3)本研究提出的二階段DM算法比其他算法有更高的定位精度，并且能很好地解決了上面第2點(diǎn)發(fā)現(xiàn)的其他智能優(yōu)化算法的缺陷，在信標(biāo)節(jié)點(diǎn)極少的條件下，還能得到很好的定位精度。原因在于本研究的二階段差分演化定位算法是基于第一階段得到的DV-Hop定位結(jié)果，有效地避免了信標(biāo)節(jié)點(diǎn)稀疏時(shí)無法有效優(yōu)化的缺陷。

4)從不同信標(biāo)節(jié)點(diǎn)數(shù)量的仿真結(jié)果可以發(fā)現(xiàn)，本研究算法不但在較多信標(biāo)節(jié)點(diǎn)時(shí)有更高的定位精度，而在信標(biāo)節(jié)點(diǎn)稀疏時(shí)有更好的表現(xiàn)。

5)總的來說，本研究算法對(duì)提高未知節(jié)點(diǎn)定位的精度效果明顯，說明了本研究算法的有效性。

3.2.2 定位誤差與通信半徑關(guān)系

實(shí)驗(yàn)結(jié)果如圖5所示，分析：

圖5 定位誤差與通信半徑關(guān)系

1)跟上面的分析類似地，作對(duì)比的兩種傳統(tǒng)智能優(yōu)化算法在通信半徑22米以上的，都比DV-Hop更好的定位精度，但在通信半徑小于22米時(shí)，出現(xiàn)了反而不如DV-Hop的現(xiàn)象，原因在于通徑半徑更短時(shí)，鄰接節(jié)點(diǎn)會(huì)明顯減少，傳統(tǒng)智能優(yōu)化算法將無法搜索到足夠有效信息導(dǎo)致無法進(jìn)行有效優(yōu)化的現(xiàn)象。

2)兩種傳統(tǒng)智能優(yōu)化算法定位精度出現(xiàn)了波動(dòng)較大的現(xiàn)象，并且波動(dòng)規(guī)律類似，原因在于傳統(tǒng)智能優(yōu)化算法是隨機(jī)搜索，容易陷入局部最優(yōu)，明顯影響了定位精度。

3)本研究算法有效解決了上面1、2點(diǎn)分析的傳統(tǒng)智能優(yōu)化算法缺陷，不管在通信半徑短的特殊條件下，還是在定位精度的穩(wěn)定性方面，都比其他智能優(yōu)化算法表現(xiàn)得更好?？偟膩碚f，本研究算法具有更好的定位精度，更好的穩(wěn)定性。

4 結(jié)語

針對(duì)WSN定位問題，在分析DV-Hop算法的不足和其他應(yīng)用在WSN定位的智能優(yōu)化算法迭代次數(shù)較大耗能較多的缺陷，提出一種基于二階段的差化演化的WSN定位優(yōu)化算法，經(jīng)過仿真實(shí)驗(yàn)驗(yàn)證，在只需要迭代10代的情況下，證明了本研究算法不但有效提高了定位精度，并且在信標(biāo)稀疏和通信半徑較短時(shí)具有更好的穩(wěn)定性。