|
|||||
|
|
| 多跳中继无线网络资源复用的建模及算法设计 | |
| 引用本文： | 郭欣,马文超,郭子华,侯紫峰.多跳中继无线网络资源复用的建模及算法设计[J].软件学报,2009,20(2):425-436. |
| 作者姓名： | 郭欣 马文超 郭子华 侯紫峰 |
| 作者单位： | 1. 中国科学技术大学,计算机科学与技术系,安徽,合肥,230027 2. 联想研究院,北京,100085 3. 联想研究院,北京,100085;中国科学院,计算技术研究所,北京,100190 |
| 基金项目： | Supported by the National Natural Science Foundation of China under Grant No.90604029 (国家自然科学基金); the National Basic Research Program of China under Grant No.2003CB314801 (国家重点基础研究发展计划(973)) |
| 摘 要： | 建立了中继网络资源复用问题的图论模型,依据该模型设计了自适应资源复用调度算法ARRS(adaptive resource reuse scheduling),以提高中继网络资源利用率.由于ARRS算法的核心步骤涉及顶加权图G(V,E,W)的染色,是NP-hard问题,为此给出了求解最优资源复用约束的顶加权图染色的近似算法ARRS_Greedy.该算法被证明具有时间复杂度O(|V|2),近似比为?(Δ+1)/2?(Δ表示图G顶点度数的最大值).该近似比是紧的.仿真分析验证了近似算法ARRS_Greedy在应用中取得了与最优解非常接近的性能,证明了ARRS算法能够动态适应网络状态变化,因而与现有算法相比大幅度提高了系统容量. |
| 关 键 词： | 多跳中继 资源复用 图论模型 调度算法 近似算法 |
| 收稿时间： | 2007/7/16 0:00:00 |
| 修稿时间： | 9/6/2007 12:00:00 AM |
Modeling and Algorithm Designing of Resource Reuse for Multihop Relay Wireless Network |
|
| GUO Xin,MA Wen-Chao,GUO Zi-Hua and HOU Zi-Feng.Modeling and Algorithm Designing of Resource Reuse for Multihop Relay Wireless Network[J].Journal of Software,2009,20(2):425-436. | |
| Authors: | GUO Xin MA Wen-Chao GUO Zi-Hua and HOU Zi-Feng |
| Affiliation: | 1+;2;3;Department of Computer Science and Technology;University of Science and Technology of China;Hefei 230027;China;Lenovo Corporate Research & Development;Beijing 100085;China;Institute of Computing Technology;The Chinese Academy of Sciences;Beijing 100190;China |
| Abstract: | Two methods are presented to calculate the lower bound and upper bound on the bisection width of H-Torus topology. These two methods can also be applied to the 2D Torus topology. A method is presented to calculate the exact bisection width for H-Torus too. But this method has unacceptable complexity and can only be accepted with small scale. It is shown that H-Torus topology has larger bisection width. Regarding precision, the lower bound and upper bound introduced in this paper are greatly improved. This result strongly supports the design of scalable routers. |
| Keywords: | multihop relay resource reuse graph theory model scheduling algorithm approximation algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ | |
| 点击此处可从《软件学报》浏览原始摘要信息 | |
| 点击此处可从《软件学报》下载全文 | |