基于混沌克隆遺傳算法的無線傳感器網(wǎng)絡低能耗分簇方法

楊瑞，周杰

(石河子大學信息科學與技術學院，新疆 石河子 832003)

無線傳感器網(wǎng)絡通常由大量傳感器節(jié)點組成，這些節(jié)點隨機分布在監(jiān)測區(qū)域內(nèi)，多數(shù)無需基礎設施支撐網(wǎng)絡運行，并且自組織成簇[1-2]。隨著嵌入式和無線通信技術的創(chuàng)新和進步，部分應用場景下的無線傳感器網(wǎng)絡節(jié)點體積已經(jīng)越來越小。體積的減小使無線傳感器網(wǎng)絡的應用范圍更加廣闊，同時也降低了使用成本[3-4]。無線傳感器的部署效率較高，同時擁有強大的環(huán)境適應能力，因而在國防和軍事、智能家居、農(nóng)業(yè)工程、環(huán)境監(jiān)測等眾多領域有著廣泛的應用[5-6]。

在隨機部署方式下，無線傳感器網(wǎng)絡的傳感器節(jié)點經(jīng)常由無人機隨機拋灑至指定目標區(qū)域。這種隨機部署方式雖然降低了部署成本，卻無法保證傳感器節(jié)點分布的合理性，從而導致部分區(qū)域出現(xiàn)覆蓋空洞或者重疊覆蓋的情況，進而導致監(jiān)測效果不佳以及部分傳感器節(jié)點能量的浪費[7]。因此，如何對網(wǎng)絡進行有效分簇并在確保完成監(jiān)測任務的同時降低網(wǎng)絡能耗，是無線傳感器網(wǎng)絡研究中的一個重要問題。目前，已有部分專家學者提出許多低能耗分簇算法來優(yōu)化無線傳感器網(wǎng)絡通信能耗[8-9]。

王磊[10]提出了一種粒子群算法(Particle Swarm Optimization, PSO)來優(yōu)化無線傳感器網(wǎng)絡通信能耗，延長網(wǎng)絡的生命周期。該算法雖能有效降低無線傳感器網(wǎng)絡的能耗，但收斂速度較慢，全局搜索能力較差。蔣華等[11]設計了一種基于改進灰狼優(yōu)化算法的水下無線傳感器網(wǎng)絡分簇方案，該方案優(yōu)化了網(wǎng)絡的傳輸能量消耗，具有計算量小，便于實驗的優(yōu)點，能夠有效降低傳感器節(jié)點間傳輸數(shù)據(jù)的通信能耗，但容易陷入早熟收斂，難以通過優(yōu)化獲得較好的分簇結(jié)果。

為了解決無線傳感器網(wǎng)絡節(jié)點間數(shù)據(jù)傳輸能耗過大，生命周期較短的問題，本文提出了一種基于混沌克隆遺傳算法(Chaotic Clonal Genetic Algorithm，CCGA)的無線傳感器網(wǎng)絡低能耗分簇方案，并建立了相應的目標函數(shù)。方案中設計了新的混沌算子和克隆算子，在降低網(wǎng)絡通信能耗的同時有效解決了啟發(fā)式算法收斂慢、運行時間過長等問題。在仿真中，對比了傳感器節(jié)點數(shù)量分別為100、150、200、250時所提算法與常用的PSO和混合蛙跳算法(Shuffled Frog Leaping Algorithm，SFLA)的網(wǎng)絡通信能耗。仿真結(jié)果表明相比于常用的PSO和SFLA，所提出的CCGA方案可以有效的降低無線傳感器網(wǎng)絡通信能耗，延長網(wǎng)絡生存周期。

1 資料與方法

1.1 無線傳感器網(wǎng)絡低能耗分簇模型

在本節(jié)中，針對無線傳感器網(wǎng)絡中傳感器節(jié)點通信能耗的約束，提出了一種低能耗分簇模型。本文研究的無線傳感器網(wǎng)絡結(jié)構如圖1所示。

圖1 無線傳感器網(wǎng)絡分簇結(jié)構

