无线网络中控制集构造算法的研究

发布时间：2019-11-25 18:47

【摘要】：近年来,随着无线通信技术与设备的发展,无线网络在各种领域得到了广泛应用。无线设备使用局部广播的方式进行彼此之间的通信造成了网络中大量信息的冗余与能量的浪费。如何减少网络中信息的冗余、节约能量是无线网络协议设计过程必需要考虑的问题。从某种意义上来说这一问题决定了无线网络的服务质量,而拓扑控制能够解决上述问题,因此设计有效的拓扑控制协议是十分必要的。所谓拓扑控制,是指在无线网络相应的图模型中构造具有某些特殊性质(如,连通性、稀疏性、低干扰等)的子图。控制集是拓扑控制中的一种重要的方法,在无线网络中得到了广泛研究。本文通过对现有控制集算法的研究与分析,首先在beep模型下提出了BMDS. BCDS与BCDSC算法。离散beep模型是一个极其严格的局部广播模型,该模型仅依赖载波侦听,网络中的节点不需要任何先验信息,例如节点的唯一标识符,网络的拓扑信息等。然后,在SINR模型下设计了DSSMIS与DSS_CDS算法。SINR(Signal-to-Interference-plus-Noise-Ratio)模型是一个更加切合实际的累积干扰模型。事实上,我们还通过理论分析分别证明了它们的有效性与正确性。本文共分为五章。第1章介绍了研究的背景、意义与研究现状。第2章对当前存在的一些控制集算法进行了分类与总结,并对某些经典的控制集构造协议进行了分析。第3章首先给出了离散beep模型下的一个分布式最小控制集的近似算法(Beeping a Minimum Dominating Set, BMDS),该算法是一个基于局部控制度(节点的非受控邻接点的数目)的贪心选择策略,然后设计了beep模型下的极大独立集构造算法以及弱连通控制集构造算法,基于上述两种算法,提出了beep模型下的连通控制集构造算法(Beeping a Connected Dominating Set, BCDS)。最后利用节点间的冲突提出了另一个连通控制集的构造算法(Beeping a Connected Dominating Set with Collision, BCDSC)。在一个自稳定的系统是指具有错误容忍能力的系统,即能够承受发生的错误,并且在没有外力干扰的情况下从这些短暂的错误中恢复过来。由于无线网络面临着复杂的工作环境,其拓扑变化时常发生变化,所以自稳定性是无线网络协议设计过程中必要选择。为了保证这些自稳定算法能够在实际网络中应用,还必须在协议的设计过程中考虑干扰因素。第4章解决了自稳定性与干扰的问题,基于分区与着色的思想,首先在SINR模型下提出了分布式自稳定的极大独立集构造算法(Distributed Self-Stabilizing Maximal Independent Set construction algorithm, DSS_MIS),然后在概算法的基础上进行改进最终得到了分布式自稳定的连通控制集构造算法(Distributed Self-Stabilizing Connected Dominating Set construction algorithm, DSS CDS)。第5章对本文进行了总结,并对未来进一步的研究工作进行了展望。
【学位授予单位】：曲阜师范大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TN92

【相似文献】

相关期刊论文 前10条

1 强宇,刘宗田,林炜,时百胜,李云;一种模糊概念格构造算法研究[J];计算机工程与应用;2004年29期

2 樊建席;最小T－2倍树的构造算法[J];青岛大学学报(自然科学版);1996年04期

3 杨凯;马垣;张小平;;基于属性的概念格快速渐进式构造算法[J];计算机应用与软件;2006年12期

4 杨海峰;张继福;;粗糙概念格及构造算法[J];计算机工程与应用;2007年24期

5 余远;钱旭;钟锋;李晓瑞;;基于最大概念的概念格增量构造算法[J];计算机工程;2009年21期

6 赵焕平;;圈图的点可区别强全染色算法[J];计算机与现代化;2013年09期

7 董辉;马垣;宫玺;;概念格并行构造算法研究[J];广西师范大学学报(自然科学版);2008年03期

8 郑金英;滕春霞;;概念格构造算法的现状与发展前景[J];硅谷;2011年22期

9 林春杰;普杰信;张瑞玲;;近似概念格及其增量构造算法研究[J];计算机应用研究;2012年01期

10 杜秋香;张继福;张素兰;;概念特化的概念格更新构造算法[J];智能系统学报;2008年05期

相关会议论文 前5条

1 曲立平;刘大昕;杨静;张万松;;基于属性的概念格快速渐进式构造算法[A];第二十四届中国数据库学术会议论文集（研究报告篇）[C];2007年

2 杨本良;;压缩候选的贝叶斯信念网络构造算法[A];广西计算机学会2005年学术年会论文集[C];2005年

3 申锦标;;一种新颖的概念格构造算法[A];全国第20届计算机技术与应用学术会议（CACIS·2009）暨全国第1届安全关键技术与应用学术会议论文集（上册）[C];2009年

4 高茜;周大均;李爱民;;Petri网改进的可覆盖性树的构造算法[A];全国第20届计算机技术与应用学术会议（CACIS·2009）暨全国第1届安全关键技术与应用学术会议论文集（上册）[C];2009年

5 韩锋;张鸿宾;;不连通模型上多尺度Reeb图的构造算法[A];2008'中国信息技术与应用学术论坛论文集（二）[C];2008年

相关硕士学位论文 前10条

1 张海燕;准循环LDPC码的构造算法研究[D];西安电子科技大学;2014年

2 李晓龙;基于最大闭合项集的概念构造及应用[D];燕山大学;2016年

3 姜琴;基于多属性消减的概念格构造算法研究[D];郑州大学;2016年

4 朱文君;构造概念格的权值优化改进算法研究[D];上海海洋大学;2016年

5 贾莉俐;无线网络中控制集构造算法的研究[D];曲阜师范大学;2015年

6 孙斌斌;概念三元格构造算法研究[D];西安电子科技大学;2015年

7 王绍斐;概念格构造算法的研究及其在本体中的应用[D];大连交通大学;2010年

8 刘晓今;概念三元格构造算法及应用研究[D];西安电子科技大学;2013年

9 吴新荣;全可逆递进网格构造算法研究[D];中南大学;2007年

10 黄永城;基于多核环境的基因贝叶斯网络构造算法研究与实现[D];上海交通大学;2012年

，

本文编号：2565810