Article

Publish/Subscribe Tree Construction in Wireless Ad-Hoc Networks

Authors:

Yongqiang Huang,

Hector Garcia-MolinaAuthors Info & Claims

MDM '03: Proceedings of the 4th International Conference on Mobile Data Management

Pages 122 - 140

Published: 21 January 2003 Publication History

Abstract

Wireless ad-hoc publish/subscribe systems combine a publish/subscribe mechanism with wireless ad-hoc networking. The combination, although very attractive, has not been studied extensively in the literature. This paper addresses an important problem of such systems: how to construct an optimal publish/ subscribe tree for routing information from the source to all interested recipients. First we precisely define the optimality of a publish/subscribe tree by developing a metric to evaluate its "efficiency." The optimality metric takes into account both the goal of a publish/subscribe system (i.e., to route a set of events), and the characteristics of an ad-hoc network (for example, devices are resource limited). We propose a greedy algorithm, SHOPPARENT, which builds the publish/ subscribe tree in a fully distributed fashion. A key feature is that this algorithm can be "subscription-aware", allowing it to use publication/subscription information in order to find a better outcome. Our simulations show that SHOPPARENT's performance is within 15% of optimal under normal configurations. We also study the effect of geographically localized subscriptions.

References

[1]

Huang, Y., Garcia-Molina, H.: Publish/subscribe in a mobile enviroment. In: Proceedings of the Second ACM International Workshop on Data Engineering for Wireless and Mobile Access. (2001) 27-34.

[2]

Cugola, G., Nitto, E.D., Picco, G.P.: Content-based dispatching in a mobile environment. In: Workshop su Sistemi Distribuiti: Algoritmi, Architetture e Linguaggi. (2000).

[3]

Meier, R., Cahill, V.: STEAM: Event-based middleware for wireless ad hoc networks. In: Proceedings of the International Workshop on Distributed Event-Based Sytems. (2002) 639-644.

[4]

Estrin, D., Govindan, R., Heidemann, J., Kumar, S.: Next century challenges: scalable coordination in sensor networks. In: Proceedings of the Fifth Annual ACM/IEEE International Conference on Mobile Computing and Networking. (1999) 263-270.

[5]

Lim, H., Kim, C.: Multicast tree construction and flooding in wireless ad hoc networks. In: Proceedings of the 3rd ACM International Workshop on Modeling, Analysis and Simulation of Wireless and Mobile Systems. (2000) 61-68.

[6]

Wu, C., Tay, Y., C.-K.Toh: Ad hoc Multicast Routing protocol utilizing Increasing idnumberS (AMRIS) functional specification. Internet Draft (1998).

[7]

Garcia-Molina, H., Kogan, B.: An implementation of reliable broadcast using an unreliable multicast facility. In: Proceedings of the 7th IEEE Symposium on Reliable Distributed Systems. (1988) 101-111.

[8]

Lee, S.J., Su, W., Hsu, J., Gerla, M., Bagrodia, R.: A performance comparison study of ad hoc wireless multicast protocols. In: Proceedings of the IEEE Conference on Computer Communications (INFOCOM). (2000) 565-574.

[9]

Kantor, B., Lapsley, P.: Network News Transfer Protocol: A proposed standard for the stream-based transmission of news. Request for Comments: 977 (1986).

[10]

Banavar, G., Kaplan, M., Shaw, K., Strom, R.E., Sturman, D.C., Tao, W.: Information flow based event distribution middleware. In: Proceedings of the 1999 ICDCS Workshop on Electronic Commerce and Web-Based Applications. (1999).

[11]

Carzaniga, A., Rosenblum, D.S., Wolf, A.L.: Achieving scalability and expressiveness in an Internet-scale event notification service. In: Proceedings of the 19th Annual ACM Symposium on Principles of Distributed Computing. (2000) 219-227.

[12]

Ho, C., Obraczka, K., Tsudik, G., Viswanath, K.: Flooding for reliable multicast in multihop ad hoc netowrks. In: Proceedings of the 3rd International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIAL-M'99). (1999) 64-71.

[13]

Oki, B., Pfluegl, M., Siegel, A., Skeen, D.: The Information Bus - an architecture for extensible distributed systems. Operating Systems Review 27.5 (1993) 58-68.

[14]

Segall, B., Arnold, D.: Elvin has left the building: A publish/subscribe notification service with quenching. In: Proceedings of the 1997 Australian UNIX Users Group Technical Conference. (1997) 243-255.

[15]

