机会网络中基于摆渡节点与簇节点相互协作的路由机制

刘春蕊,张书奎,2,贾俊铖,林政宽

(1.苏州大学计算机科学与技术学院,江苏苏州 215006;2.江苏省无线传感网高技术研究重点实验室 江苏南京 210003)



机会网络中基于摆渡节点与簇节点相互协作的路由机制

刘春蕊1,张书奎1,2,贾俊铖1,林政宽1

(1.苏州大学计算机科学与技术学院,江苏苏州 215006;2.江苏省无线传感网高技术研究重点实验室 江苏南京 210003)

机会网络是一种不需要在源节点和目的节点之间存在完整路径,利用节点移动带来的相遇机会实现网络通信的延迟容忍自组织网络,它以“存储—携带—处理—转发”的模式进行.为实现互不相交簇间的信息传输,本文设计了一种带阈值的簇移动模型CMMT,并提出了一种基于摆渡(Ferry)节点与簇节点协作的路由算法(CBSW).该算法减少了冗余的通信和存储开销,以及在Spray 阶段簇节点没有遇到目的节点或摆渡节点,进入Wait阶段携带消息的节点采用直接分发方式只向目的节点传输等问题.仿真实验表明,CBSW算法能够增加传输成功率,减少网络开销和传输延迟.

机会网络;移动模型;协作;路由算法

1 引言

机会网络源于延迟容忍网络(DTN)和移动自组网络(MANET),可视为两者的子类[1],它是一种在源节点和目的节点之间不存在连通路径的情况下,利用节点移动带来的相遇机会实现网络通信的延迟容忍自组织网络[2].由于环境干扰、应用特点等影响,在许多情况下无法建立全连通网络,而机会网络可满足这些应用需求,广泛应用于野生动物监测、手持设备组网、智能交通等领域.典型应用:ZebraNet[3]是一个追踪肯尼亚草原斑马活动的机会网络系统,SWIM[4]是一个监视鲸鱼活动的水下机会网络系统,基于车辆传感器的网络系统CarTel[5],能够用于监测环境、诊断车辆状态和交通路线导航等,DakNet[6]为偏远乡村提供成本较低的数字通信服务.此外,文献[7,8]设计了一种社交机会网络系统.

目前,国内外研究人员提出的机会网络路由机制,主要有:Direct Delivery、CAR等[9]基于转发策略的路由算法和Epidemic[10]、Spray and Wait[11]、PRoPHET[12]等基于复制策略的路由算法.多副本机制虽然时延较低、可靠性较高,但其占用了大量的网络带宽和缓存空间,不适合于资源受限的机会网络.在节点能量和带宽受限的情况下,单副本路由机制在网络资源开销方面有较强的优势[13].

在许多应用中,有些节点的地位高于其它节点,这些节点具有较强的存储能力和无线通讯能力,称之为摆渡(Ferry)节点.自从基于消息摆渡的路由算法被提出以后,人们对其加以改进和拓展的研究一直在进行,在Ferry节点主动运动路径的设计和优化等方面已经取得了一些进展,但在消息传输方面存在冗余的通信和存储开销,这些问题对机会网络的性能产生重要影响.在节点移动过程中,由于密度分布不均等形成互不相交的“簇”,为实现不同簇间的信息快速传输,本文设计了一种带阈值的簇移动模型CMMT,并在此基础上提出了一种协作路由算法CBSW.本文的主要贡献如下:

①设计了移动模型CMMT,该模型增加了Ferry节点与簇节点的相遇机会.

②通过簇节点与Ferry节点的协作,设计了路由算法CBSW.该算法减少了冗余的通信和存储开销、解决了在Wait阶段采用Direct Delivery方式只向目的节点传输等问题,提高了传输成功率,减少了路由开销.

2 相关工作

2.1 机会转发

路由和转发是组网技术的两个首要问题.现有的Ad-Hoc网络路由协议都是假设源节点与目的节点之间至少存在一条连通路径,不适合于机会网络.机会网络以“存储—携带—处理—转发”的模式工作,当路由表中不存在下一跳节点时,消息在当前节点存储,并随着该节点的移动寻找合适的转发时机,因而每个消息选择合适的转发节点和时机就成为设计高效机会网络路由协议的关键.文献[14]根据转发策略的不同,将现有的转发机制分为:基于冗余的转发机制、冗余效用混合的转发机制、主动运动的转发机制和基于效用的转发机制,如图1所示.

