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

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

戴珍香¹^,²，李曙光¹^,²，亓兴勤³

1. 山东大学数学与系统科学学院，山东济南250100； 2. 烟台大学数学与信息科学学院，山东烟台264005；3. 山东大学威海分校应用数学系，山东威海264209

收稿日期:2005-10-27 修回日期:1900-01-01 出版日期:2006-10-24 发布日期:2006-10-24
通讯作者: 戴珍香

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

DAI Zhen-xiang¹^,²，LI Shu-guang¹^,² and QI Xing-qin³

1. School of Math. and System Sci., Shandong Univ. , Jinan 250100;2. School of Math. and Info. Sci., Yantai Univ., Yantai 264005;3. Department of Applied Math., Shandong University at Weihai, Weihai 264209

Received:2005-10-27 Revised:1900-01-01 Online:2006-10-24 Published:2006-10-24
Contact: DAI Zhen-xiang

摘要/Abstract

摘要： 考虑波分复用星形单跳网中的数据包传输调度问题, 假定诸发送机频率可调, 而接收机频率固定. 当m≥2时, 这一调度问题是NP-完备的, m表示所拥有的信道数目. 对目前所知最好的一个2-近似算法进行了精细的分析, 证明了m=3时, 该算法近似比为7/4, 并通过实例说明此结果为最佳可能.

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

Abstract: The problem of scheduling packet transmissions in WDM star single-hop networks with tunable transmitters and fixedtuned receivers is considered. It is NP-complete for any fixed m≥2， where m is the number of available channels. By a rigorous analysis, the worstcase performance ratio of the currently 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 best possible.

Key words: worst-case analysis , approximation algorithms, tuning delay, packet transmission scheduling, single-hop, star networks, WDM

中图分类号:

O157.5

戴珍香,李曙光,亓兴勤 . 波分复用星形单跳网中3信道的传输调度问题[J]. J4, 2007, 42(2): 46-50 .

DAI Zhen-xiang,LI Shu-guang,and QI Xing-qin . Three-channel transmission scheduling in WDM star single-hop networks[J]. J4, 2007, 42(2): 46-50 .

参考文献

相关文章 9

[1]	蔡裕华,魏凤英*. 度量空间的概率近似算法[J]. J4, 2013, 48(09): 51-55.
[2]	杨朝霞 . 超图嵌入带权重圈的一个2-近似算法[J]. J4, 2008, 43(8): 11-13 .
[3]	杨振光,李曙光,王秀红 . 工件尺寸不同的并行机批调度问题[J]. J4, 2007, 42(4): 63-66 .
[4]	亓兴勤,曹静,张晨 . 环型二元序列的赋权对换排序问题[J]. J4, 2007, 42(12): 46-48 .
[5]	李曙光,白淑岩,何志红,亓兴勤 . 圈中t-区间的k-染色问题[J]. J4, 2006, 41(6): 40-42 .
[6]	李曙光,杨振光,何志红 . 多纤波分复用链网与环网中的利润极大化问题[J]. J4, 2006, 41(5): 7-11 .
[7]	王继强, . 一类median问题的近似算法研究[J]. J4, 2006, 41(4): 1-03 .
[8]	李曙光,亓兴勤,何志红 . 环网络中的呼叫接纳控制[J]. J4, 2006, 41(4): 15-19 .
[9]	亓兴勤,何志红,赵洪銮 . 二元序列的赋权对换排序问题[J]. J4, 2006, 41(1): 82-85 .

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed