WSN中连通支配集构造算法的研究

发布时间：2020-08-06 17:04

【摘要】：由于无线传感器网络(Wireless Sensor Network,WSN)具有低功耗、自组织、多跳等特点,因此被广泛应用于诸多领域,如医疗卫生、国防军事、环境监测等。目前,WSN已引起研究人员的高度关注。其中,虚拟骨干网已成为该领域的热门研究之一,它在网络中的主要作用是进行路由管理。利用图论中的连通支配集(Connected Dominating Set,CDS)在WSN中构建虚拟骨干网以构造分层网络的方法已被普遍运用。然而WSN中的节点具有能量不足以及处理和储存能力低等缺陷,因此如何均衡利用节点能量从而尽可能延长网络的生命周期成为研究的重点。本文通过对已有连通支配集构造算法的研究以及总结归纳,首先提出一种基于能量均衡改进的集中式算法(Centralized Algorithm for Improved Energy-Balance Connected Dominating Set,IEB-CDS)构造连通支配集,综合考虑节点的一跳和二跳邻居节点,剩余能量及能量阈值等影响虚拟骨干网网络周期的因素,构造节点权值公式。IEB-CDS算法分三个阶段实现。第一阶段选取具有较大权值的节点以构造一个独立集,第二阶段选取权值较大的节点连接独立集中的节点,第三阶段检查网络中是否所有节点都被支配。通过仿真实验及相关分析表明,IEB-CDS算法不仅能获得较小的连通支配集,而且可以有效地均衡整个网络的节点能量,延长了网络寿命。以上提出的算法是在无向图中进行研究的,每个节点均有相同的传输范围,然而在实际网络情况中,由于功率和功能的差异,大多数网络链路是不对称的,网络中各节点的通信范围不一定相同。针对这一问题,本文在IBE-CDS的基础上提出了一种基于有向图的强连通支配集构造算法D-SCDS(Construction Algorithm of Strongly Connected Dominating Set based on Directed graphs)。首先分析影响网络生命周期的各个因素,D-SCDS算法考虑全局网络信息,利用权值公式计算节点权值,选取权值较大的节点构造强连通支配集。通过仿真实验及相关对比分析表明,D-SCDS算法最终得到一个能量均衡,规模较小以及生命周期较长的强连通支配集。
【学位授予单位】：南昌航空大学
【学位级别】：硕士
【学位授予年份】：2019
【分类号】：TP212.9;TN929.5
【图文】：

同时也为数据转发和避免路由协议中的故障节点提供了基础。近年来，相关学者将“虚拟骨干网”（如图1-1）的概念应用于 WSN，通过虚拟骨干网进行层次拓扑结构的研究。基于虚拟骨干网的拓扑结构不仅可以尽快适应网络拓扑的变化，还可以应用于网络节点的路由过程[8]。通常，研究人员使用图论中的连通支配集（Connected Dominating Set，

的相关概念基于图（Graph），是数学的一个分支[58]。图由很多给定的点以及点之成，普遍用于表示事物间的某种关系。其中，点表示事物，点之间的线之间存在的关系。WSN 可以抽象成图来表示，图中的顶点对应 WSN 的点间的边对应 WSN 中各节点间的通信链路。因此，利用图的基本性质SN 的拓扑结构进行深入研究，从而优化网络性能。基本定义顶点集和顶点间的边集组成，一般用 G (V ,E)来表示。其中， nV v,v...,v12, 集，称 V 中的元素为顶点，n=|V|表示顶点的个数。 mE e,e,...,e12 表示 E 中的元素为边，m=|E|表示边数。实践中，网络拓扑图通常由几何图由平面上的点表示图中的顶点，顶点之间的连线表示边。如果图形的所有方向，则该图形称为为无向图。否则，称为有向图。如下图 2-1 所示

称这种图为简单无向图。通图）：对于无向图 G (V ,E)，若 v, vij 连通图。通图）：若 G (V ,E)是有向图，对于 v i jv 。当存在ijv v或j viv 时，称 G 为j viv ，则称 G 为强连通有向图。设置一个集合I ， I V，对于 vVij v , G 的一个独立集（Independent Set，I不再是 IS，则称I 为 G 的极大独立集(M 中最大顶点数的 IS 为最大独立集， （G）表示，简单表示为 。如图 2-2 的研究中，可以利用极大独立集来构

【相似文献】

相关期刊论文 前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 徐彤;WSN中连通支配集构造算法的研究[D];南昌航空大学;2019年

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

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

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

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

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

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

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

9 林霖;无线传感器网络分布式连通支配集构造方法研究[D];电子科技大学;2012年

10 陈蓓玮;加权边支配集问题的参数算法研究[D];中南大学;2009年

本文编号：2782709