Loss inference in wireless sensor networks based on data aggregation

ABSTRACT

In this paper, we consider the problem of inferring per node loss rates from passive end-to-end measurements in wireless sensor networks. Specifically, we consider the case of inferring loss rates during the aggregation of data from a collection of sensor nodes to a sink node. Previous work has studied the general problem of network inference, which considers the cases of inferring link-based metrics in wireline networks. We show how to adapt previous work on network inference so that loss rates in wireless sensor networks may be inferred as well. This includes (1) considering the per-node, instead of per-link, loss rates; and (2) taking into account the unique characteristics of wireless sensor networks. We formulate the problem as a Maximum-Likelihood Estimation (MLE) problem and show how it can be efficiently solved using the Expectation-Maximization (EM) algorithm. The results of the inference procedure may then be utilized in various ways to effectively streamline the data collection process. Finally, we validate our analysis through simulations.

REFERENCES

• 1: I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci. A Survey On Sensor Networks. IEEE Communications Magazine, 40(8):102--114, August 2002.
• 2: Tian Bu , Nick Duffield , Francesco Lo Presti , Don Towsley, Network tomography on general topologies, Proceedings of the 2002 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 15-19, 2002, Marina Del Rey, California
• 3: R. Caceres, N. Duffield, J. Horowitz, and D. Towsley. Multicast Based Inference of Network Internal Loss Characteristics. IEEE Trans. on Information Theory, 45:2462--2480, 1999.
• 4: M. Coates, A. H. III, R. Nowak, and B. Yu. Internet Tomography. IEEE Signal Processing Magazine, 19(3):47--65, May 2002.
• 5: M. Coates and R. Nowak. Network Loss Inference Using Unicast End-to-End Measurement. In ITC Seminar on IP Traffic, Measurement and Modelling, September 2000.
• 6: M. Coates and R. Nowak. Network Delay Distribution Inference from End-to-end Unicast Measurement. In Proceedings 2001 IEEE Int. Conf. Acoust., Speech, and Signal Processing, May 2001.
• 7: N. Duffield, J. Horowitz, F. L. Presti,and D. Towsley. Multicast Topology Inference From Measured End-to-End Measurements. In ITC Seminar on IP Traffic, Measurement and Modelling, September 2000.
• 8: Nick G. Duffield , Joseph Horowitz , Francesco Lo Presti , Donald F. Towsley, Network Delay Tomography from End-to-End Unicast Measurements, Proceedings of the Thyrrhenian International Workshop on Digital Communications: Evolutionary Trends of the Internet, p.576-595, September 17-20, 2001
• 9: N. Duffield, J. Horowitz, F. L. Presti,and D. Towsley. Multicast Topology Inference From Measured End-to-End Loss. IEEE Trans. on Information Theory, 48:26--45, 2002.
• 10: N. Duffield, F. L. Presti, V. Paxson, and D. Towsley. Inferring Link Loss Using Striped Unicast Probes. In Proceedings of IEEE INFOCOM 2001.
• 11: Wendi Rabiner Heinzelman , Anantha Chandrakasan , Hari Balakrishnan, Energy-Efficient Communication Protocol for Wireless Microsensor Networks, Proceedings of the 33rd Hawaii International Conference on System Sciences-Volume 8, p.8020, January 04-07, 2000
• 12: Wendi Rabiner Heinzelman , Joanna Kulik , Hari Balakrishnan, Adaptive protocols for information dissemination in wireless sensor networks, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.174-185, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313529]
• 13: Chalermek Intanagonwiwat , Ramesh Govindan , Deborah Estrin , John Heidemann , Fabio Silva, Directed diffusion for wireless sensor networking, IEEE/ACM Transactions on Networking (TON), v.11 n.1, p.2-16, February 2003 [doi>10.1109/TNET.2002.808417]
• 14: G. J. McLachlan and T. Krishnan. The EM Algorithm and Extensions. John Wiley and Sons, Inc., New York, 1997.
• 15: S. Ratnasamy and S. McCanne. Inference of Multicast Routing Trees and Bottleneck Bandwidths using End-to-End Measurements. In Proceedings IEEE INFOCOM 1999.
• 16: Y. Tsang, M. Coates, and R. Nowak. Passive Network Tomography Using EM Algorithms. In Proceedings 2001 IEEE Int. Conf. Acoust., Speech, and Signal Processing, volume 3, pages 1469--1472, May 2001.
• 17: Fan Ye , Haiyun Luo , Jerry Cheng , Songwu Lu , Lixia Zhang, A two-tier data dissemination model for large-scale wireless sensor networks, Proceedings of the 8th annual international conference on Mobile computing and networking, September 23-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570645.570664]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Fault tolerance

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS

General Terms:
Measurement, Performance, Reliability

Keywords:
data aggregation, sensor networks, tomography