导读:本文包含了最小连通支配集论文开题报告文献综述、选题提纲参考文献及外文文献翻译，主要关键词:最小,传感器,算法,网络,邻域,启发式,分布式。
最小连通支配集论文文献综述
吴明功,李佳威,温祥西,刘飞[1]（2019）在《基于免疫粒子群的最小连通支配集求解算法》一文中研究指出为解决复杂网络最小连通支配集(MCDS)求解算法复杂度高、速度慢及解的精确度差等问题,采用一种免疫粒子群优化(IPSO)算法进行求解.该算法将连通支配集的支配规则转化为基于邻接矩阵的并集约束,并结合图连通分支约束设计优化目标,采用二进制粒子群算法对MCDS进行求解.在求解过程中引入免疫机制,依据网络关键节点与支配节点之间的重迭关系,设置抗原因子,指导粒子群搜索方向、加快算法收敛速度.在随机网络上的仿真实验表明:相较于传统算法,所提算法能够找出网络的MCDS,并且在保证解精度的前提下提高了求解速度.(本文来源于《华中科技大学学报(自然科学版)》期刊2019年11期）
李佳威,吴明功,温祥西,刘飞[2]（2019）在《基于最小连通支配集的复杂网络关键节点与连边识别方法》一文中研究指出复杂网络关键节点与关键连边在网络中均起着十分重要的作用,目前的识别方法往往无法做到同时识别,并且识别指标角度较为单一。为解决上述问题,提出一种基于最小连通支配集(minimum connected dominating set,MCDS)的复杂网络关键节点与连边识别方法,通过使用免疫粒子群(immune particle swarm optimization,IPSO)算法寻找网络最小连通支配集,构建核心骨干网,实现对复杂网络关键节点与连边的同时识别。该算法在求解过程中引入免疫机制指导粒子节点搜索方向、加快算法收敛速度,同时优化搜索节点质量。经实验验证表明,所提识别方法能够有效识别网络中的关键节点与关键连边。(本文来源于《系统工程与电子技术》期刊2019年11期）
王彬,孙德峰[3]（2017）在《最小连通支配集问题的分解算法》一文中研究指出在无线网络设计中,连通支配集(CDS)有着广泛的应用。针对最小连通支配集问题(MCDSP),提出了基于Benders的分解算法进行最优求解。将原问题分解为较易求解的最小支配集主问题和连通性子问题,其中主问题能够生成最小支配集,子问题负责判断所生成的最小支配集的连通性。若不连通,生成相应的Benders cut对主问题进行修正和进一步限定。在上述Benders算法中,主问题与子问题均为纯整数规划。在此基础上,分析了最小连通支配集问题的上下界性质,通过构造容易求解的辅助问题,并结合二分法思想进一步降低问题的搜索空间,设计了改进的Benders分解算法,加速算法收敛速度。通过计算实验与现有文献中的分解算法进行对比,证明了所提分解算法的优越性。(本文来源于《沈阳师范大学学报(自然科学版)》期刊2017年04期）
万欣[4]（2016）在《迭代禁忌搜索算法求解最小连通支配集问题》一文中研究指出在无线传感器网络中,由于没有固定的基础网络设施,传感器节点以广播的形式进行通信,容易引起广播风暴等问题。为了提高网络带宽的利用率,降低传感器能源消耗,通常利用连通支配集在无线传感器网络中虚拟出一个骨干网络,作为通信的中继节点。然而,最小连通支配集的构造作为一个全局优化问题,已被证明是一个NP难问题,因此越来越多的学者对在无线传感器网络中构造最小连通支配集这一问题开展了广泛又深入的研究。本文以静态的无线传感器网络为研究目标,结合启发式算法理论,提出了一种基于集合划分的迭代禁忌搜索启发式算法(RSN-TS)来求解最小连通支配集问题。算法主要利用集合划分的思想,将网络中不同的节点置于不同集合之中,然后利用迭代禁忌搜索启发式算法进行快速评估、迭代、交换各集合中的节点,从而获得近似最小连通支配集或求解出最小连通支配集。通过对国际公共算例的测试,并与其他学者所提出的精确算法,启发式算法的对比实验发现,本文所提出的RSN-TS算法是求解最小连通支配集问题的高效算法。此外,本文还分析了一些影响RSN-TS算法性能的关键部件,对算法中使用到的快速增量评估技术,扰动机制以及禁忌搜索算法做了不同的对比实验。(本文来源于《华中科技大学》期刊2016-05-01）
王灵敏,周淘晴,吴歆韵,吕志鹏[5]（2016）在《求解最小连通支配集问题的变深度邻域搜索算法》一文中研究指出本文提出了一种求解最小连通支配集问题的变深度邻域搜索(VDNS)算法.结合最小连通支配集问题的特点,VDNS算法采用了一种高效的邻域结构,该邻域结构由一系列基础邻域动作组成,合理地限制了搜索空间,提高了算法的搜索效率.同时,本文还提出了两种提高算法搜索效率的方法:修剪搜索分支以及增量评估更新技术.用本文提出的VDNS算法对当前国际文献公开的共91个算例进行了测试,VDNS算法能够在非常短的计算时间内改进其中38个算例,优于此前国际文献中报道的最好结果,表明了本文所提出的VDNS算法的有效性.(本文来源于《中国科学:信息科学》期刊2016年04期）
任思君[6]（2015）在《最小连通支配集算法研究》一文中研究指出最小连通支配集在无线传感器网络(Wireless Sensor Networks,WSN)中发挥着重要的作用,它可以作为一个“虚拟骨干网”从而可以减少节点的能量损耗、网络拓扑维护的开销,减轻广播风暴的影响等。构造一个最小连通支配集被证明是一个NP完全问题,并且无线传感器网络中的节点具有能量、存储和计算方面的约束,以及无线传感器网络的无中心自组织成网、多跳通信的特征,因此许多学者对在无线传感器网络中构造最小连接支配集这一问题展开了广泛而又深入的研究。作者以静态的无线传感器网络为研究目标,设计了四个近似最小连通支配集的分布式算法。算法-Ⅰ是一个完全异步并行的算法,网络中的每个节点异步并同时执行相同的算法且只根据一跳邻居的消息来决定自己是否加入连通支配集。根据最大独立集亦是一个支配集,算法-Ⅰ首先构造一个最大独立集,然后通过“信息叁跳中继”结合相应的规则使其它一些节点加入最大独立集,使最大独立集连通,最终生成连通支配集。在算法-Ⅱ中,以“有效度”代替节点的度数来作为选取属于最大独立集中的支配点的标准,可以有效减少生成的连通支配集的大小。算法-Ⅰ与算法-Ⅱ构建的近似最小连通支配集的收敛时间与网络规模、拓扑结构等直接相关,存在收敛时间不可直接控制和估计等问题。因此作者设计了算法-Ⅲ。算法-Ⅲ分为两个阶段,分别为初始化阶段和状态更新阶段。通过对不同规模和拓扑结构的无线传感器网络进行计算机仿真,可以得到构造近似最小连通支配集所需的相关时间参数。在算法-Ⅳ中,作者首次提出把两个支配点之间的节点个数等效转化成带有权值的路径,从而转化成有权图,然后在这个图中找到一个最小生树来对连通支配集进行优化的思想。实验仿真结果表明,算法-Ⅳ具有非常出色的性能表现。(本文来源于《上海交通大学》期刊2015-06-30）
辛强伟[7]（2015）在《基于最小连通支配集的无线传感器网络容错研究》一文中研究指出过多的跳数对于无线传感器网络容错是不利的。无线传感器网络以往的研究中最小连通支配集主要是作为骨干网来使用,通过结合度来构建最小连通支配集,使得所构建的最小连通支配集不仅具备骨干网的功能,还具有容错的作用。提出了构建具有容错作用的基于度的最小连通支配集算法,仿真证明该算法可以有效地减少无线传感器网络的跳数,从而达到增强无线传感器网络容错的目的。(本文来源于《计算机工程与应用》期刊2015年11期）
吴振华,米凡,谭波峰[8]（2014）在《能量均衡的最小2-连通2-支配集的分布式算法》一文中研究指出在无线传感器网络中,一般通过构造连通支配集形成虚拟骨干网来分层路由.现有算法通常只考虑如何获得规模较小的支配集,忽略网络自身的不稳定性,使得节点失效或链路失败经常发生.针对连通支配集的容错能力,结合节点度与能量因素,提出一种能量均衡的最小2-连通2-支配集的分布式算法(DA-EBM).Omnet仿真实验表明,DA-EBM算法构造的容错连通支配集能有效均衡能量消耗,延长网络生命周期.(本文来源于《计算机系统应用》期刊2014年08期）
周杰,姚雷,杜景林[9]（2014）在《基于最小连通支配集移动的WSANs连接恢复算法》一文中研究指出在无线传感器与执行器网络(wireless sensor-actor networks,简称WSANs)关键任务应用中,单个或多个节点的失效可能造成内执行器节点产生网络分隔,自动检测和快速恢复来保持内执行器网络的连接性显得非常重要.论文提出了一种基于最小连通支配集移动的连接性恢复算法(minmal CDS motion-based connectivity recovery,简称MCDSR),该算法主动探测影响网络连通的割点,并为其指定最小的连通支配集.一旦检测到节点失效,备份的支配集初始化恢复进程直到网络连接恢复.并通过实验与现有的恢复算法进行比较,发现MCDSR算法在移动的节点数目、总的移动距离、覆盖度减少等方面有更好性能.(本文来源于《安徽大学学报(自然科学版)》期刊2014年03期）
鲁登月,樊建席,刘文军,张标[10]（2014）在《一种能量均衡的最小连通支配集构造算法》一文中研究指出针对无线传感器网络中没有固定的基础设施问题,提出一种能量均衡的最小连通支配集构造算法,该算法首先为网络构造一个极大独立集,然后选择最少的连接节点使极大独立集连通,并在使极大独立集连通时加入了修剪规则,使连通支配集规模更小,最后,针对网络拓扑变化导致连通支配集重构问题,提出了局部构造最小连通支配集算法.通过优先选择能量多、度数大的节点来构造连通支配集,并考虑了连通支配集重构问题,使网络中节点能量消耗更加均衡,从而有效地延长了网络寿命.理论分析和实验结果表明,与相关的分布式算法相比,本文算法产生的连通支配集在规模上更优,网络寿命更长.(本文来源于《小型微型计算机系统》期刊2014年03期）
最小连通支配集论文开题报告
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
复杂网络关键节点与关键连边在网络中均起着十分重要的作用,目前的识别方法往往无法做到同时识别,并且识别指标角度较为单一。为解决上述问题,提出一种基于最小连通支配集(minimum connected dominating set,MCDS)的复杂网络关键节点与连边识别方法,通过使用免疫粒子群(immune particle swarm optimization,IPSO)算法寻找网络最小连通支配集,构建核心骨干网,实现对复杂网络关键节点与连边的同时识别。该算法在求解过程中引入免疫机制指导粒子节点搜索方向、加快算法收敛速度,同时优化搜索节点质量。经实验验证表明,所提识别方法能够有效识别网络中的关键节点与关键连边。
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
最小连通支配集论文参考文献
[1].吴明功,李佳威,温祥西,刘飞.基于免疫粒子群的最小连通支配集求解算法[J].华中科技大学学报(自然科学版).2019
[2].李佳威,吴明功,温祥西,刘飞.基于最小连通支配集的复杂网络关键节点与连边识别方法[J].系统工程与电子技术.2019
[3].王彬,孙德峰.最小连通支配集问题的分解算法[J].沈阳师范大学学报(自然科学版).2017
[4].万欣.迭代禁忌搜索算法求解最小连通支配集问题[D].华中科技大学.2016
[5].王灵敏,周淘晴,吴歆韵,吕志鹏.求解最小连通支配集问题的变深度邻域搜索算法[J].中国科学:信息科学.2016
[6].任思君.最小连通支配集算法研究[D].上海交通大学.2015
[7].辛强伟.基于最小连通支配集的无线传感器网络容错研究[J].计算机工程与应用.2015
[8].吴振华,米凡,谭波峰.能量均衡的最小2-连通2-支配集的分布式算法[J].计算机系统应用.2014
[9].周杰,姚雷,杜景林.基于最小连通支配集移动的WSANs连接恢复算法[J].安徽大学学报(自然科学版).2014
[10].鲁登月,樊建席,刘文军,张标.一种能量均衡的最小连通支配集构造算法[J].小型微型计算机系统.2014
论文知识图
