基于分簇的能量有效多路径路由协议的研究*

童孟军，李光辉，徐小良

(1.浙江农林大学信息工程学院，杭州临安311300;2.杭州电子科技大学计算机学院，杭州310018)

无线传感器网络WSNs(Wireless Sensor Networks)［1］是继Internet之后随着无线通信技术、传感器技术、微电子技术和分布信息处理技术发展起来的一种新兴信息获取技术。WSNs综合了嵌入式技术、传感器技术、通信技术和分布式信息处理技术，能够协作实时感知、监测、采集网络分布区域内的各种环境的信息，并对数据进行适当的处理以获得精简准确的信息，并传送给最终的用户。收集环境数据是无线传感网的主要目的，无线传感网中收集环境数据的方法有以下几种方法［2］:

周期传输 汇聚节点定期收到传感器节点发来的数据信息。

事件驱动型 汇聚节点平时收不到任何数据，只有当有事件发生时，传感节点才会产生数据信息给汇聚节点。

查询型 只有在收到汇聚节点发出的请求包后，传感节点才会发送数据给汇聚节点。

混合型 采用的是以上三种方法中的的两到三种方法的信息传输方法。

事件型驱动网络中，一般在同一个事件区域布置大量的无线传感网节点，当有事件发生时，也就是传感器节点检测的事件信息超过某一个门限值，传感节点会被动发送数据给汇聚节点。事件型网络可应用于森林检测、水资源环境和火灾报警等，这样的网络有个特点，网络规模大，节点多，事件附近的信息都比较类似，如果有大量的源节点要发送数据，会产生大量的路由请求开销、数据发送冲突和能量消耗。而分簇机制非常适合这种事件型驱动的网络。

目前已经开发出多种以节约能量为目的的路由协议，其中最流行和有效的方法是分簇机制。平面路由协议具有简单、健壮性好等优点，但数据传输的跳数较多，适用于小规模网络。对于大规模的无线传感网，层次型路由协议是一个很好的选择。在层次型路由协议中使用分簇技术将达到很高的能量有效性。此外，分簇还可以提高网络的可扩展性，以及降低由于数据分组转发带来的时延。

对于汇聚节点来说，有时候也可能需要查询事件区域的信息，对于这样网络情况，从汇聚节点出发的搜索蚂蚁机制非常合适。

本文提出一种基于分簇和蚁群算法［3］的能量有效的多路径路由协议CAEMP(Cluster-Based and Ant-Based Energy-Efficient Multipath Protocol)，主要适用于事件驱动和查询的混合数据采集方法。对于事件区域附近的节点，由于感知信息的高度相似性，通过成簇的方法来减少发送的数据。对于汇聚节点，如果需要事件区域的数据，可以采用发送搜索蚂蚁到事件区域的方法来获取所需要的数据，同时在链路上释放搜索信息素［4－5］。事件区域形成的簇，簇头可以通过发送前向蚂蚁的方法来寻找到汇聚节点的多路径，搜索蚂蚁留下的信息素可以加快前向蚂蚁到达汇聚节点的速度。

1 相关工作

在WSNs的研究技术领域，网络的拓扑控制具有重要的研究意义。通过拓扑控制技术可以优化网络拓扑，节省不必要的节点能量损耗，有利于延长网络的寿命。拓扑控制包括功率控制和层次型拓扑控制。功率控制是调节节点的发送功率，均衡每个节点的单跳邻居节点数目，使得网络的能量更加均衡，延长网路寿命。层次型拓扑控制采用分簇机制，即一个网络分为几个簇，每个簇选择一个簇头，同一个簇内的节点均将数据发送给簇头，由簇头同簇外通信。

在无线传感网中，有许多的分簇机制可以有效地提高网络能量的利用效率。在许多的分簇算法中，簇头CH(Cluster Head)节点的选择是基于节点的ID号、节点的执行能力和节点的度量［6］等。还有一些分簇算法试图在同一个地方的网络中耗尽所有传感器节点的能量，为了实现这个目标，CH节点的选取就要依靠节点的剩余能量或者周期性地重新成簇［7］。然而像文献［8］中提到的一样，许多的分簇算法规定了簇的大小或者集中在减少簇内节点的数量。另外许多分簇算法是基于传感器节点的度、剩余能量和选择CH节点的连接性提出的。然而，大多数的这些分簇算法没有考虑WSNs中具体的数据采集问题。

分簇和多路径路由协议结合，是近年来WSNs中数据采集问题研究的一个热点问题。文献［9］按照节点与汇聚节点之间的距离对网络进行了分层，这里的距离用跳数来进行计量。在网络分层的基础上，研究人员提出了多路径路由协议，从而可以达到网络能量消耗的负载均衡。但这种网络分层的方法只适合比较小的网络系统。

