Power Efficient Algorithms for Computing Fast Fourier Transform over Wireless Sensor Networks

Abstract

Collaborative signal processing is one of the most promising applications that are currently being investigated for sensor networks. In this paper, we use FFT computation as a vehicle to highlight the issues involved in realizing distributed computations over sensor networks that have global and local communication and synchronization characteristics. We present a power efficient algorithm for computing 1-D Fast Fourier Transform (FFT) over single and multi-hop wireless sensor networks. The proposed algorithm reduces the number of transmissions, eliminates typical redundant computations in a distributed FFT algorithm and uniformly maps complex multiplications over all the sensors nodes by introducing an extra bit-complement permutation stage after first (log2N)/2 iterations. We show that the proposed algorithm improves energy consumption by 36 % on the average on multi-hop sensor networks. This saving in energy consumption significantly improves the battery life of the sensor nodes thereby increasing lifetime of the sensor network. 1.