论文部分内容阅读
无线传感器网络(Wireless Sensor Networks,WSNs)是集信息采集、信息传输和信息处理为一体的综合智能信息系统,在诸多领域都有非常广阔的应用前景和研究空间。无线传感器网络具有面向应用的特点,因此必须考虑服务质量(Quality of Service,QoS)保障的问题。例如在入侵检测应用中,对移动对象的定位、识别和跟踪需要在传感器节点和控制节点之间进行实时、可靠的数据交换,以便监控者及时采取措施。因此如何满足应用的QoS需求,同时有效利用全网资源是一个相对新且不容忽视的问题。WSNs的大规模性、自组织性、多跳路由和严重资源受限等特点增加了QoS支持的复杂度,而且WSNs的应用还提出一些不同于传统网络的新QoS需求。因此,传统网络的QoS保障技术并不适合WSNs。本文分析了WSNs中的QoS问题及其面临的挑战,归纳总结了现有研究成果的主要思想和优缺点,重点研究了应用层、数据管理层、连通覆盖层和路由层的QoS保障技术,主要研究成果如下:首先,本文针对同构传感器网络提出有QoS保障的能源高效的任务分配算法。WSNs中传感器节点的电池能量、计算能力、存储容量和通信范围都非常有限,节点通常无法单独完成计算密集型任务,但可以通过多节点协作共同完成任务。任务分配对实时应用的性能有很大影响,除了要考虑节能,还要考虑应用的实时性要求。WSNs自身的特点使得传统分布式系统中的任务分配算法无法直接移用,本文提出一个新颖的基于遗传算法的嵌套优化技术,保证应用在指定的时限之前完成,同时最小化网络的能耗。嵌套框架中包含基于遗传算法的任务映射,基于遗传算法的路由路径分配,任务调度和动态电压调制。将这几个优化阶段有机地结合在一起,高效的搜索任务分配的解空间,获得满足各种约束条件的优化任务分配方案。第二,本文针对异构传感器网络提出有QoS保障的能源高效的任务分配算法。采用分治技术将原始任务分配问题分解为4个子问题:任务划分、时限分配、任务调度和运行时的再调度。核心思想是将原始任务划分为简单任务和分支任务,同时处理,提高并行效率。用马尔科夫决策过程确定分支任务的优化调度,目标是最小化执行任务的能量消耗,并满足分支任务的时限要求。分治策略的优点是当节点失效时,不需要对整个任务图进行重新调度,调整受影响的局部任务图即可满足应用的QoS要求。实验结果表明:本文提出的基于分治策略的任务分配算法简化了原始问题的复杂性,缩小了原始问题的解空间,能够获得满足QoS要求的能源高效的任务分配方案。第三,本文提出有QoS保障的能源高效的节点睡眠调度机制。能量是WSNs中最受限制的资源。在监控区域内高密度地部署节点,调度节点轮流工作,可以有效的节省网络能耗,延长网络生命期。感知覆盖度是传感器网络一个特定的QoS需求。本文提出一个数据驱动的节点睡眠调度机制,根据节点感知数据的时空相关性计算节点间的预测关系并求解节点支配集。调度支配集节点轮流工作,节省网络能耗的同时也保证了网络的QoS需求。针对小规模网络提出了集中式睡眠调度算法,针对大规模网络提出了半分布式和分布式睡眠调度算法。理论分析与实验结果表明,数据驱动的睡眠调度机制能够保证网络感知全覆盖,节省网络能耗,有效延长网络生命期。第四,本文研究了查询处理中的QoS保障技术,为对象跟踪应用中的连续k近邻(Continuous K Nearest Neighbor,CKNN)查询提出一个能源高效的阈值搜索算法。对象跟踪是传感器网络的主要应用之一, CKNN是该类应用中常见的查询类型。为了快速响应用户查询并减少网络能耗,本文提出一个两阶段搜索算法。初始搜索阶段获得静态空间的k近邻,增量维护阶段获得监控期间k近邻的更新。用网格存储方式对查询和移动对象进行索引,避免了集中式存储的网络开销。提出环形搜索算法和基于阈值的增量维护算法。理论分析和实验结果表明,本文提出的本地存储和基于阈值的增量维护方法比集中式方法的能耗少,而且可以及时更新查询结果,快速响应用户查询。最后,本文为无线传感器网络中的实时通信提出一个有QoS保证的能源高效的路由协议,简称REER(Real-time and Energy Efficient Routing)协议。REER协议把应用通信的实时性要求转化为数据包的速度要求,根据数据包速度和网络状态动态调整节点的发射功率和路由决策。当通信的实时性要求比较高时,REER协议增加节点的发送功率,用增加能耗和减少系统吞吐量换取速度;当通信的实时性要求较低时, REER协议通过降低节点的发送功率节省能耗,增加系统吞吐量。REER协议结构中包括动态速度分配器、延迟估计器、转发策略器、队列管理器和邻居管理器。实验结果表明, REER协议大大减少了实时数据通信延迟的丢失率和能量消耗。在非实时数据吞吐量和实时数据的延迟之间进行了有效的权衡。