Source delay, the time a packet experiences in its source node, serves as a fundamental quantity for delay performance analysis in networks. However, the source delay performance in highly dynamic mobile ad hoc networks (MANETs) is still largely unknown by now. This paper studies the source delay in MANETs based on a general packet dispatching scheme with dispatch limit @math (PD- @math for short), where a same packet will be dispatched out up to @math times by its source node such that packet dispatching process can be flexibly controlled through a proper setting of @math . We first apply the Quasi-Birth-and-Death (QBD) theory to develop a theoretical framework to capture the complex packet dispatching process in PD- @math MANETs. With the help of the theoretical framework, we then derive the cumulative distribution function as well as mean and variance of the source delay in such networks. Finally, extensive simulation and theoretical results are provided to validate our source delay analysis and illustrate how source delay in MANETs are related to network parameters.
Overall delay (also called end-to-end delay), defined as the time it takes a packet to reach its destination after it is generated at its source, has also been extensively studied in the literature. For MANETs with two-hop relay routing, closed-form upper bounds on expected overall delay were derived in @cite_33 @cite_5 . For MANETs with two-hop relay routing and its variants, approximation results on expected overall delay were presented in @cite_11 @cite_20 . For MANETs with multi-hop relay routing, upper bounds on the cumulative distribution function of overall delay were reported in @cite_15 @cite_19 , and approximations on the expected overall delay were derived in @cite_24 . Rather than studying upper bounds and approximations on overall delay, some recent works explored the exact overall delay and showed that it is possible to derive the exact results on overall delay for MANETs under some special two-hop relay routings @cite_33 @cite_13 .
@cite_33 @cite_24 @cite_19 @cite_5 @cite_15 @cite_13 @cite_20 @cite_11
2171471095 2121368972 2049732373 2076363954 2101863060 1854119092 2063378231
We consider the throughput delay tradeoffs for scheduling data transmissions in a mobile ad hoc network. To reduce delays in the network, each user sends redundant packets along multiple paths to the destination. Assuming the network has a cell partitioned structure and users move according to a simplified independent and identically distributed (i.i.d.) mobility model, we compute the exact network capacity and the exact end-to-end queueing delay when no redundancy is used. The capacity-achieving algorithm is a modified version of the Grossglauser-Tse two-hop relay algorithm and provides O(N) delay (where N is the number of users). We then show that redundancy cannot increase capacity, but can significantly improve delay. The following necessary tradeoff is established: delay rate spl ges O(N). Two protocols that use redundancy and operate near the boundary of this curve are developed, with delays of O( spl radic N) and O(log(N)), respectively. Networks with non-i.i.d. mobility are also considered and shown through simulation to closely match the performance of i.i.d. systems in the O( spl radic N) delay regime. A large body of work has theoretically analyzed the performance of mobility-assisted routing schemes for intermittently connected mobile networks. But the vast majority of these prior studies have ignored wireless contention. Recent papers have shown through simulations that ignoring contention leads to inaccurate and misleading results, even for sparse networks. In this paper, we analyze the performance of routing schemes under contention. First, we introduce a mathematical framework to model contention. This framework can be used to analyze any routing scheme with any mobility and channel model. Then, we use this framework to compute the expected delays for different representative mobility-assisted routing schemes under random direction, random waypoint and community-based mobility models. Finally, we use these delay expressions to optimize the design of routing schemes while demonstrating that designing and optimizing routing schemes using analytical expressions which ignore contention can lead to suboptimal or even erroneous behavior. The class of Gupta-Kumar results, which predict the throughput capacity in wireless networks, is restricted to asymptotic regimes. This tutorial presents a methodology to address a corresponding non-asymptotic analysis based on the framework of the stochastic network calculus, in a rigorous mathematical manner. In particular, we derive explicit closed-form results on the distribution of the end-to-end capacity and delay, for a fixed source-destination pair, in a network with broad assumptions on its topology and degree of spatial correlations. The results are non-asymptotic in that they hold for finite time scales and network sizes, as well as bursty arrivals. The generality of the results enables the research of several interesting problems, concerning for instance the effects of time scales or randomness in topology on the network capacity. The two-hop relay algorithm and its variants have been attractive for ad hoc mobile networks, because they are simple yet efficient, and more importantly, they enable the capacity and delay to be studied analytically. This paper considers a general two-hop relay with f-cast (2HR-f), where each packet is delivered to at most f distinct relay nodes and should be received in order at its destination. We derive the closed-form theoretical models rather than order sense ones for the 2HR-f algorithm with a careful consideration of the important interference, medium contention, traffic contention and queuing delay issues, which enable an accurate delay and capacity analysis to be performed for an ad hoc mobile network employing the 2HR-f. Based on our models, one can directly get the corresponding order sense results. Extensive simulation studies are also conducted to demonstrate the efficiency of these new models. The class of Gupta-Kumar results give the asymptotic throughput in multi-hop wireless networks but cannot predict the throughput behavior in networks of typical size. This paper addresses the non-asymptotic analysis of the multihop wireless communication problem and provides, for the first time, closed-form results on multi-hop throughput and delay distributions. The results are non-asymptotic in that they hold for any number of nodes and also fully account for transient regimes, i.e., finite time scales, delays, as well as bursty arrivals. Their accuracy is supported by the recovery of classical single-hop results, and also by simulations from empirical data sets with realistic mobility settings. Moreover, for a specific network scenario and a fixed pair of nodes, the results confirm Gupta-Kumar's Ω(1√n log n) asymptotic scaling law. Understanding the delay performance in mobile ad hoc networks (MANETs) is of fundamental importance for supporting Quality of Service (QoS) guaranteed applications in such networks. Despite lot of research efforts in last several decades, the important end-to-end delay modeling in MANETs remains a challenging issue. This is partially due to the highly dynamical behaviors of MANETs but also due to the lack of an efficient theoretical framework to depict the complicated network state transitions under such dynamics. This paper demonstrates the potential application of the Quasi-Birth-and-Death process (QBD) theory in MANETs delay analysis by applying it to the end-to-end delay modeling in broadcast-based two-hop relay MANETs. We first demonstrate that the QBD theory actually enables a novel and powerful theoretical framework to be developed to efficiently capture the complicated network state transitions in the concerned MANETs. We then show that with the help of the theoretical framework, we are able to analytically model the exact expected end-to-end delay and also the exact per node throughput capacity in such MANETs. Extensive simulations are further provided to validate the efficiency of our QBD theory-based models. Due to their simplicity and efficiency, the two-hop relay algorithm and its variants serve as a class of attractive routing schemes for mobile ad hoc networks (MANETs). With the available two-hop relay schemes, a node, whenever getting an opportunity for transmission, randomly probes only once a neighbor node for the possible transmission. It is notable that such single probing strategy, although simple, may result in a significant waste of the precious transmission opportunities in highly dynamic MANETs. To alleviate such limitation for a more efficient utilization of limited wireless bandwidth, this paper proposes a more general probing-based two-hop relay algorithm with limited packet redundancy. In such an algorithm with probing round limit τ and packet redundancy limit f, each transmitter is allowed to conduct up to τ rounds of probing for identifying a possible receiver and each packet can be delivered to at most f distinct relays. A general theoretical framework is further developed to help us understand that under different setting of τ and f, how we can benefit from multiple probings in terms of the per node throughput capacity and the expected end-to-end packet delay.