工程科学与技术   2017, Vol. 49 Issue (2): 177-185
多监控任务移动传感器网络高效数据路由协议
刘唐1, 彭舰2, 杨进2     
1. 四川师范大学 基础教学学院, 四川 成都 610068;
2. 四川大学 计算机学院, 四川 成都 610065
基金项目: 国家自然科学基金资助项目(61303204;U1333113)
摘要: 在多监控任务移动传感器网络中,不同的监控对象对数据传输实时性有着不同的要求。为满足监控数据不同的实时性要求,提出了既能满足软实时监控要求,也能满足硬实时监控要求的多级分层实时数据路由协议MRDR(layer-based multilevel real-time data routing protocol)。MRDR协议将分层机制引入移动传感器网络,将网络分成宽度相等的若干圆环。对具有实时性要求更低的普通事件消息,MRDR在消息失效前以尽量低的能耗将消息转发至sink节点。对于实时性要求更高的紧急事件消息,MRDR让消息以层间多跳方式实时传输到sink。同时,针对硬实时路由过程中的节点空洞问题,提出了消息回传机制,使得紧急事件消息能绕过节点空洞并最终传输至sink。最后,为降低网络中的消息冗余,设计了消息队列管理机制,给出了队列满时的消息丢弃原则。为评价算法性能,仿真实验对比了MRDR与其他3种算法在网络寿命、数据传输成功率与消息平均延迟方面的表现,结果验证了算法的有效性。在不同的网络环境下,MRDR算法能有效适应多监控任务移动传感器网络,满足具有不同实时性要求的不同消息的传输要求。
关键词: 移动传感器网络    多监控任务    实时    路由协议    分层机制    
Efficient Data Routing Protocol for Multi-monitoring-task Mobile Sensor Networks
LIU Tang1, PENG Jian2, YANG Jin2     
1. College of Fundamental Education, Sichuan Normal Univ., Chengdu 610068, China;
2. College of Computer Sci., Sichuan Univ., Chengdu 610068, China
Abstract: In multi-monitoring-task mobile sensor networks, different monitored objects have different requirements for real-time transmission.To satisfy those requirements, a multi-layered real-time data routing protocol (MRDR) was proposed to satisfy the requirements of both soft real-time and hard real-time monitoring.In MRDR, a layer mechanism was introduced into mobile sensor networks and the network was divided into layers with equal width.For ordinary event messages with higher delay tolerance, MRDR could enable messages to be forwarded to the sink at as low energy consumption as possible.For emergent event messages with lower delay tolerance, MRDR could send messages to the sink by multi-hop real-time transmission.At the same time, for the problem of energy holes in hard real-time routing, a backward mechanism was proposed to enable emergent event messages avoiding node holes and finally be transmitted to the sink.At last, to reduce message redundancy, message queue management was designed and the principle for discarding messages was presented when the queue was full.To evaluate the performance, simulation was carried out to compare MRDR and other three algorithms in terms of network lifetime, average delivery ratio and average delay.The result proved the efficiency of MRDR.In different network environments, MRDR could effectively be applied to multi-monitoring-task mobile sensor networks and satisfy different requirements of different real-time transmissions.
Key words: mobile sensor networks    multi-monitoring-task    real-time    routing protocol    layered mechanism    

近年来,移动传感器网络[1-3]被广泛应用于移动对象的数据收集,例如野生动物生活习性、空气质量监测、军事探测、灾害预警等。在移动传感器网络的实际应用中, 同一监测范围内常常有多种数据需要被收集。因此,网络中的移动节点会承担多种监控任务,从而构成多监控任务传感器网络MMTMSN (multi-monitoring-task mobile sensor networks)。很明显, 不同的监控对象对数据传输实时性有着不同的要求。不失一般性,监控对象的数据传输实时性可被分为两类:软实时与硬实时。

