无线传感器网络中能量有效的节点调度机制研究

本项目以节点调度在无线传感器网络中的应用为基本背景，以减小覆盖集的大小为切入点，探索能进一步延长网络生存时间、适用范围广且实用强的节点调度机制，使之基本满足在无线传感器网络中的理论和应用的需要。从几何的角度出发，提出一种求解覆盖集问题的启发式算法，在选择节点时尽量避免产生"必然导致较多重叠的未被覆盖的点"，以进一步改善前期贪婪算法在覆盖集大小方面的性能，并将此算法推广至多重覆盖、部分覆盖等更复杂的情况，从而扩大适用范围和增强实用性；通过基于本地信息的最短路径的判别方法，提出一种统一考虑连通和覆盖条件的连通覆盖集的构造算法，在最小化工作节点向基站传输数据的能耗的基础上，减少工作节点的数目；提出一种覆盖集的动态维护算法，通过少量睡眠节点与工作节点之间的互换来减小盲区的尺寸，以增加盲区被单个节点完全覆盖的概率，并将覆盖集的构造与动态维护过程相结合，以减少节点调度的运行开销。

目前，网络生存时间仍然是无线传感器网络发展和应用的主要瓶颈。节点调度就是在保证网络服务质量的前提下，将一部分节点投入低功耗的睡眠状态，只保留部分节点工作，从而有效地降低系统整体能耗，延长网络生存时间。本项目基于几何覆盖的原理，系统深入地研究了无线传感器网络中的节点调度问题，主要研究内容和研究结果包括：.(1) 研究了覆盖集的构造问题，分别提出了一种基于蜂窝结构的传感器网络覆盖问题求解算法(BCS算法)和一种通过增量迭代方法构造最小覆盖集的近似算法(CCS算法)。在BCS算法中，在迭代构造过程的每一阶段，选择与蜂窝结构误差最小的节点，加入到初始为空的节点集合中，直至所有未选的节点都不能覆盖更多的区域。实验结果表明BCS算法的执行时间较短，在大部分实验场景下都可在1秒内执行完，在各个实验场景下得到的覆盖集的平均大小分别为现有的OGDC算法和CVT算法的93.8%和84.8%。在CCS算法中，在迭代过程中从最难覆盖的位置选择节点，不仅考虑候选节点对已覆盖区域的面积影响，也考虑候选节点对已覆盖区域的形状影响。实验结果表明CCS算法得到的覆盖集的大小为现有的OGDC算法的82.6%。.(2) 研究了覆盖增强问题，提出了一种贪婪迭代算法(GIA算法)，在每次迭代中，调整那些使得覆盖率增加最大的节点的感知方向，重复此迭代过程直至通过调整任一节点的感知方向已不能再增加覆盖率。此外，还提出了一种通过计算几何求解该算法中区域计算问题的方法，以提高计算精度和减少计算时间。实验结果表明该算法的执行时间较短，收敛速度较快，能够获得比现有算法更高的目标区域覆盖率。.(3) 研究了覆盖集的动态维护问题，提出了一种基于缩小盲区的覆盖集维护算法(MCS算法)，通过少量睡眠节点与工作节点之间的互换来缩小盲区的尺寸，以增加盲区被单个节点完全覆盖的概率，从而在失效覆盖集的基础上，仅通过置换少量节点和添加一个节点，即可使之重新有效。实验结果表明MCS算法可将覆盖集的生存周期平均延长20.7倍。.通过本项目的研究，推动了无线传感器网络中节点调度问题的理论研究和应用研究，为几何覆盖问题提供新的研究方法和研究思路。此外，本项目还促进了项目组团队的成长，取得了令人鼓舞的进展：已发表了21篇相关论文，其中4篇被SCI收录，15篇被EI收录；已培养了2名硕士研究生毕业，现有5名在读硕士研究生正在开展此方向的研究工作。