摘要
网络编码是一种新的网络传输技术,能够充分利用网络的理论组播速率上限.讨论了在网络编码下综合考虑编码开销和网络链路开销的网络总开销优化问题,将由网络编码引起的编码开销同样纳入优化问题的考虑范围.给出了2种各有优劣的网络信息流模型描述这一问题,并在不同模型下定义了2种开销的一般形式.由于这一优化问题属于NP难问题,目前一般采用启发式算法获得近似的优化解.随后的实验中,在不同规模的拓扑下对比了基于2种不同信息流模型的启发式算法的性能.由于考虑了编码开销使得联合优化问题远比链路开销优化问题复杂,模拟实验显示,只有当编码开销与链路开销价值系数之比达到1000以上时,才能获得比单纯链路优化更小的总开销.在提出基于遗传算法的方案之前,还简单地讨论了联合优化问题的复杂度.
Network coding is a kind of novel network transmission technology, which can achieve the network multicast capacity. In this paper, an overhead optimization problem （OOS） is presented to minimize the sum cost of network coding and network link in networks with network coding. This optimization takes not only the link transmission overhead but also the coding overhead incurred by network coding into consideration. By using two different network information flow models, which are the receivers＇ data flow mixture model and the data element flow model, the general forms of both kinds of overhead are presented separately. As this problem is NP-hard, only the approximately optimized solution can be got through heuristic algorithms. In the experiments, different genetic algorithms＇ performance are evaluated under two different information flow models and different random generated topologies. Because it makes the optimization problem even more complex that takes the network coding overhead into consideration, the computed approximate solution may be poorer than only considering the network link cost. Simulation results show that only under the condition of the overhead coefficient 7～1000, the joint optimization can get a better solution. This result may have considerable importance when network coding comes into practice in the future.
出处
《计算机研究与发展》
EI
CSCD
北大核心
2010年第3期390-397,共8页
Journal of Computer Research and Development
基金
国家自然科学基金项目(60702054)
上海市科委启明星计划基金项目(08QA14009)
上海市教育发展基金会晨光计划项目(2007CG07)
上海市科委科技攻关基金项目(08dz150010E)
关键词
网络编码
联合优化
编码开销
遗传算法
网络信息流
network coding
joint optimization
coding overhead
genetic algorithm
network information flow
