基于结合节点概率与消息ST的DTN传输策略

摘 要:在延迟容忍的移动无线网络中,为确保消息,进行少副本、短延迟、少能耗的高效传递,选择合适的传输策略至关重要。提出一种新的基于节点位置信息建立的传输概率机制,在消息传递时通过基于传输概率的消息生存时间进行队列的管理、优化。经过仿真实验得出数据,对比现有的几种方式,该策略可以在减少消息副本,缩短传输延迟,提高传输成功率等方面做到不同程度的优化,且效果良好。

关键词:延迟容忍;传输概率;队列管理;生存时间

中图分类号:TP393 文献标识码:A

文章编号:1004-373X(2009)21-067-04

DTN Delivery Scheme Based on Transfer Possibility and ST

SONG Jipeng

(Research Institution of Electronic Science and Technology,University of Electronic Science and Technology of China,Chengdu,610054,China)

Abstract:In delay tolerant mobile sensor network,delivery scheme is a key point for effective way that offers less copies,delay and high delivery rate.At first,a new real-time delivery possibility mechanism based location information is proposed.Using the possibility to mend the survival time of messages to send.In addition,optimizing the management of message-queue can be made.By simulation,the scheme gets higher message delivery ratio,lower copies and delivery delay.

Keywords:delay-tolerant;delivery possibility;queue managemant;survival time

0 引 言

在无线传感器网络中,被传递消息的生存时间(Survival Time,ST)[1]对网络中传感器能量和网络带宽的消耗影响较大。通过加入刻画整个网络延迟容忍程度的全局性变量标签,当消息的在网生存时间大于该阈值时丢弃此消息。这样做的主要目的是为了避免生存时间过大的消息继续存留。这样就产生了一个问题,当某一消息的在网时间已经达到或超过阈值,但是没有一份传到中心节点,则会出现处于不同节点的该消息副本同时“自杀”,进而造成信息的丢失。问题归结到这个全局阈值的确定问题,但无线传感器网络的动态特性和区域差距的影响使得该值既要考虑整体网络状况,又要兼顾局部区域的通信状况,难于平衡,所以应转换思路,将全局的考虑下放到节点。

为了反映当前局部环境的状况,结合对消息传递成功的估计,可以在消息中带入一定量的标签信息,但是这些新的数据会对节点消息队列的管理以及消息通信带来额外的负担,为了解决这一困扰,可以沿用消息生存时间,并设其为可变量,将多种因素反映到对生存时间的动态修改上,这样不会引入额外的开销,且在一定程度上优化了生存时间,进而达到优化消息传递的目的。

在传输区域内如何选取下一步要传输的点,此前有多种方案:一方面是结合路由的直接传输方式[2,3],资源消耗少,但因为将传输的希望全部放在单一路线上,由于各种因素的影响,相对成功传输概率不高;另一个方面是泛洪方式,向所有进入有效传输区域的节点发送消息副本,提高了传输的成功率,但带来的网络资源消耗过大,它随传输阶数的增多呈几何级数增长;其余的是在这两个极端方式间,根据不同的策略,选择一定数量的节点进行传输,目的是在提高传输成功率和降低消耗间进行均衡,选取更佳的方案。这里采用基于传输概率的选取策略。

1 传输概率

传输概率指描述节点所携带的消息到达中心节点的可能性。在传统的无线网络中,节点静止、位置固定,传输概率由距离Sink节点的远近来确定。在加入了移动后,这种固定的方式就不存在了。图1中的点B,D位于以Sink为中心的同一圆上,与中心距离相同,但是其运动方向相反,即B出圆,D进圆。单纯按位置制定的传输概率是相同的,然而在移动的情况下,趋向中心的节点D显然要比背离中心的节点B的传输可能性要大。而这是RED [4,5],RAD [6]等策略中所采取的方式。

针对仅考虑位置,而不考虑移动方向的情况,采取新的方式。根据节点运动的目的地与中心节点通信范围的远近来刻画。通过夹角可知,当运动终点的角较大时,节点最终距中心较近,传输可能性较大,在0～180°间变化,相应的点Destiny在距中心通信范围+∞～0之间;当Destiny位于中心通信范围内时传输概率为1。这样以上的问题得以解决。然而新的问题随之而来,上面的模型是以移动的终点来代表运动方向的,没有考虑到运动路线的整体情况,按照上面模型衡量,拥有相同的终点,其传输概率置为相同,但实际情况是沿途经过中心区域的要拥有更高的传输可能性,模型出现了问题。究其原因,是将节点的运动依靠终点来衡量,而不是运动的路线,也就是考虑了终点而没有考虑起点。

图1 移动节点全局分布