在無線傳感器網(wǎng)絡中，分簇即在監(jiān)測的范圍之內(nèi)劃分多個節(jié)點簇，每個節(jié)點簇內(nèi)選擇一個傳感器節(jié)點作為簇頭節(jié)點，并將簇內(nèi)的其他節(jié)點作為感知節(jié)點[12-13]。在數(shù)據(jù)上行階段，每個感知節(jié)點對目標進行感知，在完成感知任務后感知節(jié)點將數(shù)據(jù)上傳至該節(jié)點簇內(nèi)的簇頭節(jié)點。簇頭節(jié)點匯集簇內(nèi)感知節(jié)點上傳來的數(shù)據(jù)，再直接上傳或多跳上傳數(shù)據(jù)至網(wǎng)關節(jié)點。在任務下發(fā)階段，感知節(jié)點執(zhí)行的監(jiān)測任務由網(wǎng)關節(jié)點發(fā)布到簇頭節(jié)點，再由簇頭節(jié)點下發(fā)至簇內(nèi)的感知節(jié)點上。

無線傳感器網(wǎng)絡在發(fā)送和接收數(shù)據(jù)時會產(chǎn)生通信能耗，而通信能耗受到傳感器節(jié)點間通信距離的影響[14-16]。由于通信能耗和數(shù)據(jù)傳輸距離直接相關，合理有效的分簇方式可以有效降低網(wǎng)絡通信距離，進而降低網(wǎng)絡能耗。由于節(jié)點電池能量有限，因此低能耗分簇對于無線傳感器網(wǎng)絡非常重要。

在無線傳感器網(wǎng)絡中，發(fā)送節(jié)點將p比特的數(shù)據(jù)的傳輸?shù)浇邮展?jié)點所消耗的通信能耗為：costsend(p,d,i)=Eelec·p+εamp·p·di。其中，costsend(p,d,i)表示兩個節(jié)點之間的距離為d時，源節(jié)點將p比特的數(shù)據(jù)發(fā)送到接收節(jié)點時需要的通信能耗。其中，Eelec表示電能參數(shù)，εamp表示功率放大參數(shù)，i為通信環(huán)境質(zhì)量參數(shù)，i的值通常在2到4之間，通常根據(jù)通信環(huán)境的質(zhì)量來確定i的取值。一般情況下，通信環(huán)境越好，i的值越小。

接收節(jié)點接收q比特的數(shù)據(jù)所需的通信能耗為：costreceived(q)=Eelec·q。其中，costreceived(q)代表接收節(jié)點接收q比特的數(shù)據(jù)時消耗的通信能耗。在本文的仿真實驗中，假設q為3072 bit，εamp=100 pJ·bit-1·m-2，Eelec=50 nJ·bit-1，i=3。

1.2 遺傳算法

遺傳算法(Genetic Algorithm, GA)是一種適合解決復雜優(yōu)化問題的智能算法，它模仿自然界中物種自然選擇過程，具有強大的優(yōu)化和搜索能力，可用于解決多目標優(yōu)化問題[17]。遺傳算法受達爾文進化論和優(yōu)勝劣汰生存觀念的啟發(fā)，通過模擬基因隨機重組和突變的過程向預定目標完成種群進化。然而，傳統(tǒng)遺傳算法易陷入早熟收斂，導致算法陷入進化停滯。

本文提出了一種新的CCGA無線傳感器網(wǎng)絡低能耗分簇方案。算法設計了相應的混沌算子以增強算法的全局搜索能力，并設計了新的克隆選擇算子來避免算法陷入局部最優(yōu)?；煦缢阕雍涂寺∷阕幽軌蛴行U大算法的搜索范圍，加快算法的收斂速度，進而完成能量高效分簇，從而有效降低無線傳感器網(wǎng)絡節(jié)點間數(shù)據(jù)傳輸所需通信能耗。通過CCGA優(yōu)化無線傳感器網(wǎng)絡通信能耗主要步驟如下：

(1)利用混沌算子生成隨機的染色體組，并完成CCGA染色體的初始化。

(2)選擇優(yōu)良的染色體作為親本，以供交叉和變異算子使用。

(3)通過交叉和變異產(chǎn)生一個新種群。

(4)使用適應度函數(shù)評估新種群的優(yōu)劣程度。

(5)使用克隆算子將產(chǎn)生的優(yōu)秀染色體進行克隆擴增和高強度變異。

(6)使用適應度函數(shù)評估克隆算子的結(jié)果，淘汰劣等染色體并更新種群。

重復循環(huán)，直至達到最大迭代次數(shù)則輸出最優(yōu)染色體。

1.3 基于CCGA的無線傳感器網(wǎng)絡低能耗分簇方法

1.3.1 染色體編碼

