无线传感网络中分布式资源分配和队列调度问题研究

摘要

无线传感网络被广泛应用在军事、工业、医疗、运输等领域，其作为时代的产物在未来将占据越来越重要的地位。这种网络通常由大量低功耗、低成本的传感节点构成。源节点负责收集所探测范围内的数据，并且通过中继节点以多跳方式将数据传递给汇聚节点。然而，由于无线传感网络中的传感节点主要通过能量有限的电池进行供电，并且有限的网络信道容量限制了数据速率在整个网络中的传输与分配，因此，如何通过有效分配网络资源和进行队列调度来保证无线传感网络的服务质量是确保网络性能的一个关键问题。此外，随着传感网络规模的不断增大和流量的快速增长，仅通过一个基站节点负责集中处理来自于各个汇聚节点的数据已经相当困难，如何通过节点和链路之间局部网络的信息交互分布式解决网络资源分配和队列调度问题，不仅可以大幅度改善网络性能，而且还能大大提高网络实际问题的求解速度。因此，如何在资源有限的情况下，通过快速优化算法来分布式解决网络资源分配和队列调度问题，是一项意义非常重大的研究课题。
　　本文在充分了解国内外有关无线传感网络分布式资源分配、队列调度和分布式算法研究现状的基础上，深入研究了资源有限和网络稳定约束下无线传感网络流控制优化问题和分布式快速优化算法，主要的工作和创新点包括:
　　(1)在单径、路由确定的无线传感网络情况下，提出了一种基于节点能量和链路容量共同约束的流控制问题模型。传统的网络效用最大化问题仅仅考虑了链路容量对网络性能的制约作用，而没有考虑到无线传感网络主要通过能量有限的电池进行供电这一实际特点。文章则考虑了这一有限资源对无线传感网络整体性能的影响。此外，传统意义上用来解决流控制问题的方法主要为对偶-次梯度算法，而在实际应用中，这一算法存在收敛速度慢、步长选择敏感等缺点，为了提高分布式优化算法的整体性能，文章设计了具有二阶收敛速度的分布式牛顿算法，研究结果和仿真实验表明，通过问题转化和使用矩阵分裂技术，该算法在与对偶次梯度算法交互信息几乎相同的情况下，运行时间和迭代次数远小于传统一阶求解算法，收敛速度提高将近两个数量级。
　　(2)在研究点(1)的研究基础上，把网络场景扩展到多径、路由不确定的情况中，进一步建立了一个能够实现效用比例公平的联合路由选择与流控制的效用最大化问题模型。与传统网络模型不同，该问题模型不仅考虑了链路容量、节点能量等有限资源对网络的限制，而且把资源传输时如何选择最优路由考虑在内。此外，为了实现流控制的效用比例公平，该研究点的优化目标选择了能够实现比例公平的“伪效用函数”。特别需要指出的是，由于该优化问题网络场景完全不同于前一问题（如多径、系数矩阵不满足行满秩、Hessian矩阵分块对角等），导致牛顿算法的分布式计算及其在网络内的执行过程与(1)完全不同。文章通过一系列问题等价转化、变量重组、使用矩阵分裂技术，最终实现了问题的高效求解。最后，文章用Matlab仿真平台验证了分布式牛顿算法的性能。
　　(3)提出了一个队列稳定、资源有限以及流无溢出（no-underflow constraints）约束情况下，关于如何调度队列以确保网络稳定、实现网络效用时间平均最大化的调度问题模型。此外，为了研究链路相互干扰时对无线传感网络队列调度性能的影响，文章在该模型的基础上进一步提出了干扰矩阵概念，引入了链路干扰约束模型，把前一问题模型扩展成链路有干扰情况下的资源队列调度问题。针对这两个问题，文章设计了基于李雅普优化方法和对偶理论的扰动最大加权算法(Perturbed Max-weight algorithm)，高效求解了有干扰和无干扰两种情况下的资源队列调度问题。最后，文章从理论上对这一算法性能进行了分析证明，并用Matlab仿真验证了算法的收敛性，研究表明该算法在保证网络队列稳定情况下，所得解与最优解之间的误差在(O)(1/V)以内，队列积压的时间平均与惩罚因子V满足(O)(V)关系。

目录

声明

摘要

第一章 绪论

1．1 论文的研究背景及意义

1．2 国内外研究现状

1．3 本文的主要工作

1．4 本文的组织结构

第二章 无线传感网中节点能量和链路容量约束的二阶分布式流控制方法

2．1 网络模型及问题描述

2．1．1 网络模型

2．1．2 能量模型

2．1．3 容量模型

2．1．4 问题描述

2．2 原始-对偶分解算法

2．3 二阶分布式分解算法

2．3．1 问题转化

2．3．2 集中式牛顿算法

2．3．3 分布式牛顿算法

2．4 仿真及性能分析

2．4．1 仿真参数设置及拓扑结构

2．4．2 算法性能分析

2．5 本章小结

第三章 无线传感网中联合路由选择与流控制的分布式牛顿算法

3．1 网络模型及问题描述

3．1．1 网络模型

3．1．2 流守恒模型

3．1．3 能量和容量模型

3．1．4 问题描述

3．2 问题求解

3．2．1 问题转化

3．2．2 集中式牛顿算法

3．2．3 分布式牛顿算法

3．3 信息交互及算法描述

3．4 仿真及性能分析

3．4．1 仿真参数设置及拓扑结构

3．4．2 算法性能分析

3．5 本章小结

第四章 无线传感网络中基于队列稳定和流控制的最优效用调度方法

4．1 网络模型及问题描述

4．1．1 网络模型

4．1．2 队列和容量模型

4．1．3 竞争模型

4．1．4 问题描述

4．2 扰动最大加权算法

4．2．1 无竞争问题模型优化

4．2．2 竞争问题模型优化

4．3 算法性能分析

4．4 仿真实验

4．4．1 仿真参数设置及拓扑结构

4．4．2 无竞争模型仿真性能分析

4．4．3 竞争模型仿真性能分析

4．5 本章小结

第五章 总结与展望

5．1 研究工作总结

5．2 进一步的研究方向

参考文献

致谢

攻读学位期间的研究成果