2.2 移动过程

在机会网络中,移动模型研究的是以刻划节点的相遇特征为核心.因为在机会网络中,数据传输依赖于节点移动带来的相遇机会,而节点的相遇概率和相遇时间分布是由节点的移动模型决定的.因此,与传统的MANET相比,移动模型的研究更加重要.

对于移动模型的研究主要有两种途径,一种是对模型进行理论或仿真分析,如Random Way Point[15](RWP)、Random Walk[16](RW)和Random Direction[17](RD)是3个经典的移动模型.另一种是基于运动轨迹集进行统计分析,收集运动轨迹集也就成为移动模型的研究基础之一,如MIT的Reality Mining[18]记录了MIT校园中100个智能手机移动轨迹和相遇数据,UCSD的Wireless Topology Discovery[19]收集了300个PDA与Wi-Fi接入点的相遇数据,Cambridge的Haggle[20]记录了若干iMote设备在校园内的相遇情况,UMass的DieselNet[21]收集了公交车上无线节点组成的机会网络实际运行中的相遇规律.

本文设计的移动模型根据节点类型不同而不同.簇节点采用CMMT移动模型,它们在簇范围内按一定规则移动,Ferry节点采用基于地图的移动模型,它们沿着预先设定的路径移动,为簇节点提供消息转发服务.

2.3 路由算法

在机会网络的路由算法中,Epidemic[10]是经典的路由算法之一.在Epidemic算法中,每个节点维护一个缓存区,存储源于本节点和以本节点作为中继节点的数据分组,每个数据分组有一个全局唯一标识符.同时每个节点维护一个概要向量,用来记录节点所携带的数据分组.当两节点相遇时,首先交换彼此的概要向量,获知对方存储数据分组情况后,仅传输对方没有的数据分组.Epidemic算法本质上是一种洪泛算法,每个节点都将数据分组转发给所有遇到的节点.其主要优点是能最大化数据分组传输的成功率,找到一条最短路径,减少传输延迟,其主要缺点是网络中存在大量的数据分组副本,会消耗大量的网络资源.

Spray and Wait[11](SW)也可视为基于泛洪策略的路由算法,当两节点相遇时,向对方传输没有的数据分组,但通过一定策略限定数据分组副本数量以免泛洪.Binary Spray and Wait (BSW)算法是SW算法的一种改进.

Ferry路由算法根据Ferry节点的数量可以分为两类:单Ferry路由算法和多Ferry路由算法.根据Ferry节点是否按照同一路径进行路由,多Ferry路由算法分为:Ferry单路径算法和Ferry多路径算法.典型的Ferry路由算法有:MFS[22]、NIMF/FIMF[23]、SIRA/MURA/NRA/FRA[24]算法.MFS算法是一种单Ferry节点的路由算法,首次在DTN中引入Ferry节点,为不存在连通的DTN节点提供消息转发服务,该算法主要研究静态DTN在节点稀疏分布网络场景下的数据通信问题.

为了减少冗余的通信和存储开销,本文设计了一种CBSW路由算法,该算法结合了Ferry路由与BSW路由算法的优点,并解决了在Spray阶段簇节点没有遇到Ferry节点造成传输成功率较低等问题.

3 移动模型

3.1 网络环境

被动式Ferry路由规划在已有的DTN部署应用和实验中得到了更多的应用,这是因为在实际的DTN部署应用中,由于受地理环境、交通条件以及Ferry节点承载工具的限制,Ferry节点只能被动地按照预先设定的运动路径运动,独立或辅助完成DTN网络的数据传输.例如,图2乡村通信网络就是一个典型的被动式Ferry路径规划的应用实例.

网络由多个互不相交的簇和预先设定的路径组成.移动节点分为Ferry节点和簇节点,Ferry节点采用基于地图的移动模型,且按照预先设定的路径移动.簇节点采用CMMT移动模型,且只能在其所在的簇范围内按一定规则移动.设簇的个数为N,簇的范围是半径为R的圆形区域,每个簇内有n个簇节点且簇中心位置已知,Ferry节点的个数为F,不同簇内的簇节点进行数据交换时,需通过Ferry节点协作转发,并作如下设定:

(1)同一簇内的簇节点在本簇范围内移动,移动速度较慢,它们之间的相遇概率较高,通过一跳或多跳可完成数据交换.

(2)不同簇内的簇节点移动范围互不相交,相遇概率为零.因此,不同簇内的簇节点通过移动速度较快的Ferry节点协作完成消息传递.

3.2 移动模型

设节点A在半径为R的圆形区域S内运动,Pt和Pt+1分别表示A的当前位置和下一时刻移动到的位置,并按以下规则从Pt移动到Pt+1:

(1)Pt+1从S中按均匀分布随机选择,且其选择与历史及当前位置无关.

(2)A以速度Vt从Pt匀速运动到Pt+1,且Vt的选择与历史以及当前速度大小无关.以常用的均匀速度分布为例,Vt从[Vmin,Vmax) 按均匀分布随机选择,即f(v)=1/(Vmax-Vmin)(Vmin≤v

对于一个正方形区域S内的RWP移动模型[25],其节点位置(x,y)的分布与Vmin和Vmax无关,节点位置分布的概率密度函数,记f(x,y).其特点如下:

(1)节点运动方向偏向中心,方向角θ的概率密度函数为:

+cos2θ+cosθ|cosθ|+1))

(1)

f(θ)的概率分布图如图3所示:

(2)

对于一个圆形区域S内的Cluster Movement (CM)移动模型[25],节点位置分布的概率密度函数,记f(r,θ).稳态的概率密度函数f(r,θ)在圆形区域S内非均匀分布,如下式所示:

(3)

为了增加簇节点与Ferry节点的相遇机会,通过对RWP和CM移动模型分析,设计了一种带阈值的移动模型CMMT,该移动模型增加了Ferry节点与簇节点的相遇机会.当节点A从当前坐标(Xt,Yt)移动到簇内另一随机坐标(Xt+1,Yt+1)时,需判断(Xt+1,Yt+1)到所在簇中心的距离是否大于阈值(Threshold),如果是,则先经过簇中心,再移动到(Xt+1,Yt+1),否则直接移动到(Xt+1,Yt+1).假设N个节点在半径为R的圆形区域S内运动,N分别为3,5,7,9,10,15,20,R=100m,阈值分别为0,10,20,30,40,50,60,70,80,90,100.图6为阈值对传输成功率均值的影响.以阈值=0为例,求不同节点个数的传输成功率,取其均值.当阈值>R/2时,阈值=60传输成功率均值最大.图4、5、7分别为阈值=0,50,100时节点运动轨迹.CMMT包含:在簇内按均匀分布随机选择坐标(Xt+1,Yt+1)和根据条件判断是否将簇中心加入到路径.分别如算法1、2所示.

4 路由算法

在移动模型CMMT基础上,提出了一种基于簇节点与Ferry节点协作的Binary Spray & Wait路由算法CBSW.基本思想:在网络中引入Ferry节点,其沿着预先确定的路径移动,通过控制簇节点的运动路径使其与Ferry节点相遇,从而实现不同簇内的消息传输.该算法分为两个阶段,Spray阶段和Wait阶段.

在Spray阶段,源节点将需要传输的消息复制L份.若有A节点,其中包含n个数据分组,在n个数据分组中,包括起源于A节点和以A节点作为中继节点的数据分组.A节点为簇节点或Ferry节点.

②如果A节点是Ferry节点,A进行消息转发时,只向D节点所在簇内的节点进行转发.

如果在该阶段遇到目的节点,则消息传输结束,否则随后源节点和中继节点重复进行上述过程,直到节点中只有一个数据分组为止,然后此节点转入Wait阶段.

在Wait阶段,如果消息M的源节点S与目的节点D属于同一簇,采用Direct Delivery方式转发给目的节点,否则,如果在Spray阶段没有遇到Ferry节点,采用向Ferry节点转发并向重新注入L份消息副本重复Spray阶段操作.流程图如图8所示,算法如算法3所示.

5 性能分析

在网络模型中,设簇的个数为N,每个簇内有n个簇节点和F个Ferry节点,则节点总数为N*n+F,数据分组总数为m,消息生存时间为livebime消息副本个数为L.