针对现有多路径路由算法中可扩展性差的问题，在文献［10］中作者提出了一种基于簇的多路径路由算法CBMRP，该算法使用分簇的方法来提高可扩展性。首先利用基于簇的层次结构动态处理网络拓扑变化，能够减少路由管理和路由维护的开销，另外利用建立多路径来传输数据，可以实现拥塞避免和负载均衡，实现网络带宽的优化应用。CBMRP协议是一个单层簇、分布式推进逐段查找路径的多路径路由协议，其缺点是:采用单层簇的简单结构可扩展性较差，适用范围有限;采用分布式逐段查找路径方法对于稍大一点网络，这种方法查找路径太过繁杂，开销迅速增加。

针对无线传感网中节点数量多、节点分布不均匀、网络拓扑动态变化等特点，在文献［11］中作者提出一种基于簇头指挥路径的多路径路由协议(CDPMR)，运用该协议的无线传感网，簇头负责簇的管理、簇指挥路径生成、指挥簇成员生成多路径路由。对于大规模的无线传感网来说，CDPMR协议使得网络可扩展性好、稳定性高，能及时响应网络负载和网络局部变化，有效减少网络重构代价，节省能量。在生成多路径路由阶段，簇头考虑当前节点的实时信息，生成多路径路由速度快，健壮性好，负载均衡，网络吞吐量高，从而有利于延长网络生命周期。

针对事件驱动型的无线传感网，按需的事件驱动路由算法可以克服主动型协议的许多缺点，在文献［12］中作者提出了一种被动分簇多路径算法(PPCMP)，PPCMP算法在逻辑上将网络划分为簇，并使用分层管理策略，以实现能量的有效利用、可扩展性和负载平衡。算法执行分为许多轮次，在第一轮使用事件驱动的按需分簇，而在以后的轮次采用主动分簇。簇头和各个簇内节点的通信是在规定的不同的时隙内完成的。在簇外使用不交叉的多路径来实现簇头和Sink节点之间的通信，以避免拥塞及扩大带宽。最佳路径搜索和多路径扩展是建立多路径路由的核心。同时该算法在数据传输阶段使用网络编码技术实现数据的可靠传输。仿真结果表明，该路由协议适用于事件驱动型的大规模无线传感网。

针对事件驱动型无线传感网的应用，在文献［13］中作者提出一种基于簇的多路径数据收集协议MRP，该算法结合了层次路由协议和多路径路由协议的各自优点。在该协议簇的形成阶段中，由位于事件区域的节点动态成簇来提高数据融合的效率，因此降低了节点的能耗，在多路径建立阶段，通过蚁群算法实现从簇首节点到汇聚节点的多路径路由，在数据传输阶段通过人工蚂蚁的返回信息动态地选择一条路径传输数据，达到了负载平衡和节能要求。此外，MRP协议还可根据监测精度要求进行簇内调度，通过控制活动节点数进一步降低能耗。仿真结果表明，通过数据融合后，MRP协议能有效地降低节点的能耗，具有较长的网络生存期，适用于大规模的事件驱动型无线传感网。

上述介绍的一些分簇多路径路由协议。有些协议分簇时候没有考虑到事件区域，这样会造成簇头节点数据的不相关性增大，不能很好的进行数据融合，也不能有效减少到达目的节点的数据量。有些协议，多路径上没有考虑能量因素，不能做到整个网络的能量负载均衡。有些协议，只是单个的数据采集方法，不能进行查询。基于蚁群算法的路由协议适合设计能量负载均衡的多路径路由协议［14－15］。在综合考虑以上这些因素，结合分簇和蚁群算法，提出提出一种适用于事件驱动和查询的混合数据采集方法的CAEMP协议

2 CAEMP协议

CAEMP协议对于事件区域附近的节点，由于感知信息的高度相似性，通过成簇的方法来减少发送的数据。对于汇聚节点，如果需要事件区域的数据，可以采用发送搜索蚂蚁到事件区域的方法来获取所需要的数据，同时在链路上释放搜索信息素。事件区域形成的簇，簇头可以通过发送前向蚂蚁的方法来寻找到汇聚节点的多路径，搜索蚂蚁留下的信息素可以加快前向蚂蚁到达汇聚节点的速度。

2.1 系统模型

CAEM协议采用了动态分簇方式。对于事件区域的传感器节点，为了更好的节省能量，假设事件区域的每个节点装有低功率射频唤醒设备［16］。射频唤醒电路所消耗的能量如下所示:

