A classic experiment by Milgram shows that individuals can route messages along short paths in social networks, given only simple categorical information about recipients (such as "he is a prominent lawyer in Boston" or "she is a Freshman sociology major at Harvard"). That is, these networks have very short paths between pairs of nodes (the so-called small-world phenomenon); moreover, participants are able to route messages along these paths even though each person is only aware of a small part of the network topology. Some sociologists conjecture that participants in such scenarios use a greedy routing strategy in which they forward messages to acquaintances that have more categories in common with the recipient than they do, and similar strategies have recently been proposed for routing messages in dynamic ad-hoc networks of mobile devices. In this paper, we introduce a network property called membership dimension, which characterizes the cognitive load required to maintain relationships between participants and categories in a social network. We show that any connected network has a system of categories that will support greedy routing, but that these categories can be made to have small membership dimension if and only if the underlying network exhibits the small-world phenomenon.
Abstract : Digital packet networking technology is spreading rapidly into the commercial sector. Currently, most networks are isolated local area networks. This isolation is counterproductive. Within the next twenty years it should be possible to connect these networks to one another via a vast inter network. A metropolitan inter network must be capable of connecting many thousand networks and a national one several million. It is difficult to extend current inter networking technology to this scale. Problems include routing and host mobility. This report addressed these problems by developing an algorithm that retains robustness and has desirable commercial characteristics. For many years, scalable routing for wireless communication systems was a compelling but elusive goal. Recently, several routing algorithms that exploit geographic information (e.g. GPSR) have been proposed to achieve this goal. These algorithms refer to nodes by their location, not address, and use those coordinates to route greedily, when possible, towards the destination. However, there are many situations where location information is not available at the nodes, and so geographic methods cannot be used. In this paper we define a scalable coordinate-based routing algorithm that does not rely on location information, and thus can be used in a wide variety of ad hoc and sensornet environments. We conjecture that any planar 3-connected graph can be embedded in the plane in such a way that for any nodes s and t, there is a path from s to t such that the Euclidean distance to t decreases monotonically along the path. A consequence of this conjecture would be that in any ad hoc network containing such a graph as a spanning subgraph, two-dimensional virtual coordinates for the nodes can be found for which the method of purely greedy geographic routing is guaranteed to work. We discuss this conjecture and its equivalent forms show that its hypothesis is as weak as possible, and show a result delimiting the applicability of our approach: any 3-connected K3,3-free graph has a planar 3-connected spanning subgraph. We also present two alternative versions of greedy routing on virtual coordinates that provably work. Using Steinitz's theorem we show that any 3-connected planar graph can be embedded in three dimensions so that greedy routing works, albeit with a modified notion of distance; we present experimental evidence that this scheme can be implemented effectively in practice. We also present a simple but provably robust version of greedy routing that works for any graph with a 3-connected planar spanning subgraph. We consider routing problems in ad hoc wireless networks modeled as unit graphs in which nodes are points in the plane and two nodes can communicate if the distance between them is less than some fixed unit. We describe the first distributed algorithms for routing that do not require duplication of packets or memory at the nodes and yet guarantee that a packet is delivered to its destination. These algorithms can be extended to yield algorithms for broadcasting and geocasting that do not require packet duplication. A by product of our results is a simple distributed protocol for extracting a planar subgraph of a unit graph. We also present simulation results on the performance of our algorithms. We present Greedy Perimeter Stateless Routing (GPSR), a novel routing protocol for wireless datagram networks that uses the positions of routers and a packet's destination to make packet forwarding decisions. GPSR makes greedy forwarding decisions using only information about a router's immediate neighbors in the network topology. When a packet reaches a region where greedy forwarding is impossible, the algorithm recovers by routing around the perimeter of the region. By keeping state only about the local topology, GPSR scales better in per-router state than shortest-path and ad-hoc routing protocols as the number of network destinations increases. Under mobility's frequent topology changes, GPSR can use local topology information to find correct new routes quickly. We describe the GPSR protocol, and use extensive simulation of mobile wireless networks to compare its performance with that of Dynamic Source Routing. Our simulations demonstrate GPSR's scalability on densely deployed wireless networks. We propose a scalable and reliable point-to-point routing algorithm for ad hoc wireless networks and sensor-nets. Our algorithm assigns to each node of the network a virtual coordinate in the hyperbolic plane, and performs greedy geographic routing with respect to these virtual coordinates. Unlike other proposed greedy routing algorithms based on virtual coordinates, our embedding guarantees that the greedy algorithm is always successful in finding a route to the destination, if such a route exists. We describe a distributed algorithm for computing each node's virtual coordinates in the hyperbolic plane, and for greedily routing packets to a destination point in the hyperbolic plane. (This destination may be the address of another node of the network, or it may be an address associated to a piece of content in a Distributed Hash Table. In the latter case we prove that the greedy routing strategy makes a consistent choice of the node responsible for the address, irrespective of the source address of the request.) We evaluate the resulting algorithm in terms of both path stretch and node congestion. Suppose that a traveler arrives to the City of Toronto, and wants to walk to the famous CN-Tower, one of the tallest free-standing structures in the world. Assume now that our visitor, lacking a map of Toronto, is standing at a crossing from which he can see the CN-tower, and several streets S1, . . . , Sm that he can choose to start his walk. A natural (and most likely safe assumption), is that our visitor must choose to walk first along the road that points closest in the direction of the CN-tower, see Figure 1. A close look at maps of numerous cities around the world, show us that the previous way to explore a new, and unknown city will in general yield walks that will be close enough to the optimal ones to travel from one location to another. In mathematical terms, we can model the map of many cities by geometric graphs in which street intersections are represented by the vertices of our graphs, and streets by straight line segments. Compass routing on geometric networks, in its most elemental form yields the following algorithm: Geographic Routing is a family of routing algorithms that uses geographic point locations as addresses for the purposes of routing. Such routing algorithms have proven to be both simple to implement and heuristically effective when applied to wireless sensor networks. Greedy Routing is a natural abstraction of this model in which nodes are assigned virtual coordinates in a metric space, and these coordinates are used to perform point-to-point routing. Here we resolve a conjecture of Papadimitriou and Ratajczak that every 3-connected planar graph admits a greedy embedding into the Euclidean plane. This immediately implies that all 3-connected graphs that exclude K 3,3 as a minor admit a greedy embedding into the Euclidean plane. We also prove a combinatorial condition that guarantees nonembeddability. We use this result to construct graphs that can be greedily embedded into the Euclidean plane, but for which no spanning tree admits such an embedding. In this paper, we presented a fully distributed algorithm to compute a planar subgraph of the underlying wireless connectivity graph. We considered the idealized unit disk graph model in which nodes are assumed to be connected if and only if nodes are within their transmission range. The main contribution of this work is a fully distributed algorithm to extract the connected, planar graph for routing in the wireless networks. The communication cost of the proposed algorithm is O(d log d) bits, where d is the degree of anode. In addition, this paper also presented a geometric routing algorithm. The algorithm is fully distributed and nodes know only the position of other nodes and can communicate with neighboring nodes in their transmission range We describe a method for producing a greedy embedding of any n -vertex simple graph G in the hyperbolic plane, so that a message M between any pair of vertices may be routed by having each vertex that receives M pass it to a neighbor that is closer to M 's destination. Our algorithm produces succinct drawings, where vertex positions are represented using O (logn ) bits and distance comparisons may be performed efficiently using these representations. We show that greedy geometric routing schemes exist for the Euclidean metric in R 2, for 3-connected planar graphs, with coordinates that can be represented succinctly, that is, with O(logn) bits, where n is the number of vertices in the graph. All too often a seemingly insurmountable divide between theory and practice can be witnessed. In this paper we try to contribute to narrowing this gap in the field of ad-hoc routing. In particular we consider two aspects: We propose a new geometric routing algorithm which is outstandingly efficient on practical average-case networks, however is also in theory asymptotically worst-case optimal. On the other hand we are able to drop the formerly necessary assumption that the distance between network nodes may not fall below a constant value, an assumption that cannot be maintained for practical networks. Abandoning this assumption we identify from a theoretical point of view two fundamentamentally different classes of cost metrics for routing in ad-hoc networks.  Note: Special Issue on Selected Papers from GD '08 Reference EPFL-ARTICLE-158714doi:10.7155 jgaa.00197 Record created on 2010-11-26, modified on 2017-07-08