基于应急场景的自组织网络机会路由算法

范晓军,刘林峰,3,李思颖

(1.南京邮电大学 计算机学院,江苏 南京 210023;2.江苏省无线传感网高技术研究重点实验室,江苏 南京 210003;3.东南大学 计算机网络和信息集成教育部重点实验室,江苏 南京 211189)

基于应急场景的自组织网络机会路由算法

范晓军1,2,刘林峰1,2,3,李思颖1

(1.南京邮电大学 计算机学院,江苏 南京 210023;2.江苏省无线传感网高技术研究重点实验室,江苏 南京 210003;3.东南大学 计算机网络和信息集成教育部重点实验室,江苏 南京 211189)

应急场景是移动自组织网络的重要应用场景，在该场景中难以保证节点能够实时通信，为了在高效转发数据包的同时尽量减少网络传输中的时延，提出了基于稳定值的机会网络路由算法，并在其中引入了稳定因子的概念，将节点的移动规律与其邻居节点进行关联。对网络中的节点根据稳定值进行分类，稳定性越好的节点转发概率越高，更容易受到节点转发消息的青睐。此外，考虑到应急场景的动态性、复杂性，算法还会对节点的稳定性进行动态更新。仿真结果表明，在不同的网络规模下，逐渐增加网络中的节点数量，相比于传统的Epidemic、Direct Delivery以及Prophet路由算法，该算法的网络开销能接近较高水平，取得较高的消息送达成功率，降低平均网络时延，适用于应急场景。

移动自组织网络；机会路由算法；应急场景；稳定值

0 引 言

移动自组织网络(Ad Hoc网络)是由可移动节点互联组成的具有临时性拓扑结构的自组织对等网络系统。该网络特点是节点之间的数据传输过程不需要存在完整的链路，也不用网络提供中央控制单元和实体对等，通过节点的自组织形式形成通信域。在整个数据传输的过程中，节点通过“携带-存储-转发”的方式将消息传递到下一跳节点[1]。根据这种特点，移动自组织网络通常能够在恶劣条件下进行网络通信，可以适用于各种突发事件的应急通信场合。

应急场景是移动自组织网络的重要应用场景之一，如地震、火灾等严重灾害发生过后，包括通信、电力等一系列基础设施遭到破坏，依赖通信基础设施的通信系统瘫痪都可能无法使用。此时，依靠身处应急场景的个人或者可移动的传感器节点来进行通信，进而以这些节点组成具有临时性的通信网络将成为应急场景中至关重要的通信技术。在应急场景中，节点的运动规律很难把握，节点之间的通信成功率难以得到保证。因此，理清不同节点的移动规律，及时准确地传递消息意味着救援行动会有更高的成功率。

目前，关于移动自组织网络中对于数据传输有效性的研究已经取得了一些成果。传统的路由算法，主要沿着两大基础策略进行：(1)基于冗余的路由算法，将消息通过复制拷贝扩散到网络中，形成多消息储存的路由策略。具有代表性的是Epidemic算法[2]。(2)基于效用值的路由算法，通过效用值的计算为节点转发数据提供参考，筛选一个或多个转发节点。Prophet算法[3]就是利用转发概率这一指标进行数据转发的指导。文中所提算法也属于该类方法。

文中提出了一种应用于特定紧急场景的路由算法(Routing Scheme for Emergency Scenarios,RSES)，通过节点稳定值的计算来体现阶段时间内作为转发节点的概率值，以此概率值作为机会转发的效用值，同时对节点的稳定值进行动态更新。该算法旨在利用节点在应急场景中的稳定性，得到一个较为合理的转发策略。

1 相关研究

