On the Interdependence of Sensing and Estimation Complexity in Sensor Networks

Abstract

Computing the exact maximum likelihood or maximum a posteriori estimate of the environment is computationally expensive in many practical distributed sensing settings. We argue that this computational difficulty can be over- come by increasing the number of sensor measurements. Based on our work on the connection between error cor- recting codes and sensor networks, we propose a new algo- rithm which extends the idea of sequential decoding used to decode convolutional codes to estimation in a sensor net- work. In a simulated distributed sensing application, this algorithm provides accurate estimates at a modest compu- tational cost given a sufficient number of sensor measure- ments. Above a certain number of sensor measurements this algorithm exhibits a sharp transition in the number of steps it requires in order to converge, leading to the poten- tially counter-intuitive observation that the computational burden of estimation can be reduced by taking additional sensor measurements.