在软实时网络中,监控数据 (如野生动物生活习性、空气质量监测等普通事件) 允许在一定的延迟容忍时间内传输到sink[3, 5-13]。因此,这种网络也被称为延迟容忍网络。对于软实时数据传输,文献[10]提出了一个移动数据收集算法FPAD。该算法面向节点通信能力、移动速度、信息存储能力不同的异构移动传感器网络。将节点活动因素加入传输概率预测,文献[11]提出了一个基于节点活动的概率路由协议。文献[12]提出了一个支持间歇连接的数据传输策略,该策略中节点能延迟数据包的传输以等待更好的网络连接。文献[13]提出了一个减少可变邻居搜索的优化路由算法,算法能计算一个实时阈值以控制数据包的传输。上述的机会路由方式能让数据以“存储-携带-转发”的形式完成数据路由。但是携带数据的节点只有在遇到其他满足条件的节点时,才进行数据转发。机会路由通常有着较大的传输延迟,因此并不适用于实时性要求更高的数据传输。

在硬实时网络中,监控数据 (如军事探测, 灾害预警等紧急事件) 必须及时传输到sink,此时能耗代价成为了考虑的次要因素[2, 14-17]。因此,即使付出较大的能耗,也需要保证收集到的数据在失效前完成实时传输。针对硬实时网络中的数据传输,文献[14]提出了一个路由协议RACE,该协议考虑到QoS、移动性和高网络负载的要求,以实时的方式将数据传输至sink。文献[15]提出了一个基于树的实时路由协议。该协议将数据路由分为3个阶段:形成树、数据收集与传输与优化。文献[16]综合考虑信任、能量及有效性,提出了一个仿生信赖实时路由协议。文献[17]提出了一个增强实时的负载分发路由协议。该协议使用优化转发指标实现数据包的实时转发。然而在软实时网络中,以上这些算法不会考虑数据允许的延迟,依然用实时的方式完成传输,因此会带来很大的能耗代价。

目前,研究者多集中于研究软实时/硬实时数据传输中的一种,而很少有人关注同时监控普通事件与紧急事件的多监控任务传感器网络。针对此,本文提出了多级分层实时数据路由协议MRDR (multi-layered real-time data routing protocol)。主要贡献包括:

1) MRDR算法能依据消息的不同类型,采用不同的路由策略,以更恰当的方式把数据发送至sink。

2) 为有效管理移动传感器节点,以同时适应不同实时性的数据传输要求,本文在移动传感器网络中引入分层机制,使得不同类型的数据均能利用分层机制寻找下一跳路由。

3) 对软实时数据,MRDR协议能以尽量低的能量代价在数据失效前将数据传输至sink。对硬实时数据,MRDR能以多跳路由的形式完成数据的实时传输,并能利用消息回传机制让数据绕过“节点空洞”。

4) 仿真实验表明,MRDR算法能有效适应多监控任务移动传感器网络,满足具有不同实时性要求的不同消息的传输要求。

1 网络模型 1.1 网络模型

为满足移动传感器网络的现实应用需求,本文定义网络中不同的传感器节点监控不同的对象,不同的对象对应于有着不同实时性要求的监控事件。半径为R的圆形网络区域A内部署着N个移动传感器节点。该移动传感器网络性质如下:

1) 唯一的sink位于圆形网络中心O。以sink为圆心,网络被均分为宽度相等的k层圆环。

2) 网络中存在两种不同实时性要求的监控事件:1) 有较大延迟容忍度的普通事件;2) 有较小延迟容忍度的紧急事件。

3) 所有节点的运动规律符合Random Waypoint模型[17]。在该模型下,传感器节点在网络范围内随机产生起始点S和目的点D,节点以速度vS直线运动到D,节点在一个随机时间内静止在D,并完成一次运动过程。图 1给出了节点的运动过程。

图1 随机游走运动模型 Fig. 1 Random waypoint movement mode

4) sink采用基站形式部署,可不考虑能耗。sink能通过调整发送功率,对整个网络进行广播。对所有节点,sink位置已知。

5) 所有节点装配了具有定时功能的定时器。

1.2 能量模型

本文使用简单能耗模型[19]。在该模型下,传感器节点在d距离发送l比特数据所消耗的能量为:

$ {E_{{\rm{T}}x}}\left( {l, d} \right) = \left\{ \begin{array}{l} l{E_{{\rm{elec}}}} + l{\varepsilon _{{\rm{fs}}}}{d^2}, d\; < \;{d_0};\\ l{E_{{\rm{elec}}}} + l{\varepsilon _{{\rm{mp}}}}{d^4}, d \ge {d_0} \end{array} \right. $ (1)

传感器节点接收数据的能耗为:

$ {E_{{\rm{R}}x}}\left( l \right) = l{E_{{\rm{elec}}}} $ (2)
2 多级分层实时数据路由协议 2.1 分层机制

网络分层机制多用于传统的静态传感器网络。在移动传感器网络中引入分层机制的原因为:对保持随机运动状态的节点进行分层管理,使得所有节点知道自身当前所属网络层次,并能完成邻居节点管理。同时,分层机制要能同时适应不同的路由策略,以满足不同数据的不同实时性要求。

定义网络各层层高均为节点通信半径τ,任意节点i所属的网络层次为RIDi

节点能通过信号强度的衰减感知相互距离。因此,设定sink每间隔t时间以能量Esink_tran进行广播,本文中t时间取为圆环高度与节点运动速度之比。网络中各节点在接收到该广播的同时探测接收信号强度 (接收能量)。对任意节点i,通过信号发送强度Esink_send与接收强度Ei_rec之间的关系为[20],可得出该节点与sink的距离为:

$ {d_{{\rm{sink}}, i}} = \sqrt[\alpha]{{\frac{{K \times {E_{{\rm{sink\_tran}}}}}}{{{E_{i\_{\rm{rec}}}}}}}} $ (3)

其中,K为一个常量,α∈[1, 6]为环境参数,其取值范围为1~6。

因此,可知任意节点i所属网络层次为:

$ R_{ID}^i = \left\lfloor {\frac{{{d_{{\rm{sink}}, i}}}}{\tau }} \right\rfloor + 1 $ (4)
2.2 邻居节点管理

本节讨论如何对邻居节点进行管理。首先给出相关定义:

定义1(邻居节点)  对任意节点i,它的邻居节点为其通信范围内的所有Z′个节点。设Σ={Ψ|1≤zZ′}为Z′个邻居节点集合。

网络中所有节点的邻居表内存储的信息包括:节点所属层次、当前能量、与所有邻居节点的距离、以及消息发送距离。

定义2(消息发送距离)  在节点的一次运动过程中,只有节点运动到与sink距离最小时才进行消息发送。该最小距离为节点i当前的消息发送距离di_o

图 2所示,节点i的当前运动的起始点为S(x1, y1)、目的点为D(x2, y2)。消息发送距离di_o计算如下:

图2 距离计算示意图 Fig. 2 Sketch map of distance calculation

$ {d_{i\_o}} = \frac{{{x_1}{y_2}-{x_2}{y_1}}}{{{{({y_1}-{y_2})}^2} + {{({x_2}-{x_1})}^2}}} $ (5)

显然,di_o>τ时节点i携带的消息不能被i直接发送到sink。

由于网络内所有节点保持移动,若每个节点以较高频率进行邻居表的更新,则各节点会花销大量的能量进行频繁的数据交换。因此,设定当节点i有待发送数据时,才在通信范围内发送邻居管理请求。收到请求的所有节点,根据式 (3) 得出自身与节点i的相互距离后,向节点i发送包括自身网络分层、剩余能量、消息发送距离的请求回答。节点i收到回答后,完成邻居表的更新。

特别的是,如果节点i的待发送数据为紧急事件消息,可被选作下一跳路由的邻居节点包括两类:同层邻居节点、内层邻居节点。此时,节点i需通过邻居发现广播,获得它所有邻居节点的同层/内层邻居数量。

2.3 普通事件路由

给出基于概率的普通事件消息mnor的路由策略。对有较大的消息延迟容忍度普通事件消息,进行路由选择的时候,应更多的考虑转发消息对节点能耗的影响。基于此,首先给出相关定义。

定义3(节点传输概率Pi)  它表示节点i把消息直接发送到sink的可能性,满足0≤Pi≤1。

定义4(节点转发概率Fi_z)  它表示节点i将消息转发至它的邻居节点z的概率,同样满足0≤Fi_z≤1。

定义5(消息延迟容忍度Tm)  它表示消息距离失效的时间。即消息在Tm时间后,若还未被发送至sink,该消息将失效。

首先,对节点传输概率Pi进行计算。在两种情况下,Pi=0:1) 节点i的当前运动无法经过最内层圆环R1,即节点i的消息发送距离di_o>τ;2) 节点i的待发送消息将在它移动到消息发送点之前失效。令节点i从当前位置移动到消息发送点的距离为di_send,由图 2可知,${d_{i\_{\rm{send}}}} = \sqrt {{d_{{\rm{sink}}, i}}^2-{s_{i\_{\rm{sink}}}}^2} $,因此节点i移动到消息发送点的所需时间为ti=di_send/v