当n≤L时,BSW算法退化成Epidemic算法,假设在某时间段△t内,数据分组mk传输成功的概率为Pd,目的节点遇到簇节点i的概率为Pi,节点携有mk的概率为Pik；目的节点遇到Ferry节点f的概率为Pf,节点携有mk的概率为Pfk,则

(4)

(5)

当n≥L时,T1为Spray阶段,L为副本的数量,则

(6)

当不同簇内的节点进行数据传输时,在BSW算法中,如果在Spray阶段簇节点没有遇到Ferry节点,在Wait阶段,采用Direct Delivery方式传输给目的节点,会导致这些消息永远不能到达目的节点,影响传输成功率.CBSW路由算法解决了这些问题,数据传输成功率不会随着节点的增加而减少.

6 性能评价

6.1 实验平台及评价指标

ONE(Opportunistic Networking Environment)[26]仿真系统是SINDTN和CATDTN工程项目开发的,它是一个基于离散事件引擎,通过使用不同的路由协议来模拟机会网络中消息的收发,并生成多种报告.

为定量对比分析机会网络各路由算法的性能,用传输成功率、传输延迟和路由开销[27]作为评价路由算法的度量依据.

①传输成功率

传输成功率(Delivery Ratio)是在一定时间内成功到达目的节点数据分组总数和源节点发出的需传输数据分组总数之比,该度量值刻划了路由算法正确转发数据分组到目的节点的能力.

(7)

②传输延迟

传输延迟(Delivery Delay)是数据分组从源节点到达目的节点所需要的时间,通常采用平均传输延迟来评价.尽管机会网络允许较大的延迟,但传输延迟小意味路由算法传输能力强、传输效率高,同时也意味着数据分组在传输过程中占用较少的网络资源.平均消息传输延迟可用公式(8)计算,其中N表示成功传输的消息总数,TRi表示消息i成功到达目的节点的时间,TSi表示消息i的发送时间.

(8)

③路由开销

路由开销(Overhead)是指在一定时间内节点转发数据分组的总数,即源节点产生的数据分组总数和所有节点转发数据分组总数之比.路由开销高,意味着节点大量地转发数据分组,这会使网络中充斥着大量的数据分组副本,增加网络中数据分组发生碰撞的概率,也会大量地消耗节点能量.

路由开销=

(9)

6.2 仿真场景设计

仿真界面如图9所示,Ferry节点的运动轨迹如图10所示,仿真参数如表1所示.

表1 仿真场景设置

6.3 实验结果及分析

6.3.1 簇内不同节点密度下路由算法的表现

在表1中,以不同的簇内节点个数进行仿真.簇节点与Ferry节点采用的路由及仿真结果对应如表2所示,仿真实验结果如图11所示：

表2 簇节点与Ferry节点采用路由与仿真结果对应表

簇节点采用路由Ferry节点采用路由仿真结果表示EpidemicEpidemicEpidemicBSWEpidemicBSW&EBSWBSWBSW

由图11(a)可知,Epidemic、BSW&E传输成功率基本与簇内节点密度无关,BSW的传输成功率随着簇内节点个数的增加而下降,当簇内节点较少时,其传输成功率高于其它两种路由算法,当簇内节点个数较多时,其传输成功率与BSW&E算法相差较小,但不及Epidemic算法.由图11(b)可知,当簇内节点密度达到一定程度,Epidemic的路由开销随其增加近似呈指数增长,其它两种算法的路由开销基本与簇内节点密度无关,且两者的路由开销较小.由图11(c)可知,Epidemic传输延迟较大,BSW&E次之,BSW传输延迟最小.随着簇内节点个数增加,BSW&E与BSW差距变小.

在上实验的基础上,采用BSW路由算法,簇节点采用CMMT移动模型,以不同的节点数再次进行仿真,实验结果用CMMT-BSW表示,簇节点采用CM移动模型的实验结果用BSW表示.仿真实验结果如图12所示：

由图12(a)可知,当簇内节点个数较小时,CMMT-BSW传输成功率比BSW有所增加,但随着节点的增加,增加的幅度变小.原因分析：在增加簇节点与Ferry节点相遇机会的同时,促使消息在Spray阶段快速扩散,导致Spray阶段的时间变短.倘若在Spray阶段簇节点没有遇到Ferry节点,进入Wait阶段后,用Direct Delivery方式传输给目的节点,由于移动模型的约束,携带消息的节点不可能遇到目的节点并传输给目的节点,这样会导致消息传输失败.由图12(b)可知,当簇内节点个数较小时,CMMT-BSW开销比BSW小,但随着节点的增加,两者相差较小.由图12(c)可知,在传输延迟上,CMMT-BSW比BSW减少,在簇内节点个数少时,两者相差较大,且随着簇内节点个数的增加而变小.

