Disjoint Path Set Selection Algorithm Research On A New Model Of Ad Hoc Networks

What we study and discuss in this paper is how to improve the reliability of the Ad Hoc networks by using edge-disjoint path set selection algorithm under the new model whose vertices and edges are all unreliable.Topological changes in typical mobile Ad Hoc networks frequently render routing paths unusable. Such recurrent path failures have detrimental effects on the network performance;moreover some of the vertices in the networks may be unreliable. In order to discuss the effects on the routing algorithm and the networks performance based on the reliability deeply, this paper studies a kind of network model whose vertices and edges are all unreliable and gives an edge-disjoint path set selection algorithm (DPSP) in the defined network. First, this paper introduces the origin, the development, the application of Ad Hoc networks and some of the important route protocols, especially the Disjoint Path Set Selection Protocol. First, this paper makes a summary of the network topology, gives a kind of network model whose vertices and edges are all unreliable and gives some of the computation reliable methods, especially the method of DPSP. Second, this paper gives the design idea and the algorithm procedure of the DPSP. This main algorithm includes two sub algorithms. The first sub algorithm uses the shortest path algorithm to find path set. The second sub algorithm improves the path set that is found by using the first sub algorithm, and enhances the reliability of the Ad Hoc networks. Its time complexity is polynomial time. The path set found by DPSP is the set of disjoint multipath .The disjoint multipath set is very important to the Ad Hoc networks. It can keep the balance of the load of network and reduce the route overhead. This paper also gives the concrete example. The reliability of network gains enhancement by using the DPSP. It can be improved that the disjoint path set selection algorithm has predominance then other algorithms in the aspect of improving the network reliability.Under the new model whose vertices and edges are all unreliable, this paper enhances the network correspondence reliability by using edge-disjoint path set selection algorithm, and makes the algorithm much clearer.