传统的路由算法，如极端的不泛洪Direct Delivery算法[4]，在任何情况下都是单副本传输，不会对数据包进行复制，只有遇到目标节点时才进行数据包的交付，因此路由开销最小，但是送达率和传输延迟较差。而与之相反，极端无限制的泛洪Epidemic算法是通过复制拷贝节点信息的方式，采用遇到节点就转发的方法，所有相遇节点都会收到数据包。该算法能够增加数据传输的成功率同时减少传输延迟，但是转发过程会产生大量副本，容易造成网络传输的拥塞。而Spray and Wait算法则是一定策略下的泛洪，文献[5-6]表明该算法在多数场景的应用具有一定的效果，但是在邻居节点的选择过程中，依然存在着节点选择不合理造成送达率不高和开销大等问题。Prophet算法是一种基于概率预测的算法。该算法通过统计节点与自己相遇的历史信息，得到一个转发概率的计算方式，通过计算转发概率预测将来的移动。该算法能够提高信息传递的效率和成功率，但是在节点较多的情况，要经过大量的计算才可能得到下一跳的节点，造成传递方式过于复杂的问题。Inwhee Joe等在文献[7]设定了一种特殊场景，场景中包括道路、巡逻警车、人员等节点遭受自然灾害都有不同程度的损伤，比较了传统算法在普通场景和特殊场景下的表现，指出传统的路由算法在特殊场景下各项路由指标都有退化的现象，并不能完全适用于特殊场景。文献[7]依据节点的速度来对消息进行分类，在消息传递阶段，只让移动速度快的节点进行消息转发，在降低能耗的同时，却付出了增大时延的代价。

机会网络摒弃了传统自组织网需要在端到端建立路由的工作模式，利用节点移动带来相遇机会实现通信，不要求网络全连通，可以看成是具有一般DTN网络特征的无线自组网，更符合实际环境下的自主组网需求，近年来成为国际、国内学术界关注的热点[8]。目前，关于在应急场景中机会网络的研究取得了一些成果，一般通过建立适合于应急场景的移动模型来反映节点的移动属性，并研究如何在该移动模型下，通过分析得出应急场景节点的接触规律，利用节点之间稀有的接触机会为应急场景通信创造更多的通信可能和提供更好的送达保证，是应急场景机会转发的一个重要研究方向。文献[9]定义了PDM(Post-Disaster Mobility)模型来模拟应急场景。该模型用来抽象应急场景中人的移动特征，认为在应急场景中节点的运动并不完全是随机的，如救援人员会在救护站与受灾区频繁往来，巡逻车会在主要街道来回巡逻，人员会在学校操场、广场等空旷地方集合。与此类似，Aschenbruck N等在文献[10-11]中也针对人类行为的特点提出了应急场景下的移动模型。文献[10]提出了一个以地理社区为基础的移动模型来描述受灾者的运动模式，受灾者有更高的概率在他们的家庭社区内随机移动，而在非家庭区域的社区内移动概率则较小，同时社区管理人员和救援人员会有一定的概率在社区之间移动。这两种假设有效地描绘了受灾者和社区管理人员、救援人员的应急反应运动模式。文献[12]通过对目前现有的随机移动模型进行统一化的形式描述，建立起包含所有随机模型的新的随机模型。该模型将节点移动速度设定在一个速度区间(vmin,vmax)内，通过扩大速度取值范围，扩大节点移动速度的多样性，并采用速度取值范围极差(VelocityValueIntervalRange,VVIR)这一指标来进行衡量，最后通过选取合适的速度多样性来保证适当的通信时间和通信次数以提高网络性能。然而在应急场景中，实际上节点移动速度是完全随机的，文献[13]将速度限制在某个速度区间，通过调整节点运动速度达到较好的通信效果显然并不适合于真实场景，并且作为通信中继的节点并不一定具备人的移动特征，因此文献[9，12]用在此场景中会显得比较局限。

文中定义了基于应急场景的移动模型，认为在应急场景中巡逻车辆、救援人员的运动并不完全是随机的，如巡逻车辆会在主要街道来回巡逻，救援人员会选择最短路径到达救援现场；而作为通信介质的传感器节点运动遵循随机移动模型，在速度区间(vmin,vmax)随机运动。

2 基于稳定值的转发概率更新与机会转发算法

首先介绍应急场景通信网络。在应急场景中，每个救援人员的身上配备一个带有通信功能的弹射装置，在救援过程中自动弹出一些小的传感器节点，这些传感器节点具有定位的辅助功能，在救援人员和外界指挥中心间组成一个多跳网络[14]。该网络的核心思想是将单跳通信链路转换成基于中继传感器的多跳网络，以此来消除极端环境给通信带来的影响。

传感器节点在稳定环境下会保持原先的状态，并可以维持通信网络完整，但当遇到诸如地震、火灾等恶劣环境时，节点会发生大幅度移动，或者高温使得节点损坏等都会使原先保持的通信网遭到破坏。为此，定义了2个概念：

(1)应急场景中的节点集{Va,Vb,Vc…}。其中，既有救援人员、巡逻车辆组成的规律运动的节点集，也有传感器节点这类随机运动的节点。

