On-Demand Relay Communication Infrastructure for Base Station Connectivity

Huang, Ying

Permalink

https://hdl.handle.net/2142/18243 Copy

Description

Title

On-Demand Relay Communication Infrastructure for Base Station Connectivity

Author(s)

Huang, Ying

Issue Date

2011-01-14T22:41:03Z

Director of Research (if dissertation) or Advisor (if thesis)

Nahrstedt, Klara

Doctoral Committee Chair(s)

Nahrstedt, Klara

Committee Member(s)

• Abdelzaher, Tarek F.
• Vaidya, Nitin H.
• Lu, Songwu

Department of Study

Computer Science

Discipline

Computer Science

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• Relay placement
• relay deployment
• Base Station (BS) - connectivity
• multi-commodity flow
• optimization

Abstract

In public safety and homeland security, reliable communication among the command center (CC), first responders (FRs) and surveillance sensors is critical to real-time monitoring and control applications. Com- manders want to check measurements from all surveillance sensors in the field and respond to critical incidents in real-time. In addition, commanders desire to monitor every FR’s location, health and device status to safeguard their lives. Frequently, they need to exchange dispatch commands and incident status with FRs in the field via voice. Occasionally, commanders inform FRs by transferring various data, such as building maps and fire hydrant locations, or pull back video feeds and text reports. We refer to the multi-functional mobile devices being monitored and controlled by CC as terminals. In order to support all these life-critical and mission-critical applications, a communication infrastructure offering reliable communication paths between CC and terminals is needed. However, such an infrastructure meeting various performance requirements from emergency response op- erations often does not exist. It is either impaired or nonfunctional due to incompatibility of radio frequency and communication protocols. Hence, we are interested in establishing a communication infrastructure on demand and cost-effectively, so that FRs can be continuously monitored, informed, managed and protected, while mobilized around a large incident area. In order to provision such a communication infrastructure, two means are taken simultaneously: (a) installing multiple base stations (BSs) to increase the coverage of the command center; (b) dropping relays to further extend the connectivity to BSs, especially when terminals are far away from BSs. In this thesis, we study various algorithms to determine the optimal locations of relays and the installation sequence so that the total number of relays is minimized, hence the infrastructure cost. We call such problems relay management problems. There are typically two categories for relay management problems: relay placement problems for static networks and relay deployment problems for mobile networks. Many papers have studied the relay placement and deployment problems. However, FR systems do exhibit special properties of disconnected evolving networks, which are either overlooked or treated primitively by the prior work. To the best of our knowledge, (a) none of the relay placement algorithms consider polymorphous networks with multiple topologies, due to terminal movement, unsynchronized wakeup schedule and packet forwarding policy; (b) all the prior work on relay deployment problems drop more relays than what is necessary, because they follow the “breadcrumb” approach, by which a FR will drop a relay whenever the connectivity to BSs is about to break. Despite having evolving network topologies, FR systems are not completely unpredictable. A large amount of operation planning and scheduling knowledge can be exploited in relay management. For poly- morphous networks, we have rudimentary knowledge about potential network configurations, e.g., where terminals will be placed or moved occasionally. For mobile networks, we know the coarse-level mobility patterns of FRs, e.g., the set of locations FRs will visit, from FRs dispatch and task assignment. In this thesis, we broadly exploit the predictability to deal with evolving topologies for FR systems, while meeting unique performance requirements, such as cost-effectiveness, reliability, load balance, etc. Weigh-and-place algorithm (WPA) is proposed to optimize relay placement across topologies with balanced load, reliably if required. Energy-aware relay placement is studied so that the communication infrastructure lasts for a desired network lifetime under different transmission control schemes. M-Breadcrumb, a mission-aware constrained relay deployment algorithm, is invented to minimize the total number of relays and navigate FRs to relay deploying locations with reduced traversal distance.

Graduation Semester

2010-12

Permalink

http://hdl.handle.net/2142/18243

Copyright and License Information

2010 by Ying Huang. All rights reserved.

Owning Collections