Distributed Algorithms for End-to-End Packet Scheduling in Wireless Ad Hoc Networks
Authors: 
V. S. Anil Kumar, 
Madhav V. Marathe, Srinivasan Parthasarathy, Aravind SrinivasanAuthors Info & Claims
Article No.: 28, Pages 1 - 25
Abstract
Packet scheduling is a particular challenge in wireless networks due to interference from nearby transmissions. A distance-2 interference model serves as a useful abstraction here, and we study packet routing and scheduling under this model of interference. The main focus of our work is the development of fully distributed (decentralized) protocols. We present polylogarithmic/constant factor approximation algorithms for various families of disk graphs (which capture the geometric nature of wireless-signal propagation), as well as near-optimal approximation algorithms for general graphs. A basic distributed coloring procedure, originally due to Luby [1993] (Journal of Computer and System Sciences, 47:250--286, 1993), underlies many of our algorithms. The work of Finocchi et al. [2002] (Proc. ACM-SIAM Symposium on Discrete Algorithms, 2002) showed that a natural modification of this algorithm leads to improved performance. A rigorous explanation of this was left as an open question, and we prove that the modified algorithm is indeed provably better in the worst case.
References
[1]
N. Alon, F. Chung, and R. Graham. 1994. Routing permutations on graphs via matchings. SIAM Journal of Discrete Mathematics 7 (1994), 513--530.
[2]
M. Andrews. 2000. Probabilistic end-to-end delay bounds for earliest deadline first scheduling. In Proceedings of the IEEE Conference of Computer and Communications Societies (INFOCOM’00), Vol. 2. 603--612.
[3]
M. Andrews, A. Fernandez, M. Harchol-Balter, T. Leighton, and L. Zhang. 1997. General dynamic routing with per-packet delay guarantees of O(distance+1/session rate). In Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS’97). 294--302.
[4]
F. Meyer auf der Heide, C. Schindelhauer, K. Volbert, and M. Grünewald. 2004. Congestion, dilation, and energy in radio networks. Theory of Computer Systems 37, 3 (2004), 343--370.
[5]
F. Meyer auf der Heide and B. Vöcking. 1995. A packet routing protocol for arbitrary networks. Lecture Notes in Computer Science 439 (1995), 291--302.
[6]
B. Awerbuch, B. Berger, L. Cowen, and D. Peleg. 1994. Low-diameter graph decomposition is in NC. Random Structures & Algorithms 5 (1994), 441--452.
[7]
B. Awerbuch, A. V. Goldberg, M. Luby, and S. A. Plotkin. 1989. Network decomposition and locality in distributed computation. In Proceedings of the IEEE Symposium on Foundations of Computer Science. 364--369.
[8]
B. Awerbuch and D. Peleg. 1992. Routing with polynomial communication-space trade-off. SIAM Journal on Discrete Mathematics 5 (1992), 151--162.
[9]
H. Balakrishnan, C. Barrett, V. S. Anil Kumar, M. Marathe, and S. Thite. 2004. The distance-2 matching problem and its relationship to the MAC-layer capacity of ad hoc wireless networks. IEEE Journal on Selected Areas in Communications (JSAC) 22, 6 (2004), 1069--1079.
[10]
V. Bonifaci, P. Korteweg, A. Marchetti-Spaccamela, and L. Stougie. 2011. Minimizing flow time in the wireless gathering problem. ACM Transactions on Algorithms 7, 3, Article 33 (July 2011), 20 pages.
[11]
D. Chafekar, V. S. Anil Kumar, M. V. Marathe, S. Parthasarathy, and A. Srinivasan. 2007. Cross-layer latency minimization in wireless networks with SINR constraints. In Proceedings of the ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc’07). 110--119.
[12]
H. Chernoff. 1952. A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Annals of Mathematical Statistics 23 (1952), 493--509.
[13]
J. Dams, M. Hoefer, and T. Kesselheim. 2012. Scheduling in wireless networks with rayleigh-fading interference. In Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA’12).
[14]
M. Dinitz. 2010. Distributed algorithms for approximating wireless network capacity. In Proceedings of the 29th Conference of the IEEE Communications Society (INFOCOM’10). 1397--1405.
[15]
D. Dubhashi, A. Mei, A. Panconesi, J. Radhakrishnan, and A. Srinivasan. 2005. Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons. Journal of Computer and System Sciences 71, 4 (2005), 467--479.
[16]
A. Fanghänel, T. Kesselheim, and B Vöcking. 2009. Improved algorithms for latency minimization in wireless networks. In Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP’09). 447--458.
[17]
I. Finocchi, A. Panconesi, and R. Silvestri. 2002. Experimental analysis of simple, distributed vertex coloring algorithms. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 606--615.
[18]
D. A. Grable and A. Panconesi. 2000. Fast distributed algorithms for brooks-vizing colorings. Journal of Algorithms 37 (2000), 85--120.
[19]
M. M. Halldórsson and P. Mitra. 2011. Nearly optimal bounds for distributed wireless scheduling in the SINR model. In Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP’11).
[20]
M. M. Halldórsson and T. Tonoyan. 2015. How well can graphs represent wireless interference? In Proceedings of the ACM Symposium on Theory of Computing (STOC’15).
[21]
M. M. Halldórsson and R. Wattenhofer. 2009. Wireless communication is in APX. In International Colloquium on Automata, Languages and Programming (ICALP’09). 525--536.
[22]
W. Hoeffding. 1963. Probability inequalities for sums of bounded random variables. American Statistical Association Journal 58 (1963), 13--30.
[23]
T. Kesselheim. 2012. Approximation algorithms for wireless link scheduling with flexible data rates. In Proc. European Symposium on Algorithms (ESA’12).
[24]
S. O. Krumke, M. V. Marathe, and S. S. Ravi. 2001. Models and approximation algorithms for channel assignment in radio networks. Wireless Networks 7, 6 (2001), 575--584.
[25]
V. S. Anil Kumar, M. Marathe, and S. Parthasarathy. 2008. Cross-layer capacity estimation and throughput maximization in wireless networks. Handbook on Algorithms for Next Generation Networks (2008).
[26]
V. S. Anil Kumar, M. V. Marathe, S. Parthasarathy, and A. Srinivasan. 2004. End-to-end packet scheduling in Ad hoc networks. In Proc. ACM SIAM Symposium on Discrete Algorithms (SODA’04).
[27]
V. S. Anil Kumar, M. V. Marathe, S. Parthasarathy, and A. Srinivasan. 2005. Algorithmic aspects of capacity in wireless networks. In Proc. of the ACM International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS’05). ACM, New York, NY, 133--144.
[28]
F. T. Leighton, B. M. Maggs, and A. W. Richa. 1999. Fast algorithms for finding O(Congestion + Dilation) packet routing schedules. Combinatorica 19, 2 (1999), 1--27.
[29]
T. Leighton, B. Maggs, and S. Rao. 1994. Packet routing and job shop scheduling in O(Congestion+Dilation) steps. Combinatorica 14, 2 (1994), 167--180.
[30]
N. Linial. 1992. Locality in distributed graph algorithms. SIAM Journal on Computing 21 (1992), 193--201.
[31]
N. Linial and M. Saks. 1993. Low diameter graph decompositions. Combinatorica 13 (1993), 441--454.
[32]
Z. Lotker and D. Peleg. 2010. Structure and algorithms in the SINR wireless model. ACM SIGACT News (2010).
[33]
M. Luby. 1993. Removing randomness in parallel computation without a processor penalty. Journal of Computer and System Sciences 47, 2 (1993), 250--286.
[34]
R. Ostrovsky and Y. Rabani. 1997. Universal O(Congestion + Dilation + log 1 + ε(N)) local control packet switching algorithms. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing. ACM, 644--653.
[35]
A. Panconesi and A. Srinivasan. 1996. On the complexity of distributed network decomposition. Journal of Algorithms 20, 2 (1996), 356--374.
[36]
G. Pei and A. K. S. Vullikanti. 2012. Brief announcement: Distributed algorithms for maximum link scheduling under the physical interference model. In Proceedings of the International Symposium on Distributed Computing (DISC’12).
[37]
L. Peterson and B. Davie. 2000. Computer Networks: A Systems Approach. Morgan Kaufman Publishers.
[38]
S. Ramanathan. 1993. Scheduling Algorithms for Multi-Hop Radio Networks. (1993). Ph.D. thesis, Department of Computer Science, University of Delaware.
[39]
S. Ramanathan. 1999. A unified framework and algorithm for channel assignment in wireless networks. Wireless Networks 5, 2 (1999), 81--94.
[40]
S. Ramanathan and E. L. Lloyd. 1993. Scheduling algorithms for multihop radio networks. IEEE/ACM Transactions on Networking 1, 2 (1993), 166--177.
[41]
S. Ruhrup, C. Schindelhauer, K. Volbert, and M. Grunewald. 2003. Performance of distributed algorithms for topology control in wireless networks. In Proceedings of the IEEE International Parallel and Distributed Processing Symposium (IPDPS’03).
[42]
C. Scheideler. 1998. Universal routing strategies for interconnection networks. Lecture Notes in Computer Science 1390 (1998).
[43]
A. Srinivasan and C.-P. Teo. 2001. A constant-factor approximation algorithm for packet routing and balancing local vs. global criteria. SIAM Journal on Computing 30, 6 (2001), 2051--2068.
[44]
P.-J. Wan, X. Jia, and F. Yao. 2009. Maximum independent set of links under physical interference model. In Proceedings of Wireless Algorithms, Systems, and Applications (WASA). 169--178.
[45]
D. Zuckerman. 2007. Linear degree extractors and the inapproximability of max clique and chromatic number. Theory of Computing 3, 1 (2007), 103--128.
Index Terms
- Distributed Algorithms for End-to-End Packet Scheduling in Wireless Ad Hoc Networks
Recommendations
Distributed algorithms for connected domination in wireless networks
We present fast distributed local control connected dominating set (CDS) algorithms for wireless ad hoc networks. We present two randomized distributed algorithms, CDSColor and CDSTop which take into account the effect of wireless interference and the ...
A Beaconless Minimum Interference Based Routing Protocol to Minimize End-to-End Delay per Packet for Mobile Ad hoc Networks
The authors propose a beaconless, on-demand, mobile ad hoc network routing protocol called minimum interference based routing protocol MIF that minimizes the end-to-end delay per data packet. During route discovery, each node inserts its identification ...
Logarithmic expected packet delivery delay in mobile ad hoc wireless networks: Research Articles
Special Issue: Scalability Issues in Wireless Networks—Architectures, Protocols and ServicesIt has been shown that in a mobile ad hoc wireless network per node throughput remains constant as the number of nodes approaches infinity, when the nodes lie in a disk of unit area. However, this requires that some packets are delivered indirectly by a ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
June 2016
408 pages
Copyright © 2016 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 25 April 2016
Accepted: 01 August 2015
Revised: 01 July 2015
Received: 01 July 2012
Published in TALG Volume 12, Issue 3
Check for updates
Author Tags
Qualifiers
- Research-article
- Research
- Refereed
Funding Sources
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 526Total Downloads
- Downloads (Last 12 months)57
- Downloads (Last 6 weeks)6
Reflects downloads up to 11 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in