[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.1145/2942358.2942389acmconferencesArticle/Chapter ViewAbstractPublication PagesmobihocConference Proceedingsconference-collections
research-article
Public Access

Throughput-optimal broadcast in wireless networks with dynamic topology

Published: 05 July 2016 Publication History

Abstract

We consider the problem of throughput-optimal broadcasting in time-varying wireless network with an underlying Directed Acyclic Graph (DAG) topology. Known broadcast algorithms route packets along pre-computed spanning trees. In large wireless networks with time-varying connectivities, the optimal trees are difficult to compute and maintain. In this paper we propose a new online throughput-optimal broadcast algorithm, which takes packet-by-packet scheduling and routing decisions, obviating the need for maintaining any global topological structures, such as spanning-trees. Our algorithm utilizes certain queue-like system-state information for making transmission decisions and hence, may be thought of as a generalization of the well-known back pressure algorithm, which makes point-to-point unicast transmission decisions based on local queue-length information. Technically, the back-pressure algorithm is derived by stabilizing the packet-queues. However, because of packet-duplications, the work-conservation principle is violated and appropriate queuing processes are difficult to define in the broadcast setting. To address this fundamental issue, we identify certain state-variables whose dynamics behave like virtual queues. By stochastically stabilizing these virtual queues, we devise a throughput-optimal broadcast policy. We also derive new characterizations of the broadcast-capacity of time-varying wireless DAGs and derive an efficient algorithm to compute the capacity exactly under certain assumptions, and a poly-time approximation algorithm for computing the capacity approximately under less restrictive assumptions.

References

[1]
P. Agrawal and N. Patwari. Correlated link shadow fading in multi-hop wireless networks. Wireless Communications, IEEE Transactions on, 8(8):4024--4036, 2009.
[2]
D. Bertsimas and J. N. Tsitsiklis. Introduction to linear optimization, volume 6. Athena Scientific Belmont, MA, 1997.
[3]
Y. Chu, S. Rao, S. Seshan, and H. Zhang. Enabling conferencing applications on the internet using an overlay muilticast architecture. A CM SIGCOMM computer communication review, 31(4):55--67, 2001.
[4]
R. G. Gallager. Discrete stochastic processes, volume 321. Springer Science & Business Media, 2012.
[5]
R. Gandhi, S. Parthasarathy, and A. Mishra. Minimizing broadcast latency and redundancy in ad hoc networks. In Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, pages 222--232. ACM, 2003.
[6]
M. Ge, S. V. Krishnamurthy, and M. Faloutsos. Overlay multicasting for ad hoc networks. In Proceedings of Third Annual Mediterranean Ad Hoc Networking Workshop, 2004.
[7]
T. Ho and H. Viswanathan. Dynamic algorithms for multicast with intra-session network coding. In Proc. 43rd Annual Allerton Conference on Communication, Control, and Computing, 2005.
[8]
S. C. Huang, P.-J. Wan, X. Jia, H. Du, and W. Shang. Minimum-latency broadcast scheduling in wireless ad hoc networks. In 26th IEEE INFOCOM 2007.
[9]
L. Junhai, Y. Danxia, X. Liu, and F. Mingyu. A survey of multicast routing protocols for mobile Ad-Hoc networks. Communications Surveys Tutorials, IEEE, 11(1):78--91, First 2009.
[10]
A. Kamthe, M. A. Carreira-Perpiñán, and A. E. Cerpa. Improving wireless link simulation using multilevel markov models. ACM Trans. Sen. Netw., 10(1):17:1--17:28, Dec. 2013.
[11]
X. Lin, N. Shroff, and R. Srikant. A tutorial on cross-layer optimization in wireless networks. Selected Areas in Communications, IEEE Journal on, 24(8):1452--1463, Aug 2006.
[12]
D. V. Lindley. The theory of queues with a single server. In Mathematical Proceedings of the Cambridge Philosophical Society, volume 48, pages 277--289. Cambridge Univ Press, 1952.
[13]
J. Macker, J. Klinker, and M. Corson. Reliable multicast data delivery for military networking. In Military Communications Conference, 1996. MILCOM '96, Conference Proceedings, IEEE, volume 2, pages 399--403 vol. 2, Oct 1996.
[14]
M. J. Neely. Stochastic network optimization with application to communication and queueing systems. Synthesis Lectures on Communication Networks, 3(1):1--211, 2010.
[15]
N. Patwari and P. Agrawal. Effects of correlated shadowing: Connectivity, localization, and rf tomography. In Information Processing in Sensor Networks, 2008. IPSN'08. International Conference on, pages 82--93. IEEE, 2008.
[16]
R. Rustin. Combinatorial Algorithms. Algorithmics Press, 1973.
[17]
S. Sarkar and L. Tassiulas. A framework for routing and congestion control for multicast information flows. Information Theory, IEEE Transactions on, 48(10):2690--2708, 2002.
[18]
A. Schrijver. Combinatorial optimization: polyhedra and efficiency, volume 24. Springer, 2003.
[19]
A. Sinha, G. Paschos, C. ping Li, and E. Modiano. Throughput-optimal broadcast on directed acyclic graphs. In Computer Communications (INFOCOM), 2015 IEEE Conference on, pages 1248--1256.
[20]
A. Sinha, L. Tassiulas, and E. Modiano. Tech report {online}: Throughput-Optimal Broadcast in Wireless Networks with Dynamic Topology, 2016. http://arxiv.org/abs/1604.00576
[21]
D. Smith. IP TV Bandwidth Demand: Multicast and channel surfing. In INFOCOM 2007. 26th IEEE International Conference on Computer Communications. IEEE, pages 2546--2550, May 2007.
[22]
L. Tassiulas and A. Ephremides. Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks. Automatic Control, IEEE Transactions on, 37(12):1936--1948, 1992.
[23]
D. Towsley and A. Twigg. Rate-optimal decentralized broadcasting: the wireless case, 2008.
[24]
D. Tse and P. Viswanath. Fundamentals of wireless communication. Cambridge university press, 2005.
[25]
D. B. West et al. Introduction to graph theory, volume 2. Prentice hall Upper Saddle River, 2001.
[26]
J. Yuan, Z. Li, W. Yu, and B. Li. A cross-layer optimization framework for multihop multicast in wireless mesh networks. Selected Areas in Communications, IEEE Journal on, 24(11), 2006.

Cited By

View all
  • (2024)A Tutorial-Cum-Survey on Percolation Theory With Applications in Large-Scale Wireless NetworksIEEE Communications Surveys & Tutorials10.1109/COMST.2023.333619426:1(428-460)Online publication date: Sep-2025
  • (2024)Traffic Divergence Theory: An Analysis Formalism for Dynamic NetworksIEEE Access10.1109/ACCESS.2024.338343612(67512-67524)Online publication date: 2024
  • (2023)The Stochastic Network ModelLearning for Decision and Control in Stochastic Networks10.1007/978-3-031-31597-8_2(5-12)Online publication date: 20-Jun-2023
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
MobiHoc '16: Proceedings of the 17th ACM International Symposium on Mobile Ad Hoc Networking and Computing
July 2016
421 pages
ISBN:9781450341844
DOI:10.1145/2942358
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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 July 2016

Permissions

Request permissions for this article.

Check for updates

Badges

  • Best Paper

Qualifiers

  • Research-article

Funding Sources

Conference

MobiHoc'16
Sponsor:

Acceptance Rates

Overall Acceptance Rate 296 of 1,843 submissions, 16%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)54
  • Downloads (Last 6 weeks)11