設計CCGA的第1步是找到合適的染色體編碼方案。CCGA的效率部分取決于所采用的編碼技術。由于二進制編碼具有表示形式簡單、表達能力強的特點，本文在低能耗分簇問題編碼方案上選擇二進制編碼。當某向量上對應的二進制編碼為數(shù)字“1”則表示該向量位置上的傳感器節(jié)點為簇頭節(jié)點，當二進制編碼為數(shù)字“0”時，則表示該向量位置上為感知節(jié)點。若染色體的染色體編碼為“0100110101”，編碼的第2個數(shù)字是1，則表示第2個傳感器節(jié)點是簇頭節(jié)點。編碼中的每個二進制數(shù)字為1個基因，例如該染色體中基因數(shù)為10，即每個基因代表1個傳感器節(jié)點，無線傳感器網(wǎng)絡中傳感器節(jié)點的數(shù)量為10。換句話說，染色體符號長度即為無線傳感器網(wǎng)絡中傳感器節(jié)點的數(shù)量。

1.3.2 初始化種群

在本文中，將初始種群的大小設置為M，并且假定初始種群中有N個基因，即無線傳感器網(wǎng)絡中存在N個傳感器節(jié)點，種群編碼可由公式(1)表示：

(1)

式中，Bm表示為第m個染色體，bm,n表示在第m染色體中第n個傳感器節(jié)點是否為簇頭節(jié)點，若bm,n=1，表示該傳感器節(jié)點為簇頭節(jié)點，否則為感知節(jié)點。當無線傳感器網(wǎng)絡中簇頭的數(shù)量固定為S，約束條件如公式(2)所示：

(2)

公式(2)約束了無線傳感器網(wǎng)絡中簇頭節(jié)點的數(shù)量，并且將簇頭節(jié)點的數(shù)量固定為S。例如，當無線傳感器網(wǎng)絡中的傳感器節(jié)點的數(shù)量為100個時，如果將簇頭比例定為10%，則簇頭節(jié)點的數(shù)量為10，即S=10。

在CCGA中，初始化的質(zhì)量對迭代優(yōu)化速度會產(chǎn)生很大的影響。CCGA利用混沌序列Logistic映射來豐富初始化種群的多樣性，從而加大算法的搜索范圍便于找到更優(yōu)解?；煦缬成鋷淼碾S機性完全在解空間范圍內(nèi)，并且可以有效提升初始種群的質(zhì)量，因此可以提升算法的收斂速度。Logistic映射數(shù)學如式(3)所示：

Za+1=μZa(1-Za),Za∈[0,1],μ∈(2,4]。

(3)

式中，μ為控制參量，μ的取值一般為4。

1.3.3 適應度計算

本文的目標是最大程度地降低無線傳感器網(wǎng)絡通信能耗，因此需要根據(jù)無線傳感器網(wǎng)絡的通信能耗評估每個染色體的適應度。對于CCGA中的染色體，其適應度值根據(jù)適應度函數(shù)計算得出。適應度值越低，染色體的質(zhì)量越好。在本文中，通過公式(4)計算染色體的適應度值。

(4)

式中，F(xiàn)it(Bm) 表示第m個染色體的適應度，Bm為第m個染色體，F(xiàn)it(Bm)即第m個染色體的簇頭選擇結(jié)果所需要消耗的通信能耗，也就是第m種簇頭的選擇方法的適應度。i為通信環(huán)境質(zhì)量參數(shù)，costsend,m,n(p,d,i)為在第m個染色體的方案中第n個傳感器節(jié)點發(fā)送p比特數(shù)據(jù)到距離為d的傳感器節(jié)點所需的能耗，而costreceived,m,n(q) 為在第m個染色體的方案中第n個傳感器節(jié)點接收q比特數(shù)據(jù)所需的能耗。

1.3.4 選擇

CCGA采用輪盤賭選擇策略來選擇父代染色體，選擇程序采用最優(yōu)染色體保存方法和輪盤賭技術。在輪盤賭中，具有更好的適應度值的染色體更有可能被選中。因此，可以在不同的輪次選擇相同的染色體。CCGA根據(jù)基于適應度的方式確定被選的概率，進而進行父代的選擇，然后將被選的父代染色體用于交叉算子。這樣，在種群中適應度更優(yōu)的染色體更容易被傳給下一代。

為了確保具有較低通信能量消耗的染色體被選擇的可能性更大，染色體的被選擇概率與染色體的適應程度成反比，如公式(5)所示：

(5)

1.3.5 交叉

