Detecting the presence of nodes in MANETs

ABSTRACT

While mobility in the sense of node movement has been an intensively studied aspect of mobile ad-hoc networks (MANETs), another aspect of mobility has not yet been subjected to systematic research: nodes may not only move around but also enter and leave the network. In fact, many proposed protocols for MANETs exhibit worst-case behavior when an intended communication partner is currently not present. Therefore, knowing whether a given node is currently present in the network can often help to avoid unnecessary overhead. In this paper, we present a solution to the presence detection problem. Our method uses a Bloom filter-based beaconing mechanism to aggregate and distribute information about the presence of network nodes. Analytical and simulation results show interesting properties of presence detection in wireless multihop environments and underline the effectiveness and practical applicability of our approach.

REFERENCES

• 1: Burton H. Bloom, Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, v.13 n.7, p.422-426, July 1970 [doi>10.1145/362686.362692]
• 2: K. Cheng, M. Iwaihara, L. Xiang, and K. Ushijima. Efficient Web Profiling by Time-Decaying Bloom Filters. Database Society of Japan Letters, 4(1):137--140, June 2005.
• 3: Kai Cheng , Limin Xiang , Mizuho Iwaihara , Haiyan Xu , Mukesh M. Mohania, Time-Decaying Bloom Filters for Data Streams with Skewed Distributions, Proceedings of the 15th International Workshop on Research Issues in Data Engineering: Stream Data Mining and Applications, p.63-69, April 03-04, 2005 [doi>10.1109/RIDE.2005.15]
• 4: Nathan Eagle , Alex Pentland, Social Serendipity: Mobilizing Social Software, IEEE Pervasive Computing, v.4 n.2, p.28-34, April 2005 [doi>10.1109/MPRV.2005.37]
• 5: Li Fan , Pei Cao , Jussara Almeida , Andrei Z. Broder, Summary cache: a scalable wide-area web cache sharing protocol, IEEE/ACM Transactions on Networking (TON), v.8 n.3, p.281-293, June 2000 [doi>10.1109/90.851975]
• 6: Robert Gilbert , Kerby Johnson , Shaomei Wu , Ben Y. Zhao , Haitao Zheng, Location independent compact routing for wireless networks, Proceedings of the 1st international workshop on Decentralized resource sharing in mobile computing and networking, July 25-25, 2006, Los Angeles, California [doi>10.1145/1161252.1161267]
• 7: S. Giordano and M. Hamdi. Mobility Management: The Virtual Home Region. Technical Report SSC/1999/037, EPFL-ICA, Lausanne, Switzerland, Oct. 1999.
• 8: P. Gupta and P. R. Kumar. The Capacity of Wireless Networks. IEEE Transactions on Information Theory, 46(2):388--404, Mar. 2000.
• 9: L. E. Holmquist, J. Falk, and J. Wigström. Supporting Group Collaboration with Interpersonal Awareness Devices. Springer Personal and Ubiquitous Computing, 3(1/2):13--21, Mar. 1999.
• 10: Y. Iwatani. Love: Japanese Style. Wired News, online, http://www.wired.com/news/culture/0,1284,12899,00.html, June 1998.
• 11: P. Jacquet, P. Mühlethaler, T. Clausen, A. Laouiti, A. Qayyum, and L. Viennot. Optimized Link State Routing Protocol. In INMIC '01: Proceedings of the 5th IEEE International Multi Topic Conference, pages 62--68, Dec. 2001.
• 12: D. B. Johnson and D. A. Maltz. Dynamic Source Routing in Ad Hoc Wireless Networks. In T. Imielinski and H. F. Korth, editors, Mobile Computing, pages 153--181. Kluwer Academic Publishers, Norwell, MA, USA, Jan. 1996.
• 13: Wolfgang Kieß , Holger Füßler , Jörg Widmer , Martin Mauve, Hierarchical location service for mobile ad-hoc networks, ACM SIGMOBILE Mobile Computing and Communications Review, v.8 n.4, p.47-58, October 2004 [doi>10.1145/1052871.1052875]
• 14: Choonhwa Lee , Sungshick Yoon , Eunsam Kim , Abdelsalam (Sumi) Helal, An efficient service propagation scheme for large-scale MANETs, Proceedings of the 4th international workshop on Middleware for Pervasive and Ad-Hoc Computing (MPAC 2006), p.9, November 27-December 01, 2006, Melbourne, Australia [doi>10.1145/1169075.1169084]
• 15: C. Lindemann and O. P. Waldhorst. Effective Dissemination of Presence Information in Highly Partitioned Mobile Ad Hoc Networks. In SECON '06: Proceedings of the 3rd IEEE ComSoc Conference on Sensor, Mesh and Ad Hoc Communications and Networks, Sept. 2006.
• 16: Robert Morris , John Jannotti , Frans Kaashoek , Jinyang Li , Douglas Decouto, CarNet: a scalable ad hoc wireless network system, Proceedings of the 9th workshop on ACM SIGOPS European workshop: beyond the PC: new challenges for the operating system, September 17-20, 2000, Kolding, Denmark [doi>10.1145/566726.566741]
• 17: The Network Simulator ns-2, version 2.30. Online, http://www.isi.edu/nsnam/ns/.
• 18: Charles E. Perkins , Elizabeth M. Royer, Ad-hoc On-Demand Distance Vector Routing, Proceedings of the Second IEEE Workshop on Mobile Computer Systems and Applications, p.90, February 25-26, 1999
• 19: S. C. Rhea and J. Kubiatowicz. Probabilistic Location and Routing. In INFOCOM '02: Proceedings of the 19th Annual Joint Conference of the IEEE Computer and Communications Societies, volume 3, pages 1248--1257, June 2002.
• 20: I. Stojmenovic. Home Agent Based Location Update and Destination Search Schemes in Ad Hoc Wireless Networks. Technical Report TR-99-10, University of Ottawa, Sept. 1999.
• 21: Michael Terry , Elizabeth D. Mynatt , Kathy Ryall , Darren Leigh, Social net: using patterns of physical proximity over time to infer shared interests, CHI '02 extended abstracts on Human factors in computing systems, April 20-25, 2002, Minneapolis, Minnesota, USA [doi>10.1145/506443.506612]

INDEX TERMS

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

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

General Terms:
Algorithms, Design, Performance

Keywords:
MANETs, mobile ad-hoc networks, presence detection, soft state bloom filter