用column generation算法规划网络编码业务  

Network coding traffic design using column generation techniques

作　　者：宋运吉[1] 王晟[1] 王雄[1] 

机构地区：[1]电子科技大学宽带光纤传输与通信网络技术教育部重点实验室,成都610054

出　　处：《计算机应用》2008年第8期1951-1953,共3页journal of Computer Applications

基　　金：国家973计划项目(2007CB307100);国家自然科学基金资助项目(60472008);四川省青年科技基金项目(05ZQ026-002)

摘　　要：网络编码能够有效降低网络中关键边的资源消耗,改善网络的负载均衡。但是普通的启发式路由算法通常只能为单个业务寻找最优路由,无法优化网络的整体性能。运用column generation算法对网络编码业务进行规划,为松弛系数赋予具体的物理含义,并据此进行路径更新,有针对性地为每个业务寻找路由。与启发式算法相比,column generation从整体上提高了网络的吞吐量,改善了网络的负载均衡。同时,与普通ILP算法相比,column generation算法无需计算大量备选路径,且函数始终处于收敛状态,不会产生振荡,求解总时间缩短了23.5%,总代价优化2.5%。Network coding can reduce the cost of key links and improve the load balance of the network. But heuristic routing algorithms cannot find the global optimal solution for the network, We used column generation to solve the Network Coding based traffic programming problem. First, we relaxed the constraints of the problem by using Lagrange Relaxation, then defined the physical meaning of each relaxation variable. At last, used relaxation variables updating the muhicast graph in iteration. Compared with the heuristic routing algorithm, column generation can improve the network throughput, compared with Integer Linear Programming （ ILP）. It can compute less inventory routings and accelerate convergence.

关 键 词：网络编码 整数线性规划 网络吞吐量 

分 类 号：TP393.02[自动化与计算机技术—计算机应用技术]