无线传感器网络中连通控制集问题的研究

发布时间：2017-11-21 09:08

  本文关键词：无线传感器网络中连通控制集问题的研究

  更多相关文章： 无线传感器网络 圆盘图 最小k-连通m-控制集 最小m-连通k-全控制集

【摘要】： 随着传感器技术的快速发展和大众对无线传感器网络(wireless sensor network, WSN)应用前景的日益重视,国内外对无线传感器网络的研究越来越多、越来越深入。其中,由于无线传感器网络是一个没有基础设施的自组织无线移动网络并且传感器网络中的节点很容易发生故障或者能量耗尽导致通信中断。因此,在网络中通过建立多连通多控制集来构造容错的虚拟骨干(virtual backbone)来负责数据的路由转发成为目前学术界的一个热点问题。 鉴于传感器网络具有很好的平面结构和连通控制集的良好性质,本文主要在圆盘图中研究了传感器网络的最小多连通多控制集问题。首先,本文对现有的连通控制集问题进行了分析和总结。其次,本文在现有的理论成果的基础上,给出了针对在节点传输半径可变的一般圆盘图中的最小k-连通m-控制集问题的新型算法和新型分析方法。该算法主要分为四步：一、用贪婪算法和染色机制构造一个连通控制集；二、通过不断地选择极大独立集k-1次构造一个k-控制集,使得除了控制集外的每个节点被控制集中至少k个节点所控制；三、用贪婪算法选择连通控制集中的节点,通过选取块k-1次使得连通k-控制集k-连通；四、选择极大独立集m-k次构造k-连通m-控制集(其中,k,m为任意正整数且m不小于k),并通过理论分析得到该近似算法的近似比。最后,我们提出了新的研究模型,即在节点传输半径可变的圆盘图中研究最小m-连通k-全控制集问题(其中,k,m为任意正整数),对这一问题给出新的算法并进行了理论分析。
【学位授予单位】：北京邮电大学
【学位级别】：硕士
【学位授予年份】：2010
【分类号】：TN929.5;TP212.9

【共引文献】

中国期刊全文数据库 前10条

1 王琳珠;范亚芹;胡可刚;;基于Ad Hoc的有效广播路由算法[J];吉林大学学报(信息科学版);2009年01期

2 张静,孙雨耕,房朝晖;能量有效的最小连通支配集近似算法[J];传感技术学报;2004年04期

3 孙彦景;钱建生;顾相平;陈光柱;;联合约束无线传感器网络连通支配集算法[J];电子科技大学学报;2009年02期

4 孙彦景;钱建生;顾相平;陈光柱;;时延和功耗约束无线传感器网络连通支配集算法(英文)[J];Journal of Southeast University(English Edition);2008年04期

5 唐勇;周明天;;基于极大独立集的最小连通支配集的分布式算法[J];电子学报;2007年05期

6 许力,郑宝玉;MANET环境下基于能量保护的路由策略及其研究进展[J];电子与信息学报;2005年05期

7 谭国真;黄利华;;基于骨干子网内竞争的Internet自治域层演化模型[J];复杂系统与复杂性科学;2007年03期

8 陈涛;郭得科;罗雪山;陈洪辉;;一种基于移动基站的无线传感器网络数据收集方法[J];国防科技大学学报;2011年02期

9 郑婵;尹令;张义青;;监测奶牛无线传感器网络的连通支配集构造[J];广西大学学报(自然科学版);2012年02期

10 王玉明;赵大胜;;基于串行最大独立集的连通支配集构造及分析[J];华中科技大学学报(自然科学版);2011年03期

中国博士学位论文全文数据库 前10条

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

2 赵楠楠;无线传感器网络拓扑控制算法研究[D];北京邮电大学;2011年

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

4 焦贤龙;无线自组网广播与数据聚合算法研究[D];国防科学技术大学;2011年

5 王旭东;基于图论的智能电网最优孤岛划分模型和算法[D];天津大学;2011年

6 马娅婕;MPLS网络拓扑聚合算法的研究[D];华中科技大学;2005年

7 赵大胜;无线传感器网络广播与节点休眠算法中的节能覆盖问题研究[D];华中科技大学;2005年

8 胡鹏;无线自组网路由关键技术的研究[D];中国科学技术大学;2006年

9 张磊;移动自组网络协议关键技术研究[D];国防科学技术大学;2005年

10 汪学清;无线传感器网络中连通与覆盖问题研究[D];哈尔滨工程大学;2006年

中国硕士学位论文全文数据库 前10条

1 刘兰涛;无线传感器网络中时间同步技术的研究[D];郑州大学;2010年

2 王楠楠;无线网络中基于CDS的拓扑控制算法研究[D];曲阜师范大学;2011年

3 朱韬;移动Ad hoc网络中文件广播分发算法的研究与实现[D];杭州电子科技大学;2011年

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

5 张军;关于无线传感器网络虚拟骨干网构造算法的研究[D];电子科技大学;2011年

6 王怀彩;基于图论的移动Ad Hoc网络分群算法研究[D];青岛理工大学;2010年

7 侯加涛;延迟容忍移动传感器网络中基于接收者的分阶段数据传输协议[D];湖南科技大学;2011年

8 韩希先;基于分类树的P2P电子商务平台搜索机制的研究[D];哈尔滨工业大学;2006年

9 李嘉琳;复杂网络核心子网的构造及特性分析[D];大连理工大学;2006年

10 王雪瑜;无线传感器网络虚拟骨干网的构造研究[D];哈尔滨工业大学;2006年

，

本文编号：1210385