(2)节点稳定值(StabilityValue)。每个节点都保留着一段时间内的稳定值，用以表示这段时间内同邻居节点的关联程度，并且稳定值可能会随着时间而发生改变。

文中提出算法的理论基础，是考虑到应急场景中不同节点的运动规律。救援人员的运动具有目的性，可在最短时间到达目标地点；传感器节点受环境影响表现出移动不可预测性。假设源节点为Vs，在T0时刻产生一个发往目的节点Vd的消息，消息在传输过程中的有效生存期为Tsuv。算法思想表述为在T0+Tsuv时刻内将消息发给受恶劣环境影响最小的节点，也就是对稳定性较高的节点赋予较高的转发概率，由此类节点尽可能转发数据包，而不稳定的节点则尽可能少地转发数据包。该方式可以减少恶劣环境对路由转发的影响，减少网络中传输的副本数量，同时保证较高的送达率。

2.1 稳定值

稳定值表示一段时间内节点在通信网络中的稳定性。文中认为节点与邻居节点的距离变化值越小，稳定性越好。对于节点Vk，通过计算其与邻居节点的距离变化值来确定稳定性。

通过式(1)计算t时刻到t+1时刻节点Vk与节点Vk1之间的距离变化值。

(1)

选取节点Vk同邻居节点距离变化值最小的Δmin值，通过式(2)计算距离变化方差。

(2)

其中，Δ(k,ki)表示节点Vk和邻居节点之间的距离变化值。

(3)

其中，S(t)表示稳定因子。

每个节点都维护着一张稳定值效用表，该表格显示了节点在固定时间内的稳定值大小，当节点之间接触时，会查询对方的稳定值，并且节点的稳定值会随着时间的变化而更新，更新公式如下：

(4)

其中，Spre(t)表示上一个t时刻节点的稳定系数；k为自上次计算概率后经过的时刻数。

从式(4)可以看出，如果节点同邻居节点的偏离程度开始变大，则稳定值变小(稳定性变差)。

2.2 机会转发策略

当节点Vi携带消息准备转发时，如果检测到周围存在其他节点，则将待转发消息广播给通信半径中的其他节点，其他节点收到消息后，更新转发概率，稳定性高的节点具有较高的转发概率，更新转发概率计算如式(5)所示：

P(Vi,Vk)=

{Ppre(Vi,Vk)+[1-Ppre(Vi,Vk)]Pi}(1-S(t))

(5)

其中，Ppre(Vi,Vk)表示节点Vi，Vk相遇之前的转发概率；Pi表示[0,1]范围内的预设常量。

节点Vi搜集到通信半径内所有节点的转发概率，选择概率较大的节点进行数据转发，其中稳定因子值越大则说明这一时间段内节点稳定，作为中继节点传输的概率就大。

此外，转发概率具有传递性，Vi与Vk经常相遇，Vk与Vk1经常相遇，那么节点Vk1可能是转发消息到达节点Vi的良好中继。计算方式如下：

P(Vi,Vk1)=Ppre(Vi,Vk1)+[1-Ppre(Vi,Vk1)]* P(Vi,Vk)P(Vk,Vk1)β

(6)

其中，传递系数β∈[0,1]是常量。

算法步骤如下：

(1)任意两节点Vi和Vk进入到彼此的通信半径中建立连接；

(2)检查节点Vi和节点Vk的稳定值，用式(4)进行更新，转入步骤(3)；

(3)节点Vi和节点Vk交换彼此的信息，包括稳定值和转发概率值以及各自节点同其他节点的转发概率，交换之前检查稳定值是否更新，更新则转入步骤(4)，没更新转回步骤(2)；

(4)根据式(5)重新计算节点Vi和节点Vk之间的转发概率，并利用式(6)计算节点Vi与节点Vk1之间的转发概率；

(5)节点Vi携带发往目标节点的数据包M，如果节点Vk没有数据包M并且节点Vk的转发概率比其余节点大，则将数据包M从节点Vi发往节点Vk。

3 实验模拟及性能分析

利用3个指标(消息送达率、路由开销比和传输延时)对提出的RSES算法有效性进行验证。

消息送达率：在整个仿真期间传递成功的数据包总数(Ndelivered)与需要传递的数据包总数(Ncreated)的比值。

