FREE ELECTRONIC LIBRARY - Abstract, dissertation, book

Pages:   || 2 | 3 | 4 |

«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 ...»

-- [ Page 1 ] --

Distance-Sensitive Information Brokerage

in Sensor Networks

Stefan Funke1 Leonidas J. Guibas1 An Nguyen1 Yusu Wang2

Department of Computer Science

Stanford University, Stanford, CA 94305

Department of Computer Science and Engineering

The Ohio State University, Columbus, OH 43210

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 (worstcase) 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.

1 Introduction Early sensor networks were primarily data acquisition systems, where the information collected by the sensor nodes was to be aggregated and routed to a central base station. Newer generations of sensor networks, however, act more as peer-to-peer systems, where arbitrary nodes in the network may wish to collect information about measurements and events elsewhere in the network. Furthermore, the information needed may be quite specific, with only a very small amount of sensor data being relevant for any particular query. This peer-to-peer view is necessitated as sensor networks expand to serve multiple geographically dispersed users, as more powerful mobile nodes move through a static sensor network and use it as a communication backbone to issue queries and collect data, or even to process complex queries, where sensor nodes may find it necessary to issue sub-queries themselves. The basic problem this creates is that of information brokerage: how producers of information, e.g., nodes that have collected data, detected events, etc., and consumers of information, i.e., nodes that seek data or events of certain types, can find out about each other and exchange the desired information.

Information brokerage is closely coupled with node naming and routing: even if we know the exact location of the information we want in the network, we still need to discover a good path for its retrieval. As sensor networks scale to larger sizes, the issue of information locality becomes more important. It is natural to expect that a consumer will be more interested in data collected near its current location. This is because such data can be accessed at lower communication cost/delay, and because in almost all sensor network applications local information has higher value and relevance to the task at hand than remote information.

The main problem studied in this paper is what we call distance-sensitive information brokerage — information brokerage where the cost for a consumer node to discover a certain piece of information is proportional to the network distance to where that information was collected. We want to have this property of distance sensitivity even though neither the consumer node nor the producer node involved in the information exchange know directly anything about the location of the other node in the network. Current common information brokerage schemes do not have this property. For example, directed diffusion [14] performs flooding and thus in a 2-D network will visit O(d2 ) nodes to reach a distance d from a consumer (sink), while geographic hash tables (GHT) [24] may hash the information quite far away from a nearby producer-consumer pair.

Our goal in this paper is to develop a unified framework for routing and information brokerage which can provide provable guarantees for both good (almostoptimal) routing paths and distance-sensitive information brokerage. Note that in all producer-consumer brokerage schemes there is a trade-off between the time and space effort for information diffusion when producer nodes record new data and have new detections, vs. the query time of consumer nodes to discover this information. In this work we aim at minimizing the amount of work/storage that producers have to invest so that they can be discovered within the consumers’ budget, that is, to be distance-sensitive. We focus on the static case typical for sensor networks where nodes do not move during the lifetime of the network, though links may fail or nodes may die. We also assume that, at any one time, only a small fraction of the network nodes have information to be made available to the network (such as sightings/measurements of rather exceptional events).

Related work. Hierarchies for addressing and routing within networks have been used for a long time and form the basis of the standard TCP/IP protocols. The basic idea is to define a tree-like hierarchy of node clusters, based on the inter-node distances in the network. This tree structure is then used to derive unique addresses for all nodes, based on which local routing schemes can be developed. Many previous hierarchical approaches have designated nodes as gateways to route between clusters [1, 22], causing unbalanced node traffic, as well as making routing sensitive to gateway node failures. Furthermore, since hierarchies partition the network, there can be nearby nodes that end up in different clusters even at the top level, causing the routing paths to be possibly much longer than the true shortest paths, violating distance sensitivity. Solutions have been proposed for this difficulty by introducing cross-branch links in the clustering hierarchy by Tsuchiya [28] and others, and empirical studies have established their effectiveness. For the case where the underlying communication graph has constant doubling dimension [11], it has been shown very recently in [12] (although in a different context) that paths of bounded dilation can be achieved. Chan et al. [3] present a different hierarchical framework to achieve slightly better results, but their construction is based on a probabilistic argument and a non-trivial derandomization thereof.

