FREE ELECTRONIC LIBRARY - Abstract, dissertation, book

Pages:     | 1 | 2 || 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 3 ] --

In other words, by visiting the information server µ(σ, L(w, d)) directly, a consumer w is guaranteed to collect all sources that have information about data item σ within roughly distance 2d to itself. If the consumer only wants to know the number of such sources (range counting), it can simply return. Otherwise, if it wishes to report all such data (range reporting), it can then route to each of these sources and fetch the data.

Hash function µ(σ, L) We still have to define the hash function µ(σ, L) that maps any given data item σ to an information server in a particular cluster L.

Ideally, in order to have a good load balance, this function should distribute the information servers uniformly to all nodes contained in L for various σ ∈ Σ.

One possible choice of this function is deployed in the GLS approach, where each sensor node in the sensor network has a unique id (an integer). Given an data item σ ∈ Σ, assume there is a function that maps σ to one of this id, say IDσ, randomly. The information server µ(σ, L) is then defined as the node s ∈ L with smallest id that is greater than IDσ. However, in order to identify and reach node s, one has to build extra structure (which needs about O(h log n) bits per-node memory) on top of whatever routing structure exploited.

A simpler way to define µ(σ, L) is to use σ as the seed of some pseudorandom function and traverse the HD tree downward randomly according to that function. µ(σ, L) is then defined as the leaf node reached in the process.

Note that this definition of µ(σ, L) also gives a routing path to access it. We can first route to any node in L, using σ to determine the pseudo-random subcluster L of L that contains µ(σ, L), then recursively route toward µ(σ, L ) = µ(σ, L).

The number of hops to route from any node in L to µ(σ, L) is obviously bounded d by i=1 α · 2i ≤ α · 2d+1.

Robustness The routing components of our information brokerage scheme inherit the robustness properties of the routing scheme; in particular, messages that are unable to make progress due to node or link failures can recover by simple local rules and be eventually forwarded to their destinations. Furthermore, recovery after failure of an information server is possible by querying the information server one level higher, incurring only a constant factor overhead.

3 Experimental Results We implemented the discrete center hierarchy in java to experimentally evaluate the performance of our proposed schemes. Currently our implementation simulates the network at the graph level only. While it does not mimic network attributes like packet loss or delay, we are quite confident that the results reported here give a good indication about the usefulness of our approach in practical scenarios.

3.1 Data Generation and Implemented Algorithms All our measurements were carried out on a unit disk graph of nodes that were spread uniformly at random in a unit square, and subsequently nodes may have been removed to simulate the presence of large holes in the network topology.

Note that this “unit disk graph” is not required in our approach—our system can take an arbitrary graph as input. We also want to emphasize that in this model, as long as the average node degree is below about 10, a large fraction of the unit disk graph is not connected, and the dilation factor is rather large, i.e. the shortest path in the graph between two nodes is much larger than their Euclidean distance. This is quite different in the ‘skewed grid’ model where the node positions are determined by randomly perturbing points on a grid by some rather small amount. There the unit-disk graph is almost always connected for any grid-width slightly smaller than 1 (which corresponds to an average degree of 4 or more) and the geometric dilation is very small. See Figure 2 for an example.

While our scheme performs much better in the skewed grid model as compared to the random model, we feel the latter provide more insight on realistic scenarios, and present all our results in this random model.

Fig. 2: Random sensor field (left) has degree 6.26 and has many holes, some of which are quite large. Skewed grid field (right) has lower degree, 5.18, yet is much more regular.

In the following subsections, we compare our routing scheme with GPSR, and our information brokerage scheme with GHT by assuming that the geographic locations of sensors are known (although not used in our approach).

The underlying planar graph for GPSR is the Gabriel graph.

3.2 Evaluation of Routing Strategies

Routing quality. In the first experiment we evaluate the quality of the paths produced by our routing scheme. We fix a sensor field of 2000 nodes and vary the average degree from roughly 6 to 12. We then select at random 1000 pairs of nodes from the largest connected component of the sensor field. We compute the paths between the nodes in these pairs using the HD as well as using GPSR.

For each of such path, its quality is defined as the ratio between its length and the shortest distance between its two endpoints. We show in Table 1 (a) the average and standard deviation of the quality of these 1000 paths. Note that our HD routing scheme always produces near-optimal paths regardless of the node density. The practical constant is much better than the worst case bound of 4 we could prove.

–  –  –

