机会网络路由

机会网络路由（通用7篇）

机会网络路由 篇1

随着大量具有短距离通信功能的智能终端设备出现,研究人员开始利用这些设备移动带来的通信机会,在网络基础设施无法完全覆盖的环境中进行组网,提出了机会网络[1](Opportunistic Network)的概念。在机会网络中,通信节点之间不存在一条端到端的完整路径,消息是通过节点移动并与其他若干节点相遇进行存储、携带、转发。社区模型的机会网络,是指由具有社会属性的个体所携带的短距离通信设备组网而成的机会网络。由于携带者之间的社会关系存在一定的依赖性,相对稳定,因此,这种机会网络会出现节点聚集的现象,从而形成社区。节点在社区内移动相对缓慢,节点相遇频繁,但不同社区间的节点连接比较稀疏,个别节点相对活跃,经常往返于不同社区之间。

1 相关工作

机会网络中典型的路由算法,如Epidemic[2],Spray and Wait[3],Spray and Focus[4],Prophet[5]等,基本思想都是增加消息的拷贝份数,从而提高消息传输的成功率。然而,社区模型下,节点的运动具有一定的规律,根据其规律性来考虑消息的拷贝份数和转发时机,可以有效降低消息传输的延迟和网络资源的开销。

文献[6]提出了一种用于延迟容忍网络的、基于社区的消息传递算法,其基本思想是根据节点的活跃度对节点进行社区内的排名和整个网络的全局排名。当源节点发送消息时,在相遇的节点中寻找全局排名比自己大的节点进行社区间的转发,直到将消息传递到目标社区内的节点,由后者根据社区内排名进行传输,直到遇到目标节点为止。算法利用社会关系进行消息传输,提高了消息传输成功的概率,但是,该算法采用的是单消息拷贝策略,消息传输延迟较大。

文献[7]提出了一种基于社区模型的机会网络消息传输算法。算法根据节点接触的频繁程度,将所有节点划分到不同的社区。社区内,根据节点的平均相遇时间间隔来确定消息的拷贝份数和转发时机;社区间,依靠相对活跃节点的移动来进行消息的传输。该算法还考虑了过期拷贝的删除机制,有效降低了网络负担。但是,该算法的社区模型与真实社会的移动规律还有差距,并且,该算法节点活跃度的计算只考虑了节点的相遇历史情况,这使得消息投递成功的概率较低。

文献[8]提出了一种CSB算法,该算法和文献[7]基本类似,但在对社区间的消息进行转发时,引入了特殊节点的概念,即新加入本社区的节点,认为这些节点会与原社区的一些节点保持密切的联系,因此本社区节点可以借助这些特殊节点与原社区进行消息传递。

在对以上工作研究的基础上,改进了现有的社区模型,使之更加符合真实社会移动规律,并设计了新的社区间和社区内的路由算法,提高了消息投递的成功率,有效降低网络资源的消耗。

2 基于节点回归的社区模型

真实社会中,节点除了具备聚集现象外,往往会带有一定的回归性。基于这种规律,改进了现有的社区模型:

(1)设节点集为一个社会C,分为若干社区Di,一个节点只允许属于一个社区Di。

(2)节点在社区内的移动采用随机目标点模型。

(3)节点具有一个社会度属性(<1),表征节点本次移动离开家乡社区进入其他社区的概率。

(4)节点具有活跃度向量属性T,Tij表示节点ni和nj之间的相遇属性,Tij越大,表示ni和nj之间越容易相遇。

(5)设置社区向量V,Vi记录了节点s遇到的处于社区Di中的节点数。

(6)设归属阈值Ths,若节点s记录的Vi>Ths,则认为节点s到达社区Di一次,并且清除V。

(7)设吸引力向量Att,Atti表征了节点s对非家乡社区Di的趋向度,Atti越大,节点s越倾向于将Di作为下一个目标社区,初始化时所有节点的吸引力向量为0,节点s到达过Di后,则Atti++。

(8)当节点要离开家乡社区时,以80%的概率选择吸引力最大的社区作为移动目标社区,以20%的概率随机选择目标社区,节点到达目标社区后随机选取目标社区中的一个位置作为目的地。

(9)节点移动到目的地后,随机停留一段时间,然后以80%的概率选择回归家乡社区,以10%的概率用吸引力来选择下个目标社区,以10%的概率随机选择下个目标社区。

(10)设置节点回归规则,在规定的周期时间tback点,所有节点停止当前的活动,以90%的概率回归家乡社区,10%的概率留在当前社区。停留tsleep时间后,节点重新选择是否移动以及移动的目标社区,正常运行。

模型工作前采用文献[9]提出的G-N社区发现算法进行社区的划分。

3 消息传递算法

社区模型的消息传递分为社区内和社区间的传递,分别采用不同的路由算法实现。

3.1 社区内路由算法

适当增加消息拷贝数量,合理控制消息转发时机和转发时消息拷贝数量的分配,能够提高消息投递的成功率,降低网络资源的消耗。因此算法采用多拷贝加转发限制的规则,首先确定消息的拷贝份数,然后在节点相遇、消息传递的过程中,将消息按活跃度的比例进行消息拷贝份数的分配,直到遇到目标节点后删除消息的拷贝。

首先,当有消息产生并需要转发时,产生L份拷贝,由式(1)算出

$L=\frac{\text{E}\text{Μ}{}_{\text{o}\text{p}\text{t}}}{\text{E}\text{Μ}{}_{\text{r}\text{w}\text{p}}}(1)$

其中EMopt表示最优消息传输延迟,即消息按理论上的最优路径到达目标节点的传输延迟;EMrwp表示社区内节点的平均相遇时间。通过式(1)可以看出,拷贝份数等于最优传输延迟内社区中节点相遇的次数,这就保证了节点相遇时,即使每次都需要进行一次消息的拷贝,拷贝份数最多也只是最优消息传输延迟内所有节点相遇过的次数,即每个相遇节点都只保存了一份消息拷贝,从而减少了网络的开销。

EMopt的计算方法如式(2)所示[10]

$\text{E}\text{Μ}{}_{\text{o}\text{p}\text{t}}=\frac{C{\rm N}\log {}_2{\rm N}}{2({\rm M}-1)\overline{V}{\rm K}}(2)$

式(2)中,C为经验常数;文献[10]设定为0.34,N表示社区的面积;M表示社区内节点的数量;$\overline{V}$表示节点的平均移动速度;K表示节点的无线射频覆盖范围。

EMrwp的计算方法如式(3)所示[10]

$\text{E}\text{Μ}{}_{\text{r}\text{w}\text{p}}=\frac{1}{pm\overline{V}+2(1-pm)}\frac{{\rm N}}{2{\rm K}\overline{D}}(\overline{{\rm T}}+\overline{{\rm T}}{}_{\text{s}\text{t}\text{o}\text{p}})(3)$

$pm=\frac{\overline{{\rm T}}}{\overline{{\rm T}}+\overline{{\rm T}}{}_{\text{s}\text{t}\text{o}\text{p}}}(4)$

其中,$\overline{{\rm T}}$表示节点平均移动时间;$\overline{{\rm T}}{}_{stop}$表示节点平均停留时间;$\overline{D}$表示节点在一次移动过程中的平均移动距离;$\overline{V}$、N和K同式(2)一致。

此后,当消息携带节点ns移动并与nm相遇时,若nm非目标节点,则利用节点活跃度作为转发时机的判断条件:若ns的活跃度低于nm,认为转发时机成熟,将消息的一部分交由nm进行转发,否则,不进行消息转发。

节点活跃度的确定。首先,如果消息由与目标节点接触频率大的节点进行转发,则消息投递成功率也就大。其次,若一个节点比较活跃,经常遇到社区内其他节点,那么这个节点可以提高消息投递成功率。针对后者,以节点转发消息量作为度量。将以上两个因素作为正反馈效应体现在活跃度的计算中,节点活跃度的计算公式如下

${\rm T}{}_{ij}=\frac{C{}_{i}E{}_{ij}}{{\rm T}{}_{\text{n}\text{e}\text{t}}}+\frac{(1-C{}_i){\rm P}{}_i}{{\rm T}{}_{\text{n}\text{e}\text{t}}}(5)$

其中,Tij表示节点ni到节点nj的活跃度;Tnet表示到目前为止网络运行的时间;Eij表示在Tnet内,节点ni和节点nj相遇的次数;Pi表示在Tnet内,节点ni转发过的消息数量;Ci是经验常数,用来调节节点相遇频率和节点转发过的消息数量这两个因素的比例,这里设定为0.7。Tij越大,表明单位时间内ni与nj相遇的次数越多,并且ni转发过的消息数量越多,即节点i越活跃,其活跃度越高。

社区内消息转发算法如下:

(1)消息源节点ns产生一条到nt的消息,并根据式(1)确定消息的拷贝份数L${}_s^0$,L${}_s^k$表示ns将携带的消息转发过k次后剩余的拷贝数量。

