Decentralized Utility-based Sensor Network Design

Wireless sensor networks consist of energy-constrained sensor nodes operating unattended in highly dynamic environments. In this paper, we advocate a systematic decentralized approach towards the design of such networks based on utility functions. A local utility function is defined for each sensor node in the network. While each sensor node “selfishly” optimizes its own utility, the network as a “whole” converges to a desired global objective. For the purpose of demonstrating our approach, we consider the following two separate case studies for data gathering in sensor networks: (a) construction of a load balanced tree and (b) construction of an energy balanced tree. Our work suggests a significant departure from the existing view of sensor networks as consisting of cooperative nodes, i.e. “selfish”sensor nodes is a useful paradigm for designing efficient distributed algorithms for these networks. Narayanan Sadagopan received the B.S. degree in computer science from the Regional Engineering College, Trichy, India, in 1998, and the M.S. degree in computer science from University of Southern California (USC), Los Angeles, in 2001. He is currently working toward the Ph.D. degree in the Computer Science Department, USC. His research is focused on theoretical aspects of wireless ad hoc and sensor networks. Mitali Singh received the BTech. degree in Computer Science and Engineering from the Indian Institute of Technology, New Delhi, India in 2000, and the M.S. degree in Computer Science from the University of Southern California, Los Angeles, USA. She is currently working towards the Ph.D. degree in Computer Science at the University of Southern California. Her research interests lie in the area of applied theory and networks. Presently, her work is focused on high level modeling and distributed algorithm design for wireless sensor systems. Bhaskar Krishnamachari received the B.E.E.E. degree from The Cooper Union for the Advancement of Science and Art, New York, in 1998, and the M.S.E.E. and Ph.D. degrees in electrical engineering from Cornell University, Ithaca, NY, in 1999 and 2002, respectively. He is now an Assistant Professor in the Department of Electrical Engineering, University of Southern California, Los Angeles, where he also holds a joint appointment in the Department of Computer Science. His current research is focused on the discovery of fundamental principles and the analysis and design of protocols for next-generation wireless sensor networks.