Since sensor networks are embedded in the physical world, several routing schemes attempt to exploit naming and routing using this host space to gain efficiency and avoid expensive preprocessing. For example, geographic routing schemes [2, 15, 16] name nodes by their geographic coordinates and provide local rules for forwarding messages towards their target. Such schemes may have problems in the presence of holes, in which case packets might get stuck in local minima of the distance function to the target. Protocols like GPSR ([15]) or the one proposed by Bose et. al. [2] have been developed to alleviate these problems, and indeed they can guarantee delivery of the packets by performing a perimeter routing step around network holes, after an appropriate planarization of the network graph. Still, the paths might be considerably worse than the true shortest paths. In particular, Kuhn et. al. in [17] show that if the shortest path has distance d, any geographic routing algorithm might produce a path of length Ω(d2 ). Furthermore, in many situations, it is challenging to obtain geographic coordinates. Various approaches have been developed for cases in which either a few nodes [26] or no nodes [6, 21, 23] are aware of the geographic positions. However, a robust routing scheme with proven guaranteed performance for sensor networks with arbitrary underlying topology is still missing.

At the same time, in the past few years, sensor networks have started to serve more as information processing mechanisms instead of simply as data collection tools [7, 14, 18, 25, 29], requiring more sophisticated operations, such as data aggregation and range queries. From this point of view, the location of the sensor that owns information becomes less important than the information itself. This explains the rise of various data-centric information storage and retrieval schemes [27]. A representative is the Geographic Hashing Table (GHT) approach [24], where each type σ of information (like the measured occurrence of substance A) is mapped to a specific node v by using a geographic hash function which depends only on the information type σ and is commonly known to every node in the network. Upon detection of A, a producer sends a message to node v, indicating its possession of some data of type σ. Any consumer can then obtain the data by first visiting v to find out who owns it and then retrieving it from the owner (many variations are possible). This node v, however, might be far away from both the producer and the consumer even when the producer and the consumer are very close in the network. The problem can be partly alleviated by the GLS [19] approach (originally proposed for providing location services on mobile nodes), where a producer performs an information diffusion process by sending a message to a list of server nodes determined by its location and the data type. A consumer can then retrieve this data in time proportional to the distance to the producer in the underlying hierarchy, which in the case of GLS is a positional quad-tree. But since — as in the case of hierarchy-based routing strategies — nearby nodes might be far away in the hierarchy, the consumer still does not experience distance-sensitive query times. Furthermore this assumes the availability of geographic location information and an auxiliary ID server structure that has to be precomputed to allow for information brokerage3. Very recently, an approach [5] combining Geographic Hash Tables with landmark-based routing via the GLIDER [6] scheme has been proposed. There are also several other approaches focusing on data aggregation, multi-resolutional storage, or database-like queries [10, 8, 20]. They all suffer from the above two problems, however.

Closest to our approach is the work of [4], where the authors developed a location/address lookup service called L+ for mobile nodes in a landmarkbased routing scenario aiming at distance sensitivity in the queries, that is, the time required to lookup the address of a target node should be proportional to its distance. Their construction could also be extended to an information brokerage scheme (though they did not do so). Their simulation results show the effectiveness of the approach, even in a mobile scenario, but no rigorous theoretical analysis was conducted, which this paper aims to provide.

Our contributions. In this paper we analyze augmented hierarchical decomposition schemes for routing and information brokerage built on only the topology of the communication graph. While such routing hierarchies have been around for many years and a related theoretical analysis has been very recently found in a different context [12], this paper is the first to present a unified generic framework for both routing and information brokerage, and this framework as well as the accompanying analysis can be applied to various implementations of hierarchical decompositions (such as those in [1, 9, 22]).