式(1)中k是唤醒报文的大小，以比特为单位，Eradio代表射频唤醒电路消耗的能量，Eamp表示在射频唤醒设备上放大每比特所消耗的能量。

根据文献［17］，对于空闲侦听时所消耗的能量也不能忽略，具体定义如下:

Eelec代表接收电路的能耗;α是调整因子，α值比1小，但比较接近于1。

2.2 簇头的选择

无线传感器节点能量的主要消耗在于通信模块，并且节点空闲监听时所消耗的能量与接收信息时所消耗的能量差不多，比节点发送数据时所消耗的能量稍微少点。为了尽可能节约空闲监听时的能量消耗，CAEMP协议的基本能量管理机制采用的是射频唤醒技术［17－18］。事件区域的传感节点在没有事件发生的时候处于睡眠状态，当有事件发生的时候，节点就会转到激活工作状态。

CAEMP协议包括两个阶段:簇的形成和多路径的建立。在簇的形成阶段解决的最主要问题是簇头的产生。如果事件区域有事件发生或者事件区域有搜索蚂蚁到达，那感知到事件或收到搜索蚂蚁的节点都会被激活，处于工作初始状态。处于工作初始状态的节点，首先会给邻居节点发送HELLO报文，获取邻居节点也就是节点周围的信息。当过了一定的时间，事件区域感知到事件的节点都获知了周围的信息，这时候节点就要相互竞争成为簇头。有资格竞选簇头的节点，在竞争开始阶段，都处于候选簇头状态。在这个竞争簇头的时间内，侯选簇头们采用的是文献［19］提出的“先发布者胜”的机制。每个节点都延迟等待一段时间，哪个节点的延迟等待时间短，就先发送簇头广播通告，成为簇头。另外还处于候选监听状态的节点，就取消延迟等待，并申请成为一个簇内成员节点。在簇头选择阶段，如何计算簇头竞选等待时间Twait就变得非常重要。为了优化簇头结构，减少能量消耗，所以计算等待时间Twait时需要考虑以下几个因素［20］:

(1)由于簇头节点不仅要接受簇内节点的数据，同时还需要转发给Sink节点，簇头节点的能量消耗是最大的。所以在计算等待时间Twait的时候，一定要考虑节点的剩余能量，节点的剩余能量越多，当选簇头的概率就越大，即Twait越小，节点也越早广播簇头通告。

(2)为了解决簇内节点能量非均匀分布的问题，文献［21］表明考虑邻居节点的平均能量，能更好的平衡能量负载。在计算等待时间Twait的时候，优先考虑邻居节点平均能量小的那些节点成为簇头。

(3)在选择簇头时，为了节省簇内的通信代价，使得簇头节点尽量处于相对中间的位置［2］。所以在计算等待时间Twait的时候，还需要考虑的两个参数是节点的邻居数量和通信代价，节点邻居数量越多，通信开销越少，节点就更有机会当选为簇头。

(4)当簇头节点会于事件区域中心的时候，采集数据所消耗的能量是最小的。所以，计算等待时间Twait的时候，也要考虑节点感知到的事件的信号强度，信号越强，当选簇头的机会就越大。

简言之，要使乡村从原来被动接受的从属地位中摆脱出来，伴随两个平等主体在异质中发挥各自优势，城乡融合的体制机制加快形成，两者的互补和互需将不断增强，最终形成命运共同体。

综合上述考虑，得出Twait的计算公式为:

其中α和β是时间系数，其值在0到1之间，α+β=1，本文后面的实验，这两个系数的值都为0.5。T1的计算公式如下所示:

其中，Ei是当前节点i的剩余能量，Ni是节点i的邻居节点的数量，Si是节点i接受到的事件信号强度，k1、k2、k3分别是控制 Ei，Ni和 Si的权衡参数，本文后面的实验，这几个系数的值都为1。Ei_avg是节点i的邻居节点的平均剩余能量，计算公式如下所示:

其中，Ej是节点i的邻居节点j的剩余能量。

选择簇头的时候，簇内通信代价也是决定节点是否成为簇首的一个重要标准，成簇后，簇内通信开销少，节点能量消耗少，网络的寿命就更长。簇内通信代价可以表示为一个节点与其邻节点之间的平均距离的平方，这个距离平方实际上与邻居节点通信时消耗的能量成正比［21］。作为一个候选簇头，能耗是一个关键因素。如果与邻节点的平均距离短，候选簇头将花费较少能量与之通信，这样就使候选簇头拥有较大的概率成为簇头。T2是簇内通信开销的参数，它的计算公式如下所示:

其中，Dij是节点j与节点i的距离，从式(6)可以看出，Dij越大，T2的值就越大;相反，Dij越小，T2的值就越小，节点就越有机会成为簇头。这样就可以减少簇内通信代价。通过上述计算得出的Twait值最小的节点当选为簇头。

成簇算法具体描述如下:

第1步 如果检测到有事件发生，节点就要被激活，进入工作初始状态。节点开始进入了簇头选择过程的准备工作。节点在初始状态，主要是发送HELLO报文给邻居，用以确认感知事件的邻居的数量和邻居节点的能量，当获取到周围节点的信息后，节点开始计算簇头竞争等待时间。

第2步 节点在初始状态后，如果节点剩余能量满足要求，即节点的剩余能量大于邻居节点的平均能量的一半，节点才有资格成为簇头，节点就进入候选簇头监听状态。节点在候选簇头监听状态的时间最大值为簇头竞争时间。在这个时间内，侯选簇头们采用的是“先发布者胜”的机制，节点一直处于监听状态，看看有没有收到别的节点发送过来的簇头广播通告，如果在等待时间内，节点收到簇头广播通告，节点就进入普通状态。如果等待时间结束，节点还没有收到任何簇头广播通告，节点就发送簇头广播通告，节点自己就进入簇头状态。

第3步 节点如果是处于普通状态，就要发送加入簇的请求报文给簇头。簇头收到全部加入请求报文后，根据簇的情况，部分或全部接受普通节点为簇内成员节点，并分配相应的时隙。

第4步 簇内节点在自己分配的时隙发送信息给簇头。如果普通节点没有成为簇内成员节点，节点不用发送数据，节点就进入睡眠状态。

第5步 簇头根据加入请求报文里的簇头竞争时间，选择其中最大的作为备份簇头。

第6步 为了均衡事件区域节点的剩余能量。簇头在进行数据收发的时候，需要定期监测自己的剩余能量，如果簇头节点发现成簇后已经消耗了一半的剩余能量，簇头就要准备进行切换，备份簇头成为簇头，同时减少重新成簇的开销。

2.3 簇的形成

簇头选举完成后，事件区域内收到簇头广播通告的节点就要发送加入请求报文。在簇内部，由于节点距离都比较近，如果不采取一定的机制，簇内成员节点同时给簇头发送数据，会容易造成冲突，所以簇内通信采用TDMA［22］机制。簇头给簇内成员节点分配时隙，簇内成员就可以开始在分配的时隙给簇头发送数据。簇头接收完簇内成员节点的数据后，对数据进行融合，然后发送给SINK节点。本文不考虑簇头具体的融合过程，由于事件区域的数据都比较接近，CAEMP协议认为簇头数据的融合是100%融合。考虑到上面这个数据发送和融合过程，如果簇内节点比较多，簇内的通信开销和簇头发送数据给SINK节点也会比较延后。如果是在应用比较紧急的场合，需要事件区域及时把信息数据传递给SINK节点。事件区域的传感器节点分布密集，事件信息又有高度的重合性，所以簇头在选取簇内节点的时候，可以不超过一定的数量，本文选择的数量是事件区域中原始节点数的一半节点。簇头节点在收到加入请求报文后，选取Twait最小的几个节点作为簇内成员节点，然后给它们分配时隙，没有成为簇内节点的普通节点，就可以进入睡眠状态，节省能量。控制事件区域簇的规模，可以减少事件区域节点的能量开销和数据发送的延迟。

簇头的能量消耗比较大，如果事件区域的数据量比较大，为了避免簇头的频繁选举，簇头根据加入请求报文里的簇头竞选等待时间，选择其中时间最小的作为备份簇头。当簇头节点能量消耗到一定的程度，簇头可以发消息给备份簇头，备份簇头成为簇头，继续按照簇头分配的时隙进行数据的传递。同时，新当选的簇头，则可以根据Twait选取其中对应的节点成为备份簇头。

2.4 多路径的形成

当簇头收集到簇内的数据，进行数据融合后，就需要给SINK节点发送数据。当簇头需要向目的节点发送数据时，需要查看路由信息，如果这个时候没有到达目的节点的路由，就需要开始发送前向蚂蚁，需要发送的数据进行缓存。如果有到达目的节点的路由，就可以直接进行数据发送。

CAEMP协议采集数据的方式是事件驱动和查询的混合数据采集方法。所以，当SINK节点需要数据的时候，也会对事件区域发送搜索蚂蚁，同时在链路上释放搜索信息素，搜索信息素可以加快前向蚂蚁到达汇聚节点的速度。式(7)显示了路由表中搜索蚂蚁信息素更新的方式:

