Numerical Algebra, Control and Optimization (NACO)

Asynchronous multiple source network coding for wireless broadcasting

Pages: 577 - 592, Volume 1, Issue 4, December 2011      doi:10.3934/naco.2011.1.577

       Abstract        References        Full Text (263.8K)       Related Articles

Keisuke Minami - Graduate School of Engineering, Osaka University, Suita, 5650871, Japan (email)
Takahiro Matsuda - Graduate School of Engineering, Osaka University, Suita, 5650871, Japan (email)
Tetsuya Takine - Graduate School of Engineering, Osaka University, Suita, 5650871, Japan (email)
Taku Noguchi - College of Information Science and Engineering, Ritsumeikan University, Kusatsu-Shi, 5258577, Japan (email)

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:  Network coding, broadcasting, multi-hop wireless networks.
Mathematics Subject Classification:  Primary: 90B18; Secondary: 68M10.

Received: May 2011;      Revised: August 2011;      Available Online: November 2011.