Fractionally Cascaded Information in a Sensor NetworkJie Gao∗Leonidas J. Guibas∗John Hershberger†Li Zhang‡ABSTRACTWe address the problem of distributed information aggrega-tion and storage in a sensor network, where queries can beinjected anywhere in the network. The principle we prop oseis that a sensor should know a “fraction” of the informationfrom distant parts of the network, in an exponentially decay-ing fashion by distance. We show how a sampled scalar fieldcan be stored in this distributed fashion, with only a mod-est amount of additional storage and network traffic. Ourstorage scheme makes neighboring sensors have highly corre-lated world views; this allows smooth information gradientsand enables local search algorithms to work well. We studyin particular how this principle of fractionally cascaded in-formation can be exploited to answer range queries aboutthe sampled field efficiently. Using local decisions only weare able to route the query to exactly the portions of thefield where the sought information is stored. We providea rigorous theoretical analysis showing that our scheme isclose to optimal.Categories and Subject DescriptorsH.3.3 [Information Systems]: information storage and re-trieval—information search and retrieval; F.2.2 [Theory ofComputation]: analysis of algorithms and problem com-plexity—non-numerical algorithms and problemsGeneral TermsAlgorithms, Design∗Department of Computer Science, Stanford Uni-versity, Stanford, CA 94305, USA Email: {jgao,guibas}@cs.stanford.edu†Mentor Graphics, 8005 S.W. Boeckman Road, Wilsonville,OR 97070, USA Email:john [email protected]‡Hewlett-Packard Labs, 1501 Page Mill Road, Palo Alto,CA 94304, USA Email: [email protected] to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies arenot made or distributed for profit or commercial advantage and that copiesbear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.IPSN’04, April 26–27, 2004, Berkeley, California, USA.Copyright 2004 ACM 1-58113-846-6/04/0004 ...$5.00.KeywordsSensor networks, information aggregation and storage, frac-tional cascading, range searching1. INTRODUCTIONSensor network technology is in a rapid state of evolu-tion, especially at the hardware level. Sensors are becom-ing smaller, more power efficient, and less expensive [5].Networking for sensor networks is also quickly developing,with certain protocols such as directed diffusion [11] al-ready widely deployed and sensor-net specific adaptationsof the network stack drilling down all the way to the MAClayer [23, 10]. But for sensor nets to attain their true po-tential, equal strides must be made at the application level,facilitating the deployment and use of a sensor network fora variety of purposes by many simultaneous and geographi-cally distributed users. To this end, a more abstract view ofthe sensor network is useful, and the view that has receivedthe most attention to date is that of the sensor network asa distributed database [8].The advantage of the database approach is that it offersa separation between the logical view (naming, access, op-erations) of the data held by the sensor net and the actualimplementation of these operations on the physical network.Though any such abstraction comes with some loss of effi-ciency, it compensates by increased ease of use. Sensor netusers can focus on the logical structure of the queries theywant to ask and are relatively isolated from the details ofphysical storage and data networking on the volatile physi-cal infrastructure of the network (sensors can fail, links comeand go, etc.).Standard distributed database technology, however, can-not be ported as-is to sensor networks because both the log-ical structure of the data and the economics of the physicalmedium are different. At the logical level, one major dif-ference is that sensor data are typically measurements fromthe physical world and as such there is always the potentialof error. Thus exact queries are not so meaningful in thesensor network context—instead it is more appropriate touse probabilistic queries [6], or range queries, where we askthat the values of certain attributes lie in certain ranges.Furthermore, sensors often sample a physical quantity atdiscrete time intervals and thus generate a stream of data.Whatever index structure we plan to build must thereforebe able to accommodate a stream of continuous updates, aswe go forward in time. Furthermore, the cost of processinga query is likely to be dominated more by the communica-tion costs of getting to all the relevant data than by the datapro cessing or aggregation cost. While in a classical databasewe worry about what and how much to store in an index, inthe sensor net setting the dominant worry is where to storethe distributed index.In this paper we investigate a new lightweight distributedmechanism for storing data in a sensor network that allowsrange queries injected anywhere in the network to be servedefficiently. The key idea of our approach is to store at eachsensor information about data available elsewhere in the net-work, but in such a way that a sensor knows only a “frac-tion” of the information from distant parts of the network, inan exponentially decaying fashion by distance. The preciseway in which information is to be subsampled, compressed,or aggregated to meet this constraint will be application de-p endent. This accomplishes three goals simultaneously:• the total amount of information duplication across allsensors is kept small, because of the geometric decreasewith distance,• the communication cost required to build this indexand its update cost remain reasonable, as on the aver-age information travels only short distances, and• neighboring sensors have highly-correlated world views;this allows for smooth information gradients and en-ables local search algorithms to work well.Because our method is effectively a broadcast with geometricdecay of the information, we call the technique fractionalcascading.Although several prior works, as discussed below, havealso given distributed indices for range queries in sensornetworks, our approach highlights an important aspect ofqueries in a sensor network that has not been discussedmuch up to now. This is the issue of locality: when