Power efficient computation and communication primitives in wireless sensor networks

Wireless sensor networks (WSNs) are emerging as a new distributed computing paradigm for a variety of applications including collaborative signal and information processing. Realizing distributed as well as in-network WSN applications that do not depend on gathering all the sensed data at one sink node is essential to the successful deployment of WSNs in different scenarios. Towards this end, power efficient implementations of different communication and computing primitives are desired. In this dissertation we develop energy efficient algorithms for different computations and associated communication primitives arising in collaborative signal processing applications in WSNs. For communication primitives, we investigate cross layer designs aimed at capitalizing on energy reduction, delay reduction, and throughput improvement opportunities that may arise from the cooperation between routing and MAC layers. For realizing efficient computations, we investigate the use of memory and work-efficient design techniques that also minimize power usage.;Cooperation between routing and MAC layers can reduce energy and delay cost of the communication primitives. One particular area open for improvement that can benefit from this cooperation is the utilization of wireless medium during the sleep period of duty cycle MAC protocols. We present different methods that utilize the unused sleep time such that nodes set up multi hop flows for transferring multiple packets during their active period; next, the packets are transmitted in sleep period. In addition, we explore cross-layer optimization method that is specific to data gathering communication primitives. MAC protocols for data collection primitives can be designed to allow communication between two neighboring nodes that need to communicate with each other, rather than any two neighbors. We develop the design of multiple trees based data collection schemes.;No matter how efficient a communication primitive is, if at the application layer data scheduling is not designed according to sensor network costs, power efficiency cannot be attained; furthermore, improvements at communication layers cannot be reaped to the fullest extent. Towards this end, we develop energy efficient algorithm for different single processing tasks and investigate development of efficient implementations of several numerical algorithms including 1D- Fast Fourier Transform and matrix multiplication over WSNs.