(2)当消息携带节点ni与nj相遇时,若L${}_i^k$>1,nj没有该消息的拷贝,且Tjt>Tit,则ni将该消息复制一份给nj,令$L{}_i^{k+1}=\lfloor L{}_i^k\left(\frac{{\rm T}{}_{it}}{{\rm T}{}_{it}+{\rm T}{}_{jt}}\right)\rfloor ,L{}_j^0=L{}_i^k-L{}_i^{k+1}$。

(3)若L${}_i^k$=1,nj无该消息的拷贝,且Tjt>Tit,则将该消息复制一份给nj,令L${}_j^0$=1,删除ni上该消息的拷贝。

(4)其余情况不转发该消息,直至遇到目标节点,将消息转发给目标节点,并删除本节点上该消息的拷贝。

选取到目标节点的活跃度高的节点转发消息,可以降低消息转发的次数,从而减少网络的开销。在延迟要求相对宽松的机会网络中,可以权衡资源消耗和网络性能之间的关系,在降低网络资源消耗的同时,提高消息传输的成功率。

3.2社区间路由算法

社区间的路由分为两个阶段,首先是找寻目标社区,然后是在目标社区中,找寻目标节点,其中第二阶段由上述方法给出。社区间的消息传输,在查询社区间路由表的基础上,结合判断节点回归的因素。本社区内经常往返于其他社区的节点活动频繁,可以作为社区的桥接节点,来进行社区间消息的转发。为控制网络的开销,在社区间进行传输的消息也需设置一个最大拷贝份数,本文取当前网络中的社区个数C为消息的最大拷贝份数,在最坏的情况下,每个社区有且只有消息的一份拷贝,从而减小了社区间多余的消息拷贝。路由表的结构如表1所示。

表1中,吸引力是对该桥接节点而言的,按照上述社区模型中的规则进行计算,吸引力越大,表明该桥接节点到达目标社区的概率越高。

在基于回归的社区模型下,社区间消息传输的算法如下:

(1)消息源节点ns产生一条消息,确定消息的社区间拷贝份数C,查询路由表。

(2)找到一条社区号与目标社区相同,并且吸引力最高的路由信息,确定桥接节点nb。

(3)将消息在社区内传输,目标节点为nb,消息到达nb后,由nb负责将消息传输到目标社区。

(4)消息携带者ni在寻找nb的过程中,假设ni的社区间消息拷贝份数为L${}_i^k$,若相遇节点nj属于目标社区,则将消息复制一份给nj,并进行判断:若当前时间距离节点回归时间tback大于时间阈值tbback,设置nj该消息的拷贝份数为1,ni的拷贝份数为L${}_i^k$-1;否则设置nj的拷贝份数为L${}_i^k$,删除ni该消息的拷贝。tbback的大小人为设定。当到达时间截点tback时,所有节点将以90%的概率回归家乡社区,此时,选择由即将回归家乡社区的节点将消息带回目标社区,消息传输成功概率比由桥接节点转发消息到目标社区的成功概率大很多。

(5)消息到达目标社区后,采用社区内路由算法进行消息的传输。

3.3 缓存管理机制

对于已经到达的消息,或已经超过其生存周期TTL的消息,文中采用一种文献[11]中描述的缓存管理机制,用来管理系统中过时的消息。

4 仿真及性能评价

本文采用基于Java的DTN仿真工具ONE[12](Opportunistic Network Environment)进行算法性能的仿真,与机会网络的典型算法Epidemic以及现有的基于社区的机会网络路由算法CMTS进行比较。

4.1 仿真环境参数设置

仿真开始时,由于要收集节点相遇信息,所以系统先运行10 min,节点社会度随机生成,tback设置为60 min,tbback设置为10 min,tsleep设置为60 min,Ths设置为20,设置节点的最大缓存消息个数为10个,场景采用ONE中默认的城市地图,主要配置参数如表2所示。

4.2 仿真结果分析

从图1中可以看出,随着TTL的增加,各算法的消息传输成功率不断提升。Epidemic采用洪范的机制,当TTL足够大时,其消息传输成功率接近1。NBR消息传输成功率比CMTS高,这是因为在更加准确地定义了节点移动模型并且重新设计了相应的路由算法后,社区内和社区间的消息传输成功率有所提高,从而使整个网络的消息传输成功率得到了提升。

如图2所示,随着节点最大移动速度的增加,消息传输延迟明显降低。由于Epidemic采用的是洪范的消息传输策略,所以在相同的节点移动速率下,其消息传输延迟最低。NBR的消息传输延迟较CMTS算法低,由于节点会在固定的时刻回归家乡社区,这就使得消息在一定时间内,会以较高的概率到达目标社区,从而降低了消息传输延迟[13,14]。

如图3所示,在相同的TTL时,Epidemic算法中缓存消息的平均个数最低,NBR算法的缓存中消息的平均个数较CMTS低,这是由于系统的缓存管理机制会删除已经投递成功的消息的拷贝,随着消息投递成功率的提高,缓存中已经投递成功的消息会被大量的删除,因此,消息投递成功率越高则缓存中消息的平均个数就越少,所以,结果表明NBR算法较CMTS算法投递成功率高。但随着TTL的增大,消息的存活时间得到了延长,所以缓存中消息的平均个数随之增高[15,16]。

5 结束语

对社区模型下机会网络中节点的移动规则和路由算法进行了研究,提出了一种更加符合现实社会移动规律的节点移动模型,并在该模型下提出了一种社区间和社区内的路由算法NBR。该算法在充分考虑现实可能性的情况下,有效提高了消息传输的成功率,减小了消息传输时延,并且对网络内的冗余消息进行了处理,从而减少了网络资源的消耗,提高了网络的性能。

摘要：当前,基于社区的机会网络研究在模型上还有待完善,在社区间的路由算法没有考虑消息的传输效率,只采用简单的分发等待路由算法,使得路由效率较低。为此,对社区模型进行了改进,加入节点回归因素,并在此模型下提出了新的路由算法NBR。在社区内采用混合路由算法,并加入了正反馈思想重新计算节点活跃度。在社区间采用查询路由表和判断节点回归相结合的方法,利用节点回归的特性提高转发效率。仿真结果表明,在改进后的社区模型下,NBR算法使得社区间和社区内的消息传输成功率得到了提升,有效的降低了网络资源的消耗。

关键词：机会网络,社区模型,路由算法,网络效率

浅谈机会网络路由算法 篇2

机会网络是一种不需要在源节点和目标节点之间存在完整连通路径, 利用节点移动带来的相遇机会实现通信的时延和断裂可容忍的自组织网络[1]。在机会网络中, 节点之间的链路经常间歇性的中断且这种中断一般持续时间较长, 以至于在任何时刻源节点和目标节点之间可能一直不存在连通的路径。

很明显, 机会网络和现有的常用的网络不同, 它具有以下特性:

(1) 低数据传输速率、高延迟 (2) 网络断开 (Network disconnection) (3) 长排队时间。正是由于这些特性, 使得传统的存储—转发模式不适合于机会网络, 在机会网络中要采用存储—携带—转发模式来进行通信。

2、机会网络路由算法

路由问题是任何组网技术的首要问题。机会网络的路由问题更是机会网络中的研究重点。现有常用的网络路由协议中都是假设在源节点和目标节点之间至少存在一条完整的通信路径, 所以不适合在机会网络中运行。机会网络中的路由转发机制是以“存储—携带—转发” (Store-CarryForwarding) 的模式工作。要设计出高效机会网络路由协议的关键问题在于如何针对每个消息来找出最好的下一跳转发节点和何时进行数据转发。良好的路由算法能提高报文传输的成功概率, 降低传输延迟, 减少能量的消耗。

人们针对不同类型的机会网络提出了各式各样的路由算法。目前现有机会网络路由算法主要有以下几类:

2.1 基于复制的转发算法

在基于复制的路由转发机制中, 一条消息会有多份拷贝被注入网络, 只要其中有一份拷贝被传送到目标节点, 这条消息则传输成功。然而, 它的核心问题在于消息拷贝数怎么确定才算合适以及怎样来产生消息拷贝。最简单的方法就是直接传输 (Direct Transmission, 简称DT) [2]方法, 即源节点直在和目标节点相遇时才进行数据转发, 这样做网络耗费是最小的, 但往往会传输延迟较大, 并且经常会因为源节点碰不到目标节点而造成传输失败, 其传输成功率最低。在源扩散Source Spray and Wait (SSW) 算法[3]中, 事先指定消息的最大拷贝数为L。源节点起始时拥有一个消息的L个拷贝, 源节点先将消息拷贝给最先遇到的L-1个中继节点, 然后源节点和中继节点只在遇到目标节点时才进行转发。

2.2 基于编码的转发算法

这类机制中, 会把要传输的数据先编码成互相冗余的消息, 目标节点接收到编码后的一部分消息, 就能够通过一定的运算来重组原始数据。在Ling-Jyh[4]等人提出的H-EC中, 针对每个编码后的小消息会生成两个拷贝。当遇见邻居节点的时候, 首先会将消息的第l份拷贝传递给该邻居节点, 然后会在该连接持续的时间内, 将其他消息的第2份拷贝传输给该节点。该机制因为充分利用了所有的连接机会所以传输性能更好。

2.3 基于相遇预测的转发算法

