一种基于移动Sink的容迟网络自适应机会路由算法

徐飚

（四川大学计算机学院，成都　610000)

一种基于移动Sink的容迟网络自适应机会路由算法

徐飚

（四川大学计算机学院，成都610000)

容忍延迟传感器网络；机会路由；数据收集

0　引言

在容忍延迟移动无线传感器网络[1-2]的研究中，如何提高网络数据的传输成功率和降低并且均衡网络能量消耗一直是研究者致力的目标和研究热点。使用移动Sink进行数据收集可以有效提高网络性能，这种方法已经被广泛采用，但现存算法有以下不足：不合理的数据传输方案增大了网络时延[3]，能量消耗过大，网络传输延迟较高，且可扩展性较差。笔者提出一种高效的基于Sink简单轨迹的机会路由数据传输算法（DAOR，Dynamic Adaptive Opportunistic Routing），由数据传输和队列管理两部分组成，实验结果与DT[4]、Flooding[5]和SRAD[6]比较，实验结果表明，采用DAOR算法能够较好地延长网络生存时间，降低数据传输时延以及提高数据传输成功率。

1　模型与问题描述

在半径为R的圆形监测区域内，随机部署N个不同类型的异构传感器，传感器可以在监测区域内随机移动。石高涛等[7]等提出一种可负载平衡的移动Sink数据收集模式，并证明了当缓冲区为距离圆心R的圆环时，网络传输数据消耗能量最小。笔者设定Sink沿L=R的环形缓冲区移动并收集数据。网络结构如图1所示。网络节点异构，节点运动符合Random Waypoint（RWP）模型[1]，如图2。Sink能量不限，发射功率可控；节点可感知自己当前位置到网络原点的距离。

图1　

图2　

2　数据结构及算法

2.1数据包信息结构

对于所有数据包，在其中加入如下结构类型信息：

struct info{

int level;

int levelCount;

int position;

}

level表示当前副本的复制层级。如果当前数据包由节点直接产生，则令level=1。levelCount表示该数据在level层的副本序数，每层数据副本数不超过K。把监测区域半径分为I（I〉1）等份，从而把监测区域分为I个宽度为的圆环。每个圆环用i（1≤i≤I）表示。当节点产生数据时，节点位于i环，令position=i，表示该数据包产生位置。

2.2副本复制算法

当两节点m，n互相进入数据传输范围时，若m携带有n没有的数据包a且n离缓存节点比m近，则进行如下计算：

（1）若a的levelCount〈K,m将数据包a发送给n。节点n收到数据包后将收到的副本中levelCount加1，其他不变；

（2）若a的levelCount=K且level〈T（T值的计算见3.3），m将数据包a发送给n。节点n收到数据包后将收到的副本中level加1，其他不变。

（3）若a的levelCount=K且level=T，则将副本复制给n后，在m中删除此副本。

（4）数据包生存时间不断减少，当数据包生存时间为0时，丢弃数据包。

图3　节点运动速度对传输成功率的影响

2.3节点数据结构及算法

在每个移动节点内部设置一个数组A[I]，数组元素为结构体：

struct meanLevel{ int count;

float meanLevel;

}

A[i](1≤i≤I)表示在第i环上产生的数据包的信息。其中，A[i].count表示第i环上产生的数据包成功传输到缓存节点的个数,A[i].meanLevel表示第i环上产生的数据需要复制的层数。

每当节点成功传输第i层产生的数据包：

（1）A[i].count=A[i].count+1,当A[i].count=c时，不再增加。c表示转发层数计算的敏感度。

（2）A[i].meanLevel=(A[i].meanLevel*count+info.level)/(count+1)。

3　仿真实验

定义100个传感器节点随机分布在半径R=100m的圆形区域，节点运动符合RWP模型。设网络带宽为10kbit/s,传输半径为2-4m，运动速率为1-5m/s，节点初始能量为5-15J。

DT算法中消息副本数为1，但交付周期过长；Flooding算法中产生了大量消息副本；SRAD算法在选择下一跳时,尽可能选择与汇聚点进行通信的节点转发消息，因此传输成功率高于DT算法和Flooding算法,但算法并没有综合考虑节点与汇聚点通信的可能性和能量消耗对传输概率的影响。DAOR算法引入移动Sink节点，在转发过程中自适应控制消息副本数量，尽可能利用节点的移动，减少传输能耗，因此综合性能更优。

图4　　节点运动速度对品均时延的影响

4　结语

本文通过在机会路由过程中，根据产生数据位置，自适应计算所需转发副本数，在满足网络时延的前提下，尽可能利用节点的移动携带数据，减少副本数量，延长网络生存时间。该算法复杂度低，适合移动节点计算。

[1]刘唐，彭舰，杨进.异构延迟容忍移动传感器网络中基于转发概率的数据传输［J］.软件学报，2013，24(2):215-229.

[2]杨奎武，郭渊博，郑康锋，等.延迟容忍移动传感器 网络高效广播数据传输机制［J］.北京邮电大学学报，2013，36(1):1007-5321.

[3]Guerroumi M，Badache N，Moussaoui S.Sink Mobile for Efficient Data Dissemination in Wireless Sensor Networks［J］.Networked Digital Technologies，2012，293(8):635-645.

[4]Wang Yu，Wu Hongyi.Delay/Fault-Tolerant Mobile Sensor Network(DFT-MSN):a New Paradigm for Pervasive Information Gathering ［J］.Mobile Computing，IEEE Transactions on，2007，6(9):1021-1034.

[5]Vahdat A，Becker D.Epidemic Routing for Partially Connected Ad Hoc Networks［R］.Technical Report CS-200006，Duke University，2000.3

[6]朱金奇，刘明，龚海刚，等.延迟容忍移动传感器网络中基于选择复制的数据传输［J］.软件学报，2009，20(8):2227-2240.

[7]石高涛，廖明宏.传感器网络中具有负载平衡的移动协助数据收集模式［J］.软件学报，2007，18(9):2235-224.

Delay Tolerant Mobile Sensor Networks;Opportunistic Routing Algorithm;Data Collection

A Dynamic Adaptive Opportunistic Routing Algorithm Based on Mobile Sink in Delay Tolerant Sensor Networks

XU Biao
（College of Computer Science，Sichuan University，Chengdu 610000）

2015-12-20

2015-12-30

提出一种基于Sink简单固定轨迹的机会路由算法，算法使用改进的机会路由策略，适用于由移动节点组成的延迟容忍无线传感器网络。数据传输采用机会路由策略，每次传输数据包，在包内记录所转发层数，通过自适应算法，动态调整从任意位置将数据发送至Sink路线所需转发层数。实验结果验证算法的有效性。

徐飚（1988～），男，河南郑州人，在读研究生，研究方向为无线传感器网络、云计算

Proposes an opportunistic routing algorithm which is based on the simple mobile sink trajectory.It can be applied to delay tolerant mobile sensor network.The data transmission uses opportunistic routing strategy.Every data packet records the level by which it is transmitted. Through dynamic adapting opportunistic routing algorithm the necessary transmission level is counted.Simulations show that this algorithm has a better effectiveness.