Abstract We consider the network analytics problem of comparing two distance metrics on the same set of n entities. The classical solution to this problem is the Mantel test, which uses permutation testing to accept or reject the null hypothesis that there is “no relationship between the two metrics.” Its computational complexity is n2 times the number of permutations (based on a user supplied parameter). This work makes two contributions: (1) DIMECOSTP, a more efficient hypothesis test based on uniform random spanning trees whose complexity is n times the number of permutations. (2) DIMECOSTCC, which uses the correlation coefficient between the two sets of edge weights in a random spanning tree as an indication of the strength of the relationship between the two distance metrics. Both methods utilize sound statistical principles. Experimental results confirm the efficacy of our methods.

In addition to being realistic, a mobility model should be easy to understand and use. Unfortunately, most of the simple mobility models proposed thus far are not realistic and most of the realistic mobility models proposed thus far are not simple to use. The main contribution of this work is to present SMOOTH, a new mobility model that is realistic (e.g., SMOOTH is based on several known features of human movement) and is simple to use (e.g., SMOOTH does not have any complex input parameters). We first present SMOOTH. We then validate that SMOOTH imitates human movement patterns present in real mobility traces collected from a range of diverse scenarios. In addition, we compare SMOOTH with the other mobility models developed based on these mobility traces. Thus, with SMOOTH, we provide researchers with a tool that allows them to leverage the statistical features present in real human movement in a simple and easy to understand manner.

Mobile Ad Hoc Networks (MANETs) are usually studied through simulation. Network simulators allow users, in principle, to set values for several hundred variables. A few of these variables, including node speed, node pause time, and packet size, receive much of the attention in MANET simulation studies, because their values are generally believed to have an important effect on simulation results (e.g., delivery ratio). There are, however, a number of variables that are less discussed, but which have a substantially greater effect on simulation results than those more commonly considered. Given a typical simulation scenario, we demonstrate that variables such as the number of sources and random versus fixed destinations, which have received comparatively little attention in the literature, have a substantially greater impact on delivery ratio than do variables such as node speed and pause time, which have received significant attention in the literature. Failure to consider the values of these variables in simulation studies can result in misleading conclusions regarding the performance of routing protocols. We conclude that before investigators draw firm conclusions about the performance of a MANET routing protocol, they should examine the effects of a wider variety of variables than has generally been the practice.

Choosing an appropriate simulation scenario to study the performance of a MANET routing protocol is an important process. For example, routing will not be properly evaluated when a simulation scenario with a low average hop count or a large degree of network partitioning is used. To ensure that a simulation scenario provides an effective platform for testing a MANET routing protocol, we recommend that researchers use two metrics to characterize their simulation scenarios: the average shortest-path hop count and the average amount of network partitioning. In this paper, we provide researchers with several models that take the desired values for these two metrics as inputs, and output the simulation area and number of nodes required to create a simulation scenario that meets the researcher's target values for these two metrics to a close approximation. In this way, we provide several models that researchers can use to construct simulation scenarios that meet their standards in the evaluation of a MANET routing protocol.

In this paper we look at issues with the simulation of generic mobile ad hoc network (MANET) routing protocols. MANET simulation-based research is an involved process driven by the scenarios used in the simulations. Scenarios must be properly constructed in order to be effective in evaluating the performance of generic MANET routing protocols. For example, in scenarios with a low average hop count, little routing is needed, and poor protocols might appear successful. On the other hand, in scenarios with a high degree of partitioning, many pairs of nodes have no usable route between them, and good protocols might appear unsuccessful. Many standards are needed to establish rigorous evaluations for MANET simulation research, from simulation scenario standards to random number generator standards to results analysis standards. We do not attempt to standardize all of these areas. We do, however, propose two standards that should be employed to ensure long routes are available and used in the evaluation of generic MANET routing protocols. That is, we qualify a simulation scenario to be used for rigorous generic MANET routing protocol evaluation, based on the scenario's average shortest-path hop count and its amount of network partitioning. We construct several simulation scenarios that meet our two standards, using example metric values for our two standards. We note that our method can be modified to generate scenarios with different metric values that a researcher finds appropriate

Predicting the location of a mobile via a previously known location can reduce costs over non-predictive methods that always begin paging in the last known location. If the mobility pattern of a mobile can be described by a mathematical model, such as the Gauss-Markov model, a predictive management scheme based on that model is ideal. Typically, however, the mobility pattern of a mobile is too complex to be modeled accurately. In this paper, we propose an adaptive mobility management method which is not based upon a mathematical model. In our method, the location of a mobile is predicted solely on the basis of previously reported locations. We compare our method, through simulations, with a non-predictive method and a method based upon a mathematical model. The results show that our adaptive mobility management method performs well under a wide variety of mobility patterns.

In simulations of mobile ad hoc networks, the probability distribution governing the movement of the nodes typically varies over time and converges to a "steady-state" distribution, known in the probability literature as the stationary distribution. Some published simulation results ignore this initialization discrepancy. For those results that attempt to account for this discrepancy, the practice is to discard an initial sequence of observations from a simulation in the hope that the remaining values will closely represent the stationary distribution. This approach is inefficient and not always reliable. However, if the initial locations and speeds of the nodes are chosen from the stationary distribution, convergence is immediate and no data need be discarded. We derive the stationary distributions for location, speed, and pause time for the random waypoint mobility model. We then show how to implement the random waypoint mobility model in order to construct more efficient and reliable simulations for mobile ad hoc networks. Simulation results, which verify the correctness of our method, are included. In addition, implementation of our method for the NS-2 simulator is available.

Network wide broadcast is a fundamental operation in mobile ad hoc networks (MANETs). Several broadcast protocols have been proposed in the literature that improves on simple flooding by reducing the probability that a receiving node retransmits a packet. We propose analytical models to estimate these probabilities for three broadcast protocols. Our simulations show that these analytical models, which were derived under some simplifying assumptions, predict retransmission probabilities for static and mobile networks quite accurately when only the network layer is considered.

Many location based routing protocols have been developed for ad hoc networks. This paper presents the results of a detailed performance evaluation on two of these protocols: location-aided routing (LAR) and distance routing effect algorithm for mobility (DREAM). We compare the performance of these two protocols with the dynamic source routing (DSR) protocol and a minimum standard (i.e., a protocol that floods all data packets). We used NS-2 to simulate 50 nodes moving according to the random waypoint model. Our main goal for the performance investigation was to stress the evaluated protocols with high data loads during both low and high speeds. Our performance investigation produced the following conclusions. First, the added protocol complexity of DREAM does not appear to provide benefits over a flooding protocol. Second, promiscuous mode operation improves the performance of DSR significantly. Third, adding location information to DSR (i.e., similar to LAR) increases both the network load and the data packet delivery ratio; our results conclude that the increase in performance is worth the increase in cost. Lastly, our implementation of DREAM provides a simple location service that could be used with other ad hoc network routing protocols.