多跳中继无线网络资源复用的建模及算法设计

• 作者: 侯紫峰 郭子华 郭欣 马文超
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 多跳中继 资源复用 图论模型 调度算法 近似算法
• 年，卷（期）: 2009,（2）
• 所属期刊栏目: 计算机网络与信息安全
• 页码范围: 425-436
• 页数: 12页
• 分类号: TP393
• 字数: 10121字
• 语种: 中文
• DOI: 10.3724/SP.J.1001.2009.03204

摘要

建立了中继网络资源复用问题的图论模型,依据该模型设计了自适应资源复用调度算法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算法能够动态适应网络状态变化,因而与现有算法相比大幅度提高了系统容量.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	侯紫峰		40	444	12.0	19.0
5	马文超		2	10	2.0	2.0
6	郭欣	中国科学技术大学计算机科学与技术系	6	30	3.0	5.0
7	郭子华		4	13	3.0	3.0