ALGORITHM FOR WIRELESS SENSOR NETWORKS

(Received: 2016-01-18, Revised: 2016-04-01 , Accepted: 2016-04-17)

Authors Maha I. Raheem,

Keywords #Wireless Sensor Networks #Distributed Computing #Distributed Processing #Gossip Algorithms #Routing.

Abstract A novel gossip algorithm for distributed averaging with fast convergence and reduced cost of communication over wireless sensor networks (WSNs) is proposed in this paper. This algorithm is proved to improve the behaviour of the standard gossip algorithm (SGA), triplewise gossip algorithms (TGAs) and the geographic gossip algorithm (GGA) by exploiting the geographic information of the network. An analysis of convergence time and cost of communication of the proposed algorithm is performed and a comparison with other existing methods is provided.

References

[1] F. Benezit, Distributed Average Consensus for Wireless Sensor Networks, Ph.D. dissertation, vol. 4509, 13 November 2009.

[2] M. I. Raheem and N. A. S. Alwan, "Performance Evaluation of Different Gossip Algorithms for Distributed QR Factorization in Wireless Sensor Networks," Emirates Journal for Engineering Research, vol. 20 , no. 1, pp. 93-100, 2015.

[3] O. Sluciak, H. Strakova, M. Rupp and W. N. Gansterer, "Distributed Gram-Schmidt Orthogonalization Based on Dynamic Consensus," In: IEEE 2012 Conference Record of the Forty Sixth Asilomar Conference on Signals, Systems and Computers (ASILOMAR), pp. 1207- 1211, 4-7 Nov. 2012.

[4] N. A. S. Alwan and A. S. Mahmood, "Distributed Gradient Descent Localization in Wireless Sensor Networks," Arabian Journal for Science and Engineering, vol. 40, no. 3, pp 893-899, March 2015.

[5] A. G. Dimakis, S. Kar, J. M. F. Moura, M.G. Rabbat and A. Scaglione, "Gossip Algorithms for Distributed Signal Processing," Proceedings of the IEEE, vol. 98, no. 11, pp. 1847-1864, 2010.

[6] S. Boyd, A. Ghosh, B. Prabhakar and D. Shah, "Gossip Algorithms: Design, Analysis and Applications," Proceedings IEEE 24th Annual Joint Conference of the IEEE Computer and Communications Societies, vol. 3, pp. 1653–1664, 13-17 March 2005.

[7] S. Boyd, A. Ghosh, B. Prabhakar and D. Shah, "Randomized Gossip Algorithms," IEEE Transactions on Information Theory, vol. 52, no. 6, pp. 2508–2530, June 2006.

[8] A .G. Dimakis, A. D. Sarwate and M. J. Wainwright, "Geographic Gossip: Efficient Averaging for Sensor Networks," Proceedings of the 5th International Conference on Information Processing in Sensor Networks, pp. 69-76, 19-21 April 2006.

[9] F. Benezit, P. Denantes, A. G. Dimakes, P. Thiran and M. Vetterli, "Reaching Consensus about Gossip: Convergence Time and Costs," Information Theory and Applications, NCCR-MICS, 2009.

[10] B. Yang, W. Wu and G. Zhu, "Distributed Averaging in Wireless Sensor Networks with Triplewise Gossip Algorithms," In: IEEE 2013 TENCON - Spring Conference, pp. 178-182, 17- 19 April 2013.

[11] D. Bertsekas, M. Athans and J. Tsitsiklis, "Distribution Asynchronous Deterministic and Stochastic Gradient Optimization Algorithm," IEEE Transactions on Automatic Control, vol. AC-31, no. 9, Sept. 1986.

[12] F. Benezit, A. G. Dimakis, P. Thiran and M. Vetterli, "Order–Optimal Consensus Through Randomized Path Averaging," IEEE Transactions on Information Theory, vol. 56, no. 10, pp. 5150-5167, October 2010.

[13] P. Denantes, F. Benezit, P. Thiran and M. Vetterli, "Which Distributed Averaging Algorithm Should I Choose For My Sensor Network?," In: The 27th Conference on Computer Communications, IEEE INFOCOM 2008, 13-18 April 2008.

[14] F. Benezit, V. Blondel, P. Thiran, J. Tsitsiklis and M. Vetterli, "Weight Gossip: Distributed Averaging Using Non-Doubly Stochastic Matrices," In: 2010 IEEE International Symposium on Information Theory, pp. 1753-11757, 13-18 June 2010.

[15] C. Ming, A. S. Daniel and M. Y. Edmund, "Accelerate Gossip Algorithms for Distributed Computation," 44th Annual Allerton Conference, Allerton House, UIUC, USA, pp. 952-959, 27- 29 September 2006.

[16] T. C. Aysal, M. E. Yildiz, A. D. Sarwate and A. Scaglione, "Broadcast Gossip Algorithm for Consensus," IEEE Transaction on Signal Processing, vol. 57, no. 7, pp. 2748-2761, July 2009.