根据对历史概率进行统计, 每个节点都具有一个与目标节点相遇的概率, 人们也可以通过节点的历史移动来预测该概率值。在节点移动过程中每个节点选择与目标节点相遇的概率值更高的节点作为转发的中继节点, 这就是基于相遇预测的机会转发机制。比如Seek and Focus[5]协议中, 针对每一个节点, 当前节点都会记录下自上次相遇之后所经历的时间, 并据此来估计节点间的相遇概率值。此外, 节点间的相遇概率还可以根据节点的位置和节点的运动方向来进行估计。

2.4 基于链路估计的转发算法

基于链路估计的机会转发机制在选择转发节点时则根据节点之间的“端到端”的链路状态。在机会网络中是否转发可以依照根据收集到的单跳链路状态进行估算得出的端到端路径的效用值。在最短期望路径路由 (Shortest Expected Path Routing Protocol) [6]中, 利用节点所维护的到达已知节点的链路效用值也即链路可用概率值。再通过Dijkstra算法计算出当前节点与目标节点之间的最短路径。

2.5 冗余效用混合转发算法

冗余效用混合转发机制结合了并行传输和基于效用的转发决策的优点来提高传输的性能。PROPHET (Probabilistic Routing Protocol Using History of Encounters and Transitivity) [7]就是综合了传染转发和基于相遇预测转发二者的优点。在PROPHET中, 每个节点都维护着对网络中其它节点的一个效用值, 在转发过程中会根据节点对消息的目的节点的效用值来选择是否进行转发。只是在PROPHET中概率效用值的更新使用了概率的传递性, 即如果节点a有可能遇到节点b, 而节点b又有可能遇到节点c时, 则认为节点a也可以成为目标节点为c的消息的转发节点。当节点相遇的时候, PROPHET会将消息传输给那些到达目标节点的概率比自身高并且没有存储该消息的节点, 从而降低了传染转发中因为广播消息引起拥塞而导致的性能下降。

2.6 基于节点主动运动的转发算法

当网络中拓扑变化或因节点稀疏而存在较强的随机性时, 以上所介绍的机会转发机制都因为被动等待与更好的转发节点相遇, 而造成传输成功率降低或者传输时延增大。在基于节点主动移动的转发机制中, 有一部分特殊的节点可以通过自身的主动移动, 为其他的普通节点提供通信服务。DataMULEs系统[8]即是通过引入移动节点从而实现稀疏传感器网络中的数据收集。

3、结语

机会网络路由是一个富有挑战性的问题, 它要求对路径选择、评估传递性能、缓存管理和调度传输等多种技术来综合考虑。而目前的各种机会路由技术还存在一些关键的问题需要解决, 可以预见, 未来对于机会网络路由问题的研究可能会致力于实际应用的考虑, 使机会网络得到更大范围的应用。

摘要：随着传感技术、嵌入式技术、无线通信技术、高性能计算等相关领域的迅猛发展, 以物联网为代表的新一代的智能互联网络应运而生。出现了一种新的基于机会转发的路由技术, 使用该技术的网络, 称为机会网络。本文主要介绍了机会网络的概念和理论基础, 并分析比较了当前机会网络的一些较为重要的路由算法。

关键词：机会网络,路由,路由算法

参考文献

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

[2]肖明军, 黄刘生.容迟网络路由算法[J].计算机研究与发展, 2009, 46 (7) :1065-1073.

[3]spyropoulos T, Psounis k, Raghavendra CS.Spray andwait:An efficient routing scheme for intermittently connect-ed mobile networks[C].In:Proc.of the 2005 ACM SIG-COMM Workshop on Delay-Tolerant Networking.Philadelphia:ACM, 2005, 252-259.

[4]Chen L, Yu C, Sun T, Chen YC, Chu HH.A hybrid rout-ing approach for opportunistic networks[C].In:Proc.of the2006 SIGCOMM Workshop on Challenged Networks.Pisa:ACM, 2006, 213-220.

[5]Spyropoulos T, Psounis K, Raghavendra C.Single-Copyrouting in intermittently connected mobile networks[C].In:Proc.of the 2004 1st Annual IEEE Communications SocietyConf.on Sensor and Ad Hoc Communications and Net-works.2004, 235-244.

[6]Tan K, Zhang Q, Zhu W.Shortest path routing in partial-ly connected ad hoc networks[J].In:Global Telecommunica-tions Conf.the GLOBECOM 2003, Vol.2, 2003, 1038-1042.

[7]Lindgren A, Doria A, Schelen O.Probabilistic routing inintermittently connected networks[J].ACM SIGMOBILEMobile Computing and Communications Review, 2003, 7 (3) :19-20.

社区机会网络路由性能提升策略 篇3

机会网络具有高延迟、低数据率、缺少端到端路径、能量和缓存受限等特点, 这使得路由设计成为机会网络中的关键问题。机会网络中路由研究的主要成果按网络中存在的副本数可分为两类:单副本路由和多副本路由。其中具有代表性的单副本路由为第一次接触路由 (First Contact routing) ;具有代表性的多副本路由为传染路由[4] (Epidemic routing) 。然而由于链路间断、节点缓存和能量受限等原因, 多副本路由虽然可以提高网络的投递率, 但是它同时会增加网络的时延、开销、跳数等, 而单副本路由虽然可以减小网络的时延、开销, 但是其投递率较低, 由此可知副本数的多少将直接影响到网络的性能。

由于地理环境或社会关系的影响, 人们活动的规律往往具有区域性特点, 而由人随身携带的具有无线短距离通信能力的智能设备组成了基于社会性的社区机会网络[5]。在这种网络结构中, 由于人们活动规律的稳定性, 网络中的节点往往呈现出聚集的现象, 也就是说形成了不同的社区。社区中的大部分节点通常只在本社区内活动, 而只有少数的节点穿梭于不同的社区中, 因此这部分相对活跃的节点更适合进行消息的传输, 把这些节点定义为中心节点。在社区机会网络的研究中, Hui等人通过设置社区节点的等级来选择中心节点, 并且由中心节点进行数据的传输[6]。Daly等人采用相似性方法来检测社区中的节点, 他根据两个节点间最短路径的中心性来确定社区中的中心节点[7]。Cputa等人提出了一种基于最大连接度算法 (Highest Connectivity Cluster Algorithm, HCCA) , 该算法通过周期性选取连接度大的节点作为中心节点的方式来划分社区[8]。在上述所有社区中心节点的选取过程中并没有把节点的缓存、带宽、能量、通信范围等属性考虑进去, 而在机会网络中, 节点的属性能直接影响到网络的性能。鉴于上述分析, 本文提出一种结合节点属性与节点中心性的路由算法WRACS来改善网络的性能。在介绍该算法之前, 首先了解下社区机会网络的特点。

1 社区机会网络的特点

根据个体的运动规律可以把人活动的区域划分为许多个社区, 这些社区中具有无线通信能力的设备所组成的社区机会网络往往具有区域性的特点, 也就是说网络中的节点有唯一归属的社区。在社区机会网络中, 根据节点运动过程所处社区的不同可以将它们分为两种状态, 即本地状态和漫游状态。当节点处于漫游状态时, 那么它会以较大的概率回到原来的社区中, 而处于本社区的节点往往会以较小的概率离开本社区, 也就是说留在本社区的概率很大。社区中的大多数节点只在本社区内运动, 往往与本社区中的成员保持相对密切的联系, 而与其他社区中的节点联系较少, 处于同一社区中的节点由于分工和职能的不同, 其移动模式也有很大的差异性。有些节点由于移动相对活跃, 接触别的社区的机会也较大, 因此这部分节点也就更适合进行消息的传递, 把这部分节点看成中心性更高的节点。例如出租车司机或警察与普通群众相比往往会接触更多的人, 因此他们也就具有较强传递信息的能力, 也就是说中心性级别更高。

基于上述节点中心性的分析, 可以把现实中的网络场景抽象为许多不同的社区 (见图1) 。假设社区1中的人要与社区4中的人进行通信, 由于社区中的节点往往与本社区的节点接触得较为频繁而与其他社区的节点接触较少, 因此要达到通信的目的, 它需要通过中心性较高的其他节点进行中继转发, 如图1中节点C是可以联系其他社区的具有较强中心性的节点, 这样不同的社区之间就可以实现通信。

2 算法的选用及优化

2.1 喷射等待路由

Spray and Wait[9,10,11]路由分为两个阶段:喷射 (Spray) 和等待 (Wait) 阶段。在喷射阶段, 消息在源节点中共生成N个相同的副本, 这些副本将由源节点或中继节点传送到目的地;在等待阶段, 如果目的地在喷射阶段没有被发现, 消息将通过直接传输的方式到达目的节点。

Spray and Wait路由算法有两种模式, 分别为源喷射等待路由模式和二分喷射等待路由模式。在源喷射等待路由模式下, 源节点将N个消息副本转发给其最初遇到的N个不同节点, 此扩散方法完全由源节点完成, 扩散速度较慢, 并且源喷射等待路由最多只有两跳, 可靠性也不高。而在二分喷射等待路由模式中, 源节点在开始阶段产生N个副本, 在遇到没有副本的中继节点时将传递一半的副本给当前的节点, 随后源节点和中继节点继续以二分的方式传播, 在节点只有一个消息副本时进入Wait阶段, 在遇到目的节点时直接传输给目的地。

