蚁群优化和能量管理的ZigBee网络路由

摘 要：

延长ZigBee网络的寿命是设计ZigBee路由协议的一个重要目的，通过对ZigBee网络协议的研究提出一种基于能量管理的ACOAODV路由协议，能降低网络延时并延长ZigBee网络寿命。仿真结果表明，ACOAODV协议的方法是可行的和节能的，可以在保持较低数据分组的平均端到端时延的同时降低能量开销，达到了低开销、低时延的设计目标。

ス丶词：

蚁群算法；ZigBee；无线自主网按需平面距离矢量路由协议；能量管理

ブ型挤掷嗪牛 TP393

文献标志码：A

英文标题

Ant colony optimization and energy management routing algorithm for ZigBee network

び⑽淖髡呙

PENG You1, YANG Huixian1, MAN Sha2

び⑽牡刂(

1. Faculty of Material and Photoelectronic Physics, Xiangtan University, Xiangtan Hunan 411105, China;

2. College of Information Engineering, Xiangtan University, Xiangtan Hunan 411105, China

英文摘要

)

Abstract:

To prolong the life of ZigBee networks is an important goal to design ZigBee routing protocol. Ant Colony OptimizationAd hoc OnDemand Distance Vector Routing(ACOAODV) based on energy management routing protocol was proposed, which can keep the good network performance and extend the life of ZigBee networks. The simulation results show that ACOAODV algorithm is feasible and energysaving. This approach can maintain a low delay of the average endtoend data packet while effectively reducing energy consumption，so the design goals of low energy consumption and lowdelay are achieved.

英文关键词

Key words:

Ant Colony Optimization (ACO); ZigBee; Ant Colony OptimizationAd hoc OnDemand Distance Vector Routing (AODV); energy management

0 引言

ZigBee网络［1］与其他网络主要的区别是其移动性，ZigBee网络的性能很大程度取决于电池的效率。因此，要充分利用电池的能量来延长ZigBee节点以及整个ZigBee网络的寿命。相对于计算机和其他通信技术的发展，电池的技术进步相对缓慢。针对ZigBee网络关键节点特性来设计路由算法可以在较大程度上降低能量消耗［2］。本文着重从两个方面来降低ZigBee网络的能量消耗。第一是利用蚁群算法来优化无线自主网按需平面距离矢量路由(Ad Hoc OnDemand Distance Vector Routing, AODV)协议路由算法［3］降低路由开销以最大限度地利用有限能源和延长ZigBee网络的寿命；第二是加入能量管理策略，避免低能量节点过度使用而产生易于过早失效的网络节点，达到平衡整体网络能量消耗的目的。

1 ZigBee路由算法与蚁群算法

1.1 ZigBee技术

ZigBee是一种新兴的低成本、低功耗的短距离无线通信协议，主要用于近距离无线连接。在很多个微小的传感器之间相互协调实现通信。这些传感器只需要很少的能量，以接力的方式通过无线将数据从一个传感器传到另一个传感器，通信效率非常高。802.15.4标准定义了ZigBee协议栈MAC和PHY层的标准，制定了具有高可靠、高性价比、低功耗的网络应用规格。图1是ZigBee协议栈图，图2是一种ZigBee网络拓扑图［4-5］。

图片

图1 ZigBee协议栈

图片

图2 ZigBee网络拓扑

1.2 AODV及其优缺点

AODV即无线自组网按需平面距离矢量路由协议，是应用于无线网状网络中进行路由选择的路由协议［6］。该协议是Ad Hoc网络中按需生成路由方式的典型协议和反应式路由协议，只有当向目的节点发送数据时，源节点才在网络中发起路由查找过程，找到相应的路由，且仅在通信过程中才维持路由，当通信完毕后路由将被拆除，节点只需保存它们作为源节点或者中间节点时，到达所需要通信的目的节点的路由，路由开销较少。

通过模拟实验发现按需路由协议AODV存在一些缺点:

1)当一个节点发送数据包而没有路由存在时，它只能等待，直到建立起一条合适的路由才能发送，因此，AODV也存在较长的路由时延。

2)建立路由时，邻居节点依次向周围节点广播此分组直到该分组被送到一个知道目的节点路由信息的中间节点。但是通过这个中间节点找到的路由不一定是最好的路由。

3)没有支持广播节点动态调整等节能策略。

1.3 蚁群算法及其优缺点

