求解最小双连通支配集问题的变邻域禁忌搜索算法

针对经典NP难优化问题——最小双连通支配集问题,提出了一种元启发式求解算法——变邻域禁忌搜索算法。算法将原优化问题的求解转换为一系列判定问题——k双连通支配集问题的求解,使用两种邻域结构更加有效地覆盖解空间,同时使用扰动及禁忌机制帮助算法跳出局部最优陷阱。通过与现有文献中的精确算法、启发式算法在国际文献公开的38个双连通图算例上的实验对比,结果表明变邻域禁忌搜索算法能够有效求解最小双连通支配集问题,可求得所有公开算例的最优解,并且在稠密图中计算效率明显优先于其他算法。

区间图最小连通支配集问题的最优算法

针对区间图的最小连通支配集问题,设计简洁的线性算法。对该算法的时间、空间复杂度进行分析,并从实例和理论两方面验证其可行性和有效性。研究结果表明:该算法是线性的,即区间图上可在O(m+n)时间内找到一个最小连通支配集。

基于极大权的最小连通支配集启发式算法

Adhoc无线网络中基于最小连通支配集 (MCDS)的路由是一个引人瞩目的方法 ,文中提出了一种基于极大权的MCDS的启发式算法 ,确保了性能强的主机担任网关节点的角色 ,能更好的协调管理网络中其他的节点 ,从而保持MCDS的相对稳固性并为全网中的广播和路由操作提供一个高效的通信基础 .仿真结果表明 ,该算法能在保证生成权和极大的连通支配集的同时也确保它的极小性 。

Ad Hoc网络和无线传感器网络中连通支配集的分布式构造(英文)

Ad hoc网络和无线传感器网络具有广泛的应用,但对于这样自组性的网络须采用分层结构的聚簇来有效管理.通过选择具有支配属性的节点构成虚拟主干以支持路由、广播及覆盖等应用.大部分的研究都集中在高效选择较小的连通支配集.全面阐述了连通支配集构造的研究进展,并依据不同的网络假设、设计目标和性能对超过20种连通支配集的构造算法进行分类和总结.指出这一领域的研究方向.

无线传感器网络中一种能量均衡的基于连通支配集的数据收集算法

采用连通支配集来构建虚拟骨干可以减轻无线传感器网络的广播风暴问题.目前已有大量工作通过构造最小连通支配集形成网络虚拟骨干来进行高效数据收集.然而,最小连通支配集并不能有效均衡节点的能量耗费,导致网络生命周期较短.提出了一种能量均衡的基于连通支配集的分布式算法EBCDS来进行数据收集,通过选择能量水平和度均比较大的节点组成连通支配集,支配集中的节点组成一个规模不大但具有较高能量水平的网络骨干.网络中的所有数据沿骨干在较小的寻路空间中转发,能够节省节点能量,使骨干节点不会因为能量不足而过早死亡.理论分析表明,EBCDS能以O(nlogn)的消息复杂度构造连通支配集,仿真实验表明,EBCDS能有效节省节点能耗并延长网络生命周期.

移动Ad Hoc网络中最小连通支配集的分布式高效近似算法

提出了一种基于局部最大度数与节点标识号相结合的支配点选择方式,并基于该方式给出了一种计算移动AdHoc网络最小连通支配集的分布式近似算法CDSA,实验显示,CDSA算法生成的连通支配集比文献[3～5]所提出的WL、CBBA及MCDS算法更小。另外,CDSA是一种动态的和基于分布式的算法,因此它不但适用于移动AdHoc网络,也适用于一般网络中的最小连通支配集的近似计算问题。

一个新的分布式最小连通支配集近似算法

在计算机网络中广泛使用广播来解决一些网络问题 ,设计有效的广播算法是一项重要的课题 .文中提出了一种分布地计算网络最小连通支配集的近似算法并给出了它的正确性证明 .它只需要网络节点具有局部的网络状态信息 ,可伸缩性强 .通过此算法可以在网络中自动形成一个虚拟骨干网 ,从而可为网络中的广播和路由操作提供一个有效的通信基础 .模拟结果表明 ,文中提出的算法求得的连通支配集小 ,能较好地应用于一般网络以及移动自组网络中 .