Spray and Wait路由算法通过限制消息的副本数来改善传染路由协议的过分冗余, 其网络的负载远远小于传染路由, 其优点是信息的投递率较高、时延较小, 无论网络的复杂度如何都能够保持稳定的网络性能。但是由于节点运动的区域局限性, 大部分节点往往只在某一个社区内活动, 这时大部分的副本只能扩散到源节点附近, 当源节点与目的节点处在不同的社区时消息的投递率很低。为了解决这个问题, 本文提出了一种适合于社区机会网络的路由算法WRACS, 该算法结合节点的缓存、带宽、能量、通信范围等属性与节点的中心性特性来进行副本的分配。在消息的传输过程中, 若携带有消息副本的源节点或中继节点在扩散过程中遇到一个没有携带此消息且中心性比自己高的节点, 则按照WRACS算法将此消息的大部分副本扩散给该节点, 从而扩大扩散的范围。由于中心性较高的中继节点在一定程度上更加活跃, 遇到目的节点的概率更大, 时延较小, 因此该路由方案能提高消息的交付比率并减小延时, 这在一定程度上改善了喷射等待算法的性能, 下面将详细介绍改进的喷射等待算法。

2.2 WRACS算法

在Freeman[12]分析节点中心性的多种方法中, 本文采用式 (1) 来表示节点的中心性, 其中n为社区中总的节点数目, 若在时间t内节点i与节点j接触, 那么at (i, j) =1, 反之at (i, j) =0。与节点i相邻的节点总数小于等于n-1, 因此Ci≤1。

在定义了节点的中心性之后, 就可以利用中心性级别较高的节点进行消息的中继, 但是节点中心性的高低并不能直接决定中继效果的好坏, 往往中心节点本身的属性 (带宽、缓存、能量等) 值也是需要特别关注的因素。假设一个中心性较高的节点, 它的缓存、能量受限, 那么它也并不是中继节点的最好选择。因此如何在多个备选的中心节点中进行选择, 以达到最优化的效果是一个关键的问题, 为了解决这个问题。本文引入了多属性决策[13] (MADM) 思想来进行中心节点的选择。通过该理论思想, 能够以一种优化的方法来分配权值以区分感兴趣的属性, 其可简单的表述如下:

1) X= (X1, X2, X3, X4, …, XK) , 表示K个所感兴趣的属性。

2) ε= (ε1, ε2, ε3, ε4, …, εK) , 表示K个属性对应的权值, 其中。

WRACS算法分为扩散和等待两个阶段。在上面的网络模型中, 社区1中的节点S要与社区4中的节点D进行消息M的传递。假设在此时携带消息M的节点A与节点B相遇, 副本数为N, 则有:

1) 若N=1, 则节点A进入等待阶段。节点A缓存消息M直到和目的节点D相遇, 将M交付给D。

2) 若1

通过副本的分配, 节点A将消息M扩散给没有携带此消息的下一跳节点B, 或在扩散过程中直接将消息M交付给目的节点D。

在机会网络中, 节点的资源是非常宝贵的, 它们的缓存、能量、带宽等属性值将直接影响到网络的性能, 因此该算法在比较节点中心性高低的同时, 也充分考虑到了节点属性对网络性能的影响。WRACS算法原理如图2所示。

WRACS算法的伪代码描述如下:

3 仿真及结果分析

3.1 参数设置

为了模拟所提出的路由算法WRACS在真实网络环境下的性能, 本文采用ONE[14] (Opportunistic Network Environment) 仿真工具对其进行仿真, 所涉及的相关参数定义如表1所示。

仿真中主要对以下3种性能参数进行评估:

1) 投递率, 即投递成功的消息与总的消息之间的比值。

2) 平均时延, 即投递成功的消息从源端到目的端的时间之和与总的投递成功消息个数之比。

3) 平均缓存时间, 即所有消息在网络中占用缓存的时间与消息个数的比值。

3.2 仿真结果与分析

从图3中可以看出, WRACS的投递率一直比其他两种要高, 这是因为在消息副本的扩散过程中, WRACS采用的是多属性分配副本的方式, 这在缓存、能量、带宽非常有限的机会网络中是一个能直接影响到网络投递率的关键因素。当副本数为2时, 3种路由方式的投递率相差不大, 这是因为当副本数较小时, 网络的负载也较小, 同时副本再分配也受到一定的局限性, 中心性节点副本的再分配往往很小, 因此投递率相差不是很大;而在副本数为6时, 因为中心性节点副本的多属性分配方式, WRACS路由算法明显优于其他两种路由算法, 这主要是由于中心性节点分配副本方式的不同, WRACS路由算法在带宽、缓存、能量等多重因素影响下进行了副本再分配的原因。

从图4中可以看出, 3种路由算法随着消息副本数的不断增大, 平均时延不断减小。这是因为在机会网络中, 消息副本数越多, 消息能到达目的节点的概率也就越大, 在一定时间内, 成功到达目的地的副本数增加, 因此平均时延也就越低。在WRACS算法中随着副本数的增加, 平均时延减小的趋势越来越小, 直到趋于一个平稳值, 这是因为网络的中心性节点的数目是非常有限的, 当副本数不断增加时, 由于中心性节点携带副本使消息到达目的节点的时间越来越短;当副本数增加到一定的数量时, 中心性节点几乎都进行了副本的再次分配, 因此继续增加副本的数量对网络的平均延时没有太大的影响。在WRACS路由算法中同理, 由于充分考虑了影响机会网络传输效率的多种属性, 进行了副本的再分配, 因此传输效率较高, 平均时延比其他两种路由算法相对较低。

从图5中可以看出, 相对于其他两种路由算法, WRACS路由算法的平均缓存时间最低, 也就是说对缓存资源的占用最小, 这是因为WRACS路由协议副本再分配上与其他两种路由算法不一样;随着副本数的不断增大, 3种路由协议的平均缓存时间都不断减小, 这是因为副本数目越多, 中心性节点得到副本的机会越大, 消息也就越容易到达目的节点, 因此平均缓存时间越来越小。

4 小结

机会网络是一种缓存、带宽、能量严格受限的网络, 其属性值的大小将直接影响到网络的性能, 本文把网络场景划分为不同的社区, 通过节点的中心性与多属性共同作用来决定副本的再次分配以达到优化网络的性能。最后通过ONE仿真软件对3种不同的路由算法进行仿真验证。仿真结果表明, 本文提出的算法较其他两种算法能够提高信息的投递率, 减少传输时延及平均缓存时间。在未来的工作中, 将深入分析中心性节点的活动规律, 并把合作机制引入到中心性节点中进行分析验证。

摘要：在社区机会网络中由于网络资源的限制, 节点的缓存、能量、带宽等属性会严重影响网络的性能。现有的社区机会网络路由算法往往只根据节点的中心性级别来进行副本的分配, 而并没有充分考虑上述属性的影响。针对这一问题, 提出一种结合节点属性与中心性的路由算法WRACS。该路由算法既考虑了影响节点传输能力的各种属性, 又结合了节点的活跃程度。最后通过ONE仿真分析可知, 该算法在信息投递率、平均延时和平均缓存时间等性能指标上都体现出良好的性能。

机会网络路由 篇4

车载自组织网络作为一种特殊的移动自组织网, 不仅面临一般无线自组织网络已有的挑战[1],同时其自身网络的特性也面临诸如车辆移动性高、拓扑变化快、车辆地理位置以及移动方向受限等问题。 这些问题造成了事先建立端到端路由路径的传统单播路由协议并不能很好适应复杂的城市环境。而在该无线环境下,利用了无线信道天然广播特性的机会转发策略能够有效提升单跳路由的转发性能,从而显著提升端到端的路由性能。

已有的机会转发研究[2,3]通过数据包迭代的方式来计算最优转发节点,这在拓扑高速变化的街道会带来很大的开销。本文提出一种只需单跳邻居动态信息的机会路由协议,该协议考虑了多个影响路由性能的要素,从而设计合理的转发优先级。为了进一步优化性能,本文针对车辆的移动性对发送车辆候选集进行了优化。

1候选集选择

考虑城市环境下车辆高速移动性,定义两车在时间内的链路可用概率如下:

其中和分别表示车辆Vs和Vr在T 时间后的欧拉距离以及相对速度,T的取值依赖于路由协议邻居信息的刷新时间。假设街道内相同行驶方向的车辆其速度服从高斯分布[4],则两车相对速度∆vsr也服从高斯分布, f （∆vsr）为其概率密度函数。Rsrd余可持续传输距离,其值将根据以下情况来确定。

情况一:两车具备相同的行驶方向。

情况二:两车具备不同的行驶方向。

在机会转发策略中,候选集的大小对路由性能有着至关重要的影响。当数据包被转发时,它会被以广播的形式发送至候选集中的车辆。只有在发送车辆候选集中的车辆才能有机会被最终选择为转发车辆。虽然更大的候选集可以提高单跳的数据包投递率,但是该候选集也会包含更多更小地理前进的车辆,从而潜在造成路由性能下降的可能。因此车辆的运动状态和所处位置需要满足以下两条规则:

规则一:只有当链路可用概率大于一定的阈值时,车辆才会被纳入发送车辆的候选集。

规则二:候选集中的车辆必须比发送车辆具备更大的地理前进。

如图1所示,假设链路可用概率P lr的阈值为0.1, 发送车辆Vs的邻居车辆Ve由于规则一被排除,车辆Va和Vb由于规则二被排除。

2机会转发设计

当发送车辆进行数据转发时,首先检测当前无线信道是否空闲,如空闲则以广播的形式发送数据包进而取代原有的单播转发形式,否则执行相应的退避算法。收到数据包且满足一定转发条件的邻居车辆将分别设置等待计时器(wait-time timer),其配置的初始化将结合接收车辆自身以及发送车辆的情况来完成。等待计时器最先到期的车辆将以广播的形式继续转发该数据包,其余的接收车辆感知到其转发的数据包时将取消自己的等待计时器,并且丢弃该已收到的数据包。本节将对影响路由性能的三个要素对等待计时器进行设计。

2.1街道内地理前进

接收车辆Vr对于发送车辆Vs的地理前进距离为Dr,其定义如下:

其中ds ,s tr ee t和dr, st re e t表示发送车辆Vs和接收车辆Vs沿发送方向到达当前街道的街道口距离。沿发送方向街道口更近的接收车辆拥有更大的地理前进距离,但是需要注意的是本节所有统计地理前进距离采用的目的地并不是诸如GPSR[5]等地理路由协议中使用的数据包目的车辆。这样做可以避免路由协议在街道内遇到的局部最大值(local maximum)问题[5]。

2.2平均缓冲区队列长度

街道内车辆缓冲区队列的状态对路由性能起着至关重要的影响。如果数据包被发送至一个已经具有更多数据包缓存的车辆,这势必会带来额外的排队时延。同时数据包引导的不合理也会导致数据包在某些特定的车辆造成堆积,导致缓冲区溢出丢包。 所以平均缓冲区队列长度将作为衡量一个车辆数据负载程度的重要指标。车辆Vr平均缓冲区队列长度计算如下:

其中Q l e nr代表车辆在采样时刻平滑后的缓冲区队列平均长度。 Q l e nold代表了车辆上一时刻所维护的历史缓冲区队列平均长度,Q l e ncurrent代表了车辆在采样时间时的瞬时缓冲区队列长度。α的值域为[0,1], α的值越大表示路由策略更关注缓冲区队列的历史信息。

2.3平均竞争窗口大小

当前竞争窗口的大小在一定程度上能够反映当前车辆所处的无线信道环境以及自身的数据流量特征[5]。 关于车辆Vr平均竞争窗口CW大小的计算如下:

其中C Wr代表车辆Vr在采样时刻平滑后的平均竞争窗口大小。 C Wold代表了车辆上一时刻所维护的历史平均竞争窗口大小, C Wc u r r e nt代表车辆在采样时间时的瞬时竞争窗口大小。β的值域为[0,1],β的值越大表示路由策略更关注竞争创窗口的历史信息。

2.4多路由度量等待计时器设计

本节将考虑上述三个路由度量来初始化车辆的等待计时器,具有更高优先转发权的邻居车辆具有更小的等待时间,其初始值设置的函数如下:

其中Dr(max)、Q l e nr(max)和C Wr(max)分别为最大地理前进(通信半径)、最大缓冲队列长度和最大竞争窗口大小。 αi( i = 1 , 2 , 3)为三个路由度量的权重 ,Tmax为最大等待时间。因此公式7返回一个不大于Tmax的等待时间,各邻居车辆根据其计算的结果设置自身的等待计时器,从而分布式的决定各个邻居车辆的转发优先级。

2.5基于多路由度量的机会路由算法

数据包在街道内根据多路由度量执行机会转发策略,在街道口根据Dijkstra算法选取一条拥有转发车辆且处于最短路径中的街道作为下一条转发街道。 基于多路 由度量的 机会路由 协议O R P M(Opportunistic Routing Protocol based on Multi-metrics)如下:

3性能评测

为了评测ORPM协议的性能,本文在仿真软件NS-2中实现了另外两个路由协议GPSR[5]和LSGO[2]。 城市拓扑大小设置为2000m*2000m,车辆的初始化分布和行驶轨迹都被限制于街道内,车辆的行驶速度为30km/h至60km/h,通信半径为250m。随机选取10对CBR产生数据流量,仿真时间300s,图中所有数据都是10次实验的平均值。

图2是端到端时延的对比结果,ORPM在街道内考虑多路由度量作为车辆转发优先级的依据,该策略能够有效减少排队时延以及转发跳数,因此能够获得更小的端到端时延。

图3是数据包投递率的对比结果,ORPM使用机会转发策略,该策略利用了无线信道广播的特性, 从而提升了单跳的数据包投递率,获得更高的端到端数据据包包投投递递率率。 。

图3数据包投递率 (参见右栏)

图4路由开销 (参见右栏)

图4是路由开销的对比结果,其定义为全网控制数据包的总大小与目的车辆收到数据包总大小的比值。ORPM利用单跳邻居信息进行路由决策,能够有效控制网络中用于信息交换的控制数据包的总大小,因此具有最小的路由开销。

4结束语

本文提出了基于多路由度量的机会路由协议ORPM,该协议使用多路由度量确定候选集中车辆的转发优先级,指引数据包在街道内高效的传输。 实验表明ORPM在更低的路由开销情况下显著降低了端到端时延并提升了数据包投递率。

摘要：车载自组织网络面临车辆移动速度快、拓扑变化频繁等问题,而机会转发策略利用无线信道天然的广播特性相比于传统的确定性转发策略能更加有效应对复杂的城市环境。本文提出一种只需利用单跳邻居信息的多路由度量机会路由协议,该协议能够合理安排邻居车辆的转发优先级,同时根据车辆移动特性对候选集进行了进一步优化。仿真结果表明,本文所提出的路由协议能够显著提升单播路由性能。

关键词：车载自组织网络,机会路由,路由度量,候选集

参考文献

[1]Zhang X M,Zhang Y,Yan F.Interference-based Topology Control Algorithm for Delay-constrained[J].IEEE Transactions on Mobile Ad hoc Networks.2014,14(4):742-754.

[2]Cai X,He Y,Zhao C.LSGO:Link State aware Geographic Opportunistic routing protocol for VANETs[J].EURASIP Journal on Wireless Communications and Networking,2014(1):1-10.

[3]Dubois H,Grossglauser M.Least-cost opportunistic routing[R].Technical Report,2007.

[4]Eiza M H,Ni Q.An evolving graph-based reliable routing scheme for VANETs[J].IEEE Transactions on Vehicular Technology,2013,62(4):1493-1504.

[5]Karp B,Kung H T.GPSR:Greedy perimeter stateless routing for wireless networks[C].Proc.of ACM/IEEE Mobi Com&apos;00,2000:243-254.

机会网络路由 篇5

1 机会网络安全路由架构建设的必然性

所谓的机会网络,就是利用大家的各种社会活动所创造的机遇性机会对信息进行传输,其将网络断路当做一种常态,将每一次节点的移动都当做一次新的传输机会,即使面对再恶劣的环境也可以以完全颠覆传统网络的处理方式对数据进行处理,其概念来源极为广泛,与容迟网络、移动的自组织网络以及社会网络等都有着极为密切的关系。从当前社会网络的蓬勃发展来看,机会网络越来越广泛的的应用前景是毋庸置疑,尤其是低成本手持通信设备高速普及的今天,以日常生活中的移动对数据进行传输与共享极为普遍。

由于机会网络是一种公共通信设施,其网络建立在开放式的环境下,在其网络中进行上传或者接受等信息的传输时,随时都有遭受窃听、截取、修改、重放等方式攻击的威胁[2],而传统的网络公钥密码体制对公钥的约束较多,公钥的使用必然要先依赖于所谓的认证中心的可信第三方存在,统一由认证中心为用户颁发公钥证书。因此,公钥证书中认证中心的签名信息就将用户身份与看似随机的公钥信息紧密联系在了预期,所有用户身份与公钥一定要经过认证中心签名才是合法的,因而认证中心成为网络路由架构下的关键核心部门,对用户公钥证书的生命周期中任何一个环节都要负责。此类证书的使用不但耗费了巨大的计算与存储开销,管理工作比较纷繁复杂,而且处于系统中心地位的证书认证机构有着非常高的要求,系统负担极重,最重要的是对用户信息数据保密性不强,安全性存在极大的缺陷[3]。

由此可见,在机会网络中建立起以身份加密的安全路由架构,保护开放性环境下用户资料和数据的安全,是非常有必要的,也是当前信息化社会建设迫切需要解决的问题之一。

2 基于身份加密的机会网络安全路由架构的基本概况

在机会网络中,网路节点都是以“存储-携带-转发”的基本模式对所传输的消息进行路由,任意一个节点都需要通过自身具备的知识来进行计算,做出判断,选用最佳的路由策略。

