• Previous Article
    Load distribution performance of super-node based peer-to-peer communication networks: A nonstationary Markov chain approach
  • NACO Home
  • This Issue
  • Next Article
    Optimal visiting order of isolated clusters in DTNs to minimize the total mean delivery delay of bundles
2011, 1(4): 577-592. doi: 10.3934/naco.2011.1.577

Asynchronous multiple source network coding for wireless broadcasting

1. 

Graduate School of Engineering, Osaka University, Suita, 5650871, Japan, Japan, Japan

2. 

College of Information Science and Engineering, Ritsumeikan University, Kusatsu-Shi, 5258577, Japan

Received  May 2011 Revised  August 2011 Published  November 2011

In multi-hop wireless networks, broadcasting with flooding causes significant packet loss and battery power consumption, which is referred to as the broadcast storm problem. In this paper, we consider the broadcast storm problem in a broadcasting system in which each node generates a new packet periodically as in routing protocols. In order to resolve the problem, we apply network coding, which can reduce the number of forwarded packets by encoding several packets into a single packet at intermediate nodes. We propose a broadcasting system called asynchronous multiple-source network coding (AMSNC), where nodes encode received packets asynchronously generated from different source nodes. In order to apply multiple-source network coding to large multi-hop wireless networks, AMSNC has two mechanisms: timer-based coding scheduling and packet header format with compressed coding vector. With the timer-based coding scheduling, AMSNC effectively encodes packets asynchronously generated at source nodes. Further, with the packet header format with a compressed coding vector, we resolve the overhead problem, where the length of coding vectors becomes long in large multi-hop wireless networks. Simulation results show that AMSNC reduces the number of forwarded packets significantly and improves packet loss rate, end-to-end delay, and radio resource consumption.
Citation: Keisuke Minami, Takahiro Matsuda, Tetsuya Takine, Taku Noguchi. Asynchronous multiple source network coding for wireless broadcasting. Numerical Algebra, Control and Optimization, 2011, 1 (4) : 577-592. doi: 10.3934/naco.2011.1.577
References:
[1]

R. Ahlswede, N. Cai, S. Y. Li and R. Yeung, Network information flow, IEEE Trans. Inf. Theory, 46 (2000), 1204-1216. doi: 10.1109/18.850663.

[2]

P. A. Chou, Y. Wu and K. Jain, Practical network coding, Proc. 41st Allerton Conf. Commun., Cont. and Comput., 2003.

[3]

T. Clausen and P. Jacquet, Optimized link state routing protocol (OLSR), RFC3626, 2003.

[4]

C. Fragouli, J. Widmer and J. Y. Le Boudec, Efficient broadcasting using network coding, IEEE/ACM Trans. Netw., 16 (2008), 450-463. doi: 10.1109/TNET.2007.901080.

[5]

M. Jafari, L. Keller, C. Fragouli and K. Argyraki, Compressed network coding vectors, Proc. IEEE ISIT, (2009), 109-113. doi: 10.1109/ISIT.2009.5206041.

[6]

T. Ho, M. Médard, R. Koetter, D. R. Karger, M. Effros and B. Leong, A random linear network coding approach to multicast, IEEE Trans. Inf. Theory, 52 (2006), 4413-4430. doi: 10.1109/TIT.2006.881746.

[7]

Y. Kondo, H. Yomo, S. Yamaguchi, P. Davis, R. Miura and S. Obana, Reliable wireless broadcast with random network coding for real-time applications, Proc. IEEE WCNC, 2009. doi: 10.1109/WCNC.2009.4917943.

[8]

S. Li and A. Ramamoorthy, Improved compression of network coding vectors using erasure decoding and list decoding, IEEE Commun. Letters, 14 (2010), 749-751. doi: 10.1109/LCOMM.2010.08.092453.

[9]

L. Li, R. Ramjee, M. Buddhikot and S. Miller, Network coding-based broadcast in mobile ad hoc networks, Proc. IEEE INFOCOM 2007, (2007), 1739-1747. doi: 10.1109/INFCOM.2007.203.

