以数据为中心的无线传感器网络中生命期最优路由的构造

Since sensor nodes are battery powered devices, conserving sensor energy and extending the network lifetime become a very critical and challenging task to the large scale deployment of wireless sensor networks. The routing structures used for sensor data collection determine the number of packets received and transmitted by different sensor nodes and thus their energy consumption. Therefore, it is important to design routing structures that can balance the energy consumed at different sensor nodes to optimize the network lifetime. Existing routing protocols are mainly designed to deal with the static network traffic pattern in which a fixed set of nodes reporting data to the base station at each sampling interval. However, in data-centric network, due to the exploitation of temporal and spatial data correlations, as well as the nature of condition-based monitoring applications, the network traffic pattern often changes over different sampling intervals in an unpredictable manner. Most existing energy conserving routing protocols designed for static traffic pattern are inefficient in handling data collection with dynamic traffic patterns in data-centric network. ..This project investigates efficient routing structures to extend the network lifetime for data-centric sensor network with dynamic traffic patterns. Both the tree and DAG (Directed Acyclic Graph) routing structures are explored. We develop a performance model to analyze the energy consumption of sensor nodes in tree-based routing structures and apply the model to the construction of the routing tree to optimize the network lifetime. The model incorporates not only the cost of transmitting data, but also the costs of receiving data and idle listening. We formulate the problem of finding the lifetime-optimal DAG routing structure as a mixed integer programming problem and design an efficient greedy algorithm to compute a near-lifetime-optimal DAG structure. We further propose two methods to carry out data collection based on the DAG structure constructed. The DAG decomposition method decomposes the DAG into a set of trees and chooses one of the trees as the routing structure for data collection at each sampling interval. The DAG-based scheduling method directly constructs a TDMA schedule on the DAG structure for data collection. We intend to conduct simulation experiments to evaluate the performance of the proposed methods using real-world data traces. We also intend to test our methods and other state-of-the-art routing protocols on real platforms. To the best of our knowledge we are the first to incorporate the maximization of the network lifetime into the construction of energy conserving routing structures for data collection in data-centric network. The achievement of this project would serve as building blocks for the cross-layer optimization of the lifetime in data-centric network.

延长网络生命期是大规模应用无线传感器网络所亟需解决的问题。路由结构作为影响生命期的重要因素，必须予以优化。现有路由算法的设计，都针对网络中报送数据给基站的传感器节点固定不变的情况。在以数据为中心的无线传感器网络中，出于节能的需要，发送数据的节点动态变化，为节能路由的设计带来了挑战。本项目研究如何构造路由结构，高效应对发送数据节点动态变化的情况。研究内容包括：(1)建立新颖的节点能量消耗模型，利用它构造生命期最优路由树；(2)用数学规划的方法，寻找生命期最优的有向非循环图(DAG)结构；(3)设计高效的贪心算法，在短时间内计算次优DAG；(4)发明基于DAG结构的调度算法，直接利用DAG高效的收集数据。本项目是跨层（数据链路、路由、访问控制层）优化网络生命期的重要组成部分。我们首次将网络中数据的分布情况，纳入路由算法的设计中。研究目标是使路由适应数据分布，平衡节点的能量消耗，延长网络生命期。

本项目研究如何构造路由结构，高效应对发送数据节点动态变化的情况。研究内容包括：(1) 针对树型结构，设计了一个数学模型，用于精确描述传感器节点的能量耗费，并将设计出的数学模型应用于构造生命期近优的路由树；(2) 用数学规划的方法，将寻找最优有向非循环图(DAG)结构的问题建模为混合整数线性规划Mixed Integer Linear Programing (MILP)模型，并用当前最先进的数学规划解法器求解最优DAG结构；(3) 通过图的转化和等价性证明，将求解最优DAG问题转化为求解经典最大流问题，并设计启发式方法，快速构造生命期近优DAG；(4) 发明基于生命期最优DAG的分解方法，将能量高效的DAG结构分解为一个路由树的集合，为每棵路由树构造一个时分多址的传输表，同时为每棵树分配一个使用概率；(5) 发明基于DAG结构的调度算法，直接基于DAG构造出一个时分多址的传输表。在数据收集中，每个中间节点为不同的数据包灵活的选择不同的父节点，无论网络中的数据图样如何变化，父节点的选择始终能够使得每条边上的数据流量，接近于DAG中的流量配比。. 通过细致的仿真实验，我们评估了不同路由结构在网络生命期的性能。模拟结果表明: (1) 基于树的路由结构在优化网络生存期方面的性能不如基于有向非循环图DAG 的路由结构; (2) 贪心算法在网络生存期方面的性能与最优算法类似而计算时间更短; (2) 项目所提出的DAG 分解和基于DAG 的调度方法都优于只构建单一路由树进行数据采集的方法; (3) 在延长网络生存期方面，与DAG 分解方法相比，基于DAG 的调度方法更能适应动态网络流量的模式并在不同节点间更好的均衡网络负载; (4) 基于DAG 的调度和DAG 分解方法的设计体现了数据的能量效率和时间效率之间的权衡。本项目首次将网络中数据的分布情况，纳入路由算法的设计中，是跨层（数据链路、路由、访问控制层）优化网络生命期的重要组成部分。研究目标是使路由适应数据分布，平衡节点的能量消耗，延长网络生命期。