机会网络中基于社团的能量均衡路由算法

姚明辉,张 胜,王 瑜,黄 毅

(南昌航空大学 信息工程学院,南昌 330063)

1 引 言

机会网络是由延迟容忍网络(DTN)和移动自组网络(MANET)发展而来的新型网络.它是一种源节点和目标节点之间不存在完整链路,利用节点移动带来的相遇机会实现通信的延迟容忍自组网络[1].该类网络具有节点部署稀疏、节点通信距离短、存储容量有限和拓扑结构多变等特点.随着延迟容忍网络和移动自组网络研究和应用的不断深入,机会网络越来越受到人们的关注,逐渐成为研究热点.该网络广泛应用[2,3]于野生动物监测、手持设备组网、车载网络、环境监测和交通管理等领域.应用前景十分广阔.

机会网络节点之间是利用节点移动带来的相遇机会进行通信.因此,节点之间的通信链路具有间断性,传统的基于完整链路通信的路由算法已不再适用机会网络.取而代之的是＂存储-携带-转发＂的消息转发模式.这种新的消息转发模式的核心挑战是:(1)消息转发时机与消息转发节点如何选取;(2)源节点和目标节点之间的最优通信链路如何确定;(3)不同网络模型对转发机制的影响.

为了提出能够适用于机会网络的消息传输机制,国内外研究人员提出了许多路由机制,主要有:基于转发的路由策略(如:Direct Delivery[4]等);基于复制的路由策略(如:PRoPHET[5]等).这些算法多采用多副本机制,虽然可以提高消息传输成功率和降低传输延迟.但,数据复制会给带宽有限的机会网络带来很大的网络开销,也给存储空间有限的节点带来很大的存储开销.多副本路由策略不适合于资源受限的机会网络．在节点能量和带宽受限的情况下,单副本路由机制在网络资源开销方面有较强的优势.

在许多应用中,机会网络节点一般由人类(或动物)携带,而人的移动具有社会属性.通过分析人类行为可以发现,人类行为具有时空受限特性.因此,机会网络节点移动也具有时空受限特性,即节点的移动受到时间和空间的限制,表现出周期特性.有效的利用机会网络的时空特性,能提高节点间的消息传输效率.虽然研究者已经提出了许多基于节点社会特性的路由策略,但是针对节点的时空受限特性还有待进一步的研究,在路由策略方面需进一步提高消息传输效率和均衡网络能量.针对节点移动的时空特性,本文设计了一种时空受限的移动模型,并在此基础上提出一种路由算法.本文的主要贡献如下:

①设计了节点移动模型RTSM,该模型体现了节点的时空受限特性和周期特性,反应了机会网络节点的移动规律,符合实际场景需求.

②通过综合考虑节点的相遇概率、相遇周期和剩余能量,设计了基于社团的能量均衡路由算法.该算法利用节点移动的时空特性,保证了消息高效传输、均衡了节点能量、延长了网络生存期.

2 相关工作

2.1 移动模型

机会网络移动模型是以刻画节点相遇特征为核心.移动模型决定了节点的相遇概率与相遇时间分布.而机会网络就是利用节点的相遇来实现消息的传输.因此,与传统的延迟容忍网和移动自组网相比,机会网络移动模型的研究更为重要.

目前,在机会网络移动模型研究方面取得了很多研究成果.文献[6,7]综述了机会网络移动模型研究现状.从移动模型研究角度可以将移动模型分为两类:一类是基于理论的移动模型,另一类是基于真实场景的移动模型.前者主要从理论方面构建分析移动模型,如,随机移动模型、高斯-马尔科夫移动模型等.后者主要通过分析节点的真实移动轨迹构建移动模型.如:基于社区的移动模型、基于地图的移动模型、基于工作日的移动模型、基于事件的移动模型等.

