山东大学学报（理学版）
山東大學學報（理學版）
산동대학학보（이학판）
JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
2007年
2期
46-50,55
,共6页
波分复用%星形网%单跳%数据包传输调度%调谐时延%近似算法%最坏情形分析
波分複用%星形網%單跳%數據包傳輸調度%調諧時延%近似算法%最壞情形分析
파분복용%성형망%단도%수거포전수조도%조해시연%근사산법%최배정형분석
考虑波分复用星形单跳网中的数据包传输调度问题,假定诸发送机频率可调,而接收机频率固定.当m≥2时,这一调度问题是NP-完备的,m表示所拥有的信道数目.对目前所知最好的一个2-近似算法进行了精细的分析,证明了m=3时,该算法近似比为7/4,并通过实例说明此结果为最佳可能.
攷慮波分複用星形單跳網中的數據包傳輸調度問題,假定諸髮送機頻率可調,而接收機頻率固定.噹m≥2時,這一調度問題是NP-完備的,m錶示所擁有的信道數目.對目前所知最好的一箇2-近似算法進行瞭精細的分析,證明瞭m=3時,該算法近似比為7/4,併通過實例說明此結果為最佳可能.
고필파분복용성형단도망중적수거포전수조도문제,가정제발송궤빈솔가조,이접수궤빈솔고정.당m≥2시,저일조도문제시NP-완비적,m표시소옹유적신도수목.대목전소지최호적일개2-근사산법진행료정세적분석,증명료m=3시,해산법근사비위7/4,병통과실례설명차결과위최가가능.