蚁群优化（Ant Colony Optimization, ACO）算法是一种用来在网络中寻找优化路径的机率型算法［7］。它由Marco Dorigo创立，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为，通过模拟自然界中蚂蚁集体寻径的行为而提出的一种基于种群的启发式仿生优化系统。蚁群算法基本原理是蚂蚁在外出觅食时，个体之间通过一种称为外激素（“信息素”）的物质进行信息传递，蚂蚁在运动过程中，能够在经过的路径上留下并感知这种物质，并以此来指导自己的运动方向：某一路径上走过的蚂蚁越多，留下的信息就越多，后者选择该路径的可能性就越大。

基本的ACO路由算法［8］在模拟时发现存在如下缺点：

1)节点只是单独依靠蚂蚁来寻找最短路由，当网络动态变化较大和路由生命周期较小时，性能不会很好。

2)在ACO路由算法中没有考虑能量管理，而ZigBee节点能量有限，关键路由节点容易出现失效节点。

2 蚁群优化与能量管理路由算法设计

2.1 ACOAODV算法设计思路

考虑到降低成本、节约能耗和易于使用，ZigBee一般使用简化版本的AODV路由协议，这包含了AODV的主要功能，还具有一定程度的节能优化。为了进一步延长网络的寿命，节约能量，克服传统的AODV路由协议存在的缺点，提出改进的ACOAODV路由算法。算法主要从两个方面来设计。

1)能量管理［9］。根据使用时长设立能量管理，对低电量信息素降低被选中路由概率，对高电量信息素增加优先使用的概率，极大降低失效节点率。改进算法设计中考虑节点的剩余能量，路由选择的时候尽量避开剩余能量较低的节点，使整个网络生存时间延长，提高节点的连接性，从而降低失效节点率。

2)降低时延。根据跳数和时延以及剩余能量函数构建信息素增量，增加短路径和最优路由选中概率。主要在AODV算法组播之前加入蚁群优化处理［10］，快速找出符合条件的路由节点集，缩小组播范围。算法设计时融合ACO算法和AODV算法的优点，利用ACO算法寻找优化路径并结合AODV算法按需路由，降低端到端的时延和寻找路由的延迟，提高网络运行效率。

首先取时延函数T为各节点时延之和，即：

T=∑Ni=0TiВ1）

其中：跳数N即路由中转次数n，剩余能量函数由能量初值E0，时间t和参数α构成，参数α为特定系数, 作用在于减缓能量初值E0减小的速度。

E=1t×E0×αВ2）

从式（2）可以看出节点剩余能量值与节点使用时间成反比，当时间t增大到一定程度，ACOAODV算法使得之前由于剩余能量较低而避免连接使用的一些节点又能继续使用，当时间t趋近于无穷大时，可以认为剩余能量E趋近于零。时延函数，跳数和剩余能量函数组成信息素增量函数，即：

Δ 吉n,d= 1ω┆1T + ω┆2N + ω┆3E -1В3）

其中Е鬲1、ω2、ω3为对应参数的权值。再通过信息素迭代公式（式（4））对信息素进行实时更新。

Еi+1c,d=(1-λ)吉ic,d+Δ ic,dВ4）