本文主要研究的是基于真实场景的移动模型.分析节点的真实移动轨迹可以发现,节点的移动具有时间和空间受限特性.即节点会按照一定的时间到同一个地点聚集,如,学生需要按照课表在指定的时间到指定的教室上课;员工会按照公司规定时间到办公室上班等.针对节点这种社会特性文献[8]提出了用户移动模型.该模型将节点的空间分为家社区和其他社区,节点以更大的概率留在家社区.该模型很好的反应的节点的空间特性,但没有考虑节点的时间特性;文献[9]提出了时变的用户移动模型,该模型很好的反应了节点的时间特性,但并没有体现节点的空间受限特性.文献[10,11]也提出了具有类似特性的节点移动模型,但都没有同时考虑节点的时间和空间受限特性.

本文根据节点的时空受限特性设计了移动模型.节点的移动受到时间和空间的限制,同时具有周期特性.该模型体现了节点移动的时空受限社会特性,符合一定场景的需求.

2.2 路由算法

目前,越来越多的研究者关注机会网络路由算法,国内外研究者从不同的角度提出了许多机会网络路由算法.最早的算法大多从消息复制方面增强机会网络的消息传输.Epidemic算法和Spray and Wait是基于洪泛的思想增加网络中消息副本数量来提高路由效率;PRoPHET,MaxProp算法通过相遇概率决定消息是否转发.

此外,具有社会特性的复杂路由算法也被相继提出.文献[12]提出一种基于社区机会网络的消息传输算法.该算法根据节点之间的相遇频繁程度,将节点划分为不同的社区,自适应的控制消息拷贝数量并依靠活跃节点传输消息.文献[13]提出了一种预测辅助的动态多副本数据传输机制.该方法根据节点时空维度相遇特征预测节点接触概率,引入区间数不确定理论描述节点接触的不确定性.文献[14]根据节点周期性的运动规律,将时间离散化并给定了时间片上节点的接触概率,提出了一种机会路由算法.文献[15]根据节点周期性相遇规律,假设节点在相同时间段有相同的相遇概率,根据节点的历史相遇概率提出概率转发机制的路由.文献[16]将节点流行度和归属团体相结合,通过具有高流行度的节点来传输消息,提出了高传输成功率消息传输的路由算法.文献[17]提出了一种基于区域朋友关系的机会路由算法.该算法利用节点的历史接触信息构造了节点亲密度评价模型,进而利用节点的当前位置和亲密关系传输数据.文献[18]利用节点兴趣提出了机会网络兴趣社团路由算法(ICR),该算法定义了节点兴趣和消息兴趣,通过节点兴趣的相似性来划分社团,然后通过节点同目标节点是否属于同一个兴趣社团来确定消息的转发策略.

为了平衡节点能量消耗,研究者也提出了一些能量均衡的路由算法.文献[19]综合考虑消息扩散程度和节点剩余能量,并结合节点相遇概率预测方法,提出了能量有效的副本分布状态感知路由机制.文献[20]提出了一种自适应动态功率控制的节能路由算法.该算法通过改进基于接收信号强度指示值的节点测距机制,将功率控制范围扩展到全部来减少节点能耗.文献[21]提出基于节点探测的能量均衡机制.该机制先通过泊松分布模型得到有效的探测概率,然后,根据相关计算得出探测接触数,最后,探测有效的能量均衡点.

本文在上述移动模型基础之上,考虑节点的移动规律和节点的能量提出了基于社团的能量均衡路由算法,该算法分为社团内的消息传输策略和社团间的消息传输策略.本文提出的消息传输策略保证了消息的高效传输、均衡了节点能量和延长了网络生存期.

3 移动模型

3.1 空间划分

在该模型中,将整个区域S划分为若干个子区域,称为活动区.活动区是指在规定的时间内同一个社团的节点参与活动的区域.活动区的形状设置为圆形.区域S内除去所有活动区外,剩余的区域为非活动区,用S0表示.如图1所示,在区域S内包含三个活动区S1、S2和S3以及非活动区S0.因此,如果网络中包含n个活动区域,即{S1,S2,…,Sn} 那么,区域S可以表示为:

S=S0∪S1∪S2∪…∪Sn

3.2 时间划分

现有的节点移动模型主要考虑节点位置、方向、速度等特点,很少考虑节点移动的时空受限特性和周期特性.针对节点的这一社会特性,本文将仿真时间划分为两个时间段,即,tf时间段,和tr时间段.tf时间段为所有节点在仿真区域自由移动的时间;tr时间段为社团节点在活动区参加活动的时间.tr和tf交替发生具有周期特性.如图2所示.

图1 区域划分示意图Fig.1 Sketch map of regional division

图2 时间划分示意图
Fig.2 Sketch map of time division

从图2中,可以得出,

T=tf+tr

(1)

t=kT

(2)

其中,t为仿真时间,T为仿真周期,k为周期数.

3.3 总体描述

移动模型共分为两个阶段,初始化阶段和节点移动阶段.在初始化阶段:节点进行社团划分和确定活动区.根据节点的相遇持续时间将节点划分为不同的社团并为它们分配活动区,这些节点称为受限节点.没有被组成社团的节点称为自由节点.社团的具体划分步骤如下:

1.初始化节点i的社团为Cx;

2.当节点i与节点j相遇时,记录两个节点的相遇开始时间tstart和结束时间tend,通过节点的相遇开始时间和结束时间可以计算出节点i与节点j此次相遇的持续时间te=tend-tstart.将这两个节点每次相遇持续时间累加,更新节点的持续相遇时间te

3.当节点i与节点j的持续相遇时间te大于阀值σ时,将节点j划分到社团Cx

由Newman和Girvan提出的模块度[22]来衡量社团划分的好坏.其计算公式如下:

(3)

其中,Q为模块度函数,其值越大社团划分效果越好.A为邻接矩阵,m为图中总边数,Pij代表节点i与节点j在模型中的边数.若节点i与节点j属于同一个社团,则δ(Ci,Cj)为1,否则为0.

由公式(3)可知,取不同的阀值将得到不同的社团结构,使得获得不同的Q值.经试验验证,阀值σ为100秒为优值.按此方法将网络中的n个节点划分为m个社团.该社团划分允许节点不属于任何社团,此节点为自由节点在仿真时间内可以自由移动.社团个数是可变的.

随着节点的移动和时间的变化,节点可能会选择参加其他社团,网络中的社团结构也会随之变化,因此,在每个周期开始之前都会有1000秒的初始化阶段来更新节点间的相遇持续时间,根据节点的相遇持续时间重新对节点进行社团划分,这样不仅符合节点的移动规律而且能降低算法的时间复杂度.

图3 移动模型流程图Fig.3 Flow chart of mobility model

在节点移动阶段:社团节点在tf时间段在整个仿真区域自由移动,在tr时间段到指定的活动区参加活动;自由节点在整个仿真时间都保持自由移动.具体流程如图3所示.

4 路由算法

在机会网络中,根据节点的移动规律将节点划分为不同的社团有利于提高消息的传输效率.若,源节点和目标节点处于同一个社团,可以在节点参加社团活动时将消息从源节点传输给目标节点,这样不仅避免了消息在其他社团中扩散降低网络资源,而且提高了消息传输成功率.若,源节点和目标节点不在同一社团,可以先利用即和源节点处于同一个社团又和目标节点处于同一个社团的中继节点将消息带到目标节点所在的社团,再通过社团内的消息传输机制,将消息传输给目标节点.若,源节点和目标节点有一个参与社团或都不参与社团,可以利用节点在自由移动时间段构建源节点与目标节点之间的消息传输路径,进而传输消息.在此情况下使用社团内的消息传输机制.因此,该算法可分为社团内的消息传输机制和社团间的消息传输机制.