式中Ni是当前节点i搜索信息素链路上的邻居集合。

从簇头出发的前向蚂蚁，如果没有发现搜索信息素，就要按照广播的方法来搜索到目的节点的多路径。

如果簇头发现链路上有搜索信息素，就需要往搜索信息素的链路上分别发送同类的前向蚂蚁。节点如果收到的是不同类的蚂蚁，节点可以直接按照搜索信息素概率公式(8)把前向蚂蚁转发出去。对于源节点的邻居节点，只接收从源节点直接发出的前向蚂蚁。为了减少网络中蚂蚁传播的开销，节点如果收到的是相同类型的前向蚂蚁，时延、跳数和能量可能比前面的蚂蚁包都要差，如果都被丢弃，中间节点到目的节点就只能形成单路径，不能发挥蚁群算法的优势。下面是同类的蚂蚁的多路径判断规则，形成源节点到目的节点的多路径:

第1步 如果新收到的前向蚂蚁的入链路和节点中保存的不一样，只要新收到的蚂蚁的时延和跳数在可接受的范围内，就接收新来的前向蚂蚁，这个范围可以是个参数λ，可以根据不同的网络环境来进行调整，本文规定跳数的λ为1.5，时间的参数λ为2.5。

第2步 如果新收到的前向蚂蚁的入链路一样，就要判断两个蚂蚁的第一跳是否一样，这个第一跳也就是离开源节点后的第一节点。如果第一个节点不一样，只要新收到的蚂蚁的时延和跳数在可接受的范围内，就接收新的前向蚂蚁，这个范围可以是个参数λ，可以根据不同的网络环境来进行调整，本文规定跳数的λ为1.5，时间的参数λ为2.5。

第3步 如果新收到的前向蚂蚁的入链路与第一跳和节点中保存的一样，只有新来前向蚂蚁的跳数小于等于原来前向蚂蚁的跳数，才接收新来的蚂蚁。

前向蚂蚁来到一个节点，如果有同类蚂蚁已经来过，就要根据上面的多路径判断原则进行判断。如果符合要求，就可以转发给下一跳，在选下一跳选择的时候，为了搜索更多路径，可以依次在余下还没有转发给前向蚂蚁的链路上进行搜索信息素概率公式选择发送。

通过上述方法，可以使得蚂蚁探索路径时获得多条路径，在数据发送的时候，如果一个链路出现故障，可以通过另外的链路发送出去，提高投递率。同时，多路径有助于网络的能量和负载均衡。

符合时延要求的前向蚂蚁到达目的SINK节点后，就转变成对应的后向蚂蚁，从SINK节点原路返回。当后向蚂蚁从一个编号为j的节点移动到编号为i的节点时，需要对节点i进行路由信息素更新，节点i更新或建立目的节点为d的路由信息，这个路由信息的下一跳就是j，具体公式如下:

式中，H是当前节点i到达目的节点d的跳数。Ts－i是源节点到当前节点的时延，Eavg是从源节点s到目的节点已经消耗的平均能量，由目的节点根据跳数和消耗的总能量进行计算，后向蚂蚁在返回的路径上携带这个值。Min值是后向蚂蚁所经过的所有节点中，剩余能量最小节点的能量值。k1，k2，k3和k4是以上4个参数的系数，在各个不同的网络环境，通过调节各个系数，来适应网络的环境，本文后面的实验，这几个系数的值都为1。

2.5 数据发送

通过蚂蚁的发送，在各个节点建立了路由信息，一旦有后向蚂蚁返回，簇头中融合后保存在缓冲区里的数据就可以通过蚂蚁建立起来的路由信息发送出去。数据发送是以概率发送的方法进行，所有的节点收到需要转发的数据包后，按照式(10)进行选择发送:

式中，β1是一个参数因子，可以调节链路信息素对数据转发的影响，β1值越大，信息素值越大的链路，被选中转发的数据的概率就越大，也就是“好的链路“使用频率会更高，可以根据具体的使用环境进行调整。本文中β1是一个大于等于1的值。发送数据多的链路，可能会比较拥挤，发送时间变长，能量消耗也会比较多，链路上节点的剩余能量减少，通过信息素的自动更新，数据会自动往剩余能量多和数据少的路径上发送，最后做到整个网络的负载均衡。

信息素的挥发是周期性进行的。对于给定的τ的时间周期，节点将进行一次信息素的挥发，信息素挥发包括路由信息素和搜索信息素，具体如下:

式(11)和式(12)中，ρ的范围是0到0.05之间，本文后面仿真设置为0.05。

