徐艮鳳， 張曦煌

(江南大學 物聯(lián)網工程學院，江蘇 無錫 214122)

基于CS優(yōu)化的雙簇頭分簇路由算法研究

徐艮鳳， 張曦煌

(江南大學 物聯(lián)網工程學院，江蘇 無錫 214122)

為了減少無線傳感器網絡(WSNs)分簇路由中簇頭的能量消耗，提出了一種基于布谷鳥搜索(CS)優(yōu)化的雙簇頭分簇路由算法。CS通過采用節(jié)點的剩余能量和節(jié)點之間的位置關系來構造適應值函數并選舉出最優(yōu)雙簇頭。其中，主簇頭將數據進行融合，副簇頭將融合的數據發(fā)送給基站，緩解了以往單簇頭同時負責數據融合和傳輸的雙重壓力，使得整體能耗在各個節(jié)點的分配更均衡。仿真實驗表明：與LEACH算法、粒子群優(yōu)化(PSO)算法相比，CS算法在減小網絡能耗以及延長網絡生存周期上更具優(yōu)勢。

無線傳感器網絡； 分簇路由算法； 布谷鳥搜索算法； 數據融合

0 引 言

無線傳感器網絡 ( wireless sensor networks,WSNs)是由在空間上相互離散的各類傳感器相互協(xié)作構成的傳感器網絡系統(tǒng),使得分布于不同場所的數量龐大的傳感器之間能夠實現更加有效、可靠的通信[1]。無線傳感器網絡工作時,由于本身能量有限,且不能夠對能量進行補充,導致其應用受到了較大的限制。在這種背景下,延長網絡生存周期己經成為了一個研究的重點。

LEACH算法中，簇頭根據節(jié)點隨機產生的隨機數是否小于閾值產生，雖然可以避免連續(xù)成為簇頭，但過多的分簇以及分布不均衡會導致節(jié)點過早死亡。文獻[2，3]在LEACH分簇算法基礎上，采用了粒子群優(yōu)化(PSO)算法選擇最優(yōu)簇頭。算法中，簇頭需要采集、融合以及轉發(fā)數據，耗能過快，導致節(jié)點過早死亡。文獻[4]采用了PSO算法選擇雙簇頭，通過主、副簇頭分工工作有效減輕了單簇頭的負載，但簇頭的能量利用率不高。

本文在LEACH算法基礎上，將簇頭個數設置為存活節(jié)點個數的5 %，并采用布谷鳥搜索(cuckoo search,CS)算法選擇最優(yōu)的雙簇頭，主簇頭負責收集和融合簇內的數據，并將數據轉發(fā)給副簇頭，副簇頭再將數據發(fā)送給基站，從而降低了單簇頭的能耗，使得節(jié)點能耗更均衡。

1 CS算法

CS算法，也叫杜鵑搜索算法，由劍橋大學Yang X S教授和Deb S教授于2009年提出的一種新興啟發(fā)算法[5～7]。研究發(fā)現，CS算法獲取的全局最優(yōu)解要比其他的優(yōu)化算法更有效。

CS算法是模擬布谷鳥覓食而提出來的,布谷鳥隨機游走的方式下，下一步的行動取決于兩個因素：1)當前的位置(狀態(tài));2)過渡到下一個位置的概率。整個過程基于以下3個理想化狀態(tài):1)布谷鳥每次只產一個卵，并隨機選擇鳥巢孵化；2)在隨機選擇的一組鳥巢中，最好的鳥巢將會保留到下一代；3) 可利用的鳥巢數量n是固定的，一個鳥巢的主人發(fā)現一個外來鳥蛋的概率Pa∈[0，1]。在這3個理想狀態(tài)的基礎上，布谷鳥尋巢的路徑和位置的更新公式如下

(1)

Levy(β)～u=t-β，1<β≤3

(2)

2 基于CS優(yōu)化分簇路由算法

優(yōu)化的分簇路由算法在LEACH算法基礎上采用CS算法，根據節(jié)點的剩余能量和節(jié)點之間的位置關系來構造適應值函數，選取主簇頭和副簇頭，分別負責融合和傳輸。

