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, Shop Parent, 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 Shop Parent’s performance is within 15% of optimal under normal configurations. We also study the effect of geographically localized subscriptions.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
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
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)
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
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
Lim, H., Kim, C.: Multicast tree construction and flooding in wireless ad hoc networks. In: Proceedings of the 3rd ACMInternationalWorkshop on Modeling, Analysis and Simulation of Wireless and Mobile Systems. (2000) 61–68
Wu, C., Tay, Y., C.-K. Toh: Ad hoc Multicast Routing protocol utilizing Increasing idnumberS (AMRIS) functional specification. Internet Draft (1998)
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
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
Kantor, B., Lapsley, P.: Network News Transfer Protocol: A proposed standard for the stream-based transmission of news. Request for Comments: 977 (1986)
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)
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
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
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
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
TIBCO Software Inc.: TIBCO Rendezvous. (http://www.tibco.com/solutions/products/active_enterprise/rv/)
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)
Bonnet, P., Gehrke, J., Seshadri, P.: Towards sensor database systems. In: Proceedings of the 2nd International Conference on Mobile Data Management. (2001) 3–14
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Huang, Y., Garcia-Molina, H. (2003). Publish/Subscribe Tree Construction in Wireless Ad-Hoc Networks. In: Chen, MS., Chrysanthis, P.K., Sloman, M., Zaslavsky, A. (eds) Mobile Data Management. MDM 2003. Lecture Notes in Computer Science, vol 2574. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36389-0_9
Download citation
DOI: https://doi.org/10.1007/3-540-36389-0_9
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-00393-9
Online ISBN: 978-3-540-36389-7
eBook Packages: Springer Book Archive