基于混沌遺傳算法的無線傳感器網絡改進LEACH算法

李 蛟, 胡黃水, 趙宏偉, 魯曉帆

(1. 吉林大學 圖書館, 長春 130012； 2. 吉林建筑科技學院 計算機科學與工程學院, 長春 130114；3. 吉林大學 計算機科學與技術學院, 長春 130012)

無線傳感器網絡(wireless sensor networks, WSNs)是實際應用中最基本的信息采集技術之一, 其通過內置各種傳感器節點測量周圍環境中的熱、 紅外、 聲納和地震等信號. 由于無線傳感器網絡節點能量等資源有限, 因此如何節約能量以延長網絡生命周期是無線傳感器網絡面臨的重要挑戰, 而分簇是一種有效的方法[1]. LEACH(low energy adaptive clustering hierarchy)是面向無線傳感器網絡的最早分簇協議[2], 算法復雜度低, 能量效率和可擴展性相比分布式方法更好. 但基于概率隨機選舉簇頭CH(cluster head)、 成員CM(cluster member)僅根據接收信號強度大小加入簇以及忽略簇頭節點剩余能量、 單跳等將導致LEACH簇頭、 能耗、 負載分布不均衡, 從而縮短網絡的生命周期[3]. 于是, 出現了很多改進LEACH算法以提高其性能[4]. 為避免LEACH協議簇頭選取不合理導致能耗增大, 文獻[5-6]考慮利用節點剩余能量以及節點分布密度修正LEACH閾值函數, 分別提出了改進的LEACH算法LEACH-N和LEACH-C, 并根據節點分布密度調整節點傳輸功率, 從而均衡網絡能量消耗. 但減小節點傳輸功率將增加網絡簇數, 降低數據融合率并增加傳輸數據量, 從而增大網絡能耗. 且簇頭選舉不考慮節點位置, 易使位于簇邊緣的節點被選為簇頭, 增大簇內通信能耗. 因此, 文獻[7]提出了一種改進的LEACH算法NEWLEACH, 其在定義閾值函數時, 不僅考慮節點的剩余能量, 同時考慮節點到簇中心距離以及節點到基站距離, 使剩余能量多、 位置更佳的節點成為簇頭的概率更大. 但其并未考慮節點負載情況, 且不能處理簇頭選舉過程的不確定因素. 而通常模糊邏輯對網絡中存在大量不確定性時仍能產生較好的結果[8], 于是文獻[9]提出了一種基于模糊C-均值(FCM)的改進LEACH算法, 其采用FCM劃分區域, 每個區域為一個簇, 將剩余能量大的節點作為簇頭. 但FCM初始時隨機選取節點成為簇頭導致收斂速度慢, 形成的簇中心也并不準確[10], 此外未考慮節點間距離以及簇頭與基站間距離將導致距離遠的節點出現早死現象.

上述LEACH改進算法都能在一定程度上提高LEACH的性能, 但很難獲得全局最優解. 而遺傳算法具有良好的全局搜索能力, 因此文獻[11-12]采用遺傳算法選舉簇頭, 并根據適應度值修改交叉和變異概率因子, 從而均衡網絡能量消耗. 但適應度函數僅考慮剩余能量, 易產生分布不均的簇, 尤其是傳統遺傳算法收斂速度慢, 容易陷入局部最優. 而混沌遺傳算法具有避免搜索過程局部優化、 隨機性和遍歷性等優點[13]. 因此本文提出一種基于混沌遺傳算法的改進LEACH算法CGA-LEACH(an improved LEACH algorithm for wireless sensor network based on chaotic genetic algorithm)最小化網絡能耗, 延長網絡生命周期. 為實現該目標, CGA-LEACH構建了考量能量和負載的適應度函數, 基于該函數值進行混沌遺傳選擇、 交叉和變異操作, 找到最優簇頭及其相應的簇成員, 從而形成優化的簇結構. 從能量效率以及生命周期方面對CGA-LEACH與其他相關算法進行仿真分析的結果驗證了算法性能.

1 網絡模型

在CGA-LEACH中, 將n個具有唯一ID能量受限的節點隨機部署在目標感知區域. 與LEACH和文獻[11-12]相同, 簇被用于組織網絡中的節點, 每個簇中選出一個節點作為簇頭管理簇, 其他節點作為成員節點. 所有成員節點都只能與其簇頭進行通信, 簇頭接收各成員節點信息, 融合后直接發送給基站. 一旦完成部署, 節點和基站都保持靜止, 所有節點具有相同的初始能量, 基站能量無限, 節點間距離可通過接收信號強度計算, 節點間通信采用雙向鏈路. 為計算節點能量消耗, 采用一階無線電模型, 即節點i發送l位數據到節點j, 其消耗的能量為

