基于汇聚环的网内事件路由策略

贺晟，黄冠银，朱石明，刘安丰, 2



基于汇聚环的网内事件路由策略

贺晟1，黄冠银1，朱石明1，刘安丰1, 2

(1. 中南大学 软件学院，湖南 长沙，410083；2. 中南大学 信息科学与工程学院，湖南 长沙，410083)

对事件数据融合策略进行改进，提出一种新的基于汇集环的数据融合路由策略，论述策略的各个方面，包括路由的形成、汇集环停留的时间比例等，并对策略性能进行分析，最后通过实验予以验证。研究结果表明：在网络的非hotspots建立环绕网络的汇集环，除第1环数据直接发往Sink外，其他环的数据由汇集环融合后再发往Sink，极大地减少了需要发往Sink的数据量，成倍地提高了网络寿命，验证了该策略的有效性。

无线传感器网络；数据融合；汇集环；网络寿命

无线传感器网络的节点是由电池供电，其能量非常有限，而且不能被替换与更新，因而传感器节点的能量一旦消耗殆尽，传感器节点便完全失去功能而死亡，因而，如何在有效监测事件的基础上节省网络的能量，提高网络寿命是一个重要的研究课题。大量研究表明[1−6]：事件信息在时间上与空间上都存在相关性，因而可以通过数据融合(data aggregation)技术将多个事件的信息融合成数据量少得多的数据包，然后发往Sink，从而极大地减少了网络所需要传送的数据量，提高了网络寿命[7−9]。Villas等[5]提出了一种较好的事件信息融合策略。该策略的主要思想是：若将多个不同区域发生的事件信息汇合在1条路由路径发往Sink，则这些事件的数据包就可以在经过同一节点时进行数据融合，从而可以进一步减少数据发送量，进一步提高网络寿命。但是，这种策略还存在一个很大不足，即这种策略只是一种能够在局部将多个事件的信息融合在一起，而没有全局网络事件信息融合的能力。若事件发生的区域相距较远，则这些事件信息依然独立地将没有进行数据融合的事件信息发往Sink，从而使这种策略的有效性大大降低。为此，本文作者提出一种能够进行全局事件信息融合的策略，称为基于汇集环的路由策略(aggregation ring based routing, ARR)。与以往的策略相比，该策略具有以下特点： 1) 策略具有全局事件信息融合的能力，因而能够极大地减少发送到Sink的数据量，极大地提高网络寿命；2) 具有很高的能量有效性；3) 提高了网络寿命达数倍，验证该策略的有效性。

1 系统模型与问题描述

1.1 网络模型

本文所采用的网络模型如下。

1)个同构节点随机地部署在1个二维平面网络内，节点密度为，每个节点持续监测周围的环境，一旦监测到感兴趣的事件，则将事件信息发往Sink。应用对事件的延迟不敏感。

2) 假设被监测的目标出现在网络中的位置是随机分布的，也就是每个传感器节点监测到目标的概率是均等的。

3) 数据融合模型。本文采用逐步多跳无损数据融合模型(lossless step-by-step multi-hop aggregation model)[10]。在该模型中，当2个数据包在1个节点上相遇时，就进行数据融合。用表示节点s的数据和节点s的数据进行数据融合(data aggregate)后的结果。数据融合公式如下：

1.2 能量消耗模型

本文只考虑数据通信的能量消耗[2−3, 9]。在发送数据时，若数据发送距离小于阈值0，则采用自由空间模型，否则，采用多路径衰减模型。发送和接收长度为的数据的能耗分别为

其中：为数据发送距离；elec为无线收发电路发送或接收单位长度数据的电路能耗；fs和mp分别为自由空间模型和多路径衰减模型的放大器能耗参数。

1.3 问题描述

本文的主要目标是针对无线传感器网络设计一种有效的事件信息融合路由策略，能够有效地将事件信息融合后发往Sink，并使得网络寿命最大化。与文献[1, 4−5]中的定义一样，网络寿命定义为网络中第1个节点死亡的时间。设E为节点的能量消耗，则使得网络寿命最大化可以表达为

2 基于汇集环的网内事件聚合策略

2.1 ARR策略总体概略

本文提出的基于汇集环的路由策略(aggregation ring based routing, ARR)是对DRINA策略的改进。DRINA策略是由Villas等[5]提出的一种较好的事件数据聚集路由策略。策略主要首先执行跳数扩散协议从而使每个节点得到到达Sink的跳数，如图1所示。

