突发事件下机会网络节点移动模型研究

王霞,李旭宏，张伟，潘文文，徐涛

(1.枣庄学院信息科学与工程学院，山东枣庄　277160；2.南京大学计算机科学系,江苏南京　210000)



突发事件下机会网络节点移动模型研究

王霞1，2,李旭宏1，张伟1，潘文文1，徐涛1

(1.枣庄学院信息科学与工程学院，山东枣庄277160；2.南京大学计算机科学系,江苏南京210000)

[摘要]针对地震、水灾、强热带风暴等突发事件下固定网络通信设施可能被摧毁而无法正常工作的情况，提出突发情况下机会网络节点移动模型与相应路由算法.模拟实际的灾后场景，分析各移动节点的移动特征，构建灾后节点移动模型，并对节点之间的协作性进行研究，提出适合的邻域协作路由算法，仿真结果说明基于邻域的节点移动模型及路由算法适用于灾后网络通信.

[关键词]机会网络；节点移动模型；灾后场景；移动特征；邻域协作路由算法

0引言

地震、火灾等灾难性突发事件往往引起大规模的网络中断，这给灾后的救援工作带来了很大困难.而传统的互联网络很难在短时期内正常恢复使用，机会网络以其节点移动性和通信的随机性等特点，适用于灾后暂时性网络通信.将机会网络应用于灾后暂时性通信系统的构建，将会给灾后的救援工作带来很大的帮助.

机会网络是一种不需要源节点和目的节点存在完整链路，利用节点移动带来的相遇机会实现通信的网络.机会网络应用于灾后应急通信的关键是建立灾后节点移动模型和构建相应路由算法.目前国内外都没有建立针对灾后应急通信的节点移动模型；机会网络路由协议大多都处于研究之中.如何构建灾后应急通信的节点移动模型，如何根据灾后通信节点的移动特征，设计适合的路由算法使得各点利用有限的资源进行协作完成数据转发是目前急需解决的两大问题.

本文对灾后场景中的节点分布进行模拟，对节点移动特征进行分析统计，研究出灾后节点移动模型；并在现有路由协议的基础上，对节点集进行区域划分并实现基于邻域的节点协作式路由算法.

1国内外研究现状

目前，机会网络主要应用于车载网络、手持设备网络、野生动物追踪、偏远地区网络传输等领域，针对灾后应急通信的研究目前还比较少.

节点移动模型研究是当前机会网络理论研究的热点之一.节点移动模型[1]描述了移动节点的移动模式，包括节点位置、节点移动速度、以及加速度等特征的变化.目前，针对机会网络节点移动模型的研究主要包括以下几种[2]：

(1)基于统计的实际移动模型：采用统计的方法收集实际环境中节点的运动轨迹，从而研究节点移动特征而生成的移动模型.MIT 的Reality Mining 项目[3]、UCSD 的Wireless Topology Discovery[4]、剑桥大学的Haggle 项目[5]都采用统计的方法对实际节点移动模式进行研究并生成了相应的机会网络节点移动模型.

(2)独立同分布的理论移动模型：目前存在3 个经典的独立同分布移动模型---- Random Walk[6](RW)的原型是物理学中的布朗运动模型；Random Way Point[7](RWP) 是一种个体移动模型；Random Direction[8](RD)是一种更稳定的随机模型，更加符合实际节点运动轨迹.

(3)基于社区的移动模型：文献[9]通过分析发现，实际节点的移动具有社区特性.Musolesi 等人[10]提出了一种基于社区的移动模型；在此基础上， Spyropoulos 等人[11]提出了时变的社区移动模型.

综合国内外机会网络节点移动模型的研究，具有如下特点：(1)由于机会网络尚未大规模应用，对其实用性仍需考证；(2)很大程度上，节点移动模型和路由算法分离开研究，使得路由算法缺乏对具体场景的针对性.

本文将模拟实际场景中灾后节点的移动变化，分析位置变化的特征，在社区移动模型的基础之上根据灾后场景下节点移动的特征对节点进行区域划分，构建灾后节点移动模型，并根据各移动节点的协作特征，研究出适合的节点邻域协作路由算法.

2突发事件下机会网络节点移动模型构建

根据对地震等灾后通信场景进行模拟，我们发现，地震后网络中断，各个村子或社区的网络成为一个个网络孤岛，很难连成一个完整的城市网络.但根据统计分析，灾后的通信节点仍具有社区性特征，只是各个社区间的移动节点发生了改变[12].

根据对真实场景进行模拟，搭建出基于区域的灾后节点移动模型，模型具有以下特征：

(1)移动节点位置特征：移动节点具有区域聚集性，比如一个村落，或者一个社区，但同时又具有移动区域的局限性，因为灾难的发生，移动幅度很小，或者几乎没有.但是根据灾难发生后移动网络的特征，一般在搜救的过程中，会出现频繁出没在各个区域的搜救节点，比如搜救飞机或者其他快速搜救工具带来的移动节点，这一类移动节点大多具有基点的作用，但比基点具有快速移动性的特点，其活动范围和活动频率要活跃的多.