TIBCO Software Inc.: TIBCO Rendezvous. (http://www.tibco.com/ solutions/products/active_enterprise/rv/).

[16]

Cabrera, L.F., Jones, M.B., Theimer, M.: Herald: Achieving a global event notification service. In: Proceedings of the Eighth Workshop on Hot Topics in Operating Systems (HotOS-VIII). (2001).

[17]

Bonnet, P., Gehrke, J., Seshadri, P.: Towards sensor database systems. In: Proceedings of the 2nd International Conference on Mobile Data Management. (2001) 3-14.

Cited By

Siegemund GTurau V(2018)A Self-Stabilizing Publish/Subscribe Middleware for IoT ApplicationsACM Transactions on Cyber-Physical Systems10.1145/31855092:2(1-26)Online publication date: 9-Jun-2018
https://dl.acm.org/doi/10.1145/3185509
Dehghani SEhsani SHajiaghayi MLiaghat V(2016)Online degree-bounded steiner network designProceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms10.5555/2884435.2884448(164-175)Online publication date: 10-Jan-2016
https://dl.acm.org/doi/10.5555/2884435.2884448
Kündig SLeone PRolim JCuevas ÁChatzimisios PDe Grande R(2016)A Distributed Algorithm Using Path Dissemination for Publish-Subscribe Communication PatternsProceedings of the 14th ACM International Symposium on Mobility Management and Wireless Access10.1145/2989250.2989268(35-42)Online publication date: 13-Nov-2016
https://dl.acm.org/doi/10.1145/2989250.2989268
Show More Cited By

Index Terms

Publish/Subscribe Tree Construction in Wireless Ad-Hoc Networks
1. Networks
  1. Network types
    1. Mobile networks
2. Software and its engineering
  1. Software organization and properties
    1. Software system structures
      1. Distributed systems organizing principles

Index terms have been assigned to the content through auto-classification.

Recommendations

Subscription-aware publish/subscribe tree construction in mobile ad hoc networks
ICPADS '07: Proceedings of the 13th International Conference on Parallel and Distributed Systems - Volume 01

A publish/subscribe system consists of publishers, subscribers, and a delivery infrastructure, where publishers produce events, subscribers declare their interests in receiving events via subscriptions, and the delivery infrastructure forwards ...
High performance publish/subscribe protocols for wireless ad hoc networks using geographic information
The Analysis of Publish/Subscribe Systems over Mobile Wireless Ad Hoc Networks
MOBIQUITOUS '07: Proceedings of the 2007 Fourth Annual International Conference on Mobile and Ubiquitous Systems: Networking&Services (MobiQuitous)

In this work, we analyze the publish/subscribe distributed system paradigm over mobile ad hoc networks with respect to the performance and the impact of different mobility speeds and patterns of all participants in urban and high-way scenarios. In order ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

MDM '03: Proceedings of the 4th International Conference on Mobile Data Management

January 2003

412 pages

ISBN:3540003932

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 21 January 2003

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

28
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 26 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Siegemund GTurau V(2018)A Self-Stabilizing Publish/Subscribe Middleware for IoT ApplicationsACM Transactions on Cyber-Physical Systems10.1145/31855092:2(1-26)Online publication date: 9-Jun-2018
https://dl.acm.org/doi/10.1145/3185509
Dehghani SEhsani SHajiaghayi MLiaghat V(2016)Online degree-bounded steiner network designProceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms10.5555/2884435.2884448(164-175)Online publication date: 10-Jan-2016
https://dl.acm.org/doi/10.5555/2884435.2884448
Kündig SLeone PRolim JCuevas ÁChatzimisios PDe Grande R(2016)A Distributed Algorithm Using Path Dissemination for Publish-Subscribe Communication PatternsProceedings of the 14th ACM International Symposium on Mobility Management and Wireless Access10.1145/2989250.2989268(35-42)Online publication date: 13-Nov-2016
https://dl.acm.org/doi/10.1145/2989250.2989268
Yoon YRobinson NMuthusamy VMcIlraith SJacobsen HOssowski S(2016)Planning the transformation of overlaysProceedings of the 31st Annual ACM Symposium on Applied Computing10.1145/2851613.2851639(500-507)Online publication date: 4-Apr-2016
https://dl.acm.org/doi/10.1145/2851613.2851639
Abdennadher FBen Jemaa MNikoletseas SRumín Á(2013)Accurate prediction of mobility into publish/subscribeProceedings of the 11th ACM international symposium on Mobility management and wireless access10.1145/2508222.2508234(101-106)Online publication date: 3-Nov-2013
https://dl.acm.org/doi/10.1145/2508222.2508234
Pham CTran D(2013)DIBSAd Hoc Networks10.1016/j.adhoc.2012.08.00811:3(735-746)Online publication date: 1-May-2013
https://dl.acm.org/doi/10.1016/j.adhoc.2012.08.008
Mutluoglu MBaydere S(2011)Network capacity analysis for code propagation in Wireless Sensor NetworksInternational Journal of Ad Hoc and Ubiquitous Computing10.1504/IJAHUC.2011.0407717:4(221-234)Online publication date: 1-Jun-2011
https://dl.acm.org/doi/10.1504/IJAHUC.2011.040771
Pei GRavindran BJensen E(2011)Self-organizing and self-reconfigurable event routing in ad hoc networks with causal dependency awarenessACM Transactions on Autonomous and Adaptive Systems10.1145/2019583.20195866:3(1-28)Online publication date: 29-Sep-2011
https://dl.acm.org/doi/10.1145/2019583.2019586
Ma SWolfson OLin JGeers GTimpf S(2010)IIPProceedings of the Third International Workshop on Computational Transportation Science10.1145/1899441.1899443(1-6)Online publication date: 2-Nov-2010
https://dl.acm.org/doi/10.1145/1899441.1899443
Thanawala RWu JSrinivasan A(2009)Efficient resource discovery in mobile ad hoc networksProceedings of the 2009 IEEE international conference on Communications10.5555/1817271.1817340(363-367)Online publication date: 14-Jun-2009
https://dl.acm.org/doi/10.5555/1817271.1817340
Show More Cited By

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents