无线传感器网络簇头多跳路径路由算法*

朱夏冰， 崔宝同

(江南大学 物联网工程学院,江苏 无锡 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-),男,河南信阳人,硕士研究生,主要研究方向为无线传感器网络能量管理。