Research On Path Finding Strategy Of Complex Networks

Path finding problem is a classical and important content in network research.It has not only solved many problems in practical application,but also been used as a basic tool for solving other optimization problems.With the development of techniques,the current real networks are organized by various individuals and complex relationships among them,and they can exist not only in the substantial form(such as traffic network),but also in the virtual form(such as WWW).In such backgrounds,traditional path finding strategy based on simple graph theory can not provide an efficient tool for studying these real networks now.Recent booming complex network theory could clearly explain many characters of real networks and help to reveal the rules concealed among individuals.Based on above,this paper focuses on the topic of path finding strategy.First we start our thesis with analyzing and researching the shortest path mapping schema and congestion adaptive optimization stragety based on random walk.Then combined with the application of wireless sensor networks,we propose a routing schema to find reliable path based on path reliability and arrival reliability.Theory analysis and numerical simulation are adopted in the research.The main work of this thesis is as follows:1.The properties of complex networks structure including the property of small-world and scale-free in real networks are reviewed,and some real examples are presented.Some network models including random networks,small-world networks and scale-free networks which can be used to test the algorithm in the following chapters,introduced.2.Research on shortest path mapping strategy for complex networks based on multiple particles from multiple sources.Aiming at the problem such as the chance and the bad effect of path mapping brought by the tradional randowm walk in complex network,we propose a shortest path finding strategy based on multiple particles from multiple sources(MPMS)by combining the multiple particles method and multiple sources schema.Based on the finite state Markov chain,the mathematical model of MPMS is established.Theoretical analysis shows that,compared with the traditional random walk model,the first particle reaching the destination in MPMS gets a higher probability within t steps,and the average path length is close to the shortest path.The simulation results show that the average path length is low and the universality is strong.3.Research on complex network path optimization strategy based on congestion adaptation.According to the problems of common random walk path optimization strategies often select path from static and fixed point of view and are unable to effectively deal with network congestion,the paper presents a congestion adaptive complex network path optimization strategy.By introducing the concept of particle node queue we establish the flow balance equation of the dynamic node and use adaptive parameter to calculate nodes'own accepting probability.Instead of number of hops,we use traveling time,which includes not only the number of hops for a particle to jump from the source node to the destination but also the time that the particle stays in the queues of nodes,to evaluate the search ability of Brownian particles.In the end,we propose an absorption strategy to deal with the additional Brownian particles in networks.The experiment results show that the strategy has a strong anti-congestion and a wide range of application4.Research on reliable path search based on path reliability and arrival reliability.Inspired by the shortest path algorithm,a polynomial time heuristic algorithm based on path reliability(PR)is proposed for solving the reliable path finding problem.The reliable path from the origin node r to destination node s can be found by tracing the predecessor node back to the origin node.To overcome the shortcoming of above method,such as difficult toset the threshold value,we propose an arrival reliability(AR)based method to find the path.Finally,the performance evaluation results based on OPNET on the designed scene show that the protocol provides energy-efficiency,reliability,and lower average report delay in wireless sensor networks.