学位论文 > 优秀研究生学位论文题录展示

环型网络的信息通过量问题

作　者: 陈树强
导　师: 方奇志
学　校: 中国海洋大学
专　业: 运筹学与控制论
关键词: 环形SONET NP-困难近似算法路由负载平衡信息通过量
分类号: TN929.11
类　型: 硕士论文
年　份: 2008年
下　载: 13次
引　用: 0次
阅　读: 论文下载

内容摘要

同步光纤网络(SONET)在当今网络通讯技术中被普遍应用。分布在网络各节点处的设备控制网络的容量,且SONET网络的费用随着其容量的增加而增加。针对环型SONET上的一组信息发送请求,设计一个路由算法来确定各条信息被传送的方向,使得传送所有信息所必需的带宽达到最小,该问题称为路由负载平衡问题。而如果网络带宽本身是有限制的,则要求我们设计路由选择算法来确定各条信息的传送策略-包括顺时针传送、逆时针传送和放弃传送,使得在不超过带宽限制的前提下,被传送的信息总量达到最大,该问题称为信息通过量问题。对于信息通过量问题的研究具有很好的理论意义和应用前景。本文主要内容如下:对于环型SONET的路由负载平衡问题现有算法中的“线性规划舍入”技巧进行总结,分析一般信息权重情况下的近似算法的设计和在单位信息权重情况下的多项式时间精确算法的设计。对于环型SONET信息通过量问题进行深入研究,论证其NP-困难性、并通过改进“线性规划舍入”方法给出该问题的多项式时间近似算法和近似度估计。

全文目录

摘要  4-5
Abstract  5-7
第1章综述  7-13
  1.1 SONET路由问题的背景  7-8
  1.2 研究现状  8-13
第2章环型SONET路由负载平衡问题的研究方法及其复杂性  13-22
  2.1 问题的描述  13-14
  2.2 1 + 3D/2 近似算法  14-17
  2.3 PTAS算法  17-19
  2.4 单位权重情况下的精确算法  19-22
第3章环型SONET信息通过量问题  22-33
  3.1 信息通过量问题及其计算复杂性  22-24
  3.2 信息通过量问题的整数规划模型  24-25
  3.3 信息通过量问题的近似算法  25-31
    3.3.1 线性规划松弛  26-27
    3.3.2 转化为平行解  27
    3.3.3 利用“LP舍入技术”得到半整解  27-30
    3.3.4 利用“LP舍入技术”得到整数解  30-31
  3.4 结论  31-33
参考文献  33-36
致谢  36-37
攻读硕士学位期间完成的文章  37

环型网络的信息通过量问题

内容摘要

全文目录

相似论文