最小MPR集选取问题的改进蚁群优化算法

Minimum MPR Set Selection: an Improved Ant Colony Optimization Approach

多点中继(MPR)是移动自组网中用来降低网络开销所采用的一种机制,但由于最小MPR集的选取属于NP完全问题,传统的贪心算法往往难以取得较好的结果.本文将蚁群优化用于最小MPR集选取问题的求解,给出了一种基于候选解的改进蚁群算法CSACO.通过使用候选解集进行信息素的更新,提高了算法的收敛速度,同时避免了算法陷入早熟.模拟实验表明,CSACO可以有效降低MPR集的大小,同时在较短的时间内收敛到最优解,提高网络性能.

Multipoint Relay （MPR） is a mechanism to reduce the overhead in Mobile Ad hoe networks. However, the selection of MPR set with minimum size is NP-hard, and the original greedy algorithm doesnt work well in most cases. In this paper, 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 soludon 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.