An efficient demand-driven and density-controlled publish/subscribe protocol for mobile environments

ABSTRACT

A protocol for high-density Mobile Ad Hoc Networks (MANETs) is presented. Subscription-Based Permission (SP) routing extends Self-Balancing Supply/Demand (SBSD) protocols, which combine the Publish/Subscribe paradigm and demand-controlled flooding. The goal of SP is to reduce redundant broadcasting without sacrificing coverage, by exploiting high density. SP defines η sets of brokers, each set refusing to accept replicas of a fraction (1/η) of all subscription types. The value of η is determined such that each set is expected to comprise a connected dominating set. Given a theoretical mobile device population N0 sufficient to achieve one connected dominating graph and an actual network population N > N0, we show that SBSD-SP increases subscription propagation areas by a factor of (N/N0) without materially sacrificing reachability. This improves network throughput by a factor of (N/N0), as publications are delivered to (N/N0) times as many brokers.

REFERENCES

• 1: Abramson, N., "The Throughput of Packet Broadcasting Channels," IEEE Trans. Communications, 25 (January 1977), 117--128.
• 2: Barabási, A.-L. and Albert, R., "Emergence of Scaling in Random Networks," Science, 286, 509--512, 1999.
• 3: Antonio Carzaniga , David S. Rosenblum , Alexander L. Wolf, Achieving scalability and expressiveness in an Internet-scale event notification service, Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.219-227, July 16-19, 2000, Portland, Oregon, United States [doi>10.1145/343477.343622]
• 4: Josh Broch , David A. Maltz , David B. Johnson , Yih-Chun Hu , Jorjeta Jetcheva, A performance comparison of multi-hop wireless ad hoc network routing protocols, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.85-97, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288256]
• 5: Dipanjan Chakraborty , Anupam Joshi , Yelena Yesha , Tim Finin, Toward Distributed Service Discovery in Pervasive Computing Environments, IEEE Transactions on Mobile Computing, v.5 n.2, p.97-112, February 2006 [doi>10.1109/TMC.2006.26]
• 6: Chen, Y. and Schwan, K., "Opportunistic Overlays: Efficient Content Delivery in Mobile Ad Hoc Networks," Proceedings of the 6^th ACM/IFIP/USENIX International Middleware Conference (Middleware 2005), November 2005.
• 7: Cockayne, E. and Hedetniemi, "Optimal Domination in Graphs," IEEE Transactions on Circuits and Systems, 22, 11, 855--857, 1975.
• 8: Costa, P., Picco, G., and Rosetto, S., "Publish/subscribe on Sensor Networks: A Semi-Probabilistic Approach," The 2nd IEEE International Conference on Mobile Ad-hoc and Sensor Systems (MASS05), Washington DC, USA, November, 2005.
• 9: Das, B. and Bharghavan, V., "Routing in Ad-Hoc Networks Using Minimum Connected Dominating Sets," in IEEE Int'l Conference on Communications (ICC '97), 1997.
• 10: Patrick Th. Eugster , Pascal A. Felber , Rachid Guerraoui , Anne-Marie Kermarrec, The many faces of publish/subscribe, ACM Computing Surveys (CSUR), v.35 n.2, p.114-131, June 2003 [doi>10.1145/857076.857078]
• 11: Michael Franklin , Stanley Zdonik, A framework for scalable dissemination-based systems, Proceedings of the 12th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.94-105, October 05-09, 1997, Atlanta, Georgia, United States
• 12: Sudipto Guha , Samir Khuller, Approximation Algorithms for Connected Dominating Sets, Proceedings of the Fourth Annual European Symposium on Algorithms, p.179-193, September 25-27, 1996
• 13: Yongqiang Huang , Hector Garcia-Molina, Publish/Subscribe in a mobile enviroment, Proceedings of the 2nd ACM international workshop on Data engineering for wireless and mobile access, p.27-34, May 2001, Santa Barbara, California, United States [doi>10.1145/376868.376889]
• 14: Issariyakul, T., Hossain, E., and Kim, D., "Medium Access Control Protocols for Wireless Mobile Ad Hoc Networks: Issues and Approaches," Wireless Communications and Mobile Computing, 3, 935--958, 2003.
• 15: Amit Jardosh , Elizabeth M. Belding-Royer , Kevin C. Almeroth , Subhash Suri, Towards realistic mobility models for mobile ad hoc networks, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.939008]
• 16: David Karger , Eric Lehman , Tom Leighton , Rina Panigrahy , Matthew Levine , Daniel Lewin, Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the World Wide Web, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.654-663, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258660]
• 17: Liang, B. and Haas, Z., "Virtual Backbone Generation and Maintenance in Ad Hoc Network Mobility Management," INFOCOM 2000, 1293--1302, 2000.
• 18: Min, M., Wang, F., Du, D.-Z., and Pardalos, P. M., "A Reliable Virtual Backbone Scheme in Mobile Ad-Hoc Networks," in 1st IEEE International Conference on Mobile Ad-hoc and Sensor Systems (MASS), 2004.
• 19: Valery Naumov , Thomas Gross, Scalability of routing methods in ad hoc networks, Performance Evaluation, v.62 n.1-4, p.193-209, October 2005 [doi>10.1016/j.peva.2005.07.024]
• 20: Newman, M., "The Structure and Function of Complex Networks," SIAM Review, 45, 2, 167--256, 2003.
• 21: Ouksel, A., "Self-Balancing Selective Information Dissemination and Discovery in Mobile Environments," IEEE International Conference of Data Engineering (ICDE), Atlanta, March 2006.
• 22: Ouksel, A. and Lundquist, D., "Demand-Driven Publish/Subscribe in Mobile Networks," University of Illinois at Chicago Technical Report, September 2006. Submitted to IEEE Transactions on Mobile Computing.
• 23: Royer, E., Melliar-Smith, P., and Moser, L., "An Analysis of the Optimum Node Density for Ad Hoc Mobile Networks," in Proceedings of the IEEE Int'l Conference on Communications (ICC '01), 2001.
• 24: Zorzi, M. and Tomba, L., "A Comparison of CDMA, TDMA, and Slotted Aloha Multiple Access Schemes in Cellular Mobile Radio Systems," PIMRC '94, 1994.

INDEX TERMS

General Terms:
Performance, Reliability

Keywords:
connected dominating sets, controlled flooding, mobile ad hoc networks