朱夏冰， 崔寶同

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

無(wú)線傳感器網(wǎng)絡(luò)簇頭多跳路徑路由算法*

朱夏冰， 崔寶同

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

在LEACH協(xié)議特定簇頭選取(DCHS)算法的基礎(chǔ)上，提出了一種基于蟻群優(yōu)化(ACO)的簇頭間多跳路徑(ACO-CHMP)路由算法。該算法先采用DCHS算法分簇，在穩(wěn)態(tài)運(yùn)行階段，利用改進(jìn)的ACO算法找到從距基站最近簇頭節(jié)點(diǎn)到基站的遍歷所有簇頭節(jié)點(diǎn)的最優(yōu)路徑，然后從該簇頭節(jié)點(diǎn)開(kāi)始沿著最優(yōu)路徑進(jìn)行數(shù)據(jù)傳輸?shù)交?。仿真結(jié)果表明:與LEACH算法、DCHS算法和ACO算法相比，該算法極大地均衡了網(wǎng)絡(luò)的能量消耗，延長(zhǎng)了無(wú)線傳感器網(wǎng)絡(luò)生命周期。

無(wú)線傳感器網(wǎng)絡(luò)； DCHS算法； 蟻群優(yōu)化； 蟻群優(yōu)化的簇頭間多跳路徑； 生命周期

0 引 言

無(wú)線傳感器網(wǎng)絡(luò)(WSNs)是一種新型的無(wú)線通信網(wǎng)絡(luò)。路由協(xié)議是無(wú)線傳感器網(wǎng)絡(luò)的一個(gè)核心環(huán)節(jié)，因節(jié)點(diǎn)的能量有限、動(dòng)態(tài)拓?fù)浣Y(jié)構(gòu)以及數(shù)據(jù)融合處理等問(wèn)題，路由協(xié)議的設(shè)計(jì)顯得尤為關(guān)鍵[1]。

無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議從網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的角度考慮一般分為兩類(lèi)：平面路由協(xié)議和分簇路由協(xié)議。LEACH(low energy adaptive clustering hierarchy)[2]算法是一種經(jīng)典的分簇路由協(xié)議，但是該算法對(duì)節(jié)點(diǎn)剩余能量和節(jié)點(diǎn)分布位置等因素缺乏考慮，導(dǎo)致簇頭的分布位置不均衡。文獻(xiàn)[3]提出了特定簇頭選取(deterministic custer-head selection，DCHS) 算法，通過(guò)將剩余能量因素加入到閾值公式，一定程度避免了低剩余能量的節(jié)點(diǎn)當(dāng)選簇首，但簇首與基站間的單跳通信會(huì)消耗大部分能量。文獻(xiàn)[4，5]分別在不均勻分簇和LEACH分簇的基礎(chǔ)上，利用蟻群優(yōu)化(ant colony optimization,ACO)算法分別尋找每一個(gè)簇頭節(jié)點(diǎn)到匯聚節(jié)點(diǎn)的最優(yōu)路徑，但會(huì)造成蟻群尋路的擁擠與阻塞，同時(shí)影響網(wǎng)絡(luò)快速性。

本文在DCHS算法的基礎(chǔ)上，提出了一種基于ACO的簇頭間多跳路徑(ACO-CHMP)路由算法。該算法先采用DCHS算法分簇，在穩(wěn)態(tài)運(yùn)行階段，結(jié)合ACO算法解決TSP問(wèn)題的方法，并加以改進(jìn)，只尋找從距基站最近簇頭節(jié)點(diǎn)到基站的，遍歷所有簇頭節(jié)點(diǎn)的最優(yōu)路徑，然后從該簇頭節(jié)點(diǎn)開(kāi)始沿著最優(yōu)路徑進(jìn)行數(shù)據(jù)傳輸?shù)交?且將螞蟻選擇下一城市節(jié)點(diǎn)的能量因素與其至基站的距離因素考慮到啟發(fā)函數(shù)中。該算法只有全局一條最優(yōu)路徑，有效地避免了分別由每個(gè)簇頭節(jié)點(diǎn)找尋最優(yōu)路徑來(lái)傳輸數(shù)據(jù)到基站。

