Asynchronous multiple source network coding for wireless broadcasting

Keisuke  Minami; Takahiro Matsuda; Tetsuya Takine; Taku Noguchi

doi:10.3934/naco.2011.1.577

Article Contents

2011, Volume 1, Issue 4: 577-592. Doi: 10.3934/naco.2011.1.577

This issue Previous Article Optimal visiting order of isolated clusters in DTNs to minimize the total mean delivery delay of bundles Next Article Load distribution performance of super-node based peer-to-peer communication networks: A nonstationary Markov chain approach

Asynchronous multiple source network coding for wireless broadcasting

1.
Graduate School of Engineering, Osaka University, Suita, 5650871
2.
College of Information Science and Engineering, Ritsumeikan University, Kusatsu-Shi, 5258577

Received: April 30, 2011

Revised: July 31, 2011

Published: October 2011

Abstract Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Primary: 90B18; Secondary: 68M10.

Citation:

Related Papers

Cited by

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,'' 4^th 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.