王 旭， 張曦煌

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

基于布谷鳥(niǎo)搜索算法的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)改進(jìn)路由協(xié)議

王 旭， 張曦煌

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

為了解決無(wú)線(xiàn)傳感器網(wǎng)絡(luò)(WSNs)能量消耗不均衡，網(wǎng)絡(luò)生存時(shí)間短的問(wèn)題，在研究了幾種現(xiàn)有路由協(xié)議基礎(chǔ)上，提出一種基于LEACH協(xié)議改進(jìn)的簇間多跳路由協(xié)議。該協(xié)議引入能量因子、密度因子和距離因子,修正了LEACH協(xié)議的閾值函數(shù)，并結(jié)合布谷鳥(niǎo)搜索算法對(duì)簇頭集合進(jìn)行了優(yōu)化，同時(shí)提出新的路由機(jī)制，在簇頭采用多跳方式和Sink節(jié)點(diǎn)進(jìn)行數(shù)據(jù)通信。模擬實(shí)驗(yàn)表明：相比于LEACH協(xié)議，提出的新協(xié)議可以有效地均衡網(wǎng)絡(luò)節(jié)點(diǎn)能量，延長(zhǎng)網(wǎng)絡(luò)生命周期。

閾值函數(shù)； LEACH協(xié)議； 布谷鳥(niǎo)搜索算法； 多跳

0 引 言

由于無(wú)線(xiàn)傳感器網(wǎng)絡(luò)(WSNs)節(jié)點(diǎn)的電量受限，故延長(zhǎng)網(wǎng)絡(luò)的生命周期是目前無(wú)線(xiàn)傳感器網(wǎng)絡(luò)領(lǐng)域研究的主要問(wèn)題。目前，相關(guān)研究人員已經(jīng)提出多種路由協(xié)議，其中比較經(jīng)典的路由協(xié)議有低能耗自適應(yīng)聚類(lèi)分級(jí)(low energy adaptive clustering hierarchy,LEACH)[1]協(xié)議，PEGASIS[2]協(xié)議等。

布谷鳥(niǎo)搜索算法是全局搜索性能較優(yōu)秀的一種元啟發(fā)式算法，采用相關(guān)的Levy飛行搜索機(jī)制。研究表明，布谷鳥(niǎo)搜索比其他群體優(yōu)化算法更有效。

1 基于布谷鳥(niǎo)算法的新的改進(jìn)協(xié)議

LEACH協(xié)議是無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中最早提出的分層路由協(xié)議，其基本思想是通過(guò)隨機(jī)循環(huán)地選擇簇頭節(jié)點(diǎn)，將網(wǎng)絡(luò)的能耗平均分配到傳感器節(jié)點(diǎn)上，提高網(wǎng)絡(luò)存活時(shí)間。

LEACH協(xié)議采用的閾值方程由于是概率化的，很可能導(dǎo)致以下問(wèn)題：低能量的節(jié)點(diǎn)可能會(huì)成為簇頭節(jié)點(diǎn)，導(dǎo)致節(jié)點(diǎn)提前死亡；選舉的簇頭節(jié)點(diǎn)的數(shù)目不確定，若選舉的簇頭節(jié)點(diǎn)的數(shù)目小于最優(yōu)節(jié)點(diǎn)數(shù)目，會(huì)導(dǎo)致網(wǎng)絡(luò)消耗更多的能量，如果選舉的簇頭節(jié)點(diǎn)的數(shù)目大于最優(yōu)節(jié)點(diǎn)數(shù)，網(wǎng)絡(luò)消耗的能量將不會(huì)達(dá)到最優(yōu)。

由于經(jīng)典LEACH協(xié)議存在許多缺點(diǎn)，故有大量改進(jìn)LEACH的研究[3～6]，這些工作在一定程度上改善網(wǎng)絡(luò)存活時(shí)間。

本文通過(guò)研究已有幾種協(xié)議的優(yōu)缺點(diǎn)，提出一種基于布谷鳥(niǎo)算法的的改進(jìn)多跳路由協(xié)議。

1.1 準(zhǔn)備階段

1.1.1 預(yù)優(yōu)化階段

