NBgossip: An Energy-Efficient Gossip Algorithm for Wireless Sensor Networks

Gossip-based algorithms for information dissemination have recentlyreceived significant attention for sensor and ad hoc networkapplications because of their simplicity and robustness. However, a commondrawback of many gossip-based protocols is the waste of energy inpassing redundant information over the network. Thus gossip algorithmsneed to be re-engineered in order to become applicable to energyconstrained networks. In this paper, we consider a scenario where eachnode in the network holds a piece of information (message) at thebeginning, and the objective is to simultaneously disseminate allinformation (messages) among all nodes quickly and cheaply. To provide apractical solution to this problem for ad hoc and sensor networks,NBgossip algorithm is proposed, which is based on network coding andneighborhood gossip. In NBgossip, nodes do not simply forward messagesthey receive, instead, the linear combinations of the messages are sentout. In addition, every node exchanges messages with its neighboringnodes only. Mathematical proof and simulation studies show that theproposed NBgossip terminates in the optimal O(n)-order rounds andoutperforms the existing gossip-based approaches in terms of energyconsumption incurred in spreading all the information.