text: 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.
  @cite_13: 
  @cite_14: 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.
  @cite_9: 
  @cite_24: An ad-hoc network is the cooperative engagement of a collection of mobile nodes without the required intervention of any centralized access point or existing infrastructure. We present Ad-hoc On Demand Distance Vector Routing (AODV), a novel algorithm for the operation of such ad-hoc networks. Each mobile host operates as a specialized router, and routes are obtained as needed (i.e., on-demand) with little or no reliance on periodic advertisements. Our new routing algorithm is quite suitable for a dynamic self starting network, as required by users wishing to utilize ad-hoc networks. AODV provides loop-free routes even while repairing broken links. Because the protocol does not require global periodic routing advertisements, the demand on the overall bandwidth available to the mobile nodes is substantially less than in those protocols that do necessitate such advertisements. Nevertheless we can still maintain most of the advantages of basic distance vector routing mechanisms. We show that our algorithm scales to large populations of mobile nodes wishing to form ad-hoc networks. We also include an evaluation methodology and simulation results to verify the operation of our algorithm.
  @cite_19: We propose FResher Encounter SearcH (FRESH), a simple algorithm for efficient route discovery in mobile ad hoc networks. Nodes keep a record of their most recent encounter times with all other nodes. Instead of searching for the destination, the source node searches for any intermediate node that encountered the destination more recently than did the source node itself. The intermediate node then searches for a node that encountered the destination yet more recently, and the procedure iterates until the destination is reached. Therefore, FRESH replaces the single network-wide search of current proposals with a succession of smaller searches, resulting in a cheaper route discovery. Routes obtained are loop-free.The performance of such a scheme will depend on the nodes' mobility processes. Under standard mobility processes our simulations show that route discovery cost can be decreased by an order of magnitude, a significant gain given that route discovery is a major source of routing overhead in ad hoc networks.
  @cite_23: In a color television display system comprising a kinescope having in-line electron beams and a deflection yoke having saddle horizontal and toroidal vertical windings, a correcting apparatus comprises a magnetically permeable ring disposed at the rear of the yoke around the neck of the kinescope. Slots are formed into the ring at the top and bottom, separating it into two semi-circular segments. External flux from the deflection yoke horizontal and vertical coils is shunted into the permeable corrector and away from the focus region of the kinescope electron gun assembly, thereby improving beam focus and reducing vertical coma error. The slots formed in the ring prevent excessive flux from being shunted into the corrector which otherwise would undesirably reduce the amount of beam scan, and require a compensating increase in deflection power.
  @cite_2: A Mobile Ad Hoc Network ( MANET ) is a mobile, wireless network, that does not need preexisting infrastructure. The routing infrastructure needs to be established in a distributed, self-organized way. Many routing protocols for MANETs have been proposed, and also some evaluating work has been done. The number of the proposed routing protocols and evaluations makes it difficult to keep track of the development and to get an overview about the strengths and weaknesses of routing protocols. In this report we provide a comprehensive introduction into most currently proposed routing protocols in Mobile Ad Hoc Networks. We present each routing protocol with references and the results of any evaluations known. We also classify the routing protocols according to their key characteristics.
  @cite_16: To effectively support communication in such a dynamic networking environment as the ad hoc networks, the routing framework has to be adaptable to the spatial and temporal changes in the characteristics of the network, such as traffic and mobility patterns. Multiscoping, as is provided through the concept of the Zone Routing Protocol (ZRP) for example, can serve as a basis for such an adaptive behavior. The Zone Routing framework implements hybrid routing by every network node proactively maintaining routing information about its local neighborhood called the routing zone, while reactively acquiring routes to destinations beyond the routing zone. In this paper, we propose the Independent Zone Routing (IZR) framework, an enhancement of the Zone Routing framework, which allows adaptive and distributed configuration for the optimal size of each node's routing zone, on the per-node basis. We demonstrate that the performance of IZR is significantly improved by its ability to automatically and dynamically tune the network routing operation, so as to flexibly and robustly support changes in the network characteristics and operational conditions. As a point of reference, through this form of adaptation, we show that the volume of routing control traffic overhead in the network can be reduced by an order of magnitude, under some set of parameter values. Furthermore, the adaptive nature of IZR enhances the scalability of these networks as well.
  @cite_10: 
  @cite_25: 
  @cite_12: The Dynamic Source Routing protocol (DSR) is a simple and efficient routing protocol designed specifically for use in multi-hop wireless ad hoc networks of mobile nodes. DSR allows the network to be completely self-organizing and self-configuring, without the need for any existing network infrastructure or administration. The protocol is composed of the two mechanisms of Route Discovery and Route Maintenance, which work together to allow nodes to discover and maintain source routes to arbitrary destinations in the ad hoc network. The use of source routing allows packet routing to be trivially loop-free, avoids the need for up-to-date routing information in the intermediate nodes through which packets are forwarded, and allows nodes forwarding or overhearing packets to cache the routing information in them for their own future use. All aspects of the protocol operate entirely on-demand, allowing the routing packet overhead of DSR to scale automatically to only that needed to react to changes in the routes currently in use. We have evaluated the operation of DSR through detailed simulation on a variety of movement and communication patterns, and through implementation and significant experimentation in a physical outdoor ad hoc networking testbed we have constructed in Pittsburgh, and have demonstrated the excellent performance of the protocol. In this chapter, we describe the design of DSR and provide a summary of some of our simulation and testbed implementation results for the protocol.
summary: 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.