图1 DRINA 策略

DRINA策略的创新点主要体现在事件发生后的路由过程，如图1所示。当事件1(event 1)发生后，事件信息沿最短路由路径向Sink发送，但与以往研究不同的是：DRINA策略将事件信息发送到Sink这条路由上的所有节点到达Sink的跳数都设置为0跳，然后，此路由上的节点进行类似于前面所述的跳数扩散协议。这样，一旦有1条到达Sink的路由，此路由上节点到达Sink的跳数由于被设置为0跳，其附近节点到达Sink的路由就会更改为向此路由，受此路由影响范围内的事件就会经过此路由向Sink发送事件信息，此路由影响范围内多个事件的信息就能够进行数据融合，从而减少发送到Sink的数据量，提高网络寿命。但是DRINA只能从局部进行优化。如图1所示，由于事件3与事件1和2发生的位置相距较远，因而，依据DRINA的路由策略，事件3的信息将产生独立的路由路径，独立地将自己的事件信息发往Sink，而不能进行数据融合。可见DRINA是一种具有局部视野的优化策略，能够对距离相近的事件信息进行信息融合，不能对整个网络的数据进行整体数据融合。针对DRINA策略存在的不足，本文提出一种基于汇集环的路由策略(aggregation ring based routing, ARR)，如图2所示。ARR策略的主要特征是在网络能量有较多剩余的区域建立围绕Sink的汇集环。事件发生后，汇集环外的所有事件信息都会经过环，汇集环内(指距离Sink的跳数小于或者等于环上节点到达Sink节点跳数的区域)依据自己距离环的位置决定是否向环发送信息还是直接向Sink发送信息。因为距离Sink 1跳范围内节点的能量消耗最高，是整个系统的瓶颈，因而，在ARR策略中，若事件发生在距离Sink 1跳范围内，则事件信息直接向Sink发送，否则，都向汇集环发送。向汇集环发送虽然增加了系统的总能量消耗，但还是能够减少hotspots区域的能量消耗，这对整个网络寿命的提高是有利的。

图2 ARR策略

当网络中的事件信息发送到汇集环后，事件信息围绕汇集环路由1周，这样将整个网络的所有事件信息都能够进行融合，大大减少了需要发送到Sink的数据量。可见，ARR策略是一种具有全局视野的信息融合路由策略。

2.2 ARR策略详细设计

在ARR策略中，每个节点需要存储2个变量的值：一组值是到达 Sink的最小跳数(hop to sink, 简称HTS)；另一个值是到达汇集环的最小跳数(hop to ring, HTR)。当节点存储这2个值后，节点就能够有效地形成到达Sink或者汇集环的路由。总体来说，ARR策略由如下几个阶段组成：1) 每个节点距离Sink跳数的形成。每个节点到达Sink的跳数在此阶段获得，即确定每个节点的HTS[9]。2) 汇集环的创建。创建汇集环，在创建汇集环后，将汇集环上的节点到达汇集环的跳数设为0跳，然后向外广播从而使整个网络的节点获得到达汇集环的跳数即HTR。3) 事件簇的创建。事件发生后可能有多个节点感知到事件，因而一般采用簇的方式，由事件附近的感知事件的节点形成簇，由簇头节点融合簇内节点感知的事件信息。事件簇的形成与文献[9]中的类似。4) 事件信息的路由过程。簇头节点的事件信息路由到汇集环，传送到Sink的路由阶段。

2.2.1 阶段2:汇集环的创建

设汇集环创建的位置位于距离Sink为跳处，则创建汇集环的过程如下：由Sink节点发起，沿着最大跳数节点向外路由(即每次选择比自己HTS大的节点作为下一跳路由方法)，直到下一跳节点(如)的HTS为时，则以节点为起点开始创建汇集环。其过程是：依据左手(右手)规则选择自己左边(右边)且与自己HTS相同的节点作为路由的下一跳节点，下一跳节点同样依据左手(右手)规则选择自己左边(右边)且与自己的HTS相同的节点作为路由的下一跳节点。如此过程一直进行下去，直到当依据左手(右手)规则选择下一跳范围内可以选择到节点时，则选择节点为终点，这样，形成既以节点为起点，又以为终点的汇集环。具体算法如算法1所示。

算法1：汇集环创建算法

//指定在距离Sink跳数为处创建环

Stage I: route to ring

1: let nodeis sink,is HTS

3: select nodefrom neighbor node of

