无线传感器网络数据收集若干问题的研究

发布时间：2018-01-08 15:26

本文关键词：无线传感器网络数据收集若干问题的研究　出处：《哈尔滨工业大学》2014年博士论文　论文类型：学位论文

【摘要】：数据收集问题是无线传感器网络的非常重要的研究问题之一，近几年对数据收集问题的研究也很广泛。数据收集问题即是研究外界用户如何通过无线传感器网络从监控区域收集感应数据。在数据收集问题中，用户先在监控区域中放置大量特定用途的传感器节点，监控区域内的传感器节点以自适应方式组成无线传感器网络。数据收集是就将采集到的传感器数据通过多跳的形式传输给用户进行处理的过程。传感器网络数据收集问题包含的范围非常广，从数据收集协议，到多信道调度，从静态网络，到可移动网络数据收集等，都存在大量的研究问题。本文将从如何减少数据收集过程中的数据传输量、数据收集协议、增大网络吞吐量等几方面开展工作。首先，本文研究了在多任务共享的传感器网络如何减少数据传输量问题。在多任务共享的传感器网络中，人们可以利用数据可被多任务共享这一特性来减少数据传输量。本文提出一个区间数据共享问题。与现有研究中每个任务只采集一个数据不同，本文的问题中每个任务需要采集一段连续的数据。由于数据可以被多任务共享，该问题的目的是采集最少的连续数据，，满足所有任务的数据需求。本文将该的问题刻画为非线性非凸问题，并提出一个近似算法来减少非线性非凸问题求解的复杂性。文章还分析了该问题的一个特例，并提出一个动态规划算法求解最优解。针对任务陆续到达的情况，文章还提出了三个在线算法。文章对每个算法的理论性能、时间复杂性和空间复杂性都进行了分析。其次，本文研究了多对象计数聚集过程中如何减少数据传输量问题。与现有的单对象计数问题的研究不同，本文研究多对象计数问题。由于所有的对象都需要返回各自的计数结果，因此，多对象计数问题会造成大量的通信开销。本文提出一个分布式的多对象计数算法。该算法可以保证在每个节点最多发送一定数量数据包的情况下，使得返回具有上界误差的结果。针对每个对象权重不同的情况，本文还分析了带权多对象计数问题。带权多对象问题可以刻画为不带权问题的一个特例。文章对所提出的算法的误差上界、节点数据发送量以及内存使用量都进行了分析。然后，本文研究了数据收集过程中的地理路由协议。地理路由协议只需维护一小部分节点的信息就可实验路由数据的功能，因此得到广泛关注。但是地理路由算法都需要将网络进行拓扑平面化处理，从而避免路由环问题。针对现有平面化方法维护代价很高的问题，本文提出一种具有高可靠性和低维护成本的地理路由协议。该协议的基本思想是将网络划分为规则多边形区域,并在贪心路由失败时将多边形区域内的所有节点看作一个虚拟节点进行周边路由。多边形区域间通信能够降低平均路由路径长度,从而提高了路由的可靠性。最后，本文研究了如何最大化网络吞吐量的问题。文章提出一个多信道TDMA调度算法最大化数据聚集网络的数据收集速率。为了更接近真实网络，本文使用的干扰模型是物理干扰模型。本文所提方法共包括三个步骤。首先需建立一棵路由树，其次在路由树的基础上进行时间槽分配，最后是进行信道分配。本文提出的方法是分布式的，其比集中式的方法的调度代价更低。本文分析了所给算法的时间槽数的上界，通过最小化所使用的时间槽数，从而最大化吞吐量。
[Abstract]:Data collection is one of the important research issues in wireless sensor networks, the research on the data gathering problem in recent years is also very extensive. Data collection problem is how to collect sensor data from the outside user monitoring area through the wireless sensor network. The problem in the data collection, the user first place a large number of sensor nodes in specific applications in the monitoring area, sensor nodes in the monitoring area of the wireless sensor network in an adaptive way. Data collection is the sensor data collected for the user for processing through multi hop transmission form. The range contains the problem of data collection sensor network is very wide, from the data collection protocol, multi channel scheduling. From the static network, to the mobile network data collection, there are a host of problems. This article from how to reduce the data collection process The amount of data transmission, data collection protocol, increase network throughput and other aspects of work.
Firstly, this paper studies how the sensor network sharing in multi task problem. Reduce the amount of data transmission in sensor networks multi task sharing, people can use the data can be multiple tasks share this property to reduce the amount of data transmission. This paper proposes an interval data sharing problem. With each existing research tasks in the acquisition of a a different data, the problems in each task requires a continuous data acquisition. The data can be multi task sharing, the problem is the purpose of continuous data acquisition at least, meet all task data needs. The problems are characterized as nonlinear and non convex problem, and propose an approximate algorithm to reduce the complexity of solving nonlinear nonconvex problems. The paper also analyzes a special case of this problem, and propose a dynamic programming algorithm for solving the optimal solution for the task. Arriving. In addition, three online algorithms are proposed. The paper analyzes the theoretical performance, time complexity and space complexity of each algorithm.
Secondly, this paper studies how to reduce the amount of data transmission problem of multi object counting during aggregation. Research and the existing problems of the single object counting, this paper studies a multi object counting problem. Because all objects need to return to their respective counting results, therefore, multi object counting problems will cause a large amount of communication overhead is proposed in this paper. A distributed algorithm for multi object counting. The algorithm can guarantee that each node in the data packet sent in a certain number of cases, make the return error with upper bound results. For each object with different weights, this paper also analyzes the multi object counting problem with multi object problem with the right. The right can be described as a special case the problem with no right. The error bounds of the proposed algorithm, the sending node data and memory usage are analyzed.
Then, this paper studies the geographic routing protocol in the process of data collection. Geographic routing protocol maintains only a small part of the node information can be experimental data routing function, so it has been widely attention. But the geographic routing algorithms require the network topology of the plane processing, so as to avoid the problem. Aiming at the cost of the existing routing ring plane method of maintenance is very high, this paper presents a high reliability and low maintenance cost. The basic idea of the geographical routing protocol is the network is divided into regular polygon area, and the greedy routing failure when all nodes in the polygon as a virtual node routing. The communication between the surrounding polygon to reduce the average path length, thus improving the reliability of routing.
Finally, this paper studies how to maximize the throughput of the network. This paper proposes a multi-channel TDMA scheduling algorithm to maximize the data gathering network data collection rate. In order to be closer to the real network, the interference model used in this thesis is the physical interference model. The proposed method consists of three steps. The first need to establish a route the tree, then the time slot assignment based on routing tree, finally is the channel assignment. The method proposed in this paper is distributed, the centralized scheduling method than lower cost. This paper analyzes the given upper bound algorithm time slot number, time slot number by minimizing the use, to maximize throughput.

【学位授予单位】：哈尔滨工业大学
【学位级别】：博士
【学位授予年份】：2014
【分类号】：TN929.5;TP212.9

【参考文献】