4.1 社团内的消息传输

PRoPHET算法是通过分析节点的移动行为,认为现实中的节点很可能不完全按照随机的移动方式移动,而是基于某种重复行为模型,这种移动行为是可预测的.该算法定义了一个传输预测值来描述节点之间成功传输的概率,当两个节点相遇时,节点更新自身的传输预测值,并利用该值决定是否转发数据分组.由于社团内的节点相遇比较频繁,相遇概率较高,如果直接使用该算法传输数据会使得社团内存在大量消息副本,浪费资源,同时该算法没用考虑节点的剩余能量,如果节点的相遇概率很高但是剩余能量很少,那么也不利于消息传输.因此,本文将PRoPHET作相应的改进以适合社团内的消息传输.在消息转发时选择目标节点的一跳节点作为中继节点转发,同时考虑节点的相遇概率和剩余能量来决定是否转发数据分组.这样不仅保证了传输成功率,而且平衡了节点能量消耗.

网络中的每个节点维护一个转发概率向量表,用来存储节点的转发概率,节点的转发概率的计算分为转发概率更新和老化.

当节点i与节点j相遇时,节点间的相遇概率由公式(4)计算,

pm(i,j)=pm(i,j)old+(1-pm(i,j)old)×pinit

(4)

其中pinit为初始相遇概率为0.75.

节点剩余能量所占的比例pE,由公式(5)计算:

(5)

其中,Ec为节点的剩余能量,Ei为节点的初始总能量.

转发概率由公式(6)计算.该公式保证了经常相遇的且剩余能量多的节点转发概率更大.

p(i,j)=αpm(i,j)+(1-α)pE

(6)

其中α为权值因子,由实验可知,α=0.75最为合适.

节点i和j在时间单元内没用相遇,则其转发概率逐渐老化,计算公式如(7)式所示.

p(i,j)=p(i,j)old×γk

(7)

其中,γ∈[0,1] 是一个初始化常数,k为经过的时间单元数.经试验验证,γ=0.98为最合适的常数.

故,社团内的消息传输策略为:当两个节点相遇时,通过比较两个节点的转发概率来确定是否转发数据分组.若相遇节点到目标节点的转发概率大于当前节点到目标节点的转发概率,则将消息转发给相遇节点;否则,不转发.同时,算法增加了ACK机制,当目标节点收到消息时,向网络中发送ACK数据包响应消息,收到数据包的节点通过对比数据包的信息删除该消息的冗余副本,这样既能减少资源浪费,又能节约节点能量.

4.2 社团间的消息传输

社团间的消息传输的关键是找到连接社团的中继节点,通过这些中继节点构成社团间的连通路径,从而完成社团间的消息传输.由于节点可能参与不同的社团,因此,存在一些节点即与源节点在同一个社团又和目标节点在同一个社团,可以通过这些节点建立社团之间的连接路径.大量节点参与不同的社团可能存在多条连通社团间的路径,找出这些路径中的最佳路径就可以完成社团间的消息传输.

如图4所示,节点i要将消息传给目标节点d具体过程如下:假设节点i属于Cx社团,节点d属于Cy社团,节点j即属于Cx社团又属于Cy社团.当社团Cx举办活动时,节点i将消息转发给节点j,当社团Cy举办活动时,节点j会将消息带入到社团Cy,这样就建立了Cx→Cy之间的链路,通过这样的连通链路就可实现社团之间的消息传输.由于这种连通链路可能有很多条,为了找出社团间的最佳路径,本文定义了传输概率.

由于不同的社团举办活动的周期不同,可以通过周期来确定社团间的最优路径.选择频繁参加活动的节点来传输消息.通过公式(8)将社团活动的周期转化为效用值.

pt(Cy)=e-βTc

(8)

其中,Tc为节点参与社团活动的周期,β为保护因子,其取值与Tc有关,本实验设置为0.001.

