• Previous Article
    Optimal visiting order of isolated clusters in DTNs to minimize the total mean delivery delay of bundles
  • NACO Home
  • This Issue
  • Next Article
    Load distribution performance of super-node based peer-to-peer communication networks: A nonstationary Markov chain approach
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 & 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. doi: 10.1109/18.850663.

[2]

P. A. Chou, Y. Wu and K. Jain, Practical network coding,, Proc. 41st Allerton Conf. Commun., (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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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.

[16]

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

[17]

A. S. Tanenbaum, "Computer Networks,'', 4th edition, (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. 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. doi: 10.1109/18.850663.

[2]

P. A. Chou, Y. Wu and K. Jain, Practical network coding,, Proc. 41st Allerton Conf. Commun., (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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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.

[16]

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

[17]

A. S. Tanenbaum, "Computer Networks,'', 4th edition, (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. doi: 10.1109/MWC.2007.4407231.

[1]

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

[2]

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 & Management Optimization, 2011, 7 (3) : 607-622. doi: 10.3934/jimo.2011.7.607

[3]

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

[4]

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

[5]

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

[6]

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

[7]

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

[8]

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

[9]

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 & Management Optimization, 2014, 10 (1) : 1-19. doi: 10.3934/jimo.2014.10.1

[10]

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

[11]

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 & Management Optimization, 2009, 5 (3) : 493-510. doi: 10.3934/jimo.2009.5.493

[12]

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 & Optimization, 2011, 1 (4) : 627-638. doi: 10.3934/naco.2011.1.627

[13]

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

[14]

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

[15]

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

[16]

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

[17]

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

[18]

Zhuwei Qin, Fuxun Yu, Chenchen Liu, Xiang Chen. How convolutional neural networks see the world --- A survey of convolutional neural network visualization methods. Mathematical Foundations of Computing, 2018, 1 (2) : 149-180. doi: 10.3934/mfc.2018008

[19]

Yunan Wu, T. C. Edwin Cheng. Classical duality and existence results for a multi-criteria supply-demand network equilibrium model. Journal of Industrial & Management Optimization, 2009, 5 (3) : 615-628. doi: 10.3934/jimo.2009.5.615

[20]

T.C. Edwin Cheng, Yunan Wu. Henig efficiency of a multi-criterion supply-demand network equilibrium model. Journal of Industrial & Management Optimization, 2006, 2 (3) : 269-286. doi: 10.3934/jimo.2006.2.269

 Impact Factor: 

Metrics

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

[Back to Top]