Fig. 3: (a) The storage required growths slowly when the network becomes large. (b) The success rate of routing vs. node depletion for sensor fields with various average degree. (c) Number of hops to information server using HD and number of hops in a shortest path to an ideally random information server.

We note that the cost of initializing the network, i.e., the number of messages sent to establish our hierarchical decomposition, is directly proportional to the storage at each node. As the storage cost is low, the cost of network initialization is also low.

Hot spots. Even though our implementation of the HD uses cluster heads, they are not special nodes in the network In a typical route, the moment a package heading towards a cluster reaches any of its nodes, the package starts heading towards a different cluster. So these cluster heads do not form a backbone structure, nor do they create bottlenecks in network traffic. Figure 4 (c) gives an example where two routes with nearby sources and destination nodes stay separate during their course. On the other hand, when large holes are present in the network, nodes close to holes will naturally have a heavier burden, as our HD paths approximate the shortest paths well. Still, our paths do not hug the holes in the sensor net as tightly as GPSR paths do, as shown in Figure 4 (a) and (b) for a sensor field with 2000 nodes and average degree 9.5. Our HD scheme produces many fewer higher load nodes (larger dots in the picture).

Robustness. To measure the performance of our routing scheme under node depletions, we start with a graph with average degree of 7, 8, 9, or 12, build the HD routing structure on top of it, and then randomly remove a small percentage of sensors (from 2% to 20%) from the sensor field. We then pick 1000 pairs of live nodes at random, and show the success rate of routing between these pairs in Figure 3 (b). During the routing process, if a node finds that the next sensor on its shortest path to some cluster L is dead, it locally floods a neighborhood of nodes at most 5 hops away from itself to find a node with smaller distance to (a) (b) (c) Fig. 4: Hotspots comparisons for (a) GPSR and (b) HD scheme. Larger dots are nodes with higher traffic loads. In (c), two paths generated by HD scheme with nearby sources and destinations.

L. The result shows that the performance is gracefully degraded when the node failure rate increases.

