skip to main content
article

Efficient broadcasting using network coding

Published: 02 April 2008 Publication History

Abstract

We consider the problem of broadcasting in an ad hoc wireless network, where all nodes of the network are sources that want to transmit information to all other nodes. Our figure of merit is energy efficiency, a critical design parameter for wireless networks since it directly affects battery life and thus network lifetime. We prove that applying ideas from network coding allows to realize significant benefits in terms of energy efficiency for the problem of broadcasting, and propose very simple algorithms that allow to realize these benefits in practice. In particular, our theoretical analysis shows that network coding improves performance by a constant factor in fixed networks. We calculate this factor exactly for some canonical configurations. We then show that in networks where the topology dynamically changes, for example due to mobility, and where operations are restricted to simple distributed algorithms, network coding can offer improvements of a factor of log n, where n is the number of nodes in the network. We use the insights gained from the theoretical analysis to propose low-complexity distributed algorithms for realistic wireless ad hoc scenarios, discuss a number of practical considerations, and evaluate our algorithms through packet level simulation.

References

[1]
{1} R. Ahlswede, N. Cai, S. R. Li, and R. W. Yeung, "Network information flow," IEEE Trans. Inf. Theory, vol. 46, no. 4, pp. 1204-1216, Jul. 2000.
[2]
{2} S.-Y. R. Li, R. W. Yeung, and N. Cai, "Linear network coding," IEEE Trans. Inf. Theory, vol. 49, pp. 371-381, Feb. 2003.
[3]
{3} C. Gkantsidis and P. Rodriguez, "Network coding for large scale content distribution," in IEEE INFOCOM, Miami, FL, Mar. 2005.
[4]
{4} C. Diot, J. Scott, E. Upton, and M. Liberatore, "The Haggle architecture," Intel Research Cambridge, Tech. Rep. IRC-TR-04-016, 2004.
[5]
{5} K. Fall, "A delay-tolerant network architecture for challengend internets," in ACM SIGCOMM, Karlsruhe, Germany, Aug. 2003.
[6]
{6} M. Mitzenmacher and E. Upfal, Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge, U.K.: Cambridge Univ. Press, 2005.
[7]
{7} S. Deb and M. Medard, "Algebraic gossip: A network coding approach to optimal multiple rumor mongering," in Annu. Allerton Conf. Communication, Control, and Computing, Univ. of Illinois at Urbana-Champaign, Oct. 2004.
[8]
{8} A. Demers, D. Greene, C. Hauser, W. Irish, J. Larson, S. Shenker, H. Sturgis, D. Swinehart, and D. Terry, "Epidemic algorithms for replicated database maintenance," ACM SIGOPS Operating Syst. Rev., vol. 22, no. 1, pp. 8-32, Jan. 1988.
[9]
{9} R. Karp, C. Schindelhauer, S. Shenker, and B. Vocking, "Randomized rumor spreading," in Proc. SODA, San Francisco, CA, Jan. 9-11, 2000.
[10]
{10} D. Mosk-Aoyama and D. Shah, "Information dissemination via network coding," in Proc. ISIT, Jul. 2006, pp. 1748-1752.
[11]
{11} M. Elkin and G. Kortsarzk, "Logarithmic in approximability of the radio broadcast problem," J. Algorithms, vol. 52, pp. 8-25, Jul. 2004.
[12]
{12} N. Alon, A. Bar-Noy, N. Linial, and D. Peleg, "On the complexity of radio communication," in Proc. 21st ACM Symp. Theory of Computing (STOC), 1989, pp. 274-285.
[13]
{13} R. Prakash, A. Schiper, M. Mohsin, D. Cavin, and Y. Sasson, "A lower bound for broadcasting in mobile ad hoc networks," Tech. Rep. (IC/ 2004/37), Jun. 2004.
[14]
{14} K. Jain and K. Talwar, "On the power saving of network coding," in Proc. Allerton Conf., Allerton, IL, Oct. 2005.
[15]
{15} Y.-C. Tseng, S.-Y. Ni, Y.-S. Chen, and J.-P. Sheu, "The broadcast storm problem in a mobile ad hoc network," in ACM/IEEE MobiCom, Seattle, WA, Aug. 1999.
[16]
{16} Y. Sasson, D. Cavin, and A. Schiper, "Probabilistic broadcast for flooding in wireless mobile ad hoc networks," in IEEE WCNC, New Orleans, LA, Mar. 2003.
[17]
{17} Z. J. Haas, J. Y. Halpern, and L. Li, "Gossip-based ad hoc routing," in IEEE INFOCOM, New York, NY, Jun. 2002.
[18]
{18} B. Chen, K. Jamieson, H. Balakrishnan, and R. Morris, "Span: An energy-efficient coordination algorithm for topology maintenance in ad hoc wireless networks," ACM Wireless Networks J., pp. 85-96, Sep. 2002.
[19]
{19} I. Stojmenovic, M. Seddigh, and J. Zunic, "Dominating sets and neighbor elimination-based broadcasting algorithms in wireless networks," IEEE Trans. Parallel Distrib. Syst., vol. 15, no. 11, pp. 1054-1055, Jan. 2002.
[20]
{20} J. Wu and F. Dai, "A generic distributed broadcast scheme in ad hoc wireless networks," IEEE Trans. Computers, vol. 53, no. 10, pp. 1343-1354, Oct. 2004.
[21]
{21} Y. Wu, P. A. Chou, and K. Jain, "A comparison of network coding and tree packing," in ISIT 2004, Chicago, IL, 2004.
[22]
{22} D. S. Lun, N. Ratnakar, R. Koetter, M. Medard, E. Ahmed, and H. Lee, "Achieving minimum-cost multicast: A decentralized approach based on network coding," in IEEE INFOCOM, Miami, FL, Mar. 2005.
[23]
{23} Y. Wu, P. A. Chou, and S.-Y. Kung, "Minimum-energy multicast in mobile ad hoc networks using network coding," in IEEE Information Theory Workshop, San Antonio, TX, Oct. 2004.
[24]
{24} D. Lun, M. Medard, T. Ho, and R. Koetter, "Network coding with a cost criterion," in ISITA, Parma, Italy, Oct. 2004.
[25]
{25} P. A. Chou, Y. Wu, and K. Jain, "Practical network coding," in Proc. Allerton Conf., Allerton, IL, Oct. 2003.
[26]
{26} R. Koetter and M. Medard, "Beyond routing: An algebraic approach to network coding," in Proc. IEEE INFOCOM, Jun. 2002, vol. 1, pp. 122-130.
[27]
{27} J. T. Schwartz, "Fast probabilistic algorithms for verification of polynomial identities," J. ACM, vol. 27, pp. 701-717, 1980.
[28]
{28} S. Jaggi, P. Chou, and K. Jain, "Low complexity algebraic multicast network codes," in Proc. ISIT, 2003, p. 368.
[29]
{29} T. Ho, M. Mèdard, J. Shi, M. Effros, and D. R. Karger, "On randomized network coding," in Proc. Allerton Conf., Monticello, IL, Oct. 2003.
[30]
{30} C. Fragouli, J. Widmer, and J.-Y. L. Boudec, "A network coding approach to energy efficient broadcasting: From theory to practice," in IEEE INFOCOM, Barcelona, Spain, Apr. 2006.
[31]
{31} C. H. Lim and P. J. Lee, "More flexible exponentiation with precomputation," in Proc. Advances in Cryptology: 14th Annu. Int. Cryptology Conf., Santa Barbara, CA, Aug. 1994.
[32]
{32} P. Pakzad, C. Fragouli, and A. Shokrollahi, "Coding schemes for line networks," in ISIT 2005, Adelaide, Australia.
[33]
{33} J. Blömer, R. Karp, and E. Welzl, "The rank of sparse random matrices over finite fields," Random Structures Algorithms, vol. 10, pp. 407-419, 1997.
[34]
{34} A. Shokrollahi, "Raptor codes," IEEE Trans. Inf. Theory, vol. 52, no. 6, pp. 2551-1567, 2004.

