论文部分内容阅读
与传统蜂窝通信网络不同,无线ad hoc网络不具有基础的骨干设施,其节点一般通过洪泛的广播方式进行通信,这不仅会产生大量的消息延迟和冲突,甚至会产生广播风暴,从而增加网络能耗,缩短网络生命周期。在无线网络中使用虚拟骨干网(Virtual Backbone Network,VBN)进行通信能够有效解决上述问题。利用图论中连通支配集(Connected Dominating Set,CDS)的思想是构建VBN的重要方式之一。基于目前CDS构造算法的研究现状和常用的性能指标分析,发现CDS规模不是所有无线网络中追求的唯一目标。例如在移动Ad Hoc网络中,由于节点具有一定的移动速度,使得节点之间的链路容易出现故障,因此,更加需要关注CDS的生命周期。另外,与传统的只考虑局部干扰的图模型(协议模型)相比,物理干扰(Signal-to-Interference-plusNoise-Ratio,SINR)模型考虑了全局干扰问题,反映了干扰的累加和衰落特性,符合实际网络环境。基于上述两个问题,本论文主要研究移动Ad Hoc网络中具有极大生命周期的CDS构造算法和基于SINR模型的无线网络CDS构造算法。主要研究内容和贡献如下:(1)在移动Ad Hoc网络中,本论文主要从两个方面来提高CDS的生命周期。首先,根据节点之间的欧氏距离与它们通信范围的比值小于固定参数?,对原始网络进行“升级”,一开始就将潜在的不稳定链路删除;其次,优先选择移动速度小的节点成为CDS节点。一旦节点被选定为CDS节点,则它的所有邻居都将被探索并存储在队列中,成为下一次迭代的候选者。所有被探索的节点按照移动速度非递减排列,当被探索过的节点有至少一个邻居未被探索时,该节点将加入到CDS中。该过程一直持续,直到网络中不存在未被探索的节点。理论分析和仿真实验表明,相较于传统的基于度的思想构建的CDS,本论文提出的算法构建的CDS生命周期更长。(2)针对一般无线网络的物理干扰模型,本文设计了SINR模型下CDS的构造算法D-CDS。首先,将网络划分成边长相同的六边形网格,每个网格称为一个小区。另外,为了避免冲突,我们引入物理载波侦听。算法D-CDS包含两个阶段,第一阶段是领导者选举阶段,为每个小区选择领导者。第二个阶段选择合适的连通者来连接第一阶段的领导者,构成网络的一个CDS。第二阶段主要包含三个子阶段,分别是区内学习、区间学习和连通者选择。领导者通过区内学习来获得同小区中邻居节点的信息,并将这些信息共享给邻居节点;然后,节点通过区间学习来确定不同小区中的邻居节点信息;最后,选择能降低网络连通分量的节点作为连通者,并根据最小规则降低连通者的数量,得到规模较小的CDS。本文通过严格的理论分析证明了算法D-CDS在SINR模型下的可行性和正确性;同时,算法的时间复杂度优于目前已有算法,并且能得到具有常数近似比的CDS。