无线网络中的在线信道分配问题  

Online Channel Scheduling in Wireless Networks

作　　者：张韬[1] 

机构地区：[1]复旦大学计算机科学与工程系上海市智能信息处理重点实验室,上海200433

出　　处：《计算机研究与发展》2008年第z1期31-34,共4页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(60573025)

摘　　要：研究一个无线网络中信道分配的最大化问题.对该问题的离线版本给出了一个O(n2)时间的算法.对在线问题的一般情况,证明了k-look-ahead算法的下界至少为(k+2)/(k+1);还给出了一个竞争比为2的1-look-ahead算法.We consider an online maximization problem in wireless channel scheduling. We give an O(n2) algorithm for the offline version. For the online version we provide a natural lower bound of (k+2)?(k+1) in the general k-look-ahead setting, and a 2-competitive online algorithm in the 1-look-ahead setting.

关 键 词：在线算法 竞争比 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]