A greedy algorithm in WSNs for maximum network lifetime and communication reliability

A wireless sensor network (WSN) usually operates in an unreliable wireless environment with energy constraint. Many researchers are primarily interested in energy awareness and communication reliability of WSNs to maximize network lifetime. However, dealing with the conflicting problems of improving energy efficiency and fault-tolerance simultaneously is a challenging task. Most previous studies have shown that both problems can be approached by using either data link or network layer protocols. In this paper, we present a cross-layer protocol, which integrates a multipath routing protocol and a data interleaving technique based on Reed-Solomon code. We formulate the problem of selecting sensor transmission paths as a knapsack problem and solve it by a greedy algorithm. Our multipath routing protocol then enables each sensor to select multiple transmission paths using the proposed optimization algorithm. On the basis of multiple transmission paths, the technique of data interleaving is employed by using Reed-Solomon code to provide reliable data transmission. Simulation results demonstrate that our scheme outperforms the existing multipath routing protocols with respect to the network lifetime since it balances energy consumption and promotes communication reliability.