//选择比节点的跳数大1的邻居节点作为下一跳；

4: let=；

5: end while

Stage II: creating ring

6:=

7: nodeselect it’s the most faraway left neighboras next hop whose HTS is

8: while the select node is notDo

9: if nodeis node’s left neighbor then

10: the next hop is;

11: else

12: next hop is’s the most faraway left

neighborwhose HTS is；

13: let=；

14: end if

15: end while

2.2.2 阶段4:路由阶段

路由阶段由汇集环创建后，汇集环中的所有节点将自己到达汇集环的跳数(HTR)为0跳，然后，环上的每个节点将自己的HTR向外广播扩散，与得到HTS跳数的过程类似，通过HTR的扩散过程后每个节点都确定了自己的HTR。

当所有节点确定了自己的HTR与HTS后，事件数据发送的原则如下：1)近Sink 1跳范围内产生的事件数据直接发往Sink；2) 非Sink 1跳范围内的节点先依据HTR指示的信息发往汇集环，即每次选择比自己HTR少的节点作为下一跳，直到HTR为0时发送到环上。然后，在环上路由1周后，将汇集环上的所有数据融合后再发往Sink。而发往Sink时路由的依据是依据HTS，即每次选择比自己少的HTS路由到Sink。

采用这种策略的原因是：1) 由于近Sink 1跳范围内是hotspots区域，因此，环一定不在1跳范围内，因为在1跳范围内会加重hotspots的负载。而1跳节点内的信息可直接发往Sink，比经过环转发更节省能量，因而，Sink 1跳内节点的数据直接发往Sink。 2) 由于其能量有剩余，非hotspots区域节点的数据都发往环，在环上进行数据融合后再发往Sink的数据量，在hotspots区域内会少于不进行数据融合再发往Sink的数据量。簇头节点数据产生后的路由算法如下。

算法2：数据路由

Ⅰ: stage 1: route to ring

1: cluster headis the node which have data to send to sink, letis HTS,is HTR;

3: else

4: ifcan send the data to the ring then nodesend data to Sink;

5: else

6: nodeselect neighborwhose=.−1;

7: while the selected nodeis not in the Ring Do

8: send data to node;

9: select neighborwhose=.−1;

10: end while

Ⅱ: stage 2: ring circle route

11: random select nodeas initiate circle routing node

12: nodeselect left neighborof ring

13: while nodeis not

14:send data to;

15: ifalso has data

then aggregation all data into one data packet

16: let=

17: end while

Ⅲ: stage 2: routing to Sink

18: nodeselect neighborwhose

19: let nodesend data to, let=

20: while the nodeis not Sink Do

21: nodeselect neighborwhose

22: let nodesend data to, let=;

23: end while

2.3 策略的参数优化

前面给出了ARR策略的具体设计，但还有1个重要问题即ARR策略中汇集环(aggregation ring)的位置问题。汇集环的位置应该位于网络能量剩余的位置，以便充分利用网络的剩余能量，因此，确定汇集环的位置选择要先分析网络的能量消耗，然后才能确定汇集环在网络不同位置停留的时间比例关系。设网络半径为，网络以节点的发送半径划分为不同的环，Sink为0环，距离Sink 1跳范围内的节点为第1环，环的编号依次向外。第环的节点承担第环以及大于第环的数据。第环以及大于第环的节点个数为。第环的节点个数为

每个事件发生后，采用基于簇的方式收集事件信息，由簇头节点来处理。假设节点在1个事件周期内产生数据的可能性为，事件产生后，必有1个簇头节点收集事件的信息。由于簇头节点收集事件信息与事件发生的概率是相等的，因而，每个节点充当簇头节点的概率相同，在1个事件周期内产生数据的概率也为。事件产生后，经过簇头节点数据融合后的数据包长度为，因而可以认为：在1个事件周期内节点产生数据概率为，产生的数据包长度为。若汇集环位于第环，则网络中节点承担的数据量情况分析如下：网络中第1环节点只需要发送自己的数据直接到达Sink以及整个网络经过数据融合后的数据，其他环的节点将自己的数据发送到第环，节点所在的环号大于沿Sink方向路由的环号。若节点所在的环号小于，则沿背离Sink的方向路由。ARR数据路由如图3所示。

图3 ARR数据路由