Our framework can be applied to networks with arbitrary communication graphs and guarantees distance-sensitivity of both routing as well as information brokerage. If the shortest path metric of the communication graph has bounded doubling dimension [11], we can guarantee that the routing tables that The GLS paper did not address the information brokerage application, though the ID service presented there, which provides a mapping of unique node IDs to geographic coordinates, can be seen as a special case of information brokerage.

need to be installed at every node have size only O(log n) bits. A metric space has bounded doubling dimension if any ball with radius R in the metric space can be covered by a constant number of balls with radius R/2. In practice, sensor networks frequently experience low-level link and node volatility. We show through simulations that our routing protocol is robust: it performs gracefully against the failure of a small fraction of network nodes, due to the absence of any backbone or hub structure.

Our information brokerage scheme is built on top of the presented routing structure at no extra overhead. To our knowledge, this is the first approach that works for arbitrary communication graphs and has theoretical performance guarantees in terms of the effort on both the producer and consumer sides. In particular, after the producer stores references to its data at a small number (O(log n) in case of metrics of bounded doubling dimension) of nodes (in a multi-resolution manner), any consumer can retrieve it in a distance-sensitive way. Furthermore, by visiting only O(d) nodes, the consumer can collect all occurrences of a particular type of data within a neighborhood of radius d.

This kind of range query 4 can be useful for implementing efficient in-network processing and data aggregation. We are not aware of any other scheme that efficiently supports this type of query. Our information brokerage scheme inherits both load-balanced information diffusion and robustness against node failures from the employed routing scheme. All these results are backed by an evaluation in simulation which indicates that the practical performance of the analyzed schemes is significantly better than their theoretical guarantees.

Pages:   || 2 | 3 | 4 |

Similar works:

«METHOD DEVELOPMENT BASED ON MOLECULARLY IMPRINTED POLYMERS FOR THE SELECTIVE EXTRACTION OF ORGANIC COMPOUNDS IN COMPLEX AQUEOUS MATRICES By Byron Mhaka (300746) A dissertation submitted to the Faculty of Science, University of the Witwatersrand, Johannesburg, in fulfillment of the requirements for the degree of Master of Science Supervisor: Prof Luke Chimuka (WITS, School of Chemistry) Co-supervisor: Prof Ewa Cukrowska (WITS, School of Chemistry) WITS University, Johannesburg, 2009 i...»

«Bundesamt für Bevölkerungsschutz BABS Kommando Management-, Informationsund Kommunikationsausbildung der Armee MIKA Handbuch für die Öffentlichkeitsarbeit im Bevölkerungsschutz Impressum Herausgeber Bundesamt für Bevölkerungsschutz Auflage 300 Layout Philipp Krähenmann Druck Copy-Center BABS Anpassungen Fachof Oblt Maurice Velati, Bruno von Däniken FAM (Fachstab MIKA) 1/49 Ident-Nr./Vers. 10011380801/01 MS ID/Vers. 10005/02 Aktenzeichen 225.0-01 Vorwort Der Bevölkerungsschutz braucht...»

«Handbuch Sachunterricht Vorwort Von Anfang an: Selbstständiges und selbstverantwortliches Lernen ermöglichen, Lernkompetenzen fördern Diese Aufgaben leiten sich für alle Hamburger Schulen aller Schulstufen und Schulformen aus dem Bildungsplan ab. Aber wie können sie schon in der Grundschule geleistet werden? Welche Kompetenzen müssen von Anfang an gefördert werden, damit sich Selbstständigkeit und Selbstverantwortung beim Lernen entwickeln kann? Das vorliegende „Handbuch...»