其中：Е宋信息素衰减系数(0

Pc,d=(吉ic,d)β∑i∈M(吉ic,d)βВ5）

其中:β为信息素可调权重，M为与节点c相距一跳的所有节点集合，所有下一跳节点概率之和为1。И

Аj∈Mpj,d=1В6）

┑2期

彭友等：蚁群优化和能量管理的ZigBee网络路由

┆扑慊应用 ┑31卷

2.2 算法设计流程

网络初始化后，相关节点产生探索蚂蚁，依据式（1）、（2）计算出时延T，剩余能量E以及跳数N等相关参数，依据式（3）、（4）更新信息素增量和信息素，再按照式（5）计算出相关节点的下一跳选择概率，找到优化路径节点集，用AODV组播，再用后向蚂蚁返回路径，更新所经过的最优路径信息素浓度。

算法设计中，中间节点的路由流程如图3所示。

图片

图3 中间节点路由流程

基于蚁群优化和能量管理的ACOAODV路由算法流程的主要有下面4个步骤。

1）初始化。

程序前

t = 0 ,n = 0,Φi(0)=c, ΔЕ氮i=0；

程序后

2）搜索循环。

程序前

For t=0 to ti do

For node=1 to n do

Launch exploring ant ();

End For

For k = 1 to m do

Compute T，N，E;/*计算蚂蚁到达目的节点的时延T，跳数N，なS嗄芰E，更新信息素增量和信息素*/お

choose the next nodes(p);/*根据概率p来选择下一步可能到达的节点j，じ新找到的优化路径*/お

End For

End For

程序后

3）AODV组播。

程序前

Launch backward ant ();

For each backward ant do

Track back along the exploring ant ();

Update Е氮i();更新当前最优解的蚂蚁所走路径的信息素浓度

Update routing tables ();

End For

程序后

4）处理数据。

程序前

Receive packet from MAC layer ();

Processing data packet ();

Compute network statistics ();

程序后

3 算法分析与实验仿真

3.1 实验环境

仿真工具采用Linux+NS2，网络覆盖面积500@m×500@m，网络节点数目设置为60，设置节点的传输距离为50@m。采用的传输信道数据传输率为250@Kbps，信道延迟为0.3@s，数据包长度为128@bit。网络中设定， 所有节点的初始能量为10B000个能量单位，接收一个消息消耗1个能量单位，发送一个消息消耗 2个能量单位，接收一个信息包消耗2个能量单位，发送一个信息包消耗4个能量单位。每次模拟运行时间为200@s，使用30次模拟的平均数据。

3.2 实验仿真结果

实验仿真结果如图4~6所示。

在图4中可以看出由于ACOAODV算法在探索路由过程中对时延和跳数进行控制，而且避免连接能量较低的节点，所以大幅度节省了网络整体能耗。粒子群算法(Particle Swarm Optimization, PSO)和差分进化(Differential Evolution, DE)算法运行后，可以看出对ZigBee节点能量管理效率比ACOAODV算法低，对能量消耗优化效果不明显，整个网络能耗偏高。

图片

图4 网络能量消耗对比

在图5中可以看出在节点较少时，ACOAODV算法的网络时延较大，降低网络时延的效果不明显。这是因为路由节点较少时，优化的计算开销大；当路由节点数增加时，ACOAODV算法延时优化效果明显增强，而粒子群算法和差分进化算法在节点增加后易出现早熟，容易陷入局部最优，导致网络时延较大。失效节点对比如图6所示，由图6可以看出由于加入了节点能量管理，所以优化算法出现第一个失效节点时间推迟，而粒子群算法和差分进化算法在多目标动态优化方面效率不高，所以运行中出现的失效节点数目较多。运行一段时间后，ACOAODV算法相对于无节点能量管理的差分进化算法和粒子群优化算法失效节点数要明显减少。

图片

图5 网络延时对比

图片

图6 失效节点对比

4 结语

针对基本ZigBee网络AODV算法和网络路由ACO算法，提出一种基于ACOAODV的ZigBee路由算法。ACOAODV算法在传统的按需路由算法上，加入蚁群优化算法，并具体针对时延，跳数和剩余能量进行优化，能在一定程度上降低总体网络能耗，而且保持了低时延的网络性能并减少失效节点，从而延长ZigBee网络寿命。

げ慰嘉南:

［1］

蒋挺，赵成林.紫蜂技术及其应用［M］.北京:北京邮电大学出版社, 2006.

［2］

王芳, 柴乔林,班艳丽.基于ZigBee网络的ZiCL改进算法［J］.计算机应用, 2009, 29(2): 156-159.

［3］

班艳丽,柴乔林,王芳.改进的ZigBee网络路由算法［J］.计算机工程与应用, 2009, 45(5): 95-97.

［4］

ZigBee协议规范篇――网络层［EB/OL］.［2007-01-01］. http:∥.

［5］

王琛, 柴乔林,王芳.基于树形结构的ZigBee能量均衡协议研究［J］.计算机工程与设计, 2009, 30(15): 3534-3536.

［6］

周武斌,罗大庸. ZigBee路由协议的研究［J］.计算机工程与科学, 2009, 31 (6): 12-14.

［7］

梁华为, 陈万明,李帅,等.基于蚁群优化的无线传感器网络能量均衡路由算法［J］. 模式识别与人工智能, 2007, 20(2): 275-280.

［8］

王合义,丁建立,唐万生.基于蚁群优化的路由算法［J］.计算机应用, 2008, 28(1): 13-14.

［9］

FRIEDMAN R, SHOTLAND A, SIMON G. Efficient route discovery in hybrid networks［J］. Ad Hoc Networks, 2008, 7(6): 1110-1124.

［10］

OKDEM S, KARABOGA D. Routing in wireless sensor networks using ant colony optimization［C］//First NASA/ESA Conference on Adaptive Hardware and Systems. Washington, DC: IEEE Computer Society, 2006: 401-404.