無線傳感器網絡能量高效分簇的一種改進方法

竇佩佩，曾玉琴，盧 毅，馬洪亮，徐夢穎，周 杰

(石河子大學 信息科學與技術學院，新疆維吾爾自治區 石河子 832003)

無線傳感器網絡通常由大量廉價的微型傳感器節點構成。無線傳感器網絡融合了無線通信技術、傳感器技術、嵌入式計算技術等關鍵技術，網絡中的傳感器節點能夠對外部環境中的對象進行監測并采集相關數據[1-2]。隨著相關技術的飛速發展，無線傳感器網絡在軍事、醫學、農業、工業、環境監測等領域的應用變得更加廣泛[3-7]，在防震、航空等特殊領域也表現出了相應價值[8-9]。隨著5G技術的蓬勃發展，未來無線傳感器網絡在智能灌溉、智慧城市等領域將有廣闊的發展空間[10-12]。

在無線傳感器網絡內，傳感器節點的部署位置通常較為隨機。由于大多數傳感器節點體積較小且由電池供電，其能源總量受到限制，故降低網絡能耗、提高能源利用率是無線傳感器網絡的一個重要研究方向。研究表明，采用分簇算法對網絡中的傳感器節點進行分簇能夠有效地降低網絡能耗。分簇算法將無線傳感器網絡內的傳感器節點分成若干個節點簇，每一個節點簇中包含多個成員節點和一個簇頭節點。簇頭節點主要用于匯集數據處理結果和發放監測任務，成員節點主要用于監測。當上行傳輸數據時，成員節點首先將采集到的監測對象相關數據信息進行處理，然后把處理結果發送給所屬簇的簇頭節點；在下行傳輸數據時，各個成員節點接收來自所屬簇中的簇頭節點發放的監測任務。簇頭節點和成員節點在數據傳輸的過程中會消耗較多能量，因此尋找合適的簇頭節點是降低網絡通信能耗的關鍵。

針對如何降低無線傳感器網絡能耗、延長網絡壽命這一問題，文獻[13]提出了一種基于模糊聚類和粒子群算法的簇頭選擇方法，利用模糊算法初始聚類，然后利用粒子群算法選擇簇頭節點。該算法能夠有效地降低節點的死亡率，但當網絡中節點的部署密度較大時，算法復雜度也隨之增長，算法的搜索效率也跟著下降。文獻[14]提出了一種灰狼優化算法，該算法能夠有效降低網絡能耗，但存在收斂速度不夠理想的缺點。文獻[15]提出了一種蟻群算法，該算法能夠有效縮短收斂時間，但容易陷入局部最優。文獻[16]提出了一種基于模糊邏輯的土狼優化聚類方法，先利用模糊邏輯算法獲得初始分簇方案，再利用土狼優化算法進行優化；該算法有效延長了無線傳感器網絡壽命，但分簇方案中的簇頭節點分布較為不均勻。文獻[17]提出了一種改進的人工蜂群算法進行分簇，該算法能夠合理地選出簇頭節點，但算法易陷入進化停滯。

針對以上問題，筆者提出了一種基于克隆精英遺傳算法的分簇方法，且將其和基于精英遺傳算法的分簇方法、基于蛙跳算法的分簇方法進行了仿真比較。從仿真結果中可以看出，基于克隆精英遺傳算法的分簇方法能夠找到更加合適的簇頭節點進行合理分簇，且網絡能耗明顯低于基于精英遺傳算法的分簇方法和基于蛙跳算法的分簇方法。

1 無線傳感器網絡分簇模型

在監測范圍內節點隨機分布的無線傳感器網絡分簇結構如圖1所示。在大多數無線傳感器網絡中，通信能耗占網絡能耗總量的一半以上，故分簇時需要重點考慮如何降低發送和接收數據時的通信能耗。將大小為bbit的數據包發送到距離為d的接收節點時所消耗的能量為

圖1 無線傳感器網絡分簇結構

Es(b，d)=bEelec+bεampdi。

(1)

接收節點接收大小為b的數據包所消耗的能量為

Er(b)=bEelec，

(2)

其中，Eelec表示電子能量參數，εamp表示功率放大參數。i的取值主要取決于所處的環境，周圍的環境越差，i的值就越大。通常i的取值范圍是[2，4]。

2 基于克隆精英遺傳算法的無線傳感器網絡分簇方法

2.1 克隆精英遺傳算法

遺傳算法(Genetic Algorithm，GA)最早是由美國的 John Holland于20世紀70年代提出的。它是一種能夠在全局中進行尋優搜索的算法，具有隨機、迭代和進化等特點。但是它在對簇頭節點方案進行選擇、交叉和變異操作時，很有可能會破壞原本較好的簇頭節點方案，使得新一代簇頭節點方案網絡能耗可能高于上一代簇頭節點方案的網絡能耗的情況。為了保證迭代過程中簇頭節點方案不斷優化，網絡能耗越來越低，將克隆算子和精英算子引入遺傳算法，以增加最佳總體解決方案的可能性。

