Distance-Sensitive Information Brokerage in Sensor Networks
Stefan Funke, Leonidas J. Guibas, An Nguyen, Yusu Wang
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 \emph{producers} of information, e.g.,
those that have collected data, detected events, etc., and nodes
that are \emph{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 \emph{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.
PDF