欢迎访问中国科学院大学学报,今天是

中国科学院大学学报 ›› 2010, Vol. 27 ›› Issue (4): 530-537.DOI: 10.7523/j.issn.2095-6134.2010.4.015

• 论文 • 上一篇    下一篇

无线中继网络的联合路由与调度的近似最优算法

孙绍峰, 卫国   

  1. 中国科学技术大学无线网络通信安徽省重点实验室,合肥 230027
  • 收稿日期:2009-12-02 修回日期:2010-02-20 发布日期:2010-07-15
  • 通讯作者: 孙绍峰
  • 基金资助:

    国家重点基础研究973计划(2007CB310602)资助 

Approximate algorithm for joint routing and scheduling in wireless relay networks

SUN Shao-Feng, WEI Guo   

  1. Wireless Information Network Laboratory, University of Science and Technology of China, Hefei 230027, China
  • Received:2009-12-02 Revised:2010-02-20 Published:2010-07-15

摘要:

在基于802.16j的无线中继网络中,考虑路由和调度的联合优化问题,最小化系统总调度时间. 首先采用线性规划的方法建立路由,进行链路业务速率分配,然后基于平移和交换思想提出一种链路调度算法. 理论分析证明所提算法的性能在最坏情况下,不会超过最优性能的1.5倍. 仿真结果表明,所提算法的平均性能非常接近最优性能.

关键词: 无线中继网络, 路由, 调度, 近似算法

Abstract:

The problem of joint routing and scheduling in 802.16j based wireless relay networks is studied to minimize the traffic time. The routing problem is solved by linear programming method, and the traffic is allocated to links. A novel link scheduling algorithm based on shifting and switching is proposed. Theoretical analysis indicates that the performance of the proposed algorithm is within a factor of 1.5 of that of any optimal algorithm in the worst case. Simulation results show that with the proposed algorithm near-optimal performance can be effectively achieved.

Key words: wireless relay networks, routing, scheduling, approximate algorithm

中图分类号: