Distributed self-tuning of sensor networks

This work is motivated by the need for an ad hoc sensor network to autonomously optimise its performance for given task objectives and constraints. Arguing that communication is the main bottleneck for distributed computation in a sensor network we formulate two approaches for optimisation of computing rates. The first is a team problem for maximising the minimum communication throughput of sensors and the second is a game problem in which cost for each sensor is a measure of its communication time with its neighbours. We investigate adaptive algorithms using which sensors can tune to the optimal channel attempt rates in a distributed fashion. For the team problem, the adaptive scheme is a stochastic gradient algorithm derived from the augmented Lagrangian formulation of the optimisation problem. The game formulation not only leads to an explicit characterisation of the Nash equilibrium but also to a simple iterative scheme by which sensors can learn the equilibrium attempt probabilities using only the estimates of transmission and reception times from their local measurements. Our approach is promising and should be seen as a step towards developing optimally self-organising architectures for sensor networks. Aditya Karnik obtained his B.E. from the University of Pune, Pune, India, and M.E. and Ph.D. (2004) in electrical communication engg. from the Indian Institute of Science, Bangalore, India. He is currently a postdoctoral fellow at the University of Waterloo, Waterloo, Canada. He was a recipient of the IBM Research Fellowship. His research interests are in performance evaluation, optimisation and control of communication networks. Anurag Kumar obtained his B.Tech. degree from the Indian Institute of Technology at Kanpur, and the PhD degree from Cornell University, both in Electrical Engineering. He was then with Bell Laboratories, Holmdel, N.J., for over 6 years. Since 1988 he has been with the Indian Institute of Science (IISc), Bangalore, in the Dept. of Electrical Communication Engineering, where he is now a Professor, and is also the Chairman of the department. From 1988 to 2003 he was the Coordinator at IISc of the Education and Research Network Project (ERNET), India’s first wide-area packet switching network. His area of research is communication networking, specifically, modeling, analysis, control and optimisation problems arising in communication networks and distributed systems. Recently his research has focused primarily on wireless networking. He has been elected Fellow of the IEEE, and the Indian National Science Academy (INSA), both from 2006, and has been a Fellow of the Indian National Academy of Engineering (INAE) since 1998. He is an associate editor of IEEE Transactions on Networking, and of IEEE Communications Surveys and Tutorials. He is a coauthor of the advanced text-book “Communication Networking: An Analytical Approach,” by Kumar, Majunath and Kuri, published by Morgan-Kaufman/Elsevier. Vivek Borkar got his B. Tech. (Elec. Engg.) from Indian Institute of Technology, Mumbai, in 1976, M. S. (Systems and Control) from Case Western Reserve Uni. in 1977, and Ph.D. (Elec. Engg. and Computer Sci.) from the Uni. of California, Berkeley, in 1980. He was with TIFR Centre, Bangalore (1982–1989) and Indian Institute of Science (1989–1999) before taking up his present position at the School of Technology and Computer Science, Tata Inst. of Fundamental Research, Mumbai. He is a Fellow of the Indian Academy of Sciences, Indian National Science Academy, Indian National Academy of Engineers and the IEEE. His research interests are stochastic control, stochastic algorithms and applications. He is on the editorial boards of Sadhana, Systems and Control Letters, SIAM J. Control and Optim., and Applicationes Mathematicae. He is the author of ‘Optimal Control of Diffusion Processes’ (Longman, 1989), ‘Topics in Controlled Markov Chains’ (Longman, 1991), ‘Probability Theory: An Advanced Course’ (Springer, 1995).