基于混沌優化螢火蟲算法的WSN分簇算法*

孫愛晶，鄭世鵬

(西安郵電大學通信與信息工程學院，陜西 西安 710121)

無線傳感器網絡(wireless sensor network，WSN)中是由大量低成本、能量有限的無線傳感器節點組成的自組織多跳網絡，對于復雜的環境很難給節點補充能量，所以為了盡可能的延長網絡的生存時間，節能是無線傳感器網絡中很重要的一個問題[1－2]。高效合理的網絡拓撲結構能夠大幅提高網絡的利用效率并延長其生命周期，優化網絡的整體能耗效率、延長網絡壽命是WSN中一項重要的研究內容[3－4]。

經典的低功耗自適應集簇分層型(low-energy adaptive clustering hierarchy，LEACH)[5]協議根據提出的概率公式隨機選取簇首，節點隨機生成一個隨機數，并和閾值做比較，如果小于該閾值，則節該點被選為簇頭，節點根據簇首的位置就近入簇，簇頭對采集的數據進行融合后以單跳方式傳輸到基站，該策略不能保證簇首數目及簇首位置的合理分布，選取簇頭也沒有考慮節點的剩余能量。研究者針對LEACH協議的缺點提出的多種改進型協議。其中較為經典的如李成法等人提出的EEUC算法[6]，該算法中候選簇頭的選取方式和LEACH協議選取簇頭的方式類似，在候選簇頭中引入了競爭半徑決定最終簇首，使用非均勻成簇的策略，縮小基站周圍簇首的成簇半徑，減小了簇頭收集簇內數據時的負載，有效的緩解了以多跳方式向基站傳輸數據時產生的“熱區”問題；文獻[6]在LEACH協議的基礎上提出了LEACH-improved算法，在選取簇首時考慮了多個影響因子，避免了能量較小的節點當選為簇首，但因子間的權重值難以確定，實際應用困難，且易形成極大簇造成節點間的負載不平衡；針對WSN節點能耗不均的問題，文獻[8]引入蟻群算法確定路由，通過信息素濃度選出路由節點優化路徑質量；文獻[9]針對簇首位置和傳輸路徑選取不合理加劇節點能耗、縮短網絡壽命的問題，采用改進粒子群算法對網絡分簇，并設計了一種最小生成樹的多跳路由，有效延長了網絡的生存周期。還有一些研究者引入聚類算法對網絡進行分簇，Bakaraniya等[10]基于K-means算法提出了K-LEACH算法，初始階段利用K-means進行聚類，簇頭的選舉沒有考慮節點的剩余能量；直接使用傳統K-means和FCM算法進行聚類容易產生局部最優解和收斂速度慢的問題，文獻[11]使用遺傳算法(GA)優化模糊C均值聚類從而提出了GAFCMCR算法，該算法將GA應用到FCM算法的優化計算中，由GA得到初始聚類中心，再使用標準的FCM算法聚類，然后通過評價函數，在每個簇內競選出最終簇首，該算法成簇效果較好，具有較好的能量均衡性。但在簇頭輪換階段，判斷更換簇頭的條件里參數λ選取困難，文中只提到λ取值太大或者太小都會增加網絡的能量消耗，并沒有驗證所選取值是否最優，也沒有給出選取最佳值的方法。

本文針對簇首分布不合理，節點負載不均衡，簇首輪換能耗大的問題，綜合上述算法的優缺點提出了一種基于混沌優化螢火蟲算法的WSN分簇算法。算法首先利用混沌理論優化的螢火蟲算法，根據節點的位置分布設計目標函數對節點進行聚類，使簇首在整個檢測區域內的分布更合理；然后引入雙簇首規則均衡簇頭負載，避免某些簇頭負載過大較早死亡，并在數據傳輸階段使用最短路徑Bellman-Ford算法[12－13]確定數據多跳傳輸鏈路。另外，在簇首輪換階段，充分考慮整個網絡的剩余能量，由主簇首選出簇內當前剩余能量最高的兩個節點充當下一輪的簇頭。本文將從以上敘述的幾個方面對算法進行仿真和分析。

1 系統模型

1.1 網絡模型

