已为您找到该学者19条结果 成果回收站
【期刊论文】Survey of Approximation Algorithm on Virtual Backbone of Wireless Sensor Network
计算机研究与发展,-0001,53(1):15-25
-1年11月30日
Using virtual backbone in wireless sensor network can effectively save energy, reduce interference, and prolong lifetime, which has a wide application in the field of geometric routing and topology control. Virtual backbone can be modeled as a connected dominating set (CDS) in a graph. This paper introduces the state of art of approximation algorithms on CDS and its variations. The focus is put on theoretical results and methods. The purpose is to provide a reference for researchers who are interested in this field.
wireless sensor network (, WSN), ,, virtual backbone,, connected dominating set (, CDS), ,, approximation algorithm,, performance ratio
0
-
33浏览
-
0点赞
-
0收藏
-
0分享
-
0下载
-
0
-
引用
【期刊论文】Approximation Algorithm for Minimum Weight Fault-Tolerant Virtual Backbone in Unit Disk Graphs
IEEE/ACM Transactions on Networking,2016,25(2):925 - 933
2016年09月28日
In a wireless sensor network, the virtual backbone plays an important role. Due to accidental damage or energy depletion, it is desirable that the virtual backbone is fault-tolerant. A fault-tolerant virtual backbone can be modeled as a k-connected m-fold dominating set ((k, m)-CDS for short). In this paper, we present a constant approximation algorithm for the minimum weight (k, m)-CDS problem in unit disk graphs under the assumption that k and m are two fixed constants with m ≥ k. Prior to this paper, constant approximation algorithms are known for k = 1 with weight and 2 ≤ k ≤ 3 without weight. Our result is the first constant approximation algorithm for the (k, m)-CDS problem with general k, m and with weight. The performance ratio is (α+5ρ) fork ≥ 3 and (α+2.5ρ) for k = 2, where α is the performance ratio for the minimum weight m-fold dominating set problem and ρ is the performance ratio for the subset k-connected subgraph problem (both problems are known to have constant performance ratios).
无
0
-
26浏览
-
0点赞
-
0收藏
-
0分享
-
0下载
-
0
-
引用
【期刊论文】Fault-Tolerant Virtual Backbone in Heterogeneous Wireless Sensor Network
IEEE/ACM Transactions on Networking,2017,25(6):3487 - 349
2017年08月23日
To save energy and alleviate interference, connected dominating set (CDS) was proposed to serve as a virtual backbone of wireless sensor networks (WSNs). Because sensor nodes may fail due to accidental damages or energy depletion, it is desirable to construct a fault tolerant virtual backbone with high redundancy in both coverage and connectivity. This can be modeled as a k-connected m-fold dominating set (abbreviated as (k, m)-CDS) problem. A node set C ⊆ V (G) is a (k, m)-CDS of graph G if every node in V(G)\C is adjacent with at least m nodes in C and the subgraph of G induced by C is k-connected. Constant approximation algorithm is known for (3, m)-CDS in unit disk graph, which models homogeneous WSNs. In this paper, we present the first performance guaranteed approximation algorithm for (3, m)-CDS in a heterogeneous WSN. In fact, our performance ratio is valid for any topology. The performance ratio is at most γ, where γ = α + 8 + 2 ln(2α - 6) for α ≥ 4 and γ = 3α +2 ln 2 for α <; 4, and α is the performance ratio for the minimum (2, m)-CDS problem. Using currently best known value of α, the performance ratio is ln δ +o(ln δ), where δ is the maximum degree of the graph, which is asymptotically best possible in view of the non-approximability of the problem. Applying our algorithm on a unit disk graph, the performance ratio is less than 27, improving previous ratio 62.3 by a large amount for the (3, m)-CDS problem on a unit disk graph.
无
0
-
32浏览
-
0点赞
-
0收藏
-
0分享
-
0下载
-
0
-
引用
【期刊论文】Primal dual based algorithm for degree-balanced spanning tree problem
Applied Mathematics and Computation,2018,316():167-173
2018年01月01日
This paper studies approximation algorithm for the degree-balanced spanning tree (DBST) problem. Given a graph the goal is to find a spanning tree T such that ∑v ∈ VdegT(v)2 is minimized, where degT(v) denotes the degree of node v in tree T. The idea of taking squares on node degrees is to manifest the role of nodes with large degree, and thus minimizing the sum will result in a comparatively balanced degree distribution. This is a non-linear objective function. We prove that DBST is NP-hard, and then develop a primal–dual based algorithm with a guaranteed performance ratio.
Degree-balanced spanning tree, Nonlinear objective function, Primal dual algorithm
0
-
34浏览
-
0点赞
-
0收藏
-
0分享
-
0下载
-
0
-
引用
合作学者
- 暂无合作作者