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||http://infolab.stanford.edu/|
|Deposited By:||Import Account|
|Deposited On:||15 Nov 2001 16:00|
|Last Modified:||27 Dec 2008 10:01|
Repository Staff Only: item control page