论文标题:无线传感器网络路由与广播算法研究
The Research on Routing and Broadcasting Algorithms for Wireless Sensor Networks
论文作者
论文导师 周明天,论文学位 博士,论文专业 计算机应用技术
论文单位 电子科技大学,点击次数 105,论文页数 118页File Size7467K
论文网 http://www.lw23.com/lunwen_398086507/
wireless sensor networks; routing algorithm; broadcasting algorithm; maximal independent set based algorithm for minimum connected dominating set; minimum energy broadcasting algorithm; clustering based energy aware broadcasting algorithm; transmission range coverage based broadcasting algorithm
随着无线通信技术、计算机技术与微系统技术的发展，无线传感器网络引起了人们的广泛关注。无线传感器网络由具有传感、数据处理和短距离无线通信功能的传感器组成，在军事国防、环境监测、生物医疗以及商业应用等领域具有广阔的应用前景，是当前计算机网络领域一个极为重要的创新课题。 路由算法与广播算法在无线传感器网络中有着重要而广泛的应用。在无线传感器网络中，路由协议负责在源节点和目的节点间传输数据，是无线传感器网络的重要组成部分。而无线传感器网络具有与传统网络不同的特点，因而众多传统网络的路由算法不能有效应用于无线传感器网络。广播在无线传感器网络中可用于传递控制信息、重要数据与报警信号等，同时也是建立路由的重要手段，甚至在极端条件下可以直接充当路由。广播可采用泛洪方式实现，泛洪虽然简单，但是存在冗余转发节点多、冲突与碰撞严重等问题，极为消耗能量与带宽等资源。 路由算法与广播算法是无线传感器网络中的热点研究领域，研究人员正在努力研究适合无线传感器网络的相关算法。在对当前无线传感器网络路由算法与广播算法研究成果的系统学习和总结基础上，本文就无线传感器网络路由算法与广播算法展开了相关研究，主要的贡献与创新包括： (1)研究了当前无线传感器网络路由算法进展情况。由于无线传感器网络与应用高度相关，单一的路由算法不能满足各种应用需求，因而人们研究了众多的路由算法。本文分析与总结了当前较重要的无线传感器网络路由算法的分类方法、核心路由机制与特点，目的在于为无线传感器网络路由算法的进一步研究提供参考。 (2)研究了当前无线传感器网络广播算法进展情况。在国内外相关文献中相继出现了许多各具特点的无线传感器网络广播算法，但总的说来还有很多需要深入研究的问题。由于尚未出现对这些算法进行全面综述的相关文献，为此，本文分析与总结了当前较重要的无线传感器网络广播算法，目的在于更好地理解算法的机理，特点与使用方法，为无线传感器网络广播算法的进一步研究提供参考。 (3)提出了基于极大独立集构造最小连通支配集的算法MISB(Maximal Independent Set Based algorithm for minimum connected dominating set)。基于连通支配集的路由算法的关键在于构造连通支配集，较小的支配集不但有利于构造更优的路由，并且非支配节点在没有监测任务时，可进入休眠状态，从而极大的节约能量。本文提出了一种基于极大独立集构造最小连通支配集的算法MISB：首先基于图的局部拓扑信息，并利用贪心算法，使具有极大度的节点为独立点，构造出一个极大独立集；然后利用独立点作为锚点，利用分治的思想使用图的局部拓扑信息来连通极大独立集，从而构造出连通支配集。MISB算法能够得到较小的连通支配集，应用于无线传感器网络路由，能够大大节省宝贵的网络资源。 (4)提出了最小化能量广播算法ERBOP(Enhanced Relative neighborhood graph Broadcasting Oriented Protocol)。在节点发送功率可调节并同时保证所有节点都接收到广播的数据包的约束条件下，本文在RBOP算法的基础上提出了一种高效节能的最小化能量广播算法ERBOP。ERBOP算法的设计过程及仿真结果表明，ERBOP的性能明显优于RBOP。ERBOP算法可节约无线传感器网络的能量资源，能较好的适用于无线传感器网络的广播。 (5)提出了基于聚簇的能量感知广播算法CBEA(Clustering Based Energy Aware broadcasting algorithm)。从减少转发节点以节约能量、平衡通信量以平均消耗网络节点能量出发，本文提出了一种基于聚簇的能量感知广播算法CBEA。仿真实验表明，CBEA算法有效减少了冗余转发节点从而节约了网络能量，平衡了网络通信量从而平均消耗了网络节点能量，因此大大延长了网络生存时间。CBEA算法是一种性能优越的广播算法，能够较好的适用于无线传感器网络的广播。 (6)提出了基于传输范围覆盖的广播算法TRCB(Transmission Range Coverage Based broadcasting algorithm)。为更好的实现无线传感器网络广播，本文仅利用1跳邻节点信息提出了一种基于传输范围覆盖的广播算法TRCB。分析与仿真表明，TRCB有效减少了冗余转发节点，从而节约了无线传感器网络能量；利用1跳邻节点信息，具有通信开销小、适应网络拓扑变化的特点；并且其性能优于同样利用1跳邻节点信息的边缘转发算法EFB。
Recent advances in wireless communications, computing technology, and micro-electro-mechanical systems technology have enabled the development of multifunctional sensor nodes which consist of sensing, data processing, and communicating components. Sensor nodes leverage the idea of wireless sensor networks based on collaborative effort of a large number of nodes. Wireless sensor networks, which are an important creative project in computer networks area, are much attractive in military applications, environmental applications, health applications, and other commercial applications. The responsibility of routing protocol is to deliver data between source and destination nodes. The different features of wireless sensor networks make the traditional routing algorithms can not be applied efficiently to them. Broadcasting is an important operation used for delivering control message, emergent data, alarming, route discovery, and even direct routing. The straightforward solution for broadcasting in wireless sensor networks is flooding (blind flooding), however blind flooding is improper in wireless sensor networks since it consumes too much energy and bandwidth which are deeply constrained in wireless sensor networks, and results in serious redundancy, contention, and collision. Routing and broadcasting algorithms are hot research area in wireless sensor networks, and researchers are endeavoring to study the algorithms suitable for wireless sensor networks. Based on systematically summarizing the relevant works on routing and broadcasting algorithms, this dissertation focuses on the routing and broadcasting algorithms for wireless sensor networks, and gains several achievements. The major contributions of this dissertation are as below: (1) This dissertation studies the progress of the routing algorithms for wireless sensor networks. Traditional routing algorithms can not be applied efficiently to wireless sensor networks. Therefore many routing algorithms for wireless sensor networks are put forward. After presenting the classification standards for routing protocols, the key mechanisms of the existing representative routing protocols are analyzed. (2) This dissertation studies the progress of the broadcasting algorithms for wireless sensor networks. There are many broadcasting algorithms for wireless sensor networks proposed in literatures, and there are still some issues needed to be studied further. For no comprehensive survey for this area, the key mechanisms and characteristics of the broadcasting algorithms that are among the most representative of this research area are analyzed. (3) This dissertation proposes an algorithm for minimum connected dominating set basing on maximal independent set which is called MISB. Constructing connected dominating set is the key technology for routing algorithm basing on connected dominating sets. The better routing can be constructed via smaller connected dominating set, and the non-dominating nodes without monitoring task can be in sleep mode, so energy is conserved much. At first MISB makes the nodes with maximal degree as independent nodes basing on the local network topology information, and get a maximal independent set. Then MISB makes use of the independent nodes as anchor nodes, and connects the anchor nodes to get a connected dominating set. The simulation results show that, using MISB, the size of the resultant connected dominating set is smaller. So MISB can conserve the energy efficiently while using in routing. (4) This dissertation proposes a minimum energy broadcasting algorithm improving upon RBOP which is called ERBOP. In ERBOP, nodes can adjust its transmission power in order to minimize total energy consumption but still enable a message originated from a source node to reach all the other nodes in wireless sensor networks. The simulation results show that ERBOP conserves energy efficiently. (5) This dissertation proposes an energy aware broadcasting algorithm basing on clustering which is called CBEA. Considering that nodes almost being static and position aware in wireless sensor networks, CBEA is proposed for using energy efficiently. Simulations show that CBEA reduces the number of redundant retransmissions nodes and balances the network traffic, so energy is conserved and energy dissipation is distributed evenly throughout the nodes. Thereby network lifetime is prolonged greatly. (6) This dissertation proposes a broadcasting algorithm basing on transmission range coverage with 1-hop neighbor knowledge which is called TRCB. Leveraging 1-hop neighbor knowledge can adapt topology changing with little communication overhead. Simulations show that TRCB reduces redundant retransmissions efficiently and outperforms edge forwarding broadcasting (EFB) which also leverages 1-hop neighbor knowledge.
|