2.1 簇建立階段

傳統(tǒng)的LEACH算法選擇簇頭是隨機選擇一個0～1的數與閾值T(n)進行比較，若小于T(n)則選取為簇頭。由于未考慮節(jié)點的能量以及簇頭個數，可能導致能量低的節(jié)點成為簇頭，為了避免該問題，閾值公式修改如下

(3)

p(n)=p×n×S(n).E/Et

(4)

式中p(n)為被選為簇頭的概率；r為當前循環(huán)的輪數；G為最近1/p輪被選為簇頭的節(jié)點集合；S(n).E為當前節(jié)點的能量；Et為所有初始節(jié)點的總能量。

算法中，與傳統(tǒng)LEACH算法篩選簇頭的方法一致，但定義了簇頭個數為存活節(jié)點總個數的5 %，有效避免了簇范圍過大或過小。

2.2 主、副簇頭的選擇

在分簇完成后，CS算法構造了兩個關于節(jié)點剩余能量和節(jié)點之間位置關系的適應值函數，分別用來選取主簇頭和副簇頭。將建立的n個簇范圍分別代入算法中，選取出n對主、副簇頭。為了使CS算法適合該研究環(huán)境，需對原CS算法中的位置更新式(1)進行改進，并采用合適的適應值函數。

(5)

(6)

則

(7)

主簇頭的主要任務為收集并融合簇內數據，并將數據發(fā)送給副簇頭，因此,需要較高的能量以及該節(jié)點距離簇內節(jié)點的平均距離越小越好。主簇頭的選取采用以下適應值函數

(8)

式中δ和1-δ分別為節(jié)點能量影響因子和節(jié)點平均距離倒數的影響因子，δ∈[0,1]；k為簇內節(jié)點數；E(c)為主簇頭c的能量；E(i)為節(jié)點i的能量；ditoc為節(jié)點i到簇頭c的能量；f1為主簇頭能量占簇內節(jié)點的比例；f2為簇內節(jié)點到主簇頭平均距離的倒數。

副簇頭的主要任務是將主簇頭發(fā)送的數據轉發(fā)至基站，因此，需要較高的能量以及該節(jié)點距離基站的距離越小越好。副簇頭的選取采用以下適應值函數

(9)

式中 γ和1-γ分別為節(jié)點能量影響因子和節(jié)點距離影響因子，γ∈[0,1]；g1為副簇頭能量占簇內節(jié)點的比例；g2為副簇頭到基站的距離占簇內節(jié)點到基站的距離和的比例。

2.3 CS優(yōu)化的雙簇頭選取的具體步驟

算法的主簇頭選取具體步驟如下：

1)初始化鳥巢數n，Pa及最大迭代次數Nmax。

3)利用式(8)計算出適應值f(i)。

7)副簇頭的選取具體步驟與主簇頭類似。

3 算法仿真與分析

3.1 仿真環(huán)境

采用Matlab仿真平臺。100個傳感器節(jié)點隨機分布在100m×100m的網絡中，基站坐標位于(50，75),節(jié)點的初始能量為E0×(1+rand)，E0為0.5J，控制包大小為100B，數據包大小為4kB,εfs=10pJ/(bit·m2),εamp=0.001 3pJ/(bit·m4),Etx=Erx=Eelec=50nJ/bit,EDA=5nJ/(bit·signal)。

3.2 仿真結果

為了分析本文算法的性能，將本文算法與LEACH算法以及PSO_DH算法[4]進行仿真比較，以不同輪數中存活節(jié)點數、網絡總能耗、數據到基站傳輸量為評價標準。

圖1為網絡生命周期的比較。以第一個節(jié)點死亡時間作為網絡的生命周期，通過仿真實驗可以看出:本文算法第一個死亡節(jié)點的輪數為1 623輪;LEACH算法為174輪;PSO_DH算法為1 607輪。相對LEACH算法、PSO_DH算法具有更長的網絡生命周期。

圖1 網絡生命周期比較

