Mathematical techniques for optimizing data gathering in wireless sensor networks

Recent technological advances in miniaturization and chip design have led to the ubiquity of small, low cost devices capable of sensing, computation and wireless communication. This has resulted in the emergence of a novel networking paradigm where a network of several wireless sensors interacts with the physical world. This network senses interesting events and collects data about them, making it similar to a distributed database. Developing data gathering algorithms is hence one of the most widely studied topics in sensor network research. The limited energy of the sensor nodes, their autonomous mode of operation and highly dynamic environmental conditions makes the design of these mechanisms/algorithms extremely challenging. Several algorithms proposed for gathering data from a sensor network are mainly based on intuition or heuristic approaches. In this thesis we argue that the energy constraints of the sensor nodes engender the need for designing these algorithms in a principled manner using mathematical modeling and optimization techniques. We study complementary aspects of data gathering which include one-shot data gathering, en masse data gathering and continuous data gathering. While these studies are independent and involve the use of varied mathematical tools including first order models, linear program duality and game theory, they illustrate the advantage of using the analytical approach by outlining scenarios where traditional solutions to these data gathering problems are not optimal.