Cited By

View all
  • (2024)Enabling Distributed Control of Vehicle Platooning via Over-the-Air ConsensusIEEE Transactions on Wireless Communications10.1109/TWC.2024.345170323:11_Part_2(17205-17221)Online publication date: 1-Nov-2024
  • (2023)Low Latency Allcast Over Broadcast Erasure ChannelsIEEE Transactions on Information Theory10.1109/TIT.2022.321977369:3(1604-1617)Online publication date: 1-Mar-2023
  • (2022)To overhear or not to overhear: a dilemma between network coding gain and energy consumption in multi-hop wireless networksWireless Networks10.1007/s11276-018-1733-025:7(4097-4113)Online publication date: 11-Mar-2022
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking
IEEE/ACM Transactions on Networking  Volume 16, Issue 2
April 2008
244 pages

Publisher

IEEE Press

Publication History

Published: 02 April 2008
Published in TON Volume 16, Issue 2

Author Tags

  1. network coding
  2. wireless broadcast

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)1
  • Downloads (Last 6 weeks)0
Reflects downloads up to 18 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2024)Enabling Distributed Control of Vehicle Platooning via Over-the-Air ConsensusIEEE Transactions on Wireless Communications10.1109/TWC.2024.345170323:11_Part_2(17205-17221)Online publication date: 1-Nov-2024
  • (2023)Low Latency Allcast Over Broadcast Erasure ChannelsIEEE Transactions on Information Theory10.1109/TIT.2022.321977369:3(1604-1617)Online publication date: 1-Mar-2023
  • (2022)To overhear or not to overhear: a dilemma between network coding gain and energy consumption in multi-hop wireless networksWireless Networks10.1007/s11276-018-1733-025:7(4097-4113)Online publication date: 11-Mar-2022
  • (2019)Multisource Rumor Spreading with Network CodingIEEE INFOCOM 2019 - IEEE Conference on Computer Communications10.1109/INFOCOM.2019.8737576(2359-2367)Online publication date: 29-Apr-2019
  • (2018)MixerProceedings of the 16th ACM Conference on Embedded Networked Sensor Systems10.1145/3274783.3274849(145-158)Online publication date: 4-Nov-2018
  • (2018)Hand: Header-Assisted Network Decoding2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)10.1109/ICASSP.2018.8462564(3744-3748)Online publication date: 15-Apr-2018
  • (2017)One for All, All for OneProceedings of the 4th ACM Workshop on Hot Topics in Wireless10.1145/3127882.3127884(19-23)Online publication date: 16-Oct-2017
  • (2017)Fountain-Coded File Spreading Over Mobile NetworksIEEE Transactions on Wireless Communications10.1109/TWC.2017.273087416:10(6766-6778)Online publication date: 1-Oct-2017
  • (2017)Deterministic Broadcasting and Random Linear Network Coding in Mobile Ad Hoc NetworksIEEE/ACM Transactions on Networking10.1109/TNET.2016.264168025:3(1540-1554)Online publication date: 1-Jun-2017
  • (2016)Analyzing Network Coding (Gossip) Made EasyJournal of the ACM10.1145/262969663:3(1-22)Online publication date: 22-Aug-2016
  • Show More Cited By

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media