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

摘要

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 source-destination 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 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. (Abstract shortened by UMI.)