hide
Free keywords:
-
Abstract:
In a sensor network information from multiple nodes must usually be aggregated
in order to accomplish a certain task. A natural way to view this information
gathering is in terms of interactions between nodes that are producers of
information, e.g., those that have collected data, detected events, etc., and
nodes that are consumers of information, i.e., nodes that seek data or events
of certain types. Our overall goal in this paper is to construct efficient
schemes allowing consumer and producer nodes to discover each other so that the
desired information can be delivered quickly to those who seek it. Here,
efficiency means both limiting the redundancy of where producer information is
stored, as well as bounding the consumer query times. We introduce the notion
of distance-sensitive information brokerage and provide schemes for efficiently
bringing together information producers and consumers at a cost proportional to
the separation between them — even though neither the consumers nor the
producers know about each other beforehand.
Our brokerage scheme is generic and can be implemented on top of several
hierarchical routing schemes that have been proposed in the past, provided that
they are augmented with certain key sideway links. For such augmented
hierarchical routing schemes we provide a rigorous theoretical performance
analysis, which further allows us to prove worst case query times and storage
requirements for our information brokerage scheme. Experimental results
demonstrate that the practical performance of the proposed approaches far
exceeds their theoretical (worst-case) bounds. The presented algorithms rely
purely on the topology of the communication graph of the sensor network and do
not require any geographic location information.