基于最小连通支配集的无线传感网拓扑构建研究

基于通信虚拟主干网的拓扑构建是关闭冗余节点,节省全网能耗的有效方法。该文将全连通网络环境下寻找最优虚拟主干网问题抽象转化成最小连通支配集求解问题(MCDS),并建立了基于混合整数规划的数学模型(NMIP-MCDS)。NMIP-MCDS在分析MCDS解的基础上,确定以令牌分发数与节点能耗乘积为目标的优化函数,通过令牌分发同时辅以全网能量负载均衡的方式,构建最优MCDS。仿真实验结果验证了NMIP-MCDS的有效性,并可进一步实际应用在中等规模的无线传感网中。

用马尔科夫模型优化分布式最小连通支配集算法

为了提高无线传感器网络(WSNs)的能量利用效率、延长网络的生存时间,对基于极大独立集的最小连通支配集算法(MISB)进行优化,提出了一种新的算法.本文首先应用离散马尔科夫链为节点建立模型,并且根据模型预测节点的能量消耗;本算法进行多轮选举,每一轮开始时根据节点的度和能量选举支配点,依据模型预测的能量消耗决定本轮的运行时间,本轮运行结束时从新选举支配点,开始新一轮.仿真结果表明,本算法和原算法相比可以更好地平衡网络的能量消耗,提高全网的能量利用率,极大地延长网络的生存时间.

基于极大独立集的最小连通支配集的分布式算法

全网范围的广播在无线传感器网络和移动自组织网络中有着广泛的应用.为节省网络资源,减少冗余转发节点成为广播中需解决的关键问题.广播过程中最小化参与转发节点数问题与图论中求解最小连通支配集问题等价,而在任意图中求解最小连通支配集是NP完全问题.本文基于极大独立集,提出了一种求解最小连通支配集的分布式算法(MISB),并证明了算法的正确性.仿真结果表明,使用该算法能得到较小的连通支配集,从而有效减少网络广播过程中的转发节点数,大大节省了网络资源.

无线传感网络中能量均衡的连通支配集算法

连通支配集是无线传感器网络中构建虚拟骨干网络的重要手段。由于支配集中节点的能耗相对其他节点要多,支配集中剩余能量较小的节点决定了虚拟骨干网的生命周期。现有算法或者只是关注构造较小的支配集,或者没有考虑调整能耗极快的支配节点。提出了一种能量均衡的连通支配集算法,基于节点剩余能量和连通度构造支配集,在网络运行过程中根据耗能速度,提前选择候选支配节点,分流负载过重的支配节点。仿真结果表明,新算法能以较小消息开销,有效延长网络寿命。

基于图着色的无线自组网极小连通支配集算法

基于连通支配集算法的虚拟主干网技术对于无线自组网的路由优化、能量保护和资源分配都具有重要的作用。通过引入极大独立集和极小支配集概念,基于图着色思想提出一种新的适合于无线自组网的极小连通支配集算法,从理论上证明了该算法的正确性和高效性,也通过仿真实验分析了该算法在多种情况下的实际性能,仿真结果表明新算法在簇头和主干节点数目方面具有较好的性能,特别在节点密集的网络环境中更加突出。

一种求解最小连通支配集的高效近似算法

寻找出一个网络图的最小连通支配集有重要实际应用背景,然而如何找到它却是一个NP难题.本文设计了一种简单且高效的近似启发式算法构造网络图的连通支配集,该算法分为三个阶段:首先为顶点分配等级和生成顶点次序表,其次构造一个极大独立集,最后连接极大独立集中顶点.模拟实验表明该算法无论在运行时间和结果上都达到良好的效果.

分布式最小连通支配集启发式算法