上述两种情况不满足时,节点i首先完成邻居节点管理,随后根据自身与邻居节点间的距离,计算出普通事件消息mord从节点i转发到任意邻居节点z的能耗:

$ {E_{i\_z}}({m_{{\rm{ord}}}}) = \left\{ \begin{array}{l} {l_{{\rm{ord}}}}{E_{{\rm{elec}}}} + {l_{{\rm{ord}}}}{\varepsilon _{{\rm{fs}}}}s_{i\_z}^2, {s_{i\_z}} < {d_0};\\ {l_{{\rm{ord}}}}{E_{{\rm{elec}}}} + {l_{{\rm{ord}}}}{\varepsilon _{{\rm{mp}}}}s_{i\_z}^4, {s_{i\_z}} \ge {d_0} \end{array} \right.{\rm{ }} $ (6)

其中,lord为消息大小,si_z为节点i与节点z的距离。节点z接收消息所消耗的能量为:

$ {E_{{\rm{re}}, z}}({m_{{\rm{ord}}}}) = {l_{{\rm{ord}}}}{E_{{\rm{elec}}}} $ (7)

消息mord再从节点z发送到sink所需的能量消耗为:

$ {E_{z\_{\rm{sink}}}}({m_{{\rm{ord}}}}) = \left\{ \begin{array}{l} {l_{{\rm{ord}}}}{E_{{\rm{elec}}}} + {l_{{\rm{ord}}}}{\varepsilon _{{\rm{fs}}}}d_{z\_o}^2, {d_{z\_o}} < {d_0};\\ {l_{{\rm{ord}}}}{E_{{\rm{elec}}}} + {l_{{\rm{ord}}}}{\varepsilon _{{\rm{mp}}}}d_{z\_o}^4, {d_{z\_o}} \ge {d_0} \end{array} \right. $ (8)

其中,dz_o为节点zsink的距离。

因此,消息mnor通过任意邻居节点z进行转发所消耗的总能量Ei_z(mord) 为:

$ {E_{i, z}}({m_{{\rm{ord}}}}) = {E_{i\_z}}({m_{{\rm{ord}}}}) + {E_{{\rm{re}}, z}}({m_{{\rm{ord}}}}) + {E_{z\_{\rm{sink}}}}({m_{{\rm{ord}}}}) $ (9)

考虑节点iz的在消息转发过程中的能量消耗与剩余能量之间的比值,以及z所属的网络分层,节点转发概率计算Fi_z如下:

$ {F_{i\_z}} = \left\{ \begin{array}{l} {e^{-\left| {1-\frac{{R_{{\rm{ID}}}^i-1}}{{R_{{\rm{ID}}}^z}}} \right|}} \times (1 - {\rm{max}}(\frac{{{E_{i\_z}}({m_{{\rm{ord}}}})}}{{{E_{{\rm{cur}}\_i}}}}, \\ \;\;\;\;\;\;\;\frac{{{E_{{\rm{re}}, z}}({m_{{\rm{ord}}}}) + {E_{z\_{\rm{sink}}}}({m_{{\rm{ord}}}})}}{{{E_{{\rm{cur}}\_z}}}}\\ \;\;\;\;\;\;\;\;{d_{z\_o}} \le \tau {\rm{and}}{t_z} \le {T_m};\\ 0, {d_{z\_o}} > \tau {\rm{or}}\;{t_z} > {T_m} \end{array} \right.)), {\rm{ }} $ (10)

节点i的邻居节点中,如果有节点的转发概率Fi_z大于Pi,则节点i将消息mord复制给所有满足Fi_z>Pi的邻居节点。否则,节点i的通过自身将消息发送至sink。

2.4 紧急事件路由

给出紧急事件消息memg的路由策略。若与普通事件消息相同,紧急事件消息以节点“存储-携带-转发”的形式完成数据路由,则必然存在较大的延迟。因此,紧急事件消息的路由原则是:以多跳形式实时将消息转发至sink。图 3为紧急事件路由过程的示意图。

图3 紧急事件路由过程 Fig. 3 Routing process for the emergent event message

为尽快将消息传输至距离sink更近的位置,节点i依据它的邻居节点的同层/内层邻居节点数量,选择紧急事件路由的下一跳节点。节点i选择下一跳路由的步骤为:

步骤1:节点i在它的内层邻居节点中,选择具有最多内层邻居的节点作为下一跳路由节点。

步骤2:若节点i的所有内层邻居节点都没有内层邻居,则节点i在它的内层邻居节点中选择具有最多同层邻居的节点作为下一跳路由节点。

步骤3:若节点i的所有内层邻居节点都没有内层及同层邻居,或节点i没有内层邻居节点,则节点i在它的同层邻居节点中选择具有最多内层邻居的节点作为下一跳路由节点。

步骤4:若节点i的所有同层邻居都没有内层邻居,则节点i在它的同层邻居节点中选择具有最多同层邻居的节点作为下一跳路由节点。

步骤5:若节点i的所有同层邻居都没有内层/同层邻居,或节点i没有内层/同层邻居,此时节点空洞问题出现。

2.5 节点空洞问题

给出节点空洞问题避免方法。

定义6(节点空洞问题)  若紧急事件消息被转发至一个既没有内层邻居也没有同层邻居的节点,该节点将无法将消息转发至下一跳路由。这被称为节点空洞问题。

图 4为节点空洞问题示例。设当前节点a有待发送紧急事件消息。由于节点b有内层邻居c,因此节点b被选为节点a的下一跳节点。然而当节点b把消息转发到c时,由于节点c没有内层/同层邻居,节点c无法进一步转发消息,节点空洞问题出现。此时,节点c启动消息回传机制。

图4 节点空洞问题中的消息回传机制 Fig. 4 Backward mechanism in the node hole problem

在消息回传机制下,节点c首先沿路径将消息回传到上2跳的节点a。依据路由选择步骤,节点a将会选择b以外的次优节点d作为下一跳节点。随后紧急事件消息将会被转发至节点e,从而绕过节点空洞,最终被转发至sink。

若节点c启动消息回传时,节点ab已经运动离开了节点c的通信范围,则节点c携带该紧急事件消息保持运动。在τ/2v时间后,节点c重启路由发现过程。

2.6 消息队列管理

显然,普通事件路由策略会使网络中的消息出现冗余。为控制消息副本的数量,利用消息队列管理确定各节点携带的消息的转发/丢弃次序。同时队列管理还应保证紧急事件消息在队列中的可靠存储。本文根据消息延迟容忍度对队列进行管理。

各节点的待发送数据均保存在消息队列中。普通事件消息,在队列中按延迟容忍度由小到大的顺序进行排列,延迟容忍度小的消息排在前面优先发送。紧急事件消息,则总是排在队头。

为控制网络中的消息冗余,以下两种情况发生时,产生消息丢弃。

随着消息延迟容忍度的更新,若某消息的延迟容忍度减小到0,该消息立即被丢弃。

若队列已满且有新消息到达,依据到达消息的类型产生消息丢弃。①新到达消息为普通事件消息时,比较新到消息与队尾消息的延迟容忍度,并丢弃延迟容忍度更大的消息。②新到达消息为紧急事件消息时,将新到消息放在队头,同时删除队尾消息。

3 仿真实验

为评价本文提出的MRDR路由策略,利用MATLAB平台进行了仿真实验。在仿真实验中,本文定义100个移动节点在半径为100 m的圆形区域内运动。唯一的sink位于运动区域的网络中心。紧急事件消息占所有消息的30%。表 1给出了实验参数取值。

表1 实验参数 Tab. 1 Simulation parameters

实验中,MRDR算法将与FPAD、RACE算法进行对比。选择这两个算法进行对比的原因是FPAD是典型基于机会路由的数据传输算法,RACE则是面向数据硬实时数据传输的算法。仿真实验将对比3个算法在以下3个方面的性能:1) 网络寿命;2) 数据传输成功率;3) 消息平均延迟。

