移动传感器网络中基于选择复制的数据传输

1 相关工作 延迟容忍网络 DTN(delay tolerant network)用于间断连通的网络传送数据.文献[5]给出了 DTN 的总体结构, 作为网络互联时传输层上的覆盖网,它提供了数据存储和重传、经过鉴别的数据传输等服务.DTN 是基于信息 (message)交换的,它的数据单元可能是信息、分组或束(bundles).Burleigh 等人还提出了一个新的端到端覆盖层 网络协议[6],称为捆绑(bundling).

DTN 技术近几年被引入无线传感器网络,根据节点移动性的不同,可以把相关研究工作大致分为 3 类:  (1) 传感器节点均静止.第 1 类延迟容忍的无线传感器网络 DTSN(delay tolerant sensor networks)是静止的, 所有传感器节点和汇聚点全部固定不动.基于传感器节点传输距离有限及电池能量低的限制,各个节点之间松 散地连接在一起,并且传感器节点脱离网络成为孤立节点的现象时有发生.文献[7]就是静态 DTSN 具体应用的 一个实例,文中提出采用传感器网络来监控人类生活环境,并赋予用户通过 Internet 网络对此传感器网络进行控 制的权限.文献[8]提到的 SENDT 工程,其目的是建立一个 proof-of-concept 的传感器网络,对湖水质量进行监测. 由于需要定期关闭一些传感器节点以保存电池能量,因此各个节点之间就形成了一个间断连接的 DTSN 结构.

(2) 网络中具有一些易于管理的移动节点.在第 2 类 DTSN 中,可以采用一些移动节点来改善网络的连通 性.例如,data mule 方法[9]用来聚集传感器数量稀少的网络中每个传感器节点采集到的数据信息.网络中存在一 个在传感器部署区域随机移动的 data mule 实体,定期收集各个节点采集到的数据并提供交互式的信息存储转 发服务.由于传感器节点所需传输距离大为减小,因此,这种策略比静态的 DTSN 更能节省传感器的能量.

(3) 传感器节点是运动的,即 DTMSN,其中最关键的是如何设计 DTMSN 环境下的路由算法.最基本的路由 算法(数据收集方法)称为直接传递[10],基本思想是,传感器节点只与汇聚点发生通信,即只有当传感器节点运动 到汇聚点的通信范围内时两者才进行消息传输.显然,这种策略的传输能耗非常低(因为 sensor 节点只与汇聚点 通信),并且消息传输延迟主要取决于各个传感器节点和汇聚点之间的通信频率:通信频率越低,消息的传输延 迟就越大.由于 DTMSN 中传感器节点和汇聚点间的通信频率往往较低,因此该算法的传输延迟大并且数据传 输成功率也较低.针对上述问题,文献[11]提出了泛洪算法,令传感器节点把消息复制给它的通信范围内的所有 节点,目的是使网络中所有节点均包含此消息的复本.节点存储队列的大小和队列满后的丢包策略对此算法的 性能影响很大,若存储队列足够大,则这种算法能够以消耗大量传感器能量为代价获得较高的数据传输成功率. 然而,由于传感器节点的存储队列有限,致使这种算法丢包现象严重,性能较差.此外,ZebraNet[12]使用移动传感 器监测斑马的生活习性.他根据历史纪录进行路由:每个传感器节点均保存它把数据包直接成功转发给汇聚点 的历史级别,当一个传感器节点与另一个传感器节点相遇后,只有当前者的历史级别小于后者时二者才发生数 据传输.然而,这种简单的策略并不能保证所需的数据传输成功率.文献[13]讨论了采用 SWIM 系统收集鲸的生 物信息的场景,SWIM 认为,传感器的随机移动性导致所有的传感器节点和汇聚点相遇的概率均相同.为了获得 所需的数据传输成功率,传感器节点只需向网络中分发满足一定数量的数据包的复本即可.然而在实际应用中, 各个传感器节点和汇聚点相遇的概率并不相等,致使 SWIM 工作效率低下.