传输延时：是从源节点发送一个数据包到达目的节点所需要的时间。传输延时越小，说明路由算法的传输效率越高。

3.1 仿真参数设置

采用机会网络仿真平台(Opportunistic Networking Environment，ONE)[15]进行测试，模拟了基于Helsinki市的应急场景，如图1所示。

图1 基于Helsinki市的仿真场景

与路由算法Epidemic、Direct Delivery算法以及Prophet算法进行比较，具体设置见表1。

同时，为了体现应急场景的特点，设定5%的节点受不良环境影响而损坏(包括巡逻车辆、救援人员组成的节点和传感器节点)。其中巡逻车辆由于道路的坍塌损坏不能移动，救援人员的通信设备受到强干扰丧失通信功能，损坏的传感器节点其中1/2能移动但不能通信，1/2的传感器节点既不能移动也不能通信，特别说明的是传感器节点的运动是完全随机的，即随机的速度、方向和暂停时间，具体设置见表2。

表1 仿真参数设置

表2 节点设置

3.2 实验结果和性能分析

在表1的场景下，设计了不同网络规模场景，改变网络中的节点数目，依次考察三种算法性能的变化。仿真结果如图2～4所示。

图2 消息送达率与节点之间的关系

图3 路由开销比与节点数之间的关系

图2显示了当节点数目增加时算法送达率之间的比较。可以看出，三种传统算法的送达率始终低于RSES算法，主要原因是随着节点数目的增加，Epidemic算法以及Prophet算法会引起整个网络节点相遇次数的急剧增加，从而增加了传递的消息次数，造成整个网络的拥塞。在缓存区有限的条件下，这两种机制会在缓存满时丢弃一些数据包，进而影响了送达率。Epidemic算法会对遇到的每一个节点都进行消息转发，节点越多，需要转发的次数也就越多，从而导致的网络开销也急剧增长。结合图3，Direct Delivery算法只对目标节点进行消息转发，虽然网络开销基本可以忽略，但送达率较低。而RSES算法可以有效控制副本的数量，在传输之前考虑邻居节点的稳定性，只对稳定性好、转发概率大的节点进行转发，大大减少了副本数量，在节点逐渐增多的情况下，能始终保持送达率上的优势。相较于Prophet算法，RSES算法在交换历史信息的同时考虑到节点的稳定性，稳定性越高反映受到恶劣环境的影响越小，对这种节点进行转发，可以避免复制消息的盲目性，从而降低了路由开销。

图4 传输时延与节点数之间的关系

从图4中可以看出，DirectDelivery算法的平均时延随着节点数目的增加而延长，原因是DirectDelivery算法只对目标节点进行转发，当节点数目增加时，寻找目标节点也就越耗时。此外，三种算法的平均时延随着节点数目的增加都有所缩短，这是因为节点数目增加后，网络中的副本数量随之增加，和目的节点的相遇机会也随之增加，所以消息转发的平均时延会降低。同Prophet算法相比，在拥有更高的送达率的前提下，RSES算法的平均时延和Prophet算法相仿，虽然网络中的副本数量少于Epidemic算法和Prophet算法，但是正确的转发方向往往会对成功转发起到很大作用。RSES路由算法考虑到了应急场景的节点特点，在恶劣环境下，移动路线相对稳定的节点比随机移动、受环境干扰的节点更容易将消息送至目的节点，这也验证了RSES算法考虑的选择稳定性高节点进行转发的方式。

4 结束语

分析了应急场景的特点，充分利用节点运动的历史信息，结合应急场景节点特点，提出一种基于分组的路由策略—RSES。对稳定性高、受恶劣环境影响小的节点进行数据转发，避免复制消息的盲目性。仿真结果表明，RSES算法可以在保持较高送达率的同时有效减少网络中的副本数量，降低路由开销，适用于能量稀缺的应急场景。

文中仅对救援人员、传感器节点的移动特点进行了简要的仿真分析，今后的移动模型设计将从受灾者以及救援人员的角度出发，设置更多的参数准确地归纳人类的移动特征，构造特定场合的移动模型，使模型与现实场景具有高度的匹配性。

[1] 熊永平,孙利民,牛建伟.机会网络[J].软件学报,2009,20(1):124-137.

[2] Becker V D.Epidemic routing for partially connected ad hoc networks[R].Durham,NC:Duke University,2000.