(1)

ERij=l×Eelec,

(2)

簇頭融合l位數據消耗的能量為

EDA=l×EpDb,

(3)

其中EpDb表示融合單位數據消耗的能量.

2 CGA-LEACH設計

CGA-LEACH采用混沌遺傳搜索最優簇頭, 一個可能解用實數編碼的染色體(也稱為個體)表示, 所有染色體構成初始種群. 在每個染色體中, 由節點ID表示的每個基因代表對應節點的簇頭, 如圖1所示. 圖1中第一行為普通節點ID, 第二行為每個普通節點對應的簇頭節點ID. 由圖1可見, 染色體不僅能表示每個成員的簇頭, 同時也能表示每個簇頭包含的簇成員, 這樣可減少大量成簇報文, 從而降低能耗. 此外, 由于Logistic混沌映射具有對初值敏感、 良好的隨機序列生成、 能遍歷混沌區域所有狀態點以及不可預測等特點, 因此被用于生成染色體基因, 表示為

圖1 CGA-LEACH中的染色體表示Fig.1 Representation of chromosome in CGA-LEACH

(4)

其中:μ是控制參數, 且當μ>3.57,zi≠0.25,0.5,0.75時, 系統進入混沌狀態, 與文獻[12]相同,μ=4;b為基因最大值,b=n.為避免產生不合理的染色體并提高收斂速度, 僅選擇位于節點通信范圍內且剩余能量大于平均鄰居剩余能量的節點作為簇頭, 即

(5)

其中:H={h1,h2,…,hi,…,hk}為簇頭節點集,dihi表示節點i與其簇頭hi之間的距離,dmax表示所有節點最大通信范圍,Ereshi表示簇頭節點hi的剩余能量,Eresj表示節點j的剩余能量,nMi為節點i的鄰居節點數.如圖1所示, 網絡由10個節點構成, 簇頭數k=4, 簇成員總數m=6, 隨機選擇簇頭H={3,5,8,9}, 則簇成員CM={1,2,4,6,7,10}, 基于式(4)和式(5)隨機生成一個染色體, 可得節點1和4的簇頭為節點3, 節點2和7的簇頭為節點5, 節點6的簇頭為節點8, 節點10的簇頭為節點9.同時可知, 簇頭3的成員有{1,4}, 簇頭5的成員有{2,7}, 簇頭8的成員有{6}, 簇頭9的成員有{10}.以此類推, 直到產生所需的初始種群.然后構建適應度函數評價每個個體的質量, 由于CGA-LEACH主要目標是最小化網絡能耗及均衡網絡負載, 因此適應度函數考量網絡能耗和負載.網絡的總能耗為

(6)

其中ETiBS表示簇頭i與基站之間的通信能耗.則第p個個體的總能耗歸一化表示為

(7)

其中netEmin,netEmax分別為種群中個體最小和最大總能耗.此外, 網絡負載均衡用簇頭單位數據所需剩余能量表示, 即

(8)

則個體的負載均衡歸一化表示為

(9)

其中ltoEmin,ltoEmax分別為簇頭中負載均衡最大和最小值.于是, 適應度函數可定義為

(10)

由式(10)可見, 適應度越大的個體越接近最優解, 即此時的網絡能耗越小且負載越均衡.CGA-LEACH以能耗最低和負載均衡為目標, 并通過混沌遺傳算法搜索其最優解, 與LEACH等未考慮網絡能耗的協議相比, 網絡能耗更低. 采用適應度函數計算初始種群中每個個體的適應度函數值, 并按從小到大排列. 遺傳選擇采用與文獻[11-12]中類似的精英選擇而不是傳統的輪盤賭選擇方法, 適應度函數值大的為精英個體, 直接選至下一代, 其中精英個體占比為10%, 其他依次與由式(4)隨機生成的個體比較適應度函數值大小, 適應度函數值大的進入交叉操作, 這樣既保證了種群的多樣性又加速了算法收斂. 之后對種群采用單點交叉操作, 如圖2所示.

圖2 CGA-LEACH中的單點交叉操作Fig.2 Single-point crossover operation in CGA-LEACH