在移动的影响下,传输概率的衡量方法灵活多样,测算的公式以及策略简繁不一。

然而,回过头来分析移动节点,目的是以极大可能转向中心节点而多跳的形式转发消息。作为节点本身,已知中心位置、自身的位置、通信范围内的其他节点,考虑节点运动路线来衡量传输概率固然理想,但实际的运动与预期路线的差距往往使效果打折扣。如地形的起伏、节点间的碰撞、存在障碍物等。反观最初的节点-中心距离的方式,因为移动而失效,现在将移动融合进去,将节点实时的位置反映到传输概率中。

下面根据上述Random Waypoint运动模型[7],以节点i为例,定义任意时刻节点i的传输概率pi:

pi=1,R/d≥1

R/d,R/d<1

式中:d为当前节点到Sink节点的距离;R为Sink节点的通信半径。

当R/d≥1时,节点位于Sink通信范围内,传输概率为1。

当R/d<1时,说明节点与Sink圆的接近程度偏向1,则更接近圆,反之偏离圆。

在传输前用当前位置更新节点传输概率;通过握手通信,得到邻近节点的pi值;选择传输概率较高的点传输消息。信息沿着趋向Sink的同心圆方向逐级传递。

这样可以脱离消息传递对于节点移动的依赖,可以视中心节点及其传输范围为中心,形成一个传输概率场,距离场心近的传输概率大,反之则小。

这一方式避免了不考虑运动情况的模型,也避免了只考虑移动终点的偏颇,实现上也简便易行。在以消息传递为最终目标的运动中,通过节点位置定义的传输概率可以优化消息的传递。在这一模型下,消息沿着传输概率递增的节点路径进行多跳传输,减少了副本数量,提高了传输效率。

2 生存时间

设消息M中的生存时间变量为T0,所在节点为Q,节点的传输概率为Qp,包括通信范围内所有节点。经过基于传输概率的选取策略选定将要传输的点,不妨设这n个节点为Xi(i∈[1,n])以及节点各自的传输概率pi,传输到n个节点的消息副本为Mi,生存时间为Ti。下面所要做的是在完成消息传递的同时,分别设置发送、接收的n+1个节点消息的生存时间。

研究发送节点消息:

(1) 当传出消息副本数量n增多时,成功传输的概率就大,消息的在网生存时间相应减少。

(2) 当接收节点本身的传输概率较大时,成功传输的概率就大,可以减少生存时间。

(3) 当接收节点相对发送节点传输概率的梯度较大时,意味着消息向目标传输的爬升速度加快,需要减少生存时间。

总地来说,消息的传输过程是所经历过节点的传输概率严格单调递增,生存时间严格单调递增。

综合以上各因素,进行线性化,可得出发送节点生存时间刷新公式:

T′0

=T0•

从副本数、接收节点传输概率、消息传输梯度等方面刻画了对生存时间的影响,这些待定系数的权重需要模拟真实环境,在分析全局数据后,进行最佳逼近,此处暂定为1∶2。

研究接收节点消息:

(1) 由于消息的ST随节点的推移呈单调递增趋势,所以接收节点的ST要严格小于上一节点的ST值。

(2) 接收节点各自的传输概率不同,所接收消息的ST值也应反映这种差异性,即传输概率大的ST要相对小。

(3) 随着传输概率的递增,消息队列中的消息数也递增,而队列的长度受制于硬件的设计,已经先天固定。在这一逐级的累积效应下,要对队列进行频繁的出入管理,但此处消息又相对重要,因此要通过ST值的设定权衡处理。将节点累计反映到ST中。

在各种因素下,接收节点副本消息ST设置公式为:

Ti=T′0(1-dpi)

通过对上一节点、本节点传输概率的累计效应刷新本地消息的生存时间。

在接收节点得到的消息副本后,要将该副本插入已有的消息队列中。这样要选择一方(发/收)设置副本的生存时间。一方面,此处的生存时间来源于发送节点,继承自已经重置后的

T′0

;另一方面,由于节点本身传输概率的差异,同一消息发往不同节点副本的ST值不尽相同。

综合考虑后,采取的策略为发出方将更新ST后的消息复制n份,分别发送到n个接收节点。接收节点再将该副本消息结合自身的特征对ST进行刷新重置,之后插入消息队列中进行管理。

算法如下:

1. if (Receiving a new message i from other node)

2. {Ti = T0-de•pi-e•mi;

3. mi++;

4. insert into message queue of this node;

5. }----接受消息副本更新ST插入队列----

6.. if (Sending the copies of the messages MSG to nodes Xi which i∈[1,n])

7. {T′0=T0•

8. for(every int i∈[1,n])

9.{

10.send MSGi to node Xi;

11.}

12. }----发送消息到选中节点----