本文提出一個(gè)備用簇頭選舉方程

Ci(t)=Yi(t)+RNi(t)

(1)

式中

Yi(t)=we×R(i,t)+wm×M(i,t)-wd×S(i,t)

(2)

式中 R(i,t)=E(i,t)/E0；E(i,t)為節(jié)點(diǎn)t輪時(shí)的剩余能量，E0為節(jié)點(diǎn)初始能量，R(i,t)為正因素;M(i,t)=Q(i,t)/Qmax,Q(i,t)普通節(jié)點(diǎn)密度，Qmax為最大密度，M(i,t)為正因素；S(i,t)=D(i,t)/Dmax，D(i,t)為節(jié)點(diǎn)到基站的距離，Dmax為最大距離，S(i,t)為負(fù)因素；we,wm,wd為權(quán)值因子，其中,we=0.7，wm=0.4，wd=0.1。

由于簇頭選擇的隨機(jī)性，故還應(yīng)該加上隨機(jī)因子RNi(t)。

顯然,剩余能量越大，節(jié)點(diǎn)密度越高，節(jié)點(diǎn)距離基站越近，成為簇頭可能越高。

根據(jù)文獻(xiàn)可知，最優(yōu)簇頭數(shù)為

(3)

1.1.2 簇頭選舉階段

在簇頭選舉階段，本文通過(guò)布谷鳥(niǎo)算法搜索(CS)算法[7,8]來(lái)對(duì)備用簇頭集合進(jìn)行優(yōu)化，從而獲得較好的簇頭集合。

為了模擬布谷鳥(niǎo)尋窩的方式，首先，需要設(shè)定以下3個(gè)理想的狀態(tài)：1)布谷鳥(niǎo)一次只產(chǎn)一個(gè)卵，并隨機(jī)選擇鳥(niǎo)窩來(lái)孵化;2)在隨機(jī)選擇的一組鳥(niǎo)窩中，最好的鳥(niǎo)窩將會(huì)被保留到下一代;3)可利用的鳥(niǎo)窩數(shù)量是固定的，一個(gè)鳥(niǎo)窩的主人能發(fā)現(xiàn)一個(gè)外來(lái)鳥(niǎo)蛋的概率P∈[0,1]。

在這3個(gè)理想狀態(tài)的基礎(chǔ)上，布谷鳥(niǎo)尋窩的路徑和位置更新公式如下

(4)

在無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中，能耗是最關(guān)鍵的問(wèn)題，本文提出的目標(biāo)方程為

fmin(CH[Kopt])=(Ech,Eoc)

(5)

(6)

Eoc=∑∑(E(ch)E(oc)

(7)

式中 Ech為簇頭剩余能量，Eoc為普通節(jié)點(diǎn)消耗能量。

通過(guò)上述算法選舉出Kopt個(gè)節(jié)點(diǎn)充當(dāng)簇頭，并向所有節(jié)點(diǎn)廣播簇頭當(dāng)選消息，節(jié)點(diǎn)根據(jù)所收到的信號(hào)強(qiáng)度決定加入哪個(gè)簇。

1.2 穩(wěn)定階段

根據(jù)能量模型可知，傳輸距離對(duì)能耗的影響很大，而在傳統(tǒng)的LEACH協(xié)議中簇頭融合數(shù)據(jù)后一般通過(guò)單跳和基站通信，將獲取的數(shù)據(jù)傳輸給基站，這導(dǎo)致電量很大程度的浪費(fèi)，故本文對(duì)節(jié)點(diǎn)的路由進(jìn)行了改進(jìn)。

如圖1所示，可以將傳感器節(jié)點(diǎn)覆蓋區(qū)域想象成一個(gè)正方形區(qū)域，節(jié)點(diǎn)隨機(jī)分布，可以將此區(qū)域分成3個(gè)區(qū)域：其中，普通區(qū)覆蓋所有區(qū)域；對(duì)于開(kāi)始階段選出來(lái)的簇頭集合，同樣可以將簇頭分為三類(lèi)：路由簇頭、普通簇頭、中轉(zhuǎn)簇頭。

圖1 節(jié)點(diǎn)區(qū)域劃分Fig 1 Node region division

假如傳感網(wǎng)區(qū)域?yàn)檫呴L(zhǎng)為a的正方形區(qū)域，則路由區(qū)所覆蓋的面積百分比為

