Localized distance-sensitive service discovery in wireless sensor networks

ABSTRACT

In this paper, we identify a new problem in wireless sensor networks, distance sensitive service discovery, where nearby or closest service selection guarantee is expected. We propose a lightweight solution algorithm, iMesh, which uses no global computation and generates constant per node storage load. In iMesh, service providers construct a localized planar structure, information mesh, using the existing blocking rule enhanced with a newly proposed expansion rule. The information mesh possesses good proximity property and serves as service directory. Service consumers conduct a lookup process restricted within their home mesh cells to discover nearby services. We first analytically study its properties over a grid network model. Then we evaluate its performance in randomized network scenarios by extensive simulation. Simulation results indicate that iMesh guarantees nearby (closest) service selection with very high probability >99% (resp., >97%) at considerably low message cost.

REFERENCES

• 1: I. F. Akyildiz and I. H. Kasimoglu. "Wireless sensor and actor networks: research challenges". Ad Hoc Networks, 2(4):351--367, 2004.
• 2: Prosenjit Bose , Pat Morin , Ivan Stojmenović , Jorge Urrutia, Routing with guaranteed delivery in ad hoc wireless networks, Proceedings of the 3rd international workshop on Discrete algorithms and methods for mobile computing and communications, p.48-55, August 20-20, 1999, Seattle, Washington, United States [doi>10.1145/313239.313282]
• 3: Z. Gao, Y. Yang, J. Zhao, J. Cui, and X. Li. "Service Discovery Protocols for MANETs: A Survey". In Proc. of MSN (LNCS 4325), pages 232--243, 2006.
• 4: Jinyang Li , John Jannotti , Douglas S. J. De Couto , David R. Karger , Robert Morris, A scalable location service for geographic ad hoc routing, Proceedings of the 6th annual international conference on Mobile computing and networking, p.120-130, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345931]
• 5: X. Li, N. Santoro, and I. Stojmenovic. "Mesh-based Sensor Relocation for Coverage Maintenance in Mobile Sensor Networks". In Proc. of UIC (LNCS 4611), pages 696--708, 2007.
• 6: A. N. Mian, R. Beraldi, and R. Baldoni. "Survey of Service Discovery Protocols in Mobile Ad Hoc Networks". Technical Report 4/06, Universit degli Studi di Roma La Sapienza, Rome, Italy, 2006.
• 7: Sylvia Ratnasamy , Brad Karp , Li Yin , Fang Yu , Deborah Estrin , Ramesh Govindan , Scott Shenker, GHT: a geographic hash table for data-centric storage, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570750]
• 8: Rik Sarkar , Xianjin Zhu , Jie Gao, Double rulings for information brokerage in sensor networks, Proceedings of the 12th annual international conference on Mobile computing and networking, September 23-29, 2006, Los Angeles, CA, USA [doi>10.1145/1161089.1161122]
• 9: Ivan Stojmenovic , Dandan Liu , Xiaohua Jia, A scalable quorum-based location service in ad hoc and sensor networks, International Journal of Communication Networks and Distributed Systems, v.1 n.1, p.71-94, February 2008 [doi>10.1504/IJCNDS.2008.017205]
• 10: J. B. Tchakarov and N. H. Vaidya. "Efficient Content Location in Wireless Ad Hoc Networks". In Proc. of IEEE MDM, pages 74--85, 2004.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Applications (SMTP, FTP, etc.)

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Design studies

General Terms:
Algorithms, Performance

Keywords:
localized algorithms, sensor networks, service discovery