當完成選擇算子后，被選擇的染色體被直接轉(zhuǎn)移給交叉算子。交叉算子的目的是搜尋具有更低能耗的染色體。交叉算子是將父代的染色體重新組合為兩個新的染色體的啟發(fā)式過程。算法對B1、B2兩個染色體進行交叉運算的過程如下。首先通過邏輯與運算得到B′,B′是將兩個染色體中對應位置的布爾代數(shù)進行對比，對應位置布爾代數(shù)相同則保持不變，不同則變?yōu)椤?”。例如當B1=[010011001]、B2=[010010110]時，通過邏輯與運算后得到B′=[010010000]。

其次，再對兩個染色體進行邏輯與運算得到B″,B″是將B1和B2中對應位置布爾代數(shù)相同的位置變成0，不同則變?yōu)?，則得到B″=[000001111]

最后，將B″中的“1”隨機平均分配到B′中的相應位置，以獲得兩個由交叉產(chǎn)生的新染色體。如圖4所示，B″中的數(shù)字“1”平均分配給B′，并且位置是隨機的。因此，兩個新獲得的染色體Bnew1和Bnew2，其中一種的分配方案可以為Bnew1=[010011100]、Bnew2=[010010011]。

1.3.6 變異

在CCGA中，每條染色體上的每個基因都有突變的可能性。變異的主要目標是維持群體內(nèi)的多樣性。考慮到染色體中簇頭的數(shù)量是恒定的，變異操作以一定概率將染色體中“ 1”的位置隨機改變?yōu)椤?”，并隨機選擇其中為“0”的位置成為“1”。在CCGA中，設置基因變異概率為0.05。例如B1=[010011001]，隨機變異后可以得到B2=[010001011]。

2 結(jié)果與分析

在本節(jié)中，給出了在無線傳感器網(wǎng)絡中CCGA與常用的SFLA和PSO方案的仿真結(jié)果對比。通過進行仿真實驗來驗證本文所提出的CCGA低能耗分簇方法的性能。在配置為Intel Core i7-8550U，2.00 GHz，8GB RAM，Win10操作系統(tǒng)的電腦上利用MATLAB R2012a軟件測試了該方案的性能。

在仿真中，設置監(jiān)測范圍為100 m×100 m的正方形區(qū)域，每個傳感器的位置坐標在監(jiān)測范圍內(nèi)隨機生成。CCGA與常用的PSO以及SFLA方案的參數(shù)設置根據(jù)實驗經(jīng)驗所得，其中CCGA和PSO兩種方案的迭代次數(shù)與種群中染色體數(shù)的設置均一致，迭代次數(shù)設為100代，種群染色體個數(shù)為50。在CCGA中，變異概率和交叉概率分別設置為0.05和0.8。在PSO中，設置學習因子C1=C2=2。在SFLA中，全局迭代次數(shù)設置為100代，組內(nèi)迭代次數(shù)設為20代，種群數(shù)量為6，子種群中青蛙的個數(shù)為5。

無線傳感器網(wǎng)絡的通信能量消耗由發(fā)送能耗和接收消耗組成。在實驗中，為了考慮不同傳感器節(jié)點數(shù)量和不同簇頭比例對實驗結(jié)果的影響，針對不同傳感器節(jié)點數(shù)量進行了多次仿真實驗。當簇頭比例為10%，傳感器節(jié)點數(shù)分別為100、150、200和250時，三種算法的通信能耗仿真結(jié)果如圖2所示。

當簇頭節(jié)點比例為10%時，在不同的傳感器節(jié)點數(shù)量條件下，3種啟發(fā)式算法得出的通信能耗均隨算法迭代次數(shù)的增加而降低。這3種算法中，CCGA的通信能耗在迭代過程中始終低于常用的PSO與SFLA，且在代數(shù)增加時通信能耗下降速度較快。

當傳感器節(jié)點數(shù)量為100時(圖2A)，在經(jīng)過100次的迭代后，CCGA的通信能耗低于常用的PSO和SFLA。CCGA低能耗分簇方案的通信能耗為0.028 10 J，而相同條件下PSO的通信能耗為0.028 18 J，SFLA的通信能耗為0.028 25 J。CCGA優(yōu)化后的通信能耗比常用的PSO和SFLA分別降低了0.28%和0.53%。這表明了在優(yōu)化無線傳感器網(wǎng)絡低能耗分簇中，CCGA搜索能力更強，收斂速度更快。