[10]

S. Y. Li, R. W. Yeung and N. Cai, Linear network coding, IEEE Trans. Inf. Theory, 29 (2003), 371-381. doi: 10.1109/TIT.2002.807285.

[11]

T. Matsuda, T. Noguchi and T. Takine, Survey of network coding and its applications, IEICE Trans. Commun., E94-B (2011), 698-717. doi: 10.1587/transcom.E94.B.698.

[12]

T. Matsuda, T. Noguchi and T. Takine, Broadcasting with randomized network coding in dense wireless ad hoc networks, IEICE Trans. Commun., E91-B (2008), 3216-3225. doi: 10.1093/ietcom/e91-b.10.3216.

[13]

S. Y. Ni, Y. C. Tseng, Y. S. Chen and J. P Sheu, The broadcast storm problem in a mobile ad hoc network, Proc. ACM Mobicom 99, (1999), 151-162. doi: 10.1023/A:1013763825347.

[14]

D. Nguyen, T. Tran, T. Nguyen and B. Bose, Wireless broadcast using network coding, IEEE Trans. Veh. Technol., 58 (2009), 914-925. doi: 10.1109/TVT.2008.927729.

[15]

W. Peng and X. C. Lu, On the reduction of broadcast redundancy in mobile ad hoc networks, Proc. ACM Mobihoc 2000, (2000), 129-130.

[16]

M. Sheng, J. Li and Y. Shi, Relative degree adaptive flooding broadcast algorithm for ad hoc networks, IEEE Trans. Broadcast., 51 (2005), 216-222. doi: 10.1109/TBC.2005.847624.

[17]

A. S. Tanenbaum, "Computer Networks,'' 4th edition, Prentice Hall, Upper Saddle River, NJ, 2002.

[18]

, Wireless LAN medium access control (MAC) and physical layer (PHY) specifications,, IEEE Std. 802.11, (1999). 

[19]

N. Wisitpongphan, O. K. Tonguz, J.S. Parikh, P. Mudalige, F. Bai and V. Sadekar, Broadcast storm mitigation techniques in vehicular ad hoc networks, IEEE Wireless Communications, 14 (2007), 84-94. doi: 10.1109/MWC.2007.4407231.

show all references

References:
[1]

R. Ahlswede, N. Cai, S. Y. Li and R. Yeung, Network information flow, IEEE Trans. Inf. Theory, 46 (2000), 1204-1216. doi: 10.1109/18.850663.

[2]

P. A. Chou, Y. Wu and K. Jain, Practical network coding, Proc. 41st Allerton Conf. Commun., Cont. and Comput., 2003.

[3]

T. Clausen and P. Jacquet, Optimized link state routing protocol (OLSR), RFC3626, 2003.

[4]

C. Fragouli, J. Widmer and J. Y. Le Boudec, Efficient broadcasting using network coding, IEEE/ACM Trans. Netw., 16 (2008), 450-463. doi: 10.1109/TNET.2007.901080.

[5]

M. Jafari, L. Keller, C. Fragouli and K. Argyraki, Compressed network coding vectors, Proc. IEEE ISIT, (2009), 109-113. doi: 10.1109/ISIT.2009.5206041.

[6]

T. Ho, M. Médard, R. Koetter, D. R. Karger, M. Effros and B. Leong, A random linear network coding approach to multicast, IEEE Trans. Inf. Theory, 52 (2006), 4413-4430. doi: 10.1109/TIT.2006.881746.

[7]

Y. Kondo, H. Yomo, S. Yamaguchi, P. Davis, R. Miura and S. Obana, Reliable wireless broadcast with random network coding for real-time applications, Proc. IEEE WCNC, 2009. doi: 10.1109/WCNC.2009.4917943.

[8]

S. Li and A. Ramamoorthy, Improved compression of network coding vectors using erasure decoding and list decoding, IEEE Commun. Letters, 14 (2010), 749-751. doi: 10.1109/LCOMM.2010.08.092453.

