Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Given n sensors and m targets, a monitoring schedule is a partition of the sensor set such that each part of the partition can monitor all targets. Monitoring schedules are used to maximize the time all targets are monitored when there is no possibility of replacing the batteries of the sensors. Each part of the partition is used for one unit of time, and thus the goal is to maximize the number of parts in the partition.

We present distributed algorithms for Monitoring Schedule under the following assumptions: 1) identical sensors can each monitor all targets within a certain radius, 2) the n sensors are randomly distributed uniformly in a large square containing the targets, 3) the number of sensors is high enough given the area the square, and 4) the communication range is twice the sensing range (thus any two sensors which can monitor the same target can communicate in one hop). Our results hold with high probability. With the further assumptions that the sensors are capable (for example, by GPS) of knowing their exact geographic position, and targets fill out the square, our schedule has at least (1-ε) opt parts, where opt is the optimum solution. Without geographic position we show that a previously proposed distributed algorithm can be modified to achieve a constant approximation ratio. Our algorithms run in a polylogarithmic number of communication rounds, with the exact running time depending on assumptions on the information a sensor receives when packets collide.

REFERENCES

• 1: I. F. Akyildiz , W. Su , Y. Sankarasubramaniam , E. Cayirci, Wireless sensor networks: a survey, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.38 n.4, p.393-422, 15 March 2002 [doi>10.1016/S1389-1286(01)00302-4]
• 2: N. Alon and J.H. Spencer. The Probabilistic Method (second edition). Wiley Interscience, 2000.
• 3: C. Ambühl, T. Erlebach, M. Mihalak, and M. Nunkesser. Constant-factor approximation for minimum-weight (connected) dominating sets in unit disk graphs. In APPROX 2006, pages 3--14, 2006.
• 4: Stefano Basagni, Distributed Clustering for Ad Hoc Networks, Proceedings of the 1999 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '99), p.310, June 23-25, 1999
• 5: P. Berman, G. Calinescu, C. Shah, and A. Zelikovsky. Power efficient monitoring management in sensor networks. In Proc. IEEE Wireless Communications and Networking Conference, 2004.
• 6: D.C. Brinza, G. Calinescu, S. Tongngam, and A. Zelikovsky. Energy-efficient continuous and event-driven monitoring. In IEEE International Conference on Mobile Ad-hoc and Sensor Systems (MASS), pages 167--169, 2005.
• 7: Gruia Calinescu, A fast localized algorithm for scheduling sensors, Journal of Parallel and Distributed Computing, v.66 n.4, p.507-514, April 2006 [doi>10.1016/j.jpdc.2005.11.003]
• 8: Mihaela Cardei , Ding-Zhu Du, Improving wireless sensor network lifetime through power aware organization, Wireless Networks, v.11 n.3, p.333-340, May 2005 [doi>10.1007/s11276-005-6615-6]
• 9: M. Cardei, M.T. Thai, Y. Li, and W. Wu. Energy-efficient target coverage in wireless sensor networks. In Proc. of IEEE Infocom, 2005.
• 10: A. Cerpa and D. Estrin. Ascent: Adaptive self-configuring sensor networks topologies. In Proceedings of IEEE INFOCOM, June 2002.
• 11: Mainak Chatterjee , Sajal K. Das , Damla Turgut, WCA: A Weighted Clustering Algorithm for Mobile Ad Hoc Networks, Cluster Computing, v.5 n.2, p.193-204, April 2002 [doi>10.1023/A:1013941929408]
• 12: R.M. Corless, G.H. Gonnet, D.E.G. Hare, D.J. Jeffrey, and D.E. Knuth. On the Lambert W function. Adv. Comput. Math., 5:329--359, 1996.
• 13: Uriel Feige , Magnús M. Halldórsson , Guy Kortsarz , Aravind Srinivasan, Approximating the Domatic Number, SIAM Journal on Computing, v.32 n.1, p.172-195, 2003 [doi>10.1137/S0097539700380754]
• 14: Naveen Garg , Jochen Koenemann, Faster and Simpler Algorithms for Multicommodity Flow and other Fractional Packing Problems., Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.300, November 08-11, 1998
• 15: Robert Hahn , Herbert Reichl, Batteries and Power Supplies for Wearable and Ubiquitous Computing, Proceedings of the 3rd IEEE International Symposium on Wearable Computers, p.168, October 18-19, 1999
• 16: Tian He , Sudha Krishnamurthy , John A. Stankovic , Tarek Abdelzaher , Liqian Luo , Radu Stoleru , Ting Yan , Lin Gu , Jonathan Hui , Bruce Krogh, Energy-efficient surveillance system using wireless sensor networks, Proceedings of the 2nd international conference on Mobile systems, applications, and services, June 06-09, 2004, Boston, MA, USA [doi>10.1145/990064.990096]
• 17: 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
• 18: W. Heizelman, A. Chandrakasan, and H. Balakrishnan. An application-specific protocol architecture for wireless microsensor networks. IEEE Transactions on Wireless Communications, 1(4):660--670, 2002.
• 19: R. Kershner. The number of circles covering a set. American J. Mathematics, 61:665--671, 1939.
• 20: V.F. Kolchin, B.A. Sevastyanov, and V.P. Chistyakov. Random allocations. V.H. Winston & Sons, Washington, D.C., 1978. Translated from the Russian, translation edited by A.V. Balakrishnan, Scripta Series in Mathematics.
• 21: K. Krizman, T. Bieda, and T. Rappaport. Wireless position location: fundamentals, implementation strategies, and source of error. In Veh. Tech. Conf., pages 919--923, 1997.
• 22: Santosh Kumar , Ten H. Lai , József Balogh, On k-coverage in a mostly sleeping sensor network, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA [doi>10.1145/1023720.1023735]
• 23: T. Moscibroda and R. Wattenhofer. Maximizing the lifetime of dominating sets. In 5th International Workshop on Algorithms for Wireless, Mobile, Ad Hoc and Sensor Networks (WMAN), Denver, Colorado, USA, 2005.
• 24: Asis Nasipuri , Kai Li, A directionality based location discovery scheme for wireless sensor networks, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570754]
• 25: J. Pach, 2006. Personal Communication.
• 26: David Peleg, Distributed computing: a locality-sensitive approach, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2000
• 27: M. Perillo and W. Heinzelman. DAPR: A protocol for wireless sensor networks utilizing an application-based routing cost. In Proceedings of the IEEE Wireless Communications and Networking Conference, March 2004.
• 28: Di Tian , Nicolas D. Georganas, A coverage-preserving node scheduling scheme for large wireless sensor networks, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570744]
• 29: Sameer Tilak , Nael B. Abu-Ghazaleh , Wendi Heinzelman, A taxonomy of wireless micro-sensor network models, ACM SIGMOBILE Mobile Computing and Communications Review, v.6 n.2, p.28-36, April 2002 [doi>10.1145/565702.565708]
• 30: Ting Yan , Tian He , John A. Stankovic, Differentiated surveillance for sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958498]
• 31: Fan Ye , Gary Zhong , Songwu Lu , Lixia Zhang, PEAS: A Robust Energy Conserving Protocol for Long-lived Sensor Networks, Proceedings of the 10th IEEE International Conference on Network Protocols, p.200-201, November 12-15, 2002
• 32: Peng-Jun Wan , Chih-Wei Yi, Coverage by randomly deployed wireless sensor networks, IEEE/ACM Transactions on Networking (TON), v.14 n.SI, p.2658-2669, June 2006 [doi>10.1109/TIT.2005.862092]
• 33: O. Younis and S. Fahmy. Distributed clustering in ad-hoc sensor networks: a hybrid energy-efficient approach. In IEEE/INFOCOM, 2004.
• 34: Honghai Zhang , Jennifer C. Hou, On the upper bound of α-lifetime for large sensor networks, ACM Transactions on Sensor Networks (TOSN), v.1 n.2, p.272-300, November 2005 [doi>10.1145/1105688.1105693]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations
          Subjects: Network management

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.9 Robotics
          Subjects: Sensors

General Terms:
Algorithms, Performance, Theory

Keywords:
approximation algorithm, localized algorithm, monitoring schedule, sensor network