WSN中基于灰狼和差分進化的簇首選擇算法

張 新，俞宗佐

(內(nèi)蒙古師范大學(xué) 計算機科學(xué)技術(shù)學(xué)院，內(nèi)蒙古 呼和浩特 010000)

0 引 言

無線傳感器網(wǎng)絡(luò)(wireless sensor network，WSN)[1]中節(jié)點由電池供電，大多數(shù)情況下無法及時補充能量，因此，對WSN設(shè)計能量均衡策略以延長網(wǎng)絡(luò)生命周期具有重要意義。

LEACH協(xié)議的簇首選擇是隨機的，導(dǎo)致所有節(jié)點的總能量消耗既不平衡也不最小化[2]。LEACH-E協(xié)議將節(jié)點剩余能量的影響因素加入到簇首選擇的概率中[3]，但是，該協(xié)議仍然使用隨機的方式選擇簇首。WSN成簇和簇首選擇問題屬于NP難問題[4]，不易求解。近年來，有研究者用群體智能算法來優(yōu)化WSN分簇與簇首選擇問題。文獻[5]提出了一種改進的灰狼優(yōu)化算法FIGWO來優(yōu)化簇首選擇，將適應(yīng)度值作為獵物新位置權(quán)重，充分考慮節(jié)點當(dāng)前狀態(tài)最優(yōu)解的最終位置，以合理選擇簇首節(jié)點。文獻[6]中首先使用SOM算法對網(wǎng)絡(luò)進行分簇，然后在每個簇中使用改進的灰狼優(yōu)化算法選擇簇首。

上述協(xié)議在優(yōu)化簇首選擇、均衡網(wǎng)絡(luò)能耗方面取得了一定的成效，但由于灰狼優(yōu)化算法容易出現(xiàn)局部最優(yōu)和精度不夠等問題，導(dǎo)致選擇的簇首不一定為最優(yōu)，所以仍需進一步研究和改進。本文提出一種基于改進灰狼優(yōu)化(grey wolf optimization，GWO)和差分進化(differential evolution，DE)的混合算法對WSN進行簇首選擇(diffe-rential evolution and grey wolf optimization，DEGWO)。將差分進化算法混合到灰狼優(yōu)化算法中，調(diào)整混合算法的收斂因子與縮放因子，避免了GWO早熟收斂而無法有效地搜索最優(yōu)解的問題，從而選擇最優(yōu)的簇首。

1 系統(tǒng)模型

1.1 網(wǎng)絡(luò)模型

對本文算法與對比算法所使用的網(wǎng)絡(luò)模型，做出如下假設(shè)：

(1)所有節(jié)點和基站在部署后是靜止的，每個節(jié)點分配一個索引。

(2)所有節(jié)點初始能量相同且能夠報告其位置。

(3)所有節(jié)點以固定速率測量環(huán)境參數(shù)，能夠根據(jù)到目標(biāo)的距離調(diào)整其傳輸功率并定期向目標(biāo)節(jié)點發(fā)送數(shù)據(jù)。

(4)所有節(jié)點可以獨立地與基站通信，基站的位置已知，具有較高的計算能力且沒有能量限制。

1.2 能量消耗模型

本文使用與文獻[7]相同的能耗模型，在該模型中，根據(jù)發(fā)送電路與接收電路之間的距離來選擇能量消耗模型，在距離d上傳輸lbit數(shù)據(jù)所消耗的能量如式(1)所示

(1)

其中，Eelec為傳輸1 bit數(shù)據(jù)所消耗的能量，d0為距離閾值，傳輸距離d小于d0時，采用自由空間衰減模型，Efs是其功率放大所需能量。傳輸距離d大于d0時，采用多徑衰減模型，Emp是其功率放大所需能量。距離閾值d0如式(2)所示

(2)

節(jié)點接收和融合lbit數(shù)據(jù)消耗的能量分別如式(3)和式(4)所示

ERX(l)=lEelec

(3)

EDA(k)=lEda

(4)

其中，Eda表示節(jié)點融合1 bit數(shù)據(jù)所消耗的能量。

1.3 網(wǎng)絡(luò)生存期模型