在开展对比实验前,首先对2.5节提出的节点空洞问题避免方法进行验证。在MRDR算法中,紧急事件消息的平均回传次数为3.67次。图 5给出了在紧急事件消息的一次路由过程中,消息回传次数与传输成功率之间的关系。由图 5可以看出,当消息回传次数少于5次时,传输成功率下降较慢。当消息回传次数大于5次后,传输成功率快速下降。在提出的MRDR算法中,紧急事件消息的平均次数为3.76次。因此,消息回传机制能保证紧急事件消息以较高的传输成功率传输至sink。

图5 紧急事件消息传输成功率 Fig. 5 Delivery ratio of emergent event message

3.1 默认环境下的算法对比

表 2给出了默认参数下,各算法取得的网络寿命。

表2 默认参数下的网络寿命 Tab. 2 Network lifetime with default parameters

定义网络寿命为网络内10%的节点死亡时间。为了评价消息队列管理机制对网络寿命的影响,也对比了没有消息队列管理的MRDR-wq (MRDR-without message queue) 算法。由表 2可以看到,FPAD算法由于对紧急事件消息也采用能耗较小的机会路由的方式进行传输,因此达到了最长的网络寿命。本文提出的MRDR算法网络寿命为1.88 d,RACE算法由于对所有的消息都进行硬实时数据路由,因此网络寿命最短。而MRDR-wq算法由于缺少消息队列管理机制,节点无法将冗余消息丢弃,因此更多的节点能量浪费于这些冗余消息的传输,从而影响了网络寿命。

