论文部分内容阅读
移动机会网络是满足物联网透彻感知与泛在互联的一种重要技术手段。机会路由作为实现间歇式连通环境下节点通信的理论基础,具有十分重要的研究意义。但是移动机会网络中节点移动、资源受限、拓扑时变的特点为设计高效的路由算法带来了巨大的挑战。为了降低数据传输时间、提高数据投递率,目前机会路由算法中广泛采用多备份的数据转发策略,这种方式加重了网络负载,严重影响系统的可扩展性。如何设计轻量级、分布式的机会路由算法,满足大规模的自主组网需求,是目前移动机会网络研究中迫切需要解决的关键科学问题之一。针对上述问题,本文结合移动机会网络中节点具有的丰富社会属性,从信息扩散机理、数据转发策略两个方面入手开展研究,提出了一系列模型和方法。本文的主要贡献如下:(1)基于节点时空相关性的信息扩散模型。移动机会网络中节点的位置分布由于节点的移动性而具有时空相关性,导致节点的扩散能力不同,使得传统方法无法准确地刻画信息的扩散过程。针对节点具有不同的扩散能力这一事实,我们提出利用异质的传染率来刻画节点传播信息的能力。基于该传染率,结合马尔可夫链模型对移动机会网络信息的扩散情况进行了研究,给出了移动机会网络中信息扩散情况的更紧的上限表示。在此基础上,建立了信息扩散过程中参与节点个数与信息传播延时、投递率之间的关系模型。(2)基于节点社会度量的机会路由策略。传统基于节点社会度量的路由算法需要获取网络的全局性信息来评价节点的中心度和相似度,无法满足分布式的机会转发需求。针对上述问题,本文提出利用节点的移动模式来量化节点的社会度量,并通过设计一种融合节点中心度、相似度的数据转发策略来提高机会路由算法的性能。该策略分为三个阶段:a)节点移动模式的提取;b)节点中心度、相似度的量化;c)中继节点的选择。在节点移动模式提取阶段,通过将感知区域划分为一个网格,统计节点在每个格子内的停留次数与停留时间,挖掘节点的频繁移动模式。在节点中心度、相似度量化阶段,基于节点的频繁移动模式,聚合系统的热区分布,利用信息熵理论来评价节点的中心度和相似度。最后在中继节点选择阶段,通过融合节点的中心度和相似度,将节点的选择问题转化为一个多目标优化问题,采用自适应加权的方法来选择中继节点。(3)基于节点社会关系的机会路由策略。利用移动机会网络中节点之间相对稳定的社会关系可以减少控制信息的交换次数,提高路由效率。我们对节点之间的社会关系在Epidemic算法和贪婪算法数据转发过程中的参与程度进行了分析,观察到三类现象:a)陌生人具有两面性。一方面,陌生人可以加快数据包的扩散过程,具有积极的一面。另一方面,陌生人感染了所在区域的其它节点,加重了路由负载,具有消极的一面;b)贪婪算法降低了路由负载,但增大了传输延时;c)随着数据转发过程的进行,陌生人所起的作用逐步降低,而社区伙伴所起的作用逐渐增大。基于上述观察结果,我们设计了一种面向节点社会关系的机会路由策略:STRON。STRON通过在数据转发过程中有意识地引入少量陌生人来提高路由效率。陌生人参与转发的概率随着转发过程的进行而逐步降低。实验结果表明,STRON在不影响传输延时的基础上,路由负载只有原有工作的四分之一左右。(4)基于社区结构的机会路由策略。研究节点之间形成的网络社区在数据转发过程中的作用,可以使我们从更高的层面观察数据包在网络中的扩散情况,有助于深入理解移动机会网络的数据转发机理。基于上述考虑,我们对数据包在网络社区内与社区间的扩散情况进行了研究。我们发现a)数据包在社区之间的传输时间明显长于数据包在社区内的传输时间;b)将数据包转发给那些相对重要性高的节点能够显著提高数据包的投递速度(这里节点的相对重要性指的是节点相对于目的节点所在社区的重要程度)。结合这两点,我们提出了一种基于网络社区结构的路由算法。该算法主要包括两个阶段。在数据包没有进入目的节点所在社区以前,将数据包转发给那些相对于该社区重要性高的节点,加快数据包向目的节点所在社区的扩散速度;在数据包进入目的节点所在社区之后,将数据包转发给该社区内重要性高的节点,控制数据包的扩散范围,降低路由负载。综上,本文从机会路由的信息扩散机理与数据转发策略两个方面,围绕移动机会网络中节点分布的时空相关性、节点的社会度量、社会关系、网络社区等社会性信息,提出一系列的模型和方法。理论分析及大量实验验证了所提出模型及方法的有效性。这些模型和方法为移动机会网络的高效数据传输提供保障。