無線傳感器網絡簇頭多跳路徑路由算法*

朱夏冰， 崔寶同

(江南大學 物聯網工程學院,江蘇 無錫 214122)

無線傳感器網絡簇頭多跳路徑路由算法*

朱夏冰， 崔寶同

(江南大學 物聯網工程學院,江蘇 無錫 214122)

在LEACH協議特定簇頭選取(DCHS)算法的基礎上，提出了一種基于蟻群優化(ACO)的簇頭間多跳路徑(ACO-CHMP)路由算法。該算法先采用DCHS算法分簇，在穩態運行階段，利用改進的ACO算法找到從距基站最近簇頭節點到基站的遍歷所有簇頭節點的最優路徑，然后從該簇頭節點開始沿著最優路徑進行數據傳輸到基站。仿真結果表明:與LEACH算法、DCHS算法和ACO算法相比，該算法極大地均衡了網絡的能量消耗，延長了無線傳感器網絡生命周期。

無線傳感器網絡； DCHS算法； 蟻群優化； 蟻群優化的簇頭間多跳路徑； 生命周期

0 引 言

無線傳感器網絡(WSNs)是一種新型的無線通信網絡。路由協議是無線傳感器網絡的一個核心環節，因節點的能量有限、動態拓撲結構以及數據融合處理等問題，路由協議的設計顯得尤為關鍵[1]。

無線傳感器網絡路由協議從網絡拓撲結構的角度考慮一般分為兩類：平面路由協議和分簇路由協議。LEACH(low energy adaptive clustering hierarchy)[2]算法是一種經典的分簇路由協議，但是該算法對節點剩余能量和節點分布位置等因素缺乏考慮，導致簇頭的分布位置不均衡。文獻[3]提出了特定簇頭選取(deterministic custer-head selection，DCHS) 算法，通過將剩余能量因素加入到閾值公式，一定程度避免了低剩余能量的節點當選簇首，但簇首與基站間的單跳通信會消耗大部分能量。文獻[4，5]分別在不均勻分簇和LEACH分簇的基礎上，利用蟻群優化(ant colony optimization,ACO)算法分別尋找每一個簇頭節點到匯聚節點的最優路徑，但會造成蟻群尋路的擁擠與阻塞，同時影響網絡快速性。

本文在DCHS算法的基礎上，提出了一種基于ACO的簇頭間多跳路徑(ACO-CHMP)路由算法。該算法先采用DCHS算法分簇，在穩態運行階段，結合ACO算法解決TSP問題的方法，并加以改進，只尋找從距基站最近簇頭節點到基站的，遍歷所有簇頭節點的最優路徑，然后從該簇頭節點開始沿著最優路徑進行數據傳輸到基站,且將螞蟻選擇下一城市節點的能量因素與其至基站的距離因素考慮到啟發函數中。該算法只有全局一條最優路徑，有效地避免了分別由每個簇頭節點找尋最優路徑來傳輸數據到基站。

1 ACO算法

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

(1)

(2)

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

當所有螞蟻完成一次循環后，各城市連接路徑上的信息素需進行更新，即

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

(3)

(4)

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

(5)

其中，Q為信息素強度；Lk為第k只螞蟻經過的路徑的長度。

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

2.1 簇的建立階段

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

(6)

其中，p為簇頭占所有節點的百分比，rmod(1/p)為當前輪數被1/p整除后的余數，En_current為節點當前的能量，En_max為節點初始能量，G為最近1/p輪中沒有擔任過簇頭的節點集合。

根據簇頭選擇公式(6)，每個節點從0到1的隨機數中任意選擇一個，若當前輪中這個數值小于域值T(n)，則當選為簇頭。

2.2 ACO-CHMP路由算法尋找簇頭間多跳最優路徑

在各個簇頭完成了收集簇內數據之后，在距離基站最近的簇頭節點放置m只前向螞蟻，尋找遍歷所有簇頭節點，并最終到達Sink節點的最優路徑。前向螞蟻實際上就是只包含了很小的消息格式的數據結構，包括螞蟻的序號，源節點的ID，路徑記錄表Table，下一簇頭節點的ID，以及經過的路徑長度Lengh。前向螞蟻的行進規則為：

1)每只螞蟻從源節點出發，將源簇頭節點編號賦值為Tabu的第一個元素，根據公式(1)選擇下一訪問的簇頭節點，確定下一簇頭節點的ID，之后每經過一個節點，更新相應的下一簇頭節點ID和經過的路徑長度Lengh。

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

3)直到前向螞蟻遍歷了所有簇頭節點，最終到達Sink節點，再由Sink節點發送逆向螞蟻，進行信息素的更新。

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

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

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

直到達到最大迭代次數，由Sink節點選出最優路徑，發送給源簇頭節點，然后，由該簇頭節點開始，沿著該路徑進行數據傳輸。值得指出的是，下一簇頭節點將上一簇頭節點的數據與本簇的數據融合后，再發往下一個簇頭，直至將數據發送至Sink節點(基站)。

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

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表示簇頭數目加1，意思是把Sink節點也算在內，并且Sink節點表示第a個簇頭。

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

3 仿真結果與分析

為了驗證該算法的有效性，本文采用Matlab進行仿真。設置仿真環境為：在200 m×200 m的監測區域，隨機分布了200個傳感器節點，監測區域的平面坐標范圍為(0,0)～(200,200)m。基站距離監測區域很遠，坐標位置為(100,350)m。數據包和控制包大小分別為Packetgth=4 000 bit，Ctrpacketgth=100 bit。每個節點的初始能量為0.5 J。本文采用與文獻[10]相同的通信能耗模型，簇頭占全部節點的比例同樣依據該文獻，取p=0.05。本文定義網絡生命周期為從仿真開始到最后一個節點耗盡能量經過的輪數。

圖2為仿真出的距基站最近的簇頭遍歷所有簇頭并最終到達基站的最優路徑。

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

從圖中可以看出:從距基站最近的簇頭出發，遍歷了所有簇頭后到達基站的最優路線，將避免簇頭直接與基站間的長距離通信。每個簇頭在收到上一個簇頭的數據后，與自己的數據融合，并且傳送到下一個簇頭，直至將數據傳輸至基站。

ACO-CHMP算法與LEACH算法、DCHS算法和文獻[5]所用ACO算法的節點剩余數目與網絡運行輪數的關系圖如圖3所示。

圖3 節點剩余數目與網絡運行輪數的關系圖Fig 3 Relationship between residual number of nodes and running round number of network

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

4 結 論

本文提出的ACO-CHMP路由算法，在分簇階段考慮到節點剩余能量；在數據通信階段，利用ACO算法找到由距基站最近簇頭出發，遍歷所有簇頭到基站的全局最優路徑，然后從該簇頭節點出發傳送數據,并且在啟發函數中加入了當前城市節點的能量因素與當前城市節點距基站距離的因素。該算法顯著地延長了出現第一個死亡節點的運行周期，并且使得網絡的生命周期也有大幅地提高。

[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個案例分析[M].北京:北京航空航天大學出版社,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-),男,河南信陽人,碩士研究生,主要研究方向為無線傳感器網絡能量管理。