在大多數(shù)應(yīng)用中，當(dāng)某些節(jié)點出現(xiàn)故障時，網(wǎng)絡(luò)仍能有效地運行。特別是當(dāng)大量傳感器節(jié)點部署在一個區(qū)域時，一個節(jié)點有幾個相鄰節(jié)點，這些鄰居節(jié)點配備了相同的傳感設(shè)備，所以網(wǎng)絡(luò)將能夠應(yīng)對某些節(jié)點的故障。因此，第一個節(jié)點的死亡時間不是評估網(wǎng)絡(luò)生存期的唯一指標(biāo)[8,9]。在評估高節(jié)點密度的性能檢測時，部分節(jié)點的死亡時間(a part of node die，PND)是一個更有效的指標(biāo)[10]。將網(wǎng)絡(luò)的生命周期描述如式(5)所示

(5)

其中，N是網(wǎng)絡(luò)中傳感器的數(shù)量。k是活動節(jié)點的數(shù)量。該式表明，PND的定義為活動節(jié)點與初始節(jié)點個數(shù)的比例下降到閾值ξ的時間。

2 基本算法

2.1 灰狼優(yōu)化算法

在GWO[11]中，灰狼群體被分為α、β、δ、ω這4個社會等級[12]，其中，最優(yōu)解為α狼，次優(yōu)解為β狼，第三優(yōu)解為δ狼，其余的解為ω狼，尋優(yōu)過程是由α、β、δ狼領(lǐng)導(dǎo)ω狼更新位置，最終獲得近似最優(yōu)解。

GWO中，灰狼群體首先對獵物進行包圍，灰狼包圍獵物的數(shù)學(xué)模型的如式(6)和式(7)所示

D=|CXp(t)-X(t)|

(6)

X(t+1)=Xp(t)-AD

(7)

其中，t表示當(dāng)前迭代次數(shù)，A和C表示系數(shù)向量，X為灰狼的位置，Xp為獵物的位置。D為獵物與灰狼的距離。A和C如式(8)和(9)所示

A=2a·r1-a

(8)

C=2r2

(9)

其中，r1、r2為在[0,1]取值中的隨機向量，a為收斂因子，a如式(10)所示

(10)

其中，t是一個介于0到maxIter之間的整數(shù)，并且在迭代過程中每次增加1。maxIter為最大迭代次數(shù)。因此，a(t)在迭代過程中，從2到0線性遞減。

包圍獵物后，GWO執(zhí)行狩獵過程以不斷更新自己的位置，狩獵行為的數(shù)學(xué)模型如式(11)～式(13)所示

Dα=|C1Xα-X|
Dβ=|C2Xβ-X|
Dδ=|C3Xδ-X|

(11)

X1=Xα-A1Dα
X2=Xβ-A2Dβ
X3=Xδ-A3Dδ

(12)

(13)

2.2 差分進化算法

DE算法主要經(jīng)過種群的初始化、變異、交叉、選擇4個過程[13]。其各數(shù)學(xué)模型描述如下：

(1)初始化

(14)

其中，i=1，2，3，……，NP。n是總體向量的維度。NP是種群規(guī)模，上標(biāo)G表示第G代。這些初始種群是在[0,1]之間的均勻分布隨機選擇的。

(2)變異

變異運算在基向量上加一個差分向量，變異運算DE/current-to-best/1如式(15)所示

(15)

(3)交叉

交叉運算是在待變異個體和變異后的新個體進行元素的交換。通過式(16)實現(xiàn)對目標(biāo)向量和變異向量的交叉運算

(16)

其中，j=1，2，…，n，rand為[0,1]內(nèi)一個隨機的數(shù)。CR為交叉概率。jrand為[0,n]內(nèi)隨機選擇的索引。

(4)選擇

選擇運算是在父代個體和子代個體中選擇適應(yīng)度值較高的保留到下一代。選擇運算如式(17)所示

(17)

3 基于DEGWO算法的簇首選擇

基于DEGWO的簇首選擇算法使用經(jīng)典分簇路由協(xié)議中“輪”的思想，將網(wǎng)絡(luò)的每個運行輪次分為分簇階段與數(shù)據(jù)傳輸階段。分簇階段，基站首先使用本文中所提均值法選出初始簇首集合，然后根據(jù)距離形成初始簇，在每個簇內(nèi)，使用DEGWO算法選取出最終簇首。數(shù)據(jù)傳輸階段，簇內(nèi)節(jié)點通過TDMA的方式將數(shù)據(jù)發(fā)送給簇首，簇首節(jié)點將接收到的數(shù)據(jù)融合之后采用CDMA的方式發(fā)送給基站。

