Contour Approximation in Sensor NetworksChiranjeeb Buragohain1, Sorabh Gandhi1,John Hershberger2, and Subhash Suri11Dept. of Computer Science, University of California, Santa Barbara, CA 93106?{chiran,sorabh,suri}@cs.ucsb.edu2Mentor Graphics Corp., 8005 SW Boeckman Road, Wilsonville, OR [email protected]. We propose a distributed scheme called Adaptive-Group-Merge for sensor networks that, given a parameter k, approximates ageometric shape by a k-vertex polygon. The algorithm is well suited tothe distributed computing architecture of sensor networks, and we provethat its approximation quality is within a constant factor of the optimal.We also show through simulation that our scheme outperforms severalother alternatives in preserving important shape features, and achievesapproximation quality almost as good as the optimal, centralized scheme.Because many applications of sensor networks involve observations andmonitoring of physical phenomena, the ability to represent complex geo-metric shapes faithfully but using small memory is vital in many settings.1 IntroductionWe consider the problem of approximating polygonal paths and cycles in thecontext of a sensor network. The problem of representing complex geometricshapes using small memory is fundamental in many sensor net applications:sensor networks observe, measure, and track physical phenomena, which ofteninvolves representing and communicating a geometric shape. The problem arises,for example, in the application of computing contour lines on a field of sensormeasurements [8]. Suppose that a geographically distributed set of sensors mea-sures some physical parameter, say temperature, that varies smoothly over thesensor region. An analyst is interested in the rough shape of the temperature dis-tribution, but does not care about the exact values measured by all the sensors.A collection of isocontours—cycles along which the measured and interpolatedsensor values are constant—can be a useful summary of the distribution.Contour lines reduce the data to be reported from two dimensions (the full setof sensors) to one dimension (dependent on only those sensors near the contour).However, even this reduction may not be enough. Communication is arguablythe most important resource in a sensor net, and a one-dimensional contourwhose feature size depends on the spacing of the sensors may contain too much?The research of C. Buragohain, S. Gandhi and S. Suri was supported by grants fromthe National Science Foundation (CCF-0514738) and Army Research Organization(DAAD19-03D0004).data to send through the network back to the analyst. Therefore, it is importantto consider methods for simplifying a one-dimensional contour that approximatethe original data well and can be computed by a distributed network.We use “contour approximation” as a guiding application, but our treat-ment of the problem is at an abstract level: distributed algorithms to compute abounded-memory approximation of a polygonal curve embedded in a sensor field.Because sensor networks are envisioned as distributed “spatial instruments” thattake measurements in a physical space but have limited resources (bandwidth,power, etc.), the ability to represent complex geometric shapes faithfully but us-ing small memory is vital to sensor networks. In particular, significant improve-ment in system lifetime is possible if the network performs local computation tobuild compact approximations instead of sending the entire raw data to a cen-tralized location. Indeed, a number of techniques have been proposed recentlyfor “in-network aggregation” of sensor data [8, 12, 16]. The focus of these papersis on numerical summaries, such as min, max, average, or median, while themain focus of our paper is a fundamental form of spatial summary. Imagine, forinstance, a physical phenomenon, such as a structural fault, that is evolving withtime, and an analyst who wants to receive a periodic snapshot of the generalshape of the phenomenon. Another possible application is building a compactrepresentation of the boundary of the entire sensor field, which can be broadcastefficiently throughout the network so that each node knows the overall geograph-ical coverage of the system. Awareness of the sensor field’s shape can be useful indata storage schemes like Geographical Hash Tables (GHT) that associate datawith geometric locations.The problem of contour approximation was considered by Hellerstein et al. [8]in a sensor net setting. They proposed an algorithm in which a contour is initiallyapproximated by its axis-aligned bounding box, and then the approximation issuccessively refined. At each step the approximate polygon encloses the origi-nal contour. Each refinement step deletes from the current approximation themaximum-area rectangular notch that lies outside the original contour. The re-finement stops when the approximating polygon reaches some target complexity(number of vertices). This approach, while a useful heuristic, has several liabili-ties: (1) the restriction to rectangular approximation imposes an axis-dependencewhere none is required by the data; (2) the greedy maximization of area removedat each step does not ensure that the approximating polygon is near the origi-nal; and (3) the algorithm is a heuristic, with no proof of approximation quality.In [17], Singh, Bakshi, and Prasanna consider the problem of producing topo-graphic maps over a sensor field using a quadtree-based approach, but they donot focus on constructing a compact representation of the map.Approximating polygons is a fundamental problem that has been consideredin many fields, including geographic information systems (GIS), computer vision,and computational geometry. In these settings the computational model favorscentralized computation, in which all the input data are available to a singlecomputational engine. Performance is measured in terms of approximation qual-ity (in any of a variety of metrics) and running time/memory usage as a functionof the input size n and the output size k. Typical algorithms include dynamicprogramming (which can optimize most metrics in roughly O(n2k) time [10,Chapter 3]) and the Douglas–Peucker algorithm (which provides good practicalapproximation quality in O(n log n) time [4, 9]). Because of the centralized com-putation requirement, however, these algorithms are ill-suited for use in a sensornet setting without significant adaptation.Our ContributionWe make the