本文所采用的網絡模型如圖1所示，由N個隨機部署在M×M監測區域的傳感器節點和一個能量不受限的匯聚節點(Sink)組成，關于該模型做出以下假設:①所有節點隨機拋灑布設后位置都是固定不變的，匯聚節點位于檢測區域中心位置；②節點可以通過接收的信號強度計算與Sink節點和其他節點的距離；③節點可以感知自身位置以及其他節點位置，根據距離控制發射功率和某一特定的節點通信；④每個成員節點周期性的檢測數據并發送給相應的簇首；⑤每個節點屬性相同，都具備一定的存儲、計算、查詢和數據融合能力。

圖1 網絡模型

1.2 能量模型

傳感器節點傳輸數據所消耗的能量遠大于節點用于計算所消耗的能量[14]，根據一階無線電模型，在多徑衰落信道，能耗和傳輸距離d的四次方成正比，所以本文從優化簇首的分布與簇結構的角度來減少采集數據時傳播所消耗的能量，并采用LEACH協議中的一階無線通信能耗模型，則傳輸距離為d時傳感器節點發送lbit數據所消耗的能量ETx(l，d)可以表示為式(1):

式中，ε代表發射放大器的放大倍數；l代表傳感器節點所發送或接收消息的比特數；Eelec代表發射或接收電路處理單位比特所消耗的能量；d0＝，為傳輸距離閾值，其中εfs為自由信道的能耗參數，εmp為多徑衰落信道的能耗參數，當傳輸距離d＜d0時為自由信道，傳感器節點發送或接收數據時消耗的能量與距離的平方成正比；當d≥d0為多徑衰落信道，與距離的四次方成正比。

傳感器節點接收lbit數據消耗的能量ERx如式(2):

2 理論分析

2.1 螢火蟲算法

螢火蟲算法(Firefly Algorithm，FA)[15]是由劍橋學者Yang模擬自然界中螢火蟲的發光與移動特性提出的一種基于群體搜索的隨機優化算法。其仿生原理是:利用螢火蟲的發光特性使個體之間相互吸引，熒光度較弱的螢火蟲向較強的螢火蟲移動，從而實現位置優化。

Algorithm 1 Firefly Algorithm

FA算法主要遵循以下三個原則:①所有的螢火蟲不區分性別，個體之間可以相互吸引；②吸引度β和亮度I成正比，因此對于任意兩個螢火蟲，亮度低的將向亮度高的個體移動，并且吸引度和亮度都隨著距離的增加而減小。如果螢火蟲的周圍找不到更亮的個體，該螢火蟲將做隨機移動。③螢火蟲的亮度由目標函數的值決定。

定義1螢火蟲的相對熒光亮度為:

式中，I0為螢火蟲的最大熒光亮度，即自身(r＝0處)熒光亮度，與目標函數值相關，目標函數值越優自身亮度越高；γ為光強吸收系數，可設置為常數；rij為螢火蟲i和j之間的距離。

定義2螢火蟲的吸引度β為:

式中，β0為最大吸引度，即光源(r＝0處)的吸引度。螢火蟲個體的吸引度β隨著個體間距離的增加而降低，其值的大小決定低亮度螢火蟲個體向高亮度螢火蟲個體移動的距離。

定義3螢火蟲i被螢火蟲j吸引進行移動的位置由式(5)更新:

式中，xi、xj代表任意兩只螢火蟲i和j在空間所處的位置；(xj－xi)為它們的笛卡爾距離；α∈[0，1]，為步長因子；rand是隨機數，服從標準均勻分布；α×(rand－1/2)為隨機擾動，避免算法陷入早熟。通過多次移動后，所有的個體都聚集到亮度最高的螢火蟲位置，從而實現尋優。

下面為FA的偽代碼描述:

2.2 混沌優化

FA對初值敏感，尋優能力主要靠個體間的相互作用，缺乏變異機制，易陷入局部最優且難以擺脫。混沌是非線性系統所特有的一種非周期運動現象，其行為復雜且類似隨機，但存在精致的內在規律性，具有內隨機性、初值敏感性和遍歷性等特點[16]。混沌優化就是利用混沌運動的他特性來提高隨機優化算法的效率[17－18]。文獻[19]中的已經證明立方映射產生的序列具有較好的均勻性，本文將采用立方映射來初始化種群，文獻[20]給出了利用立方映射產生混沌序列的優化過程所包括的兩個關鍵步驟如下:①將混沌空間映射到優化問題的解空間；②利用混沌動態特性實現對解空間的搜索。

本文采用文獻[21]提出的一種將混沌空間映射到優化問題解空間的算法:

①對于D維空間的M個螢火蟲個體，首先隨機產生一個D維向量，該向量作為第一個螢火蟲個體，表示為Y＝(y1，y2，…，yd)，其中yi∈[－1，1]，1≤i≤d。

②然后將Y的每一維利用式(6)進行M－1次迭代，生成其余的M－1個螢火蟲個體。

③將產生的混沌變量按式(7)映射到解的搜索空間:

Ud和Ld分別表示搜索空間的第d維的上下限，yid是利用式(6)產生的第i個螢火蟲的第d維，xid即為第i個螢火蟲在搜索空間的第d維的坐標。

2.3 CACOFA算法

根據本文選取的網絡模型規模大小，CACOFA算法先隨機產生一個40維向量作為第一個螢火蟲個體，然后使用式(6)對該向量的每一維進行迭代19次，得到20個螢火蟲個體，最后通過式(7)將20個螢火蟲個體映射到解空間的20個解。把最終得到的20個解作為FA算法的初始解，通過對網絡節點進行聚類得到最優解，由基站向全網廣播聚類結果，節點收到數據包后解析出來自己所在的聚類及簇內成員，并創建一個鏈表存儲在內存中；采集數據時，普通節點通過查詢當前輪所屬的簇頭并向其發送數據，同時節點在發送的數據幀中加入自己的標號和當前的剩余能量信息。基站收到簇內所有存活節點的數據后會根據能量信息判斷是否需要更換簇頭，輪換簇頭的閾值條件是簇頭節點的平均剩余能量小于普通節點的平均剩余能量。更換簇頭時，基站直接查詢第一次的聚類結果中選出當前剩余能量最大的節點作為簇頭重新進行廣播，而不需要重新聚類，這樣不僅能均衡簇頭節點的負載，同時還降低了運行算法重新聚類帶來的網絡延遲。算法流程如圖2所示:

圖2 算法流程

如果簇頭分布不合理，那么在數據采集階段，會帶來很大的網絡開銷，為了使簇頭分布的更合理，本算法通過綜合考慮簇首數量和簇結構的緊湊性設計適應度函數來優化簇頭的分布。本文希望簇結構是比較緊湊的，且較均勻的分布在整個網絡，適應度函數F如式(8):

其中分子部分代表所有普通節點到基站的距離的和；分母的第一部分是普通節點到其對應的簇頭的距離和，第二部分是簇頭到基站的距離和。當簇頭均勻的分布在網絡中，且節點距離簇頭的距離越小，則對應的適應度函數值越大。

2.4 復雜度分析

混沌優化過程中只需要對表示螢火蟲向量的維數進行遍歷，復雜度可表示為O(M×D)。本文設置螢火蟲算法迭代次數為200，適應度函數的計算時間復雜度為O(f)，標準螢火蟲算法迭代過程的復雜度為O(M2)，則優化后的螢火蟲算法的計算時間復雜度為O(M×D＋200×M2×f)，可簡略表示為O(M2)。綜上，使用混沌理論優化螢火蟲算法與原算法復雜度數量級相同。

2.5 簇間路由

簇頭負責簇內所有數據的收集與融合，會消耗比普通節點更多的能量，如果繼續使用簇頭進行路由，會加劇節點間能耗的不平衡性，造成個別節點過早死亡；同時根據本文采用的簇頭輪換條件，簇頭能耗過快將導致輪換過于頻繁，會增加額外的能量消耗，故本文引入雙簇首機制，添加副簇首負責傳送數據來均衡主簇頭的能耗，減少簇頭輪換的次數。本文采用經典LEACH協議中的時分多址通信機制，簇頭為每個成員節點劃分一個時隙，普通節點在固定的時隙內以單跳的方式向主簇頭傳輸數據。主簇頭節點對采集的數據進行融合處理后發送給副簇頭并在副簇頭間以多跳的方式傳輸到基站。本文采用最短路徑算法中的Bellman-Ford算法確定多跳路徑，該算法是一種用于搜索最短路徑的圖搜索算法[22－23]。為避免單獨搜集各個節點的剩余能量會增加額外的能量開銷，本文采用文獻[9]的數據幀方式，各節點完成數據采集和處理后，將自身剩余能量作為數據添加在數據包中一起路由到基站。

3 仿真與分析

本文使用MATLAB 2016a為仿真工具在相同參數條件下對LEACH算法、EEUC算法、GAFCMCR算法和本文CACOFA算法進行了多項性能對比分析，實驗參數設置如表1所示:

表1 仿真參數

圖3仿真了LEACH算法、EEUC算法、GAFCMCR算法和本文CACOFA算法的分簇效果，LEACH算法采用概率來選擇簇頭，從子圖(a)可以看出簇頭分布和成簇效果都不理想；EEUC采用競爭半徑策略來均衡節點負載，如子圖(b)，越靠近基站的成簇半徑越小，雖然有效的避免了“熱區”內的節點較早死亡，但整個網絡的生存時間依然較短；GAFCMRA采用遺傳算法優化FCM聚類算法來進行網絡分簇，雖然有效的延長了網絡的生存時間，但從子圖(c)可以看出，簇結構存在極大極小簇；而本文提出的CACOFA算法，如子圖(d)，簇頭分布均勻，且簇結構的大小均勻；靠近基站的節點直接與基站成簇。

圖3 算法分簇效果對比圖

本文使用簇頭包含普通節點的數量表示簇頭的負載，多次運行各個算法統計數據如表2。EEUC算法與其他三種算法的思想不同，它是通過非均勻分簇的思想來均衡整個網絡的能耗，故此處不通過簇頭負載參與比較。通過數據可以看出LEACH算法存在極大簇與極小簇，方差最大；GAFCMRA算法存在極大簇，且方差較大；本文CACOFA算法不存在極大簇或極小簇，簇頭負載的方差為3.76，分簇效果最好。

表2 算法的簇頭負載

表3給出了各個算法仿真時出現第一個死亡節點的輪數，使用CACOFA算法的網絡出現第一個死亡節點的輪數是1 021，比LEACH算法、EEUC算法、GAFCMRA算法分別提高了127%、99%、39%。

表3 出現第一個死亡節點的輪數

圖4從死亡節點個數與輪數之間的關系的角度對比了各算法的生命周期，仿真結果表明本文算法CACOFA的生命周期均大于LEACH算法、EEUC算法、GAFCMRA算法；在大約700輪的時候，LEACH算法的節點已經全部死亡；900輪的時候，EEUC算法和GAFCMRA算法的存活節點只剩下總節點個數的約五分之一，而CACOFA算法還沒出現第一個死亡節點，表明CACOFA算法可以有效延長網絡的生存時間。另外，CACOFA算法的節點從開始死亡到全部死亡經歷的時間比較短，只用了150輪左右，說明網絡內所有節點的能耗是比較均衡的，驗證了算法在均衡簇頭負載方面的有效性。

圖4 存活節點的個數與輪數的關系

圖5和圖6分別仿真了網絡總剩余能量和運行輪數的關系、普通節點采集數據包與輪數的關系。當運行相同輪數時，CACOFA算法的網絡總剩余能量始終最多，而且采集的數據包大于其他三種算法，說明該算法有效的降低了每輪節點傳輸數據的能耗，使每輪的節點能量開銷比LEACH算法、EEUC算法、GAFCMRA算法都要小，從而延長了網絡的生命周期。從圖6可以看出，CACOFA算法采集的數據包均大于其他三種算法。在大約750輪之前，CACOFA算法采集的數據包個數與其他算法略有浮動，但總體差別不大，在750輪之后，采用其他三種算法的網絡均已死亡，CACOFA算法依然可以正常采集數據，進一步驗證了CACOFA算法延長網絡生命周期的有效性。

圖5 網絡總剩余能量和輪數的關系

圖6 數據包與輪數的關系

4 結論

本文從無線傳感器網絡的特點出發，為了盡可能的延長網絡的壽命，在分簇的思想上從均衡節點負載，降低每輪網絡運行所需能耗的角度考慮，提出了基于混沌優化螢火蟲算法的WSN分簇算法。在成簇階段，目標函數充分考慮距離因素，通過混沌優化的螢火蟲算法對網絡節點進行聚類；在簇頭輪換階段，從聚類結果中選取剩余能量最高的節點作為簇頭；在數據傳輸階段，采用簇內單跳、簇間多跳的方式進行傳輸。仿真結果表明，本文提出的CACOFA算法能夠有效均衡節點負載，延長網絡的生存周期。

在數據路由階段，本文采用了現有的最短經典路徑算法進行仿真，但最短路徑只能減小單條鏈路上的能耗，并不能保證鏈路上的能耗均衡。下一步工作可通過優化路由算法進一步均衡整個網絡的能耗，延長網絡的生命周期。