机会网络根据转发策略的区别可以分为基于散播的路由、基于效用值的路由以及基于移动的路由等3种,其中,最受关注的要数以节点的社会上下文作为效用值,对转发策略进行制定的路由协议。运用移动通信设备携带者的社会属性(即,社会上下文)来预测节点的下一次相遇性机会,可以制定更有效的路由策略,通过身份加密的用户隐私保护策略则重点保护用户的社会上下文不暴露给更多不受信任的节点,保护用户隐私[3]。例如,当源节点NS要想目的节点ND发送消息M时,NS首先将ND的档案合并生成消息头Header(M),再发给2跳内的邻居节点,邻居节点会通过对比自身的档案消息与Header(M)的属性消息,得到匹配度再发回给NS,NS最终会选择匹配度较高的节点作为随后的2跳路由选择,如此推进,直到到达ND。

基于身份加密的机会网络安全路由架构通过关键字可搜索的加密算法为节点的社会上下文设置了相匹配的陷门,虽然中继节点仍然可以计算上下文匹配度、制定相应的转发策略,但是不会暴露任何源节点NS属性信息。同时,节点的社会上下文信息会合成相应的公钥对信息进行加密[4]。

基于身份加密的机会网络安全路由架构一方面对方案的安全模型进行建设,另一方面也对基于身份密码体制下的强指定验证者签名、签密、多签密、多接收者匿名签密以及面向群组的加密和签密、安全密钥分发协议等密码学方案的安全性定义与具体实现进行了重点的研究,方案甚至可以满足代理签名与强指定验证者签名情况的安全特性,可以有效的防止签名滥用与签名内容的泄露。

3 机会网络安全路由架构具体内容

3.1 基于IBE的安全路由算法

为了避免信息加密阶段因为身份证书的获取与验证带来不必要的麻烦,可以运用身份密码学架构,提供在节点与私钥间无交互通信的情况下实现的安全服务,本方案需要运用到高效可搜索的加密算法,该算法是IBE的一种变形,通过该算法为节点的属性生成陷门,为节点隐私提供保护,并通过节点的社会上下文生成公私钥数据对,保障消息的机密性和安全性;通过设置相关功能函数,分别对系统参数的初始化、陷门、密钥、消息头的生成以及信息的解密等进行处理[5]。如,设网络中的节点NX有m个社会属性,但是在每一个社会属性下又要设计一些相关的函数对相关数据进行管理和推演,该类函数一般都是强密码的。如,可以设置消息分块函数,当需要传输的消息过大时,可以运行该函数将消息分成n比特的消息块,方便传输,使加解密过程更迅捷。

3.2 安全架构在机会网络中的具体实施

最开始,将网络中节点按照社会上下文中相关属性的不同被划分为诸多不同的社区定义为本架构在机会网络中实施时的安全假设。至此,某一个相同社会属性的接地同属于一个社区,而提供了这种安全假设后,属于同一社区内的用户就可以相互信任,且某一个节点为本社区内任意节点透露其共有的属性并不会被视为隐私的泄露。同时,任意节点的社会上下文具备唯一性,可以作为节点身份的代表。例如,在Comi社区中的节点都有相同的社会属性i,社区内节点见透露属性i时并不会被视为隐私泄露。

在上述安全假设基础上,架构中所有中继节点在制定转发策略时,可以轻而易举的发现自身档案与目的节点的档案之间共同的社会属性,快速计算其匹配度。如果社会属性不同,中继节点就无法获得任何信息,可以对社会上下文的隐私起到极好的保护作用[6]。

例如,在Propicman协议模型中,要在机会网络中部署实施了安全架构的S-Propicman协议,要先建立参数系统,初始化节点,节点NS将需要发送给节点ND的消息M以数据包的形式逐步发送,结果多个节点NX的转发后,消息数据包得到ND处,ND运行诸如DEC等消息加解密算法解密数据包,即可获取明文数据M。

3.3 身份加密安全架构在机会网络中的安全性

3.3.1 社会上下文的隐私性

高效可搜索的加密方案具备抵抗不可区分的自适应选择关键字符攻击的能力,可以保证节点只有在拥有对方节点的陷门时,才可以获取消息源头中的相关属性信息,而且相关环节专门负责生成并保存社会属性的私钥,其陷门的分发仅仅针对内部用户,这也就避免了单一节点被捕获可能造成的属性私钥泄露情况的发生。

3.3.2 信息的机密性

在架构中生成公钥并加密消息都是以目的节点的社会上下文属性为基础的,目的节点是唯一可以解密的节点;同时,也可以引入对称密钥来进行消息的加密,运用节点社会上下文生成的公私钥对对称密钥进行加解密,极大的提高了算法的性能也保证了消息的机密性[7]。

3.3.3 通信节点的匿名性

架构中源节点发送的数据包中包含了根据目的节点的社会上下文生成的可搜索消息头和消息秘闻,但并不包含任何源节点的消息,可见数据包在结果多跳的路由转发后,攻击节点就无法从截获的数据包中取得相关数据源节点的丁点身份信息,实现了发送者的匿名性。

4 结语

机会网络融移动的自组织网络、容迟网络、社会网络等诸多概念为一体,可以通过移动节点的相遇性机会对消息进行传输和共享。基于身份认证的机会网络安全路由架构其实就是针对目前机会网络中极为流行的基于社会中上下文的路由转发协议,来设计基于身份加密的信息安全架构,以此保证节点社会中上下文的隐私性与信息的保密性。此安全路由架构可以通过搜索方便的加密算法来为任意一个节点的社会属性设计相应的陷门,导致中继节点在可计算自身和目的节点之间社会上下文匹配度、可制定相应的转发路由策略的同时,却无法获取目的节点与属性相关的任何信息,同时,也可以使用节点的社会上下文产生公钥对信息进行加密,多次实验仿真数据表明,此安全路由架构可以确保信息的机密性,且本方案中的部署在网络报文投递率和报文的平均时延方面并未造成明显的影响,不失为一种实用、高效、稳定的机会网络安全路由架构。

参考文献

[1]沈二琳,李德其.基于MCPK的移动网络安全路由方案[J].广西计算机信息,2010,(26):74-77.

[2]王永芝,季磊,胡一度.使用对技术的基于身份密码学研究综述[J].安庆师范学院学报,2009.8,1l(3):56-59.

[3]陆乾容,杜少敏.机会网络研究进展及其安全路由架构[J].中国计算机研究,2008,(5):12-23.

[4]许娟,刘军燕.机会网络及其数据管理的概念、问题与进展[J].软件学报,2009,8,1l(3):56-59.

[5]钟桓昌,刘鼎铭.无线Ad hoc网络及其安全路由架构研究难点[J].中国计算机研究,2007,(5):46-57.

[6]刘光耀,冯凡卡,刘军.一种WSN的非一致性数据故障检测机制[J].软件学报,2010,(12):112-115.

机会网络路由 篇6

在传统的ad hoc网络中提出的路由机制是基于节点和节点之间存在着完整的端到端的路径, 而机会网络是一种节点与节点之间没有端到端路径的网络。于是在传统ad hoc网络里提出的路由机制并不适用于机会网络。

目前已经提出了众多机会网络中的路由工作。经典的路由协议有:传染路由[1] (Epidemic routing) 、概率路由 (Probabilistic Routing) [2]及信息摆渡路由[3] (Message Ferry routing) 。信息摆渡路由 (MF) 是指利用一个按照预定路由运动的特殊节点 (称ferry) 来为其他普通节点传输数据。

文献[3]提出了两种ferry路由机制FIMF和NIMF。其中FIMF需要让ferry改变自己的运动轨迹来靠近普通节点以接收信息。NIMF中, ferry按照预定轨迹运动, 而让普通节点改变自己的运动轨迹来靠近ferry以发送数据。这使得普通节点无法正常完成网络的业务。文献[4]中作者提出了几种ferry的路由方案:SIRA, MURA, NRA及FRA。其中SIRA是多个ferry按照同一路径为全网络的普通节点传输数据。MURA则是多个ferry按照各自运动路径, 负责其路径上普通节点的信息传输。而NRA和FRA则是通过中继的方法来完成区间信息的传输。其中NRA是通过在相邻区域间放置中继节点来传输区间信息。而FRA是通过相邻区域间的ferry进行直接通信来传输区间信息的。同样文献[5]给出了利用中继节点的ferry路由设计。

网络中源节点和目的节点在同一区域内的信息为区内信息, 否则称区间信息。本文基于之前工作中提出的适用于实际生活的城乡模型, 并利用ferry和ferry之间直接通信的网络情况下, 统计网络中不同种类的ferry的传输信息总量。这在ferry缓存受限制时, 为了网络不丢包的情况下, 有重要的研究意义。

2 网络模型及假设

2.1 网络模型

在城乡模型中, 乡村围绕城市而建, 如图1所示。整个网络共有N个静止普通节点。中心区域即为城市, 均匀分布N1个普通节点;圆环区域均匀分布N2个普通节点, 且N=N1+N2。对圆环区域进行M等分, 即有M个外围小区域。每个外围小区域即是一个农村, 均匀分布了个普通节点。中心区域有一个中心ferry (称fM+1) 。外围小区域i有一个区域ferry i (称fi) 。中心区域的节点密度大于小区域的节点密度。城市和农村之间的普通节点称为临界点。