(8)

Route(mun)=Kopt×Bzz

(9)

路由簇頭：根據(jù)式(8)和式(9)，選擇處于路由區(qū)的Route(num)個(gè)簇頭充當(dāng)路由簇頭，若處于路由區(qū)的簇頭數(shù)目小于Route(num)，則從候補(bǔ)簇頭中選擇，路由簇頭將普通節(jié)點(diǎn)和中轉(zhuǎn)節(jié)點(diǎn)的數(shù)據(jù)傳輸給基站；中轉(zhuǎn)簇頭：若有簇頭處于中轉(zhuǎn)區(qū)，此簇頭為中轉(zhuǎn)簇頭，中轉(zhuǎn)簇頭負(fù)責(zé)中轉(zhuǎn)數(shù)據(jù)；普通簇頭：除路由簇頭和中轉(zhuǎn)簇頭外的其他簇頭，將數(shù)據(jù)傳輸給路由簇頭和中轉(zhuǎn)簇頭；

對(duì)于除路由簇頭以外的所有簇頭

(10)

Broadcast(i)={0.5d0,d0,…k(i)d0}

(11)

式中 Broadcast(i)為簇頭向此區(qū)域廣播的圓心半徑范圍，從而獲得每個(gè)簇頭的鄰居簇頭表

(12)

根據(jù)鄰居簇頭表中的簇頭，分三種路由情況：

1)該簇頭既有路由簇頭也有中轉(zhuǎn)簇頭:將簇頭數(shù)據(jù)按式(12)的比值分別傳輸給它們，傳輸給路由簇點(diǎn)的數(shù)據(jù)直接發(fā)送到基站，中轉(zhuǎn)簇頭節(jié)點(diǎn)的數(shù)據(jù)再循環(huán)路由。

2)該簇頭鄰居簇頭表沒(méi)有路由簇頭:若鄰居簇頭表中沒(méi)有路由簇頭，則將數(shù)據(jù)按式(12)比值傳輸給中轉(zhuǎn)簇頭，然后再循環(huán)路由。

3)該簇頭鄰居簇頭表沒(méi)有中轉(zhuǎn)簇頭:若鄰居簇頭表中沒(méi)有中轉(zhuǎn)簇頭，則將數(shù)據(jù)按式(12)比值傳輸給路由簇頭。

2 仿真與結(jié)果分析

2.1 仿真環(huán)境

在200m×200m的正方形區(qū)域內(nèi)，隨機(jī)分布200個(gè)傳感器節(jié)點(diǎn)，所有傳感器節(jié)點(diǎn)能量有限，位置固定不變。仿真采用Matlab2010b模擬，仿真具體環(huán)境參數(shù)設(shè)置：基站坐標(biāo)(100，250)m，初始能量0.5J，多路衰減模型的功率放大系數(shù)10pJ·bit-1·m-2，自由空間模型的功率放大系數(shù)0.001 3pJ·bit-1·m-2,發(fā)送、接收消耗能量50nJ·bit-1，數(shù)據(jù)包400bit,數(shù)據(jù)融合消耗能量5nJ·bit-1。

2.2 仿真結(jié)果

200個(gè)節(jié)點(diǎn)初始分布如圖2。

圖2 初始200個(gè)節(jié)點(diǎn)分布Fig 2 Initial distribution of 200 nodes

由于初始節(jié)點(diǎn)是隨機(jī)生成的，為了減少誤差，實(shí)驗(yàn)采用5組數(shù)據(jù)觀察算法效果，5次運(yùn)行結(jié)果如表1。

表1 隨機(jī)5次算法運(yùn)行結(jié)果Tab 1 Random 5 times running results of algorithm

如表2可以看出，第一個(gè)節(jié)點(diǎn)死亡時(shí)間大致在500～600輪。

表2 本文算法和LEACH算法比較Tab 2 Comparison of new algorithm and LEACH algorithm