圖2B、C、D分別對比了150、200和250個傳感器節(jié)點的網(wǎng)絡通信能耗，并且得到了類似的結(jié)果：當傳感器節(jié)點為150時，CCGA、PSO和SFLA優(yōu)化后的通信能耗分別達到0.041 90 J、0.042 01 J和0.042 05 J(圖2B)，表明與常用的PSO和SFLA相比，CCGA低能耗分簇方案獲得了更低的通信能耗，有效地避免了算法陷入進化停滯。傳感器節(jié)點數(shù)為200，使用CCGA低能耗分簇方案后通信能耗下降到0.055 77 J，而常用的PSO和SFLA僅分別下降到0.055 90 J和0.055 96 J(圖2C)。傳感器節(jié)點為250，CCPEA、PSO和SFLA的通信能耗分別為0.069 61 J、0.069 76 J和0.069 82 J(圖2D)。

A:100個傳感器節(jié)點; B:150個傳感器節(jié)點; C:200個傳感器節(jié)點; D:250個傳感器節(jié)點。圖2 WSN通信能耗的對比

表1給出了當傳感器節(jié)點分別為100、150、200、250時，所提出的CCGA方案相比常用的PSO與SFLA方案網(wǎng)絡通信能耗降低的百分比。

表1 CCGA低能耗分簇方案相對PSO和SFLA方案通信能耗降低百分比

3 討論與結(jié)論

3.1 討論

針對無線傳感器網(wǎng)絡低能耗分簇問題，設計了系統(tǒng)模型，并給出了計算無線傳感器網(wǎng)絡通信能耗的適應度函數(shù)，提出了一種新的混沌克隆遺傳算法。在仿真中隨機生成傳感器節(jié)點的初始位置，在不同傳感器節(jié)點數(shù)量下對三種算法進行仿真實驗，隨著傳感器節(jié)點數(shù)量的增加，網(wǎng)絡的通信能耗變大。

(1)仿真結(jié)果表明，與常用的PSO和SFLA兩種方案相比，所提CCGA算法的優(yōu)勢如下：隨著迭代次數(shù)的增加，CCGA優(yōu)化后的通信能耗更低。當傳感器節(jié)點分別為100、150、200、250時，CCGA低能耗分簇方案獲得的通信能耗均低于常用的PSO和SFLA方案。并且CCGA利用混沌算子生成隨機初始種群，擴大了種群的搜索范圍，有助于找到更好的解，最終實現(xiàn)了較低的能耗，有效地避免了算法的早熟收斂。

(2)目前常用的PSO和SFLA兩種方案的劣勢如下：尋優(yōu)能力差，容易陷入過早收斂等缺點，如當傳感器節(jié)點數(shù)量為250時，當?shù)螖?shù)到達第20代時，PSO和SFLA的收斂速度顯著降低，并且PSO所優(yōu)化的網(wǎng)絡能耗已接近其最優(yōu)解。

綜上所述，由于CCGA低能耗分簇方案實現(xiàn)的能耗更低，其在實際應用中價值更高。因為所提CCGA得到的解更具有穩(wěn)定性，在不同傳感器節(jié)點數(shù)量條件下均取得了更低的能耗，并且算法具有較強的魯棒性，可以有效避免算法陷入早期停滯，因此該算法具有廣闊的應用前景。通過將所提算法進行推廣等措施，可以有效的在實際應用中降低無線傳感器網(wǎng)絡能耗。

本文所提CCGA方案在降低無線傳感器網(wǎng)絡通信能耗的同時避免了算法陷入早熟收斂。但是，對于CCGA參數(shù)的選擇是基于現(xiàn)有研究的經(jīng)驗值范圍，難以使算法的性能達到最優(yōu)。由于參數(shù)的敏感性，參數(shù)數(shù)據(jù)的細微變化將影響算法的性能。下一步將對參數(shù)進行遍歷搜索，從而對參數(shù)進行更細微的調(diào)整，使算法的性能達到最優(yōu)。

3.2 結(jié)論

(1)本文提出了一種新的混沌克隆遺傳算法(CCGA)，設計了新的目標函數(shù)，通過合理的低能耗分簇方案對無線傳感器網(wǎng)絡通信能耗進行了優(yōu)化。

(2)CCGA中加入的混沌算子和克隆算子能夠有效避免算法的早熟收斂和進化停滯問題，同時擴大了優(yōu)化范圍，提升了算法的運行效率。

(3)通過仿真實驗與分析，對比了CCGA低能耗分簇方案相對于常用的PSO和SFLA低能耗分簇方案的網(wǎng)絡通信能耗。實驗結(jié)果表明，當簇頭比例為10%時，不同傳感器節(jié)點數(shù)量條件下CCGA的通信能耗均低于常用的PSO和SFLA。