分别对普通事件消息和紧急事件消息在3个算法下取得的平均传输成功率进行对比,如图 6所示。从图 6可以看出,综合普通/紧急事件消息,本文提出的MRDR算法有着最高的数据传输成功率。RACE算法的传输成功率低于MRDR。而FPAD算法虽然对普通事件消息有着较高的传输成功率,但是却难以保证紧急事件消息被发送至sink。

图6 消息传输成功率对比 Fig. 6 Comparison on average delivery ratio

图 7比较了3个算法下,普通/紧急事在件消息的平均传输延迟。由图 7可以看到,RACE算法对普通事件消息的传输延迟也非常小,而FPAD算法由于对紧急事件消息依然进行机会转发,因而消息延迟最大。提出的MRDR算法则能很好适应延迟容忍度不同的不同消息。

图7 消息传输成功率延迟对比 Fig. 7 Comparison on average delay

3.2 节点通信半径对算法性能的影响

本节实验主要研究在不同节点通信半径情况下,各种算法所能达到的消息平均传输成功率和平均延迟。

图 8(a)给出了改变节点通信半径,普通事件消息的平均传输成功率变化情况。随着节点通信半径的增加, 节点在通信范围内遇到邻居节点的可能性增大,同时通信半径的增加也提高了节点与sink的通信概率。因此, 随着节点通信半径增加,3个算法的普通事件消息平均传输成功率也逐渐提高。可以看到本文提出的MRDR算法有着最高的传输成功率。RACE、FPAD的传输成功率稍低。图 8(b)给出了改变节点通信半径,紧急事件消息的平均传输成功率的变化情况。MRDR算法同样有着最高的消息最高传输成功率,并且传输成功率随着节点通信半径的增加而相应提高。这是因为节点通信半径越大,网络分层数越少,层间传递的紧急事件消息所经过的跳数也越少,同时节点的邻居节点也更多。这样消息的传输成功率得到了提升和延迟也必然降低。图 8(c)给出了紧急事件消息占30%的网络默认状态下,网络内所有消息的平均传输成功率。由图 8可以看出,无论节点通信半径如何变化, 本文提出的MRDR算法采用两种不同的消息路由机制,能保证不同类型的消息都能以很高的传输成功率发送到sink。

