基于模拟退火的流量矩阵估计

Traffic matrix estimation based on simulated anneals

OD(Origin-Destination)流量估计用以获得网络流量在各个OD对间的分布情况,在网络优化、管理和网络异常的检测与识别等方面具有重要意义。模拟退火算法是一种全局的最优化技术,运行效率高,将其应用于OD流估计中,有助于降低求解的复杂性,并取得较高精度。提出了一种基于模拟退火的流量矩阵估计方法,首先采用IPF算法(Iterative Proportional Fitting algorithm)校正后的历史均值作为模拟退火初始值;在模拟退火过程中,利用链路流量信息来缩小模拟退火解的搜索空间,以达到提高算法的估计精度及实时性的目的。采用Abilene网络实际数据的仿真结果表明,该文方法能够取得较高的OD流估计精度,且计算效率明显优于现有的广义重力模型方法。

OD（Origin-Destination） traffic estimation is often used to acquire the distribution between OD pairs,it is significant to network optimization,management and traffic anomaly detection as well.Simulated anneals algorithm is an overall optimization technology with high efficiency.Applying it in the field of OD traffic estimation helps to reduce the complexity of solving process,and achieve high precision.This paper proposes an OD traffic estimation method based on simulated anneals algorithm.First, it uses historical mean adjusted by iterative proportional fitting algorithm as the initial of simulated anneals algorithm;then,during the process of simulated anneals,it exploits the information of link traffic to reduce searching space about its solution,so as to improve precision and increase computing speed.Simulations using Abilene traffic demonstrate that the method can achieve higher precision of OD traffic estimation,and is superior to generalized gravity model method in computing efficiency.