针对Ad Hoc网络中用洪泛法进行广播易引起广播风暴的问题,提出一个新的分布式最小连通支配集启发式算法HMCDS,其中包括构建极大独立集、引入节点的有效度概念、选择有效度最大的节点作为支配点的贪心策略的方法,实验结果证明,HMCDS算法生成的连通支配集大小为7.6opt+1.4,时间复杂度为O(△2),消息复杂度为O(n),比同类算法优秀。

能量有效的最小连通支配集近似算法

针对无线自组传感器网络中有效路由提出的一种能量有效的最小连通支配集近似算法EEMCDS(Energy Effi cientminimumconnecteddominatingset) ,路由搜索主要集中在连通支配集内。本文提出一个能量有效的简洁有效的分布式算法 ,该算法根据各节点所具有的能量不同 ,优先选择高能量的节点作为连通支配集节点 ,可以有效地延长网络寿命。实例仿真表明在连通支配集节点数量较少的情况下 ,高能量的节点在支配集中所占的比例也是较高的。

传感器网络中高效的最小连通支配集求解算法

在无线传感器网络中,连通支配集被广泛应用于构建虚拟主干。由于求解最小连通支配集是一个NP难问题,许多近似算法被提出用于构建可用的最小连通支配集。针对当前近似算法存在的不足,我们提出了一个新的分布式近似构造算法—CDS-HG,该算法用层次图对无线传感器网络进行建模,算法用基于竞争的贪心策略从每一层选出最少的节点去支配下一层的所有节点。理论分析和模拟结果表明,CDS-HG算法产生的连通支配集是目前最小,并且其消息复杂度也是目前最低的。

时延和能耗均衡的强连通支配集构造算法

针对无线传感器网络中链路的非对称性,提出时延约束的强连通支配树(SDTT,strongly connected dominating tree with bounded transmission delay)问题,给出在有向图上构建传输时延和能量消耗均衡的强连通支配集的强连通支配树(SCDT,distributed strongly connected dominating tree)算法。首先在单位圆图(UDG)模型的基础上构建极大独立集(MIS),然后在具有双向权值的有向图上基于最小支撑树和最短路径树实现分布式SCDT算法,同时满足时延和能耗均衡的约束条件要求。理论算例分析和仿真结果表明提出的算法能有效地解决SDTT问题,构造联合约束的强连通支配集,形成时延和能耗均衡的虚拟骨干。

能量均衡的最小连通支配集分布式算法

在无线传感器网络路由协议中,最小连通支配集构成的虚拟骨干网是缓解广播风暴的有效方法。现有算法在构造连通支配集时,通常只考虑支配集的规模,虽然获得了较小的支配集,但也造成虚拟骨干网生命周期较短等问题。为了有效解决该问题,提出了一种能量均衡的最小连通支配集分布式算法(EB-MCDS)。仿真实验结果表明,与现有算法相比,EB-MCDS算法有效的均衡了网络能量,延长了网络生命周期20%左右。

基于学习自动机的最小连通支配集算法

为解决连通支配集的最小化问题,提出基于改进的分布式学习自动机的近似算法,在分布式学习自动机按随机选择进行深度搜索的基础上考虑回溯策略。该算法构造的是网络中的一棵支配树,只需要节点的局部信息。在网络建模图——单位圆盘图上对支配树性质进行分析和模拟实验。实验结果表明,与现有算法相比,该算法能得到更优的最小连通支配集。

移动自组网络中采用连通支配集的有效广播技术(英文)

广播是移动自组网络 (MANET)中的一种常用操作 .许多移动自组网络的按需路由协议依赖于它来发现任意两个节点之间的路径 .广播也是许多 MANET应用中发布信息的重要手段 .实现广播的直接途径是洪泛 (flood-ing) .然而 ,在没有有效的控制机制下 ,洪泛将带来严重的消息冗余、传输冲突和碰撞问题 .基于图论中的连通支配集 (CDS)概念 ,提出了一种有效的广播途径 .它能较大地减小消息的冗余度 ,同时保持了洪泛的优点 .模拟结果表明 ,提出的广播途径优于一个基于 CDS的分布式算法和一个基于簇 (cluster)的途径 .