2.2 算法流程

基于克隆精英遺傳算法的無線傳感器網絡分簇方法的基本流程是：在擁有一定數量傳感器節點的監測范圍內，選擇一定比例的節點當作簇頭節點，接著將未被選擇的節點列入距離其最近的簇頭節點所在簇內，可以得到在當前的簇頭節點方案下的網絡通信能耗，然后利用克隆精英遺傳算法優化當前的簇頭節點方案，通過不斷優化使得網絡通信能耗越來越小。算法的具體步驟如下，

(1) 編碼。克隆精英遺傳算法的一個重要步驟就是編碼，其將能量高效分簇問題轉換為克隆精英遺傳算法能夠處理的問題。在選擇、交叉和變異的過程中，編碼的好壞對算法運行效率有著直接的影響。采用二進制向量的方式對節點進行編碼，二進制向量中的每一位代表一個傳感器節點，也就是代表一個基因位點。

(2) 初始化種群。在基于克隆精英遺傳算法的分簇方法中，初始化種群時采用隨機生成的方法。例如在一定的監測范圍內有m個傳感器節點，對這m個傳感器節點進行長度為m的二進制編碼。從這m個傳感器節點中隨機選擇一定比例的節點作為簇頭節點，并將二進制向量中簇頭節點對應位置的值設為1，這樣該向量就代表了一個個體。以同樣的方法依次生成n個個體，這些個體就組成了初始種群，也就是初始的n個簇頭節點方案。

(4) 選擇。能量高效分簇是一個求解最小值的問題，在基于克隆精英遺傳算法的分簇方法中，利用克隆算子對簇頭節點方案進行選擇。將簇頭節點方案按照能耗從小到大進行排序，按照一定的比率克隆能耗較小的簇頭節點方案，對克隆后的方案以較高的變異概率實施變異，從而組成新的種群。此時種群是由原種群中最優的幾個簇頭節點方案經過克隆和變異生成的，能量消耗小的分簇方案盡可能地保留了下來。

(5) 交叉。在使用克隆精英遺傳算法解決無線傳感器網絡分簇問題的過程中，對簇頭節點方案進行兩兩交叉，即隨機選擇一個交叉點將兩個簇頭節點方案中的相應基因位點進行交換。若兩個簇頭節點方案中有部分相同的基因位點，則可能出現交叉后兩個方案沒有任何變化的情況。為了避免這種情況的發生，先將兩個方案中相同的基因位點剔除，然后對剔除相同基因位點后的兩個方案進行交叉。交叉后，再將被剔除掉的相同基因位點重新加入到方案中，以保證方案中簇頭節點數目和比例不變。種群中的所有個體都按順序進行兩兩交叉，這樣就通過交叉操作生成了新的種群。

(6) 變異。在解決無線傳感器網絡分簇問題的過程中，克隆精英遺傳算法在變異過程中采用的是隨機變異的方法。從種群中隨機選擇簇頭節點方案，然后隨機反轉方案中的部分基因位點，并將新生成的個體當作新的簇頭節點方案，這樣就形成了新的種群。在變異時，由1翻轉至0的基因位點和由0翻轉至1的基因位點數量相同，因此變異操作過程中簇頭節點數目和比例不變。

(7) 精英個體的保留和更新。在使用克隆精英遺傳算法解決無線傳感器網絡分簇時，將上一代通信能耗最低的簇頭節點方案與當前迭代過程中通信能耗最低的簇頭節點方案進行對比。如果上一代最低通信能耗高于當前迭代過程中的最低通信能耗，那么就將本代精英個體更新為當前迭代過程中通信能耗最低的簇頭節點方案，否則直接將上一代精英個體作為本代精英個體。

(8) 迭代結束。判斷基于克隆精英遺傳算法的分簇方法迭代過程是否結束時，如果達到設定的迭代次數時，就結束迭代并輸出精英個體作為最優簇頭節點方案；否則，重復選擇交叉變異等操作過程。

3 仿真及結果分析

在無線傳感器網絡中，大部分傳感器節點上行發送數據的通信能耗遠大于其接收下行控制指令時的通信能耗，所以在此仿真實驗中只考慮節點在上行發送數據時的通信能耗。實驗在Windows 10系統、 酷睿i5處理器、 8 GB內存的PC機上，通過Matlab R2015b軟件進行仿真。在仿真實驗中，設置簇頭節點的比率為10%，網絡能耗利用式(1)計算。公式中的各個參數的取值為，數據包大小b的值取為1 KB，i的值取為3，Eelec的值取為50 nJ/bit，εamp的值取為100 pJ/(bit·m-2)。

