Efficient Communication Strategies for Ad Hoc Wireless Networks |
| |
Authors: | M Adler C Scheideler |
| |
Affiliation: | (1) Department of Computer Science, University of Toronto, 10 King's College Road, Toronto, Ontario, Canada M5S 3G4 micah@cs.toronto.edu , CA;(2) Heinz Nixdorf Institute and Department of Mathematics and Computer Science, Paderborn University, 33095 Paderborn, Germany chrsch@uni-paderborn.de, DE |
| |
Abstract: | An ad hoc wireless network is a collection of wireless mobile hosts forming a temporary network without the aid of any established
infrastructure or centralized administration. This type of network is of great importance in situations where it is very difficult
to provide the necessary infrastructure, but it is a challenging task to enable fast and reliable communication within such
a network. In this paper we model and analyze the performance of so-called power-controlled ad hoc wireless networks: networks where the mobile hosts are able to change their transmission power. We concentrate on
finding schemes for routing arbitrary permutations in these networks. In general, it is NP-hard even to find an n
1-ε
-approximation for any constant ε to the fastest possible strategy for routing a given permutation problem on n mobile hosts. However, we demonstrate here that if we allow ourselves to consider slightly less general problems, efficient
solutions can be found.
We first demonstrate that there is a natural class of distributed schemes for handling node-to-node communication on top
of which online route selection and scheduling strategies can be constructed such that the performance of this class of schemes
can be exploited in a nearly optimal way for routing permutations in any static power-controlled ad hoc network. We then demonstrate
that if we restrict ourselves to the important case of routing between nodes distributed randomly in a Euclidean space, we
can route in a time that is asymptotically optimal for any routing scheme.
Received in final form January 31, 2000. Online publication October 10, 2000. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|