基于超图模型和相继干扰消除的链路调度问题的研究

摘要

随着无线技术的快速发展和日益成熟，无线传感器网络的应用已经从军事领域步入了人们的日常生活，给我们的生活带来了翻天覆地的变化。与有线网络相比，无线网络共享信道的特性使得无线传感器网络中的数据传输通常由于不同数据之间的相互冲突而失败，因此我们不得不重新传输这些冲突的数据以便能使目的节点正确接收所需信息。这也降低了网络的吞吐量。通过适当的链路调度策略减少网络中数据的冲突是提高网络吞吐量的有效方法之一。
　　无线网络中的链路调度按照调度目的可以简单分为最大链路调度问题（Maximum Link Scheduling Problem，MaxLSP）和最短链路调度问题（ Shortest Link Scheduling Problem，SLS）。前者目标是给定一个链路集合12L?{l，l,...，ln}，计算最大可能的链路子集合S?L使得当集合中的链路同时调度时它们相互之间不发生冲突。后者的目标是在尽可能短的时间内调度网络中需要调度的所有链路。
　　本文在分析现有工作的基础上，对于最短链路调度问题，我们分别利用超图模型和相继干扰消除（Successive Interference Cancellation，SIC）改进了现有的算法，通过理论和仿真，我们证明了改进后的算法与已存的算法相比在调度长度上有较好的性能；对于最大链路调度问题，利用SIC的特性，我们同样改进了已有的算法，通过理论和仿真，我们给出了改进后算法与已有算法的性能之比。
　　本文共包含5章。在第1章中我们简单的介绍了无线传感器网络的概念、常见应用领域和本文选题的意义。在第2章中我们介绍了研究链路调度算法时经常用的模型以及在本文中所用的术语及相关定义。第3章对于最短链路调度问题，在总结已有算法的基础上，我们结合功率分配在SINR模型和超图模型下，改进了一个已有的算法。我们在这一章中给出了改进后算法正确性、调度长度、时间复杂度、与已有算法在调度长度上的近似比等证明，在这一章的最后我们给出了仿真验证。第4章，对于最短链路调度问题结合前一章中对于该问题的研究，利用SIC技术我们提出了另外一个改进后的算法，对于最大链路调度问题，通过使用SIC，我们改进了已有的算法。在这一章中，我们从理论上证明了改进后算法的正确性、有效性，并且通过仿真对该算法进行了验证。
　　在第5章中，我们总结了本文所研究的最短链路调度和最大链路调度问题，并对于下一步将要进行的工作进行了展望。

目录

封面

声明

中文摘要

英文摘要

目录

第1章 绪论

1.1 无线传感器网络概述

1.2 链路调度问题的研究意义

1.3 论文的组织结构

第2章 干扰模型和相关定义

2.1 链路调度问题研究中常用干扰模型

2.2 链路调度问题研究中常见定义及术语

2.3 本章小结

第3章 基于超图模型和SINR模型下的SLS近似算法

3.1 干扰模型和定义

3.2 基于超图模型的SLS算法 pcSLS

3.3 理论证明

3.4 仿真结果

3.5 本章小结

第4章 基于相继干扰消除的近似算法及仿真结果

4.1 模型和定义

4.2 SICMaxLS近似算法

4.3 基于干扰消除的MaxLSP算法（DMaxLSP-SIC）

4.4 基于相继干扰消除的SLS算法（IAASLS）

4.5 仿真结果与分析

4.6 本章小结

第5章 总结与展望

5.1 总结

5.2 展望

参考文献

在读期间发表的学术论文及研究成果

致谢