3.1 形成初始簇

在WSN中，簇首比普通節(jié)點消耗的能量多，所以，保證簇首在網(wǎng)絡(luò)中均勻分布至關(guān)重要?；贒EGWO的簇首選擇算法，首先采用均值法選取初始簇首，并且形成初始簇，然后在每個簇中使用DEGWO選擇最終簇首，使用均值法選取初始簇首并形成初始簇的步驟如下：

步驟1 初始化(節(jié)點位置、能量等參數(shù))。

步驟2 根據(jù)3.2.4節(jié)中適應(yīng)度函數(shù)式(21)計算每個存活節(jié)點的適應(yīng)度。

步驟3 對步驟2中計算出的適應(yīng)度進行排序。

步驟4 將排序后的適應(yīng)度均勻的分成K個集合。

步驟5 計算每個集合中的適應(yīng)度值的平均值。

步驟6 計算每個集合中的每個節(jié)點與平均值的差值。

步驟7 與平均值差值最小的節(jié)點即選為初始簇首。

步驟8 普通節(jié)點選擇加入最近的簇首，形成初始簇。

3.2 使用DEGWO選擇最終簇首

3.2.1 DEGWO算法選擇簇首

由于基本GWO在執(zhí)行獵物攻擊操作時容易陷入停滯狀態(tài)[14]，使用基本GWO算法優(yōu)化簇首選擇并不能保證得到最優(yōu)近似解。而DE具有強大的搜索能力，將DE混合到GWO中可以擴大種群搜索范圍，避免種群迭代到達某一區(qū)域時出現(xiàn)局部極值。因此，本文提出一種基于DEGWO的簇首選擇算法，在父代個體結(jié)束更新位置后，使用DE算法對GWO中個體進行交叉、變異、選擇操作來維持種群的多樣性，避免GWO陷入停滯狀態(tài)，從而獲得全局最優(yōu)解。使用DEGWO選取最優(yōu)簇首的步驟如下：

步驟1 初始化參數(shù)。

步驟2 將初始簇中個體初始化為灰狼父代種群，隨機初始化變異種群、子代種群。

步驟3 根據(jù)3.2.4節(jié)中的適應(yīng)度函數(shù)式(21)計算父代個體的適應(yīng)度值。

步驟4 將步驟3中排名前三的個體分別設(shè)置為α、β、δ狼。

步驟5 使用3.2.2節(jié)中式(18)收斂因子a與式(6)～(13)對GWO中父代灰狼種群的位置進行更新。

步驟6 使用3.2.3節(jié)中縮放因子F與式(15)產(chǎn)生變異(中間體)種群。

步驟7 通過式(16)的交叉運算產(chǎn)生子代種群。

步驟8 依據(jù)式(17)判斷是否更新父代種群。

步驟9 更新參數(shù)a、A、C。

步驟10 確定是否達到了最大的迭代次數(shù)，若是則停止返回獵物位置作為最優(yōu)解，否則返回步驟3。

步驟11 得到最優(yōu)位置，距離最優(yōu)位置的節(jié)點即當(dāng)選為簇首。

3.2.2 優(yōu)化收斂因子

在GWO中，搜索新獵物與攻擊獵物之間的過渡取決于收斂因子a和系數(shù)向量A，通過式(8)得出A的值為區(qū)間 [-2a，2a] 中的隨機值。在 |A|>1時灰狼搜索新獵物，在 |A|<1時灰狼開始攻擊獵物的行為。通常，在搜索空間的搜索越廣，局部最優(yōu)停滯的概率越低。為了獲得更廣的搜索空間，在迭代中調(diào)整式(8)中收斂因子a為非線性衰減，如式(18)所示

(18)

其中，iter為當(dāng)前迭代次數(shù)，maxIter為最大迭代次數(shù)。

3.2.3 調(diào)整縮放因子