3.3 Evaluation of the Information Brokerage Scheme Brokerage quality. The efficiency of a brokerage system includes both the number of messages (i.e., # information servers) that a producer needs to replicate, and the number of hops that a consumer needs to access before locating the data it needs (i.e., the query time). In Table 1 (b), we vary the size of the sensor field from 200 to 10, 000 nodes. For each sensor field, we randomly choose 1, 000 producer/consumer pairs, with each pair producing/requesting a random data item. Columns 2,3 show the average number and standard deviation of information servers for each producer. Columns 4 and 5 show the quality of the path from the consumer to the information server, defined as the ratio between query time using our scheme (i.e., the path length to the respective information server) and the shortest hop distance between the producer and the consumer.

We see from the table that this ratio is always close to 1.0 (in fact, in most cases it is smaller than 1.0, since the information server can be even closer than the producer). If the data is large, the producers may not replicate their data and only leave their addresses at the information servers. In that case, a consumer after locating the desired information server must further route to the producers to get the data itself. The quality of the brokerage path is then defined as the ratio between the path length from the consumer to the producer obtained using our scheme over the shortest path length between the consumer and producer.

Column 6 and 7 in Table 1 (b) show this ratio in our experiment. In all cases, it is always small, around 2.0.

While the number of replications used by a particular producer is higher in our system than in the GHT approach, the query time can be much smaller, especially when the consumer is closer to the producer. This phenomenon is illustrated in Figure 3 (c), where we compare the query time in our scheme (lower curve) with the length of the shortest path to an ideally random information server (upper curve). Note that the latter is in fact a lower bound of the query time for any scheme using GHT for information brokerage. The query time for GHT using GPSR as the underlying routing scheme may be much longer than this shortest path, due to the path quality returned by GPSR. In short, our system is attractive for scenarios where there are multiple queries for the same data, as the overhead for the producer is then amortized.

It is also important to keep the distribution of information servers for different data items as uniform as possible. To test this, we let each sensor in the network produce a different data item, and record for each node the number of times that it serves as an information server for some data item. The results are in Table 2.

The distribution of information servers observed is reasonably good compared to a distribution obtained by a centralized uniformly random hash function.

–  –  –

Table 2: The average/standard deviation of the number of times that a sensor serves as an information server for some data item for various network sizes.

Approximate range counting. One important application of our information brokerage system is for approximate range counting, such as reporting all horses detected within some distance r from a particular sensor. When r is quite small, flooding is simple and effective. However, the number of nodes accessed in the flooding approach increases quadratically as r increases. This is illustrated in Figure 5 (a) where the query cost in our approach (lower curve) increase in a linear manner, while that for flooding (upper curve) increases quadratically. The size of the sensor field in this example is 2, 000 with an average degree of 6.1.

–  –  –

Fig. 5: (a) Approximate query cost is very low compared to the naive flooding. (b) The success rate of information brokerage under nodes depletions.

Robustness. Again, we fix a sensor field of 2000 nodes with various average degree, compute the HD routing structure, and remove a portion of sensors randomly (from 2% to 20%) from the field. We then randomly choose a set of producer/consumer pair, each generating/seeking a random data item. The resulting success rates are shown in Figure 5 (b). The brokerage system is slightly more robust than the routing scheme, which is not surprising: as the robustness of our information brokerage system comes partly from the robustness of the routing scheme, and partly from the fact that even if a query fails to route to a particular information server, it can simply go to the information server one level up.

4 Conclusion and Discussion

In this paper we have presented a unified framework for efficient routing and distance-sensitive information brokerage based on augmented hierarchical decompositions of communication graphs. In particular, for communication graphs of constant doubling dimensions, the guarantee for almost optimal routing paths comes at an additional cost of only O(log n) bits of storage per network node.

Our routing scheme does not rely on a dedicated backbone or hub structure, and hence performs rather well when some network nodes fail while providing a natural load balance between routing paths.

Our novel distance-sensitive information brokerage scheme is built based on the above routing scheme. We showed how information producers can diffuse pointers to their information to O(log n) other locations and in turn how information consumer can exploit this stored data to retrieve the information they want in a distant sensitive manner. As an application, our brokerage infrastructure allows for range queries with specified radius that take time proportional to the radius instead of time proportional to the area of the relevant range region.

All our procedures come with rigorous proofs of their worst-case performance guarantees, and the experimental results for both routing and information brokerage show considerably better performance than the worst case considerations in the theoretical analysis, (but the latter in some way explain this good behavior in practice).

Pages:     | 1 | 2 || 4 |

Similar works:

«AUSWIRKUNGEN DER SCHULDENBREMSE AUF DIE HAUSHALTE AUSGEWÄHLTER BUNDESLÄNDER UND IHRER GEMEINDEN Expertise im Auftrag von ver.di · von Dieter Vesper Bund+ Länder und Gemeinden AUSWIRKUNGEN DER SCHULDENBREMSE AUF DIE HAUSHALTE AUSGEWÄHLTER BUNDESLÄNDER UND IHRER GEMEINDEN Expertise im Auftrag von ver.di · von Dieter Vesper Bund+ Länder und Gemeinden Herausgeber: ver.di – Vereinte Dienstleistungsgewerkschaft, Paula-Thiede-Ufer 10, 10179 Berlin V.i.S.d.P. Achim Meerkamp, Mitglied des...»

«Access to Air Travel for Disabled People: 2005 Monitoring study by Jo Sentinella PPR 139 PPAD 9/72/90 PUBLISHED PROJECT REPORT TRL PUBLISHED PROJECT REPORT PPR 139 ACCESS TO AIR TRAVEL FOR DISABLED PEOPLE: 2005 MONITORING STUDY Version: Final by J Sentinella (TRL) Prepared for: Project Record: PPAD 9/72/90 Benchmarking and Monitoring Air Travel for Disabled People Client: Mobility and Inclusion Unit, Department for Transport Copyright TRL Limited July 2006 This report has been prepared for...»

«67 Lesson Plans: Travel Isabelle Chou 0. Background A. Description of the program C. Description of the course This unit was designed for use in a private Reading and Writing 2 is an intermediate language institute in Taiwan. The program level course in the program designed to enoffers nonacademic EFL classes for adult hance student vocabulary, reading comprelearners to improve their English profihension skills, and writing skills. Classes ciency in different skill areas. meet twice a week for...»

«America’s Favorite TV Shows (America has bad taste) Friends Which character had a twin? Phoebe Which of the friends dated Rachel? Ross, Joey Who of the following did not guest star on the show? Circle your answers. Ralph Lauren Winona Ryder Sarah Jessica Parker Ben Stiller RuPaul Brad Pitt Why did Ross get divorced from his first wife? She is a lesbian Where does Phoebe’s boyfriend David move to in the first season? Minsk Who was Rachel’s prom date? Chip On which daytime drama does Joey...»

«Ferguson, John Urquhart (2011) Mutually reinforcing systems. PhD thesis. http://theses.gla.ac.uk/2760/ Copyright and moral rights for this thesis are retained by the author A copy can be downloaded for personal non-commercial research or study, without prior permission or charge This thesis cannot be reproduced or quoted extensively from without first obtaining permission in writing from the Author The content must not be changed in any way or sold commercially in any format or medium without...»

«SOURCES ON THE ARMENIAN GENOCIDE AT THE UCLA RESEARCH LIBRARY: A Partial List Prepared by Gia Aivazian PRIMARY SOURCES Government Archives. Governments that had a relationship with the Ottoman Empire in the late 19th century and early 20th century such as Great Britain, France, Russia, Germany and the United States, have extensive archives consisting of official and unofficial reports(consular, church, organizational, individual), various types of correspondence, eyewitness accounts, etc. about...»

«Umweltforschungsplan des Bundesministeriums für Umwelt, Naturschutz und Reaktorsicherheit FuE-Vorhaben 202 91 601 Anforderungsanalyse der Nutzung von satellitenbasierten Erdbeobachtungssystemen für die Umweltpolitik (SATUM) Kurzfassung des Endberichts Projektverantwortung Bernd Beule* Projektleitung Robert Backhaus** Mitarbeit Michael Bittner**, Michael Bock**, Erik Borg**, Peter Gege**, Thomas Holzer-Popp**, Martina Kästner**, Manfred Keil**, Christian Lemm, Andreas Neumann**, Eleni...»

«Dr. Gerald Hühner Vorschlag für eine doppelte Unterrichtsstunde Im Rahmen der Abiturvorbereitung, Fach Deutsch Literatur (NEV) Die Ausarbeitung des Arbeitsvorschlags erfolgt im Rahmen eines Konzepts: Literatur als Kristallisationspunkt unterrichtspraktischer DaF-Arbeit. Unabhängig von der Relevanz des Themas für das Abitur in Slowenien, kann der hier unterbreitete Vorschlag im Kontext des Deutsch-/DSDUnterrichts auch länderübergreifend Ausgangspunkt einer auch längeren...»

«Würzburger UNTERSTÜTZER JungChemikerForum Chem-SyStM Chemie-Symposium der Studierenden Mainfrankens Vernetze dein Wissen! Abstractband 07. Dezember 2010 www.jcf-wuerzburg.de INHALTSVERZEICHNIS Inhalt des Abstractbandes  Grußwort  Unterstützer  Abstracts der Arbeitskreise  Vortragende Appetithäppchen  Abstracts der Teilnehmer  Teilnehmerliste nach Fachbereichen aufgeschlüsselt  Notizen  Programm (Rückseite) Organisationskomitee Matthias Beyer, Nicolas Brockmann,...»

«Ancient Egypt: The Light of the World by Gerald Massey Ancient Egypt: The Light of the World A Work of Reclamation and Restitution in Twelve Books by Gerald Massey London T.Fisher Unwin Adelphi Terrace Published in 1907 EDITION LIMITED TO FIVE HUNDRED COPIES AUTHOR OF A BOOK OF THE BEGINNINGS and THE NATURAL GENESIS It mav have been a Million years ago The Light was kindled in the Old Dark Land Withi which the illumined Scrolls are all aglow, That Egypt gave us with her mummied hand : This was...»

«DISS. ETH Nr. 17693 Ökonomische Analyse agrarpolitischer Umweltmassnahmen unter Verwendung eines biophysikalischen Modellansatzes ABHANDLUNG zur Erlangung des Titels DOKTOR DER WISSENSCHAFTEN der ETH ZÜRICH vorgelegt von MARTIN BRUGGER Dipl. Ing.-Agr. ETH geboren am 24. Januar 1960 von Birwinken TG Angenommen auf Antrag von Prof. Bernard Lehmann PD Dr. Daniel Schaub Zusammenfassung Zusammenfassung Die Situation vieler landwirtschaftlicher Betriebe im Schweizer Mittelland ist geprägt durch...»

«5th WORLD PIANO CONFERENCE June 27 to July 03, 2013, Novi Sad, Serbia iedrich Fr sche drich Nietz Frie etzsche Ni.this is why souls that are over come with happiness generally feel more grateful to music than others and better ones do: for they see and hear through music, as through a coloured mist, their love becoming, as it were, more distant, more touching, and less heavy. Music is the only means that such people have of observing their extraordinary condition and of becoming aware of its...»

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