共查询到20条相似文献,搜索用时 15 毫秒
1.
传感器网络中高效的最小连通支配集求解算法 总被引:1,自引:1,他引:0
在无线传感器网络中,连通支配集被广泛应用于构建虚拟主干。由于求解最小连通支配集是一个NP难问题,许多近似算法被提出用于构建可用的最小连通支配集。针对当前近似算法存在的不足,我们提出了一个新的分布式近似构造算法—CDS-HG,该算法用层次图对无线传感器网络进行建模,算法用基于竞争的贪心策略从每一层选出最少的节点去支配下一层的所有节点。理论分析和模拟结果表明,CDS-HG算法产生的连通支配集是目前最小,并且其消息复杂度也是目前最低的。 相似文献
2.
针对AdHoc网络中用洪泛法进行广播易引起广播风暴的问题,提出一个新的分布式最小连通支配集启发式算法HMCDS,其中包括构建极大独立集、引入节点的有效度概念、选择有效度最大的节点作为支配点的贪心策略的方法,实验结果证明,HMCDS算法生成的连通支配集大小为7.60pt+1.4,时间复杂度为O(△^2),消息复杂度为O(n),比同类算法优秀。 相似文献
3.
在无线传感器网络路由协议中,最小连通支配集构成的虚拟骨干网是缓解广播风暴的有效方法。现有算法在构造连通支配集时,通常只考虑支配集的规模,虽然获得了较小的支配集,但也造成虚拟骨干网生命周期较短等问题。为了有效解决该问题,提出了一种能量均衡的最小连通支配集分布式算法(EB-MCDS)。仿真实验结果表明,与现有算法相比,EB-MCDS算法有效的均衡了网络能量,延长了网络生命周期20%左右。 相似文献
4.
Motivated by the problem of supporting energy-efficient broadcasting in ad hoc wireless networks, we study the Minimum Energy Consumption Broadcast Subgraph (MECBS) problem. We present the first logarithmic approximation algorithm for the problem which uses an interesting reduction to Node-Weighted Connected Dominating Set. 相似文献
5.
6.
针对无线传感器网络常用的拓扑模型单位圆盘图,提出了基于分布式贪心策略的近似算法DDT,在算法执行的每一轮中,根据一跳邻域范围内的权值和邻居的状态信息,选举出节点并和已确定的节点连接,逐步构造出网络图中的一个支配树。用概率方法研究了支配树中的节点度的性质,通过对极大独立集和最小连通支配集之间关系的分析,得到单位圆盘图中最小连通支配集问题一个新的近似比。计算结果表明,和相关的分布式算法相比,DDT产生的连通支配集在规模上更优。 相似文献
7.
复杂性理论中,支配问题是一类重要的问题,被广泛应用于资源分配、电话交换网络和无线传感器网络等领域。支配问题主要包括点支配集(VDS)问题和边支配集(EDS)问题两大类。人们利用动态规划、加权分治等技术对VDS和EDS问题的精确算法进行设计与分析,并通过将EDS问题转化为边覆盖集问题提出了EDS问题的近似算法。近年来对参数化支配问题做了大量研究。目前已经证明了平面图中VDS问题和一般图中EDS问题都是固定参数可解的(FPT)。利用树分解和分支搜索等技术,人们分别对平面图VDS问题和一般图EDS问题提出了一系列FPT算法。文中对VDS和EDS问题进行了分类,给出了每类问题的具体定义及其相关算法介绍,此外还对矩阵支配集问题进行了简单介绍,并提出了支配问题研究中值得关注的几个方面。 相似文献
8.
能量有效的最小连通支配集近似算法 总被引:5,自引:2,他引:3
针对无线自组传感器网络中有效路由提出的一种能量有效的最小连通支配集近似算法EEMCDS(Energy-Efficient minimum connected dominating set),路由搜索主要集中在连通支配集内.本文提出一个能量有效的简洁有效的分布式算法,该算法根据各节点所具有的能量不同,优先选择高能量的节点作为连通支配集节点,可以有效地延长网络寿命.实例仿真表明在连通支配集节点数量较少的情况下,高能量的节点在支配集中所占的比例也是较高的. 相似文献
9.
10.
Johann L. Hurink 《Information Processing Letters》2008,109(2):155-160
We present the first polynomial-time approximation scheme (PTAS) for the Minimum Independent Dominating Set problem in graphs of polynomially bounded growth which are used to model wireless communication networks.The approach presented yields a robust algorithm, that is, it accepts any undirected graph as input, and returns a (1+ε)-approximate minimum independent dominating set, or a certificate showing that the input graph does not satisfy the bounded growth property. 相似文献
11.
R. Bar-Yehuda 《Algorithmica》2000,27(2):131-144
We present a simple and unified approach for developing and analyzing approximation algorithms for covering problems. We
illustrate this on approximation algorithms for the following problems: Vertex Cover, Set Cover, Feedback Vertex Set, Generalized
Steiner Forest, and related problems.
The main idea can be phrased as follows: iteratively, pay two dollars (at most) to reduce the total optimum by one dollar
(at least), so the rate of payment is no more than twice the rate of the optimum reduction. This implies a total payment (i.e.,
approximation cost) ≤ twice the optimum cost.
Our main contribution is based on a formal definition for covering problems, which includes all the above fundamental problems
and others. We further extend the Bafna et al. extension of the Local-Ratio theorem. Our extension eventually yields a short
generic r -approximation algorithm which can generate most known approximation algorithms for most covering problems.
Another extension of the Local-Ratio theorem to randomized algorithms gives a simple proof of Pitt's randomized approximation
for Vertex Cover. Using this approach, we develop a modified greedy algorithm, which for Vertex Cover gives an expected performance
ratio ≤ 2 .
Received September 17, 1997; revised March 5, 1998. 相似文献
12.
针对无线传感器网络中的有效路由,提出了一种改进的,基于最小连通支配集的能量有效算法IEEMCDS(Improved Energy-Efficient Minimum Connected Dominating Set).路由搜索主要集中在连通支配集内,通信量小.该算法是一个能量有效的分布式算法,在维护最小连通支配集时,充分考虑了节点的能量问题,优先选择高能量的节点充当连通支配集节点,提出了支配节点能量最小阈值调整法,可以有效地延长网络寿命.实例仿真表明在改进算法的连通支配集中,高能量的节点在支配集中一直占有较高的比例,从而有效地延长了网络寿命. 相似文献
13.
Subexponential algorithms for partial cover problems 总被引:1,自引:0,他引:1
Fedor V. Fomin 《Information Processing Letters》2011,111(16):814-818
Partial Cover problems are optimization versions of fundamental and well-studied problems like Vertex Cover and Dominating Set. Here one is interested in covering (or dominating) the maximum number of edges (or vertices) using a given number k of vertices, rather than covering all edges (or vertices). In general graphs, these problems are hard for parameterized complexity classes when parameterized by k. It was recently shown by Amini et al. (2008) [1] that Partial Vertex Cover and Partial Dominating Set are fixed parameter tractable on large classes of sparse graphs, namely H-minor-free graphs, which include planar graphs and graphs of bounded genus. In particular, it was shown that on planar graphs both problems can be solved in time 2O(k)nO(1).During the last decade there has been an extensive study on parameterized subexponential algorithms. In particular, it was shown that the classical Vertex Cover and Dominating Set problems can be solved in subexponential time on H-minor-free graphs. The techniques developed to obtain subexponential algorithms for classical problems do not apply to partial cover problems. It was left as an open problem by Amini et al. (2008) [1] whether there is a subexponential algorithm for Partial Vertex Cover and Partial Dominating Set. In this paper, we answer the question affirmatively by solving both problems in time not only on planar graphs but also on much larger classes of graphs, namely, apex-minor-free graphs. Compared to previously known algorithms for these problems our algorithms are significantly faster and simpler. 相似文献
14.
密钥管理是解决传感器网络安全的关键技术。现有的密钥管理机制,不能很好地优化系统的整体性能,基于连通支配集对传感器网络进行聚类,在簇内实现集中式密钥管理,簇间通过通信主干实现分布式密钥管理,从而构建安全的传感器网络。实验表明,通过混合式的密钥管理,可以有效延长网络生命期。 相似文献
15.
16.
17.
We consider the problem of scheduling jobs on related machines owned by selfish agents. We provide a 5-approximation deterministic
truthful mechanism, the first deterministic truthful result for the problem. Previously, Archer and Tardos showed a 2-approximation
randomized mechanism which is truthful in expectation only (a weaker notion of truthfulness). In case the number of machines
is constant, we provide a deterministic Fully Polynomial-Time Approximation Scheme (FPTAS) and a suitable payment scheme that
yields a truthful mechanism for the problem. This result, which is based on converting FPTAS to monotone FPTAS, improves a
previous result of Auletta et al., who showed a (4 + ε)-approximation truthful mechanism. 相似文献
18.
Sushmita Gupta 《Information Processing Letters》2008,105(4):150-154
In this paper we give ratio 4 deterministic and randomized approximation algorithms for the Feedback Arc Set problem in bipartite tournaments. We also generalize these results to give a factor 4 deterministic approximation algorithm for Feedback Arc Set problem in multipartite tournaments. 相似文献
19.
20.
The approximation ratio of the longest processing time (LPT) scheduling algorithm has been investigated in various studies. While the tight approximation ratio is known for the cases when all processors are identical, the ratio is unknown when the processors have different speeds. In this study, we provide a tight approximation ratio for three, four, and five processors. We show that the ratios for these cases are no larger than the lower bound provided by Gonzalez et al. (1977) [14]. The ratios are approximately 1.38, 1.43, and 1.46 for three, four, and five processors, respectively. 相似文献