1 ACO算法

ACO算法解決TSP問(wèn)題[6,7]的基本原理如下：

(1)

(2)

其中，ηij(t)為啟發(fā)函數(shù)，表示螞蟻從城市i轉(zhuǎn)移到城市j的期望程度；Ej為j城市節(jié)點(diǎn)的當(dāng)前能量；E0為所有城市節(jié)點(diǎn)的初始能量；d(j,BS)為當(dāng)前城市節(jié)點(diǎn)距基站的距離；D為常量；allowk為螞蟻k未訪問(wèn)城市的集合；α為信息素重要程度的因子；β為啟發(fā)函數(shù)重要程度的因子。

當(dāng)所有螞蟻完成一次循環(huán)后，各城市連接路徑上的信息素需進(jìn)行更新，即

τij(t+1)=(1-ρ)τij(t)+Δτij(t,t+1),

(3)

(4)

信息素更新策略選擇Dorigo M提出的蟻周模型[8]，計(jì)算公式如下

(5)

其中，Q為信息素強(qiáng)度；Lk為第k只螞蟻經(jīng)過(guò)的路徑的長(zhǎng)度。

2 基于ACO的簇頭間多跳路徑(ACO-CHMP)路由算法

2.1 簇的建立階段

簇的建立階段，該算法采用與DCHS算法相同的方式，簇頭選擇公式如下

(6)

其中，p為簇頭占所有節(jié)點(diǎn)的百分比，rmod(1/p)為當(dāng)前輪數(shù)被1/p整除后的余數(shù)，En_current為節(jié)點(diǎn)當(dāng)前的能量，En_max為節(jié)點(diǎn)初始能量，G為最近1/p輪中沒(méi)有擔(dān)任過(guò)簇頭的節(jié)點(diǎn)集合。

根據(jù)簇頭選擇公式(6)，每個(gè)節(jié)點(diǎn)從0到1的隨機(jī)數(shù)中任意選擇一個(gè)，若當(dāng)前輪中這個(gè)數(shù)值小于域值T(n)，則當(dāng)選為簇頭。

2.2 ACO-CHMP路由算法尋找簇頭間多跳最優(yōu)路徑

在各個(gè)簇頭完成了收集簇內(nèi)數(shù)據(jù)之后，在距離基站最近的簇頭節(jié)點(diǎn)放置m只前向螞蟻，尋找遍歷所有簇頭節(jié)點(diǎn)，并最終到達(dá)Sink節(jié)點(diǎn)的最優(yōu)路徑。前向螞蟻實(shí)際上就是只包含了很小的消息格式的數(shù)據(jù)結(jié)構(gòu)，包括螞蟻的序號(hào)，源節(jié)點(diǎn)的ID，路徑記錄表Table，下一簇頭節(jié)點(diǎn)的ID，以及經(jīng)過(guò)的路徑長(zhǎng)度Lengh。前向螞蟻的行進(jìn)規(guī)則為：

1)每只螞蟻從源節(jié)點(diǎn)出發(fā)，將源簇頭節(jié)點(diǎn)編號(hào)賦值為T(mén)abu的第一個(gè)元素，根據(jù)公式(1)選擇下一訪問(wèn)的簇頭節(jié)點(diǎn)，確定下一簇頭節(jié)點(diǎn)的ID，之后每經(jīng)過(guò)一個(gè)節(jié)點(diǎn)，更新相應(yīng)的下一簇頭節(jié)點(diǎn)ID和經(jīng)過(guò)的路徑長(zhǎng)度Lengh。

2)如果前向螞蟻行進(jìn)到非目的簇頭節(jié)點(diǎn)，該簇頭節(jié)點(diǎn)與螞蟻中下一簇頭節(jié)點(diǎn)ID不符合，則遣回該螞蟻，自己并不進(jìn)行傳輸。

