Constrained relay node placement in wireless sensor networks to meet connectivity and survivability requirements

Satyajayant Misra; Seung Don Hong; Guoliang Xue; Jian Tang

doi:10.1109/INFOCOM.2007.65

Constrained relay node placement in wireless sensor networks to meet connectivity and survivability requirements

Satyajayant Misra, Seung Don Hong, Guoliang Xue, Jian Tang

Research output: Chapter in Book/Entry/Poem › Conference contribution

103 Scopus citations

Abstract

The relay node placement problem for wireless sensor networks is concerned with placing a minimum number of relay nodes into a wireless sensor network to meet certain connectivity and survivability requirements. In this paper, we study constrained versions of the relay node placement problem, where relay nodes can only be placed at a subset of candidate locations. In the connected relay node placement problem, we want to place a minimum number of relay nodes to ensure the connectivity of the sensor nodes and the base stations. In the survivable relay node placement problem, we want to place a minimum number of relay nodes to ensure the biconnectivity of the sensor nodes and the base stations. For each of the two problems, we discuss its computational complexity, and present a framework of polynomial time script O sign (1)-approximation algorithms with small approximation ratios.

Original language	English (US)
Title of host publication	INFOCOM 2008
Subtitle of host publication	27th IEEE Communications Society Conference on Computer Communications
Pages	879-887
Number of pages	9
DOIs	https://doi.org/10.1109/INFOCOM.2007.65
State	Published - 2008
Externally published	Yes
Event	INFOCOM 2008: 27th IEEE Communications Society Conference on Computer Communications - Phoenix, AZ, United States Duration: Apr 13 2008 → Apr 18 2008

Publication series

Name	Proceedings - IEEE INFOCOM
ISSN (Print)	0743-166X

Other

Other	INFOCOM 2008: 27th IEEE Communications Society Conference on Computer Communications
Country/Territory	United States
City	Phoenix, AZ
Period	4/13/08 → 4/18/08

Keywords

Relay node placement
Wireless sensor networks

ASJC Scopus subject areas

General Computer Science
Electrical and Electronic Engineering

Access to Document

10.1109/INFOCOM.2007.65

Cite this

Constrained relay node placement in wireless sensor networks to meet connectivity and survivability requirements. / Misra, Satyajayant; Hong, Seung Don; Xue, Guoliang et al.
INFOCOM 2008: 27th IEEE Communications Society Conference on Computer Communications. 2008. p. 879-887 4509660 (Proceedings - IEEE INFOCOM).

Research output: Chapter in Book/Entry/Poem › Conference contribution

Misra, S, Hong, SD, Xue, G & Tang, J 2008, Constrained relay node placement in wireless sensor networks to meet connectivity and survivability requirements. in INFOCOM 2008: 27th IEEE Communications Society Conference on Computer Communications., 4509660, Proceedings - IEEE INFOCOM, pp. 879-887, INFOCOM 2008: 27th IEEE Communications Society Conference on Computer Communications, Phoenix, AZ, United States, 4/13/08. https://doi.org/10.1109/INFOCOM.2007.65

@inproceedings{fbfe14cf6d044bb6b30fac57b2466a22,

title = "Constrained relay node placement in wireless sensor networks to meet connectivity and survivability requirements",

abstract = "The relay node placement problem for wireless sensor networks is concerned with placing a minimum number of relay nodes into a wireless sensor network to meet certain connectivity and survivability requirements. In this paper, we study constrained versions of the relay node placement problem, where relay nodes can only be placed at a subset of candidate locations. In the connected relay node placement problem, we want to place a minimum number of relay nodes to ensure the connectivity of the sensor nodes and the base stations. In the survivable relay node placement problem, we want to place a minimum number of relay nodes to ensure the biconnectivity of the sensor nodes and the base stations. For each of the two problems, we discuss its computational complexity, and present a framework of polynomial time script O sign (1)-approximation algorithms with small approximation ratios.",

keywords = "Relay node placement, Wireless sensor networks",

author = "Satyajayant Misra and Hong, {Seung Don} and Guoliang Xue and Jian Tang",

year = "2008",

doi = "10.1109/INFOCOM.2007.65",

language = "English (US)",

isbn = "9781424420261",

series = "Proceedings - IEEE INFOCOM",

pages = "879--887",

booktitle = "INFOCOM 2008",

note = "INFOCOM 2008: 27th IEEE Communications Society Conference on Computer Communications ; Conference date: 13-04-2008 Through 18-04-2008",

}

TY - GEN

T1 - Constrained relay node placement in wireless sensor networks to meet connectivity and survivability requirements

AU - Misra, Satyajayant

AU - Hong, Seung Don

AU - Xue, Guoliang

AU - Tang, Jian

PY - 2008

Y1 - 2008

N2 - The relay node placement problem for wireless sensor networks is concerned with placing a minimum number of relay nodes into a wireless sensor network to meet certain connectivity and survivability requirements. In this paper, we study constrained versions of the relay node placement problem, where relay nodes can only be placed at a subset of candidate locations. In the connected relay node placement problem, we want to place a minimum number of relay nodes to ensure the connectivity of the sensor nodes and the base stations. In the survivable relay node placement problem, we want to place a minimum number of relay nodes to ensure the biconnectivity of the sensor nodes and the base stations. For each of the two problems, we discuss its computational complexity, and present a framework of polynomial time script O sign (1)-approximation algorithms with small approximation ratios.

AB - The relay node placement problem for wireless sensor networks is concerned with placing a minimum number of relay nodes into a wireless sensor network to meet certain connectivity and survivability requirements. In this paper, we study constrained versions of the relay node placement problem, where relay nodes can only be placed at a subset of candidate locations. In the connected relay node placement problem, we want to place a minimum number of relay nodes to ensure the connectivity of the sensor nodes and the base stations. In the survivable relay node placement problem, we want to place a minimum number of relay nodes to ensure the biconnectivity of the sensor nodes and the base stations. For each of the two problems, we discuss its computational complexity, and present a framework of polynomial time script O sign (1)-approximation algorithms with small approximation ratios.

KW - Relay node placement

KW - Wireless sensor networks

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

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

U2 - 10.1109/INFOCOM.2007.65

DO - 10.1109/INFOCOM.2007.65

M3 - Conference contribution

AN - SCOPUS:51349128745

SN - 9781424420261

T3 - Proceedings - IEEE INFOCOM

SP - 879

EP - 887

BT - INFOCOM 2008

T2 - INFOCOM 2008: 27th IEEE Communications Society Conference on Computer Communications

Y2 - 13 April 2008 through 18 April 2008

ER -

Constrained relay node placement in wireless sensor networks to meet connectivity and survivability requirements

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this