软件学报
軟件學報
연건학보
JOURNAL OF SOFTWARE
2009年
2期
425-436
,共12页
郭欣%马文超%郭子华%侯紫峰
郭訢%馬文超%郭子華%侯紫峰
곽흔%마문초%곽자화%후자봉
多跳中继%资源复用%图论模型%调度算法%近似算法
多跳中繼%資源複用%圖論模型%調度算法%近似算法
다도중계%자원복용%도론모형%조도산법%근사산법
建立了中继网络资源复用问题的图论模型,依据该模型设计了自适应资源复用调度算法ARRS(adaptive resource reuse scheduling),以提高中继网络资源利用率.由于ARRS算法的核心步骤涉及顶加权图G(V,E,W)的染色,是NP-hard问题,为此给出了求解最优资源复用约束的顶加权图染色的近似算法ARRS_Greedy.该算法被证明具有时间复杂度O(|V|2),近似比为é(D+1)/2ù(D表示图G顶点度数的最大值).该近似比是紧的.仿真分析验证了近似算法ARRS_Greedy在应用中取得了与最优解非常接近的性能,证明了ARRS算法能够动态适应网络状态变化,因而与现有算法相比大幅度提高了系统容量.
建立瞭中繼網絡資源複用問題的圖論模型,依據該模型設計瞭自適應資源複用調度算法ARRS(adaptive resource reuse scheduling),以提高中繼網絡資源利用率.由于ARRS算法的覈心步驟涉及頂加權圖G(V,E,W)的染色,是NP-hard問題,為此給齣瞭求解最優資源複用約束的頂加權圖染色的近似算法ARRS_Greedy.該算法被證明具有時間複雜度O(|V|2),近似比為é(D+1)/2ù(D錶示圖G頂點度數的最大值).該近似比是緊的.倣真分析驗證瞭近似算法ARRS_Greedy在應用中取得瞭與最優解非常接近的性能,證明瞭ARRS算法能夠動態適應網絡狀態變化,因而與現有算法相比大幅度提高瞭繫統容量.
건립료중계망락자원복용문제적도론모형,의거해모형설계료자괄응자원복용조도산법ARRS(adaptive resource reuse scheduling),이제고중계망락자원이용솔.유우ARRS산법적핵심보취섭급정가권도G(V,E,W)적염색,시NP-hard문제,위차급출료구해최우자원복용약속적정가권도염색적근사산법ARRS_Greedy.해산법피증명구유시간복잡도O(|V|2),근사비위é(D+1)/2ù(D표시도G정점도수적최대치).해근사비시긴적.방진분석험증료근사산법ARRS_Greedy재응용중취득료여최우해비상접근적성능,증명료ARRS산법능구동태괄응망락상태변화,인이여현유산법상비대폭도제고료계통용량.
