求解最小MPR集的蚁群算法与仿真

An ant colony algorithm and simulation for solving minimum MPR sets

在分析利用贪心策略启发式算法求解最小MPR集的缺陷基础上,引入蚁群算法对最小MPR集进行求解.首先定义了节点及其出度和入度,并根据节点的出度和入度限制,给出了求解最小MPR集的蚁群算法.然后,对蚁群算法的3种模型Ant-Cycle、Ant-Quantity和Ant-Density加以改进,并对这3种改进模型的收敛性进行分析与实验.实验采用了圆形分布和理想均匀分布2种拓扑结构,前者实验结果表明Ant-Cycle模型的收敛速度较快,后者结果表明Ant-Cycle模型和Ant-Density模型各有优势.因此,最小MPR集的蚁群算法的模型选择需依据拓扑结构确定.最后,使用OPNET基于该算法对数据链的点对多点的点名呼叫工作方式进行模拟仿真,选择的统计量显示了节点的连通性和数据一致性,验证了该算法的合理性.

Based on analyzing the defects of a heuristic algorithm of greedy strategy,an ant colony algorithm was imported to solve the minimum MPR set.First of all,a node and its out and in-degrees were defined,and in accordance with the out and in-degree constraints of the node,ant colony algorithms were given based on the graphics to find the minimum MPR set.Then,three kinds of ant colony algorithm models,the Ant-Cycle,Ant-Quantity,and Ant-Density models,were improved,and the convergence curves of the three kinds of models were analyzed and tested.An ideal uniform topology and a circular distribution topology were both used in experiments.Former experimental results showed that the Ant-Cycle model was faster in convergence speed;the latter results showed that the Ant-Cycle and Ant-Density models both have advantages.Therefore,ant colony algorithm model selection of the minimum MPR set might be subject to topology.Finally,OPNET was used based on the above algorithm for simulation.It adopted the data link＇s point-to-multipoint calling mode.The selected statistics show connectivity and data consistency among the nodes,which means that the algorithm is reasonable.