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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

基于堆的最小连通支配集高效近似算法

提出一种解决连通网络图上连通支配集(CDS)问题的贪心近似算法。利用堆结构逐步选出支配节点,将支配节点加入由之前已确定节点组成的树中,完成网络图中支配树的构造。通过计算堆操作次数,分析算法在平均情况下的时间复杂度。在随机网络模型上的模拟实验结果表明,与已有算法相比,该算法可以得到点数更少的连通支配集。

基于域的分布式最小连通支配集的启发式算法

在规模较大且移动较频繁的ad hoc网络中,针对构建树形连通支配集缓慢且网络开销大的问题,提出了基于域的分布式最小连通支配集的启发式算法(ZBCDS)。ZBCDS在求得极大独立集的基础上,定义了节点阶势和候选节点的概念,通过判断节点的阶势,优化了域的生成和域边界上连接节点的调整,达到CDS重构快速高效地实现的目的。实验结果表明,ZBCDS算法能高效且快速的构建最小连通支配集,且比同类算法生成的连通支配集更小,时间复杂度有所降低。

基于二跳独立邻居覆盖的极小连通支配集构造算法

提出两个基于二跳独立邻居覆盖的无线传感器网络极小连通支配集构造算法.在两个构造算法中,已选择的支配节点推举新的支配节点,并要求新推举的支配节点完全覆盖该支配节点的二跳独立邻居节点.第一个算法不考虑能量因子,以被推举节点的一跳和部分二跳独立邻居节点集合大小之和最大作为新支配节点推举依据;第二个算法以被推举节点剩余能量与其覆盖的二跳独立邻居节点个数之商最大化作为推举依据.所提出的算法具有较好的时间复杂度和消息复杂度,且均为O(n),第一个算法的性能比为O(n^(1/2)).仿真结果表明,本文提出的算法可构造较小规模的连通支配集以及延长网络生命时间.

基于GSO算法的最小连通支配集问题求解

经典的最小连通支配集(MCDS)计算是NP难问题。为此,提出一种利用萤火虫优化算法求解该难题的新方法。把网络中的每个节点当作一个萤火虫个体,以节点度为基础构成荧光素,通过概率选择和荧光素调节机制,使个体被吸引向邻接的高亮度个体,从而由所选出的个体组成网络的支配集。经连接和修剪处理后,得到MCDS的近似解。在无线传感器网络模型的单位圆盘图上进行模拟实验,结果表明,该算法得到的连通支配集规模较小,更接近集中式算法的结果。

最小连通支配集问题的化简算法

分析连通支配集的支配性约束和连通性约束条件,提出2条针对简单无向连通图最小连通支配集问题的化简规则。规则通过对图中节点的邻节点进行分类以及寻找图的割点提前确定一些必选节点,同时删除一些多余节点,从而降低原问题的规模。从理论上证明了化简规则的正确性,并通过随机仿真实验验证化简规则的有效性。

求解最小连通r-跳k-支配集的启发式算法

针对最小连通r-跳k-支配集的求解问题,提出一种基于节点度贪心策略的启发式算法。把网络节点集合作为初始解,从中选出度数最小的节点,通过判断节点的连通性决定是否将该节点从当前可行解中删除,由此逐步缩小连通支配集的规模,直至处理完所有节点。在单位圆盘图上进行算法复杂性分析和模拟实验,结果表明,相比同类算法,该算法得到的连通r-跳k-支配点集更少,且性能稳定。

高效的分布式最小连通支配集近似算法

在Alzoubi and Wan’s算法的基础上,利用2跳局部网络拓扑信息选择连通点,提出一个高效的分布式最小连通支配集算法EDMCDS。理论分析表明,EDMCDS算法生成的连通支配集大小为(5.8+ln4)opt+1.2,时间复杂度为O(△|MIS|),信息复杂度为O(4|E|)。与TFA和Alzoubi and Wan’s算法相比,该算法生成的连通支配集更小,时间复杂度和信息复杂度也有所降低。

自组织网络分布式最小连通支配集创建算法

针对无线自组织分组(Ad hoc)网络中最小连通支配集(MCDS)创建NP难问题,提出了一种分布式的最小连通集创建算法DMCA。DMCA基于最大独立集(MIS)的构建,只需要周围一跳邻居的信息,在不超过三跳距离的一对支配节点之间找出一条最短路径。对DMCA算法的性能分析表明,DMCA具有常数的近似比、线性的时间和消息复杂度。详细的仿真实验以及与其他创建最小连通支配集算法的比较表明,提出的DMCA算法在节点数量与节点传输范围变化时创建的最小连通集更小。

无线传感器网络中能量有效的最小连通支配集算法

提出了一种分布式最小连通支配集求解算法,对Rule K算法中的标记算法进行了优化,从而形成了连通支配集,并通过新的剪枝算法对连通支配集进行了有效缩减.模拟仿真结果表明:在增加算法复杂度的前提下,该算法求得的连通支配集比前算法更小.

求解圆盘图中最小连通支配集的近似算法

针对无线传感器网络常用的拓扑模型单位圆盘图,提出了基于分布式贪心策略的近似算法DDT,在算法执行的每一轮中,根据一跳邻域范围内的权值和邻居的状态信息,选举出节点并和已确定的节点连接,逐步构造出网络图中的一个支配树。用概率方法研究了支配树中的节点度的性质,通过对极大独立集和最小连通支配集之间关系的分析,得到单位圆盘图中最小连通支配集问题一个新的近似比。计算结果表明,和相关的分布式算法相比,DDT产生的连通支配集在规模上更优。

一种能量均衡的最小连通支配集构造算法

针对无线传感器网络中没有固定的基础设施问题,提出一种能量均衡的最小连通支配集构造算法,该算法首先为网络构造一个极大独立集,然后选择最少的连接节点使极大独立集连通,并在使极大独立集连通时加入了修剪规则,使连通支配集规模更小,最后,针对网络拓扑变化导致连通支配集重构问题,提出了局部构造最小连通支配集算法.通过优先选择能量多、度数大的节点来构造连通支配集,并考虑了连通支配集重构问题,使网络中节点能量消耗更加均衡,从而有效地延长了网络寿命.理论分析和实验结果表明,与相关的分布式算法相比,本文算法产生的连通支配集在规模上更优,网络寿命更长.