Not checkedNot checked for notices yet.
A novel centralized algorithm for constructing virtual backbones in wireless sensor networks
Chuanwen Luo, Wenping Chen, Jiguo Yu and 2 more
EURASIP Journal on Wireless Communications and Networking · 2018
doi:10.1186/s13638-018-1068-7 (opens in a new tab)
We email you when a new notice or a question about this paper appears.
Abstract
Abstract Finding the minimum connected dominating set (MCDS) is a key problem in wireless sensor networks, which is crucial for efficient routing and broadcasting. However, the MCDS problem is NP-hard. In this paper, a new approximation algorithm with approximation ratio H(Δ)+3 in time O(n 2) is proposed to approach the MCDS problem. The key idea is to divide the sensors in CDS into core sensors and supporting sensors. The core sensors dominate the supporting sensors in CDS, while the supporting sensors dominate other sensors that are not in CDS. To minimize the number of both the cores and the supporters, a three-phased algorithm is proposed. (1) Finding the base-core sensors by constructing independent set (denoted as S 1), in which the sensors who have the largest |N2(v)||N(v)| $\frac {|N^{2}(v)|}{|N(v)|}$ (number of two-hop neighbors over the number of one-hop neighbors) will be selected greedily into S 1; (2) Connecting all base-core sensors in S 1 to form a connected subgraph, the sensors in the subgraph are called cores; (3) Adding the one-hop neighbors of the core sensors to the supporter set S 2. This guarantees a small number of sensors can be added into CDS, which is a novel scheme for MCDS construction. Extensive simulation results are shown to validate the performance of our algorithm.
Abstract licence: CC BY-NC-ND
Reads
Read by people on this page
None yet.
Checked or read by AI through naulon
None yet.
A person counts once a day per paper. We keep no cookie and no address: a reader is a hash that changes every day. Any month under five reads shows no number.
Are you an author?
Is this your paper?
Claim it to add your note and be paid when agents cite it. Free.