无线网络中弱连通控制集构造算法研究

来源 :曲阜师范大学 | 被引量 : 0次 | 上传用户:chnlaozhang
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
近些年来,无线网络的应用范围越来越广。而普通无线网络如Ad-hoc网等都是无基础设施通信网络,它们的这个特性使它有别于有线基础设施网。有线网络不受能源供应限制,但在普通的无线网络中节点的能量问题是首要考虑的。所以在普通无线网络中建立一个专门的骨干网来负责路由通信等功能,对只依靠电池供电的无线设备和无线网络的发展来说已经变得十分重要。控制集(DS)已经广泛应用于无线网络的活动节点集的选取以建立无线网络中的虚拟骨干网络。节点之间都不连通的DS是个独立集,为了使DS成为能担当无线网络中拓扑控制、搜索、广播信息、节点覆盖等多种任务的虚拟骨干网,许多学者对应用连通控制集(CDS)作为无线网络虚拟骨干网的方法进行了大量的研究。但是在构造CDS的时候必须选取大量的连通节点,以保证DS的连通性,整个网络的活动节点会因此而增加,网络中能耗也相应的增多。于是通过放松对DS连通性的要求以减少DS中节点的数量,弱连通控制集(WCDS)作为无线网络的虚拟骨干网的方法被提出。本文在前人研究结果的基础上,从集中式算法和分布式算法两个方面出发,提出了两种在无线网络中构造WCDS的方法。在集中式算法方面,我们通过构造边控制集的方法来求解无线网络中的WCDS,该算法的时间复杂度为O(|N|+|E|);同时在保证WCDS的控制性和弱连通性不变的情况下,给出了两种修剪策略,以减小所求WCDS的规模。在分布式算法方面,本文又提出了一种基于时间竞争机制的无线网络WCDS构造策略;本算法无需全局根节点的控制,通过节点本身优先级的不同来确定自己是否为控制节点;算法的时间复杂度同样为O(| N|+| E|)。文章中从理论方面上证明了以上两种算法的正确性,并通过仿真验证了它们的有效性。与已有结果相比,本文提出的两种算法可以产生规模更小的弱连通控制集。
其他文献
Web信息具有动态性、分布性和规模性的特点,未来的Web服务应该向人们提供智能化、个性化的服务,并且能够有效地解决现实问题。在当今Web背景下,单一推理技术已无法满足现实问题
学位
秘密共享是现代密码学的一个重要分支,是保障信息安全和数据保密的重要手段之一。利用秘密共享保存和管理秘密信息,一方面可以防止权力过于集中而被滥用,分散了责任;另一方面
车间流水作业调度问题是生产、调度领域的一个热点、难点,是许多实际生产调度问题的典型调度简化模型。总完工时间是一个重要的衡量指标,它的最小化能有效提高设备利用率、缩短
H.264是国际电信联盟与国际标准化组织联合推出的新一代视频编码标准。该标准采用了先进的编码技术,具有卓越的压缩性能,并且易于网络传输,能够满足多种视频应用的需求。因此
学位
随着计算机与网络技术的快速发展,大数据集的出现致使人们获取的信息量正在以前所未有的速度日益剧增,也导致大量不相关或冗余数据的不断涌现。因此,如何快速获取所需有用信
当今,各种各样的企业级应用系统的使用缩短了业务流程执行的周期,提高了业务处理的效率,降低了业务处理的成本,并且能够为企业未来发展决策提供强有力的数据统计和分析的支持。但
数据挖掘是指从含有大量数据的数据库中提取有效的、有潜在价值的、新颖的信息和知识的非平凡过程。在许多的数据挖掘方法中,粗糙集方法是其中的一种很好的数据挖掘工具。在
服务和服务组合作为一个研究热点问题已经有很多年了。当前从工业上的标准(如BPEL、OWL-S)到理论上的方法(如Petri网、进程代数和自动机等),提出了很多的方法来研究他们,但这
计算机和网络技术的快速发展,推动了电子政务的信息化进程,政府在信息化建设过程中,经常需要根据现实情况和公众需求,对原有的应用系统进行升级改造,或者开发新的应用系统,在
学位
互联网的迅速发展和普及导致了网上信息爆炸性增长。如何在互联网上获得有价值的信息已成为人们日益关注的问题。搜索引擎是以一定的策略在互联网中发现、搜集信息,对信息进
学位