[3] Lindgren A,Doria A,Schelén O.Probabilistic routing in intermittently connected networks[J].ACM SIGMOBILE Mobile Computing and Communications Review,2003,7(3):19-20.

[4] Grossglauser M,Tse D N C.Mobility increases the capacity of ad hoc wireless networks[J].IEEE/ACM Transactions on Networking,2002,10(4):477-486.

[5] Spyropoulos T,Psounis K,Raghavendra C S.Spray and wait:an efficient routing scheme for intermittently connected mobile networks[C]//Proceedings of the ACM SIGCOMM workshop on delay-tolerant networking.[s.l.]:ACM Press,2005:252-259.

[6] Becchetti L,Clementi A,Pasquale F,et al.Flooding time in opportunistic networks under power law and exponential inter-contact times[J].IEEE Transactions on Parallel and Distributed Systems,2014,25(9):2297-2306.

[7] Joe I,Kim S B.A message priority routing protocol for delay tolerant networks (DTN) in disaster areas[J].Future Generation Information Technology,2010,4:727-737.

[8] Conti M,Kumar M.Opportunities in opportunistic computing[J].Computer,2010,43(1):42-50.

[9] Uddin M Y S,Ahmadi H,Abdelzaher T,et al.A low-energy,multi-copy inter-contact routing protocol for disaster response networks[C]//IEEE communications society conference on sensor.[s.l.]:IEEE,2009.

[10] Aschenbruck N, Gerhards-Padilla E, Martini P.Modeling mobility in disaster area scenarios[J].Performance Evaluation,2009,66(12):773-790.

[11] Aschenbruck N,Frank M,Martini P,et al.Human mobility in manet disaster area simulation-a realistic approach[C]//IEEE international conference on local computer networks.[s.l.]:IEEE,2004:668-675.

[12] Wang Xiaoming,Lin Yaguang,Zhang Shanshan,et al.A social activity and physical contact based routing algorithm in mobile opportunistic networks for emergency response of sudden disasters[J].Enterprise Information Systems,2015,3(2):1-30.

[13] Lin Yaguang,Wang Xiaoming,Zhang Lichen,et al.The impact of node velocity diversity on mobile opportunistic network performance[J].Journal of Network and Computer Applications,2015,55:47-58.

[14] 谢之恒.“面包屑”消防传感系统-火灾救援中的可靠联络器[J].中国信息界,2014(4):68-71.

[15] Keranen A.Opportunistic network environment simulator[R].Helsinki:Helsinki University of Technology,2008.

An Opportunistic Routing Algorithm Based on Emergency Scenario in Ad Hoc Networks

FAN Xiao-jun1,2,LIU Lin-feng1,2,3,LI Si-ying1

(1.School of Computer,Nanjing University of Posts and Telecommunications,Nanjing 210023,China;2.Jiangsu High Technology Research Key Laboratory for Wireless Sensor Networks,Nanjing 210003,China;3.Laboratory of Computer Network and Information Integration of Ministry of Education,Southeast University,Nanjing 211189,China)

Emergency scenario is an important application scenario of Ad Hoc Networks.In this scenario,it is difficult for nodes to ensure the communication.It becomes one of the goals that forwarding data packet efficiently while minimizing the transmission delay.A new opportunistic routing algorithm based on stability value is proposed,introduction of the concept of stable factor in it that the movements of nodes are associated with their neighbors.The node which has better stability is prone to receive the data packet.Moreover,with regard to the dynamics and complexity of the emergency scenario,the algorithm will dynamically update the stability of the nodes.According to simulation results,compared with the traditional routing algorithm like Epidemic,Direct Delivery,Prophet,the proposed algorithm suitable for emergency scenario can reduce the overhead and improve the delivery ratio in different network scales.

Ad Hoc networks;opportunistic routing algorithm;emergency scenario;stability value

2016-04-14

2016-08-10

时间：2017-02-17

国家自然科学基金资助项目(61373139,61373137,61300239,71301081);中国博士后科学基金(2014M560379,2015T80484)；江苏省自然科学基金(BK2012833)

范晓军(1992-)，男，硕士，研究方向为机会网络；刘林峰，博士，副教授，研究方向为机会网络。

http://www.cnki.net/kcms/detail/61.1450.TP.20170217.1623.016.html

TP301.6

A

1673-629X(2017)03-0006-06

10.3969/j.issn.1673-629X.2017.03.002