|
|
|
                                           
|
Return to Information Management
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.
@inproceedings {DBLP:conf/mdm/HuangG03, author = {Yongqiang Huang and Hector Garcia-Molina}, booktitle = {Mobile Data Management}, title = {Publish/Subscribe Tree Construction in Wireless Ad-Hoc Networks.}, pages = {122-140}, year = {2003}, url = {db/conf/mdm/mdm2003.html#HuangG03}, ee = {http://link.springer.de/link/service/series/0558/bibs/2574/25740122.htm}, crossref = {conf/mdm/2003}, bibsource = {DBLP, http://dblp.uni-trier.de} }  ©2005 Association for Computing Machinery |