圖2為網絡總能耗的比較。從圖中可以看出，本文算法相對LEACH算法能耗明顯減少，較優(yōu)于PSO_DH算法的總能耗。

圖2 網絡總能耗比較

圖3為數據到基站傳輸量的比較。從圖中可以看出：在運行800輪時，本文算法中數據到基站的傳輸量明顯低于LEACH算法。并且，隨著運行輪數的增加，LEACH算法在運行1039輪時，網絡中節(jié)點全部死亡。然而本文算法中數據到基站的傳輸量明顯低于PSO-DH算法。由此可見，采用CS優(yōu)化算法在簇頭進行數據融合的效果好于LEACH算法和PSO-DH算法。

圖3 數據到基站傳輸量比較

4 結束語

針對WSNs中分簇路由的不足，提出了基于CS優(yōu)化的雙簇頭分簇路由算法，通過仿真實驗證明算法較PSO優(yōu)化算法及經典LEACH算法具有更好的性能。新的分簇路由算法采用CS算法選取主簇頭和副簇頭，分別負責融合和傳輸。比之以往單簇頭同時負責數據融合和傳輸的雙重壓力，整體能耗在各個節(jié)點的分配更均衡，從而延長了整個網絡的生命周期。

[1] 劉奇奇,張曦煌.基于螢火蟲算法的無線傳感器網絡的分簇路由協(xié)議[J].傳感器與微系統(tǒng),2015,34(9):114-116.

[2] 劉志坤,劉 忠,李朝旭.基于混沌粒子群優(yōu)化的無線傳感器網絡分簇協(xié)議[J].傳感技術學報,2011(10):1459-1463.

[3] 梁 英,于海斌,曾 鵬.應用PSO優(yōu)化基于分簇的無線傳感器網絡路由協(xié)議[J]. 控制與決策,2006(4):453-456,461.

[4] 韓冬雪,張瑞華,劉丹華.基于PSO的無線傳感器網絡雙簇頭分簇算法[J].計算機工程,2010(10):100-102.

[5]YangXS,DebS.CuckoosearchviaLevyflights[C]∥2009WorldCongressonNature&BiologicallyInspiredComputing,NaBIC2009,IEEE,2009:210-214.

[6] 蘭少鋒,劉 升.布谷鳥搜索算法研究綜述[J].計算機工程與設計,2015(4)：1063-1067.

[7] 王 旭,張曦煌.基于布谷鳥搜索算法的無線傳感器網絡改進路由協(xié)議[J].傳感器與微系統(tǒng),2016,35(7):45-47.

張曦煌，男，教授，主要從事無線傳感網、嵌入式系統(tǒng)、計算機網絡、圖形與圖像處理、計算機分布式控制與智能控制等研究工作。

Research on dual-cluster heads clustering routing algorithm based on CS optimization

XU Gen-feng, ZHANG Xi-huang

(School of Internet of Things Engineering,Jiangnan University,Wuxi 214122,China)

In order to reduce the energy consumption of cluster head in wireless sensor networks(WSNs)clustering routing,a dual-cluster heads clustering routing algorithm based on cuckoo search(CS)optimization is proposed.The CS algorithm construct fitness function by using residual energy of nodes and relationship of position between nodes and elects optimal dual-cluster heads.In which,the main cluster head fuse data and the vice cluster head sends the fused data to the base station.It relieves dual pressure of data fusion and transmission beared by single cluster head in the past,so that distribution of the overall energy consumption in each node is more balanced. Simulation experiment show that compared with LEACH algorithm,PSO optimization algorithm,CS algorithm has more advantages in reducing network energy consumption and prolonging network lifetime.

wireless sensor networks (WSNs); clustering routing algorithm; cuckoo search (CS) algorithm; data fusion

10.13873/J.1000—9787(2017)09—0136—03

2016—08—17

TP 391

A

1000—9787(2017)09—0136—03

徐艮鳳(1990-)，女，碩士研究生，主要研究方向為無線傳感器網絡、嵌入式系統(tǒng)、計算機網絡，E—mail:2467933944@qq.com。