Decision making on routing and queue management with node independent multipath routing in mobile ad-hoc networks

by Oz Pasaogullari, Melike.

ii A mobile ad hoc network (MANET) is a wireless network without a fixed infrastructure. Due to the mobile nature of the nodes, connectivity between the nodes is not fixed and routing is an important problem for these types of networks and more complex compared to their counterpart in wired networks. Multipath routing is a concept in which more than one path is used to transfer packets of data between sourcedestination pairs. Multiple paths can be used either as alternate (backup) paths in case of failures or simultaneously by splitting the traffic over multiple paths to balance the network load. The main goal of this research is to develop a solution methodology to the routing and scheduling problems in MANETs via distributed algorithms to select traffic flow to be transmitted and the type of routing --unipath or multipath-- to be used at each decision point. In this work, multipath routing in MANETs is analyzed, and the decisions for selecting the paths to be used among the available paths and determining the allocations to different paths are made. A centralized routing and scheduling problem has been formulated and sample cases have been solved using the General Algebraic Modeling System (GAMS) to help propose a heuristic for the distributed problem. A node-independent multipath routing (NIMR) algorithm which allows decision making at intermediate nodes is proposed. The node-independent multipath routing algorithm is compared with a path delay based source-based unipath (SBU) routing algorithm. The NIMR algorithm performs up to 7.12% better than the SBU routing algorithm on the average. However, the spread of the data shows that the SBU routing algorithm still performs better than the NIMR algorithm in 15% to 40% of the replications. Based on iii these results, a hybrid algorithm which switches between the unipath and multipath routing algorithms based on the local information of the nodes is proposed. The NIMR, SBU and hybrid algorithms are compared in terms of average packet delay via hypothesis tests. When the NIMR and hybrid algorithms are used, an improvement ratio with respect to the SBU algorithm which differs from zero statistically is obtained in most of the cases for networks with more than 15 nodes. Also, for networks with more than 20 nodes, a negative improvement ratio which differs from zero statistically is obtained when the hybrid algorithm is compared with the NIMR algorithm indicating that the NIMR algorithm performs better than the hybrid algorithm. The NIMR algorithm is also compared with five routing algorithms adapted from the literature for different size networks and mobility scenarios in terms of end-to-end delay, throughput, and overhead of the routing algorithm. In general, the NIMR algorithm performs up to 24.052% better than the unipath routing algorithms and 37.919% better than the source-based multipath algorithms in terms of average packet delay. Based on the results of the simulation experiments, a source-based unipath routing methodology based on hop count is recommended for small size networks with 8 or 10 nodes, whereas the NIMR algorithm is recommended for larger networks. The effect of four different scheduling rules on the NIMR algorithm is also analyzed. The results show that there is not enough evidence to conclude that there is a significant different between the scheduling rules, however, the first in first out rule is recommended since it gives lower average end-to-end delay values.