无线传感器网络中基于移动元素的数据收集

摘要

无线传感器网络能够感知周边环境信息并收集相应的数据,在许多领域都有重要的应用前景。传统的数据收集一般通过单跳或多跳无线通信将传感器节点采集的数据汇聚到固定的网络基站,然后由基站将数据发送给用户。采用单跳通信会导致较高的传感器节点能耗,而采用多跳通信会使基站附近的传感器节点能耗过高导致网络节点能耗不均衡,从而缩短网络正常工作时间。同时,这两种方式要求网络必须连通,从而需要部署大量的传感器节点,这导致节点冗余而增加网络成本。另一种方式是利用移动元素在网络中漫游实现数据收集来克服传统数据收集方式的不足。无线传感器网络中基于移动元素的数据收集是本文的研究内容。
　　 移动元素可以是同时具有移动和数据收集能力的人员或设备。移动元素通过自身的移动对网络中的传感器节点进行访问,并利用近距离无线通信完成对传感器节点所采集数据的收集。通过向网络中引入移动元素来完成数据收集,传感器节点的能耗情况被显著改进,同时也降低了数据收集对网络连通性的要求。
　　 相对于电磁波和声波的传播速度,移动元素的移动速度较低,易于导致较高的数据收集延迟。过高的数据收集延迟无法满足数据实时性的应用需求,还会增加传感器节点存储空间溢出而造成数据丢失的概率。可见,对移动元素有限的移动能力进行合理及充分的利用是保证数据收集性能的关键,也是目前该领域的重点研究方向。本文根据应用场景及所涉及移动元素数目的特征对问题进行分类讨论,并分别提出合适的数据收集策略。论文的整体工作概述如下:
　　 1)离线场景基于渐进优化方法的数据收集策略
　　 在离线场景下,所有传感器节点的位置信息对移动元素均为已知,数据收集问题要求为移动元素规划出一条最优的数据收集路径,以使移动元素能够在最短的时间内完成对所有传感器节点的周期性访问及数据收集。在网络中只有一个移动元素的条件下,本文首先将问题抽象为一个带有邻域的旅行商问题。注意到其NP难解性,提出了一种采用渐进优化方法的Combine-Skip-Substitute(CSS)数据收集策略,并对其性能进行了理论分析。大量仿真实验结果表明,CSS策略所得结果能够达到相应最优解下限的1.4倍左右。该近似结果是目前所有对带有邻域旅行商问题的近似算法所不能达到的。另外,与现有针对相同数据收集问题的最优的启发式算法标识覆盖算法(Label-Covering Algorithin)相比,CSS策略可以将路径长度降低为标识覆盖算法结果的85％左右。
　　 由于单移动元素条件下数据收集的可扩展性非常有限,本文把多移动元素条件下的数据收集问题分解为一个分配问题和一个调度问题,并分别采用著名的针对多旅行商问题的k-SPLITOUR算法以及之前所提出的CSS策略对其求解,从而得到k-CSS策略,并进一步通过仿真实验验证其性能。
　　 CSS策略及k-CSS策略都没有考虑数据在移动元素与传感器节点间的传输时间。通过将该因素纳入考虑,并根据现有无线通信技术的特点,本文提出一种多数据传输速率的无线通信模型,并在其基础上对CSS策略扩展而得到Multi-Rate CSS(MR-CSS)策略。仿真实验结果表明,在引入多数据传输速率后,MR-CSS策略能够显著缩短移动元素的数据收集路径长度,较不考虑多数据传输速率时,其长度减少30%-50%。
　　 2)实时场景基于队列模型的数据收集性能分析
　　 由于在实时场景下无法求解针对所有数据收集任务的最优调度策略,本文在对实时数据收集问题分析时,首先通过两个单移动元素条件下的队列模型M/G/1与M/G/1/c,对四种简单直观的数据收集策略(FCFS,NJN,FCFSC,NJNC)的性能进行了理论分析,并给出两个利用分析结果对数据收集过程优化的示例(自适应的数据收集与P-NJN策略)。大量仿真实验验证了分析结果的准确性,并从中得到一些重要的启示:首先,最近请求优先策略在提高系统吞吐率的同时可以显著降低数据收集的延迟;第二,对数据收集任务的合并可以很大程度上提高数据收集的性能。这些分析结果和启示被用于对更加高效的实时数据收集策略的设计进行指导。
　　 与离线场景类似,考虑到单移动元素条件下数据收集有限的可扩展性,本文在多移动元素条件下对之前所采用的队列模型进行扩展。由于多服务台队列模型理论分析的复杂性,本文采用近似的方法对该队列的长度、等待时间、响应时间等进行评价。这些评价结果的准确度被大量仿真实验结果所验证。
　　 3)实时场景数据收集策略。
　　 最后,根据之前对四种简单数据收集策略性能的分析结果和上述两点启发,并结合实时场景中移动元素需要频繁决策的特点,本文对离线场景的CSS策略进行简化和扩展,从而提出一种适用于实时数据收集的Simplified-CSS策略。实验验证该策略在简化计算过程的同时,能够得到非常好的数据收集性能。