基于混沌遺傳算法的無線傳感器網(wǎng)絡(luò)改進(jìn)LEACH算法

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

(1. 吉林大學(xué) 圖書館, 長(zhǎng)春 130012； 2. 吉林建筑科技學(xué)院 計(jì)算機(jī)科學(xué)與工程學(xué)院, 長(zhǎng)春 130114；3. 吉林大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 長(zhǎng)春 130012)

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

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

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

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

(1)

ERij=l×Eelec,

(2)

簇頭融合l位數(shù)據(jù)消耗的能量為

EDA=l×EpDb,

(3)

其中EpDb表示融合單位數(shù)據(jù)消耗的能量.

2 CGA-LEACH設(shè)計(jì)

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

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

(4)

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

(5)

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

(6)

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

(7)

其中netEmin,netEmax分別為種群中個(gè)體最小和最大總能耗.此外, 網(wǎng)絡(luò)負(fù)載均衡用簇頭單位數(shù)據(jù)所需剩余能量表示, 即

(8)

則個(gè)體的負(fù)載均衡歸一化表示為

(9)

其中l(wèi)toEmin,ltoEmax分別為簇頭中負(fù)載均衡最大和最小值.于是, 適應(yīng)度函數(shù)可定義為

(10)

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

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

如果生成的子個(gè)體大于其父?jìng)€(gè)體的適應(yīng)度函數(shù)值, 則直接進(jìn)入變異操作. 否則與由式(4)隨機(jī)生成的個(gè)體比較適應(yīng)度函數(shù)值大小, 適應(yīng)度函數(shù)值大的進(jìn)入交叉操作. 同理, 當(dāng)變異產(chǎn)生的子個(gè)體小于其父?jìng)€(gè)體的適應(yīng)度函數(shù)值時(shí), 也與由式(4)隨機(jī)生成的個(gè)體比較適應(yīng)度函數(shù)值大小, 適應(yīng)度函數(shù)值大的進(jìn)入下一代. 依此迭代運(yùn)行遺傳操作, 直到達(dá)到最大迭代次數(shù)或找到最優(yōu)解, 此時(shí)找到了最優(yōu)簇頭以及各簇頭對(duì)應(yīng)的成員, 其流程如圖3所示.

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

3 仿真分析

為驗(yàn)證CGA-LEACH的性能, 在MATLAB環(huán)境下對(duì)其進(jìn)行仿真測(cè)試, 并與LEACH[2]以及文獻(xiàn)[12]中提出的RPBGK進(jìn)行比較分析. 網(wǎng)絡(luò)中100個(gè)節(jié)點(diǎn)隨機(jī)分布在100 m×100 m的目標(biāo)區(qū)域, 基站位于中心(50 m,50 m), 仿真參數(shù)設(shè)置列于表1.

表1 仿真參數(shù)

首先對(duì)網(wǎng)絡(luò)的能量消耗進(jìn)行測(cè)試, 結(jié)果如圖4所示. 由圖4可見, LEACH的能量消耗最高, 其次是RPBGK, CGA-LEACH的能耗最低. 因?yàn)長(zhǎng)EACH采用隨機(jī)成簇導(dǎo)致分簇不均勻, 一些簇頭遠(yuǎn)離基站, 消耗較高. RPBGK通過遺傳K-means算法進(jìn)行分簇并采用改進(jìn)的簇頭選舉方法, 通過多跳方式與基站通信, 從而降低了網(wǎng)絡(luò)能量消耗, 但RPBGK會(huì)產(chǎn)生多個(gè)較遠(yuǎn)簇頭向某個(gè)離基站較近的簇頭轉(zhuǎn)發(fā)數(shù)據(jù)的現(xiàn)象, 從而使離基站較近的簇頭負(fù)擔(dān)過重而導(dǎo)致能量消耗不均勻. CGA-LEACH考量了網(wǎng)絡(luò)能耗和負(fù)載均衡構(gòu)建適應(yīng)度函數(shù), 生成了均勻的簇, 避免了RPBGK中能耗不均勻現(xiàn)象發(fā)生, 而且CGA-LEACH相對(duì)減少了成簇控制報(bào)文, 從而降低了網(wǎng)絡(luò)能量消耗. 因此, CGA-LEACH具有最高的能量效率.

圖4 網(wǎng)絡(luò)能量消耗Fig.4 Network energy consumption

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

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

圖6為CGA-LEACH,RPBGK和LEACH之間的存活節(jié)點(diǎn)個(gè)數(shù)隨著輪數(shù)增加的變化. 由圖6可見: LEACH的存活節(jié)點(diǎn)個(gè)數(shù)在648輪后迅速下降, 在1 194輪后僅剩1個(gè)節(jié)點(diǎn); RPBGK的存活節(jié)點(diǎn)個(gè)數(shù)在201輪后開始下降, 在2 268輪網(wǎng)絡(luò)的所有節(jié)點(diǎn)全部死亡; 而CGA-LEACH的存活節(jié)點(diǎn)個(gè)數(shù)在361輪后開始緩慢下降, 直至3 465輪所有節(jié)點(diǎn)全部死亡. 這是因?yàn)镃GA-LEACH考量了網(wǎng)絡(luò)能耗和負(fù)載兩個(gè)指標(biāo)構(gòu)造新的適應(yīng)度函數(shù), 從而找到了能耗最低和負(fù)載最均衡的簇, 延長(zhǎng)了網(wǎng)絡(luò)的生命周期.

圖6 網(wǎng)絡(luò)的存活節(jié)點(diǎn)數(shù)Fig.6 Number of surviving nodes in network

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