除了上面提到的算法以外,相关的研究还包括文献[14,15].文献[14]提出的 RED(replication-based efficient  data delivery)策略由数据传输和消息管理两部分组成.数据传输中对传输概率的计算采用了改进的基于历史记 录的方法,每当发生消息传输时,就增加节点的传输概率.若一段时间内没有发生消息通信,则适当减小传输概 率的值.消息管理则根据节点当前的传输概率值确定最佳的容错编码(erasure coding)参数以提高传输成功率. 然而,RED 中最佳容错编码参数的计算值并不准确[10],并且在网络中传输大量小的分片消息进一步加剧了网络 的传输能耗.FAD 策略[15]是在 RED 策略的基础上形成的,FAD 在采用了与 RED 相同的传输概率计算方法的同 时,根据每个消息的错误容忍(fault tolerance)值进行消息队列的管理.然而,此机制的传输能耗仍然较大,并且它 忽略了消息的存活时间,因此有可能出现某些传输延迟已经超过了网络延迟容忍限度的消息继续存留于网络 中消耗网络带宽和能量的现象.此外,DTN 技术也被广泛运用于自组织网络中[16−19].

2 网络模型和问题描述 2.1 网络模型 本文假设初始状态时,N 个传感器节点随机分布在一个 M×M 的二维正方形区域 A 内,并且为简单起见,假设 网络中唯一的汇聚点也部署在区域 A 内且固定不动.所有传感器节点和汇聚点的通信半径均为 R.此外,假设该 传感器网络具有如下性质:

所有传感器节点的运动规律符合 Random Waypoint 运动模型,为简化计算,设模型中所有节点的运动速 度相同,均为 V.Random Waypoint 运动模型描述为:传感器节点在运动空间 A 内随机取起始点 S 和目的 点 D,使用恒定速度 V 从 S 沿直线运动到 D,在 D 随机选取一个时间 Tpause 属于(Tmin,Tmax)保持静止,这样 完成一次运动过程.将本次的目的点 D 作为下次运动的起始点 S,进行下一次运动过程,如此重复.网络中 所有传感器节点均遵循上述运动过程,它们之间相互独立.节点的运动过程如图 2 所示.  • 由于汇聚点静止,所以对于所有传感器节点来说,汇聚点的位置已知.  • 各个传感器节点均明确本节点此次运动(停止之前)的目的点 D.  • 通过全球定位系统 GPS(global positioning system),各个传感器节点可获知任意时刻自己的当前位置.  • 在所有传感器节点部署完成后执行一种时间同步算法,让所有传感器节点保持时间同步.当然,这个算法 不必太精确,比如说一些准同步算法,由于 DTN 网络中消息超时时间可能会比较长,比如几分钟、几小时 甚至几天,因此同步的间隔可以大些,所以花费的同步开销可以假设较小.

2.2 问题描述 与传统传感器网络相比,DTMSN 具有如下特性:1) 节点的随机移动性.由于传感器节点或汇聚点放置在随 机运动的物体身上,因此网络的拓扑是动态的.2) 间断的连通性.DTMSN 的连通性差,某个传感器节点与其他传 感器节点之间只是偶尔连接.3) 延迟容忍.由于传感器节点间的间断连通性,DTMSN 中数据的传输延迟往往较 高,因此,应用能够容忍较大的数据延迟.  此外,传感器节点的存储空间有限,此限制对 DTMSN 的性能影响重大.因为传感器节点的数据消息在被传输到其他传感器节点或汇聚点之前都要在队列中存放相当长的时间,如何设计队列管理策略成为瓶颈.

为了满足上述特性,有效的 DTMSN 路由算法需要同时满足以下几个特点:1) 动态地选择下一时刻最有可 能接近汇聚点的传感器节点作为消息的载体.如果下一跳节点选择不正确,则会导致节点能量消耗过快和网络 性能的急剧下降.2) 设计恰当的消息和队列管理机制.合理的队列管理必然有利于提高整个网络的性能.在目前对 DTMSN传输算法的研究中,已有工作并不能同时满足以上要 求.例如,RED 算法和 FAD 算法均基于历史记录进行路由,而基于 历史记录策略的有效程度取决于节点的运动状态(速度、方向).图 3 是一个由 8 个传感器节点和一个汇聚点组成的 DTMSN 示意图 (括号中的内容表示基于历史记录计算出的传输概率值,箭头代表 节点的运动方向),其中,位于同一圆内的节点可以相互通信,且节 点 3 和节点 4 的传输概率最高.按照 RED 和 FAD 传输策略,认为这 两个节点与汇聚点的通信频率最大,从而选择节点 3 和节点 4 成为 下一跳路由节点.但由于此时两节点的运动方向均背离汇聚点,下 一时刻其他节点把数据消息传递给这两个节点并不有效.  为了解决上面的问题,本文提出了一种同时满足上述两个要 求的动态数据传输策略 SRAD.在下一节里,我们将对 SRAD 策略进行具体的描述.