图8 节点通信半径对消息传输成功率的影响 Fig. 8 Impact of node communication radius on average delivery ratio

图 9给出了节点通信半径对消息的平均传输延迟的影响。图 9(a)显示了普通事件消息的平均传输延迟。可以看到,MRDR和FPAD算法随着节点通信半径的增加,传输延迟逐渐降低。图 9(b)给出了紧急事件消息的传输延迟对比。FPAD算法下紧急事件消息的延迟与普通事件消息相同,而提出的MRDR算法对紧急事件消息采用了不同的传输策略,应该有最小的传输延迟。图 9(c)给出了紧急事件消息占30%的网络默认状态下,网络内所有消息的平均传输延迟。可以看到,FPAD算法的延迟最大,而RACE对普通事件消息也采用能耗更大的硬实时路由,因而有着最小的传输延迟。本文提出的MRDR算法对不同的消息采用不同的路由机制,因此有着恰当的传输延迟。

图9 节点通信半径对传输延迟的影响 Fig. 9 Impact of node communication radius on average delay

3.3 紧急事件消息比例对算法性能的影响

改变网络内两种类型的事件消息比例,对比3种算法的网络寿命、消息发送成功率和消息平均延迟 (图 10~12)。从图 10可以看出,由于MRDR算法能对不同类型的消息采用不同的路由机制,因此网络寿命随紧急事件消息比例的上升而降低。RACE算法由于采用硬实时路由,因此网络寿命最低。而采用机会路由的FPAD算法,网络寿命较长。

图10 消息比例对网络寿命的影响 Fig. 10 Impact of proportion of two types of messages on network lifetime

图11 消息比例对传输成功率的影响 Fig. 11 Impact of proportion of two types of messages on average delivery ratio

图12 消息比例对传输延迟的影响 Fig. 12 Impact of proportion of two types of messages on average delay

图 11显示了两种类型的事件消息比例的改变对传输成功率的影响。由图 11可以看出,MRDR算法有着最好的表现。这是因为MRDR算法能对不同的消息分别采用软实时/硬实时路由,从而实现了最高的数据传输成功率。

图 12给出了两种类型的事件消息比例的改变对传输延迟的影响。由图 12可以看出,当紧急事件消息比例很高时,FPAD算法的传输延迟依然很大。而RACE算法对所有消息都采用硬实时路由,因此紧急事件消息比例的提高对RACE算法的传输延迟也没有影响。在MRDR算法下,平均传输延迟能随着紧急事件比例的提高而降低,这说明MRDR算法能满足不同类型消息的传输延迟要求。

4 结论

本文对监控不同事件的多监控移动传感器网络的数据路由进行了研究,提出了能适应不同实时性要求的多级分层实时数据路由协议MRDR。该算法对实时性要求更低的普通事件消息进行软实时机会路由,而对实时性要求更高的紧急事件消息以尽量低的延迟进行实时路由。仿真实验验证了MRDR算法的有效性。未来,将进一步研究如何利用移动sink在多监控任务移动传感器网络收集数据。