图4 社团间的消息传输示意图Fig.4 Sketch map of message transmission between community

社团间的传输概率可由公式(9)计算:

pm(Cy)=p(i,j)pj(Cy)

(9)

节点在移动过程中传输概率是不断更新和老化的.当节点i与节点j建立社团间的连通链路时,通过公式(9)计算这条路径的传输概率,如果新路径的传输概率大于老路径的传输概率,则更新传输概率.否则,不更新.

由于社团之间存在多条路径,且这些路径是随着时间动态变化的,若通过节点j连接两个社团之间的路径一段时间内没有更新,则其传输概率逐渐老化,由公式(10)计算:

pm(i,j)=pm(i,j)old×ηk

(10)

其中,η∈[0,1] 是一个初始化常数,经实验仿真,η=0.98是较为理想的常数值.k是经过的时间单元个数.

故,社团间的消息传输策略为:消息在社团间转发时,通过参与多个社团的节点建立社团之间的连接路径.当节点遇到多个能到达目标社团的节点时,将消息转发给传输概率高的节点,由该节点将消息带到目标节点所在的社团,进而建立社团之间的最优路径.通过这条路径将消息从一个社团带到另一个社团.达到社团间消息传输的目的.

5 实验及结果分析

5.1 仿真环境设置

本文使用由芬兰Nokia研究中心开发的开源仿真工具ONE(Opportunistic Network Environment)[23]对提出的EBRC算法进行仿真.仿真之前,先进行10000s的初始化以完成社团划分,仿真参数如表1.

5.2 实验结果及分析

基于上述参数和仿真场景,对CMOT[24],PRoPHET,Epidemic和本文提出的算法在节点个数、节点移动速度、节点缓存和消息TTL不同下进行了算法的传输成功率、平均时延、网络负载的对比分析.最后,对比了不同算法的节点剩余能量.

5.2.1 节点数对路由算法的影响

实验设置节点的平均移动速度为6m/s,节点缓存大小为10M,消息TTL为300min.其他参数如表1所示.仿真结果如图5所示.图5(a)表明,随着节点密度的增加,EBRC算法和CMOT算法的变化趋势基本一致,同时可以看出节点密度对这两种算法的传输成功率影响不大.在仿真算法中EBRC传输成功率最高.原因分析:

PRoPHET算法和Epidemic算法没

图5 节点数对路由算法的影响Fig.5 Influence of node numbers on algorithms

有考虑节点的聚集特性和周期特性,因此消息的投递范围有限,传输成功率较低.CMOT虽然考虑了节点的聚集特性,但是并不适用于周期性聚集的移动模型,所以其传输成功率略低于EBRC算法.图5(b)表明,随着节点密度的增加,EBRC,CMOT,PRoPHET算法的平均时延在一定范围内波动,整体变化不大,这说明节点密度对这3中算法的平均时延影响不大.相反,Epidemic算法的平均时延变化很大.同时可以看出,CMOT的平均时延略低于EBRC,这是因为EBRC算法在社团间主要依靠社团活动的周期来建立社团间的消息传输路径,只有当社团有活动时,才可以传输消息.图5(c)表明,随着节点密度的增加,4中算法的网络负载都在增加.EBRC算法具有最低的网络负载.

5.2.2 节点平均速度对路由算法的影响

实验设置节点的个数为150个,节点缓存大小为10M,消息TTL为300min.其他参数如上表所示.仿真结果如图6所示.从图6(a)可以看出,节点的平均移动速度对4中算法的传输成功率影响不大,且EBRC路由算法高于PRoPHET算法和Epidemic算法.图6(b)表明,随着节点平均移动速度的增加,4种算法消息的平均时延大大降低,这是因为,当移动速度大时,消息能更快的传输到目标节点,消息的平均延时会

