Localized algorithms in wireless ad-hoc networks: location discovery and sensor exposure

ABSTRACT

The development of practical, localization algorithms is probably the most needed and most challenging task in wireless ad-hoc sensor networks (WASNs). Localized algorithms are a special type of distributed algorithms where only a subset of nodes in the WASN participate in sensing, communication, and computation. We have developed a generic localized algorithm for solving optimization problems in wireless ad-hoc networks that has five components: (i) data acquisition mechanism, (ii) optimization mechanism, (iii) search expansion rules, (iv) bounding conditions and (v) termination rules. the main idea is to request and process data only locally and only from nodes who are likely to contribute to rapid formation of the final solution. The approach enables two types of optimization: The first, guarantees the fraction of nodes that are contacted while optimizing for solution quality. The second, provides guarantees on solution qualities while minimizing the number of nodes that are contacted and/or amount of communication. The localized optimization approach is applied to two fundamental problems in sensor networks: location discovery and exposure-based coverage. We demonstrate its effective-ness on a number of examples

REFERENCES

• Abe00: Harold Abelson , Don Allen , Daniel Coore , Chris Hanson , George Homsy , Thomas F. Knight, Jr. , Radhika Nagpal , Erik Rauch , Gerald Jay Sussman , Ron Weiss, Amorphous computing, Communications of the ACM, v.43 n.5, p.74-82, May 2000 [doi>10.1145/332833.332842]
• Abi00: A.A. Abidi, G.J. Pottie, W.J. Kaiser, "Power-Conscious Design Of Wireless Circuits And Systems.' Proceedings of the IEEE, vol.88, (no.10), pp. 1528-45, Oct. 2000.
• Adj99: William Adjie-Winoto , Elliot Schwartz , Hari Balakrishnan , Jeremy Lilley, The design and implementation of an intentional naming system, ACM SIGOPS Operating Systems Review, v.33 n.5, p.186-201, Dec. 1999
• Bad93: B. R. Badrinath , Arup Acharya , Tomasz Imieliński, Impact of mobility on distributed computations, ACM SIGOPS Operating Systems Review, v.27 n.2, p.15-20, April 1993 [doi>10.1145/155848.155853]
• Aur91: Franz Aurenhammer, Voronoi diagrams—a survey of a fundamental geometric data structure, ACM Computing Surveys (CSUR), v.23 n.3, p.345-405, Sept. 1991 [doi>10.1145/116873.116880]
• Ben93: M. Bender et. al. "Unix For Nomads: Making Unix Support Mobile Computing." In Proceedings of the USENIX Symposium on Mobile & Location Independent Computing, August 1993.
• Beu99: J. Beutel, "Geolocation In A PicoRadio Environment." M.S. Thesis, ETH Z~rich, Electronics Lab, 1999.
• Bul00: N. Bulusu, J. Heidemann, D. Estrin, ""GPS-less Low Cost Outdoor Localization For Very Small Devices." IEEE Personal Communications, Special Issue on "Smart Spaces and Environments", Vol. 7, No. 5, pp. 28-34, October 2000.
• Cor90: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• Dow98: Troy Bryan Downing, Java RMI: Remote Method Invocation, IDG Books Worldwide, Inc., Foster City, CA, 1998
• Dur89: E. H. Durfee , V. R. Lesser , D. D. Corkill, Trends in Cooperative Distributed Problem Solving, IEEE Transactions on Knowledge and Data Engineering, v.1 n.1, p.63-83, March 1989 [doi>10.1109/69.43404]
• Est00: Deborah Estrin , Ramesh Govindan , John Heidemann, Embedding the Internet: introduction, Communications of the ACM, v.43 n.5, p.38-41, May 2000 [doi>10.1145/332833.332836]
• Has97: Z.J. Haas, "On The Relaying Capability Of The Reconfigurable Wireless Networks." IEEE 47th Vehicular Technology Conference, Vol.2, pp. 1148-52, May 1997.
• Int00: Chalermek Intanagonwiwat , Ramesh Govindan , Deborah Estrin, Directed diffusion: a scalable and robust communication paradigm for sensor networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.56-67, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345920]
• Gal83: R. G. Gallager , P. A. Humblet , P. M. Spira, A Distributed Algorithm for Minimum-Weight Spanning Trees, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.1, p.66-77, Jan. 1983 [doi>10.1145/357195.357200]
• Gir01: L. Girod, D. Estrin, "Robust Range Estimation Using Acoustic And Multimodal Sensing." IEEE/RSI Int. Conf. on Intelligent Robots and Systems (IROS 2001), Maui, Hawaii, October 2001 (To Appear).
• Hoa85: C. A. R. Hoare, Communicating sequential processes, Prentice-Hall, Inc., Upper Saddle River, NJ, 1985
• Kan00: C.W. Kang, M.W. Golay, "An Integrated Method For Comprehensive Sensor Network Developement In Complex Power Plant Systems." Reliability Engineering & System Safety, vol.67, pp. 17-27, Jan. 2000.
• Kis92: James J. Kistler , M. Satyanarayanan, Disconnected operation in the Coda File System, ACM Transactions on Computer Systems (TOCS), v.10 n.1, p.3-25, Feb. 1992 [doi>10.1145/146941.146942]
• Lam78: Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
• Lam90: Leslie Lamport , Nancy Lynch, Distributed computing: models and methods, Handbook of theoretical computer science (vol. B): formal models and semantics, MIT Press, Cambridge, MA, 1991
• Lie98: K. Lieska, E. Laitinen, J. Lahteenmaki, "Radio Coverage Optimization With Genetic Algorithms." IEEE Int. Symp. on Personal, Indoor and Mobile Radio Communications, pp. 318-22, Sept. 1998.
• Lyn96: Nancy A. Lynch, Distributed Algorithms, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• Meg01a: S. Meguerdichian, F. Koushanfar, M. Potkonjak, M. Srivastava, "Coverage Problems in Wireless Ad-Hoc Sensor Networks." IEEE Infocom 2001, Vol. 3, pp. 1380-1387, April 2001.
• Meg01b: 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]
• Mil89: R. Milner, Communication and concurrency, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
• MIT82: MIT Lincoln Laboratories. Workshop on Distributed Sensor Networks. 1982.
• Glo2: Glomosim 2.0. http://pcl.cs.ucla.edu/projects/glomosim/
• ORo92: J. O'Rourke, Computational geometry column 15. (Open problem from art gallery solved). Int. Journal of Computational Geometry & Applications, vol.2, pp.215-17, June 1992.
• Pot00: G. J. Pottie , W. J. Kaiser, Wireless integrated network sensors, Communications of the ACM, v.43 n.5, p.51-58, May 2000 [doi>10.1145/332833.332838]
• Ray88: Michel Raynal, Distributed algorithms and protocols, John Wiley & Sons, Inc., New York, NY, 1988
• Rum86: David E. Rumelhart , James L. McClelland , CORPORATE PDP Research Group, Parallel distributed processing: explorations in the microstructure of cognition, vol. 1: foundations, MIT Press, Cambridge, MA, 1986
• Sav01a: C. Savarese, J. Rabaey, J. Beutel, "Locationing in Distributed Ad-Hoc Wireless Sensor Networks." Proceedings of the ICASSP, May 2001.
• Sav01b: Andreas Savvides , Chih-Chieh Han , Mani B. Strivastava, Dynamic fine-grained localization in Ad-Hoc networks of sensors, Proceedings of the 7th annual international conference on Mobile computing and networking, p.166-179, July 2001, Rome, Italy [doi>10.1145/381677.381693]
• Tel94: Gerard Tel, Introduction to distributed algorithms, Cambridge University Press, New York, NY, 1994
• Ten00: David Tennenhouse, Proactive computing, Communications of the ACM, v.43 n.5, p.43-50, May 2000 [doi>10.1145/332833.332837]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Algorithms, Experimentation, Performance