On Channel-Discontinuity-Constraint Routing in Wireless Networks.
Multi-channel wireless networks are increasingly deployed as infrastructure networks, e.g. in metro areas. Network nodes frequently employ directional antennas to improve spatial throughput. In such networks, between two nodes, it is of interest to compute a path with a channel assignment for the links such that the path and link bandwidths are the same. This is achieved when any two consecutive links are assigned different channels, termed as "Channel-Discontinuity-Constraint" (CDC). CDC-paths are also useful inTDMAsystems, where, preferably, consecutive links are assigned different time-slots. In the first part of this paper, we develop at-spanner for CDC-paths using spatial properties; a sub-network containingO(n/θ) links, for anyθ> 0, such that CDC-paths increase in cost by at most a factort= (1-2 sin (θ/2))-2. We propose a novel distributed algorithm to compute the spanner using an expected number ofO(nlogn) fixed-size messages. In the second part, we present a distributed algorithm to find minimum-cost CDC-paths between two nodes usingO(n2) fixed-size messages, by developing an extension of Edmonds' algorithm for minimum-cost perfect matching. In a centralized implementation, our algorithm runs inO(n2) time improving the previous best algorithm which requiresO(n3) running time. Moreover, this running time improves toO(n/θ) when used in conjunction with the spanner developed.
Department of Computer Science, The University of Arizona, Tucson, AZ, USA.
Swaminathan
S
Sankararaman
Department of Computer Science, The University of Arizona, Tucson, AZ, USA.
Alon
A
Efrat
Department of Electrical and Computer Engineering, The University of Arizona, Tucson, AZ, USA.
Srinivasan
S
Ramasubramanian
Department of Computer Science, Duke University, Durham, NC, USA.
Pankaj K
PK
Agarwal
algorithms; directional antennas; routing; spanners