降低.同时可以看出,当节点平均移动速度小于8m/s时,EBRC算法的平均延时表现较好.图6(c)可以看出,随着节点移动速度的增加,PRoPHET算法和Epidemic算法的网络负载明显增加,而EBRC算法和CMOT算法几乎不变.EBRC算法的负载最低.

表1 仿真参数设置
Table 1 Simulation parameter setting

图6 节点平均速度对路由算法的影响Fig.6 Influence of node average speed on algorithms

5.2.3 节点缓存大小对路由算法的影响

实验设置节点的个数为150个,节点平均移动速度为6m/s,消息TTL为300min.其他参数如上表所示.仿真结果如图7所示.图7(a)表明,随着节点缓存的增加4种算法的传输成功率都在增加,其中EBRC算法和CMOT算法传输成功率增加较快,PRoPHET算法和Epidemic算法增加较慢.同时可以看出,EBRC算法有最高的传输成功率.图7(b)表明,节点缓存对Epidemic算法的平均时延几乎没有影响,而对EBRC算法和CMOT算法的平均时延影响较大.同时可以看出,EBRC算法适用于缓存比较小的节点,随着缓存的曾加,EBRC算法的延迟表现不佳.图7(c)表明,随着节点缓存的增加,网络负载随之减少.且EBRC算法的网络负载远远低于PRoPHET算法和Epidemic算法表现最佳.

5.2.4 消息TTL对路由算法的影响

图7 节点缓存大小对路由算法的影响Fig.7 Influence of node cache size on algorithms

实验设置节点的个数为150个,节点平均移动速度为6m/s,节点缓存为10M.其他参数如上表所示.仿真结果如图8所示.

图8 消息TTL对路由算法的影响Fig.8 Influence of TTL on algorithms

图8(a)表明,随着消息TTL的增加,EBRC算法和CMOT算法的传输成功率呈现增加后下降的趋势变化,而PRoPHET算法和Epidemic算法的传输成功率呈下降趋势.且EBRC算法的传输成功率最高.图8(b)表明,当消息TTL小于200min时EBRC算法的平均延迟随着消息TTL的增加而增加;当消息TTL大于200min时EBRC算法的平均延迟随着消息TTL的增加几乎不变.Epidemic算法的平均延迟最差.图8(c)表明,随着消息TTL的增加,4种算法的网络负载明显增加,EBRC算法具有较低的网络负载.

5.2.5 节点剩余能量对比分析

实验设置节点的个数为150个,节点平均移动速度为6m/s,节点缓存为10M,消息TTL为300min.其他参数如上表所示.仿真结果如图9所示.

图9表明,当仿真时间结束时,对于PRoPHET算法和Epidemic算法大部分节点的剩余能量为0,一部分节点剩余很多能量,网络能量不均衡.CMOT算法有一部分节点剩余能量为0,且其他节点的剩余能量也相差较大,网络能量不均衡.EBRC算法所有节点剩余能量相差不大,且没有节点能量为0,网络能量较均衡.这是因为,EBRC算法考虑了节点的剩余能量,让剩余能量多的节点传输数据,剩余能量少的节点几乎不会传输数据,因此,具有很好的能量利用,达到网络能量均衡的效果.

图9 节点的剩余能量Fig.9 Residual energy of nodes

6 结 论

本文一方面根据机会网络的移动特性结合社会网络节点的社团和周期特性,提出了一种时空受限的移动模型,使得节点的移动更加符合具有社会特性实际场景.另一方面,在这种移动模型基础之上,提出了基于社团的能量均衡路由算法.该算法在社团内考虑节点的相遇概率和节点剩余能量来转发消息;在社团间充分利用节点移动的周期特性来寻找社团间的最佳路径进行消息传输.仿真结果表明,该算法提高了消息的传输成功率,降低了网络负载,同时也实现的网络能量均衡.本文的移动模型具有一些约束条件,这于现实场景存在一定差距,需要进一步完善,EBRC算法仅仅通过周期来确定最优路径,有一定的局限性,也需要相应的优化.