下面的实验,簇节点采用CMMT移动模型,并用CBSW和BSW路由算法进行仿真.仿真实验结果如图13所示：

由图13(a)可知,CBSW路由算法与BSW路由算法相比,在传输成功率上有明显的增加,且CBSW路由算法基本与簇内节点密度无关.由图13(b)可知,CBSW比BSW在传输开销上有所减少,且CBSW路由算法在簇内节点个数较多时,不会随着簇内节点个数的增加而增加.由图13(c)可知,在节点数量少时,CBSW传输延迟比BSW传输延迟有所减少,当簇内节点数量较多时,CBSW传输延迟比BSW传输延迟大.

6.3.2 不同簇内节点速度下路由算法的表现

在表1中,采用CMMT移动模型,并用CBSW和BSW路由算法进行仿真,在本实验中簇内节点个数为6,以不同的速度进行仿真,得到如图14所示：

由图14(a)可知,传输成功率高低：CBSW>BSW在簇内节点速度为0～1m/s时,BSW路由算法的传输成功率较高,而CBSW传输成功率较低,当簇内节点速度大于0～1m/s,CBSW路由算法与BSW路由算法的传输成功率基本与簇内节点速度大小无关.由图14(b)可知,BSW在速度为0～1m/s时,传输开销较小,当簇内节点速度大于0～1m/s时,BSW路和CBSW路由算法的开销基本与簇内节点速度大小无关.由图14(c)可知,在簇内节点速度为0～1m/s时,CBSW与BSW传输延迟都较大,当簇内节点速度大于0～1m/s时,它们的传输延迟基本与簇内节点速度大小无关.

6.3.3 不同簇内节点缓存下路由算法的表现

在表1中,同样地,采用CMMT移动模型,并用Epidemic,CBSW和BSW路由算法进行仿真,在本实验中簇内节点个数为50,以不同的缓存进行仿真,得到如图15所示：

由图15(a)可知,CBSW与BSW路由算法的传输成功率基本与簇内节点缓存大小无关.Epidemic路由算法的传输成功率随着簇内节点缓存的增加而增加.由此可见,CBSW路由算法的成功率较高,占用缓存较小.由图15(b)可知,CBSW与BSW路由算法的路由开销基本与簇内节点缓存大小无关.Epidemic路由算法的传输成功率随着簇内节点缓存的增加而减少.与Epidemic相比,CBSW与BSW路由算法的路由开销较小.由图15(c)可知,CBSW路由算法与BSW路由算法的传输延迟基本与簇内节点缓存大小无关.Epidemic路由算法的传输成功率随着簇内节点缓存的增加而增加.

6.3.4 不同Ferry节点密度下路由算法的表现

本实验采用多个Ferry节点按照相同路径进行运动,Ferry节点个数分别取1,2,4,用CBSW算法进行仿真.仿真结果如图16所示：

由图16(a)可知,当簇内节点个数较多时,随着Ferry节点个数的增加,传输成功率有所增加; 图16(b)可知,随着Ferry节点个数的增加,传输开销有所增加；图16(c)可知,传输延迟随着Ferry节点个数的增加也是有所减少.

7 结论

在本文中,一方面通过设置阈值经过簇中心的方式,增加簇节点与Ferry节点的相遇概率,设计了CMMT移动模型.另一方面,由于相遇概率的增加,使缓存中的消息增加和消息扩散速度增加,为减少节点缓存中的消息的数量,删除了用不到的消息,并解决了在Spray阶段簇节点没有遇到Ferry节点,引起传输成功率下降的问题,设计了CBSW路由算法.仿真实验表明,CBSW算法能够增加传输成功率,且其传输成功率基本与簇内节点密度无关,该算法减少路由开销,并且在簇内节点个数较小时,减少传输延迟.

本文中采用的移动模型具有严格的条件约束,这与现实情况还存在一定的差距,需进一步完善.多Ferry节点路由算法,本文采用的是同一路径的方法,对于不同路径还需进一步深入研究.