第环为汇集环，汇集环的节点有2类：一类是环路由上的节点，如图3中汇集环内的白色节点所示，环路由上的节点形成1个首尾相连的圆形环路由，除了第1环的数据外，其他环的数据都向第环发送数据，汇集环内节点接受这些数据；另一类是汇集环内的非环路由上的节点(如图3中黑色节点所示)。黑色节点接收到的数据还需要向环路由上的节点转发。由于数据是向环路由的，因而，在到达汇集环前数据路由中相遇的概率非常小，而且为降低网络延迟，每个事件的数据产生后都立即向环路由，因而，在本文中不考虑到汇集环前的数据融合。下面对网络中节点承担的数据量进行分析，然后给出汇集环位置与停留时间的比例关系。

证明：如图1所示，由于每个节点产生的数据都需要发送到汇集环，因此，对于第环，它一定承担除第1环外其他区域的所有数据。这些区域的面积为

这些区域产生的数据量为

第环的面积为

第环共有节点个数为

从而可以得到第环的节点在一轮数据收集过程中承担的数据量为

依据定理1可以看出：若汇集环离Sink越近，则承担的数据量越多；反之，若汇集环离Sink越远，则承担的数据量越少。可见，当汇集环位于网络不同区域时，传感器网络的能量消耗是不均匀的，因而，需要仔细规划汇集环的位置，汇集环建立在网络不同的区域，使不同区域的节点充当汇集环，使得网络不同区域节点的能量消耗均衡，从而提高网络寿命。

第环发送的数据量为

综合以上可得证。

证明：首先，依据定理1中式(7)可知第环每个节点的接收到数据量为。第环每个节点都向环上的节点发送，因此，第环上的每个节点发送的第1部分数据量为。由第环的平均长度为，而节点的发送半径为，因而，环上的节点个数为

至此，网络的数据都路由与数据融合到汇集环上的节点上，每个节点上的平均数据包为。然后，环上节点的数据再沿环路由1周，在此过程中再进行数据融合。由于环上的节点个数为，每经过1个节点，就会进行1次数据融合，因而最终发往Sink的数据量为

证明：首先，第环的节点将自己的数据往环形路由上转发，这一步需要发送的数据量由定理3可知第环上的节点个数为，第环总共有节点个数为。每个节点有数据量为则发往环形路由的数据总量为，然后，环上的节点向前转发。环上每个节点的初始数据量为，第1个节点向前发送的数据量为。第2个节点向前发送的数据量为。依此下去，第环向前发送的数据量为，从而可以得到在沿环路由中的发送的总数据量为

可得对环来说每个节点平均承担的数据量为

证明：汇集环内数据有2部分：一是接收网络内其他节点路由来的数据。这部分数据由定理1计算得

往环形路由上节点的数据转发以及环形路由上节点沿环路由的数据转发，这部分转发的数据量为前面定理4计算得到的。这样，第环总的转发的数据量为。

证明：定理2证明了当汇集环位于第环时，网络的第环每个节点接收的向汇集环路由的数据量如式(13)所示。对于的节点，还需要承担经过汇集环进行数据融合后发往Sink的数据，而定理2证明网络中的数据经过汇集环进行数据融合后的数据量为(据式(16))。而第环共有节点个数，因而，每个节点承担这部分的数据量为。可以得到网络的第环每个节点平均发送的总数据量为

证明：定理2证明网络中的数据经过汇集环进行数据融合后的数据量为，即式(16)所示。而第1环共有节点个数，因而，每个节点承担这部分的数据量为。1环内节点数据产生率为，数据包的长度为，因此，对于第1环的节点来说，每个节点发往Sink的数据量为。得证。

推理1 在ARR策略中，网络中不同环的节点承担的总数据量为

3 实验及性能分析

采用OMNET++网络模拟器[11]，如不加特别，说明网络参数设置为：=500 m，=50 m，节点个数为800，=0.001，数据融合率=0.3，节点密度=0.002。其他实验参数如表2所示。

表2 实验参数

图4所示为网络不同规模下的网络寿命对比。从图4可以看出：在ARR策略下，由于充分利用了网络非hotspots区域的能量来创建汇集环，从而将网络上除第1环外的所有数据都进行数据融合后再发往Sink，这时发往Sink的数据量最小，因而，ARR策略的网络寿命远比DRINA策略的网络寿命高。而在本实验中，DRINA策略中有4~5条路由路径向Sink发送，相当于其数据融合率只有ARR策略的1/4~1/5，因而其网络寿命远比ARR策略的低。另外，网络规模越大，其网络寿命越低。