3)直到前向螞蟻遍歷了所有簇頭節(jié)點(diǎn)，最終到達(dá)Sink節(jié)點(diǎn)，再由Sink節(jié)點(diǎn)發(fā)送逆向螞蟻，進(jìn)行信息素的更新。

前向螞蟻到達(dá)Sink節(jié)點(diǎn)后，將自己的記憶全部轉(zhuǎn)移給逆向螞蟻，自身將被刪除。Sink節(jié)點(diǎn)記錄最佳路徑，并派出逆向螞蟻，逆向螞蟻沿著與前向螞蟻完全相反的路徑來(lái)更新各個(gè)簇頭節(jié)點(diǎn)之間的信息素濃度。信息素濃度更新由公式(3)～式(5)所決定。這就完成了一次迭代，這里設(shè)置最大迭代次數(shù)為100。

前向螞蟻和逆向螞蟻的消息格式圖[9]如圖1所示。

圖1 前向螞蟻和逆向螞蟻的消息格式圖Fig 1 Message format chart of forward ants and reverse ants

直到達(dá)到最大迭代次數(shù)，由Sink節(jié)點(diǎn)選出最優(yōu)路徑，發(fā)送給源簇頭節(jié)點(diǎn)，然后，由該簇頭節(jié)點(diǎn)開(kāi)始，沿著該路徑進(jìn)行數(shù)據(jù)傳輸。值得指出的是，下一簇頭節(jié)點(diǎn)將上一簇頭節(jié)點(diǎn)的數(shù)據(jù)與本簇的數(shù)據(jù)融合后，再發(fā)往下一個(gè)簇頭，直至將數(shù)據(jù)發(fā)送至Sink節(jié)點(diǎn)(基站)。

該部分算法的偽代碼如下：

Initializationm=15;alpha=1;beta=4;rho=0.15;Q=1;Tau=ones(a,a);Table=zeros(m,a);

Whileiter<=iter_max

start=dis_cluster.*ones(m,1);

Table(:,1)=start;

forb= 1︰m

chose the next CH using the formula(1)

update theTable(b,:)

ifTable(b,a)=a

calculate Length(b)

preserve Length_best and Route_best

update theTauusing the formula(3)，(4)，(5)

iter=iter+1

Table=zeros(m,a)

End

Output the Shortest_Route

以上偽代碼中，a表示簇頭數(shù)目加1，意思是把Sink節(jié)點(diǎn)也算在內(nèi)，并且Sink節(jié)點(diǎn)表示第a個(gè)簇頭。

本文設(shè)置α=1，β=4，ρ=0.15，使得啟發(fā)函數(shù)重要因子置于關(guān)鍵位置。值得指出的是，本文對(duì)ACO算法解決TSP問(wèn)題的改進(jìn)在于，只在距離基站最近的簇頭放置螞蟻群，來(lái)尋找遍歷所有簇頭節(jié)點(diǎn)，最終到達(dá)基站的最短路徑。在啟發(fā)函數(shù)中，考慮到當(dāng)前城市節(jié)點(diǎn)的能量因素與當(dāng)前城市節(jié)點(diǎn)距基站距離的因素。在蟻群尋優(yōu)過(guò)程中，只對(duì)終點(diǎn)到達(dá)Sink節(jié)點(diǎn)的路徑進(jìn)行信息素的更新，并且只記錄這些路徑。最短路徑不是閉合的形式。最關(guān)鍵的是全局只有一條最優(yōu)路徑。

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