fM+1和fi的最短运动路径都是使用旅行商问题 (TSP) 得到的。其中fM+1需经过中心区域内的所有普通节点 (包括临界点) 。fi需经过外围区域i内的所有普通节点 (包括临界点) 。由于中心区域和外围区域内的普通节点都是均匀分布的, 可设中心区域和小区域内相邻普通节点之间的距离分别为1l和l2, 则fM+1和fi (1≤i≤M) 的周期分别为:其中v是fM+1和fi的运动速度。

在之前工作中, 在网络的初始阶段, fi (1≤i≤M) 在临界点i处静止不动, fM+1从某一临界点开始运动。当fM+1遇到fi, 就激活fi, 此后两者同时从临界点i处按照各自轨迹运动。直到fM+1回到最初的临界点, 初始化阶段结束。

2.2 业务模型

本文采用了传感器网络业务模型。将sink节点设在中心区域的某个普通节点处。那么整个网络中所有普通节点产生的信息的目的节点都是该sink节点。设网络中每个节点的信息产生率为λ, 信息大小归化为1。信息传输速率不受限制。

ferry的传输信息量是指在时间内所搜集到的全部信息。

3 区域ferry传输信息量分析

设R是fi在TM+1时间内的传输信息量。fi在外围区域i内按照运动轨迹每绕行一圈, 会访问个普通节点。那么fi在每圈搜集的信息为经过路由调度后, fi需要运行「A」圈后, 在临界点处和fM+1相遇并通信。那么此时fi搜集到的信息量为:此通信的过程中, fi将所携带的信息全部转发给fM+1, 而fM+1并不发送信息给fi。因为所有信息的目的节点是处于中心区域内的sink节点。

4 中心ferry传输信息量分析

设S是fM+1在TM+1时间内的传输信息量。fM+1会从两种节点上搜集到信息。一是从中心区域内的普通节点接收信息, 二是从区域ferry上接收信息。

fM+1在中心区域内按照路径每运动一圈的时间为TM+1。当fM+1到达一个普通节点时, fM+1会从该普通节点处接收到的信息为:=c TM+1⋅λ。由于fM+1每运动一圈, 需要访问N1-1个普通节点。于是在fM+1在TM+1内, 会从普通节点处搜集到信息大小为:

当fM+1到达一个临界点时, fM+1会在临界点处正好和各区域ferry相遇并通信。由于在fM+1运动的一个周期内, fM+1会访问到M个区域ferry。于是fM+1从所有区域ferry处搜集到信息大小为MR。

所以fM+1在TM+1时间内的传输信息量为:

5 数值分析

由上述分析中, 可知在TM+1时间内, fi会接收信息量为R=TM+1⋅λ⋅MN2, fM+1会接收到信息量为:S=TM+1⋅λ⋅ (N-1) 。以下利用MTLAB, 通过改变网络普通节点个数N、普通节点的信息产生率λ、外围区域个数M来研究网络参数对R、S的影响。

为了满足城乡网络中, 中心区域内节点密度大于外围区域的节点密度, 本文假设N=N1+N2, N1=N2, pl1=l2, p>1。为了方便数值分析, 设

5.1 普通节点数目N对ferry信息传输量的影响

设定普通节点的信息产生率为λ=1个/秒, 外围区域个数为M=4。表1显示了在节点的信息产生率、外围区域个数不变的情况下, 随着普通节点数目的增加, fM+1和fi传输信息量逐渐增加。这是因为随着普通节点数目的增加, 外围区域i内的普通节点数目增加, 则外围区域i内的信息总量增加, 所以fi传输信息量逐渐增加。中心网络的普通节点数目增加, 同样, 中心区域产生的信息总量增加, 所以fM+1传输信息量逐渐增加。

从表1中可以看出fM+1的传输信息量远大于fi的传输信息量。这是因为fi只负责该外围区域内的信息搜集, 而fM+1不仅要从fi上搜集信息, 还要从中心区域的普通节点上搜集信息。

5.2 信息产生速率λ对ferry信息传输量的影响

设定圆环区域和中心区域的普通节点个数为:N=1N=240, 外围区域个数为M=4。表2中显示了在普通节点数目、外围区域个数不变的情况下, 随着普通节点的信息产生率增加, fM+1和fi传输信息量逐渐增加。这是因为随着普通节点的信息产生率的增加, 外围区域和中心区域的信息量都增大了。

5.3 外围区域个数M对ferry信息传输量的影响

设定圆环区域和中心区域的普通节点个数为:N=1N=240, 普通节点的信息产生率为λ=1个/秒, 表3中显示在普通节点数目、节点信息产生率不变的情况下, 随着外围区域个数M的变化, fM+1传输信息量没变, 而fi传输的信息量逐渐减少。

这是因为网络内普通节点总数没变化, 外围区域个数增加, 即外围区域i内的普通节点数目减少, 由此外围区域i内的信息量减少, 由此fi传输的信息量逐渐减少。而由于整个网络普通节点数目不变, 到达中心区域的sink节点的信息量没有变化, 所以fM+1传输信息量没变。

6 总结

本文基于城乡模型上, 并利用ferry和ferry之间直接通信的工作方式下, 统计了区域ferry和中心ferry的传输信息量。并利用MATLAB, 通过改变过改变网络普通节点个数N、普通节点的信息产生率λ、外围区域个数M来研究网络参数对ferry传输数据量的影响。数值分析显示了网络参数的配置对区域ferry和中心ferry的影响很明显。

参考文献

[1] A.Vahdat, D.Becker.Epidemic routing for partially-connected Ad Hoc networks.Duke tech report CS-2000-06, 2000

[2] A.Lindgren, A.Doria, O.Schelen.Probabilistic routing inintermittently connected networks.2004-08-05

[3] W.Zhao, M.Ammar, and E.Zegura.A message ferryingapproach for data delivery in sparse mobile ad hocnetworks.ACM MobiHoc2004, 2004, 187-198

[4] W.Zhao, M.Ammar, and E.Zegura.Controlling the mobilityof multiple data transport ferries in a delay tolerantnetwork.IEEE INFOCOM, 2005, 1407-1418

[5] Z.Zhang, Z.Fei.Route design for multiple ferries in delaytolerant networks.WCNC, 2007, 3462-3467

机会网络路由 篇7

由于网络节点的连通性差,消息传递需要被动地等待节点随机移动带来的通信机会,节点的连接性难以预测,因而传统的Internet路由算法(如RIP[2],OSPF[3])和MANET路由算法(如AODV[4])不适用于机会网络[1]。在目前适用于机会网络的被动式路由协议(如Epidemic路由协议[5])中,节点依靠本身的移动来建立路由,节点随机移动时,相遇的机会是不可预测的以为了提高传输率,降低时延,普通节点选择在网络中大量复制以传播消息,这使得网络间节点间缓存以及能量消耗剧增。

为了缓解节点的能耗,降低网络的时延,克服在长时间高度隔断网络中的通信间断,基于主动运动的路由协议(如消息摆渡机制路由协议[6])中引进了一种非随机移动的特殊节点——Ferry节点。Ferry利用高速主动运动的能力使断裂的网络连接起来,以“存储—携带—转发”的方式协助网络传输消息,在消息的传输过程中充当渡船的角色。路由分两种形式,分别为node主动靠近Ferry进行通信(node必须具备主动运动的能力)和Ferry主动靠近node进行数据交互。

自从基于消息摆渡的机会网络路由方法被提出以后,人们对其加以改进和拓展的研究一直在进行,在主动运动节点的选择、Ferry节点主动运动路径的设计和优化等方面已取得一定进展[7,8,9,10]。但通过研究发现,现有的基于消息摆渡的机会网络路由方法在控制消息(如Hello消息和服务请求消息)的传输方面存在冗余的通信和存储开销,而且Ferry节点主动运动路线也仍然有不够优化的地方,这些问题对采用消息摆渡机制的机会网络路由方法的性能具有重要影响。

1 FIMF网络模型及存在问题

1.1 FIMF网络模型

本文所采用的FIMF网络模型如图1所示,网络区域大小为一个D×D的正方形,把网络平均分成4个正方形小栅格,Ferry节点的固定路径即由每个小栅格的中心为顶点的正方形L,设R为长距离通信半径,则当R取不小于

$\sqrt{2}D/4$的某一定值时,Ferry节点在封闭的路线L上移动一周,其通信范围能够覆盖全网。

网络初始时Ferry节点沿着预先设置好的路径移动,并通过大功率通信方式周期性地广播包含当前自身位置信息的Hello消息。当普通节点S接收到Ferry节点广播的Hello消息时,提取该Hello消息中的位置信息计算其本身与Ferry节点的距离d,若d<Rth(这里Rth<R),且节点控制机制[7]判定满足通知Ferry节点主动运动靠近进行通信的条件时,S会以大功率通信方式发送一个服务请求(Service_Request)的消息(包含节点当前位置)给Ferry节点(为了确保Service_Request的成功传送,这里取Rth<R),如图1a所示。一旦Ferry节点接收到S的服务请求消息,Ferry节点会依据消息里面节点S的坐标消息改变自己的移动路线与节点S相遇。节点本身的控制机制会适时地以大功率通信方式向Ferry节点发送位置更新(Location_Update)消息,如图1b所示。当普通节点和Ferry节点相遇时(进入双方的短距离通信范围,通信半径为r),普通节点和Ferry节点就会以正常通信方式开始交换消息,如图1c所示。当Ferry节点和普通节点之间数据交互完毕时,Ferry节点会返回原来的路由路径,如图1d所示。任何时候只要Ferry节点与普通节点进入对方的短距离通信范围则进行数据交互。

