图的连通误报容错支配集算法研究

发布时间：2020-04-30 03:54

【摘要】：随着网络通信技术的发展,无线网络由于其易安装,灵活性好和低成本等优势,在保健医,战场监测,农业和交通控制等领域被广泛应用.无线网络中的节点都是一个个廉价的传感器,每个传感器都是由电池供电,其有一定的寿命.为了增加无线网络监控的生命周期,并防止信息冗余和广播风暴的发生,许多专家学者提出改变原有的信息传递方式,应用虚拟骨干网作为无线网络的网络基站,即连通支配集.而当一个无线网络出现入侵者节点,如故障点、着火点或破坏节点等等.入侵节点的邻居节点可能会发生故障,其可能会传递错误的信息或不传递任何信息,这时候就需要虚拟骨干网具有一定的容错能力.为解决这一问题,学者Slater提出了误报容错支配集(LR)来增强网络的容错性.本文主要研究一般连通图(顶点数超过3)的最小连通误报容错支配集的构造算法,依次给出了对应的多项式模型算法、近似算法、精确算法和启发式算法,最后还对精确算法和启发式算法进行实现模拟比较,具体内容如下.首先证明了最小连通误报容错支配集(MCLR)问题属于NP-hard问题,并给出LR问题的多项式计算模型和CLR的多项式模型算法,多项式模型的时间复杂性验证了最小连通误报容错支配集问题属于NP-hard问题.其次,给出了一个在一般连通图上构造最小连通误报容错支配集的近似算法,这里的近似算法思想是基于贪婪策略,其近似比为2(1+ln△),其中△是图中点的最大度,这个近似比优于前人的结果.最后给出了在一般连通图上的求解最小连通误报容错支配集的一个精确算法和一个多项式时间的启发式算法,通过计算机仿真,比较两算法的实验结果.
【图文】：

图H的构造

连通误报容错支配集构造示例1如图4.1,图中包含12个顶点,根据启发式算法,找到图中点度数最大的点6号节点放到支配集中,并且更新L0,这里用红色表示节点被选为支配集节点,蓝色表示被1-支配的节点,灰色表示被2-支配的节点
【学位授予单位】：中国计量大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：O157.5

【相似文献】

相关期刊论文 前10条

1 骆伟忠;冯启龙;王建新;陈建二;;完全p-支配集的参数算法[J];计算机学报;2013年09期

2 王康;禹继国;;无线网络中一种简单的弱连通支配集构造策略[J];计算机工程与应用;2011年20期

3 李镇坚;葛启;王海涛;朱洪;;图的支配集若干问题的研究[J];计算机科学;2007年01期

4 黄民肃;向东;;无线自组网络中的基于多个支配集的路由协议[J];计算机应用研究;2007年05期

5 吴迪;梁辉;王光兴;;无线自组网簇间网关支配集优化策略[J];计算机工程;2007年24期

6 孙立山;郝燕玲;;能量限制的连通支配集分布式构造[J];计算机工程与应用;2006年32期

7 苏岐芳;图的支配集的有效算法[J];台州学院学报;2003年06期

8 张光铎，王正志;图论中独立支配集的最佳求解算法研究[J];国防科技大学学报;1995年02期

9 沈湘钟;黄友锐;吴建坤;;基于连通支配集的无线传感器网络拓扑控制算法仿真研究[J];仪表技术与传感器;2016年09期

10 赵学锋;;求解最小连通r-跳k-支配集的启发式算法[J];计算机工程;2012年21期

相关会议论文 前3条

1 李海坡;马向南;;无线传感器网络中基于连通支配集的覆盖控制算法[A];中国通信学会第六届学术年会论文集（下）[C];2009年

2 李克清;;基于定向扩散的最小连通支配集构造算法[A];苏州市自然科学优秀学术论文汇编(2008-2009)[C];2010年

3 蓝慧琴;钟诚;李智;;一种改进的基于连通支配集的P2P搜索算法[A];2006年全国开放式分布与并行计算学术会议论文集（二）[C];2006年

相关博士学位论文 前10条

1 袁福宇;若干支配集优化问题求解的方法研究[D];东北师范大学;2019年

2 施韦;移动Ad Hoc网络中连通支配集若干关键问题的研究[D];浙江大学;2007年

3 汪文勇;无线传感器网络若干节能关键技术研究[D];电子科技大学;2011年

4 骆伟忠;无线网络中若干NP-难问题的参数算法[D];中南大学;2012年

5 刘卓;无线传感器网络拓扑建立方法与应用技术研究[D];华中科技大学;2011年

6 陶凯;广域定向MANET组网关键技术研究[D];哈尔滨工程大学;2015年

7 郑莹;基于树分解的难解问题的参数算法研究[D];中南大学;2013年

8 于瑞云;无线传感器网络中面向数据采集的支配集算法与策略研究[D];东北大学;2009年

9 张强;基于连通性的无线传感器网络节点定位技术研究[D];天津大学;2011年

10 李睿智;基于局部搜索策略的若干组合优化问题求解算法研究[D];东北师范大学;2017年

相关硕士学位论文 前10条

1 武舒;无线网络中连通支配集问题的算法设计与分析[D];曲阜师范大学;2019年

2 李有浩;图的连通误报容错支配集算法研究[D];中国计量大学;2018年

3 徐彤;WSN中连通支配集构造算法的研究[D];南昌航空大学;2019年

4 齐晓晗;基于多连通支配集调度机制的飞行自组网拓扑控制算法[D];哈尔滨工业大学;2018年

5 荆莹;基于时变连通支配集的多层卫星网络路由算法[D];哈尔滨工业大学;2017年

6 刘华丽;若干图的连通支配问题研究[D];中国计量大学;2017年

7 刘培丽;基于集序的集优化问题的稳定性及鲁棒性分析[D];重庆大学;2018年

8 徐培培;无线传感网络中强连通支配集的构造研究[D];南昌航空大学;2016年

9 任思君;最小连通支配集算法研究[D];上海交通大学;2015年

10 鲁登月;无线传感器网络中连通支配集的构造算法研究[D];苏州大学;2014年

，

本文编号：2645361