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 - 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

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Relay placement for reliable base station connectivity in polymorphous networks'. Together they form a unique fingerprint.

  • 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