参考文献
[1]
Yick J, Mukherjee B, Ghosal D. Wireless sensor network survey[J]. Computer Networks the International Journal of Computer & Telecommunications Networking, 2008, 52(12): 2292-2330.
[2]
Mahboubi H, Aghdam A D, Sayrafian-Pour K. Toward autonomous mobile sensor networks technology[J]. IEEE Transactions on Industrial Informatics, 2016, 12(2): 576-586. DOI:10.1109/TII.2016.2521710
[3]
Karegaonkar S M, Raut A R.Review on target coverage and network connectivity in mobile sensor networks[C]//Proceedings of the 2nd International Conference on Electronics and Communication Systems.Piscataway:IEEE, 2015:490-493.
[4]
Jeong H Y, Hong B H. Monitoring system with wireless sensor network:A survey[J]. Applied Mechanics & Materials, 2013, 300-301(4): 490-493.
[5]
Wang Y, Dang H, Wu H. A survey on analytic studies of delay-tolerant mobile sensor networks[J]. Wireless Communications & Mobile Computing, 2007, 7(10): 1197-1208.
[6]
Wang Y, Wu H.Replication-based efficient data delivery scheme (red) for delay/fault-tolerant mobile sensor network (DFT-MSN)[C]//Proceedings of the 4th Annual IEEE International Conference on Pervasive Computing and Communications Workshops, 2006.Piscataway:IEEE, 2006:485.
[7]
Wang Y. Delay/Fault-tolerant mobile sensor network (DFT-MSN):A new paradigm for pervasive information gathering[J]. IEEE Transactions on Mobile Computing, 2007, 6(9): 1021-1034. DOI:10.1109/TMC.2007.1006
[8]
Juang P, Oki H, Wang Y, et al.Energy-efficient computing for wildlife tracking:Design tradeoffs and early experiences with ZebraNet[C]//Proceedings of the 10th International Conference on Architectural Support for Programming Languages and Operating Systems.New York:ACM, 2002:96-107.
[9]
Small T, Haas Z J.The shared wireless infostation model-A new ad hoc networking paradigm (or where there is a whale, there is a way)[C]//Proceedings of the 4th ACM International Symposium on Mobile Ad Hoc Networking and Computing.New York:ACM, 2003:233-244.
[10]
Liu Tang, Peng Jjian, Yang Jin. Data delivery for heterogeneous delay tolerant mobile sensor networks based on forwarding probability[J]. Journal of Software, 2013, 24(2): 215-229. [刘唐, 彭舰, 杨进. 异构延迟容忍传感器网络中基于转发概率的数据传输[J]. 软件学报, 2013, 24(2): 215-229. DOI:10.3724/SP.J.1001.2013.04202]
[11]
Wang K, Zhang Y, Shu L, et al.NAPR:A node activity-based probabilistic routing algorithm in delay tolerant-mobile sensor networks[C]//Proceedings of the 2015 IEEE International Conference on Communications.Piscataway:IEEE, 2015:7002-7006.
[12]
Cha S, Talipov E, Cha H. Data delivery scheme for intermittently connected mobile sensor networks[J]. Computer Communications, 2013, 36(5): 504-519.
[13]
Wang K, Shao Y, Shu L, et al.An improved spray and wait algorithm based on RVNS in delay tolerant mobile sensor networks[C]//Proceedings of the 2015 IEEE International Conference on Communications.Piscataway:IEEE, 2015:3552-3556.
[14]
de Araújo G M, Becker L B.A network conditions aware geographical forwarding protocol for real-time applications in mobile wireless sensor networks[C]//Proceedings of the 2011 IEEE International Conference on Advanced Information Networking and Applications.Piscataway:IEEE, 2011:38-45.
[15]
Singh M, Sethi M, Lal N, et al. A tree based routing protocol for mobile sensor networks (MSNs)[J]. International Journal on Computer Science & Engineering, 2010, 2(01S): 55-60.
[16]
Zhang Mingchuan, Xu Changqiao, Guan Jianfeng, et al. A novel bio-inspired trusted routing protocol for mobile wireless sensor networks[J]. KSII Transactions on Internet & Information Systems, 2014, 8(1): 74-90.
[17]
Ahmed A A. An enhanced real-time routing protocol with load distribution for mobile wireless sensor networks[J]. Computer Networks, 2013, 57(6): 1459-1473. DOI:10.1016/j.comnet.2013.02.003
[18]
Camp T, Boleng J, Davies V. A survey of mobility models for ad hoc network research[J]. Wireless Communications and Mobile Computing, 2002, 2(5): 483-502. DOI:10.1002/(ISSN)1530-8677
[19]
Doshi S, Bhandare S, Brown T X. An on-demand minimum energy routing protocol for a wireless ad hoc network[J]. ACM SIGMOBILE Mobile Computing and Communications Review, 2002, 6(3): 50-66.