在400 m×400 m的監測范圍內隨機部署傳感器節點，利用基于克隆精英遺傳算法的分簇方法、基于精英遺傳算法的分簇方法和基于蛙跳算法的分簇方法對WSN的網絡能耗進行優化。所提分簇方法中基因位點設為100個，變異概率設為0.1，過高的變異概率容易使算法陷入局部最優。基于精英遺傳算法的分簇方法中基因位點設為100個，變異概率設為0.1。基于蛙跳算法的分簇方法中青蛙種群數設為20個，每個種群有5只青蛙，組內迭代數為10。

圖2和圖3是傳感器節點數為100和200時，基于克隆精英遺傳算法的分簇方法、基于精英遺傳算法的分簇方法和基于蛙跳算法的分簇方法選出的簇頭節點產生的能耗隨迭代次數的變化。從圖2中可以看到，基于克隆精英遺傳算法的分簇方法的最低能耗約為1.475 8 J，基于精英遺傳算法的分簇方法的最低能耗約為1.557 9 J，基于蛙跳算法的分簇方法的最低能耗約為1.643 2 J。基于克隆精英遺傳算法的分簇方法優化結果比基于精英遺傳算法的分簇方法的優化結果好約5.27%，比基于蛙跳算法的分簇方法優化結果好約10.19%。從圖3中可以看到，基于克隆精英遺傳算法的分簇方法的最低能耗約為1.102 2 J，基于精英遺傳算法的分簇方法的最低能耗約為1.178 5 J，基于蛙跳算法的分簇方法的最低能耗約為1.517 1 J。基于克隆精英遺傳算法的分簇方法優化結果比基于精英遺傳算法的分簇方法的優化結果好約6.47%，比基于蛙跳算法的分簇方法優化結果好約27.35%。基于克隆精英遺傳算法的分簇方法在降低網絡能耗上的效果明顯比另外兩種分簇方法分簇方法好，對延長網絡壽命有顯著作用。

圖2 能耗對比(傳感器節點數為100)

圖3 能耗對比(傳感器節點數為200)

為了更加直觀地看到3種分簇方法選出的簇頭節點的分布情況，利用3種分簇方法對100個傳感器節點進行分簇，結果如圖4至圖6所示。從圖4至圖6中可以看出，利用所提方法和基于精英遺傳算法的分簇方法選出的分簇方案中，簇頭節點分布較為均勻。而利用基于蛙跳算法的分簇方法選出的簇頭節點分布較為不均勻，部分簇頭節點之間的距離較近。圖7為3種分簇方法對100個傳感器節點進行分簇的成簇情況，一條數據表示一個簇中的成員節點數。在圖7中可以看到，所提方法的分簇方案中每個簇內的成員節點數目較為平均，基于精英遺傳算法的分簇方法的分簇方案中成員節點數目較不平均，而基于蛙跳的分簇方法中成員節點數目不一。綜上所述，基于克隆精英遺傳算法的分簇方法的分簇方案，簇頭節點分布均勻，成員節點數目平均，比另外兩種分簇方法的分簇方案更為合理。

圖4 基于克隆精英遺傳算法的分簇方法分簇結果

圖5 基于精英遺傳算法的分簇方法分簇結果

圖6 基于蛙跳算法的分簇方法分簇結果

圖7 3種分簇方法的分簇結果對比(100個節點)

表1為圖2和圖3中3種方法的運行時間對比。從表1中可以看出，基于蛙跳算法的分簇方法的運行時間最長，且隨著網絡節點密度的增加，運行時間也增加得更多。基于克隆精英遺傳算法的分簇方法的運行時間比基于精英遺傳算法的分簇方法的運行時間略小，但其最終優化的網絡能耗低于基于精英遺傳算法的分簇方法的，即基于克隆精英遺傳算法的分簇方法在保證優化效果的同時，擁有較低的時間復雜度。

表1 運行時間對比 s

4 結束語

為了有效提高能源利用率、降低無線傳感器網絡能耗，筆者給出了一種基于克隆精英遺傳算法的分簇方法，用來找出合適的簇頭節點以降低無線傳感器網絡的通信能耗。將基于克隆精英遺傳算法的分簇方法與基于精英遺傳算法的分簇方法、基于蛙跳算法的分簇方法分別從不同節點數下能量消耗、簇頭節點分布、簇內成員節點數目以及運行時間進行仿真比較。仿真結果顯示，基于克隆精英遺傳算法的分簇方法在優化網絡能耗上的效果優于基于精英遺傳算法的分簇方法和基于蛙跳算法的分簇方法，有效地延長了網絡壽命，且分簇結果中簇頭節點分布與簇內節點數較為合理，算法運行時間較短。