2.6 路由维护和链路故障

簇头在数据发送的时候，需要进行路由维护，一般发送N个数据报后或者定时发送一个前向蚂蚁。协议采用定时发送前向蚂蚁的方式，当节点开始发送数据后，定时产生一个前向蚂蚁。但是否发送这个前向蚂蚁，可以根据路由表中各个链路上的剩余的路由信息素大小和蚂蚁访问列表的长度来决定，如果各个链路上最大的剩余路由信息素已经小于某个门限值，且蚂蚁访问列表的长度小于一个上限值，就可以发送前向蚂蚁。同样的，源节点收到一个后向蚂蚁，也可以根据上述的方法来决定是否发送前向蚂蚁。

路由维护时候，前向蚂蚁的发送有单播和广播两种方式，发送单个前向蚂蚁的时候，这时候链路上已经有了搜索信息素和路由信息素，前向蚂蚁就通过概率选择的方法进行发送，概率选择公式需要同时考虑搜索信息素和路由信息素，具体公式如下:

式中的α2和β2是两个参数，主要调节搜索信息素和路由信息素对前向蚂蚁的引导作用，这儿设置α2为2，β2为1，主要是让搜索信息在引导前向蚂蚁的时候起更多的作用。如果链路上只有搜索信息素或者路由信息素，另外的信息素值就作1处理。

2.7 算法描述

协议算法描述具体如下:

第1步 如果事件区域感知到事件或者有搜索蚂蚁到达，事件区域的节点就要按照相应的算法，选择簇头，形成一个事件区域的分簇;

第2步 SINK节点如果需要查询数据，就往事件区域发送搜索蚂蚁，同时在链路上释放搜索信息素。

第3步 事件区域的簇头，收到簇内成员节点的数据，经过数据融合，需要给源节点发送数据。如果没有路由信息素，需要发送前向蚂蚁，建立到目的SINK节点的多路径路由;

第4步 前向蚂蚁根据多路径判断规则来到目的节点，目的节点把符合时延的前向蚂蚁转变成对应的后向蚂蚁，按路径返回。

第5步 后向蚂蚁在链路上释放路由信息素，删除对应蚂蚁访问列表中保存的蚂蚁。

第6步 当事件区域的簇头节点收到第一个后向蚂蚁，建立到目的节点的路由信息表，删除蚂蚁访问列表中保存的蚂蚁，同时把缓存中的数据发送出去。

第7步 如果簇头的能量小于某个阀值，就通知备份簇头，进行簇头的切换。

3 仿真与分析

3.1 协议添加

本文实验仿真环境是 CentOS+NS2.34，由于NS2.34里面没有CAEMP协议，需要把我们编写好的CAEMP协议源代码添加到NS－2中，添加成功后就可以和另外协议进行仿真对比分析。

在NS－2中，每个新添加的路由协议要有自己的报文格式，新的路由协议要有自己的路由代理，这样才能把新协议的代码添加到NS－2里，添加的过程就是把源代码放入NS－2，然后进行重新编译，编译成功后协议就算添加好了，就可以在OTCL中使用这个协议进行仿真比较了。

3.2 仿真场景与参数设置

在 NS－2 仿真环境中对 CAEMP、CBMRP［9］和AOMDV做仿真比较，本文使用First-order Model能量传输模型，设置 Eelec为 50 nJ/bit，Eamp为 10 pJ/(bit·m2)，数据融合参数 EDA 为5 nJ/bit。节点初始能量为10 J，节点通信半径为90 m，基站的能量单独设为100 J，仿真的时间为120 s。数据流使用CBR流，数据包大小为512 byte，每个节点发送数据包的速度是4 packet/s，使用cbrgen工具生成数据流文件，控制消息的大小是20 byte。仿真场景大小是400 m×500 m，总共节点数量是72个，节点基本静止不动，Sink节点位于网络的右边位置。场景中有4个事件区域，每个事件区域周围的节点数量大致是9个左右，簇头给每个簇内节点分配的时隙是1 s，假设事件区域每隔12 s有事件发生，也就是说，对于CAEMP协议，事件区域每隔12 s就要形成一次簇，传感器节点的参数设置如表1所示。

表1 传感器无线节点的参数

3.3 性能分析

本文提出了基于分簇的能量有效的多路径路由协议，所以仿真实验着重从能量有效性和网络生存时间这两个方面来对几种协议进行性能分析比较。如果分簇设计合理，多路径网络流量负载均衡，则网络具有更好的能量有效性，网络生存时间就长。

