Book chapter
Topology Control with Limited Geometric Information
Principles of Distributed Systems, pp.427-442
Lecture Notes in Computer Science, Springer Berlin Heidelberg
2006
DOI: 10.1007/11795490_32
Abstract
Topology control is the problem of selecting neighbors for each node in a wireless network, so that the resulting network has a number of useful properties. More precisely, a topology control protocol P takes as input a network G and aims to construct a spanning subgraph GP, that is sparse, “energy minimizing” and has sufficient connectivity so as to guarantee multiple short paths between pairs of nodes in G. Currently, topology control protocols assume that nodes in G reside in some Euclidean (usually, 2-dimensional) space and rely on geometric information such as node locations and pairwise distances between nodes to produce GP with appropriate properties. However, these protocols are extremely sensitive to errors in location information and this feature makes them impractical because errors in location and distance information are pervasive in practical systems. This paper presents and analyzes two randomized topology control protocols that are tolerant to errors in pairwise distance estimates. The first protocol, called RTC (short for randomized topology control) uses no geometric information, relying only on connectivity information and is therefore completely immune to errors in location or distance information. The second protocol, called ε-RTC, generalizes the first protocol. Allowing for errors in distance estimates, but assuming that relative errors are bounded above by ε, the second protocol produces an output network that is symmetric, connected, sparse, and has good spanner properties. As \documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\varepsilon \longrightarrow 0$\end{document}, ε-RTC behaves like the XTC protocol (R. Wattenhofer and A. Zollinger, “XTC: A practical topology control algorithm for ad-hoc networks”, WMAN 2004) and for large values of ε, it behaves like RTC. Our results hold whenever the input network is a unit disk graph or even a quasi unit disk graph.
Details
- Title: Subtitle
- Topology Control with Limited Geometric Information
- Creators
- Kevin Lillis - University of IowaSriram V. Pemmaraju - University of Iowa
- Resource Type
- Book chapter
- Publication Details
- Principles of Distributed Systems, pp.427-442
- Publisher
- Springer Berlin Heidelberg; Berlin, Heidelberg
- Series
- Lecture Notes in Computer Science
- DOI
- 10.1007/11795490_32
- eISSN
- 1611-3349
- ISSN
- 0302-9743
- Language
- English
- Date published
- 2006
- Academic Unit
- Computer Science
- Record Identifier
- 9984259439402771
Metrics
3 Record Views