An Energy-Efficient Data Delivery Scheme Exploiting Network Coding and Maximum Node-Disjoint Paths in Wireless Sensor Networks
June-Ho Bang, Young-Jong Cho and Kyungran Kang
In this paper, we propose an energy efficient data delivery scheme for wireless sensor networks that exploits network coding and maximum node-disjoint paths. Since the sensing data concentrates to the sink, the nodes nearby the sink consumes much energy in forwarding the data. We call the area of the nodes two hops apart from the sink as bottleneck area. By selecting maximum node-disjoint paths (MDP) in the bottleneck area and combing packets with network coding, our proposed scheme reduces the number of transmission at the nodes close to the sink and, thus, extends the lifetime of the sensor network. The problem of maximum node-disjoint path selection with a specific length is known to be NP complete. We simplify the path-searching problem into a maximum bipartite matching problem, which can be solved with the well-known Hopcroft-Karp algorithm within polynomial time. The nodes that are three hops apart from the sink calculates the MDP and configures network coding parameters such as generation size and redundancy factor. Only the nodes on the MDP performs network coding and packet forwarding, thus, the packet transmission overhead of the bottleneck area is significantly reduced. We evaluate the proposed scheme by simulation and verify that the scheme requires less packet transmission overhead than flooding while supporting equivalent reliability.
Keywords: Wireless sensor networks, node-disjoint path, network coding, Bipartite graph matching, Hopcroft-Karp algorithm, energy efficiency, reliability