[9]

L. Li, R. Ramjee, M. Buddhikot and S. Miller, Network coding-based broadcast in mobile ad hoc networks, Proc. IEEE INFOCOM 2007, (2007), 1739-1747. doi: 10.1109/INFCOM.2007.203.

[10]

S. Y. Li, R. W. Yeung and N. Cai, Linear network coding, IEEE Trans. Inf. Theory, 29 (2003), 371-381. doi: 10.1109/TIT.2002.807285.

[11]

T. Matsuda, T. Noguchi and T. Takine, Survey of network coding and its applications, IEICE Trans. Commun., E94-B (2011), 698-717. doi: 10.1587/transcom.E94.B.698.

[12]

T. Matsuda, T. Noguchi and T. Takine, Broadcasting with randomized network coding in dense wireless ad hoc networks, IEICE Trans. Commun., E91-B (2008), 3216-3225. doi: 10.1093/ietcom/e91-b.10.3216.

[13]

S. Y. Ni, Y. C. Tseng, Y. S. Chen and J. P Sheu, The broadcast storm problem in a mobile ad hoc network, Proc. ACM Mobicom 99, (1999), 151-162. doi: 10.1023/A:1013763825347.

[14]

D. Nguyen, T. Tran, T. Nguyen and B. Bose, Wireless broadcast using network coding, IEEE Trans. Veh. Technol., 58 (2009), 914-925. doi: 10.1109/TVT.2008.927729.

[15]

W. Peng and X. C. Lu, On the reduction of broadcast redundancy in mobile ad hoc networks, Proc. ACM Mobihoc 2000, (2000), 129-130.

[16]

M. Sheng, J. Li and Y. Shi, Relative degree adaptive flooding broadcast algorithm for ad hoc networks, IEEE Trans. Broadcast., 51 (2005), 216-222. doi: 10.1109/TBC.2005.847624.

[17]

A. S. Tanenbaum, "Computer Networks,'' 4th edition, Prentice Hall, Upper Saddle River, NJ, 2002.

[18]

, Wireless LAN medium access control (MAC) and physical layer (PHY) specifications,, IEEE Std. 802.11, (1999). 

[19]

N. Wisitpongphan, O. K. Tonguz, J.S. Parikh, P. Mudalige, F. Bai and V. Sadekar, Broadcast storm mitigation techniques in vehicular ad hoc networks, IEEE Wireless Communications, 14 (2007), 84-94. doi: 10.1109/MWC.2007.4407231.

[1]

Ghislain Fourier, Gabriele Nebe. Degenerate flag varieties in network coding. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021027

[2]

Birol Yüceoǧlu, ş. ilker Birbil, özgür Gürbüz. Dispersion with connectivity in wireless mesh networks. Journal of Industrial and Management Optimization, 2018, 14 (2) : 759-784. doi: 10.3934/jimo.2017074

[3]

Hayato Ushijima-Mwesigwa, MD Zadid Khan, Mashrur A. Chowdhury, Ilya Safro. Optimal Placement of wireless charging lanes in road networks. Journal of Industrial and Management Optimization, 2021, 17 (3) : 1315-1341. doi: 10.3934/jimo.2020023

[4]

Hong Il Cho, Gang Uk Hwang. Optimal design and analysis of a two-hop relay network under Rayleigh fading for packet delay minimization. Journal of Industrial and Management Optimization, 2011, 7 (3) : 607-622. doi: 10.3934/jimo.2011.7.607

[5]

Stefan Martignoli, Ruedi Stoop. Phase-locking and Arnold coding in prototypical network topologies. Discrete and Continuous Dynamical Systems - B, 2008, 9 (1) : 145-162. doi: 10.3934/dcdsb.2008.9.145

[6]

Giuseppe Bianchi, Lorenzo Bracciale, Keren Censor-Hillel, Andrea Lincoln, Muriel Médard. The one-out-of-k retrieval problem and linear network coding. Advances in Mathematics of Communications, 2016, 10 (1) : 95-112. doi: 10.3934/amc.2016.10.95

[7]

Sebastià Galmés. Markovian characterization of node lifetime in a time-driven wireless sensor network. Numerical Algebra, Control and Optimization, 2011, 1 (4) : 763-780. doi: 10.3934/naco.2011.1.763

[8]

Li Gang. An optimization detection algorithm for complex intrusion interference signal in mobile wireless network. Discrete and Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1371-1384. doi: 10.3934/dcdss.2019094

[9]

Aiwan Fan, Qiming Wang, Joyati Debnath. A high precision data encryption algorithm in wireless network mobile communication. Discrete and Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1327-1340. doi: 10.3934/dcdss.2019091

[10]

Sangkyu Baek, Bong Dae Choi. Performance analysis of power save mode in IEEE 802.11 infrastructure wireless local area network. Journal of Industrial and Management Optimization, 2009, 5 (3) : 481-492. doi: 10.3934/jimo.2009.5.481

[11]

Hong Il Cho, Myungwoo Lee, Ganguk Hwang. A cross-layer relay selection scheme of a wireless network with multiple relays under Rayleigh fading. Journal of Industrial and Management Optimization, 2014, 10 (1) : 1-19. doi: 10.3934/jimo.2014.10.1

[12]

Yang Chen, Xiaoguang Xu, Yong Wang. Wireless sensor network energy efficient coverage method based on intelligent optimization algorithm. Discrete and Continuous Dynamical Systems - S, 2019, 12 (4&5) : 887-900. doi: 10.3934/dcdss.2019059

[13]

Tomoya Tainaka, Hiroyuki Masuyama, Shoji Kasahara, Yutaka Takahashi. A Markovian approach to per-flow throughput unfairness in IEEE 802.11 multihop wireless networks. Journal of Industrial and Management Optimization, 2009, 5 (3) : 493-510. doi: 10.3934/jimo.2009.5.493

[14]

Jin Soo Park, Kyung Jae Kim, Yun Han Bae, Bong Dae Choi. Admission control by dynamic bandwidth reservation using road layout and bidirectional navigator in wireless multimedia networks. Numerical Algebra, Control and Optimization, 2011, 1 (4) : 627-638. doi: 10.3934/naco.2011.1.627

[15]

Henk van Tilborg, Josef Pieprzyk, Ron Steinfeld, Huaxiong Wang. New constructions of anonymous membership broadcasting schemes. Advances in Mathematics of Communications, 2007, 1 (1) : 29-44. doi: 10.3934/amc.2007.1.29

[16]

Xianmin Geng, Shengli Zhou, Jiashan Tang, Cong Yang. A sufficient condition for classified networks to possess complex network features. Networks and Heterogeneous Media, 2012, 7 (1) : 59-69. doi: 10.3934/nhm.2012.7.59

[17]

Jacek Banasiak, Adam Błoch. Telegraph systems on networks and port-Hamiltonians. Ⅱ. Network realizability. Networks and Heterogeneous Media, 2022, 17 (1) : 73-99. doi: 10.3934/nhm.2021024

[18]

Massimiliano Caramia, Giovanni Storchi. Evaluating the effects of parking price and location in multi-modal transportation networks. Networks and Heterogeneous Media, 2006, 1 (3) : 441-465. doi: 10.3934/nhm.2006.1.441

[19]

Martin Gugat, Alexander Keimer, Günter Leugering, Zhiqiang Wang. Analysis of a system of nonlocal conservation laws for multi-commodity flow on networks. Networks and Heterogeneous Media, 2015, 10 (4) : 749-785. doi: 10.3934/nhm.2015.10.749

[20]

Andrea Picco, Lamberto Rondoni. Boltzmann maps for networks of chemical reactions and the multi-stability problem. Networks and Heterogeneous Media, 2009, 4 (3) : 501-526. doi: 10.3934/nhm.2009.4.501

 Impact Factor: 

Metrics

  • PDF downloads (65)
  • HTML views (0)
  • Cited by (1)

[Back to Top]