Math @ Duke

Publications [#235364] of Pankaj K. Agarwal
Papers Published
 Sankararaman, S; Efrat, A; Ramasubramanian, S; Agarwal, PK, On channeldiscontinuityconstraint routing in wireless networks,
Ad Hoc Networks, vol. 13 no. PART A
(February, 2014),
pp. 153169, ISSN 15708705 [doi]
(last updated on 2018/05/24)
Abstract: Multichannel 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 "ChannelDiscontinuityConstraint" (CDC). CDCpaths are also useful in TDMA systems, where, preferably, consecutive links are assigned different timeslots. In the first part of this paper, we develop a tspanner for CDCpaths using spatial properties; a subnetwork containing O(n/θ) links, for any θ > 0, such that CDCpaths increase in cost by at most a factor t = (1  2 sin(θ/2)) 2 . We propose a novel distributed algorithm to compute the spanner using an expected number of O(n log n) fixedsize messages. In the second part, we present a distributed algorithm to find minimumcost CDCpaths between two nodes using O(n 2 ) fixedsize messages, by developing an extension of Edmonds' algorithm for minimumcost perfect matching. In a centralized implementation, our algorithm runs in O(n 2 ) time improving the previous best algorithm which requires O(n 3 ) running time. Moreover, this running time improves to O(n/θ) when used in conjunction with the spanner developed. © 2011 Elsevier B.V. All rights reserved.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

