In a distributed parameter estimation problem, during each sampling instant, a typical sensor node communicates its estimate either by the diffusion algorithm or by the incremental algorithm. Both these conventional distributed algorithms involve significant communication overheads and, consequently, defeat the basic purpose of wireless sensor networks. In the present paper, we therefore propose two new distributed algorithms, namely, block diffusion least mean square (BDLMS) and block incremental least mean square (BILMS) by extending the concept of block adaptive filtering techniques to the distributed adaptation scenario. The performance analysis of the proposed BDLMS and BILMS algorithms has been carried out and found to have similar performances to those offered by conventional diffusion LMS and incremental LMS algorithms, respectively. The convergence analyses of the proposed algorithms obtained from the simulation study are also found to be in agreement with the theoretical analysis. The remarkable and interesting aspect of the proposed block-based algorithms is that their communication overheads per node and latencies are less than those of the conventional algorithms by a factor as high as the block size used in the algorithms. 1. Introduction A wireless sensor network (WSN) consists of a group of sensors nodes which perform distributed sensing by coordinating themselves through wireless links. Since the nodes operate in a WSN function with limited battery power, it is important to design the networks with a minimum of communication among the nodes to estimate the required parameter vector [1, 2]. In the literature, a number of research papers have appeared which address the energy issues of sensor networks. According to the energy estimation scheme based on the 4th power loss model with Rayleigh fading [3], the transmission of 1？kb of data over a distance of 100？m, operating at 1？GHz using BPSK modulation with 1 0 ？ 6 ？bit-error rate, requires 3？J of energy. The same energy can be used for executing 300？M instructions in a 100？MIPS/watt general purpose processor. Therefore, it is of great importance to minimize the communication among nodes by maximizing local estimation in each sensor node. Each node in a WSN collects noisy observations related to certain desired parameters. In the centralized solution, every node in the network transmits its data to a central fusion center (FC) for processing. This approach has the disadvantage of being nonrobust to the failure of the FC and also needs a powerful central processor. Again the problem with
References
[1]
D. Estrin, L. Girod, G. Pottie, and M. Srivastava, “Instrumenting the world with wireless sensor networks,” in Proceedings of the IEEE Interntional Conference on Acoustics, Speech, and Signal Processing (ICASP'01), pp. 2033–2036, May 2001.
[2]
D. Estin, R. Govindan, J. Heidemann, and S. Kumar, “Next century chanlanges: scalable cordination in sensor network,” in Proceedings of the International Conference on Mobile Computing and Networks (MobiCOM '99), pp. 263–270, 1999.
[3]
G. J. Pottie and W. J. Kaiser, “Wireless integrated network sensors,” Communications of the ACM, vol. 43, no. 5, pp. 51–53, 2000.
[4]
M. G. Rabbat and R. D. Nowak, “Decentralized source localization and tracking [wireless sensor networks],” in Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing, (ICASSP'04), vol. 3, pp. III921–III924, 2004.
[5]
A. Nedi？ and D. P. Bertsekas, “Incremental subgradient methods for nondifferentiable optimization,” SIAM Journal on Optimization, vol. 12, no. 1, pp. 109–138, 2001.
[6]
F. S. Cattivelli and A. H. Sayed, “Diffusion LMS strategies for distributed estimation,” IEEE Transactions on Signal Processing, vol. 58, no. 3, pp. 1035–1048, 2010.
[7]
C. G. Lopes and A. H. Sayed, “Diffusion adaptive networks with changing topologies,” in Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing, (ICASSP'08), pp. 3285–3288, April 2008.
[8]
N. Takahashi, I. Yamada, and A. H. Sayed, “Diffusion adaptive networks with changing topologies,” in Proceedings of the International Conference on Acoustics, Speech and Signal Processing, (ICASSP '06), pp. 2845–2849, 2009.
[9]
F. S. Cattivelli and A. H. Sayed, “Distributed detection over adaptive networks using diffusion adaptation,” IEEE Transactions on Signal Processing, vol. 59, no. 5, pp. 1917–1932, 2011.
[10]
G. A. Clark, S. K. Mitra, and S. R. Parker, “Block implementation of adaptive digital filters,” IEEE Transactions on Signal Processing, vol. 29, no. 3, pp. 744–752, 1981.
[11]
F. S. Cattivelli and A. H. Sayed, “Analysis of spatial and incremental LMS processing for distributed estimation,” IEEE Transactions on Signal Processing, vol. 59, no. 4, pp. 1465–1480, 2011.
[12]
X. Liu, Q. Huang, and Y. Zhang, “Combs, needles, haystacks: balancing push and pull for discovery in large-scale sensor networks,” in Proceedings of the Second International Conference on Embedded Networked Sensor Systems, (SenSys'04), pp. 122–133, November 2004.
[13]
S. Madden, M. Franklin, J. Hellerstein, and W. Wong, “TAG: a tiny aggregation service for ad-hoc sensor network,” in Proceedings of the ACM Symposium on Operating System Design and Implementation (OSDI'02), 2002.
[14]
J. Ahn and B. Krishnamachari, “Modelling search cost in wireless sensor network,” Tech. Rep. CENG-2007-1, Computer Science Department, Unversity of southern California, 2007.
[15]
A. Jadbabaie, J. Lin, and A. S. Morse, “Coordination of groups of mobile autonomous agents using nearest neighbor rules,” IEEE Transactions on Automatic Control, vol. 48, no. 6, pp. 988–1001, 2003.
[16]
B. Widrow and S. D. Strearns, Adaptive Signal Processing, Prentice Hall, Englewood Cliffs, NJ, USA, 1985.
[17]
S. Haykin, Adaptive Filter Theory, Prentice Hall, Englewood Cliffs, NJ, USA, 2001.
[18]
A. H. Sayed, Fundamentals of Adaptive Filtering, John Wiley and Sons, 2003.
[19]
C. G. Lopes and A. H. Sayed, “Incremental adaptive strategies over distributed networks,” IEEE Transactions on Signal Processing, vol. 55, no. 8, pp. 4064–4077, 2007.
[20]
D. P. Bertsekas and J. N. Tsitsiklis, “Comments on "Coordination of groups of mobile autonomous agents using nearest neighbor rules",” IEEE Transactions on Automatic Control, vol. 52, no. 5, pp. 968–969, 2007.
[21]
C. G. Lopes and A. H. Sayed, “Diffusion least-mean squares over adaptive networks: formulation and performance analysis,” IEEE Transactions on Signal Processing, vol. 56, no. 7, pp. 3122–3136, 2008.
[22]
A. Geary and D. P. Bertsekas, “Incremental subgradient methods for nondifferentiable optimization,” in Proceedings of the 38th IEEE Conference on Decision and Control (CDC'99), pp. 907–912, December 1999.
[23]
D. P. Bertsekas, “A new class of incremental gradient methods for least squares problems,” SIAM Journal on Optimization, vol. 7, no. 4, pp. 913–926, 1997.
[24]
R. F. Woods, J. V. McCanny, and J. G. McWhirter, “From bit level systolic arrays to HDTV processor chips,” Journal of Signal Processing Systems, vol. 53, no. 1-2, pp. 35–49, 2008.
[25]
L.-K. Ting, R. Woods, and C. F. N. Cowan, “Virtex FPGA implementation of a pipelined adaptive LMS predictor for electronic support measures receivers,” IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 13, no. 1, pp. 86–95, 2005.
[26]
P. Fletcher and M. Dean, “Low complexity implementation of LMS algorithm,” Electronics Letters, vol. 38, no. 15, pp. 836–837, 2002.