為了驗(yàn)證該算法的有效性，本文采用Matlab進(jìn)行仿真。設(shè)置仿真環(huán)境為：在200 m×200 m的監(jiān)測(cè)區(qū)域，隨機(jī)分布了200個(gè)傳感器節(jié)點(diǎn)，監(jiān)測(cè)區(qū)域的平面坐標(biāo)范圍為(0,0)～(200,200)m?；揪嚯x監(jiān)測(cè)區(qū)域很遠(yuǎn)，坐標(biāo)位置為(100,350)m。數(shù)據(jù)包和控制包大小分別為Packetgth=4 000 bit，Ctrpacketgth=100 bit。每個(gè)節(jié)點(diǎn)的初始能量為0.5 J。本文采用與文獻(xiàn)[10]相同的通信能耗模型，簇頭占全部節(jié)點(diǎn)的比例同樣依據(jù)該文獻(xiàn)，取p=0.05。本文定義網(wǎng)絡(luò)生命周期為從仿真開(kāi)始到最后一個(gè)節(jié)點(diǎn)耗盡能量經(jīng)過(guò)的輪數(shù)。

圖2為仿真出的距基站最近的簇頭遍歷所有簇頭并最終到達(dá)基站的最優(yōu)路徑。

圖2 從源簇頭到基站的多跳最優(yōu)路徑Fig 2 Optimal multi-hop path from the source cluster-head to the base station

從圖中可以看出:從距基站最近的簇頭出發(fā)，遍歷了所有簇頭后到達(dá)基站的最優(yōu)路線，將避免簇頭直接與基站間的長(zhǎng)距離通信。每個(gè)簇頭在收到上一個(gè)簇頭的數(shù)據(jù)后，與自己的數(shù)據(jù)融合，并且傳送到下一個(gè)簇頭，直至將數(shù)據(jù)傳輸至基站。

ACO-CHMP算法與LEACH算法、DCHS算法和文獻(xiàn)[5]所用ACO算法的節(jié)點(diǎn)剩余數(shù)目與網(wǎng)絡(luò)運(yùn)行輪數(shù)的關(guān)系圖如圖3所示。

圖3 節(jié)點(diǎn)剩余數(shù)目與網(wǎng)絡(luò)運(yùn)行輪數(shù)的關(guān)系圖Fig 3 Relationship between residual number of nodes and running round number of network

由圖可知，相比LEACH算法，DCHS算法使得網(wǎng)絡(luò)出現(xiàn)第一個(gè)死亡節(jié)點(diǎn)的運(yùn)行周期提高了35 %左右，但由于簇頭與基站的長(zhǎng)距離單跳通信，網(wǎng)絡(luò)整體生命周期并未很大地改善。文獻(xiàn)[5]所用ACO算法相較LEACH與DCHS算法，第一個(gè)節(jié)點(diǎn)死亡時(shí)間和整個(gè)網(wǎng)絡(luò)的生命周期都有所提高，但每一個(gè)簇頭節(jié)點(diǎn)都利用蟻群找尋到匯聚節(jié)點(diǎn)的最優(yōu)路徑，會(huì)造成蟻群尋路的擁擠與阻塞，而且影響網(wǎng)絡(luò)的快速性。而ACO-CHMP算法，整體只使用全局最優(yōu)路徑，并且在蟻群尋路的啟發(fā)函數(shù)中加入了當(dāng)前城市節(jié)點(diǎn)的能量因素與當(dāng)前城市節(jié)點(diǎn)距基站距離的因素。由仿真圖可以看出：ACO-CHMP算法使網(wǎng)絡(luò)的整體能耗極大得均衡，網(wǎng)絡(luò)出現(xiàn)第一個(gè)死亡節(jié)點(diǎn)的周期為425輪，相比前3種算法都有特別明顯地提高，整個(gè)網(wǎng)絡(luò)的生命周期也相較于LEACH算法也提升了50 %左右,得到大幅度延長(zhǎng)。

4 結(jié) 論

