|
ON THE PROBABILITY OF K-CONNECTIVITY IN WIRELESS AD HOC NETWORKS UNDER DIFFERENT MOBILITY MODELSKeywords: Wireless Ad hoc Networks , k-Connectivity , Mobility Models , Probability , Ford-Fulkerson Algorithm , Simulations Abstract: We compare the probability of k-Connectivity of an ad hoc network under Random Way Point (RWP),City Section and Manhattan mobility models. A Network is said to be k-Connected if there exists at least kedge disjoint paths between any pair of nodes in that network at any given time and velocity. Initially, foreach of the three mobility models, the movement of the each node in the ad hoc network at a givenvelocity and time are captured and stored in the Node Movement Database (NMDB). Using themovements in the NMDB, the location of the node at a given time is computed and stored in the NodeLocation Database (NLDB). A weighted graph is created using the location of the nodes from NLDB,which is converted into a residual graph. The k-Connectivity of this residual graph is obtained by runningFord-Fulkerson’s algorithm on it. Ford Fulkerson’s algorithm computes the maximum flow of a networkby recording the flows assigned to different routes from each node to all the other nodes in the network.When run for a particular source-destination pair (s, d) pair on a residual network graph with unit edgeweights as capacity, the maximum flow determined by Ford-Fulkerson’ algorithm is the number of edgedisjoint s-d paths on the network graph. Simulations show that the RWP model yields the highestprobability of k-Connectivity compared to City Section and Manhattan mobility models for a majority ofdifferent node densities and velocities considered. Simulation results also show that, for all the threemobility models, as the k value increases, the probability of k-Connectivity decreases for a given densityand velocity and as the density increases the probability of k-Connectivity increases.
|