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

張 新，俞宗佐

(內蒙古師范大學 計算機科學技術學院，內蒙古 呼和浩特 010000)

0 引 言

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

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

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

1 系統模型

1.1 網絡模型

對本文算法與對比算法所使用的網絡模型，做出如下假設：

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

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

(3)所有節點以固定速率測量環境參數，能夠根據到目標的距離調整其傳輸功率并定期向目標節點發送數據。

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

1.2 能量消耗模型

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

(1)

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

(2)

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

ERX(l)=lEelec

(3)

EDA(k)=lEda

(4)

其中，Eda表示節點融合1 bit數據所消耗的能量。

1.3 網絡生存期模型

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

(5)

其中，N是網絡中傳感器的數量。k是活動節點的數量。該式表明，PND的定義為活動節點與初始節點個數的比例下降到閾值ξ的時間。

2 基本算法

2.1 灰狼優化算法

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

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

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

(6)

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

(7)

其中，t表示當前迭代次數，A和C表示系數向量，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之間的整數，并且在迭代過程中每次增加1。maxIter為最大迭代次數。因此，a(t)在迭代過程中，從2到0線性遞減。

包圍獵物后，GWO執行狩獵過程以不斷更新自己的位置，狩獵行為的數學模型如式(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算法主要經過種群的初始化、變異、交叉、選擇4個過程[13]。其各數學模型描述如下：

(1)初始化

(14)

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

(2)變異

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

(15)

(3)交叉

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

(16)

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

(4)選擇

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

(17)

3 基于DEGWO算法的簇首選擇

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

3.1 形成初始簇

在WSN中，簇首比普通節點消耗的能量多，所以，保證簇首在網絡中均勻分布至關重要。基于DEGWO的簇首選擇算法，首先采用均值法選取初始簇首，并且形成初始簇，然后在每個簇中使用DEGWO選擇最終簇首，使用均值法選取初始簇首并形成初始簇的步驟如下：

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

步驟2 根據3.2.4節中適應度函數式(21)計算每個存活節點的適應度。

步驟3 對步驟2中計算出的適應度進行排序。

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

步驟5 計算每個集合中的適應度值的平均值。

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

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

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

3.2 使用DEGWO選擇最終簇首

3.2.1 DEGWO算法選擇簇首

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

步驟1 初始化參數。

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

步驟3 根據3.2.4節中的適應度函數式(21)計算父代個體的適應度值。

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

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

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

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

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

步驟9 更新參數a、A、C。

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

步驟11 得到最優位置，距離最優位置的節點即當選為簇首。

3.2.2 優化收斂因子

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

(18)

其中，iter為當前迭代次數，maxIter為最大迭代次數。

3.2.3 調整縮放因子

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

3.2.4 適應度函數設計

能量是節點最大的挑戰，簇首節點的能量消耗比普通節點多。選擇能量較高的節點作為簇首有助于平衡網絡的能量消耗。因此，設計適應度函數中能量部分f1如式(19)所示

(19)

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

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

(20)

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

綜上所述，適應度值函數設計如式(21)所示

Fitness=uf1+(1-u)f2

(21)

其中，Fiteness為適應函數，u為權重系數。

3.3 數據傳輸

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

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

4 仿真結果與分析

4.1 仿真環境與實驗參數

本文使用Matlab R2014b對本文所提算法DEGWO與LEACH、LEACH-E、FIGWO這3種協議進行仿真實驗，并以網絡生命周期中PND中的3個指標和網絡總能量消耗為標準進行比較。為驗證所提算法對多節點的適應性，設計了3種不同節點個數的網絡場景進行實驗，3種實驗場景見表1。

表1 3種網絡場景

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

表2 仿真實驗參數

4.2 網絡生命周期

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

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

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

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

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

為了更直觀對比網絡生命周期，以PND中第一個節點的死亡時間FND(first node dead)、一半節點的死亡時間HND(half node dead)、最后一個節點的死亡時間LND(last node dead)作為網絡生命周期的評估標準。場景1、場景2、場景3下FND、HND、LND的對比如圖5、圖6、圖7所示。其中，FND、HND、LND具體數據見表3、表4、表5。

圖5 場景1下的PND對比

圖6 場景2下的PND對比

圖7 場景3下的PND對比

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

表3 場景1下PND數據對比

表4 場景2下PND數據對比

表5 場景3下PND數據對比

4.3 網絡剩余能量

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

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

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

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

5 結束語

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