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