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

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.

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

链路调度问题是多跳无线网络中的一个基本问题。本课题面向多跳无线网络，研究物理干扰模型下以吞吐量最大化为目标的链路调度问题，重点解决了单信道多跳无线网络下的链路调度问题，取得以下创新性研究成果：.1) 单信道多跳无线网络物理干扰模型下集中式链路调度算法研究.已有相关研究工作需要针对不同的发送功率分配方式设计不同的链路调度算法且这些算法理论上保证可达到的吞吐空间仍待提高。我们提出了物理干扰模型下通用有效的集中式链路调度算法。当链路发送功率为固定分配方式时，提出了一种适用于任意固定功率分配方式的链路调度算法。当链路发送功率为可变分配方式时，提出了一种联合功率分配的链路调度算法。算法可以达到的理论吞吐空间与网络的规模以及网络中队列的动态变化无关，不会随着网络规模的增加或者队列长度的增加而恶化。仿真实验结果验证了这两个算法的有效性。.2) 单信道多跳无线网络物理干扰模型下分布式链路调度算法研究.目前物理干扰模型下分布式链路调度算法没有有效的理论保证且通信复杂度高。我们提出了物理干扰模型下oblivious和uniform这两种常用固定发送功率分配方式下低复杂度且具有理论保证的分布式链路调度算法。在oblivious发送功率分配方式下，证明所提的链路调度算法在理论上可达到常数近似的最优吞吐空间。在uniform发送功率分配方式下，证明所提的链路调度算法在理论上可达到对数近似的最优吞吐空间。在这两个分布式链路调度算法的执行过程中，每个节点只需要收集常数邻居范围内的链路调度和状态信息，无需在全网范围内广播和收集信息，极大降低了通信复杂度。仿真实验结果表明，所提的两个算法所达到的吞吐性能明显优于对比算法。.整个项目进展顺利，截止到目前为止，该项目的计划工作均已顺利完成。在本项目的开展过程中，我们共发表/录用论文16篇，其中国际期刊论文5篇（顶级国际期刊论文IEEE TPDS一篇（CCF A类））、国际学术会议论文9篇（顶级国际学术会议论文IEEE INFOCOM一篇（CCF A类））；取得专利授权两项，专利申请三项。