波分复用星形单跳网中3信道的传输调度问题  

Three-channel transmission scheduling in WDM star single-hop networks

作　　者：戴珍香[1] 李曙光[1] 亓兴勤[2] 

机构地区：[1]山东大学数学与系统科学学院 [2]山东大学威海分校应用数学系,山东威海264209

出　　处：《山东大学学报（理学版）》2007年第2期46-50,55,共6页Journal of Shandong University(Natural Science)

基　　金：国家自然科学基金资助项目(60373025)

摘　　要：考虑波分复用星形单跳网中的数据包传输调度问题,假定诸发送机频率可调,而接收机频率固定.当m 2时,这一调度问题是NP-完备的,m表示所拥有的信道数目.对目前所知最好的一个2-近似算法进行了精细的分析,证明了m=3时,该算法近似比为74,并通过实例说明此结果为最佳可能.The problem of scheduling packet transmissions in WDM star single-hop networks with tunable transmitters and fixedtuned receivers is considered. It is NP-complete for any fixed m≥2, where m is the number of available channels. By rigorous analysis, the worst-case performance ratio of the current approximation Rnown as the best algorithm for this problem is reduced to 7 /4 for three channels. An example is presented to show that this result is the best possible.

关 键 词：波分复用 星形网 单跳 数据包传输调度 调谐时延 近似算法 最坏情形分析 

分 类 号：O157.5[理学—数学] TP301[理学—基础数学]