[1]CHAINTREAU A,HUI P,CROWCROFT J,et al.Pocket switched networks:real-world mobility and its consequences for opportunistic forwarding [R].University of Cambridge,Computer Lab,Tech Rep UCAM-CL-TR-617,2005.

[2]PELUSI L,PASSARELLA A,CONTIM.Opportunistic networking:data forwarding in disconnected mobile ad hoc networks[J].Communications Magazine,IEEE,2006,44(11):134-141.

[3]JUANG P,OKI H,WANG Y,et al.Energy-efficient computing for wildlife tracking:design tradeoffs and early experiences with ZebraNet[A].Proceeding of the 10th International Conference on Architectural Support for Programming Languages and Operating Systems[C].New York:ACM,2002.96-107.

[4]SMALL T,HAAS Z J.The shared wireless infestation model:a new ad hoc networking paradigm [A].Proceedings of the 4th ACM International Symposium on Mobile Ad Hoc Networking and Computing[C].New York:ACM,2003.233-244.

[5]HULL B,BYCHKOVSKY V,ZHANG Y,et al.CarTel:a distributed mobile sensor computing system[A].The 4th ACM Conference on Embedded Networked Sensor System[C].Colorado:ACM,2006.125-138.

[6]PENTLAND A,FLETCHER R,HASSON A.DakNet:rethinking connectivity in developing nations[J].Computer,2004,37(1):78-83.

[7]MOREIRA W,FERREIRA R,CIRQUEIRA D,et al.SocialDTN:a DTN implementation for digital and social inclusion[A].ACM MobiCom Workshop on Lowest Cost Denominator Networking for Universal Access[C].Miami:ACM,2013.25-28.

[8]MOREIRA W,MENDES P,FERREIRA R,et al.Opportunistic routing based on users daily life routine[A].World of Wireless,Mobile and Multimedia Networks (WoWMoM),2012 IEEE International Symposium[C].Baltimore:IEEE,2012.1-6.

[9]NAUMOV V,GROSS T R.Connectivity-aware routing (CAR) in vehicular ad-hoc networks[A].INFOCOM 2007.26th IEEE International Conference on Computer Communications[C].Anchorage:IEEE,2007.1919-1927.

[10]VAHDAT A,BECKER D.Epidemic routing for partially connected ad hoc networks,CS2200006[R].Durham,NC:Duke University,2000.

[11]SPYROPOULOS T,PSOUNIS K,PAGHAVENDRA C S.Spray and wait:an efficient routing scheme for intermittently connected mobile networks[A].Proceedings of the 2005 ACM SIGCOMM Workshop on Delay-Tolerant Networking[C].New York:ACM,2005.252-259.

[12]LINDGREN A,DORIA A,SCHENLEN O.Probabilistic routing in intermittently connected networks[J].ACM SIGMOBILE Mobile Computing and Communications Review,2003,7(3):19-20.

[13]SPYROPOULOS T,PSOUNIS K,RAGHAVENDRA C S.Efficient routing in intermittently connected mobile networks:the multiple-copy case[J].Networking,IEEE/ACM Transactions on,2008,16(1):77-90.

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

XIONG Yong-Ping,SUN Li-Min,NIU Jian-Wei,LIU Yan.Opportunistic Networks[J].Journal of Software,2009,20(1):124-137.(in Chinese)

[15]BETTSTETTER C,RESTA G,SANETI P.The node distribution of the random waypoint mobility model for wireless ad hoc networks[J].Mobile Computing,IEEE transactions on,2003,2(3):257-269

[16]HONG X,GERLA M,PEI G,et al.A group mobility model for ad hoc wireless networks[A].Proceedings of the 2nd ACM International Workshop on Modeling,Analysis and Simulation of Wireless and Mobile Systems[C].New York:ACM,1999.53-60

[17]ROYER E M,MELLIAR-SMITH P M,MOSER L E.An analysis of the optimum node density for ad hoc mobile networks[A].Proceedings of the IEEE International Conference on Communications[C].USA:IEEE,2001.857-861.

[18]EAGLE N,PENTLAND A.Reality mining:sensing complex social systems[J].Personal and Ubiquitous Computing,2006,10(4):255-268.

[19]The University California S D.Wireless Topology Discovery Project[Z].UCSD,2004.

