Monotone Percolation and The Topology Control of Wireless Networks

Jiang, Anxiao (Andrew) and Bruck, Jehoshua (2005) Monotone Percolation and The Topology Control of Wireless Networks. Technical Report. California Institute of Technology, Pasadena, CA. [CaltechPARADISE:2005.ETR065]

Full text available as:

PDF - Requires Adobe Acrobat Reader or other PDF viewer.

Abstract

This paper addresses the topology control problem for large wireless networks that are modelled by an infinite point process on a two-dimensional plane. Topology control is the process of determining the edges in the network by adjusting the transmission radii of the nodes. Topology control algorithms should be based on local decisions, be adaptive to changes, guarantee full connectivity and support efficient routing. We present a family of topology control algorithms that, respectively, achieve some or all of these requirements efficiently. The key idea in our algorithms is a concept that we call monotone percolation. In classical percolation theory, we are interested in the emergence of an infinitely large connected component. In contrast, in monotone percolation we are interested in the existence of a relatively short path that makes monotonic progress between any pair of source and destination nodes. Our key contribution is that we demonstrate how local decisions on the transmission radii can lead to monotone percolation and in turn to efficient topology control algorithms.

EPrint Type:	Monograph (Technical Report)
Additional Information:	The authors would like to thank Matthew Cook, Jie Gao and Michael Langberg for their helpful discussions, and thank the anonymous reviewers for their helpful comments. This work was supported in part by the Lee Center for Advanced Networking at the California Institute of Technology, and by NSF grant CCR-TC-0209042. http://www.paradise.caltech.edu/papers/etr065.pdf
Uncontrolled Keywords:	Combinatorics, Graph theory, Probability, Topology, Topology Control, Wireless network.
Subjects:	All Records
ID Code:	93
Deposited By:	Caltech Library System
Deposited On:	22 March 2005
Record Number:	CaltechPARADISE:2005.ETR065
Official Persistent URL:	http://resolver.caltech.edu/CaltechPARADISE:2005.ETR065
Usage Policy:	You are granted permission for individual, educational, research and non-commercial reproduction, distribution, display and performance of this work in any format.

Archive Staff Only: edit this record