Reflects downloads up to 14 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2024)A Tutorial-Cum-Survey on Percolation Theory With Applications in Large-Scale Wireless NetworksIEEE Communications Surveys & Tutorials10.1109/COMST.2023.333619426:1(428-460)Online publication date: Sep-2025
  • (2024)Traffic Divergence Theory: An Analysis Formalism for Dynamic NetworksIEEE Access10.1109/ACCESS.2024.338343612(67512-67524)Online publication date: 2024
  • (2023)The Stochastic Network ModelLearning for Decision and Control in Stochastic Networks10.1007/978-3-031-31597-8_2(5-12)Online publication date: 20-Jun-2023
  • (2023)IntroductionLearning for Decision and Control in Stochastic Networks10.1007/978-3-031-31597-8_1(1-4)Online publication date: 20-Jun-2023
  • (2021)Distributed Broadcasting in Dynamic NetworksIEEE/ACM Transactions on Networking10.1109/TNET.2021.308781829:5(2142-2155)Online publication date: Oct-2021
  • (2021)Implementing The Abstract MAC Layer in Dynamic NetworksIEEE Transactions on Mobile Computing10.1109/TMC.2020.297159920:5(1832-1845)Online publication date: 1-May-2021
  • (2019)Broadcasting Real-Time Flows in Integrated Backhaul and Access 5G Networks2019 International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOPT)10.23919/WiOPT47501.2019.9144141(1-8)Online publication date: Jun-2019
  • (2019)Performance optimization of wireless sensor networks2019 Open Innovations (OI)10.1109/OI.2019.8908209(30-35)Online publication date: Oct-2019
  • (2019)Throughput and Packet Displacements of Dynamic Broadcasting AlgorithmsAlgorithms for Sensor Systems10.1007/978-3-030-34405-4_9(158-174)Online publication date: 5-Nov-2019
  • (2018)Joint Optimization of Multicast Energy in Delay-Constrained Mobile Wireless NetworksIEEE/ACM Transactions on Networking10.1109/TNET.2018.279063926:1(633-646)Online publication date: 1-Feb-2018
  • Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media