基于Petri网求解网络最大流的并发仿真方法

摘要

通过将网络映射为Petri网形式的大量Petri网仿真实验得知,没有任何控制且并发运行的网络,其流量不能总是自行达到理论最大值,究其原因在于托肯在路径选择时随机经过了易拥堵结点与不拥堵结点。针对性地采取相应的网络控制策略,对网络从库所参数、弧参数和变迁参数3个方面进行单一或组合的设置,使得托肯优先经过不拥堵结点。运行调整后的网络,托肯沿网络从起点出发在各个局部并发地移动,遍历每一可能达到的结点,直至终点,网络流量达到其理论最大值,网络流实现全局最优。基于Petri网求解网络最大流的并发仿真方法为大规模网络最大流问题的分布式计算提供了一个新思路。