【作者】 吴万登；

【导师】 朱艺华； 潘建；

【作者基本信息】 浙江工业大学 ， 计算机应用技术， 2009， 硕士

【摘要】 在无线传感器网络中,由于传感器节点能量的有限及它们之间不稳定的无线电通信,可能造成网络的分割。针对无线传感器网络分区之间的通信,信息摆渡(Message Ferrying)是一种十分有效的方案。对于连通网络,本文提出了几种基于树的路由算法。首先是基于Dijkstra算法的LET(Least Energy Tree)和MHT(Least Hop Tree)路由算法,它们是分别对整个网络的能量消耗和网络延时的最小化而得到的生成树。另外,一种是基于Prim算法的MST(Minimum Spanning Tree)路由算法,其中权值是根据能量消耗计算得到的。为了更好的比较,本文着重提出了一种智能的LPER(Learning-based Power EfficientRouting)路由算法。在LPER算法中,通过构建一个用来权衡网络生存时间,能量消耗和网络延时三方面的自适应函数,及使用蚁群系统来建立最佳路由。此外,使用增加学习来预测邻居节点的能量消耗。此算法可以保证低能耗和低延时的同时,最优化无线传感器网络的生存时间。通过实验显示,只是能量消耗高于LET算法,而在其他方面都要比MST和LET算法来得优越。一旦网络出现分割,那么从传感器节点到基站的端到端的路由就需要重新建立。在这种情况之下,信息摆渡技术路由对于分割网络之间传输数据将是最佳选择。由于摆渡节点从一个分区运动到另一个分区是收集数据是预先设计好的,因此信息摆渡技术对于分离网络来说是一个先应式路由方案。本文提出了两类簇头选择模式:一类是基于树的簇头模式,本章中列举了三种具体的方式;另一类是基于支配集的簇头模式,通过OLT(One Level Tree)算法还可以得到每个节点的支配节点(簇头)。摆渡节点运动一圈需要消耗最小能量是一个TSP问题,本文使用遗传算法可以很好地解决这个问题。通过实验得到,在摆渡节点的能耗忽略不计或较小的情况下,OLT算法要比MHT,MST和LET算法更加节能。然后,在摆渡节点运动需要消耗较大的能量时,LET算法是一种较理想的选择。更多还原

【Abstract】 Wireless sensor networks (WSNs) are prone to partitioning due to limited energy in sensor nodes and unreliable radio communications between them. Message ferrying (MF) schema has been proposed as an effective means to deliver data between separated parts of a partitioned WSN.This dissertation proposes a tree-based routing algorithm for connected networks, in which minimum-weight trees of each partition of the WSN are evaluated with different alternate root nodes. Appropriate choice of the weights allows overall energy consumption or delay to be minimized. Two kinds of tree-construeting algorithms respectively named Least Energy Tree (LET) and Minimum Hop Tree (MHT) based on the Dijkstra algorithm are presented and evaluated by deriving an energy model. And, Minimum Spanning Tree (MST) based on Prim algorithm at a single root node is considered. For comparison, The Learning-based Power Efficient Routing (LPER) algorithm is emphatically proposed. In the LPER, a fitness function, which balances network lifetime, energy consumption, and packet delay, is constructed and used in an ant colony system to establish the optimal route. In addition, reinforcement learning is applied in predicting the energy consumption of neighboring nodes. The LPER is able to optimize network lifetime of WSNs, while keeping energy consumption and packet delay in a relative low level. Numeric experiments show the LPER outperforms the MST and LET based routing algorithms in terms of network lifetime and packet delay, although energy consumption of LET is superior to one of LPER.An end-to-end route for data delivery from the source to the sink may not be reconstructed if the network is partitioned. In this situation, MF routing is a good choice to deliver data between network partitions. MF is a proactive routing scheme for disconnected networks, in which ferries move proactively into one network partition to collect messages and deliver them to other partitions when the network becomes partitioned. At first, this dissertation provides two kinds of cluster head selection. Three different selections are included in the first selection based on tree and OLT selection is based on the dominating set rule, which also determines each node’s route path. How to get the distance-optimal ferry route is a Traveling Salesman Problem (TSP). In light of the combinatorial nature of the problem, genetic algorithms (GAs) are viable alternatives. Simulation experiments show that OLT outperforms MHT, MST, and LET when the energy consumption of the ferry is small or negligible. However, LET probably outperforms the other three methods when the energy consumption of the ferry is in the high level.更多还原