Stanford InfoLab Publication Server

Publish/Subscribe Tree Construction in Wireless Ad-Hoc Networks

Huang, Yongqiang and Garcia-Molina, Hector (2001) Publish/Subscribe Tree Construction in Wireless Ad-Hoc Networks. Technical Report. Stanford.




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.

Item Type:Techreport (Technical Report)
Uncontrolled Keywords:publish/subscribe; wireless ad-hoc networks; wireless multicast; event systems; routing trees
Subjects:Computer Science > Distributed Systems
Computer Science > Mobile Computing
Related URLs:Project Homepage
ID Code:520
Deposited By:Import Account
Deposited On:15 Nov 2001 16:00
Last Modified:27 Dec 2008 10:01

Download statistics

Repository Staff Only: item control page