第2期 钟珞，等：求解最小MPR集的蚁群算法与仿真 ·169 100 100 100 95 95 95 90 90 90 函85 里5 的 85 80 80F 80 5 六 小3 75 MMni 20 406080100 00 20 4060 80100 100 406080100 t/s t/s (a)Ant-Cycle茯型 (b)Ant-Quantity模型 (c)Ant-Density模型 图5 采用拓扑结构(I)的3种模型的收敛曲线 Fig.5 The convergence curves of three types of models based on topology graph(I 130 130 130 125 9 120 115 I15 115 10 110 105 年 105 105 100 100 95 95 90 90 ww % 85 中 50 100 800 50 100 80 50 100 t/s tis (a)Ant-Cycle模型 (b)Ant-Quantity模型 (c)Ant-Density模型 图6采用拓扑结构（Ⅱ）的3种模型收敛曲线 Fig.6 The convergence curves of three types of models based on topology graph(II) 由图5可知Ant-Cycle模型的收敛速度较快，那 2)被点名的节点收到点名包后，启动计时器并 么在第1种拓扑结构中采用Ant-Cycle模型较好.由 逐个从数据包队列中取出数据包并发给主节点；如 图6可知Ant-Cycle模型和Ant-Density模型的收敛 果数据包发送完毕，则向主节点回复完毕信息， 效果大致相似，第2种拓扑结构可以采用其中任一 3)主节点接到数据完毕信息，立即点名下个节点 种模型.从实验中可知，可根据具体的问题来采选择 基于本文需求，设计了如图7所示的仿真节点 模型.但该算法是以收敛速度为代价来提高正确率； 模型，其中包括4个基本功能：产生包、处理包、接 在时间复杂度上要高于贪心策略的启发式算法。 收/发送包和定时控制（图7中用实线框分开） OPNET仿真 在所设计的节点模型中设计了多个进程模块， 4 此处仅以pk_deal进程模块的设计为例进行说明. 4.1模型设计 在pk_deal模块中，强制状态有：from_src、from_ra 采用OPNET工具，并设计点对多点的点名呼叫 dio、init、MPR,非强制状态：idle.其中MPR状态包含 工作方式的仿真模型，通过仿真结果说明数据连通 了以上蚁群算法，主要是计算节点的最小MPR集 性、数据一致性等来验证以所提算法的可行性 (选择Ant-Cycle模型)，便于后面数据包的发送.带 点对多点的点名呼叫工作方式的设计 箭头的线表示状态转移方向，其旁边括号内的字符 1)主节点依次给网络中的所有节点发送点名包， 串表示状态转移条件.如图8所示