DE在搜索過程中式(15)中的縮放因子F取值一般為[0,2]之間的固定實數(shù)。但是，這樣會導(dǎo)致一些問題，如果變異率過大，則算法的搜索效率較低，全局最優(yōu)解的精度較低，變異率太小，種群多樣性降低。因此，本文通過產(chǎn)生[0,2]之間的均勻分布的隨機數(shù)做為縮放因子，以增加搜索到全局最優(yōu)解的概率。

3.2.4 適應(yīng)度函數(shù)設(shè)計

能量是節(jié)點最大的挑戰(zhàn)，簇首節(jié)點的能量消耗比普通節(jié)點多。選擇能量較高的節(jié)點作為簇首有助于平衡網(wǎng)絡(luò)的能量消耗。因此，設(shè)計適應(yīng)度函數(shù)中能量部分f1如式(19)所示

(19)

其中，E0表示節(jié)點的初始能量，Eres(i) 為節(jié)點的剩余能量。

傳感器的能耗與傳輸距離成正比。傳輸距離越長，能耗越大。在選擇簇首時，選擇離基站更近的節(jié)點可以有效降低簇首的能耗。因此，設(shè)計距離影響因子f2如式(20)所示

(20)

其中，MaxD表示所有節(jié)點到基站最遠的歐式距離，MinD為所有節(jié)點中到基站最近的歐式距離，D(i)為當(dāng)前節(jié)點到基站的歐式距離。

綜上所述，適應(yīng)度值函數(shù)設(shè)計如式(21)所示

Fitness=uf1+(1-u)f2

(21)

其中，F(xiàn)iteness為適應(yīng)函數(shù)，u為權(quán)重系數(shù)。

3.3 數(shù)據(jù)傳輸

數(shù)據(jù)傳輸階段，為防止簇內(nèi)成員間的數(shù)據(jù)沖突，簇內(nèi)數(shù)據(jù)通過時分多址(time division multiple address，TDMA)的方式進行傳輸，由簇首節(jié)點給簇內(nèi)的各個節(jié)點分配通訊時隙，并以廣播的形式通知簇內(nèi)節(jié)點。所有節(jié)點均在自己的時段內(nèi)完成數(shù)據(jù)傳輸，在其它時間進入休眠狀態(tài)，以減少能耗。穩(wěn)定數(shù)據(jù)傳輸階段，節(jié)點在自己的數(shù)據(jù)傳輸時段內(nèi)把所收集的數(shù)據(jù)發(fā)送給簇首節(jié)點后，由簇首節(jié)點對數(shù)據(jù)進行融合處理后以碼分多址(code division multiple access，CDMA)的方式發(fā)送到基站。使用DEGWO算法選擇簇首并進行數(shù)據(jù)傳輸?shù)恼w流程如圖1所示。

圖1 基于DEGWO算法的分簇路由流程

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

4.1 仿真環(huán)境與實驗參數(shù)

本文使用Matlab R2014b對本文所提算法DEGWO與LEACH、LEACH-E、FIGWO這3種協(xié)議進行仿真實驗，并以網(wǎng)絡(luò)生命周期中PND中的3個指標(biāo)和網(wǎng)絡(luò)總能量消耗為標(biāo)準(zhǔn)進行比較。為驗證所提算法對多節(jié)點的適應(yīng)性，設(shè)計了3種不同節(jié)點個數(shù)的網(wǎng)絡(luò)場景進行實驗，3種實驗場景見表1。

表1 3種網(wǎng)絡(luò)場景

并按照文獻[15]將最佳簇首個數(shù)設(shè)置為5%，DEGWO算法迭代次數(shù)為20次，種群大小為初始簇中節(jié)點的個數(shù)，適應(yīng)度函數(shù)權(quán)重系數(shù)u為0.5，各仿真實驗參數(shù)見表2。

表2 仿真實驗參數(shù)

4.2 網(wǎng)絡(luò)生命周期

網(wǎng)絡(luò)生命周期是評價WSN能耗的重要指標(biāo)之一，網(wǎng)絡(luò)生命周期越長，驗證能量消耗越均衡，網(wǎng)絡(luò)對數(shù)據(jù)的吞吐量越大。場景1、場景2、場景3下以輪為單位模擬時間繪制的死亡節(jié)點數(shù)量如圖2、圖3、圖4所示，從圖2、圖3、圖4中可以看出，相較于其它3種協(xié)議，基于DEGWO的簇首選擇算法在3種不同節(jié)點個數(shù)的場景下均能很好的將節(jié)點的生存時間延長。

