Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke





.......................

.......................


Publications [#235364] of Pankaj K. Agarwal

Papers Published

  1. Sankararaman, S; Efrat, A; Ramasubramanian, S; Agarwal, PK, On channel-discontinuity-constraint routing in wireless networks, Ad Hoc Networks, vol. 13 no. PART A (February, 2014), pp. 153-169, ISSN 1570-8705 [doi]
    (last updated on 2017/12/11)

    Abstract:
    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 in TDMA systems, where, preferably, consecutive links are assigned different time-slots. In the first part of this paper, we develop a t-spanner for CDC-paths using spatial properties; a sub-network containing O(n/θ) links, for any θ > 0, such that CDC-paths 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) fixed-size messages. In the second part, we present a distributed algorithm to find minimum-cost CDC-paths between two nodes using O(n 2 ) fixed-size messages, by developing an extension of Edmonds' algorithm for minimum-cost 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 27708-0320