极端环境下自组织网络的拓扑控制与连通恢复

发布时间：2017-10-20 07:00

  本文关键词：极端环境下自组织网络的拓扑控制与连通恢复

  更多相关文章： 极端环境 自组织网络 拓扑控制 连通恢复

【摘要】：随着电子技术的飞速发展,自组织网络(ad hoc networks)在我们日常工作和生活中应用越来越广泛,特别是在网络基础设施不可用的极端环境中,如矿井监测、环境监测、军事侦查、水下监测、海岸线监测和目标跟踪等。容延／容断网络、断续连接的移动自组织网络、机会性网络都可以看作是这种网络。但是,极端环境中的自组织网络节点自身资源有限,在恶劣环境中易被损坏,且可能移动,从而造成不确定和断续的网络连接环境,从而使得数据不能及时传输,严重时甚至会导致网络分割成若干不相连的孤岛。因此如何在极端环境下实现数据的有效传输,对网络进行有效的拓扑控制,在网络出现分割时恢复连通性非常重要。 本文主要研究极端环境下自组织网络的拓扑控制和连通恢复问题,面向数据路由的需求生成网状的拓扑结构,面向数据收集的需求生成树状的拓扑结构,实现有效的数据传输;对于极端环境下遭到严重破坏的网络作了网络连通恢复方面的研究,部署尽量少的额外节点连接分割的孤岛。本文的主要贡献如下： (1)面向路由需求提出了一种基于概率的拓扑控制方法,均衡可预测DTNs的能耗和连接质量,以最小能耗代价保证每对节点间的连接概率最大或达到一个特定的阈值。PDTNs被抽象为三维时空带权有向图,不仅包含时间和空间信息,还包含能耗和连接概率等信息。拓扑控制问题被定义为寻找三维时空带权有向图的子图并且满足以下条件：节点间连接概率最大或满足一个给定的阈值,且总能耗最小。该问题被证明是NP完全问题,故提出了两种启发式拓扑控制算法,在不同链路密度和连接概率阈值情况下作了模拟实验,对平均连通概率、能耗比、边数比等指标进行了分析,与已有的算法进行了比较。实验表明这两种算法能够以较低的能耗实现有可靠性保证的数据传输。 (2)面向数据收集需求提出了一种树形拓扑控制方法,主要考虑了时延和能耗两个因素,在满足时延需求的前提下寻找能耗最小且可以将可预测DTNs中所有节点的数据收集到一个汇聚节点的生成树。此方法将PDTNs抽象为时空带权有向图模型,并进一步简化为简化融合带权有向图。拓扑控制问题被定义为在时空带权有向图或简化融合带权有向图中寻找生成树,该树要包含网络中的所有节点且满足以下条件1)生成树上的总能耗最小;2)满足性能需求,主要是时延这一因素。时延通过计算最终找到的生成树中最深路径上时间边的个数来获得。该问题也是一个NP完全问题,故分别提出了三种启发式算法,并分别基于随机产生的数据集和实际数据集进行了模拟实验,在不同链路密度和时延阈值下基于能耗比、时延等指标进行了实验比较,实验结果表明这三种算法在保证数据成功传输的前提下,大大减小了能耗,缩短了数据传输时延。 (3)针对极端环境下网络可能遭到大规模损坏的情况,提出了一种极端环境下的基于四边形斯坦纳树的网络连通恢复方法。在极端环境下,网络中的节点和通信链路常常会失效,致使网络被分割为很多分离的分区,通过布置尽量少的中继节点实现高健壮性的连通恢复对于维持网络的正常运作必不可少。对于一个被分割的网络,找到相应的位置布置最少中继节点恢复连通是一个NP难题,在实际应用中只能采用启发式算法。基于四边形斯坦纳树的网络连通恢复算法首先探测出各分区并确定各分区的代表节点及其位置,然后寻找合适的四边形连接分割的网络分区,确定这些四边形的斯坦纳点；对无法用四边形连接的各连接部分用三角形斯坦纳树或最小生成树的方法连接;最后沿着斯坦纳树的边在相应位置布置中继节点,实现网络连通的恢复。基于部署节点个数、平均节点连通度等指标对提出的算法与已有的算法做了比较,仿真实验表明文中提出的方法能够减少所需中继节点的数量,恢复后的拓扑结构节点的连通度更高,容错性更好。
【关键词】：极端环境 自组织网络 拓扑控制 连通恢复
【学位授予单位】：华中科技大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：TN929.5
【目录】：

