论文部分内容阅读
数据收集问题是无线传感器网络的非常重要的研究问题之一,近几年对数据收集问题的研究也很广泛。数据收集问题即是研究外界用户如何通过无线传感器网络从监控区域收集感应数据。在数据收集问题中,用户先在监控区域中放置大量特定用途的传感器节点,监控区域内的传感器节点以自适应方式组成无线传感器网络。数据收集是就将采集到的传感器数据通过多跳的形式传输给用户进行处理的过程。传感器网络数据收集问题包含的范围非常广,从数据收集协议,到多信道调度,从静态网络,到可移动网络数据收集等,都存在大量的研究问题。本文将从如何减少数据收集过程中的数据传输量、数据收集协议、增大网络吞吐量等几方面开展工作。首先,本文研究了在多任务共享的传感器网络如何减少数据传输量问题。在多任务共享的传感器网络中,人们可以利用数据可被多任务共享这一特性来减少数据传输量。本文提出一个区间数据共享问题。与现有研究中每个任务只采集一个数据不同,本文的问题中每个任务需要采集一段连续的数据。由于数据可以被多任务共享,该问题的目的是采集最少的连续数据,满足所有任务的数据需求。本文将该的问题刻画为非线性非凸问题,并提出一个近似算法来减少非线性非凸问题求解的复杂性。文章还分析了该问题的一个特例,并提出一个动态规划算法求解最优解。针对任务陆续到达的情况,文章还提出了三个在线算法。文章对每个算法的理论性能、时间复杂性和空间复杂性都进行了分析。其次,本文研究了多对象计数聚集过程中如何减少数据传输量问题。与现有的单对象计数问题的研究不同,本文研究多对象计数问题。由于所有的对象都需要返回各自的计数结果,因此,多对象计数问题会造成大量的通信开销。本文提出一个分布式的多对象计数算法。该算法可以保证在每个节点最多发送一定数量数据包的情况下,使得返回具有上界误差的结果。针对每个对象权重不同的情况,本文还分析了带权多对象计数问题。带权多对象问题可以刻画为不带权问题的一个特例。文章对所提出的算法的误差上界、节点数据发送量以及内存使用量都进行了分析。然后,本文研究了数据收集过程中的地理路由协议。地理路由协议只需维护一小部分节点的信息就可实验路由数据的功能,因此得到广泛关注。但是地理路由算法都需要将网络进行拓扑平面化处理,从而避免路由环问题。针对现有平面化方法维护代价很高的问题,本文提出一种具有高可靠性和低维护成本的地理路由协议。该协议的基本思想是将网络划分为规则多边形区域,并在贪心路由失败时将多边形区域内的所有节点看作一个虚拟节点进行周边路由。多边形区域间通信能够降低平均路由路径长度,从而提高了路由的可靠性。最后,本文研究了如何最大化网络吞吐量的问题。文章提出一个多信道TDMA调度算法最大化数据聚集网络的数据收集速率。为了更接近真实网络,本文使用的干扰模型是物理干扰模型。本文所提方法共包括三个步骤。首先需建立一棵路由树,其次在路由树的基础上进行时间槽分配,最后是进行信道分配。本文提出的方法是分布式的,其比集中式的方法的调度代价更低。本文分析了所给算法的时间槽数的上界,通过最小化所使用的时间槽数,从而最大化吞吐量。