本文中，能量有效性定义为从开始到模拟完成之后这段时间里Sink节点接收到的数据包总数与能量消耗总量的比值。能量有效性是评价协议能量性能的重要指标之一，网络在消耗相同能量的情况下，如果Sink节点收到的有效数据越多，说明在传送一定数据量的情况下，网络的生存时间越长。图1是3种协议的能量有效性对比图，从图中我们可以发现AOMDV协议的能量有效性最差，主要由于AOMDV协议数据采集的时候没有进行分簇处理，事件区域的每个节点感知到事件后，都会把收集到的数据直接发送给Sink节点，这样会导致以下两种情况的发生，一方面网络中同时需要传送大量的数据，会导致数据发送冲突或拥塞;另一方面，事件区域和Sink节点之间的节点的传送任务会很大，会导致这部分节点消耗过多的能量，减少存活时间。分簇多路径协议CAEMP和CBMRP的能量有效性都比AOMDV要高，主要是这个两个协议采用了分簇的方法，可以把事件区域的数据先发送到簇头，簇头经过数据融合，再把数据发送给Sink节点，这样大大减少了事件区域和Sink节点之间传送的数据量，节省了这部分节点的能量，也就提高了能量有效性。

图1 3种协议的能量有效性对比图

从图1中也可以发现，CAEMP的能量有效比CBMRP提高了将近20%，这主要是CAEMP对分簇进行了优化，整个簇以事件信息为中心，同时考虑到感知信息的高度相似性，控制了事件区域簇的规模和制定了备份簇头的机制，这样可以减少事件区域节点的通信能量开销，节省能量;另外CAEMP协议从簇头到Sink节点之间采用了蚁群多路径路由协议，可以形成可以形成更多有效的多路径，簇头可以把数据流量注入更多的路径，使得数据均衡发布，最后导致自动的网络能量负载均衡，提高了网络的能量有效性。随着时间的推移，3种协议的能量有效性都有下降的趋势，其中两种分簇协议表现得比较明显，这是因为随着时间的推移，网络中节点的能量也慢慢减少，部分节点可能提前死亡，也会导致能量有效性降低。

网络生存时间可以有多个标准来定义，它可以定义为网络中第一个节点死亡的时间，第一节点死亡时间越早，代表网络寿命越短;也可以定义为网络中生存节点个数，生存节点个数越多，网络寿命越长。图2表示了网络中第一个节点的死亡时间和随着时间的变化网络中节点的存活数，从图中可以看到，对于AOMDV协议，大约在不到100 s的时候，就有节点开始死亡，到120 s的时候，网络中绝大部分节点都已经死亡，这个主要和AOMDV协议不分簇，传送的数据量大，导致网络中的节点提早开始死亡。运行CBMRP协议的网络节点开始死亡的时间大约比AOMDV协议推迟了大约10多秒，这主要由于CBMRP协议的分簇机制，但CBMRP协议的分簇机制对于事件区域效率不高，所以大约在130多秒的时候，网络中只留下了为数不多的节点。3个协议中，运行CAEMP协议的网络节点开始死亡的时间最迟，大约在140多秒的时候，网络中才有节点开始死亡，这和CAEMP协议基于事件区域的优化分簇和基于蚁群算法的多路径协议有关，一方面减少了网络的负担，另一方面达到了网络能量负载均衡。和AOMDV协议相比较，CAEMP协议的网络寿命延长了将近50%。从图2中也可以发现，当开始有节点死亡后，3种协议网络中节点死亡的速度都比较快，这可能由于余下的节点需要承担更多的数据发送和转发任务，加剧了它们的死亡速度。

图2 网络中节点存活数与时间的关系

4 结束语

本文基于事件驱动和查询的混合数据采集方法，提出了一种基于分簇和蚁群算法的能量有效的多路径路由协议CAEMP。考虑到事件区域附近高度分布的节点，由于感知信息的高度相似性，通过把它们成簇的方法来减少发送的数据量。事件区域的传感器节点分布密集，事件信息又有高度的重合性，所以簇头在选取簇内节点的时候，可以不用超过一定的数量。控制事件区域簇的规模，可以减少事件区域节点的通信能量开销和簇头数据发送的延迟。事件区域的簇头的能量消耗比较大，为了避免簇头的频繁选举，簇头根据加入请求报文里的簇头竞争时间，制定了备份簇头的机制。

对于汇聚节点，如果需要事件区域的数据，可以采用发送搜索蚂蚁到事件区域的方法来获取所需要的数据，同时在链路上释放搜索信息素。事件区域形成的簇，簇头可以通过发送前向蚂蚁的方法来寻找到汇聚节点的多路径，搜索蚂蚁留下的信息素可以加快前向蚂蚁到达汇聚节点的速度。最后，簇头融合后的事件区域的数据就可以在蚂蚁包形成的多路径上进行数据包的发送。仿真结果表明，和传统的多路径协议和分簇多路径协议比较，协议在延长网络寿命方面和能量有效性方面，都有了一定幅度的提高。