本文提出的ACO-CHMP路由算法，在分簇階段考慮到節(jié)點(diǎn)剩余能量；在數(shù)據(jù)通信階段，利用ACO算法找到由距基站最近簇頭出發(fā)，遍歷所有簇頭到基站的全局最優(yōu)路徑，然后從該簇頭節(jié)點(diǎn)出發(fā)傳送數(shù)據(jù),并且在啟發(fā)函數(shù)中加入了當(dāng)前城市節(jié)點(diǎn)的能量因素與當(dāng)前城市節(jié)點(diǎn)距基站距離的因素。該算法顯著地延長(zhǎng)了出現(xiàn)第一個(gè)死亡節(jié)點(diǎn)的運(yùn)行周期，并且使得網(wǎng)絡(luò)的生命周期也有大幅地提高。

[1] Park P,Fischione C,Bonivento A,et al.Breath:A self-adapting protocol for wireless sensor networks[C]∥The 5th Annual IEEE Communications Society Conference on Sensor,Mesh and Ad Hoc Communications and Networks,California,USA,2008:323-331.

[2] Heinzelman W B,Chandrakasan A,Balakrishnan H.Energy-efficient communication protocol for wireless microsensor network-s[C]∥Proceedings of the 33rd Hawaii International Conference on System Sciences,Maui,Hawaii,2000:3005-3014.

[3] Handy M J,Haase M,Timmermann D.Low energy adaptive clustering hierarchy with deterministic cluster-head selection[C]∥The 4th IEEE International Conference on Mobile and Wireless Communication Network,Dalian,China,2002:368-372.

[4] Du J,Wang L.Uneven clustering routing algorithm for wireless sensor networks based on ant colony optimization[C]∥The 3rd IEEE International Conference on Computer Research and Deve-lopment,Shanghai,China,2011:67-71.

[5] Salehpour A A,Mirmobin B,Afzali-kusha A,et al.An energy efficient routing protocol for cluster-based wireless sensor networks using ant colony optimization[C]∥International Conference on Innovations in Information Technology(IIT 2008),2008:455-459.

[6] Dorigo M,Gambardella L M. Ant colony system:A cooperative learning approach to the traveling salesman problem[J].IEEE Transactions on Evolutionary Computation,1997,1(1):53-66.

[7] 史 峰,王 輝,郁 磊,等.Matlab智能算法30個(gè)案例分析[M].北京:北京航空航天大學(xué)出版社,2010:205-215.

[8] Dorigo M,Birattari M,Stutzle T.Ant colony optimization[J].IEEE Computational Intelligence Magazine,2006,1(4):28-39.

[9] Saleh A M S,Ali B M,Rasid M,et al.A self-optimizing scheme for energy balanced routing in wireless sensor networks using sensorant[J].Sensors,2012,12(8):11307-11333.

[10] Heinzelman W B,Chandrakasan A,Balakrishnan H.An application-specific protocol architecture for wireless microsensor networks[J].IEEE Transactions on Wireless Communication,2002,1(4):660-670.

Cluster-head multi-hop path routing algorithm for WSNs*

ZHU Xia-bing, CUI Bao-tong

(School of IOT Engineering,Jiangnan University,Wuxi 214122,China)

On basis of low energy adaptive clustering hierarchy(LEACH)with deterministic cluster-head selection(DCHS)algorithm,propose a cluster-head multi-hop path routing algorithm based on ant colony optimization(ACO-CHMP).This algorithm first uses DCHS algorithm to set up clusters,in steady-state operating phase,it uses the improved ACO to find out the optimal path that travels through all the cluster heads from the cluster head node which is nearest to the BS to BS,then transmit data along the optimal path from the cluster head to BS.The result of simulation shows that compared with LEACH algorithm,DCHS algorithm and ACO algorithm,this algorithm greatly balances network energy consumption,prolong lifecycle of wireless sensor networks(WSNs).

wireless sensor networks(WSNs); DCHS algorithm; ant colony optimization(ACO); ACO-CHMP; lifecycle

2013—08—15

TP 212.9

A

1000—9787(2014)04—0115—03

朱夏冰(1990-),男,河南信陽(yáng)人,碩士研究生,主要研究方向?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)能量管理。