Research On The Application Of Ant Colony Optimization For MPR Set Selection In MANET

Mobile Ad hoc networks(MANET) is a special self-organized communication network with multiple hops composed by mobile devices. Compared with other networks, MANET receives more and more concern for its flexibility and robustness, and plays an important part in the research of communication techniques.Multipoint Relay(MPR) is a mechanism to reduce the number of redundant retransmissions and flooding messages, so it reduces the overhead in Mobile Ad hoc networks. The elements in the MPR set of a given node in the network can only be selected from the set composed by the 1-hop neighbors of the given node, and all the 2-hop neighbors of the given node can be dominated by the nodes in the MPR set. However, the selection of MPR set with minimum size is NP-hard, the original greedy algorithm doesn't work well, especially in the dense networks.To solve this problem, we use the ant colony optimization (ACO) for the MPR set selection, then propose an improved ACO algorithm called CSACO based on the concept of candidate solution. By using candidate solution set to update the pheromone, the speed of convergence is improved and the premature convergence is effectively avoided. Finally, the simulation results are presented to show that CSACO performs well in different scenarios: It significantly reduces the degree of the MPR set, and obtains the convergence in a shorter time.The main work of this paper includes the following:1) Summarize and analysis the common routing protocols in MANET. After studying the principle of Multipoint Relay mechanism, we introduce the existing MPR selection methods, and present the analysis of their advantages and disadvantage.2) Based on the learning of the Ant Colony Optimization, an ACO model to solve the MPR selection problem is proposed. We discuss every part of the model in detail, including the design of the fitness function, the probability equation for the selection, and the update equation for the pheromone. Simulations under different network scenarios are used to verify the validity of our model, and we analyze the simulation data of each scenario. The simulation results are presented to show that the new MPR selection method produces better solutions.3) To solve the problem of premature convergence and slow speed of ACO, on the basis of the existing improved ACO mechanism, we propose a new improved ACO algorithm called CSACO based on the concept of candidate solution. By using candidate solution set to update the pheromone, the speed of convergence is improved and the premature convergence is effectively avoided. Finally, the simulation results are presented to show that: compared with several other MPR selection methods, CSACO receives a better performance in different scenarios: It significantly reduces the degree of the MPR set, and obtains the convergence in a shorter time.