表2和圖3是本文算法和經(jīng)典LEACH算法的比較，從中可以看出:新算法第一個(gè)節(jié)點(diǎn)死亡輪數(shù)為534輪，明顯好于經(jīng)典LEACH算法，且算法均衡全局網(wǎng)絡(luò)能量，延長(zhǎng)網(wǎng)絡(luò)存活時(shí)間。

3 結(jié)束語(yǔ)

本文提出了基于分簇思想的新的算法，在兩個(gè)層面上進(jìn)行了改進(jìn)，第一個(gè)是采用新的備用簇頭選舉方程，并結(jié)合布谷鳥(niǎo)搜索算法，避免經(jīng)典LEACH算法閾值方程的缺陷，并選取最優(yōu)簇頭數(shù)，第二個(gè)改進(jìn)是簇頭的路由機(jī)制，簇頭被分成三類(lèi)簇頭：路由簇頭、中轉(zhuǎn)簇頭、普通簇頭，通過(guò)不同半徑的廣播，簇頭生成鄰居簇頭表，并根據(jù)相應(yīng)公式將數(shù)據(jù)按比例傳輸。算法在一定程度上平衡網(wǎng)絡(luò)能量，延長(zhǎng)節(jié)點(diǎn)存活時(shí)間。

[1] Akyildiz I F,Sankarasubramaniam Y,Su W,et al.Wireless sensor networks:A survey[J].Computer Networks,2002,38(4):393-422.

[2] Stephanie Lmdsey,Cauligi S aghavendra.PEGASIS:Power efficient gathering in sensor information systems[C]∥Proceedings of IEEE Aerospace Conference，2002:1125-1130.

[3] 蘇 淼,錢(qián) 海,王煦法.基于蟻群的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)雙簇頭算法[J].計(jì)算機(jī)工程,2008,34(13):174-176.

[4] 王 進(jìn),邵玉斌,龍 華,等.基于能量和距離加權(quán)的WSNs簇頭選擇算法[J].傳感器與微系統(tǒng),2014,33(5):132-134.

[5] 酈元宏,張衛(wèi)強(qiáng),潘小龍.基于LEACH的能量節(jié)省路由協(xié)議的研究[J].通信系統(tǒng)與網(wǎng)絡(luò)技術(shù),2014，40(5):24-26.

[6] 韓 進(jìn),陳 樹(shù).受限節(jié)點(diǎn)的WSNs非均勻分簇算法應(yīng)用研究[J].傳感器與微系統(tǒng),2014,33(2):19-22.

[7] 王小輝,李圣普,呂海蓮.基于布谷鳥(niǎo)算法的WSNs節(jié)點(diǎn)定位研究[J].計(jì)算機(jī)技術(shù)與發(fā)展,2014(12):208-211.

[8] 鄭巧燕,莫愿斌,劉付永,等.一種小規(guī)模多種群布谷鳥(niǎo)算法[J].計(jì)算機(jī)應(yīng)用與軟件,2014(10):278-280，317.

Improved routing protocol for WSNs based on CuckooSearch

WANG Xu, ZHANG Xi-huang

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

In order to solve problem of unbalanced energy consumption of wireless sensor networks(WSNs),and short lifetime of networks,on the basis of studies on several existing routing protocol based on LEACH protocol,propose an inter-cluster multi-hop routing protocol based on LEACH protocol.The protocol introduces energy factor,density factor and distance factor to correct threshold function for LEACH protocol and optimize cluster head set combined with CuckooSearch,and also propose a new routing mechanism,cluster head nodes communicate with Sink node by multi-hop mode.Simulation results show that,compared with LEACH protocol,the new proposed protocol can balance effectively energy consumption of network nodes,and prolong network lifecycle.

threshold function; LEACH protocol; CuckooSearch; multi-hop

10.13873/J.1000—9787(2016)07—0045—03

2015—10—15

TP 391

A

1000—9787(2016)07—0045—03

王 旭(1991-)，男，江蘇泰州人，碩士研究生，主要研究方向?yàn)闊o(wú)線(xiàn)傳感網(wǎng)絡(luò)、云計(jì)算。