［1］ Rahman K C.A Survey on Sensor Network［J］.Journal of Computer and Information，2010，1(1):76－87.

［2］ 杨婧.无线传感器网络中高能效数据收集协议的研究［D］.江南大学，2010.

［3］ Dorigo M，Birattari M，Stutzle T.Ant Colony Optimization:Artificial Ants as a Computational Intelligence Technique［J］.IEEE Computational Intelligence Magazine，2006，1(40):28－39.

［4］ Chen Ge，Guo Tiande，Yang Wenguo，et al.An Improved Ant-Based Routing Protocol in Wireless Sensor Networks［C］//2006 International Conference on Collaborative Computing:Networking，Applications and Worksharing，Atlanta，USA:IEEE，2006，1－7.

［5］ 鲍荣，潘浩，董齐芬，等.基于信息素扩散模型蚁群算法的无线传感网路由研究［J］.传感技术学报，2011，24(11):1644－1648.

［6］ Amis A D，Prakash R，Vuong T H P，et al.Max-Min D-Cluster Formation in Wireless Ad Hoc Networks［C］//Proceedings of Infocom，2000.

［7］ Heinzelman W B，ChandrakasanA P，BalakrishnanH.An Application-Specific Protocol Architecture for Wireless Microsensor Networks［J］.IEEE Transactions on Wireless Communications，2002，1(4):660－670.

［8］ Bandyopadhyay S，Coyle E J.An Energy Efficient Hierarchical ClusteringAlgorithm forWirelessSensorNetworks［C］//Proceedings of IEEE Infocom，2003.

［9］ Wang Y，Tsai C，Mao H.HMRP:Hierarchy-Based Multipath Routing Protocol for Wirelesss Sensor Networks［J］.Tamkang Jounal of Science Engineering，2006，9(3):255－264.

［10］安辉耀，卢锡城，彭伟.移动自组网中一种基于簇的多路径路由算法［J］.软件学报，2007，18(4):987－995.

［11］于继明，卢先领，杨余旺，等.能量优先分级变化的多路径路由选择算法［J］.计算机科学，2007，34(8):45－48.

［12］高腾.能量高效的无线传感器网络分簇路由协议研究［D］.大连理工大学，2011.

［13］ Yang Jing，Xu Mai，Zhao Wei，et al.A Multipath Routing Protocol Based on Clustering and Ant Colony Optimization for Wireless Sensor Networks［J］.Sensors，2010(10):4521－4540.

［14］童孟军，俞立，郑立静.基于蚁群算法的无线传感器网络能量有效路由算法研究［J］.传感技术学报，2011，24(11):1632－1638.

［15］ Sudip Misra，Sanjay K Dhurandher，Mohammad S Obaidat，et al.An AntSwarm-Inspired Energy-Aware RoutingProtocolfor Wireless Ad-Hoc Networks［J］.The Journal of Systems and Software，2010，83(11):2188－2199.

［16］ Le-Huy P，Roy S.Low-Power 2.4 GHz Wake-Up Radio for Wireless SensorNetworks［C］//Proceedings—4th IEEE International Conference on Wireless and Mobile Computing，Networking and Communication，WiMob 2008，Avignon，France，2008:13－18.

［17］ Schurgers C，Tasiatsis V，Ganeriwal S，et al.Optimizing Sensor Networks in the Energy-Latency-Densitydesign Space［J］.IEEE Transactions on Mobile Computing，2002，1(1):70－80.

［18］ Gu L，Stankovic J A.Radio-Triggered Wake-Up for Wireless Sensor Networks［J］.Real-Time Systems，2005，29(2－3):157－182.

［19］ Kwon T J，Gerla M.Efficient Flooding with Passive Clustering(PC)in Ad Hoc Networks［J］.ACM Sigcomm Computer Communication Review，2002，32(1):44－56.

［20］郑立静.基于非均匀分簇路由算法的研究［D］.杭州电子科技大学，2013.

［21］ Liu Ming，Cao Jiannong，Chen Guihai，et al.An Energy-Aware Routing Protocol in Wireless Sensor Networks［J］.Sensors，2009，9:445－462.

［22］ Al-Karaki J N，Kamal A E.Routing Techniques in Wireless Sensor Networks:A Survey［J］.IEEE Wireless Communications，2004，11(6):6－28.