无线网络中连通控制集的算法设计与分析

发布时间：2019-04-24 14:01

【摘要】：随着无线网络在家庭自动化、交通控制、医疗保健、环境监测、战场探测和农业等方面的应用,因为网络节点是由电池供电,所以节点自身存在的能量几乎成为网络生命周期的瓶颈问题。因此,为了增大整个网络在探测区域内的生命周期,我们应该尽可能的节省节点能量消耗。然而,当网络节点通过广播的方式与邻居节点通信的过程中会造成大量的信息冗余,不仅会导致信息的传递不成功,而且也极大的造成了节点的能量损耗。为了减少节点通信过程中产生的信息冗余和节点的能量损耗,最简单有效的方法是建立网络中的虚拟骨干网络,也就是连通控制集(CDS)。目前,在无线网络中构造连通控制集的一些经典算法多数包含两个阶段。在算法的第一个阶段构造网络的一个极大独立集(MIS)。在第二个阶段,通过从V\MIS中选取一定的节点作为连通节点加入到MIS中,使得MIS中的节点都有路径相连。在本文中,首先对现有的一些经典的连通控制集算法进行研究与分析,然后在单位圆盘图(UDG)上提出了构造连通控制集的分布式算法LDDS和CT算法。之后,又提出了算法LDDS的集中式版本算法CMDS,并提出了连通CMDS构造的控制集MDS的集中式连通算法CMCDS。然后,对一般的图模型,我们得到了一个最优连通控制集MCDS的一个下界,也就是,从而证明了对于任意的连通控制集的近似因子。最后,在一般的图上构造了分布式算法Asyn_BFS、COF、CMIS、ACP、ACHC、PMIS和全局连通算法,得到了相对较优的连通控制集。本文主要分为六章。第1章介绍了研究背景、意义和构造连通控制集需要考虑的性能指标。第2章对当前的一些连通控制集算法及相关结果进行了简单分类和总结,并对其中的一些构造算法进行了简单的分析。第3章在单位圆盘图上设计了一个求解近似最小连通控制集的分布式算法。首先设计了一个求解最小控制集的近似算法LDDS,该算法根据链路的最大邻边的数目成对的选出控制集的节点,当存在一个节点v的N(v)中所有节点的邻居节点都在N(v)中时,则直接将节点v加入到控制集中。之后,提出了一个Connecting Tree构造算法CT,使得连通控制集中的节点需要的连通节点尽量的少。第4章提出了算法LDDS的集中式版本算法CMDS,得到了一个最小的控制集MDS。之后,我们设计了一个集中式连通算法CMCDS,贪心地往MDS中增加节点使得控制集MDS中的所有节点连通。这里CMCDS算法是选择最少的连通节点的算法。第5章在一般的图模型上设计了一个求解连通控制集的分布式算法。首先算法Asyn_BFS得到了一个宽度优先搜索树。然后,提出的COF算法在网络中根据节点的度构造了一个森林。算法CMIS在森林中每棵树上得到一个局部的MIS。算法ACP则根据MIS中节点的个数将将每棵树划分为|MIS|个簇。算法ACHC将每棵树上|MIS|个簇的簇头连通。算法PMIS则将所求局部CDS中冗余的节点裁剪掉。最后全局连通算法将所有的局部控制集连通。第6章对本文进行总结,并对未来进一步的研究工作进行了展望。
[Abstract]:......
【学位授予单位】：曲阜师范大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TN92

【相似文献】

相关期刊论文 前6条

1 张志强;叶安胜;周晓清;;最小控制集问题的群集策略智能算法研究[J];科学技术与工程;2014年16期

2 ;工程数学[J];中国无线电电子学文摘;2005年02期

3 曹建香;税琳琳;石民勇;;广义道路与广义圈的绑定数与增强数[J];中国传媒大学学报(自然科学版);2007年02期

4 David Crump;;氢生产的控制集成[J];软件;2010年06期

5 李峰;赵海兴;徐宗本;;构建一类新网络簇的可靠性控制集[J];计算机学报;2013年06期

6 ;[J];;年期

相关重要报纸文章 前2条

1 石家庄市畜牧水产局 赵洪明　强慧勤 王荣申 张涛 李钊;养殖投入品控制集成技术[N];河北科技报;2013年

2 宦建新　通讯员　沈维强;浙江“食品安全科技专项”取得成果[N];科技日报;2005年

相关博士学位论文 前10条

1 赵维胜;关于树的控制问题与强乘积图约束数的研究[D];兰州大学;2015年

2 董艳侠;广义de Bruijn有向图和超图的控制集问题[D];上海大学;2016年

3 彭茂;图的控制集的一些相关问题的研究[D];上海交通大学;2008年

4 陈磊;图中配对控制集问题的机械化算法研究[D];华东师范大学;2010年

5 刘清海;几类组合优化问题的算法研究[D];新疆大学;2012年

6 李宪越;关于一些网络最优化问题的近似算法的研究[D];兰州大学;2009年

7 黄佳;图的控制稳定性研究[D];中国科学技术大学;2007年

8 陈星;几类图的连通性和控制集[D];新疆大学;2011年

9 胡夫涛;图的约束数研究[D];中国科学技术大学;2012年

10 陆由;图的控制理论研究[D];中国科学技术大学;2010年

相关硕士学位论文 前10条

1 秦敏艳;路和圈的定位控制集问题[D];华东师范大学;2010年

2 罗传文;无线网络中连通控制集的算法设计与分析[D];曲阜师范大学;2016年

3 丁玲玲;图的控制集问题的近似算法研究[D];中国海洋大学;2008年

4 陈春霞;关于路和圈的验证码和定位控制集问题[D];华东师范大学;2009年

5 李秀英;求最小2连通r步控制集的两种算法[D];新疆大学;2011年

6 何永能;图的电力控制集问题[D];华东师范大学;2012年

7 盛斌;立方图的配对控制集问题上界[D];华东师范大学;2013年

8 杨晓静;图的[1,2]-控制集[D];新疆大学;2014年

9 麻娜;图的控制参数的若干问题[D];大连理工大学;2001年

10 吴亚娜;无爪图配对控制集问题上界的研究[D];华东师范大学;2013年

，

本文编号：2464508