【作者】 汪祥莉；

【导师】 李腊元；

【作者基本信息】 武汉理工大学 ， 计算机应用技术， 2011， 博士

【摘要】 无线传感器网络是当前计算机网络研究中一个极为重要的研究领域,具有广泛的应用前景。然而,由于无线传感器网络节点具有电池供电、不可回收等特点,导致其节点能量有限,能量问题成为影响无线传感器网络性能的关键问题。高效的利用传感器节点有限的能量,尽可能的延长无线传感器网络的寿命是无线传感器网络应用研究的基础内容。针对这一基础研究,本文对无线传感器网络高能效路由技术进行了研究。1.针对异构无线传感器网络中异构节点的最优部署和节点数据的路由问题,提出了一种基于混合整数规划的异构网络分簇路由算法(CHNMIP)。首先以网络中节点到Sink的等效路径长度和最小为目标,将异构节点的优化部署转化为混合整数规划问题,并利用分解算法进行求解,这种方法可以保证异构节点在最大程度上被优化部署而且求解过程具有多项式复杂度；然后对网络中的普通节点进行动态分簇,将其数据设置为簇结构的传输方式,使得任何节点的监测数据都沿着最优路径向簇首或异构节点传输。CHNMIP克服了传统异构传感器网络路由算法中异构节点部署优化程度不高、普通节点传输路径单一的缺陷,降低了网络能耗,使节点能量消耗更加均匀,延长了网络生存时间。2.针对汇聚开销和传输开销相当的传感器网络,提出了一种综合考虑汇聚开销和传输开销的最小能耗自适应汇聚路由算法(CMEAAT)。该算法的核心思想是构造一棵性能介于SPT和MST之间的传播树,以适应不同类型的网络,并由汇聚开销和传输开销定义节点的汇聚得益,节点数据传输过程中,仅在汇聚得益大于零的节点处进行汇聚,避免了不必要的汇聚开销,解决了现有汇聚算法汇聚次数过多的问题；此外,自适应汇聚后的节点数据利用第二代小波零树编码算法(EZC-SGW)进行压缩,以降低传输能耗。仿真实验表明：与传统汇聚路由相比,CMEAAT能有效减少节点能耗,显著延长网络寿命。3.根据无线传感器网络多跳传输的特点,利用动态规划思想分别提出了最小能耗、能耗均衡和最小时延的优化路由算法。运用动态规划算法对传感器网络路径进行优化,使其具有高时效的特点。在基于动态规划的路由算法中,首先通过增加虚拟节点,将每个网络节点明确划分在唯一阶段中,构造出满足动态规划标准的网络模型；然后根据网络设计目标,利用动态规划算法逐步求解最优传输路径。所提出的算法克服了传统优化路由算法计算复杂度较高的不足,仿真结果表明,基于动态规划思想所设计的以传输能耗最小为目标的路由算法LECR、以节点能量均衡为目标的路由算法EB-LECR和以传输时延最小为目标的路由算法LD-LECR,在能耗、能量均衡和时延等方面优于传统路由算法。本文得到国家自然科学基金项目(No.60672137,90304018,61171075),教育部博士点基金项目(No.20060497015),国家重点实验室开放式基金项目(No.SKLSDE-2009KF-2-02)和新世纪优秀人才支持计划(No.NECT-08-0806)的资助.更多还原

【Abstract】 Wireless sensor network is an extremely important research field in computer networks at present, and has an extensive application prospect. However, as wireless sensor nodes are characterized by limited energy availability, energy efficiency is a key issue in designing the network. Efficiently using nodes’ limited energy and extending network lifetime as possible is the basic content of application research on wireless sensor networks. For the basic research content, several key technologies about energy-efficient routing are studied.1. For the optimal deployment of heterogeneous nodes and routing of monitoring data in heterogeneous sensor networks, a clustering heterogeneous network routing algorithm based on the mixed integer programming (CHNMIP) is proposed. Firstly, in order to minimize the sum of equivalent path distance from common nodes to sink, convert the optimal deployment of heterogeneous nodes into a mixed integer programming problem. Solve the problem using the decomposition algorithm, which can ensure the heterogeneous nodes are optimally deployed as possible and the solution process has the polynomial complexity. And then all common nodes are dynamically clustered, and the monitoring data is transferred to corresponding cluster heads or heterogeneous nodes along the optimal path. CHNMIP overcomes the defects of the traditional routing algorithms for heterogeneous networks, such as not ideal deployment of heterogeneous nodes, and single transmission path. In addition, CHNMIP reduces and balances energy consumption of network, and prolongs the network lifetime.2. For the wireless sensor network with unignorable aggregation overhead, a compressing minimal energy-consumption adaptive aggregation routing algorithm(CMEAAT) is proposed. Firstly, a propagation tree is constructed whose performance is between SPT and MST, so as to adapt to different types of networks. And then the aggregation benefits of nodes are defined according to aggregation overhead and transmission overhead. Data are aggregated only at the nodes where the aggregation benefits are greater than zero, so as to avoid unnecessary aggregation overhead. It solves the problem of excessive aggregation in the existing aggregation routing algorithms. In addition, the adaptively aggregated data is further compressed using the embedded zero-tree coding algorithm based on the second generation wavelets(EZC-SGW) to reduce transmission overhead. The simulation results show CMEAAT can effectively reduce energy overhead and prolong the network lifetime, compared with the traditional aggregation routing algorithms.3. As the dynamic programming algorithm has high computation efficiency, and is very suitable for multi-hop transmission of wireless sensor networks, the lowest energy consumption routing algorithm(LECR), the energy balancing and lowest energy-consumption routing algorithm(EB-LECR), and the least delay and low energy-consumption routing algorithm (LD-LECR) are respectively proposed on the basis of the dynamic programming idea. Firstly, a real network is converted into a standard dynamic programming model where all nodes are clearly divided into several discrete stages through adding virtual nodes. And then solve the optimal transmission path step by step using the dynamic programming algorithm according to the design goal of network. It overcomes the defects of traditional routing algorithms such as the higher computation complexity. The simulation results indicate the proposed routing algorithms are superior to the traditional algorithms in the aspects of energy overhead, energy balancing and time delay, etc.This paper is supported by the National Natural Science Foundation of China (No.60672137,90304018,61171075), the Specialized Research Fund for the Doctoral Program of Higher Education of China(No.20060497015), the State Key Laboratory of Software Development Environment (No.SKLSDE-2009KF-2-02), and the New Century Educational Talents Plan (No.NCET-08-0806),.更多还原