Given a network of fixed size @math and an initial distribution of data, we derive sufficient connectivity conditions on a sequence of time-varying digraphs for (a) data collection and (b) data dissemination, within at most @math iterations. The former is shown to enable distributed computation of the network size @math , while the latter does not. Knowledge of @math subsequently enables each node to acknowledge the earliest time point at which they can cease communication, specifically we find the number of redundant signals can be truncated at the finite time @math . Using a probabilistic approach, we obtain tight upper and lower bounds for the expected time until the @math node obtains the entire collection of data, in other words complete data dissemination. Similarly tight upper and lower bounds are also found for the expected time until the @math node obtains the entire collection of data. Interestingly, these bounds are both @math and in fact differ by only two iterations. Numerical results are explored and verify each result.
A large number of specific protocols have been proposed for efficient routing in mobile networks @cite_2 . These algorithms are based on the available topological knowledge of the network communication graph, or sometimes on the relative coordinates of each node. For the latter set of geometric" routing algorithms, it has been shown that greedy (i.e., local) forwarding strategies may lead into dead-ends, while the optimal delivery strategy has only been guaranteed for the static case @cite_14 because it involves a preprocessing stage (see also @cite_23 @cite_13 @cite_10 @cite_9 @cite_25 for further developments in this area). Considering only topology-based routing algorithms, reactive protocols similar to DSR @cite_12 and AODV @cite_24 make sense in a highly mobile environment. An alternative approach FRESH @cite_19 takes mobility into account, but, arguably for the worse, it views mobility as a resource rather than a handicap. There also exist hybrid protocols, such as IZR @cite_16 . Nevertheless, none of these protocols take into account both a potential topological change at every single iteration, and simultaneously a worst-case perspective.
@cite_13 @cite_14 @cite_9 @cite_24 @cite_19 @cite_23 @cite_2 @cite_16 @cite_10 @cite_25 @cite_12
2126003739 2133937062 1975507024 2140000065 2100013559 2110865257 2141661023 2140531391 2140525529 2028069703 2136316858 2104645107 2107080471 2155564629 2083299955 2120361596 2170136598 2070317877 2152948207 2165983440
Since ad hoc and sensor networks can be composed of a very large number of devices, the scalability of network protocols is a major design concern. Furthermore, network protocols must be designed to prolong the battery lifetime of the devices. However, most existing routing techniques for ad hoc networks are known not to scale well. On the other hand, the so-called geographical routing algorithms are known to be scalable but their energy efficiency has never been extensively and comparatively studied. In a geographical routing algorithm, data packets are forwarded by a node to its neighbor based on their respective positions. The neighborhood of each node is constituted by the nodes that lie within a certain radio range. Thus, from the perspective of a node forwarding a packet, the next hop depends on the width of the neighborhood it perceives. The analytical framework proposed in this paper allows to analyze the relationship between the energy efficiency of the routing tasks and the extension of the range of the topology knowledge for each node. A wider topology knowledge may improve the energy efficiency of the routing tasks but increases the cost of topology information due to signaling packets needed to acquire this information. The problem of determining the optimal topology knowledge range for each node to make energy efficient geographical routing decisions is tackled by integer linear programming. It is shown that the problem is intrinsically localized, i.e., a limited topology knowledge is sufficient to make energy efficient forwarding decisions. The leading forwarding rules for geographical routing are compared in this framework, and the energy efficiency of each of them is studied. Moreover, a new forwarding scheme, partial topology knowledge forwarding (PTKF), is introduced, and shown to outperform other existing schemes in typical application scenarios. A probe-based distributed protocol for knowledge range adjustment (PRADA) is finally introduced that allows each node to efficiently select online its topology knowledge range. PRADA is shown to rapidly converge to a near-optimal solution. In this paper, we address the problem of energy efficient localized routing in wireless ad hoc networks. Numerous energy aware routing protocols were proposed to seek the power efficiency of routes. Among them, several geographical localized routing protocols were proposed to help making smarter routing decision using only local information and reduce the routing overhead. However, most of the proposed localized routing methods cannot theoretically guarantee the power efficiency of their routes. In this paper, we give the first localized routing algorithm, called localized energy aware restricted neighborhood routing (LEARN), which can guarantee the power efficiency of its route asymptotically almost sure. Given destination node t, an intermediate node v will only select a certain neighbor v such that pi alpha, our LEARN routing protocol will find the route for any pair of nodes asymptotically almost sure. When the transmission range rn = radicbet alnl pin for some beta < pi alpha, the LEARN routing protocol will not be able to find the route for any pair of nodes asymptotically almost sure. We also conducted simulations to study the performance of LEARN and compare it with a typical localized routing protocol (GPSR) and a global ad hoc routing protocol (DSR) The assessment of routing protocols for mobile wireless networks is a difficult task, because of the networks' dynamic behavior and the absence of benchmarks. However, some of these networks, such as intermittent wireless sensors networks, periodic or cyclic networks, and some delay tolerant networks (DTNs), have more predictable dynamics, as the temporal variations in the network topology can be considered as deterministic, which may make them easier to study. Recently, a graph theoretic model--the evolving graphs--was proposed to help capture the dynamic behavior of such networks, in view of the construction of least cost routing and other algorithms. The algorithms and insights obtained through this model are theoretically very efficient and intriguing. However, there is no study about the use of such theoretical results into practical situations. Therefore, the objective of our work is to analyze the applicability of the evolving graph theory in the construction of efficient routing protocols in realistic scenarios. In this paper, we use the NS2 network simulator to first implement an evolving graph based routing protocol, and then to use it as a benchmark when comparing the four major ad hoc routing protocols (AODV, DSR, OLSR and DSDV). Interestingly, our experiments show that evolving graphs have the potential to be an effective and powerful tool in the development and analysis of algorithms for dynamic networks, with predictable dynamics at least. In order to make this model widely applicable, however, some practical issues still have to be addressed and incorporated into the model, like adaptive algorithms. We also discuss such issues in this paper, as a result of our experience. Mobile ad hoc networks are characterized by multi-hop wireless links, absence of any cellular infrastructure, and frequent host mobility. Design of efficient routing protocols in such networks is a challenging issue. A class of routing protocols called on-demand protocols has recently attracted attention because of their low routing overhead. The on-demand protocols depend on query floods to discover routes whenever a new route is needed. Such floods take up a substantial portion of network bandwidth. We focus on a particular on-demand protocol, called dynamic source routing, and show how intelligent use of multipath techniques can reduce the frequency of query floods. We develop an analytic modeling framework to determine the relative frequency of query floods for various techniques. Results show that while multipath routing is significantly better than single path routing, the performance advantage is small beyond a few paths and for long path lengths. It also shows that providing all intermediate nodes in the primary (shortest) route with alternative paths has a significantly better performance than providing only the source with alternate paths. We propose a novel localized routing protocol for wireless sensor networks (WSN) that is energy-efficient and guarantees delivery. We prove that it is constant factor of the optimum for dense networks. To forward a packet, a node s in graph G computes the cost of the energy weighted shortest path (SP) between s and each of its neighbors which are closer to the destination than itself. It then selects node x which minimizes the ratio of the cost of the SP to the progress towards the destination. It then sends the message to the first node on the SP from s to x: say node x'. Node x' restarts the same greedy routing process until the destination is reached or the routing fails. To recover from failure, our algorithm invokes face routing that guarantees delivery. This work is the first to optimize energy consumption of face routing. First, we build a connected dominating set from graph G, second we compute its Gabriel graph to obtain the planar graph G'. Face routing is applied on G' only to decide which edges to follow in the recovery process. On each edge, greedy routing is used. This two-phase (greedy-Face) end-to-end routing process (EtE) reiterates until the final destination is reached. Simulation results show that EtE outperforms several existing geographical routing on energy consumption metric. In this paper, we propose a selection region based multihop routing protocol with directional antennas for wireless mobile ad hoc networks, where the selection region is defined by two parameters: a reference distance and the beamwidth of the directional antenna. At each hop, we choose the nearest node to the transmitter within the selection region as the next hop relay. By maximizing the expected density of progress, we present an upper bound for the optimum reference distance and derive the relationship between the optimum reference distance and the optimum transmission probability. Compared with the results with routing strategy using omnidirectional antennas in [1], we find interestingly that the optimum transmission probability is a constant independent of the beamwidth, the expected density of progress with the new routing strategy is increased significantly, and the computational complexity involved in the relay selection is also greatly reduced. Existing position-based unicast routing algorithms which forward packets in the geographic direction of the destination require that the forwarding node knows the positions of all neighbors in its transmission range. This information on direct neighbors is gained by observing beacon messages each node sends out periodically. Due to mobility, the information that a node receives about its neighbors becomes outdated, leading either to a significant decrease in the packet delivery rate or to a steep increase in load on the wireless channel as node mobility increases. In this paper, we propose a mechanism to perform position-based unicast forwarding without the help of beacons. In our contention-based forwarding scheme (CBF) the next hop is selected through a distributed contention process based on the actual positions of all current neighbors. For the contention process, CBF makes use of biased timers. To avoid packet duplication, the first node that is selected suppresses the selection of further nodes. We propose three suppression strategies which vary with respect to forwarding efficiency and suppression characteristics. We analyze the behavior of CBF with all three suppression strategies and compare it to an existing greedy position-based routing approach by means of simulation with ns-2. Our results show that CBF significantly reduces the load on the wireless channel required to achieve a specific delivery rate compared to the load a beacon-based greedy forwarding strategy generates. Routing in large-scale mobile ad hoc networks is challenging because all the nodes are potentially moving. Geographic routing can partially alleviate this problem, as nodes can make local routing decisions based solely on the destinations' geographic coordinates. However, geographic routing still requires an efficient location service, i.e., a distributed database recording the location of every destination node. Devising efficient, scalable, and robust location services has received considerable attention in recent years. The main purpose of this paper is to show that node mobility can be exploited to disseminate destination location information without incurring any communication overhead. We achieve this by letting each node maintain a local database of the time and location of its last encounter with every other node in the network. This database is consulted by packets to obtain estimates of their destination's current location. As a packet travels towards its destination, it is able to successively refine an estimate of the destination's precise location, because node mobility has "diffused" estimates of that location. We define and analyze a very simple algorithm called EASE (exponential age search) and show that in a model where N nodes perform independent random walks on a square lattice, the length of the routes computed by EASE are on the same order as the distance between the source and destination even for very large N. Therefore, without exchanging any explicit location information, the length of EASE routes are within a constant factor of routes obtained with perfect information. We discuss refinements of the EASE algorithm and evaluate it through extensive simulations. We discuss general conditions such that the mobility diffusion effect leads to efficient routes without an explicit location service. In practical settings, where these conditions may not always be met, we believe that the mobility diffusion effect can complement existing location services and enhance their robustness and scalability. Routing in large-scale mobile ad hoc networks is challenging because all the nodes are potentially moving. Geographic routing can partially alleviate this problem, as nodes can make local routing decisions based solely on the destinations' geographic coordinates. However, geographic routing still requires an efficient location service, i.e., a distributed database recording the location of every destination node. Devising efficient, scalable, and robust location services has received considerable attention in recent years. The main purpose of this paper is to show that node mobility can be exploited to disseminate destination location information without incurring any communication overhead. We achieve this by letting each node maintain a local database of the time and location of its last encounter with every other node in the network. This database is consulted by packets to obtain estimates of their destination's current location. As a packet travels towards its destination, it is able to successively refine an estimate of the destination's precise location, because node mobility has "diffused" estimates of that location. We define and analyze a very simple algorithm called EASE (Exponential Age Search) and show that in a model where Theta(n) nodes perform independent random walks on a square lattice of size n, the length of the routes computed by EASE are of the same order as the distance between the source and destination even for very large n. Therefore, without disseminating any explicit location information, the length of EASE routes are within a constant factor of routes obtained with perfect information. We discuss refinements of the EASE algorithm and evaluate it through extensive simulations. We discuss general conditions such that the mobility diffusion effect leads to efficient routes without an explicit location service. In practical settings, where these conditions may not always be met, we believe that the mobility diffusion effect can complement existing location services and enhance their robustness and scalability We propose a routing strategy to improve the transportation efficiency on complex networks. Instead of using the routing strategy for shortest path, we give a generalized routing algorithm to find the so-called efficient path, which considers the possible congestion in the nodes along actual paths. Since the nodes with the largest degree are very susceptible to traffic congestion, an effective way to improve traffic and control congestion, as our strategy, can be redistributing traffic load in central nodes to other noncentral nodes. Simulation results indicate that the network capability in processing traffic is improved more than 10 times by optimizing the efficient path, which is in good agreement with the analysis. DOI: 10.1103 PhysRevE.73.046108 PACS numbers: 89.75.Hc Since the seminal work on scale-free networks by Barabasi and Albert BA model1 and on the small-world phenomenon by Watts and Strogatz 2, the structure and dynamics of complex networks have recently attracted a tremendous amount of interest and attention from the physics community see the review papers 3‐5 and references therein. The increasing importance of large communication networks such as the Internet 6, upon which our society survives, calls for the need for high efficiency in handling and delivering information. In this light, to find optimal strategies for traffic routing is one of the important issues we have to address. There have been many previous studies to understand and control traffic congestion on networks, with a basic assumption that the network has a homogeneous structure 7‐11. However, many real networks display both scale-free and small-world features, and thus it is of great interest to study the effect of network topology on traffic flow and the effect of traffic on network evolution. present a formalism that can cope simultaneously with the searching and traffic dynamics in parallel transportation systems 12. This formalism can be used to optimize network structure under a local search algorithm, while to obtain the formalism one should know the global information of the whole networks. Holme and Kim provide an in-depth analysis on the vertex edge overload cascading breakdowns based on evolving networks, and suggest a method to avoid This paper is meant to be an illustration of the use of stochastic geometry for analyzing the performance of routing in large wireless ad hoc (mobile or mesh) networks. In classical routing strategies used in such networks, packets are transmitted on a pre-defined route that is usually obtained by a shortest-path routing protocol. In this paper we review some recent ideas concerning a new routing technique which is opportunistic in the sense that each packet at each hop on its (specific) route from an origin to a destination takes advantage of the actual pattern of nodes that captured its recent (re)transmission in order to choose the next relay. The paper focuses both on the distributed algorithms allowing such a routing technique to work and on the evaluation of the gain in performance it brings compared to classical mechanisms. On the algorithmic side, we show that it is possible to implement this opportunistic technique in such a way that the current transmitter of a given packet does not need to know its next relay a priori, but the nodes that capture this transmission (if any) perform a self-selection procedure to choose the packet relay node and acknowledge the transmitter. We also show that this routing technique works well with various medium access protocols (such as Aloha, CSMA, TDMA). Finally, we show that the above relay self-selection procedure can be optimized in the sense that it is the node that optimizes some given utility criterion (e.g. minimize the remaining distance to the final destination), which is chosen as the relay. The performance evaluation part is based on stochastic geometry and combines simulation as analytical models. The main result is that such opportunistic schemes very significantly outperform classical routing schemes when properly optimized and provided at least a small number of nodes in the network know their geographical positions exactly. Geographic routing can provide efficient routing at a fixed overhead. However, the performance of geographic routing is impacted by physical voids, and localization errors. Accordingly, virtual coordinate systems (VCS) were proposed as an alternative approach that is resilient to localization errors and that naturally routes around physical voids. However, VCS also faces virtual anomalies. Moreover, there are no effective complementary routing algorithm that can be used to traverse voids. Most existing solutions use variants of flooding or blind searching when a void is encountered. In this paper, we make the observation that increasing the number of dimensions in virtual coordinate systems cannot eliminate all virtual anomalies since some portions of the network may be 1-connected to the rest of the network. As a result, we conjecture that a delivery guaranteed protocol must be one-dimensional and propose a spanning-path virtual coordinate system that has this property. We develop a delivery guaranteed routing algorithm on top of this system that can be used on its own, or as a complementary algorithm to traverse voids. With this approach, and for the first time, we demonstrate a stateless and delivery guaranteed geometric routing algorithm on VCS. When used in conjunction with our previously proposed aligned virtual coordinate system (AVCS), it out-performs not only all geometric routing protocols on VCS, but also geographic routing with accurate location information. This paper considers the problem of designing power efficient routing with guaranteed delivery for sensor networks with known distances between neighbors but unknown geographic locations. We propose Hector, a hybrid energy efficient tree-based optimized routing protocol, based on two sets of virtual coordinates. One set is based on rooted tree coordinates, and the other is based on hop distances toward several landmarks. In our algorithm, the node currently holding the packet forwards it to its neighbor that optimizes ratio of power cost over distance progress with landmark coordinates, among nodes that reduce landmark coordinates and do not increase tree coordinates. If such a node does not exist then forwarding is made to the neighbor that reduces tree based distance and optimizes power cost over tree distance progress ratio. Our simulations show the superiority of our algorithm over existing alternatives while guaranteeing delivery, and only up to 30 additional power compared to centralized shortest weighted path algorithm. In classical routing strategies for multihop mobile wireless networks packets are routed on a pre-defined route usually obtained by a shortest path routing protocol. In opportunistic routing schemes, for each packet and each hop, the next relay is found by dynamically selecting the node that captures the packet transmission and which is the nearest to the destination. Such a scheme allows each packet to take advantage of the local pattern of transmissions and fadings at any slot and at any hop. The aim of this paper is to quantify and optimize the potential performance gains of such opportunistic routing strategies compared with classical routing schemes. The analysis is conducted under the following lower layer assumptions: the Medium Access (MAC) layer is a spatial version of Aloha which has been shown to scale well for large multihop networks; the capture of a packet by some receiver is determined by the Signal over Interference and Noise Ratio (SINR) experienced by the receiver. The paper contains a detailed simulation study which shows that such time-space opportunistic schemes very significantly outperform classical routing schemes. It also contains a mathematical study where we show how to optimally tune the MAC parameters so as to minimize the average number of time slots required to carry a typical packet from origin to destination on long paths. We show that this optimization is independent of network density. We begin by asking whether geographic routing can scale when nodes are mobile; that is, can the overhead involved in tracking node locations be accommodated within the transport capacity of large-scale mobile ad hoc networks (MANETs)? We answer this question in the affirmative by proposing an efficient position publish protocol which fits within the transport capacity and a routing protocol that operates with imperfect information of the destination's location. The routing protocol guarantees, with high probability, routes whose lengths are within a constant “stretch” factor of the shortest path from source to destination. The key idea underlying the scalability of the publish protocol is for each potential destination node to send location updates (with frequency decaying with distance) only to a subset of network nodes, structured as annular regions around it (the natural approach of updating circular regions in distance-dependent fashion does not scale). The routing protocol must then account for the fact that the source and or relay nodes may not have estimates of the destination's location (or may have stale estimates). Spatial and temporal scaling of protocol parameters are chosen so as to guarantee scalability, route reliability and route stretch. We consider a routing problem in the context of large scale networks with uncontrolled dynamics. A case of uncontrolled dynamics that has been studied extensively is that of mobile nodes, as this is typically the case in cellular and mobile ad-hoc networks. In this paper however we study routing in the presence of a different type of dynamics: nodes do not move, but instead switch between active and inactive states at random times. Our interest in this case is motivated by the behavior of sensor nodes powered by renewable sources, such as solar cells or ambient vibrations. In this paper we formalize the corresponding routing problem as a problem of constructing suitably constrained random walks on random dynamic graphs. We argue that these random walks should be designed so that their resulting invariant distribution achieves a certain load balancing property, and we give simple distributed algorithms to compute the local parameters for the random walks that achieve the sought behavior. A truly novel feature of our formulation is that the algorithms we obtain are able to route messages along all possible routes between a source and a destination node, without performing explicit route discovery repair computations, and without maintaining explicit state information about available routes at the nodes. To the best of our knowledge, these are the first algorithms that achieve true multipath routing (in a statistical sense), at the complexity of simple stateless operations. We study a mobile wireless network where groups or clusters of nodes are intermittently connected via mobile carriers'' (the carriers provide connectivity over time among different clusters of nodes). Over such networks (an instantiation of a delay tolerant network), it is well-known that traditional routing algorithms perform very poorly. In this paper, we propose a two-level Back- Pressure with Source-Routing algorithm (BP+SR) for such networks. The proposed BP+SR algorithm separates routing and scheduling within clusters (fast time-scale) from the communications that occur across clusters (slow time-scale), without loss in network throughput (i.e., BP+SR is throughput-optimal). More importantly, for a source and destination node that lie in different clusters, the traditional back-pressure algorithm results in large queue lengths at each node along its path. This is because the queue dynamics are driven by the slowest time-scale (i.e., that of the carrier nodes) along the path between the source and destination, which results in very large end-to-end delays. On the other-hand, we show that the two-level BP+SR algorithm maintains large queues only at a very few nodes, and thus results in order-wise smaller end-to-end delays. We provide analytical as well as simulation results to confirm our claims. We consider dynamic routing and power allocation for a wireless network with time-varying channels. The network consists of power constrained nodes that transmit over wireless links with adaptive transmission rates. Packets randomly enter the system at each node and wait in output queues to be transmitted through the network to their destinations. We establish the capacity region of all rate matrices ( spl lambda sub ij ) that the system can stably support-where spl lambda sub ij represents the rate of traffic originating at node i and destined for node j. A joint routing and power allocation policy is developed that stabilizes the system and provides bounded average delay guarantees whenever the input rates are within this capacity region. Such performance holds for general arrival and channel state processes, even if these processes are unknown to the network controller. We then apply this control algorithm to an ad hoc wireless network, where channel variations are due to user mobility. Centralized and decentralized implementations are compared, and the stability region of the decentralized algorithm is shown to contain that of the mobile relay strategy developed by Grossglauser and Tse (2002). 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. It was recently reported that all known face and combined greedy-face routing variants cannot guarantee message delivery in arbitrary undirected planar graphs. The purpose of this article is to clarify that this is not the truth in general. We show that specifically in relative neighborhood and Gabriel graphs recovery from a greedy routing failure is always possible without changing between any adjacent faces. Guaranteed delivery then follows from guaranteed recovery while traversing the very first face. In arbitrary graphs, however, a proper face selection mechanism is of importance since recovery from a greedy routing failure may require visiting a sequence of faces before greedy routing can be restarted again. A prominent approach is to visit a sequence of faces which are intersected by the line connecting the source and destination node. Whenever encountering an edge which is intersecting with this line, the critical part is to decide if face traversal has to change to the next adjacent one or not. Failures may occur from incorporating face routing procedures that force to change the traversed face at each intersection. Recently observed routing failures which were produced by the GPSR protocol in arbitrary planar graphs result from incorporating such a face routing variant. They cannot be constructed by the well known GFG algorithm which does not force changing the face anytime. Beside methods which visit the faces intersected by the source destination line, we discuss face routing variants which simply restart face routing whenever the next face has to be explored. We give the first complete and formal proofs that several proposed face routing, and combined greedyface routing schemes do guarantee delivery in specific graph classes or even any arbitrary planar graphs. We also discuss the reasons why other methods may fail to deliver a message or even end up in a loop.