圖2 場景1下的生命周期對比

圖3 場景2下的生命周期對比

圖4 場景3下的生命周期對比

在節(jié)點密度方面，隨著網(wǎng)絡(luò)中節(jié)點數(shù)量的不斷增加，網(wǎng)絡(luò)結(jié)構(gòu)變得復(fù)雜，合理的簇首選擇對均衡整個網(wǎng)絡(luò)的能耗的影響變得尤為突出。由于LEACH協(xié)議是根據(jù)閾值選取簇首，導(dǎo)致簇首的分布是隨機的，這樣雖然能保證每個節(jié)點成為簇首的可能性都是相等的，但是同時也導(dǎo)致了不合理的節(jié)點被選為簇首，加速了網(wǎng)絡(luò)中節(jié)點的死亡速度。LEACH-E協(xié)議中雖然在LEACH的基礎(chǔ)上將節(jié)點剩余能量的影響加入到簇首選擇閾值中，這樣可以使剩余能量較高的節(jié)點更容易被選為簇首節(jié)點，但是，其選擇簇首時仍然采用隨機的方式。導(dǎo)致LEACH-E協(xié)議相對于LEACH協(xié)議在延長網(wǎng)絡(luò)的生命周期方面能有一定的提升效果，但是，隨著節(jié)點數(shù)量的提升，提升效果變得越來越小。相對于LEACH協(xié)議與LEACH-E協(xié)議，F(xiàn)IGWO協(xié)議采用了改進灰狼優(yōu)化算法優(yōu)化簇首的選擇，使選擇的簇首變得相對合理，所以有一個較大的提升。但是，由于GWO存在容易陷入局部最優(yōu)解的問題，導(dǎo)致其優(yōu)化的簇首選擇并不一定為最優(yōu)。本文提出的基于DEGWO的簇首選擇算法，能夠根據(jù)網(wǎng)絡(luò)的結(jié)構(gòu)合理的對網(wǎng)絡(luò)進行劃分，針對GWO存在的缺點，使用DE算法對GWO進行變異、交叉操作，能夠避免GWO陷入局部最優(yōu)解，保證選擇的簇首集合為全局最優(yōu)。所以，相較于其它3種協(xié)議，本文所提的簇首選擇算法DEGWO對網(wǎng)絡(luò)生命周期方面有明顯的延長效果。并且，隨著節(jié)點數(shù)量的增加，仍然有一個明顯的提升效果。

為了更直觀對比網(wǎng)絡(luò)生命周期，以PND中第一個節(jié)點的死亡時間FND(first node dead)、一半節(jié)點的死亡時間HND(half node dead)、最后一個節(jié)點的死亡時間LND(last node dead)作為網(wǎng)絡(luò)生命周期的評估標(biāo)準(zhǔn)。場景1、場景2、場景3下FND、HND、LND的對比如圖5、圖6、圖7所示。其中，F(xiàn)ND、HND、LND具體數(shù)據(jù)見表3、表4、表5。

圖5 場景1下的PND對比

圖6 場景2下的PND對比

圖7 場景3下的PND對比

從圖5、圖6和圖7中可以看出，本文提出的DEGWO簇首選擇算法在不同節(jié)點密度的3個場景下對WSN生命周期的各個階段都有明顯延長。從表3、表4和表5中可以得出，相較于LEACH協(xié)議、LEACH-E協(xié)議、FIGWO協(xié)議，基于DEGWO的簇首選擇在第一個場景下將第一個節(jié)點的死亡時間延長了48.6%、16.6%、15.2%，將網(wǎng)絡(luò)的整個生命周期LND延長了77.9%、53.7%、12.9%，在場景2下將第一個節(jié)點的死亡時間延長了37.7%、21.4%、10.9%，網(wǎng)絡(luò)的整個生命周期LND延長了74.0%、44.9%、19.9%，場景3下，將第一個節(jié)點的死亡時間延長了33.0%、29.5%、5.8%，網(wǎng)絡(luò)的整個生命周期LND延長了66.0%、48.7%、4.7%。可見，隨著網(wǎng)絡(luò)中節(jié)點數(shù)量的增加，本文提出的簇首選擇算法在網(wǎng)絡(luò)的各個時間點對網(wǎng)絡(luò)的生命周期有較大程度的延長，這是由于DEGWO算法在網(wǎng)絡(luò)中選擇簇首時，使得最終的簇首集合在整個網(wǎng)絡(luò)中是全局最優(yōu)的。

