论文部分内容阅读
近些年来,无线网络的应用范围越来越广。而普通无线网络如Ad-hoc网等都是无基础设施通信网络,它们的这个特性使它有别于有线基础设施网。有线网络不受能源供应限制,但在普通的无线网络中节点的能量问题是首要考虑的。所以在普通无线网络中建立一个专门的骨干网来负责路由通信等功能,对只依靠电池供电的无线设备和无线网络的发展来说已经变得十分重要。控制集(DS)已经广泛应用于无线网络的活动节点集的选取以建立无线网络中的虚拟骨干网络。节点之间都不连通的DS是个独立集,为了使DS成为能担当无线网络中拓扑控制、搜索、广播信息、节点覆盖等多种任务的虚拟骨干网,许多学者对应用连通控制集(CDS)作为无线网络虚拟骨干网的方法进行了大量的研究。但是在构造CDS的时候必须选取大量的连通节点,以保证DS的连通性,整个网络的活动节点会因此而增加,网络中能耗也相应的增多。于是通过放松对DS连通性的要求以减少DS中节点的数量,弱连通控制集(WCDS)作为无线网络的虚拟骨干网的方法被提出。本文在前人研究结果的基础上,从集中式算法和分布式算法两个方面出发,提出了两种在无线网络中构造WCDS的方法。在集中式算法方面,我们通过构造边控制集的方法来求解无线网络中的WCDS,该算法的时间复杂度为O(|N|+|E|);同时在保证WCDS的控制性和弱连通性不变的情况下,给出了两种修剪策略,以减小所求WCDS的规模。在分布式算法方面,本文又提出了一种基于时间竞争机制的无线网络WCDS构造策略;本算法无需全局根节点的控制,通过节点本身优先级的不同来确定自己是否为控制节点;算法的时间复杂度同样为O(| N|+| E|)。文章中从理论方面上证明了以上两种算法的正确性,并通过仿真验证了它们的有效性。与已有结果相比,本文提出的两种算法可以产生规模更小的弱连通控制集。