[20]DIO I.An Innovative Paradigm for Autonomic Opportunistic Communication[Z].2010.

[21]ZHANG X,KUROSE J,LEVINE B N,et al.Study of a bus-based disruption-tolerant network:mobility modeling and impact on routing[A].The 3th Annual International Conference on Mobile Computing and Networking[C].Montreal:MobiCom,2007.195-206.

[22]ZHAO W,AMMAR M,and ZEGURA E.Message ferrying proactive routing in highly-partitioned wireless and ad hoc networks[A].The 9th IEEE International Workshop on Future Trends in Distributed Computing Systems (FTDCS)[C].Puerto:IEEE,2003.308-314.

[23]ZHAO W,et al.A message ferrying approach for data delivery in sparse mobile Ad Hoc networks[A].Proceedings of the 5th ACM International Symposium on Mobile Ad Hoc Networking and Computing(MobiHoc'04)[C].New York:ACM,2004.187-98.

[24]Zhao W,AMMAR M,ZEGURA E.Controlling the mobility of multiple data transport ferries in a delay-tolerant network[A].Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM’05)[C].Miami:IEEE,2005.1407-1418.

[25]BETTSTETTER C,WAGNER C.The spatial node distribution of the random waypoint mobility model[A].Proceedings of German Workshop on Mobile Ad Hoc networks(WMAN)[C].Germany:IEEE,2002.41-58

[26]KERANEN A.Opportunistic network environment simulator[R].Special Assignment report,Helsinki University of Technology,Department of Communications and Networking,2008.

[27]JONES E,WARD P.Routing strategies for delay-tolerant networks[A].Proceedings of the ACM SIGCOMM workshop on Delay-tolerant networking[C].New York:ACM,2006.1577-1580.

刘春蕊 女,1987年出生于河南周口,现为苏州大学计算机科学与技术学院硕士研究生,主要研究方向为：群智感知、网络编码以及隐私保护等.

E-mail:20134227012@suda.edu.cn

张书奎 男,1966年生于内蒙古,博士,教授、博士生导师,主要研究方向为物联网、无线传感器网络、信息安全、移动计算、智能信息处理等.

E-mail:zhangsk@suda.edu.cn

Routing Mechanism Based on the Cooperation of the Ferry Nodes and Cluster Nodes in Opportunistic Networks

LIU Chun-rui1,ZHANG Shu-kui1,2,JIA Jun-cheng1,LIN Cheng-kuan1

(1.SchoolofComputerScienceandTechnology,SoochowUniversity,Suzhou,Jiangsu215006,China;2.JiangsuHighTechnologyResearchKeyLaboratoryforWirelessSensorNetworks,Nanjing,Jiangsu210003,China)

Opportunistic Networks are delay tolerant self-organized networks with sparse nodes,where the message propagation depends on the cooperation of nodes to fulfill a “store-carry-process-and-forward” fashion by leveraging the mobility of nodes,because there does not exist a complete path from the source to the destination in the most time.To achieve the communication of nodes in mutually disjoint clusters,we propose a Cluster Movement Model with Threshold (CMMT) and routing algorithm (CBSW),which is Cooperative Binary Spray and Wait routing algorithm based on the Ferry nodes and cluster nodes cooperation.This routing algorithm reduces of the redundancy of communication and store the cost,as well as if the destination or Ferry nodes are not found in the spraying phase,nodes carrying a message copy will forward the message only to its destination in the Waiting phase nodes etc.Simulation results demonstrate the effectiveness of the proposed CBSW protocol in terms of high delivery ratio,low overhead and small average delay.

opportunistic networks;movement model;cooperation;routing algorithm

2015-04-23;

2015-10-13：责任编辑：马兰英

国家自然科学基金(No.61201212,No.61572340);江苏省自然科学基金资助项目(No.BK2011376);江苏省“六大人才高峰”项目(No.2014-WLW-010);苏州市融合通信重点实验室(No.SKLCC2013XX)；江苏省产学前瞻性项目(No.BY2012114)；软件新技术与产业化协同创新中心部分资助;江苏省科技项目(No.BY2014059-02)

TP393.04

A

0372-2112 (2016)11-2607-11

��学报URL:http://www.ejournal.org.cn

10.3969/j.issn.0372-2112.2016.11.007