skip to main content
10.1145/1266894.1266900acmconferencesArticle/Chapter ViewAbstractPublication PagesdebsConference Proceedingsconference-collections
Article

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

Published: 20 June 2007 Publication History

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]
Carzaniga, A., Rosenblum D., and Wolf A., "Achieving Scalability and Expressiveness in an Internet-Scale Event Notification System," Proc. 19th Symposium on Principles of Distributed Computing, 219--227, 2000.
[4]
Broch, J., Maltz, D., Johnson, D., Hu, Y.-C., and Jetcheva, J., "A Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols," in Proceedings of the 4th Annual ACM/IEEE Int'l Conference on Mobile Computing and Networking, 85--97, 1998.
[5]
Chakraborty, D., Chakraborty, A., Yesha, Y., and Finin, T., "Toward Distributed Service Discovery in Pervasive Computing Environments," IEEE Trans. on Mobile Computing, 5, 2 (February 2006), 97--112.
[6]
Chen, Y. and Schwan, K., "Opportunistic Overlays: Efficient Content Delivery in Mobile Ad Hoc Networks," Proceedings of the 6th 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]
Eugster, P. T., Felber, P. A., Guerraoui, R., and Kermarrec, A.-M., "The Many Faces of Publish/Subscribe," ACM Computing Surveys, 35, 2 (June 2003), 114--131.
[11]
Franklin, M. and Zdonik, S., "A Framework for Scalable Dissemination-Based Systems," In Proceedings of the 12th ACM Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA'97), pp. 94--105, October 1997.
[12]
Guha, S. and Khullar, S., "Approximation Algorithms for Connected Dominating Sets," European Symposium on Algorithms, 179--193, 1996.
[13]
Huang, Y. and Garcia-Molina, H., "Publish/subscribe in a mobile environment," In Proc. of MobiDE, 27--34, 2001.
[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]
Jardosh, O., Belding-Royer, E., Almeroth, K., and Suri, S., "Towards Realistic Mobility Models for Mobile Ad hoc Networks," MobiCom '03, 217--229, 2003.
[16]
Karger, D., Lehman, E., Leighton, F., Levine, M., Lewin, D., and R. Panigrahy, "Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the World Wide Web," In Proc. of 29th Annual ACM Symposium on Theory of Computing, 654--663, May 1997.
[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]
Naumov, V. and Gross, T., "Scalability of Routing Methods in Ad Hoc Networks," Performance Evaluation, 62, 193--209, 2005.
[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.

Cited By

View all
  1. An efficient demand-driven and density-controlled publish/subscribe protocol for mobile environments

      Recommendations

      Comments

      Information & Contributors

      Information

      Published In

      cover image ACM Conferences
      DEBS '07: Proceedings of the 2007 inaugural international conference on Distributed event-based systems
      June 2007
      275 pages
      ISBN:9781595936653
      DOI:10.1145/1266894
      Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

      Sponsors

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      Published: 20 June 2007

      Permissions

      Request permissions for this article.

      Check for updates

      Author Tags

      1. connected dominating sets
      2. controlled flooding
      3. mobile ad hoc networks

      Qualifiers

      • Article

      Conference

      DEBS07
      Sponsor:
      DEBS07: Distributed Event-based Systems Conference
      June 20 - 22, 2007
      Ontario, Toronto, Canada

      Acceptance Rates

      Overall Acceptance Rate 145 of 583 submissions, 25%

      Upcoming Conference

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • Downloads (Last 12 months)0
      • Downloads (Last 6 weeks)0
      Reflects downloads up to 18 Feb 2025

      Other Metrics

      Citations

      Cited By

      View all
      • (2016)Dynamic collaborative in-network event detection in wireless sensor networksTelecommunications Systems10.1007/s11235-015-9981-062:1(43-58)Online publication date: 1-May-2016
      • (2013)A context-aware cross-layer broadcast model for ad hoc networksPersonal and Ubiquitous Computing10.1007/s00779-013-0699-218:4(851-864)Online publication date: 29-Jun-2013
      • (2012)A Context-Aware Cross-Layer Broadcast Model for Ad Hoc NetworksProcedia Computer Science10.1016/j.procs.2012.06.06610(517-524)Online publication date: 2012
      • (2010)Demand-driven publish/subscribe in mobile environmentsWireless Networks10.1007/s11276-010-0256-016:8(2237-2261)Online publication date: 1-Nov-2010
      • (2009)Distributed delayProceedings of the 3rd international conference on New technologies, mobility and security10.5555/1790343.1790436(479-483)Online publication date: 20-Dec-2009
      • (2009)Distributed Delay: Improving Network Throughput by Reducing Temporal Saturation2009 3rd International Conference on New Technologies, Mobility and Security10.1109/NTMS.2009.5384660(1-5)Online publication date: Dec-2009
      • (2008)Dynamic Subscription PermissionProceedings of the 2008 IEEE Asia-Pacific Services Computing Conference10.1109/APSCC.2008.228(211-216)Online publication date: 9-Dec-2008
      • (2008)An Overlay Architecture for Vehicular NetworksNETWORKING 2008 Ad Hoc and Sensor Networks, Wireless Networks, Next Generation Internet10.1007/978-3-540-79549-0_6(60-71)Online publication date: 2008
      • (2008)Content Discovery in Heterogeneous Mobile NetworksHeterogeneous Wireless Access Networks10.1007/978-0-387-09777-0_15(1-20)Online publication date: 25-Aug-2008

      View Options

      Login options

      View options

      PDF

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader

      Figures

      Tables

      Media

      Share

      Share

      Share this Publication link

      Share on social media