图1　基于区域的移动节点模型

(2)节点移动数学模型的构建：通过对节点位置特征和移动特征进行研究，对移动节点划分区域，建立了基于区域的移动节点数学模型，因为区域间的节点移动仅限于小范围内移动，所以提出了邻域的概念，并且根据节点往来的频繁度提出亲密邻域的概念，其中在搜救的过程中，一般会出现频繁出现在各个区域的搜救节点，称之为活跃节点.节点移动数学模型的构建主要涉及到节点、区域、邻域、亲密邻域、活跃节点集、亲密使者集等几个概念以及其表示方法.具体模型如图1所示.

节点的表示：所有移动节点MB={节点ID,目前所属区域BZID，来自区域OZID,一定时间间隔内曾去过的区域PZID集}.

区域的表示：区域是以若干个节点为核心组成的邻接网络连通区域，区域以三元组Z={区域ID，{节点集ZN}，{拓扑表}}表示，其中，拓扑表包含节点协作路由表项：ZT={目的区域，邻域集，亲密使者集ZBS，生存周期T}，拓扑表告诉我们要到达目的区域，经过哪些邻域，通过那些亲密使者完成了信息转发.

邻域的定义：有一定节点数直接往返的两个区域成为邻域.

亲密邻域的定义：有一定节点数频繁往返的两个区域成为亲密邻域.

亲密使者集：在两个亲密邻域内频繁往返的节点，包括活跃节点和其他亲密使者节点.

(3)节点移动模型的描述：

区域边界的确定：区域的确定以文献[13]中社区的边界定义为基础，以村庄或者生活社区为基础区域边界.在特殊灾难情况下，比如森林火灾等，以地域为边界.区域边界的确定有移动节点自行搜索完成，采用触发更新式原则进行区域内部节点集的更新.

节点属性描述：在一个时间点，每一个节点的从属区域只有一个，这个从属区域可能随时改变，节点属性包含以下内容：

节点ID：本节点的标识符.

目前所属区域BZID：用以标识本节点目前的位置.

来自区域OZID：用以标识本节点最近的来源ID.

一定时间间隔内曾去过的区域ID集：这个集合包含在一定时间间隔内，本节点曾到过的区域的区域ID，用以标识本节点的活跃程度.一定时间间隔内曾去过的区域由一个二元组{区域ID，频繁度PD}构成，频繁度属性PD的值表示在一定时间间隔内本节点到这个区域的次数，根据灾后通信的特点，这个时间间隔一般定义为12-24小时，在这段时间间隔内PD值大于等于3就说明，这个区域与节点从属区域为亲密邻域，且此节点为二者之间的亲密使者.各概念之间关系如图2所示.

图2　节点移动模型各概念之间关系图

3邻域协作路由算法研究

基于邻居的路由算法在国内以后不少研究成果[14-16].本文在节点移动数学模型和已有路由算法的基础上，提出了基于邻域协作的路由算法，具体内容如下：

(1)区域的节点集和拓扑结构的更新：节点定期探寻其通信范围内其他节点位置，并根据洪泛的方法迅速建立区域的边界，确定区域内容的节点集合；节点不停搜索邻近新节点，如有新节点加入，触发更新区域边界和节点集，从而完成区域的边界界定和拓扑结构的定期更新.具体流程如图3所示.

图3　区域边界与拓扑表更新过程

图4　基于邻域的协作路由算法流程

(2)路由算法的改进：在文献[17-18]的路由算法基础上进行算法改进，亲密邻域之间通过与亲密使者的相遇进行通信；一般邻域之间扩大副本的转发范围，转发给有限个(一般是三个)亲密使者，通过亲密邻域加大到达目的节点的几率.每个数据包具有一定的生存周期，告诉每个亲密使者数据包的生存时间，一般以跳数(即所经过区域的个数)表示，超过10个区域，就会将此数据包丢弃，以免浪费网络资源.具体算法流程如图4所示.

4实验平台构建和算法验证

针对具有活跃节点和没有活跃节点的两种节点移动模型，进行.

借助C++语言对域内和域间路由算法进行实现，并在Matlab上实现对算法性能的展现.

(1)具有活跃节点的机会网络节点移动模型下，平均90%的数据包可以通过活跃节点辗转转发到目的区域的目的节点，这一成功率随着网络范围的扩大而不断减小，如表1所示.

表1　模型一不同实验参数下数据包转发成功率

(2)在模拟灾后通信状况下不具有活跃节点的机会网络节点移动模型下，成功率明显降低，因为本身节点的移动范围有限，具有亲密特性的邻域明显减少，从而转发成功率也明显降低，在定义每个区域的亲密邻域个数为3，亲密使者活跃基本活跃在相邻两个邻域之间的前提下，数据包转发成功率如表2所示.

