Stochastic coverage in heterogeneous sensor networks

ABSTRACT

We study the problem of coverage in planar heterogeneous sensor networks. Coverage is a performance metric that quantifies how well a field of interest is monitored by the sensor deployment. To derive analytical expressions of coverage for heterogeneous sensor networks, we formulate the coverage problem as a set intersection problem, a problem studied in integral geometry. Compared to previous analytical results, our formulation allows us to consider a network model where sensors are deployed according to an arbitrary stochastic distribution; sensing areas of sensors need not follow the unit disk model but can have any arbitrary shape; sensors need not have an identical sensing capability. Furthermore, our formulation does not assume deployment of sensors over an infinite plane and, hence, our derivations do not suffer from the border effect problem arising in a bounded field of interest. We compare our theoretical results with the spatial Poisson approximation that is widely used in modeling coverage. By computing the Kullback-Leibler and total variation distance between the probability density functions derived via our theoretical results, the Poisson approximation, and the simulation, we show that our formulas provide a more accurate representation of the coverage in sensor networks. Finally, we provide examples of calculating network parameters such as the network size and sensing range in order to achieve a desired degree of coverage.

REFERENCES

• 1: Akyildiz, I., Su, W., Sankarasubramaniam, Y., and Cayirci, E. 2002. A survey on sensor networks. IEEE Commun. Mag. 40, 8, 102--114.
• 2: Bettstetter, C. and Krause, O. 2001. On border effects in modeling and simulation of wireless ad hoc networks. In Proceedings of the IEEE MWCN '01.
• 3: Bettstetter, C. and Zangl, J. 2002. How to achieve a connected ad hoc network with homogeneous range assignment: An analytical study with consideration of border effects. In Proceedings of the WCNC '02. 125--129.
• 4: Blaschke, W. 1955. Vorlesungen uber Integralgeometrie 9, 3rd Ed. Deutsch Verlag Wiss, Berlin, Germany.
• 5: Bonnesen, T. and Fenchel, W. 1934. Theorie de convexen korper. Ergeb. Math. Springer, Berlin, Germany, 18.
• 6: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 7: Filipescu, D. 1971. On some integral formulas relative to convex figures in the euclidean space e2. Stud. Cerc. Mat. 23, 693--709.
• 8: Flanders, H. 1963. Differential Forms with Applications to the Physical Sciences. Academic Press, New York, NY.
• 9: Flanders, H. 1967. Differential Forms. Prentice Hall, Englewood Cliffs, NJ.
• 10: Himanshu Gupta , Samir R. Das , Quinyi Gu, Connected sensor cover: self-organization of sensor networks for efficient query execution, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778438]
• 11: Kar, K. and Banerjee, S. 2003. Node placement for connected coverage in sensor networks. In Proceedings of WiOpt '03.
• 12: Koushanfar, F., Meguerdichian, S., Potkonjak, M., and Srivastava, M. 2001. Coverage problems in wireless ad-hoc sensor networks. In Proceedings of IEEE INFOCOM '01. 1380--1387.
• 13: Bhaskar Krishnamachari , Deborah Estrin , Stephen B. Wicker, The Impact of Data Aggregation in Wireless Sensor Networks, Proceedings of the 22nd International Conference on Distributed Computing Systems, p.575-578, July 02-05, 2002
• 14: Li, X., Wan, P., and Frieder, O. 2003. Coverage in wireless ad hoc sensor networks. IEEE Trans. Comput. 52, 6, 753--763.
• 15: Liu, B. and Towsley, D. 2004. A study of the coverage of large-scale sensor networks. In Proceedings of MASS '04.
• 16: Alan Mainwaring , David Culler , Joseph Polastre , Robert Szewczyk , John Anderson, Wireless sensor networks for habitat monitoring, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570751]
• 17: Seapahn Meguerdichian , Farinaz Koushanfar , Gang Qu , Miodrag Potkonjak, Exposure in wireless Ad-Hoc sensor networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.139-150, July 2001, Rome, Italy [doi>10.1145/381677.381691]
• 18: Miles, R. 1969. The assymptotic values of certain coverage probabilities. Biometrika 56, 661--680.
• 19: Miorandi, D. and Altman, E. 2005. Coverage and connectivity of ad hoc networks in presence of channel randomness. In Proceedings of IEEE INFOCOM '05. 491--502.
• 20: Poduri, S. and Sukhatme, G. S. 2004. Constrained coverage for mobile sensor networks. In Proceedings of the IEEE International Conference on Robotics and Automation '04. 165--172.
• 21: Santalo, L. 1936. Geometrica intregral 4: Sobre la medida cinematica en el plano. Abh. Math. Sem. Univ. Hamburg 11, 222--236.
• 22: Santalo, L. 1976. Integral Geometry and Geometric Probability. Addison-Wesley, Reading, MA.
• 23: Stoka, M. 1969. Alcune formule integrali concenernenti i corpsi convessi dello spazio euclideo e3. Rend. Sem. Mat. Torino 28, 95--108.
• 24: Robert Szewczyk , Eric Osterweil , Joseph Polastre , Michael Hamilton , Alan Mainwaring , Deborah Estrin, Habitat monitoring with sensor networks, Communications of the ACM, v.47 n.6, June 2004 [doi>10.1145/990680.990704]
• 25: Guoliang Xing , Xiaorui Wang , Yuanfang Zhang , Chenyang Lu , Robert Pless , Christopher Gill, Integrated coverage and connectivity configuration for energy conservation in sensor networks, ACM Transactions on Sensor Networks (TOSN), v.1 n.1, p.36-72, August 2005 [doi>10.1145/1077391.1077394]

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology; Distributed networks

General Terms:
Algorithms, Design, Performance

Keywords:
Stochastic, coverage, heterogeneous, sensor networks