表3 場景1下PND數(shù)據(jù)對比

表4 場景2下PND數(shù)據(jù)對比

表5 場景3下PND數(shù)據(jù)對比

4.3 網(wǎng)絡(luò)剩余能量

網(wǎng)絡(luò)剩余能量是WSN中所有存活節(jié)點的剩余能量之和。同一時間點下，網(wǎng)絡(luò)的剩余能量越多，說明網(wǎng)絡(luò)的能量消耗越均衡，能量利用率越高，網(wǎng)絡(luò)的服務(wù)時間也會越長。3種場景下網(wǎng)絡(luò)總剩余能量隨時間的變化如圖8、圖9和圖10所示，可以看出，本文提出的簇首選擇算法DEGWO總的剩余能量在各個時間點都高于其它3種協(xié)議。例如，在整個網(wǎng)絡(luò)運行到1000輪時，在場景1下，LEACH協(xié)議總的剩余能量百分比為9.87%，LEACH-E為23.62%，F(xiàn)IGWO為41.28%，而DEGWO為45.51%。在場景2下，LEACH協(xié)議總的剩余能量百分比為14.24%，LEACH-E為18.89%，F(xiàn)IGWO為37.01%，而DEGWO為46.22%，場景3下LEACH協(xié)議總的剩余能量百分比為15.44%，LEACH-E為18.68%，F(xiàn)IGWO為41.77%，而DEGWO為46.17%?？梢?，隨著網(wǎng)絡(luò)節(jié)點數(shù)量的增加，LEACH協(xié)議與LEACH-E協(xié)議之間總剩余能量的差距變得越來越小，雖然LEACH-E協(xié)議是在LEACH協(xié)議之上改進，但隨著網(wǎng)絡(luò)節(jié)點數(shù)量的增加，提升效果變得越來越差，可以得出，相較于LEACH協(xié)議，LEACH-E協(xié)議在大規(guī)模節(jié)點的情況下，在均衡能量消耗方面，并不能有一個很好提升的效果。相較于LEACH協(xié)議與LEACH-E協(xié)議，本文所提簇首選擇算法DEGWO與FIGWO協(xié)議使選擇的簇首更加合理，能更好均衡網(wǎng)絡(luò)中的能量消耗。從圖8、圖9、圖10中可以看出，相較于FIGWO協(xié)議，本文所提簇首算法表現(xiàn)更優(yōu)，并且隨著網(wǎng)絡(luò)節(jié)點數(shù)量的增加，均衡能耗的效果并沒有降低，反而有一個階段性的提升，可見，本文簇首選擇算法DEGWO在網(wǎng)絡(luò)節(jié)點數(shù)量增加時，均衡全局能量消耗的適應(yīng)性更好。

圖8 場景1下的總剩余能量對比

圖9 場景2下的總剩余能量對比

圖10 場景3下的總剩余能量對比

5 結(jié)束語

針對無線傳感器網(wǎng)絡(luò)中節(jié)點的能量消耗不均衡、網(wǎng)絡(luò)生存期短的問題，本文提出了一種基于DEGWO的簇首選擇算法，將差分進化算法與灰狼優(yōu)化算法混合，調(diào)整混合算法中的收斂因子與縮放因子，改善了灰狼算法易陷入停滯的缺點；隨后通過節(jié)點的剩余能量和節(jié)點與基站的距離設(shè)計適應(yīng)度函數(shù)，用于選擇網(wǎng)絡(luò)中最適合的節(jié)點作為簇首節(jié)點。仿真實驗結(jié)果表明，與LEACH、LEACH-E和FIGWO相比，本文提出的簇首選擇算法DEGWO能顯著延長網(wǎng)絡(luò)的生命周期、均衡網(wǎng)絡(luò)的能耗。下一步的研究中將對網(wǎng)絡(luò)中節(jié)點的路由方式進行研究，設(shè)計多跳路由，能更好優(yōu)化網(wǎng)絡(luò)的能耗、延長網(wǎng)絡(luò)的生存期。