期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息
共找到62篇文章
< 1 2 … 4 >
每页显示 20 50 100
已选择0条
导出题录 引用分析
参考文献
引证文献
 统计分析
检索结果
已选文献
显示方式：
局部搜索算法求解最小弱连通支配集问题
1
作者 李睿智 何锦涛 欧阳丹彤 《软件学报》 北大核心 2025年第8期3655-3676,共22页
最小弱连通支配集问题是一个经典的NP难问题,在许多领域都有广泛的应用.提出一种高效的局部搜索算法求解该问题.在该算法中,首先采用一个基于锁定顶点和频率反馈信息的初始解构造方法.该方法可以确保将一定处于最优解中的顶点和大概率... 最小弱连通支配集问题是一个经典的NP难问题,在许多领域都有广泛的应用.提出一种高效的局部搜索算法求解该问题.在该算法中,首先采用一个基于锁定顶点和频率反馈信息的初始解构造方法.该方法可以确保将一定处于最优解中的顶点和大概率存在于最优解中的顶点添加到初始解中,从而可以得到高质量的初始解.其次,提出基于双层格局检测策略,年龄属性和禁忌策略的方法来避免循环问题.第三,提出扰动策略,使得算法能够有效跳出局部最优.第四,将两个评分函数Dscore和Nscore与避免循环问题的策略相结合,提出有效的顶点选择方法,帮助算法选择适合添加到候选解中或从当前候选解中删除的顶点.最后,与现有的最优启发式算法和CPELX求解器,在4组基准测试实例上对提出的局部搜索算法进行了对比.实验结果表明,该算法在4组经典基准测试实例上表现出更好的性能. 展开更多
关键词 最小弱连通支配集问题 组合优化 局部搜索 反馈机制 扰动策略 年龄属性
在线阅读 下载PDF
最小支配阈值集问题的降阶回溯算法
2
作者 储旭 宁爱兵 +2 位作者 胡开元 代苏玉 张惠珍 《计算机工程与科学》 CSCD 北大核心 2024年第5期897-906,共10页
图论中的最小支配阈值集问题是组合优化中的一个NP-Hard问题,该问题是最小支配集问题的一个扩展问题。基于给定无向图G=(V,E)和阈值r的最小支配阈值集问题进行研究,首先得出一些可以降低问题规模的数学性质并证明,利用这些性质可以减小... 图论中的最小支配阈值集问题是组合优化中的一个NP-Hard问题,该问题是最小支配集问题的一个扩展问题。基于给定无向图G=(V,E)和阈值r的最小支配阈值集问题进行研究,首先得出一些可以降低问题规模的数学性质并证明,利用这些性质可以减小问题规模,降低问题的求解难度;然后设计出上界子算法、下界子算法和降阶子算法,并基于这些子算法提出了一种可以减小问题规模同时得到最优解的降阶回溯算法BAR;最后,通过一个示例分析和若干随机算例测试验证了降阶回溯算法可有效降低问题的求解难度。 展开更多
关键词 最小支配阈值集问题 数学性质 上下界算法 降阶回溯算法
在线阅读 下载PDF
求解最小支配集问题的禁忌遗传混合算法
3
作者 吴歆韵 彭瑞 熊才权 《湖北工业大学学报》 2024年第2期17-22,共6页
将最小支配集问题转换为一系列判定问题k支配集问题,并提出一种禁忌遗传混合算法对k-DS问题进行求解。此算法将禁忌搜索算法和遗传算法两种启发式算法结合起来,互补不足。高效的邻域结构保证了算法的运行效率,禁忌策略防止算法过早陷入... 将最小支配集问题转换为一系列判定问题k支配集问题,并提出一种禁忌遗传混合算法对k-DS问题进行求解。此算法将禁忌搜索算法和遗传算法两种启发式算法结合起来,互补不足。高效的邻域结构保证了算法的运行效率,禁忌策略防止算法过早陷入局部最优陷阱,遗传算法框架进一步增强了算法的疏散性。经过与现有求解最小支配集算法的结果进行分析比较,禁忌遗传混合算法的结果较其它算法更优。 展开更多
关键词 最小支配集 NP难问题 禁忌遗传混合算法 k支配集
在线阅读 下载PDF
WSNs中基于能量代价的最小权和支配集拓扑控制算法 被引量：11
4
作者 孙超 尹荣荣 +1 位作者 郝晓辰 刘彬 《电子与信息学报》 EI CSCD 北大核心 2010年第4期857-863,共7页
该文针对无线传感器网络中最小连通支配集拓扑并非网络耗能最小拓扑的问题,定义由节点剩余能量,邻居个数和通信代价构建的能量代价函数综合反映支配节点的能量效率以及对降低网络整体能耗的贡献,进而以其作为拓扑权值,提出一种基于能量... 该文针对无线传感器网络中最小连通支配集拓扑并非网络耗能最小拓扑的问题,定义由节点剩余能量,邻居个数和通信代价构建的能量代价函数综合反映支配节点的能量效率以及对降低网络整体能耗的贡献,进而以其作为拓扑权值,提出一种基于能量代价的最小权和连通支配集拓扑控制算法。算法选取局部最小权值节点担负支配任务,搭建整体权和最小的支配集,最小化网络整体能耗。实验结果表明,算法不仅具有节能的特点,还确保了通信链路的可靠性,有效延长了网络生命周期。 展开更多
关键词 无线传感器网络 拓扑控制 能量代价 最小权和连通支配集
在线阅读 下载PDF
一个新的分布式最小连通支配集近似算法 被引量：42
5
作者 彭伟 卢锡城 《计算机学报》 EI CSCD 北大核心 2001年第3期254-258,共5页
在计算机网络中广泛使用广播来解决一些网络问题 ,设计有效的广播算法是一项重要的课题 .文中提出了一种分布地计算网络最小连通支配集的近似算法并给出了它的正确性证明 .它只需要网络节点具有局部的网络状态信息 ,可伸缩性强 .通过此... 在计算机网络中广泛使用广播来解决一些网络问题 ,设计有效的广播算法是一项重要的课题 .文中提出了一种分布地计算网络最小连通支配集的近似算法并给出了它的正确性证明 .它只需要网络节点具有局部的网络状态信息 ,可伸缩性强 .通过此算法可以在网络中自动形成一个虚拟骨干网 ,从而可为网络中的广播和路由操作提供一个有效的通信基础 .模拟结果表明 ,文中提出的算法求得的连通支配集小 ,能较好地应用于一般网络以及移动自组网络中 . 展开更多
关键词 广播 移动自组网络 最小连通支配集 分布式算法 计算机网络
在线阅读 下载PDF
基于图着色的无线自组网极小连通支配集算法 被引量：17
6
作者 许力 林志伟 《通信学报》 EI CSCD 北大核心 2007年第3期108-114,共7页
基于连通支配集算法的虚拟主干网技术对于无线自组网的路由优化、能量保护和资源分配都具有重要的作用。通过引入极大独立集和极小支配集概念,基于图着色思想提出一种新的适合于无线自组网的极小连通支配集算法,从理论上证明了该算法的... 基于连通支配集算法的虚拟主干网技术对于无线自组网的路由优化、能量保护和资源分配都具有重要的作用。通过引入极大独立集和极小支配集概念,基于图着色思想提出一种新的适合于无线自组网的极小连通支配集算法,从理论上证明了该算法的正确性和高效性,也通过仿真实验分析了该算法在多种情况下的实际性能,仿真结果表明新算法在簇头和主干节点数目方面具有较好的性能,特别在节点密集的网络环境中更加突出。 展开更多
关键词 无线自组网 极小连通支配集 极小支配集 极大独立集 图着色
在线阅读 下载PDF
一种求解最小连通支配集的高效近似算法 被引量：8
7
作者 廖飞雄 马良 范炳全 《小型微型计算机系统》 CSCD 北大核心 2008年第5期875-878,共4页
寻找出一个网络图的最小连通支配集有重要实际应用背景,然而如何找到它却是一个NP难题.本文设计了一种简单且高效的近似启发式算法构造网络图的连通支配集,该算法分为三个阶段:首先为顶点分配等级和生成顶点次序表,其次构造一个极大独立... 寻找出一个网络图的最小连通支配集有重要实际应用背景,然而如何找到它却是一个NP难题.本文设计了一种简单且高效的近似启发式算法构造网络图的连通支配集,该算法分为三个阶段:首先为顶点分配等级和生成顶点次序表,其次构造一个极大独立集,最后连接极大独立集中顶点.模拟实验表明该算法无论在运行时间和结果上都达到良好的效果. 展开更多
关键词 最小连通支配集 极大独立集 启发式算法
在线阅读 下载PDF
分布式最小连通支配集启发式算法 被引量：5
8
作者 陈勤 范文涛 张旻 《计算机工程》 CAS CSCD 北大核心 2009年第10期92-94,共3页
针对Ad Hoc网络中用洪泛法进行广播易引起广播风暴的问题,提出一个新的分布式最小连通支配集启发式算法HMCDS,其中包括构建极大独立集、引入节点的有效度概念、选择有效度最大的节点作为支配点的贪心策略的方法,实验结果证明,HMCDS算法... 针对Ad Hoc网络中用洪泛法进行广播易引起广播风暴的问题,提出一个新的分布式最小连通支配集启发式算法HMCDS,其中包括构建极大独立集、引入节点的有效度概念、选择有效度最大的节点作为支配点的贪心策略的方法,实验结果证明,HMCDS算法生成的连通支配集大小为7.6opt+1.4,时间复杂度为O(△2),消息复杂度为O(n),比同类算法优秀。 展开更多
关键词 有效度 支配节点 极大独立集 最小连通支配集
在线阅读 下载PDF
基于极大独立集的最小连通支配集的分布式算法 被引量：21
9
作者 唐勇 周明天 《电子学报》 EI CAS CSCD 北大核心 2007年第5期868-874,共7页
全网范围的广播在无线传感器网络和移动自组织网络中有着广泛的应用.为节省网络资源,减少冗余转发节点成为广播中需解决的关键问题.广播过程中最小化参与转发节点数问题与图论中求解最小连通支配集问题等价,而在任意图中求解最小连通支... 全网范围的广播在无线传感器网络和移动自组织网络中有着广泛的应用.为节省网络资源,减少冗余转发节点成为广播中需解决的关键问题.广播过程中最小化参与转发节点数问题与图论中求解最小连通支配集问题等价,而在任意图中求解最小连通支配集是NP完全问题.本文基于极大独立集,提出了一种求解最小连通支配集的分布式算法(MISB),并证明了算法的正确性.仿真结果表明,使用该算法能得到较小的连通支配集,从而有效减少网络广播过程中的转发节点数,大大节省了网络资源. 展开更多
关键词 无线传感器网络 移动自组织网络 广播 极大独立集 最小连通支配集
在线阅读 下载PDF
能量有效的最小连通支配集近似算法 被引量：7
10
作者 张静 孙雨耕 房朝晖 《传感技术学报》 CAS CSCD 2004年第4期603-606,610,共5页
针对无线自组传感器网络中有效路由提出的一种能量有效的最小连通支配集近似算法EEMCDS(Energy Effi cientminimumconnecteddominatingset) ,路由搜索主要集中在连通支配集内。本文提出一个能量有效的简洁有效的分布式算法 ,该算法根据... 针对无线自组传感器网络中有效路由提出的一种能量有效的最小连通支配集近似算法EEMCDS(Energy Effi cientminimumconnecteddominatingset) ,路由搜索主要集中在连通支配集内。本文提出一个能量有效的简洁有效的分布式算法 ,该算法根据各节点所具有的能量不同 ,优先选择高能量的节点作为连通支配集节点 ,可以有效地延长网络寿命。实例仿真表明在连通支配集节点数量较少的情况下 ,高能量的节点在支配集中所占的比例也是较高的。 展开更多
关键词 无线自组传感器网络 支配集 能量有效最小连通支配集 分布式算法
在线阅读 下载PDF
基于最小连通支配集的无线传感网拓扑构建研究 被引量：6
11
作者 洪榛 俞立 +1 位作者 张贵军 陈友荣 《电子与信息学报》 EI CSCD 北大核心 2012年第8期2000-2006,共7页
基于通信虚拟主干网的拓扑构建是关闭冗余节点,节省全网能耗的有效方法。该文将全连通网络环境下寻找最优虚拟主干网问题抽象转化成最小连通支配集求解问题(MCDS),并建立了基于混合整数规划的数学模型(NMIP-MCDS)。NMIP-MCDS在分析MCDS... 基于通信虚拟主干网的拓扑构建是关闭冗余节点,节省全网能耗的有效方法。该文将全连通网络环境下寻找最优虚拟主干网问题抽象转化成最小连通支配集求解问题(MCDS),并建立了基于混合整数规划的数学模型(NMIP-MCDS)。NMIP-MCDS在分析MCDS解的基础上,确定以令牌分发数与节点能耗乘积为目标的优化函数,通过令牌分发同时辅以全网能量负载均衡的方式,构建最优MCDS。仿真实验结果验证了NMIP-MCDS的有效性,并可进一步实际应用在中等规模的无线传感网中。 展开更多
关键词 无线传感器网络 拓扑构建 最小连通支配集 混合整数规划
在线阅读 下载PDF
能量均衡的最小连通支配集分布式算法 被引量：16
12
作者 凌飞 吴振华 《传感技术学报》 CAS CSCD 北大核心 2012年第9期1316-1321,共6页
在无线传感器网络路由协议中,最小连通支配集构成的虚拟骨干网是缓解广播风暴的有效方法。现有算法在构造连通支配集时,通常只考虑支配集的规模,虽然获得了较小的支配集,但也造成虚拟骨干网生命周期较短等问题。为了有效解决该问题,提... 在无线传感器网络路由协议中,最小连通支配集构成的虚拟骨干网是缓解广播风暴的有效方法。现有算法在构造连通支配集时,通常只考虑支配集的规模,虽然获得了较小的支配集,但也造成虚拟骨干网生命周期较短等问题。为了有效解决该问题,提出了一种能量均衡的最小连通支配集分布式算法(EB-MCDS)。仿真实验结果表明,与现有算法相比,EB-MCDS算法有效的均衡了网络能量,延长了网络生命周期20%左右。 展开更多
关键词 无线传感器网络 路由 能量均衡 最小连通支配集
在线阅读 下载PDF
ZigBee无线传感器网络时钟同步研究 被引量：12
13
作者 张坤 刘枫 《西南大学学报（自然科学版）》 CAS CSCD 北大核心 2007年第1期81-84,共4页
针对ZigBee网络的特点,引入连通支配集的方法对FTSP(flooding time synchronization protocol)多跳同步算法进行改进,在主节点中构建一个最小支配节点集,以减少时钟同步的通信开销．
关键词 ZIGBEE网络 时间同步 多跳同步算法 最小连通支配集
在线阅读 下载PDF
异构无线传感器网络中基于CDS树的拓扑控制方法 被引量：6
14
作者 马晨明 王万良 洪榛 《传感技术学报》 CAS CSCD 北大核心 2014年第6期814-820,共7页
拓扑控制是无线传感器网络中节约能量、延长网络生命的关键技术。针对现有拓扑控制方法主要集中在同构网络中作为拓扑构建或拓扑维护单独研究的问题,提出了包含两个过程的异构网络分布式拓扑控制算法A3M。拓扑构建基于最小连通支配集构... 拓扑控制是无线传感器网络中节约能量、延长网络生命的关键技术。针对现有拓扑控制方法主要集中在同构网络中作为拓扑构建或拓扑维护单独研究的问题,提出了包含两个过程的异构网络分布式拓扑控制算法A3M。拓扑构建基于最小连通支配集构建虚拟骨干树,在保证连通性的同时关闭网络冗余节点以降低能耗;拓扑维护对网络性能进行评估,当现有网络性能严重下降时,改变拓扑以保障网络的稳定运行。理论分析和仿真实验证实算法能够以较小的时间和消息代价减少拓扑构建能耗并延长网络时间。 展开更多
关键词 异构无线传感器网络 拓扑控制 A3 M算法 拓扑构建 拓扑维护 最小连通支配集
在线阅读 下载PDF
基于学习自动机的最小连通支配集算法 被引量：3
15
作者 赵学锋 王秀花 +1 位作者 杨海斌 张贵仓 《计算机工程》 CAS CSCD 北大核心 2011年第10期149-151,共3页
为解决连通支配集的最小化问题,提出基于改进的分布式学习自动机的近似算法,在分布式学习自动机按随机选择进行深度搜索的基础上考虑回溯策略。该算法构造的是网络中的一棵支配树,只需要节点的局部信息。在网络建模图——单位圆盘图上... 为解决连通支配集的最小化问题,提出基于改进的分布式学习自动机的近似算法,在分布式学习自动机按随机选择进行深度搜索的基础上考虑回溯策略。该算法构造的是网络中的一棵支配树,只需要节点的局部信息。在网络建模图——单位圆盘图上对支配树性质进行分析和模拟实验。实验结果表明,与现有算法相比,该算法能得到更优的最小连通支配集。 展开更多
关键词 最小连通支配集 学习自动机 单位圆盘图 支配树 深度优先搜索
在线阅读 下载PDF
无线传感器网络中最小化能量广播算法 被引量：9
16
作者 唐勇 周明天 《通信学报》 EI CSCD 北大核心 2007年第4期80-86,共7页
在无线传感器网络广播中,为保证所有节点都接收到广播的数据包并调节节点功率以最小化广播总能耗,在Cartigny等人提出的面向相对邻图的广播算法RBOP(relative neighborhood graph broadcast oriented protocol)的基础上,提出了更为节能... 在无线传感器网络广播中,为保证所有节点都接收到广播的数据包并调节节点功率以最小化广播总能耗,在Cartigny等人提出的面向相对邻图的广播算法RBOP(relative neighborhood graph broadcast oriented protocol)的基础上,提出了更为节能的增强的面向相对邻图的广播算法ERBOP(enhanced relative neighborhood graph broadcast oriented protocol)。首先在相对邻图上删除较长边得到相对邻图的子图,该子图是连通稀疏图且包含了原图的最小生成树,然后在该子图上构造1-支配的连通支配集,只有支配点才参与数据包转发。仿真显示ERBOP有效节约了能量。 展开更多
关键词 无线传感器网络 最小化能量广播 相对邻图 连通支配集
在线阅读 下载PDF
Ad hoc虚拟骨干网中一种费率优先分布式CDS算法 被引量：2
17
作者 程胜 张勖 +1 位作者 冯美玉 丁炜 《北京邮电大学学报》 EI CAS CSCD 北大核心 2004年第3期88-92,共5页
移动Adhoc网络可以通过构建虚拟骨干网来减少参与路由计算的节点数量.虚拟骨干网可以由近似的最小连接主节点集(MCDS)组成.本文对几种经典的分布式近似MCDS查找算法进行了比较,提出了一种新的费率优先的分布式近似MCDS查找算法,详细介... 移动Adhoc网络可以通过构建虚拟骨干网来减少参与路由计算的节点数量.虚拟骨干网可以由近似的最小连接主节点集(MCDS)组成.本文对几种经典的分布式近似MCDS查找算法进行了比较,提出了一种新的费率优先的分布式近似MCDS查找算法,详细介绍了该算法的流程,并对算法的性能进行了分析,仿真结果显示该算法的性能优于经典算法. 展开更多
关键词 移动AD hoe网络 虚拟骨干网 最小连接主节点集
在线阅读 下载PDF
最小支配集问题的活体分子计算模型 被引量：2
18
作者 刘向荣 王淑栋 +1 位作者 郗方 陈梅 《计算机学报》 EI CSCD 北大核心 2009年第12期2325-2331,共7页
生物体内分子网络中信息的传输、储存、放大、整合等大量任务可以看成是一种生物分子计算过程.文中提出了一种活体分子计算模型,借助RNA干扰技术和乳糖操纵子调控模型,在细胞内构建了一个基因网络,用于求解图的最小支配集.该模型展示了... 生物体内分子网络中信息的传输、储存、放大、整合等大量任务可以看成是一种生物分子计算过程.文中提出了一种活体分子计算模型,借助RNA干扰技术和乳糖操纵子调控模型,在细胞内构建了一个基因网络,用于求解图的最小支配集.该模型展示了利用生物体自身的信息处理能力进行计算的能力,在生物体内建立具有一定智能的分子机器,这将在计算科学、生物学、医学上有着深远的应用前景. 展开更多
关键词 活体分子计算 基因网络 RNA干扰 最小支配集问题
在线阅读 下载PDF
一种基于反向CDS树的异构WSNs拓扑构建方法 被引量：3
19
作者 杨明霞 王万良 马晨明 《传感技术学报》 CAS CSCD 北大核心 2016年第2期248-255,共8页
在无线传感器网络中,拓扑控制是节约能源、延长生命周期的一项关键技术。现有拓扑控制方法的研究主要集中在同构网络,对此,面向异构网络提出了一种低信息复杂度的基于反向连通支配集树的分布式拓扑构建算法。基于最小连通支配集构建虚... 在无线传感器网络中,拓扑控制是节约能源、延长生命周期的一项关键技术。现有拓扑控制方法的研究主要集中在同构网络,对此,面向异构网络提出了一种低信息复杂度的基于反向连通支配集树的分布式拓扑构建算法。基于最小连通支配集构建虚拟骨干树,改进了A3G算法中节点的适应度函数和算法流程,优化了产生的连通支配集的规模和通信开销,进一步降低信息复杂度,在保证连通性的同时关闭网络冗余节点以降低能耗。理论分析和仿真实验证明,算法能够以较小的时间和通信代价构建拓扑,延长网络生命周期。 展开更多
关键词 异构无线传感器网络 拓扑控制 拓扑构建 A3G算法 最小连通支配集
在线阅读 下载PDF
基于堆的最小连通支配集高效近似算法 被引量：2
20
作者 赵学锋 杨海斌 张贵仓 《计算机工程》 CAS CSCD 北大核心 2011年第2期54-56,共3页
提出一种解决连通网络图上连通支配集(CDS)问题的贪心近似算法。利用堆结构逐步选出支配节点,将支配节点加入由之前已确定节点组成的树中,完成网络图中支配树的构造。通过计算堆操作次数,分析算法在平均情况下的时间复杂度。在随机网络... 提出一种解决连通网络图上连通支配集(CDS)问题的贪心近似算法。利用堆结构逐步选出支配节点,将支配节点加入由之前已确定节点组成的树中,完成网络图中支配树的构造。通过计算堆操作次数,分析算法在平均情况下的时间复杂度。在随机网络模型上的模拟实验结果表明,与已有算法相比,该算法可以得到点数更少的连通支配集。 展开更多
关键词 最小连通支配集 堆 CDT算法
在线阅读 下载PDF
已选择0条
导出题录 引用分析
参考文献
引证文献
 统计分析
检索结果
已选文献
上一页 1 2 … 4 下一页 到第 页
使用帮助 返回顶部