基于分簇和蚁群的无线传感器网络多径路由协议

金永贤, 朱 虹

(浙江师范大学 数学与计算机科学学院,浙江 金华 321004)

无线传感器网络是一种便捷的新型自组织网络，已经广泛应用于工业、军事、医学等领域.它是一种由微型传感器组合而成的网络，由于传感器节点的能量有限，易受外界干扰，网络寿命和数据传输的可靠性也大大降低,因此，设计一种能量有效的路由协议是非常重要的.

按照路由特性进行分类，无线传感器路由机制一般可以分为平面型和层次型，或者单径和多径路由.单径路由算法简单、扩展性好，但容错性差，容易发生恶意攻击.一旦路径由于各种各样的原因造成节点故障，就无法将数据包传输到目的节点，尤其是在无线传感器网络这种资源很有限的网络状态下，数据传输的可靠性大大降低.多径路由协议的本质是在无线传感器网络中构建多条备用路径，避免最优路径发生故障造成数据无法成功传输到目的节点.大量研究结果表明，层次型路由和多径路由更加有助于提高网络的能量有效性，均衡网络负载.层次型路由中，分簇算法将网络节点按层次进行划分，由若干个相邻节点构成一个簇，每个簇选出一个簇首节点CH(cluster head)，簇内节点通信由簇首负责.簇的形成可以大大减少数据的传输量，节约节点能量.多径路由中，蚁群算法已逐步成为研究热点，它是一个分布式算法，最早用来解决TSP(travelling salesman problem)旅行商问题[1].蚂蚁在觅食过程中为了给同伴留下食物的位置信号，自身会散发一种信息素，一条路径中留下的信息素越多，证明经过该路径的蚂蚁越多，那么找到食物的可能性也就越大.蚁群算法正是利用该原理,建立了传输数据的最优路径.

分簇路由中，早期比较经典的路由协议是LEACH协议[2]，此协议以随机的方式选取簇首，簇首以单跳的形式将簇内数据融合并转发至汇聚节点(sink节点).由于随机选取簇首，所以不能保证每次都能选出最优簇首进行数据传输，从而导致网络的不稳定性，并且每轮重新选取簇首也会大量耗能.文献[3]提出的PEGASIS协议是在LEACH协议基础上改进的，采用贪婪算法构造链式结构进行通信，减少了节点间通信的平均距离及数据的发送量，其缺点是容易造成较长的通信时延.文献[4]提出了WCA(weighted-clustering approach)协议，采用竞争方式选取簇首，将节点剩余能量作为权重因子系数，权重值最高的即成为簇首.文献[5]提出的HRPNC(hierarchical routing protocol based on non-uniform clustering for wireless sensor network)协议，是一种非均匀分簇路由协议，与LEACH的分簇思想相结合，使用竞争机制竞选簇首，有效解决了“热区”内负载不均衡的问题.

基于蚁群算法的路由中，文献[6]提出了DAR协议，这个协议的特点是:只有在事件驱动时网络才会运行，这样可以节约节点能耗，所以是一种按需的蚁群多径路由协议.该协议的缺点是在选择下一跳节点时没有考虑能量因素，只适用于小规模网络，有一定的局限性.文献[7]提出EEABR(energy efficient ant-based routing algorithm)协议，通过提高信息素增量以降低能耗，延长网络寿命.文献[8]提出ACSBMR协议，综合考虑平均剩余能量和节点最小剩余能量，获取节点距离信息作为启发函数，能够有效降低网络时延，均衡节点能量.文献[9]提出ACOMP (ant colony optimization multipath routing algorithm adopted angle factor)协议，通过添加节点间的角度因子进行路径方向引导，建立可靠节能的路由，但是启发函数未充分考虑节点能量等因素.

在分簇与蚁群相结合的路由协议中，MRP协议[10]在分簇阶段通过延时转发选出簇首，数据传输时根据概率选出能量损耗小且长度短的路径，可以有效延长网络寿命，其缺点是容易陷入局部最优，引起部分节点过早死亡;CAEMP协议[11]采用事件驱动与查询法相混合的数据采集法，采用“先发先胜”的原理选举簇首，减少了开销，但由于没有考虑链路质量等因素，选举簇首的方法可以进一步改进.

基于上述情况，笔者提出了一个蚁群算法和分簇机制相结合的多径路由协议.其主要特点是：当无线传感器网络有事件发生时，各个有效节点通过权重值竞选出簇首，通过成簇方式减少数据传输量.在数据传输时，使用蚁群算法建立多条路径，在计算状态转移概率公式中，改进了信息素浓度因子和启发函数因子.最后，通过计算选择一条最优路径把数据发送至sink节点.

1 MRPCAC协议

1.1 系统模型

在一个M*M的方形区域内，随机散布着N个无线传感器节点，节点具有以下特征：1)每个节点都有唯一ID号(Identification)；2)所有节点的位置都是固定不变的，且知道基站位置；3)根据实际情况,传感器节点的发射功率可以独自调节；4)传感器节点初始量能及性能是一样的;5)传感器节点间的距离可以通过信号强度判断.