1.2 存在问题

FIMF路由方案中存在以下问题:

1) 普通节点上会发生以下3种事件,设事件A为节点物理层检测到来自其他节点的信号;事件B为节点缓存中有数据待发送;事件C为发送Hello消息。事件A,B,C是相互独立的,并且节点可以自主控制事件C的发生。原FIMF方案节点周期性地广播Hello消息,仔细研究不难发现,当事件A与事件B同时不发生时,事件C的发生对数据传输不起作用。

2) 普通节点都是以单一的大功率无线电发送服务请求消息与位置更新消息给Ferry节点,由于该动作发生在接收到Ferry节点的Hello消息后,因此这些节点当前与Ferry的距离d最多为R。通常通信半径为d的传输功率与dm(m>1,为路径损耗系数)成正比。因此当d小于Rth时,普通节点可以成指数倍地降低发射功率发送控制消息,节能效果是显然的。

2 改进的FIMF方案

RSSI的测距技术不需要增加额外装置和额外能量消耗,相对来说成本及复杂度低,普遍应用于各种无线多跳网络中。本文采用基于RSSI测距技术,提出改进的FIMF方案(AFIMF方案)来解决以上问题。AFIMF方案包含以下两种改进机制。

1) 普通节点基于跨层信息共享方式按需广播Hello消息。

在该机制中,当且仅当事件A或者事件B至少有一个发生时,发生事件C。这样可以减少节点发送Hello包的次数,降低网络通信的控制开销,节约节点能量。证明如下:

在N个节点,大小为D×D的正方形网络中,节点度为$n=\frac{{\rm N}\times r{}^2}{D\times D}$,则节点事件A发生的概率p等于n;取事件B发生的概率为q=1/2。$\overline{A}$,$\overline{B}$同时发生的概率为(1-n)/2,由于机会网络中节点度小于1,(1-n)/2大于0。例如在N=100,r=250 m,D=5 km的机会网络中求得n=0.25,因而采用本机制的改进方法,node在理论上可以减少发送约37.5%的Hello消息。

所以本机制的改进方法是可行的,并且能达到预期的有益效果。

2) 普通节点基于RSSI技术自适应地调整功率发送服务请求消息与位置更新消息。

本机制在普通节点MAC层采用RSSI测距技术保存最新接收到的Ferry—Hello消息的距离,当MAC层需要发送来自路由层的发送服务请求消息与位置更新消息时,根据该距离自适应地调节合适最小发射功率。这样可以整体降低节点发射服务请求消息与位置更新消息的功率,节约节点能量。证明如下:

以Ferry当前的位置为中心,设此时需要发送服务请求消息或者位置消息的任一节点与Ferry的距离为x(其中0<x≤R),将距离R分成k($k=\left|\frac{R}{r}\right|$)个子区间,其中第i(1≤i≤k-1)个子区间为((i-1)r,ir],第k个子区间为((k-1)r,R];每个子区间对应一个合适的最小发射功率Pi;设y表示x落在第i(1≤i≤k)个子区间,其中$y=\left|\frac{x}{r}\right|$是一个随机变量,因而对应发射功率P也是一个随机变量,y和P的分布律如表1所示(p为对应的概率)。

设功率期望值为$\overline{{\rm P}}$,对于∀i∈{1,2,…,k-1}有pi<Pk,且

$\overline{{\rm P}}={\displaystyle \sum _{i=1}^{k}p}{}_i{\rm P}{}_i<{\displaystyle \sum _{i=1}^{k}p}{}_i{\rm P}{}_k={\rm P}{}_k$

因此在相同网络条件下,采用本机制能够减少节点的能量消耗。

3 仿真结果及其分析

将采用本文提出的3种改进机制的FIMF路由算法称为AFIMF,并使用OPNET仿真软件分别对AFIMF与FIMF路由方案进行性能仿真分析。

3.1 仿真设置

本文对N(N=40,60,80,100,120)个节点随机分布在网络中,一个Ferry的5个场景进行仿真,每个场景采用相同的网络设置。场景大小为5 000 m×5 000 m。随机选择场景中40%的节点产生数据,随机选择网络中的其他节点作为数据目的地。源节点消息产生率服从泊松分布,消息超时值为3 000 s,节点移动模式为随机路点模型,节点最大的移动速率为5 m/s。Ferry的移动速率为20 m/s,Ferry固定路径为以位置(1 250,1 250)和位置(3 750,3 750)为对角顶点的矩形,其他参数设置如表2所示。

3.2 性能分析

1) 消息传递成功率:

消息传递成功率是成功接收到的数据分组总比特数与发送数据分组的总比特数的比值,用来表征算法在运行过程中消息传递的成功率。图2表明不同的网络场景在相同网络条件下,改进算法AFIMF与原FIMF消息传递率持衡,AFIMF有良好的稳定性。

2) 控制开销:

控制开销是指控制分组的总比特数与发送数据分组的总比特数的比值,用来说明每发送一个数据分组,需要发送控制分组的比特数。图3表明在相同网络条件下,采用AFIMF算法的控制开销均比FIMF低;这主要因为在AFIMF中,普通节点基于跨层信息共享方式按需广播的Hello消息。由图2知两种算法消息传递成功率持衡,AFIMF较FIMF在不影响网络消息传递的性能下,消耗更少的控制开销。

3) Hello包发送的总个数:

统计网络中所有节点在网络运行期间发送的Hello包个数。图4表明在相同网络条件下,采用AFIMF算法的Hello包发送的次数均比FIMF少;这是因为在AFIMF中,普通节点基于跨层信息共享方式按需地广播Hello消息。由图2知两种算法消息传递率持衡,因此在不影响网络消息传递性能的前提下,AFIMF较FIMF,节点发送的Hello消息更少,减少了节点的通信开销。

4) 总能量消耗:

网络中所有节点发送和接收消息(包括数据分组和控制消息)总消耗的能量。图5表明,采用AFIMF算法的总能量消耗均比FIMF少;这主要因为AFIMF采用普通节点基于RSSI技术自适应地调整功率发送服务请求消息与位置更新消息机制,降低了发射控制消息的功率期望值,另外,使用其他两种机制节约了网络开销,进而节约了能量。由图2知两种算法消息传递率持衡,因此在不影响网络消息传递性能的前提下,AFIMF较FIMF,节点消耗的能量更少,增强了路由算法的健壮性。

4 结论

机会网络中的FIMF路由机制中,普通节点在传递控制消息(如节点位置消息、Hello消息)时存在多余的通信开销,并且采用了大功率发送位置消息会耗费过多能量。本文提出了FIMF的改进路由算法AFIMF,该算法降低了节点长距离无线电发送控制消息的功率,减少了node发送Hello消息的次数。仿真结果表明,AFIMF在保证消息传递成功率不低于FIMF方案的前提下,能减小网络的总能量消耗、控制开销和节点Hello消息的次数。

参考文献

[1]LILIEN L,KAMAL Z H,GUPTA A.Opportunistic networks[R].Kalamazoo:Department of Computer Science Western Michigan Universi-ty,2006.

[2]RFC 1058,Routing information protocol[S].1988.

[3]SIDHU D,FU T,ABDALLAH S,et al.Open shortest path first(OSPF)routing protocol simulation[J].Computer Communication Review,1993,23(4):53-62.

[4]PERKINS C E,ROYER E M.Ad-hoc on-demand distance vector rou-ting[C]//Proc.Ninety-ninth Mobile Computing Systems and Applica-tions.[S.l.]:IEEE Press,1999:90-100.

[5]VAHDAT A,BECKE D.Epidemic routing for partially connected AdHoc networks[R].Durham:Department of Computer Science in DukeUniversity,2000.

[6]ZHAO W R,AMMAR M.Message ferrying:proactive routing inhighly-partitioned wireless Ad Hoc networks[C]//Proc.Ninth IEEEWorkshop on Future Trends of Distributed Computing Systems.[S.l.]:IEEE Press,2003:308-314.

[7]ZHAO W R,AMMAR M,ZEGURA E.A message ferrying approach fordata delivery in sparse mobile Ad Hoc networks[C]//Proc.Fifth ACMInternational Symp Mobile Ad Hoc Networking and Computing.[S.l.]:IEEE Press,2004:187-198.

[8]章韵,魏鹏,王汝传,等.DTN网络中ferry节点的MSSL路由算法研究[J].计算机技术与发展,2009,19(5):107-110.

[9]POLAT B K,SACHDEVA P,AMMAR M H.Message ferries as general-ized dominating sets intermittently connected mobile networks[J].Per-vasive and Mobile Computing,2011,7(2):189-205.