表2　模型二不同实验参数下数据包转发成功率

5结语

本文将机会网络应用于灾后应急通信，提出一种新型的节点移动模型---基于邻域的节点移动模型；并通过对现有路由算法进行改进，提出适合于灾后移动节点通信的基于邻域的协作路由算法，以提高到达目的节点的成功率.

参考文献

[1]徐鑫鑫,王玲,张衡阳.无线移动Ad hoc网络移动模型研究[J].计算机应用研究,2009, 26(3):804-808.

[2]熊永平,孙利民,牛建伟,等.机会网络[J].Journal of Software, 2009, 20(1):124-137.

[3]Eagle N, Pentland A.Reality mining: sensing complex social systems [J].Personal Ubiquitous Computing.2006, 10(4):255-268.

[4]UCSD. Wireless topology discovery project, 2004,http://sysnet.ucsd.edu/wtd/wtd.html.

[5]Diot C. Haggle project. 2004,http://www.haggleproject.org.

[6]Broch J, Maltz DA, Johnson DB, Hu Y, Jetcheva J. A performance comparison of multi-hop wireless ad hoc network routing protocols[J].MobiCom’98. 1998:85-97.

[7]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.

[8]ROYER EM, MELLIAR-SMITH PM, MOSER LE. An analyisis of the optimum node density ofr ad hoc mobile network [J]. Proc of IEEE International Conference on Communications. 2001:857-861.

[9]Pan H, Chaintreau A, Scott J, Gass R, Crowcroft J, Diot C. Pocket switched networks and human mobility in conference environments[J]. In: Proc. of the 2005 ACM SIGCOMM Workshop on Delay-Tolerant Networking. Philadelphia: ACM. 2005: 244-251.

[10]Musolesi M, Mascolo C. A community based mobility model for ad hoc network research [J]. In: Proc. of the 2nd Int’l Workshop on Multi-Hop Ad Hoc Networks: From Theory to Reality. New York: ACM.2006:31-38.

[11]Spyropoulos T, Psounis K, Raghavendra CS. Performance analysis of mobility-assisted routing [J]. In: Proc. of the 7th ACM Int’l Symp. on Mobile Ad Hoc Networking and Computing. 2006:49-60.

[12]孙践知,韩忠明,陈丹,等.灾难场景下基于分组策略的机会网络路由算法[J].计算机工程，2011, 37(23):79-83.

[13]牛建伟,周兴,刘燕,等.一种基于社区机会网络的消息传输算法[J].计算机研究与发展，2009, 46(12):2068-2075.

[14]郭陆.基于动态社会关系的机会路由研究[J].计算机应用与软件，2013, 30(11):180-183.

[15]刘亚翔,高媛,乔晋龙,等.机会社会网络中基于社区的消息传输算法[J].计算机应用，2013, 33(5):1212-1216.

[16]吴大鹏,向小华,王汝言,等.节点归属性动态估计的机会网络社区检测策略[J].计算机工程与设计，2012, 33(10):3673-3677.

[17]李东生,杨志义,郭斌,等.基于机会网络的社会性活动组织研究[J].计算机科学，2013, 40(2):35-39.

[18]周强,应晶,吴明晖. 基于特征分类的机会网络多因素预测路由[J]. 浙江大学学报(工学版),2010, 44(3):413-418.

[责任编辑：吕海玲]

A Scheme of Opportunistic Networks Nodes Mobile Model on Emergency

WANG Xia1,2,LI Xu-hong1,ZHANG Wei1,PAN Wen-wen1,XU Tao1

(1.College of Information, Zaozhuang University, Zaozhuang 277160,China;2. Departiment of Computer, Nanjing University, Nanjing 210000,China)

Abstract：Disasters result in network communication was destroyed. The characteristics of survivability, Self-organization and mobility made the opportunistic networks apply to network communication after disaster. Neighbour-based nodes mobile model and message transmission scheme are proposed which utilizes frequent moving of nodes among the neighbour areas to dispatch the message. Simulation results show that this scheme can balance well the trade off between delivery ration and resource consumption in opportunistic network.

Key words：opportunistic networks; nodes mobile model; scenes of devastation; mobile characteristic; neighbours-based routing algorithm

[中图分类号]TP393.03

[文献标识码]A

[文章编号]1004-7077(2016)02-0103-06

[作者简介]王霞(1978-)，女，山东枣庄人，枣庄学院信息科学与工程学院讲师，工学硕士，南京大学计算机科学系2015级在读博士研究生，主要从事无线网络、RFID射频识别系统的研究.

[基金项目]山东省高等学校科技计划项目(项目编号：J12LN53).

[收稿日期]2016-01-17