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

徐艮鳳， 張曦煌

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

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

徐艮鳳， 張曦煌

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

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

無線傳感器網(wǎng)絡(luò)； 分簇路由算法； 布谷鳥搜索算法； 數(shù)據(jù)融合

0 引 言

無線傳感器網(wǎng)絡(luò) ( wireless sensor networks,WSNs)是由在空間上相互離散的各類傳感器相互協(xié)作構(gòu)成的傳感器網(wǎng)絡(luò)系統(tǒng),使得分布于不同場所的數(shù)量龐大的傳感器之間能夠?qū)崿F(xiàn)更加有效、可靠的通信[1]。無線傳感器網(wǎng)絡(luò)工作時,由于本身能量有限,且不能夠?qū)δ芰窟M行補充,導(dǎo)致其應(yīng)用受到了較大的限制。在這種背景下,延長網(wǎng)絡(luò)生存周期己經(jīng)成為了一個研究的重點。

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

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

1 CS算法

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

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

(1)

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

(2)

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

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

2.1 簇建立階段

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

(3)

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

(4)

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

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

2.2 主、副簇頭的選擇

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

(5)

(6)

則

(7)

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

(8)

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

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

(9)

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

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

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

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

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

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

3 算法仿真與分析

3.1 仿真環(huán)境

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

3.2 仿真結(jié)果

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

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

圖1 網(wǎng)絡(luò)生命周期比較

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

圖2 網(wǎng)絡(luò)總能耗比較

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

圖3 數(shù)據(jù)到基站傳輸量比較

4 結(jié)束語

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

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

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

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

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

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

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

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

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

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-)，女，碩士研究生，主要研究方向為無線傳感器網(wǎng)絡(luò)、嵌入式系統(tǒng)、計算機網(wǎng)絡(luò)，E—mail:2467933944@qq.com。