Fault-Tolerant Virtual Backbone in Heterogeneous Wireless Sensor Network Article Swipe

MAKE IMPACT

Jiao Zhou , Zhao Zhang , Shaojie Tang , Xiaohui Huang , Yuchang Mo , Ding‐Zhu Du · YOU? · · 2017 · Open Access · · DOI: https://doi.org/10.1109/tnet.2017.2740328

To save energy and alleviate interferences in a wireless sensor network, the\nusage of virtual backbone was proposed. Because of accidental damages or energy\ndepletion, it is desirable to construct a fault tolerant virtual backbone,\nwhich can be modeled as a $k$-connected $m$-fold dominating set (abbreviated as\n$(k,m)$-CDS) in a graph. A node set $C\\subseteq V(G)$ is a $(k,m)$-CDS of graph\n$G$ if every node in $V(G)\\backslash C$ is adjacent with at least $m$ nodes in\n$C$ and the subgraph of $G$ induced by $C$ is $k$-connected. In this paper, we\npresent an approximation algorithm for the minimum $(3,m)$-CDS problem with\n$m\\geq3$. The performance ratio is at most $\\gamma$, where\n$\\gamma=\\alpha+8+2\\ln(2\\alpha-6)$ for $\\alpha\\geq4$ and $\\gamma=3\\alpha+2\\ln2$\nfor $\\alpha<4$, and $\\alpha$ is the performance ratio for the minimum\n$(2,m)$-CDS problem. Using currently best known value of $\\alpha$, the\nperformance ratio is $\\ln\\delta+o(\\ln\\delta)$, where $\\delta$ is the maximum\ndegree of the graph, which is asymptotically best possible in view of the\nnon-approximability of the problem. This is the first performance-guaranteed\nalgorithm for the minimum $(3,m)$-CDS problem on a general graph. Furthermore,\napplying our algorithm on a unit disk graph which models a homogeneous wireless\nsensor network, the performance ratio is less than 27, improving previous ratio\n62.3 by a large amount for the $(3,m)$-CDS problem on a unit disk graph.\n

Type

article

Language

en

Landing Page

https://doi.org/10.1109/tnet.2017.2740328

OA Status

green

Cited By

22

References

58

Related Works

10

OpenAlex ID

https://openalex.org/W3100906419

Raw OpenAlex JSON

OpenAlex ID

https://openalex.org/W3100906419

Canonical identifier for this work in OpenAlex

DOI

https://doi.org/10.1109/tnet.2017.2740328

Digital Object Identifier

Title

Fault-Tolerant Virtual Backbone in Heterogeneous Wireless Sensor Network

Work title

Type

article

OpenAlex work type

Language

en

Primary language

Publication year

2017

Year of publication

Publication date

2017-08-23

Full publication date if available

Authors

Jiao Zhou, Zhao Zhang, Shaojie Tang, Xiaohui Huang, Yuchang Mo, Ding‐Zhu Du

List of authors in order

Landing page

https://doi.org/10.1109/tnet.2017.2740328

Publisher landing page

Open access

Yes

Whether a free full text is available

OA status

green

Open access status per OpenAlex

OA URL

https://arxiv.org/pdf/1604.06181

Direct OA link when available

Concepts

Unit disk graph, Connected dominating set, Wireless sensor network, Computer science, Topology (electrical circuits), Graph, Redundancy (engineering), Algorithm, Combinatorics, Mathematics, Discrete mathematics, Wireless network, Computer network, Wireless, Theoretical computer science, Operating system, Telecommunications

Top concepts (fields/topics) attached by OpenAlex

Cited by

22

Total citation count in OpenAlex

Citations by year (recent)

2024: 1, 2023: 6, 2022: 1, 2021: 2, 2020: 2

Per-year citation counts (last 5 years)

References (count)

58

Number of works referenced by this work

Related works (count)

10

Other works algorithmically related by OpenAlex

Full payload