The impact of quasi-equally spaced sensor topologies on signal reconstruction

Abstract

A wireless sensor network with randomly deployed nodes can be used to provide an irregular sampling of a physical field of interest. We assume that a sink node collects the data gathered by the sensors and uses a linear filter for the reconstruction of a bandlimited scalar field defined over a d-dimensional domain. Sensors' locations are assumed to be known at the sink node, up to a certain position error. We then take the mean square error (MSE) of the reconstructed field as performance metric, and evaluate the effect of both uniform and quasi-equally spaced sensor layouts on the quality of the reconstructed field. We define a parameter that provides a measure of the regularity of the sensors deployment, and, through asymptotic analysis, we derive the MSE in the case of different sensor spatial distributions. For two of them, an approximate closed form expression is obtained. We validate our analysis through numerical results, and we show that an excellent match exists between analysis and simulation even for a small number of sensors.

References

1. Akyildiz, I. F., Su, W., Sankarasubramaniam, Y., and Cayirci, E. 2002. Wireless sensor networks: A survey. Comput. Netw. 38, 4, 393--422.
2. Cristescu, R. and Vetterli, M. 2005. On the optimal density for real-time data gathering of spatio-temporal processes in sensor networks. In Proceedings of the International Symposium on Information Processing in Sensor Networks (IPSN). ACM, New York, 159--164.
3. Daley, R. 1991. Atmospheric data analysis. Cambridge Atmospheric and Space Science Series.
4. de Bruijn, N. 1958. Asymptotic Methods in Analysis. North-Holland, Amsterdam, The Netherlands.
5. Dogandži'c, A. and Zhang, B. 2005. Parametric signal estimation using sensor networks in the presence of node localization errors. In Proceedings of the 39th Asilomar Conference on Signals, Systems and Computers. IEEE Signal Processing Society, Los Alamitos, CA.
6. Dong, M., Tong, L., and Sadler, B. 2006. Impact of data retrieval pattern on homogeneous signal field reconstruction in dense sensor networks. IEEE Trans. Signal Processing 54, 11 (Nov.), 4352--4364.
7. Early, D. and Long, D. 2001. Image reconstruction and enhanced resolution imaging from irregular samples. IEEE Trans. Geosc. Remote Sens. 39, 2 (Feb.), 291--302.
8. Feichtinger, H. and Gröchenig, K. 1993. Error analysis in regular and irregular sampling theory. Appl. Anal. 50, 167--189.
9. Feichtinger, H. G., Gröchenig, K., and Strohmer, T. 1995. Efficient numerical methods in non-uniform sampling theory. Numer. Math. 69, 423--440.
10. Ganesan, D., Ratnasamy, S., Wang, H., and Estrin, D. 2004. Coping with irregular spatio-temporal sampling in sensor networks. ACM SIGCOMM 34, 1 (Jan.), 125--130.
11. Kay, S. 1993. Fundamentals of statistical signal processing: Estimation theory. Prentice-Hall, Englewood Cliffs, NJ.
12. Kobayashi, M., Boutros, J., and Caire, G. 2001. Successive interference cancellation with siso decoding and em channel estimation. IEEE J. Select. Areas Commun. 19, 8 (Aug.).
13. Liu, B. and Stanley, T. 1965. Error bounds for jittered sampling. IEEE Trans. Autom. Contr. 10, 4, 449--454.
14. Liu, J., Zhang, Y., and Zhao, F. 2006. Robust distributed node localization with error management. In Proceedigs of the 7th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc'06). ACM, New York, 250--261.
15. Marvasti, F. 2001. Nonuniform Sampling: Theory and Practice. Kluwer Academic: Plenum.
16. Marziliano, P. and Vetterli, M. 2000. Reconstruction of irregularly sampled discrete-time bandlimited signals with unknown sampling locations. IEEE Trans. Signal Proc. 48, 12 (Dec.), 3462--3471.
17. Moore, D., Leonard, J., Rus, D., and Teller, S. 2004. Robust distributed network localization with noisy range measurements. In Proceedings of the 2nd ACM Conference on Embedded Networked Sensor Systems (SenSys). ACM, New York, 50--61.
18. Nordio, A., Chiasserini, C.-F., and Viterbo, E. 2006. Bandlimited field reconstruction for wireless sensor networks. arXiv:hep-th/0707.1954v1.
19. Nordio, A., Chiasserini, C.-F., and Viterbo, E. 2008. Performance of linear field reconstruction techniques with noise and uncertain sensor locations. IEEE Trans. Signal Proc. 56, 8 (Aug.), 3535--3547.
20. Rachlin, Y., Negi, R., and Khosla, P. 2005. Sensing capacity for discrete sensor network applications. In Proceedings of the International Symposium on Information Processing in Sensor Networks (IPSN). ACM, New York, 126--132.
21. Rauhut, H. 2007. Random sampling of sparse trigonometric polynomials. Appl. Computat. Harmon. Anal. 22, 1, 16--42.
22. Rauth, M. and Strohmer, T. 1997. A frequency domain approach to the recovery of geophysical potentials. In Proceedings of the 1997 Workshop on Sampling Theory and Applications (Samp TA 97). 109--114.
23. Smale, S., and Zhou, D.-X. 2004. Shannon sampling and function reconstruction from point values. Bull. Amer. Math. Soc. (N.S.) 41, 3, 279--305.
24. Stoica, P. and Moses, R. 2000. Introduction to Spectral Analysis. Prentice-Hall, Upper Saddle River, NJ.
25. Strohmer, T. 1993. Efficient methods for digital signal and image reconstruction from nonuniform samples. Ph.D. dissertation, University of Vienna, Vienna, Austria.
26. Strohmer, T., Binder, T., and Süssner, M. 1996. How to recover smooth object boundaries in noisy medical images. In Proceedings of the IEEE International Conference on Image Processing (ICIP 96). IEEE Computer Society Press, Los Alamitos, CA, 331--334.
27. Sung, Y., Tong, L., and Poor, H. 2005. Sensor activation and scheduling for field detection in large sensor arrays. In Proceedings of the International Symposium on Information Processing in Sensor Networks (IPSN). ACM, New York.
28. Taylor, C., Rahimi, A., and Bachrach, J. 2006. Simultaneous localization, calibration, and tracking in an ad hoc sensor network. In Proceedings of the International Symposium on Information Processing in Sensor Networks (IPSN). ACM, New York.
29. Tulino, A. and Verdú, S. 2004. Random matrix theory and wireless communications. Foundations and Trends in Communications and Information Theory. Now Publishers, Inc., Massachusetts.
30. Vuran, M., Akan, O., and Akyildiz, I. 2004. Spatio-temporal correlation: Theory and applications for wireless sensor networks. Comput. Netw. 45, 3 (June), 245--259.
31. Weisstein, E. 2008. Euler-mascheroni constant. from MathWorld -- A Wolfram Web Resource.
32. Zhao, P., Zhao, C., and Casazza, P. 2006. Perturbation of regular sampling in shift-invariant spaces for frames. IEEE Trans. Inf. Theory 52, 10 (Oct.), 4643--4648.

Index Terms

• General and reference

  • Cross-computing tools and techniques

    • Performance

• Mathematics of computing

  • Mathematical analysis

    • Functional analysis

      • Approximation

    • Numerical analysis

• Theory of computation

  • Design and analysis of algorithms

    • Approximation algorithms analysis