A Multicast Algorithm for Wireless Sensor Networks Based on Network Coding

We propose a set of distributed algorithms for improving the multicast throughput in wireless sensor networks. To this end, network coding is applied when exploiting path diversity with two disjoint paths to each multicast group receiver. We depart from the traditional wisdom that the multicast topology from source to receivers needs to be a tree and propose a novel and distributed algorithm to construct a 2-redundant multicast graph (a directed acyclic graph) as the multicast topology, on which network coding is applied. We conduct both analytical and simulation-based studies to evaluate the effectiveness and performance of our algorithm. 1. Introduction Multicast mechanism is mainly used in sink nodes to send control messages to the sensor nodes in wireless sensor networks (WSNs), or in a sensor node to send data to multiple sink nodes. Multicast routing algorithm plays a vital role in WSN regarding the survival time and transmission efficiency of the WSNs. Ahlswede et al. proposed network coding [1–3] in 2000. This method is useful for greatly improving the network throughput and reliability. Literatures [4, 5] have proved that in each multicast diagram, corresponding linear coding can be found to achieve minimum cut-maximum flow. Zhu et al. [6] found that the network coding has good performance and advantage in multicast network, but the network topology has different effect on the throughput and bandwidth of multicast; redundant multicast figure presented better efficiency and performance than the traditional multicast tree. Jiang et al. [7] proposed a multicast tree algorithm through network coding, determined the relationship between cluster heads, and analyzed the algorithm performance using network calculus. Yuan et al. [8] analyzed the performance of network coding by the stochastic process. Li et al. [9] analyzed the end-to-end route delay performance based on the network coding using network calculus. According to the WSN characteristic, considering the geographic and energy-aware routing (GEAR) [10], we constructed -redundant multicast graph in the form of overlay network in this paper using the multicast algorithm based on network coding (MABNC). We improved the multicast performance by reducing the energy consumption. 2. Algorithm Description The proposed algorithm is for sensor networks. Based on the geographic routing algorithms, -redundant multicast graph was constructed. The network throughput and bandwidth utilization were improved, the effect of minimum cut to maximum flow was determined, and the network multicast routing