TITLE: Publish/Subscribe Tree Construction in Wireless Ad-Hoc Networks

AUTHORS:
Yongqiang Huang and Hector Garcia-Molina
Department of Computer Science
Stanford University
Stanford, CA 94305
{yhuang, hector}@cs.stanford.edu

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.