A simple and cost-effective scheme to deploy connection-restoring nodes for disconnected WSNs

Dajin Wang, Liwei Lin, Li Xu, Bingtuan Wang

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

Abstract

We propose a simple scheme for computing the locations of restoration sensors for a disconnected WSN to recover the network's connectivity to a certain level, while keeping the number of restoration nodes as few as possible. Since an accurate, optimal solution to the problem is NP-hard, we resort to tackling the problem in a greedy and heuristic manner. We just deploy enough new nodes to establish k disjoint paths between disconnected components, where k is the network's original connectivity. That is, the scheme just grants the minimally necessary condition for restoring k-connectivity. The extremely time-consuming task of making sure the result is indeed a k-connected network will not be carried out. Empirical study has been conducted to evaluate the effectiveness of the proposed approach.

Original languageEnglish
Title of host publicationICCSP 2011 - 2011 International Conference on Communications and Signal Processing
Pages117-121
Number of pages5
DOIs
StatePublished - 22 Apr 2011
Event2011 International Conference on Communications and Signal Processing, ICCSP 2011 - Kerala, India
Duration: 10 Feb 201112 Feb 2011

Publication series

NameICCSP 2011 - 2011 International Conference on Communications and Signal Processing

Other

Other2011 International Conference on Communications and Signal Processing, ICCSP 2011
CountryIndia
CityKerala
Period10/02/1112/02/11

Fingerprint

Restoration
Costs
Computational complexity
Sensors

Cite this

Wang, D., Lin, L., Xu, L., & Wang, B. (2011). A simple and cost-effective scheme to deploy connection-restoring nodes for disconnected WSNs. In ICCSP 2011 - 2011 International Conference on Communications and Signal Processing (pp. 117-121). [5739282] (ICCSP 2011 - 2011 International Conference on Communications and Signal Processing). https://doi.org/10.1109/ICCSP.2011.5739282
Wang, Dajin ; Lin, Liwei ; Xu, Li ; Wang, Bingtuan. / A simple and cost-effective scheme to deploy connection-restoring nodes for disconnected WSNs. ICCSP 2011 - 2011 International Conference on Communications and Signal Processing. 2011. pp. 117-121 (ICCSP 2011 - 2011 International Conference on Communications and Signal Processing).
@inproceedings{73691005752b4e14b5688f3bf1df5690,
title = "A simple and cost-effective scheme to deploy connection-restoring nodes for disconnected WSNs",
abstract = "We propose a simple scheme for computing the locations of restoration sensors for a disconnected WSN to recover the network's connectivity to a certain level, while keeping the number of restoration nodes as few as possible. Since an accurate, optimal solution to the problem is NP-hard, we resort to tackling the problem in a greedy and heuristic manner. We just deploy enough new nodes to establish k disjoint paths between disconnected components, where k is the network's original connectivity. That is, the scheme just grants the minimally necessary condition for restoring k-connectivity. The extremely time-consuming task of making sure the result is indeed a k-connected network will not be carried out. Empirical study has been conducted to evaluate the effectiveness of the proposed approach.",
author = "Dajin Wang and Liwei Lin and Li Xu and Bingtuan Wang",
year = "2011",
month = "4",
day = "22",
doi = "10.1109/ICCSP.2011.5739282",
language = "English",
isbn = "9781424497980",
series = "ICCSP 2011 - 2011 International Conference on Communications and Signal Processing",
pages = "117--121",
booktitle = "ICCSP 2011 - 2011 International Conference on Communications and Signal Processing",

}

Wang, D, Lin, L, Xu, L & Wang, B 2011, A simple and cost-effective scheme to deploy connection-restoring nodes for disconnected WSNs. in ICCSP 2011 - 2011 International Conference on Communications and Signal Processing., 5739282, ICCSP 2011 - 2011 International Conference on Communications and Signal Processing, pp. 117-121, 2011 International Conference on Communications and Signal Processing, ICCSP 2011, Kerala, India, 10/02/11. https://doi.org/10.1109/ICCSP.2011.5739282

A simple and cost-effective scheme to deploy connection-restoring nodes for disconnected WSNs. / Wang, Dajin; Lin, Liwei; Xu, Li; Wang, Bingtuan.

ICCSP 2011 - 2011 International Conference on Communications and Signal Processing. 2011. p. 117-121 5739282 (ICCSP 2011 - 2011 International Conference on Communications and Signal Processing).

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

TY - GEN

T1 - A simple and cost-effective scheme to deploy connection-restoring nodes for disconnected WSNs

AU - Wang, Dajin

AU - Lin, Liwei

AU - Xu, Li

AU - Wang, Bingtuan

PY - 2011/4/22

Y1 - 2011/4/22

N2 - We propose a simple scheme for computing the locations of restoration sensors for a disconnected WSN to recover the network's connectivity to a certain level, while keeping the number of restoration nodes as few as possible. Since an accurate, optimal solution to the problem is NP-hard, we resort to tackling the problem in a greedy and heuristic manner. We just deploy enough new nodes to establish k disjoint paths between disconnected components, where k is the network's original connectivity. That is, the scheme just grants the minimally necessary condition for restoring k-connectivity. The extremely time-consuming task of making sure the result is indeed a k-connected network will not be carried out. Empirical study has been conducted to evaluate the effectiveness of the proposed approach.

AB - We propose a simple scheme for computing the locations of restoration sensors for a disconnected WSN to recover the network's connectivity to a certain level, while keeping the number of restoration nodes as few as possible. Since an accurate, optimal solution to the problem is NP-hard, we resort to tackling the problem in a greedy and heuristic manner. We just deploy enough new nodes to establish k disjoint paths between disconnected components, where k is the network's original connectivity. That is, the scheme just grants the minimally necessary condition for restoring k-connectivity. The extremely time-consuming task of making sure the result is indeed a k-connected network will not be carried out. Empirical study has been conducted to evaluate the effectiveness of the proposed approach.

UR - http://www.scopus.com/inward/record.url?scp=79954594403&partnerID=8YFLogxK

U2 - 10.1109/ICCSP.2011.5739282

DO - 10.1109/ICCSP.2011.5739282

M3 - Conference contribution

SN - 9781424497980

T3 - ICCSP 2011 - 2011 International Conference on Communications and Signal Processing

SP - 117

EP - 121

BT - ICCSP 2011 - 2011 International Conference on Communications and Signal Processing

ER -

Wang D, Lin L, Xu L, Wang B. A simple and cost-effective scheme to deploy connection-restoring nodes for disconnected WSNs. In ICCSP 2011 - 2011 International Conference on Communications and Signal Processing. 2011. p. 117-121. 5739282. (ICCSP 2011 - 2011 International Conference on Communications and Signal Processing). https://doi.org/10.1109/ICCSP.2011.5739282