基于能量高效的无线传感器网络路由与自组织算法研究

摘 要 随着电子集成和无线通信等技术的发展，由传感器设备组成的传感器网络在军事、工业、医疗和环境监控等领域得到了很好的应用。然而传感器网络的研究中还存在许多技术难题，比如本文所要讨论的无线传感器网络的路由问题。然而，广播问题是路由中最重要的一个方面。所谓广播问题就是，给定一个无线传感器网络拓扑图，以及网关节点,广播是指从网关节点出发，通过中继节点转发将消息发送给网络中的所有节点。目前研究广播问题的算法有很多，例如基于单跳信息的边缘广播算法EBA；还有基于二跳信息的连通支配集算法。这些算法均有其不足之处。本文的主要工作有： 本文首先介绍了无线传感器网络的一些基本概念、原理以及应用发展情况，然后对无线传感器网络广播与数据聚集算法的研究成果及其所面临的问题进行了探讨。在深入研究蚁群算法和现有广播与数据聚集算法的基础上，针对目前广播算法存在的约束考虑较为单一、没有考虑与能量的约束融合、仅局限于单纯的启发式算法等缺陷提出了基于蚁群系统的广播算法。基于蚁群系统的广播算法利用无线传感器网络的广播问题与旅行商(TSP)问题间的相似性， 将无线传感器网络模型描述为一个加权图，采用蚁群系统的群体智能和正反馈机制，从满足给定约束条件，优化能耗平衡度量的角度找出传感器网络拓扑中满足最小能耗并且可靠的广播路径。通过仿真工具MATLAB进行仿真实验，将新算法同以往算法进行了性能比较，结果表明新算法在能量有效性、网络生命周期和延迟方面具有明显的优势。最后对全文总结。 关键词：无线传感器网络，路由问题，蚁群算法，能量高效，广播 目录摘 要??? IAbstract??? II第1章??? 绪论??? 11.1??? 选题背景及研究意义??? 11.2??? 研究内容及方法??? 11.3??? 本文组织结构??? 2第2章??? 无线传感器网络简介??? 32.1??? 无线传感器网络概述??? 32.2??? 无线传感器网络组成结构??? 32.3??? 无线传感器网络拓扑结构??? 42.4??? 传感器网络的特征??? 52.5??? 传感器网络的应用??? 5第3章??? 无线传感器网络路由协议??? 83.1??? 无线传感器网络路由协议概述??? 83.2??? 无线传感器网络路由协议分类??? 93.3??? 路由广播问题的模型??? 103.4??? 路由广播问题的定义??? 113.5??? 现有研究成果??? 113.5.1??? 扩散法及相关算法??? 113.5.2??? 基于生成树的广播算法??? 133.5.3??? 基于线性链的广播算法??? 133.5.4??? 传统广播算法存在的不足??? 143.6??? 本章小结??? 15第4章??? 基于蚁群系统的传感器路由算法??? 164.1??? 蚁群算法介绍??? 164.2??? 基于蚁群链的广播算法??? 194.2.1??? 网络模型定义与描述??? 194.2.2??? AOBO算法的最终优化目标??? 204.2.3??? AOBO算法的实现过程??? 214.3??? 算法特点??? 234.4??? 本章小结??? 24第5章??? 仿真实验??? 255.1??? 实验场景的建立??? 255.2??? 实验结果??? 265.3??? 实验分析??? 28第6章??? 结论??? 30致谢??? 31参考文献??? 32附录 实验代码??? 33 1.1???? 选题背景及研究意义 无线通信技术、微机电系统和传感器技术的发展使得生产具有信息采集能力、数据处理能力和无线通信能力的传感器节点更加便捷。传感器节点是一种微小的嵌入式设备，它集传感与控制能力、计算能力、无线通信能力于一体。 无线传感器网络(Wireless Sensor Networks)是部署在监测区域内的大量廉价的微型传感器节点通过无线通信的方式组成的自组织的网络系统。无线传感器网络通过传感器节点之间协作地实时监测、感知和采集网络分布区域内监测对象的信息并进行数据处理来获得准确而详细的监测信息，并传送给需要这些信息的用户。所以传感器、感知对象和用户构成了无线传感器网络的三个要素。 无线传感器网络是涉及自动控制、人工智能、计算机和通信等多学科的综合性技术。随着这些学科的发展，无线传感器网络的应用范围日益广泛。美国商业周刊将无线传感器网络列为21世纪最有影响的2l项技术之一；MIT技术评论在预测未来技术发展的报告中，将其列为改变世界的10大技术之一；无线传感器网络和塑料电子学、仿生人体器官被称为世界未来的三大高科技产业。 与传统的无线网络(如Ad hoc网络和WLAN)相比，无线传感器网络具有不同的设计目标。对于Ad hoc网络，节点具有强烈的移动性，网络拓扑结构是动态变化的，其技术目标是通过优化路由和资源管理策略增加对频谱带宽的利用率，均衡网络流量并避免产生通信拥塞，为客户提供一定的服务质量保证，然后才会考虑节点能耗。在无线传感器网络中，传感器节点通常由电池提供能量。传感器节点在部署完成之后大部分不会再移动，因此网络拓扑可以看做是静态的。无线传感器网络的监控区域通常是非常恶劣的甚至是人们无法到达的极端环境，节点的供能设备无法更换，网络需要在无人维护的情况下进行长期自主工作。另外，传感器节点的处理能力、存储空间和通信带宽也是非常有限的。这些都决定了无线传感器网络的协议设计必须充分考虑能量有效性，因此如何有效地延长网络的生存周期就成了无线传感器网络技术研究中最核心的问题。 1.2???? 研究内容及方法 广播问题是无线传感器网络研究中的一个重要课题，考虑到传感器节点的能量有限性，需要减少广播过程中所消耗的总的能量。人们试图寻找一种高效实用的广播算法以解决广播问题。目前的广播算法可以分为三类，第一类是所谓的基于零跳信息的算法，即不利用任何邻节点信息的广播算法，最常见的是泛洪广播，每个节点在第一次收到转发信息后再转发给所有邻节点；第二类是基于单跳节点信息的算法，例如基于单跳信息的边缘广播算法EBA，拥有较高的性能和较小通信开销；还有基于2跳信息的连通支配集算法，通过构造最小连通支配集，减少转发节点数，具有转发节点集小，广播效率高的特点。 但是上述各种算法也各有不足，简单泛洪算法因通信能耗过高，并不适用于一般的广播通信；基于单跳信息的广播算法因未能充分利用网络节点信息，广播效率提高的空间很有限；基于2跳信息的最小连通支配集算法利用了更多的节点信息，获得了更有效的广播节点集，但是这些算法都没有考虑传感器节点剩余能量的信息，这种片面的追求最小连通支配集可能导致部分节点能量耗尽而影响连通性，从而降低整个网络的寿命。 研究无线传感器网络广播算法的目的是减少无线传感器网络的能量损耗，从而延长网络的整体寿命。如果算法只片面地考虑减少中继节点，虽然从整体上减少了无线传感器网络的能量消耗，但未必能延长网络寿命。因为片面地考虑减少中继节点，会使部分节点因为能量的耗尽而报废，导致网络出现盲点，甚至影响到网络的连通性。因此，在确定中继节点集时，不但要考虑减少中继节点的数量，还应考虑中继节点的剩余能量。 在本文将提出一种基于蚁群的无线传感器网络广播基于蚁群系统的广播算法利用无线传感器网络的广播问题与旅行商(TSP)问题间的相似性， 将无线传感器网络模型描述为一个加权图，采用蚁群系统的群体智能和正反馈机制，从满足给定约束条件，优化能耗平衡度量的角度找出传感器网络拓扑中满足最小能耗并且可靠的广播路径。通过仿真工具Matlab进行仿真实验，将新算法同以往算法进行了性能比较，结果表明新算法在能量有效性、网络生命周期和延迟方面具有明显的优势。 1.3???? 本文组织结构 本文第二章介绍无线传感器网络的背景、技术、应用及发展现状，重点了解无线传感器网络的组成和拓扑结构，以及传感器网络的应用。 第三章给出了广播问题的数学模型和定义，介绍几种典型的广播问题的研究方法，包括基于零跳信息的简单泛洪算法，基于单跳信息的边缘转发算法EFB和基于双跳信息的连通支配集算法。并分析各自的优点和不足。 第四章提出了一种基于蚁群算法的无线传感器网络中的广播算法，并对该算法的流程和性能进行了描述。 第五章为实验部分，验证本文提出的基于蚁群算法广播算法的有效性。