13. for (every j in the queue of node i )

14. Tj--;

15.----根据本地时钟更新队列中消息ST值----

3 仿真设定与性能衡量

3.1 参数设置

根据DTN网络的结构[10]特征,设计仿真实验,相关主要参数如下:

(1) 场景环境

在200×200的正方形区域内,划分20×20的100个格子作为独立区域;每格子在系统初始化时,都随机产生一定温度范围内的初始温度;随机散布传感器节点于大正方形区域内;Sink节点位于区域中心;在设定的仿真时间内节点按照waypoint方式移动,并进行节点通信;当仿真计数归零时停止运动,进行数据的统计与分析得出结果。

(2) 涉及到参数

移动速度、计时粒度、通信半径、队列限度、等待时限、格子温度范围、初始生存时间。

(3) 性能指标

传输效率:最终到达中心节点的消息占区域产生消息的百分率。

副本数:平均每条消息被复制的数目。

平均延迟:首个到达中心节点的消息(或其副本)传递的时间(从产生到抵达中心)。

3.2 数据与绘图

默认设置:

区域:200×200区域划分:10×10

区域温度:0～20初始生存时间:100

时间粒度:1 队列限度:100

节点数:100 中心节点:(100,100)

传输半径:3 移动速度:3

FAD的FT门限:0.8 FAD的a:0.5

试验在保证其余默认值的前提下,更改半径、速度、队列。

数据与绘图如图2所示。

图2 不同传输半径、移动速度、队列长度下的效率对比

4 结 语

与传统泛洪、直接传输和FAD方法相比,新的策略主要由基于传输概率的传递策略以及基于生存时间和信息融合的队列管理组成,经过对比试验,在效率与稳定性方面有优良的表现。提高了传输率,降低了整体通讯负担,优化了节点消息的管理,在一定程度上降低了消息传递对于节点的信息处理能力的依赖。但该策略有待于在实践中,尤其是在能量消耗、复杂环境等方面作进一步检验。

参考文献

[1]

Wang Yu.Replication-Based Efficient Data Delivery Scheme (RED) for Delay/Fault-Tolerant Mobile Sensor Network (DFT-MSN)[A].Proc.of Fourth Annual IEEE International Conference on Pervasive Computing and Communications Workshops.Pisa: IEEE Press,2006:485-489.

[2]Wang Yu,Dang H.Analytic Study of Delay/Fault-Tolerant Mobile Sensor Networks (DFT-MSN′s)[R].Tech.Report,Lafayette: CACS,University of Louisiana at Lafayette,2006.

[3]Mihaela Cardei,Yang Shuhui,Wu Jie.Algorithms for Fault-Tolerant Topology in Heterogeneous[J].Wireless Sensor Networks IEEE Trans.on Parallel and Distributed Systems,2008,19(4):545-558.

[4]Tracy Camp,Jeff Boleng,Vanessa Davies.A Survey of Mobility Models for Ad Hoc Network [J].Wireless Communication & Mobile Computing (WCMC): Special Issue on Mobile Ad Hoc Networking :Research,Trends and Applications,2002,2(5):483-502.

[6]周晓波,卢汉成,李津生,等.AED: 一种用于DTN 的增强型Earliest-Delivery[J].电子与信息学报,2007,29(8):1 956-1 960.

[5]Wang Yu,Wu Hongyi,Dang Ha,et al.Analytic,Simulation,and Empirical Evaluation of Delay/Fault-Tolerant Mobile Sensor Networks[J].IEEE Trans.on Wireless Communications,2007,6(9):3 287-3 296.

[7]Wang Yu,Wu Hongyi.The DFT-MSN: The Delay/Fault-Tolerant Mobile Sensor Network for Pervasive Information Gathering.25th IEEE International Conference on Computer Communications.2006:1-12.

[8]Zhou Xiaobo,Zhou Jian,Lu Hancheng,et al.Analysis of Delay Model in DTN[J].Application Research of Computers,2008,6:960-966.

[9]Vinton Cerf,Scott Burleigh,Adrian Hooke,et al.Deley-Tolorant Network Architecture[Z].DTN Research Group Internet Draft,2003:5-15.

[10]Michael Demmer,Eric Brewer,Kevin Fall,et al.Intel Implementing Delay Tolerant Networking [EB/OL].http://citeseerx.ist.psu.edu/legacymapper?did=725204.2007.10

作者简介 宋吉鹏 男,1982年出生,吉林白城人,四川大学应用数学专业理学学士、电子科技大学电子科学技术研究院硕士研究生。研究方向为无线传感器网络,无线路由、数据融合。