如果生成的子個體大于其父個體的適應度函數值, 則直接進入變異操作. 否則與由式(4)隨機生成的個體比較適應度函數值大小, 適應度函數值大的進入交叉操作. 同理, 當變異產生的子個體小于其父個體的適應度函數值時, 也與由式(4)隨機生成的個體比較適應度函數值大小, 適應度函數值大的進入下一代. 依此迭代運行遺傳操作, 直到達到最大迭代次數或找到最優解, 此時找到了最優簇頭以及各簇頭對應的成員, 其流程如圖3所示.

圖3 簇頭搜索流程Fig.3 Flow chart of cluster head search

3 仿真分析

為驗證CGA-LEACH的性能, 在MATLAB環境下對其進行仿真測試, 并與LEACH[2]以及文獻[12]中提出的RPBGK進行比較分析. 網絡中100個節點隨機分布在100 m×100 m的目標區域, 基站位于中心(50 m,50 m), 仿真參數設置列于表1.

表1 仿真參數

首先對網絡的能量消耗進行測試, 結果如圖4所示. 由圖4可見, LEACH的能量消耗最高, 其次是RPBGK, CGA-LEACH的能耗最低. 因為LEACH采用隨機成簇導致分簇不均勻, 一些簇頭遠離基站, 消耗較高. RPBGK通過遺傳K-means算法進行分簇并采用改進的簇頭選舉方法, 通過多跳方式與基站通信, 從而降低了網絡能量消耗, 但RPBGK會產生多個較遠簇頭向某個離基站較近的簇頭轉發數據的現象, 從而使離基站較近的簇頭負擔過重而導致能量消耗不均勻. CGA-LEACH考量了網絡能耗和負載均衡構建適應度函數, 生成了均勻的簇, 避免了RPBGK中能耗不均勻現象發生, 而且CGA-LEACH相對減少了成簇控制報文, 從而降低了網絡能量消耗. 因此, CGA-LEACH具有最高的能量效率.

圖4 網絡能量消耗Fig.4 Network energy consumption

由于節點能量資源有限, 作為層次型的無線傳感器網絡, 簇頭在每一階段都需要比普通節點消耗更多的能量. 因此, 簇頭的能量消耗偏差是網絡性能的重要評價指標, 其表明了網絡的能耗均衡性. 不同算法簇頭的能量消耗偏差如圖5所示. 由圖5可見: RPBGK采用遺傳K-means成簇, 比LEACH隨機成簇更均勻, 因此其能量消耗偏差比LEACH更好； 而CGA-LEACH 在網絡運行中考慮了簇頭的負載, 使每個簇的能量消耗相對均衡, 因此相比LEACH和RPBGK算法, CGA-LEACH具有最低的簇頭能耗偏差, 分別比RPBGK和LEACH平均降低了40.54%,50%. 因此CGA-LEACH在提高簇頭節點的能量效率方面也具有優勢.

圖5 簇頭的能量消耗偏差Fig.5 Energy consumption deviation of cluster heads

圖6為CGA-LEACH,RPBGK和LEACH之間的存活節點個數隨著輪數增加的變化. 由圖6可見: LEACH的存活節點個數在648輪后迅速下降, 在1 194輪后僅剩1個節點; RPBGK的存活節點個數在201輪后開始下降, 在2 268輪網絡的所有節點全部死亡; 而CGA-LEACH的存活節點個數在361輪后開始緩慢下降, 直至3 465輪所有節點全部死亡. 這是因為CGA-LEACH考量了網絡能耗和負載兩個指標構造新的適應度函數, 從而找到了能耗最低和負載最均衡的簇, 延長了網絡的生命周期.

圖6 網絡的存活節點數Fig.6 Number of surviving nodes in network

綜上所述, CGA-LEACH基于遺傳算法的全局搜索能力形成網絡能量最小的簇, 單個實數編碼的染色體既能表達選擇的簇頭, 又能確定各簇頭對應的成員, 減少了成簇階段大量的控制報文數, 降低了網絡能耗. 本文構建的適應度函數既考慮了網絡能耗又考慮了簇頭負載, 使形成的簇分布更均勻. 混沌計算既用于初始化種群, 又融入遺傳選擇、 交叉和變異操作, 在豐富種群多樣性的同時提高了算法收斂速度和避免算法陷入局部最優. 從能量消耗、 負載均衡以及網絡的存活節點個數方面對算法進行仿真分析的結果表明, CGA-LEACH能有效提高網絡能量效率, 延長網絡生命周期.