节点发送和接收k比特数据所耗的量能公式为:

(1)

ERx(k)=k×Eelec.

(2)

N_IDEresdtoBSPheromone ValueState

图1 节点信息表中数据的存储结构

1.2 分簇阶段

1.2.1 竞选簇首

为了竞选出簇首，每个节点都必须保存一个节点信息表，用于记录节点有关信息，节点信息表数据存储结构如图1所示，节点信息表中含有的元素名称和含义如表1所示.

在簇首节点竞争过程中，若某一个节点的Eres小于邻居节点(所有可以与该节点直接通信的节点为邻居节点)的平均能量Eavg(Eavg为所有邻居节点的剩余能量之和除以邻居节点数目总和)，则退出竞选.候选节点是指所有有资格参与竞选的节点，需要计算自己的权重值Posi(即位置方程)，每次竞选簇首时总是把所有有资格参加竞选的节点中(即一旦某个节点成为簇首，那么这个簇首和其簇内成员节点在下一个簇首竞选中就被排除在外)Posi值最大者当选为簇首，直到选出所有簇首，簇首数量与节点总数、簇首允许的最大成员节点数及节点分布等有关.文献[12]提出的计算节点i的位置方程Posi如式(3)所示(λ1,λ2，λ3都是权重因子系数，表示各项的重要程度，三者之和为1).

(3)

将式(3)改进成

(4)

式(4)增加了Eres和dtoBS.从式(4)可知，Eres越大、dtoBS越小的节点更易成为簇首，这样做有助于竞选出更“优”的簇首.

1.2.2 簇的形成

成功选择簇首后，簇内节点利用时分多址机制进行通信：簇首使用广播方式通知其余普通节点，要求它们选择加入距离最近的一个簇，并回复ACK(acknowledgement)消息，根据普通节点的回复情况，簇首为每个加入簇的普通节点分配时间片.某一时刻，若出现2个一样的回答信号，则簇首将根据节点唯一的标识号依次随机分配不同的时间片.

1.3 多路径的形成

由于传感器网络被划分成多个簇，所以它们各自都需要形成自身到达sink节点的传输路径.它们有2种发送路径的方式：单跳与多跳.如果簇首与sink节点的距离较短，一般采用单跳方式，这种情况下簇首可以直接将数据传输至sink节点，无需通过其他节点间接转发；相反，多跳路径则需要通过其他节点转发进行.本文提出的协议在簇间使用单跳与多跳结合的混合路由传输，簇内则使用单跳传输方式(即普通节点直接把数据发送至簇首).

1.3.1 单跳路径的建立

若dtoBS小于等于最优单跳距离dsin，则簇首可以将有效数据信息直接传输至sink节点；否则，簇首间将使用蚁群算法建立多条多跳路径.节点之点间的最优单跳距离dsin为[13]

(5)

式(5)中：γ是信息发送过程中与距离相关的损耗系数;Eamp表示功率放大的能量;Eelec表示发送过程中的电路损耗;Ecpu表示发送过程中处理数据的损耗.

1.3.2 多跳路径的建立

当dtoBS>dsin时，簇首需要通过其他节点转发完成数据传输，即实行多跳传输.

当簇首接收到成员节点传输来的数据后，检查自身路由信息，若不存在到达sink节点的路径，则缓存要传输的数据，同时向前向蚂蚁发送建立路由信息，这类蚂蚁的工作就是寻找一条到达sink节点的路径.若已经存在有效路径，则按式(6)计算Pij(t)，并按其大小顺序把数据发送转发至下一个节点.

(6)

式(6)中:Pij(t)为t时刻某只蚂蚁从节点i移动到节点j过程的状态转移概率;τij(t)为t时刻节点i至节点j路径上的信息素浓度；ηij(t)为t时刻节点i至节点j的启发函数值，它可以启发蚂蚁结合其他因素选择较优的下一跳节点；Tabu为禁忌表，它存放着同一类型蚂蚁访问过并留下标记的那些节点，同一类型蚂蚁是指从同一源地点出发的蚂蚁；α,β分别代表信息素浓度值及启发函数值的权重因子系数.式(6)中节点j需要满足以下2个条件：1)j是i的邻节点，且j比i距离sink节点更近;2)j不属于禁忌表.下面对式(6)中的2个因子项进行改进.

1)启发函数因子ηij(t)的改进.启发函数值ηij(t)的原计算公式为

(7)

式(7)只考虑了节点间的距离因素，因此,把公式改进成为

(8)

图2 节点间的角度图

式(8)中，

(9)

E为下一跳节点j的初始能量，那么E-Eres就是节点j的耗能；θ为节点i至sink节点连线与节点i至节点j连线间的夹角，如图2所示；k1,k2为权重因子系数，本文实验均设置为1；dij,dis,djs分别为i到j,i到sink,j到sink的距离.

式(8)增加了能量、角度因素.根据式(9)和图2的分析可知，θ值越小时，节点j与sink节点的距离djs也就越近，这是因为两点之间直线距离最短.当Eres越大，且θ和dij都比较小时，ηij(t)越大，则j成为下一跳转移节点的可能性也就更大.

