| 波分复用星形单跳网中3信道的传输调度问题 |
| |
| 引用本文： | 戴珍香,李曙光,亓兴勤.波分复用星形单跳网中3信道的传输调度问题[J].山东大学学报(理学版),2007,42(2):46-50. |
| |
| 作者姓名： | 戴珍香 李曙光 亓兴勤 |
| |
| 作者单位： | 1. 山东大学,数学与系统科学学院,山东,济南,250100;烟台大学,数学与信息科学学院,山东,烟台,264005
2. 山东大学,威海分校应用数学系,山东,威海,264209 |
| |
| 摘 要： | 考虑波分复用星形单跳网中的数据包传输调度问题, 假定诸发送机频率可调, 而接收机频率固定. 当m≥2时, 这一调度问题是NP-完备的, m表示所拥有的信道数目. 对目前所知最好的一个2-近似算法进行了精细的分析, 证明了m=3时, 该算法近似比为7/4, 并通过实例说明此结果为最佳可能.
|
| 关 键 词： | 波分复用 星形网 单跳 数据包传输调度 调谐时延 近似算法 最坏情形分析 |
| 文章编号： | 1671-9352（2007）02-0046-05 |
| 收稿时间： | 2005-10-27 |
| 修稿时间： | 2005-10-27 |
Three-channel transmission scheduling in WDM star single-hop networks |
| |
| DAI Zhen-xiang,LI Shu-guang,QI Xing-qin.Three-channel transmission scheduling in WDM star single-hop networks[J].Journal of Shandong University,2007,42(2):46-50. |
| |
| Authors: | DAI Zhen-xiang LI Shu-guang QI Xing-qin |
| |
| Institution: | 1. School of Math. and System Sci,, Shandong Univ. , Jinan 250100, Shandong, China; 2. School of Math. and Info. Sci., Yantai Univ., Yantai 264005, Shandong, China; 3. Department of Applied Math., Shandong University at Weihai, Weihai 264209, Shandong, China |
| |
| 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. |
| |
| Keywords: | WDM star networks single-hop packet transmission scheduling tuning delay approximation algorithms worst-case analysis |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《山东大学学报(理学版)》浏览原始摘要信息 |
| 点击此处可从《山东大学学报(理学版)》下载免费的PDF全文 |
|
