Relay placement for reliable base station connectivity in polymorphous networks

Ying Huang, Yan Gao, Klara Nahrstedt

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

With emerging demand for online surveillance and management, persistent and reliable connectivity to base stations (BSs) is indispensable so that network operators, which have access to all BSs, can collect measurements from all wireless terminals in the field, monitor their status and respond to critical incidents in real-time. However, disconnected networks make reliable BS connectivity problematic. Many papers have studied the problem of placing the minimum number of relays to retain connectivity. However, none of them considered polymorphous networks, which have multiple topologies, due to terminal movement, unsynchronized wakeup schedule and packet forwarding policy. Our paper makes the first attempt towards the study of relay placement problem in polymorphous networks. We propose two heuristic algorithms, topology stitch algorithm and topology iterative algorithm, which are built upon constrained relay placement algorithms for monomorphous networks with a single topology. Also, we propose the weigh-and-place algorithm (WPA), which optimizes relay placement across topologies with balanced load based on integer programming formulation. Evaluation shows that WPA places a smaller number of relays than the other two heuristic algorithms and achieves good load balance among multiple BSs.

Original languageEnglish (US)
Title of host publicationSECON 2010 - 2010 7th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks
DOIs
StatePublished - Aug 5 2010
Event7th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks, SECON 2010 - Boston, MA, United States
Duration: Jun 21 2010Jun 25 2010

Publication series

NameSECON 2010 - 2010 7th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks

Other

Other7th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks, SECON 2010
CountryUnited States
CityBoston, MA
Period6/21/106/25/10

Fingerprint

Base stations
Topology
Heuristic algorithms
Integer programming

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Electrical and Electronic Engineering

Cite this

Huang, Y., Gao, Y., & Nahrstedt, K. (2010). Relay placement for reliable base station connectivity in polymorphous networks. In SECON 2010 - 2010 7th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks [5508234] (SECON 2010 - 2010 7th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks). https://doi.org/10.1109/SECON.2010.5508234

Relay placement for reliable base station connectivity in polymorphous networks. / Huang, Ying; Gao, Yan; Nahrstedt, Klara.

SECON 2010 - 2010 7th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks. 2010. 5508234 (SECON 2010 - 2010 7th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Huang, Y, Gao, Y & Nahrstedt, K 2010, Relay placement for reliable base station connectivity in polymorphous networks. in SECON 2010 - 2010 7th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks., 5508234, SECON 2010 - 2010 7th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks, 7th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks, SECON 2010, Boston, MA, United States, 6/21/10. https://doi.org/10.1109/SECON.2010.5508234
Huang Y, Gao Y, Nahrstedt K. Relay placement for reliable base station connectivity in polymorphous networks. In SECON 2010 - 2010 7th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks. 2010. 5508234. (SECON 2010 - 2010 7th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks). https://doi.org/10.1109/SECON.2010.5508234
Huang, Ying ; Gao, Yan ; Nahrstedt, Klara. / Relay placement for reliable base station connectivity in polymorphous networks. SECON 2010 - 2010 7th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks. 2010. (SECON 2010 - 2010 7th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks).
@inproceedings{261c42639d7d427a928d3cb7cff93022,
title = "Relay placement for reliable base station connectivity in polymorphous networks",
abstract = "With emerging demand for online surveillance and management, persistent and reliable connectivity to base stations (BSs) is indispensable so that network operators, which have access to all BSs, can collect measurements from all wireless terminals in the field, monitor their status and respond to critical incidents in real-time. However, disconnected networks make reliable BS connectivity problematic. Many papers have studied the problem of placing the minimum number of relays to retain connectivity. However, none of them considered polymorphous networks, which have multiple topologies, due to terminal movement, unsynchronized wakeup schedule and packet forwarding policy. Our paper makes the first attempt towards the study of relay placement problem in polymorphous networks. We propose two heuristic algorithms, topology stitch algorithm and topology iterative algorithm, which are built upon constrained relay placement algorithms for monomorphous networks with a single topology. Also, we propose the weigh-and-place algorithm (WPA), which optimizes relay placement across topologies with balanced load based on integer programming formulation. Evaluation shows that WPA places a smaller number of relays than the other two heuristic algorithms and achieves good load balance among multiple BSs.",
author = "Ying Huang and Yan Gao and Klara Nahrstedt",
year = "2010",
month = "8",
day = "5",
doi = "10.1109/SECON.2010.5508234",
language = "English (US)",
isbn = "9781424471515",
series = "SECON 2010 - 2010 7th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks",
booktitle = "SECON 2010 - 2010 7th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks",

}

TY - GEN

T1 - Relay placement for reliable base station connectivity in polymorphous networks

AU - Huang, Ying

AU - Gao, Yan

AU - Nahrstedt, Klara

PY - 2010/8/5

Y1 - 2010/8/5

N2 - With emerging demand for online surveillance and management, persistent and reliable connectivity to base stations (BSs) is indispensable so that network operators, which have access to all BSs, can collect measurements from all wireless terminals in the field, monitor their status and respond to critical incidents in real-time. However, disconnected networks make reliable BS connectivity problematic. Many papers have studied the problem of placing the minimum number of relays to retain connectivity. However, none of them considered polymorphous networks, which have multiple topologies, due to terminal movement, unsynchronized wakeup schedule and packet forwarding policy. Our paper makes the first attempt towards the study of relay placement problem in polymorphous networks. We propose two heuristic algorithms, topology stitch algorithm and topology iterative algorithm, which are built upon constrained relay placement algorithms for monomorphous networks with a single topology. Also, we propose the weigh-and-place algorithm (WPA), which optimizes relay placement across topologies with balanced load based on integer programming formulation. Evaluation shows that WPA places a smaller number of relays than the other two heuristic algorithms and achieves good load balance among multiple BSs.

AB - With emerging demand for online surveillance and management, persistent and reliable connectivity to base stations (BSs) is indispensable so that network operators, which have access to all BSs, can collect measurements from all wireless terminals in the field, monitor their status and respond to critical incidents in real-time. However, disconnected networks make reliable BS connectivity problematic. Many papers have studied the problem of placing the minimum number of relays to retain connectivity. However, none of them considered polymorphous networks, which have multiple topologies, due to terminal movement, unsynchronized wakeup schedule and packet forwarding policy. Our paper makes the first attempt towards the study of relay placement problem in polymorphous networks. We propose two heuristic algorithms, topology stitch algorithm and topology iterative algorithm, which are built upon constrained relay placement algorithms for monomorphous networks with a single topology. Also, we propose the weigh-and-place algorithm (WPA), which optimizes relay placement across topologies with balanced load based on integer programming formulation. Evaluation shows that WPA places a smaller number of relays than the other two heuristic algorithms and achieves good load balance among multiple BSs.

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

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

U2 - 10.1109/SECON.2010.5508234

DO - 10.1109/SECON.2010.5508234

M3 - Conference contribution

AN - SCOPUS:77955106645

SN - 9781424471515

T3 - SECON 2010 - 2010 7th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks

BT - SECON 2010 - 2010 7th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks

ER -