能量有效的无线传感器网络路由算法研究

发布时间：2018-03-08 01:37

本文选题：无线传感器网络　切入点：能量有效性　出处：《山东师范大学》2014年博士论文　论文类型：学位论文

【摘要】：无线传感器网络（Wireless Sensor Networks， WSNs）的路由算法与传统网络不同，，不但要完成从源节点到目的节点的路由发现，还负责组织整个网络的节点激活到路由维持以及数据传输各个方面的工作，是推广WSNs应用，提升网络效率的重要方法，也是目前WSNs领域的研究热点。能量有效性是WSNs体系中衡量路由算法的重要指标，因为在无线传感器网络中，传感节点都是由片上电池供电，能源受限，因此如何最大限度的利用这些能源使之发挥最大效果，成为提升网路性能的关键；而现有的对改善能量有效性的研究有很多，有的只注重在路由发现与维持阶段的性能提升，有的着眼于快速高效的发现节点，有的则侧重于减少冗余数据的传输；很少有研究从整个网络层出发，利用路由算法全面的提升能量有效性。本文从WSNs激活阶段、路由发现阶段到信息稳定传输阶段，针对不同阶段的特点做出全面的分析，对节点的位置发现、路由路径的建立与更新、数据融合等算法进行了研究，将路由各个阶段的算法整合，全面提升网络的能量有效性。在研究过程中进行了以下创新： 1.论文完成了通用的WSNs网络模型的定义。通过对网路模型的分析，发现现有的面向WSNs的研究大都存在节点功能过强，结构不灵活，面向具体应用设计的问题，进而导致基于这些模型研究的算法通用性较差；基于这一情况，提出了面向标准化应用的无线传感器网络模型定义。本文对模型中节点的功能尽量弱化，网络的结构不加限制，更加灵活，明确软件协议与节点硬件的功能界限：在网络中不设置锚点，传感节点不具备定位能力，节点随机部署，节点间的坐标系不统一，初始状态完全一致，节点的信道冲突由MAC协议完成，片上系统能够确定信号发射能量。 2.提出了高效无锚点的节点快速定位算法。这一部分的工作是将网络中随机部署的传感节点进行激活，并帮助这些节点进行定位。包括两部分内容，一是利用刚性图理论，将网络的结构转换为图的全局刚性判断问题，证明定位算法的可行性，并提出算法的先决条件；二是设计从sink节点出发，不需借助锚点，利用无线信道信号衰减公式和角度测量器的方法获得相邻节点间的距离与角度信息，然后在满足刚性图限制的情况下，进行全网节点的发现与定位。在定位准确的前提下，信息传输次数少，除sink节点外没有大规模广播操作，大大降低了初始化阶段的能耗。 3.在节点定位获得的位置信息基础上，提出了能量有效的分层路由算法。先是在已有的聚簇算法中引入了节点剩余能量因素，设计了能量相关的HAC聚簇算法；在此基础上设计了半静态的分层路由算法，即先对所有传感节点进行聚簇，在形成的簇内根据能量状态和通信代价选举簇头，进行簇头轮换时，不必重新聚簇，而是在簇内重新选择合适的节点充当簇头，当存在簇内节点能量消耗过大的情况时，进行全局的重新聚簇；设计了特殊的数据包格式和簇内节点的管理链表，在信息传递的同时利用数据包更新节点链表信息，保证了节点能量信息的实时性和准确性，并且对节点的异常情况可以及时发现。经过理论证明和实验模拟，算法有效的解决了无线传感器网络路由算法中的“热点问题”和“能量洞”问题，具有良好的能量有效性。 4.在分层路由算法的结构基础上，提出了高效的数据融合算法。提高信息过滤效率主要通过优化设置过滤点和选择高效的信息过滤模式实现。论文首先对信息过滤方式进行改进，将基于等待的过滤方式改为基于队列的方式，在过滤点设置动态队列，存储最近转发的信息，每次有新的信息到来将与队列中的信息比较判断，并且不断更新队列信息；而队列的设置采用弹性机制，即信息转发密度大的区域将自动加长队列，反之将减少队列长度；过滤点放置在分层路由时形成的簇头节点上，并根据簇头到sink的距离反比设置初始队列长度。与基于等待方式相比，队列的方式可以保证信息传输的实时性，而弹性的队列长度减轻了节点的存储压力，同时信息过滤的准确性和完备性也大大提高，从而减少了冗余数据的发送，节省了网络能耗。虽然本文研究了三个不同的算法，分别对应于WSNs路由的三个阶段，但是这些算法都是为了提升网络的能量有效性，延长网络生命周期，可以将三个算法整合为一个整体：节点定位算法是第一部分，算法的输入是随机部署在传感区域内的大量未知节点，输出是已经激活、已知自己与邻居节点准确位置的节点集合；第二部分是路由算法，输入是已知位置的节点集合，输出是聚簇完成，簇头选举完毕，可以进行信息传输的网络结构；第三步部分是数据融合算法，输入是可以路由的节点集合以及感应到的信息，输出是最终发送到sink节点的信息。综上所述，本文对WSNs的路由算法进行了全面的分析，从网络部署后的各个阶段入手，针对路由中不同阶段的特点，分别分析了提升能量有效性所需要解决的问题，为每个阶段设计了高效的算法，并且将算法进行了整合，全面提升了WSNs网络层的性能，并且利用方针实验和理论证明验证了论文研究的有效性和先进性。
[Abstract]:Wireless sensor network (Wireless Sensor Networks WSNs) routing algorithm is different from the traditional network, not only to be found from the source node to the destination node routing node, is also responsible for the organization of the whole network to maintain routing and activation of the data transmission in various aspects, is to promote the application of WSNs, an important method to improve network efficiency, is currently a hot research field of WSNs. Energy efficiency is an important index to measure the routing algorithm in WSNs system, because in wireless sensor networks, sensor nodes are battery powered by on-chip, energy is limited, so how to maximize the use of these energy to maximize the effect, become the key to enhance the performance of network; and a lot of research on the effectiveness of improving the existing energy, some focus on discovery and maintenance stage performance in routing, some focus on finding efficient Nodes, some focus on reducing the transmission of redundant data; few studies start from the entire network layer and use routing algorithms to improve energy efficiency.
This article from the WSNs activation stage, the route discovery stage to the stage of stable transmission of information, make a comprehensive analysis on the characteristics of different stages, found on the position of the node, establish and update the routing path, data fusion algorithm is studied, the calculation method of integration in various stages of routing, to enhance the energy efficiency of the network. The following innovations in the research process:
1. the definition of WSNs in general network model. Through the analysis of the network model, the research found that WSNs for most existing node function is too strong, the structure is not flexible, application specific design problems, which led to the model of general algorithm is based on; based on this situation, put forward wireless sensor network model definition oriented standard applications. The function of the node in the model to weaken, the structure of the network without restriction, more flexible, clear boundaries in agreement with the software function: node hardware in the network does not set the anchor point, sensor nodes do not have the ability to localize the nodes are randomly deployed, inter node coordinates the Department is not unified, the initial state is completely consistent, channel conflict node by MAC protocol, system on chip can determine the energy of AE signals.
2. this paper proposes fast location algorithm, anchor free. This part of work is the sensor nodes are randomly deployed in the network to activate, and help the node location. Includes two parts, one is the use of rigid graph theory, converting the network structure for global rigid graph to determine the problem, prove the feasibility of positioning in the algorithm, a prerequisite and algorithm design; two is starting from the sink node, without using anchor method and the attenuation formula of angle measuring device using wireless channel signal to obtain the distance and angle between adjacent nodes information, and then to meet the rigid graph limit, and locate network node in the premise of discovery. The accurate positioning of the information transmission, less number, in addition to sink node no large-scale broadcast operation, greatly reduces the energy consumption of the initialization phase.
3. based on position information of node localization, proposed energy efficient routing algorithm. The first is the node residual energy factor is introduced in the clustering algorithm in the design of energy related HAC clustering algorithm; on the basis of the design of the hierarchical routing algorithm of semi static, first of all. The node of the cluster, in the formation of clusters according to the energy state and the communication cost for cluster head election, cluster head rotation, without re clustering, but within the cluster, re select the appropriate node as a cluster head node in the cluster, when energy consumption is too large when the global re cluster design; special data packet format and the cluster nodes management list, in the information transmission and the data packet to update the list node information, to ensure the timeliness and accuracy of the node energy information, and the nodes of the abnormal situation It can be found in time. After theoretical proof and experimental simulation, the algorithm effectively solves the "hot issues" and "energy hole" problems in routing algorithm of wireless sensor network, and has good energy efficiency.
4. in the hierarchical routing algorithm on the basis of the structure proposed efficient data fusion algorithm. In order to improve the efficiency of information filtering mainly through information filtering and filtering mode optimization. Firstly, selection of information filtering method. The filtering method based on waiting to queue based on dynamic queue in the filter settings recently, storage forwarding information, every time a new arrival will determine the information compared with the queue information, and constantly update the queue information; and queue settings using the elastic mechanism, namely information forwarding density of large area will be automatically extended queue, and will reduce the queue length; filter placement of cluster head nodes formed in the the hierarchical routing, and according to the cluster head to sink inverse distance. Compared with the initial set of queue length based on queue waiting mode, the method can guarantee the information transmission The real-time queue length reduces the storage pressure of nodes, and improves the accuracy and completeness of information filtering, thus reducing redundant data transmission and saving network energy consumption.
Although this paper studies three different algorithms, three stages correspond to WSNs routing, but all of these algorithms is to improve network energy efficiency and prolong the network life cycle, the three algorithms are integrated as a whole: node localization algorithm is the first part of the input of the algorithm is in random deployment. The sensing area of the unknown node, the output is activated, and their neighbors the exact location of the known node set; the second part is the routing algorithm, the input is a collection of nodes with known locations, the output is the cluster, the cluster head election is completed, the network structure can transmit information; the third step is the data fusion algorithm the input is, routing nodes and information can be sensed, the output is finally sent to the sink node information.
In summary, the routing algorithm of WSNs comprehensive analysis, starting from the various stages of the network deployment, according to the characteristics of different stages in the routing are analyzed, enhance the effectiveness of energy needed to solve the problem, the design of efficient algorithms for each phase, and the algorithm for the integration, improve the overall performance the WSNs network layer, and the proof of principle experiment and theory to verify the effectiveness and advance of the research.

【学位授予单位】：山东师范大学
【学位级别】：博士
【学位授予年份】：2014
【分类号】：TP212.9;TN929.5

【引证文献】