Skip to content
naulon

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.