I IntroductionII General FrameworkIII Case Study: Proximity-based LocalizationIII-A AssumptionsIII-B Problem FormulationIII-C Scaling by TieringIII-D Other Localization TechniquesIV Power-aware RoutingIV-A AssumptionsIV-B Problem FormulationV ConclusionsReferences1Rethinking Data Fusion-based Services in TieredSensor NetworksKarthik Dantu Gaurav [email protected] [email protected]—Tiered sensor network architectures are gaining currency.In contrast with flat networks of impoverished nodes (thehitherto common assumption in sensor networking), suchsystems offer the promise of migrating computational loadfrom sensing nodes to higher capability ’master’ nodes.We argue that for certain data fusion-based services thismeans that compute intensive algorithms, often shunnedas impractical for sensor networks, are in fact a viablepossibility. Using localization as an example, we show howaccurate results may be obtained by leveraging this capabilitywithout the use of specialized hardware or high configurationdetail; both of which are standard approaches to the problemwhen computation is at a premium. Specifically, we propose amathematical optimization-based framework for localizationbased on proximity constraints. Most variants of localizationcan be cast into this framework depending on the kindsof input available (e.g. ranging). We show accurate results,and exploit a technique from distributed optimization todivide the problem into pieces suitable for computation atthe master-level nodes. We conclude with remarks on thegeneral implications of this example for tiered systems, withpointers on how it is likely to be applicable to other problemssuch as power-aware routing.1I. INTRODUCTIONTiered sensor network architectures are a natural platformon which to build compute-intensive systems where thecomputational load is resident on the higher capability’master’ nodes, rather than the simpler impoverished sensornodes. Data fusion-based services such as localization,tracking, coverage, power-aware routing are all compute-intensive.The Tenet architecture [1] provides a vision of thelevel of support future sensor network deployments willenjoy. The basic idea is to have a large number of ’mote-class’ systems providing high density in sensing and asmaller number of ’master’ nodes with more powerfulradios and processors. This is clearly different from earlierapproaches [2] which thought in terms of large numbersof mote-class systems deployed in a ’flat’ manner. Tieredsystems are finding their way into field deployments. Asexamples consider the Great Duck Island [3] and the JamesReserve [4] deployments. In each case the number of1This work is supported in part by NSF grants CNS-0540420, CNS-0520305, CNS-0325875 and CCR-0120778master nodes is about 1-2 orders of magnitude smaller thanthe motes. Roughly, each master is ’responsible’ for 10-100motes.Tiered networks have several advantages: they are easierto program and debug [1] because there is very littleapplication logic in the mote-class system; they are easierto manage since there are few master-level nodes where thelogical complexity resides; they constrain network diameterto minimize wireless link loss [5]; there is evidence thatthey lead to longer lifetimes when the master nodes arecarefully placed [6]; Finally, and most importantly for us,tiered sensor networks are not limited by the processingavailable at each mote-class device, the master nodes docomputation on behalf of the impoverished nodes.Based on this background, we ask the following twoquestions.• Can one demonstrate that intensive computation atthe master nodes, coupled with extremely simpledata collection at sensor nodes, produces data-fusionperformance comparable to systems where the sensornodes have been outfitted with specialized sensinghardware, or carefully configured, yet have access torelatively poor computational resources ?• Are there convenient and efficient ways to distributeand manage computation across the master nodes ?We answer both questions in the affirmative, in thespecial yet representative case of localization. We alsosketch a preliminary example from power aware routingusing the same formulation. In sensor networks the focusis on developing lightweight computationally tractable al-gorithms for data-fusion services suitable for a collectionof computationally constrained nodes. In some cases, suchas localization, several approaches rely on the use ofspecialized hardware either for ranging [7], beacons [8], ora ’super-node’ which assists the nodes in the network forlocalization [9]. Other approaches carefully calibrate radiofrequencies [10] along with accurate time synchronizationto obtain accurate localization results.Inspired by the computation available in tiered systems,we propose an approach to localization which requiresno special hardware nor any configuration. The input toour system is strictly radio-based proximity. Based onthese proximity constraints, we propose a mathematicaloptimization-based framework for localization. Our resultsare accurate; and techniques from distributed optimizationare available to divide the problem into coarse piecessuitable for computation at the master-level nodes. Oursystem thus trades off computation to achieve localizationaccuracy with simple inputs.Having established the technical details for a specificproblem (localization), we argue that this result is promis-ing for data fusion-based services in general because itprovides evidence that compute intensive algorithms, oftenshunned as impractical for sensor networks, are in fact aviable possibility in tiered sensor networks. Specificallywe give arguments to show how other forms of localization(e.g. using ranging) are easily dealt with in our framework.We also give a rationale for how other data fusion servicessuch as power-aware routing could be implemented usingour formalism.In the next section we present a generic frameworkfor low level services in tiered networks distributed basedon mathematical optimization. In sectionIII, we give thetechnical details for proximity-based localization as anexample data fusion service which can be solved using ourframework. Following that we discuss generalizations toother data fusion problems. We conclude with a summaryand a sketch of ongoing and future work.II. GENERAL FRAMEWORKThis section describes the generic framework of our ap-proach. We give specific examples of formulations of local-ization