前向蚂蚁到达sink节点后会自行消亡，并生成相应的后向蚂蚁原路返回路径.

2)信息素浓度因子τij(t)的改进.信息素浓度原计算公式为

(10)

(11)

把式(10)改进为

(12)

式(12)中，

(13)

1.4 最优路径寻找与路由维护

当建立若干个有效的传输路径后，需从多条路径中动态选择一条最优路由，将数据传输至sink节点.下面给出一个寻找最优路径的计算方法.

(14)

式(14)中:k为当前已经建立的有效路径数目；Emin为第k条路径上节点能量的最小值；Ek为第k条路径上节点的总能耗值，即这条路径上每个节点的能耗之和，每个节点能耗等于初始能量和剩余能量之差；Hopk为第k条路径长度，即跳数.从式(14)可知，长度越短或实际总能耗越少的路径，fk值越大.其中，fk最大的路径就成为最优路径.若某条路径具有能量瓶颈，则不能成为最优路由.

2 仿真实验结果与分析

为验证本文提出协议算法的有效性，在NS2网络仿真环境下对LEACH协议[2]、EEABR协议[7]、CAEMP协议[11〗和MRPCAC协议进行实验对比，模拟实验环境所用的参数如表2所示.下面从能量有效性(每轮平均能耗和簇首节点能耗波动情况)和网络生存时间(节点存活数目、节点死亡情况)进行实验对比.

表2 仿真实验参数

协议图3 4种协议每轮平均能耗对比图

2.1 能量有效性分析与比较

2.1.1 每轮平均能耗

每轮平均能耗是指每轮所有节点的能耗与节点总数之比.由图3分析可以得出，每轮平均耗能：EACH协议约为0.057 J;EEABR协议约为0.036 J;CAEMP协议约为0.025 J;MRPCAC协议约为0.021 J.在这4种协议中，MRPCAC能耗平均值最低.下面分析一下其中原因：LEACH协议以随机的方式选取簇首，簇首以单跳的形式将簇内数据融合并转发至sink节点.由于随机选取簇首，所以不能

保证每次都能选出最优簇首，从而导致网络的不稳定性，并且每轮重新选取簇首也会大量耗能.由于EEABR协议是通过蚁群算法建立多径路由，通过提高信息素增量以降低能耗，延长网络寿命，因而性能好于LEACH.CAEMP协议采用事件驱动与查询法相混合的数据采集法，采用“先发先胜”的原理选取簇首，这样可以减少开销.MRPCAC协议为了降低数据发送量，用分簇技术将数据直接发送到sink节点；再加上通过对预先设定的阈值判断来决定是否需要重新选举簇首，从而避免每轮重新选举簇首所带来的能量消耗；另外，MRPCAC在簇首间使用多跳路由机制，能够将能量负载均衡地分布在网络中，避免局部产生耗能过大的现象，这样做有利于均衡整个网络能耗.

图4 4种协议簇首能耗波动情况对比图

2.1.2 簇首节点能耗波动

从图4可以看出，LEACH算法采用每轮重新选取簇首，并且采取簇首轮换机制，簇首耗能较多且波动较大；EEABR协议在分簇方式上没有考虑非均匀分簇，靠近sink节点的簇首能耗更大；在数据传输过程中，由于CAEMP协议使用信息素累加方法，在路由建立后，信息素越高的路径承担数据传输

的任务也越重，因而消耗的能量更大；MRPCAC协议只是在第1轮使用竞选方法，之后只在簇内进行竞选，所以簇首分布较为稳定，耗能较少.综上所述，MRPCAC协议只在第1轮会消耗较大能量，因而，其消耗的总能量比其他3种协议更少，从而节能效果更好.

2.2 网络生存时间分析与比较

从图5和图6可看出，LEACH协议从网络系统运作的第500轮左右就出现死亡节点(FND表示出现第1个死亡节点、LND表示最后一个死亡节点出现)，EEABR协议从900轮左右就开始出现死亡节点，CAEMP从1 100轮就开始出现死亡节点，而MRPCAC的死亡节点则是从1 500轮以后才出现.LEACH协议大约在800轮已经有一半的节点死亡，而另外3个协议还没有出现死亡节点，在LEACH出现全部死亡节点时，CAEMP和MRPCAC的大部分节点还是存活的.CAEMP协议最后一个死亡节点大约出现在1 500轮，而MRPCAC协议大约出现在1 700轮，从而可知，MRPCAC协议的网络寿命与CAEMP协议比，也是有所延长的.

图5 网络中节点存活数目对比 图6 4种协议节点的FND和LND数目对比

3 结 语

本文研究和提出了MRPCAC协议.此协议在选择簇首时考虑了能量和邻居节点数量等.簇首间利用蚁群算法建立多条路径，在计算状态转移概率公式中，改进了信息素浓度因子和启发函数因子.协议给出了最优路径计算方法.最后实验结果表明，和其他协议相比，MRPCAC具有能量有效性高、网络负载均衡和网络寿命长等优点.