• 摘要4-6
• ABSTRACT6-11
• 1 引言11-32
• 1.1 选题背景和研究意义11-12
• 1.2 国内外研究现状12-29
• 1.3 主要研究内容29-31
• 1.4 本文的组织结构31-32
• 2 面向路由的拓扑控制32-52
• 2.1 概述32-33
• 2.2 系统模型和问题描述33-40
• 2.3 面向路由的拓扑控制算法40-44
• 2.4 性能评价与分析44-50
• 2.5 本章小结50-52
• 3 面向数据收集的树形拓扑控制52-67
• 3.1 系统模型和问题描述52-54
• 3.2 面向数据收集的树形拓扑控制算法54-62
• 3.3 性能评价与分析62-66
• 3.4 本章小结66-67
• 4 极端条件下的网络连通恢复67-87
• 4.1 概述67-68
• 4.2 系统模型68-69
• 4.3 基于四边形斯坦纳树连通恢复算法69-82
• 4.4 性能评价与分析82-85
• 4.5 本章小结85-87
• 5 总结与展望87-90
• 5.1 本文工作总结87-88
• 5.2 下一步工作展望88-90
• 致谢90-91
• 参考文献91-101
• 附录1 攻读博士学位期间发表的主要论文101-102
• 附录2 博士生期间参与的课题研究情况102

【相似文献】

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

1 张学;龚海刚;刘明;;无线传感器网络拓扑控制的理论探讨[J];计算机科学;2010年10期

2 邓建良;王景;胡松华;郭建丁;;无线Mesh网络结构的拓扑控制策略[J];无线电通信技术;2011年04期

3 许蒙蒙;杨清海;;局部信息约束下的拓扑控制[J];北京邮电大学学报;2014年S1期

4 邹超伟;;传感器网络层次拓扑控制关键问题研究[J];科技信息;2009年03期

5 陈晶;刘亚斌;刘建东;赵黎;林青云;杜瑞颖;;无线Mesh网络中基于人工免疫的容错拓扑控制[J];山东大学学报(理学版);2012年09期

6 陈争宝;陈旺虎;;面向任务型无线传感器网络的拓扑控制方法[J];计算机工程;2013年04期

7 张学;陆桑璐;陈贵海;陈道蓄;谢立;;无线传感器网络的拓扑控制[J];软件学报;2007年04期

8 卞永钊;于海斌;曾鹏;;无线传感器网络中的拓扑控制[J];计算机应用研究;2008年10期

9 甘从辉;郑国强;唐盛禹;;无线传感器网络的拓扑控制研究[J];计算机应用研究;2009年09期

10 赵学健;王晓军;;适用于传感网的拓扑控制策略β-STC[J];计算机应用;2013年S2期

中国重要会议论文全文数据库 前3条

1 许蒙蒙;杨清海;;局部信息约束下的拓扑控制[A];2013年全国通信软件学术会议论文集[C];2013年

2 胡贵龙;郑宝龙;;MANET中基于拓扑控制的节能策略[A];现代通信理论与信号处理进展——2003年通信理论与信号处理年会论文集[C];2003年

3 董明杰;裴庆祺;楼顺天;;基于网格的Voronoi无线传感器网络成簇拓扑控制[A];2006全国复杂网络学术会议论文集[C];2006年

中国重要报纸全文数据库 前1条

1 李铭;拓扑控制[N];计算机世界;2004年

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

1 谭倩;能量获取无线传感器网络路由及拓扑控制优化研究[D];重庆大学;2015年

2 田一鸣;无标度网络拓扑控制优化及应用研究[D];合肥工业大学;2015年

3 陈洪生;极端环境下自组织网络的拓扑控制与连通恢复[D];华中科技大学;2015年

4 张建辉;无线传感器网络拓扑控制研究[D];浙江大学;2008年

5 沈耀;无线Ad Hoc网络的拓扑控制[D];上海交通大学;2007年

6 周坤晓;无线Mesh网络中访问点部署与拓扑控制的研究[D];武汉大学;2012年

7 向毅;无线传感器网络能量平衡的拓扑控制研究[D];重庆大学;2010年

8 熊书明;可生存的传感网拓扑控制方法研究[D];江苏大学;2011年

9 孙超;基于拓扑控制的无线传感器网络节能与容错算法研究[D];燕山大学;2010年

10 贺鹏;移动Ad Hoc网络中路由与拓扑控制技术的研究[D];西安电子科技大学;2007年

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

1 杨海俊;基于QoS的无线传感器网络拓扑控制的研究[D];上海师范大学;2015年

2 宋鑫;Ad Hoc网络自适应拓扑控制与实现[D];电子科技大学;2015年

3 任新波;基于进化计算的Ad Hoc拓扑控制研究[D];西安电子科技大学;2014年

4 黄晨程;基于博弈论的UWSNs拓扑控制技术研究[D];南京邮电大学;2015年

5 罗缔;实时应用场景中的WSNs拓扑控制与路由算法研究[D];南昌航空大学;2015年

6 于博洋;基于发射功率调整的无线传感器网络的拓扑控制[D];南开大学;2009年

7 赵琳;面向干扰优化的传感网拓扑控制[D];北京林业大学;2015年

8 沈自伟;无线Mesh网络中的接入点部署与拓扑控制研究[D];电子科技大学;2013年

9 魏亚青;Ad Hoc网络拓扑控制及其分簇研究[D];中南大学;2009年

10 吴志斌;无线传感器网络自适应拓扑控制研究[D];河南大学;2009年

，

本文编号：1065863