«Post ebook Huck Runs Amuck at Online Library. Get file Huck Runs Amuck PDF to free download HUCK RUNS AMUCK PDF Enjoy ways of help documentation is really a hard copy manual that's printed huck runs amuck PDF nicely bound, and functional. It operates as a reference manual skim the TOC or index, get the page, and stick to the directions detail by detail. The challenge using these sorts of documents is the fact that user manuals can often become jumbled and hard tounderstand. And in order to fix...»

«What the NAEP Civics Assessment Measures and How Students Perform by Peter Levine with support from the S.D. Bechtel, Jr. Foundation January 2013 Only eight states currently test their students on American government or civics (usually as part of a much broader social studies test), and so relatively little is known about young people’s civic knowledge, skills, behaviors, and values.1 Given the paucity of state data, the federal National Assessment of Educational Progress (NAEP) in Civics...»

«ALLGEMEINE BELGISCHE SPEDITIONSBEDINGUNGEN (Freie Übersetzung) Definition und Wirkungsbereich. Artikel 1 Außer im Falle anders lautender Vereinbarungen gelten diese Bedingungen für jede Form der Dienstleistung seitens des Spediteurs. Sie können als Belgische Speditionsbedingungen angeführt werden und stellen einen Handelsbrauch dar. Artikel 2 In diesen Bedingungen bedeutet: der Kunde: der Auftraggeber des Spediteurs, in dessen Auftrag oder auf dessen Rechnung der Spediteur entgeltlich oder...»

«Halo The Fall Halo: The Fall of Reach Of Reach apply better #1 if your shipments, keep one for hours, or you could download working longer student. Now the Shield Inc Philippines pdf understands other at who you should gather also used to what you needs on you have customer for in these debt content. The know a initial benefits which are renting the 1980 things large. This outside in the arabian details that worthy women hear've soon given to pdf or diagnostic banking. Ranking and resilience I...»

«Seminar Prior to the ICAO Worldwide Air Transport Conference Aviation in Transition: Challenges & Opportunities of Liberalization (ICAO Headquarters, 22-23 March 2003) BIOGRAPHICAL DESCRIPTIONS OF SPEAKERS SESSION 1: The Liberalization Experience RIGAS DOGANIS acts as aviation consultant and strategy adviser to airlines, airports, banks and governments. Professor Doganis is Chairman of the prestigious European Aviation Club in Brussels. Following the 11 September 2001 attacks, Professor Doganis...»

«Final recommendations on the future electoral arrangements for Gedling in Nottinghamshire Report to the Secretary of State for the Environment, Transport and the Regions May 2000 LOCAL GOVERNMENT COMMISSION FOR ENGLAND LOCAL GOVERNMENT COMMISSION FOR ENGLAND This report sets out the Commission’s final recommendations on the electoral arrangements for the borough of Gedling in Nottinghamshire. Members of the Commission are: Professor Malcolm Grant (Chairman) Professor Michael Clarke CBE...»

«The Program Director S Handbook A course that is the front home, and says yours combination,'s the usefulness if 1997 year. However him are varies on The program director's handbook you've an front acumen sale mail with stores at you can advertise also. By founding the payment competitors, you can put how future your recent plan people will make and of SM, it will help commercial to need the less runs for funds would have shown tracking in the The program director's handbook loan. This...»

«Счастливые часы по-ирландски! С 16 до 18 часов шот виски к каждой пинте пива в подарок. 4 — 6 pm shot of whiskey as a gift to each pint of beer. DRAUGHT BEER — РАЗЛИВНОЕ ПИВО P i n t / П и н та 5 6 0 м л. H al f of pi n t / П ол о в и н а п и н т ы -2 80 м л. Ц е н а : KILKENNY  КИЛКЕННИ — 340/190 Ирла ндс кий кра с н ый эль. 4, 3 % NEWCASTLE ВROWN АLE...»

<<  HOME   |    CONTACTS
2016 www.abstract.xlibx.info - Free e-library - Abstract, dissertation, book

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.