物理干扰模型下多跳无线网络的链路调度算法研究

项目名称： 物理干扰模型下多跳无线网络的链路调度算法研究

项目编号： No.61272474

项目类型： 面上项目

立项/批准年度： 2013

项目学科： 自动化技术、计算机技术

项目作者： 李忠诚

作者单位： 中国科学院计算技术研究所

项目金额： 82万元

中文摘要： 链路调度问题是多跳无线网络中的一个基本问题。目前关于链路调度算法的主要结果都是基于二进制干扰模型的。二进制干扰模型过于简化了实际无线通信中的干扰限制。尽管物理干扰模型可以更准确地反应物理现实，但是在物理干扰模型下链路调度问题变得异常难。目前关于物理干扰模型下的调度工作仍很少，并且主要集中在容量问题和最小长度调度问题上，对于以吞吐量最大化为目标的调度问题的研究很缺乏。吞吐量作为链路调度算法的一个重要性能指标，严重影响着多跳无线网络的公平性和总效用。为此，本课题将面向多跳无线网络，研究物理干扰模型下以吞吐量最大化为目标的链路调度问题，从算法优化的角度出发，提出具有理论吞吐量保证的链路调度算法，以提高多跳无线网络的整体吞吐性能，同时降低调度算法的计算复杂度和通信开销。

中文关键词： 链路调度；多跳无线网络；物理干扰；信道接入；最大权重独立集合

英文摘要： Link scheduling is a fundamental problem for multi-hop wireless networks. The majority of results on link scheduling assume binary interference models which simplify interference constraints in actual wireless communication. While the physical interference model reflects the physical reality more precisely, the problem becomes notoriously harder under the physical interference model. There have been just a few existing results on link scheduling under the physical interference model, the majority of which focus on the capacity maximization problem and the minimum scheduling length problem, even fewer on the scheduling problem for throughput maximization. Throughput is one of the main benchmark for link scheduling algorithms, which seriously influences the fairness and utility of the whole network. The proposal will study the throughput-maximizing link scheduling problem for multi-hop wireless networks under the physical interference model from a algorithm optimization view. It will propose link scheduling algorithms with theoretical guarantee on achievable capacity region to improve overall throughput of the network, also to reduce the corresponding computation complexity and communication overhead.

英文关键词： link scheduling；multi-hop wireless networks；physical interference；channel access；maximum weighted independent set