Gossip Algorithms for Average Energy Estimation in Wireless Sensor Networks

Abstract:

Gossip algorithms which belong to a kind of distributed algorithms can be used to compute the (possibly weighted) average of the initial measurements of the nodes at every node in the network. This paper proposes an improved broadcast gossip algorithm to estimate average energy with better accuracy. In this proposed algorithm, we use some companion variables to save the sum, and convergence error is decreasing with the number of companion variables increasing. Convergence of the proposed algorithm is studied theoretically and verified by simulations. Although the estimated value is random, we show that the novel algorithm can converge closer to average than broadcast gossip algorithm in probability.

• Periodical: Applied Mechanics and Materials (Volume 577)
• Pages: 908-912
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.577.908
• Online since: July 2014
• Authors: Yu Ze Wang*, Shao Chuan Wu, Wen Cui
• Keywords: Broadcast, Distributed Averaging, Gossip Algorithm, Sensor Network

References

[1] D. Kempe, A. Dobra, and J. Gehrke. Gossip-based computation of aggregate information. In Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on, pages 482–491, (2003).

DOI: 10.1109/sfcs.2003.1238221

[2] D. S. Scherber and H. C. Papadopoulos. Distributed computation of averages over ad hoc networks. Selected Areas in Communications, IEEE Journal on, 23(4): 776–787, (2005).

DOI: 10.1109/jsac.2005.843553

[3] Hajnal A, Milner E C, Szemeredi E. A cure for the telephone disease[J]. Canad. Math Bull, 1972(15): 447-450.

DOI: 10.4153/cmb-1972-081-0

[4] J. Tsitsiklis, Problems in Decentralized Decision Making and Computation, Ph.D. dissertation, Dept. Elec. Eng. Comput. Sci., Massachusetts Inst. Technol. (M.I.T. ), Boston, MA, (1984).

[5] Y. Hatano and M. Mesbahi, Agreement over random networks, IEEE Trans. on Autom. Control, vol. 50, no. 11, pp.1867-1872, (2005).

DOI: 10.1109/tac.2005.858670

[6] F. Fagnani and S. Zampieri, Average consensus with packet drop communication, SIAM J. Control Optim., vol. 48, no. 1, pp.102-133, (2009).

DOI: 10.1137/060676866

[7] S. Patterson, B. Bamieh and A. El Abbadi, Convergence rates of distributed average consensus with stochastic link failures, IEEE Trans. Autom. Control, vol. 55, no. 4, pp.880-892, (2010).

DOI: 10.1109/tac.2010.2041998

[8] S. Boyd, A. Ghosh, B. Prabhakar, and D. Shah, Randomized gossip algorithms, IEEE Trans. Inf. Theory, vol. 52, p.2508–2530, Jun. (2006).

DOI: 10.1109/tit.2006.874516

[9] T. Aysal, M. Yildiz, and A. Scaglione, Broadcast gossip algorithms, IEEE Trans. Signal Process. , vol. 57, no. 7, p.2748–2761, Jul. (2009).

DOI: 10.1109/tsp.2009.2016247

[10] Franceschelli M, Giua A, Seatzu C. Distributed averaging in sensor networks based on broadcast gossip algorithms[J]. Sensors Journal, IEEE, 2011, 11(3): 808-817.

DOI: 10.1109/jsen.2010.2064295