毕业设计]基于负载平衡的无线传感器网络中的多跳分群算法.doc

基于负载平衡的无线传感器网络中的多跳分群算法摘要：本文提出了一种新的基于路由算法的分群，它利用传感器网络的冗余特性，为了解决在无线传感器网络中负载平衡和能源效率的传统问题。该算法充分利用在某一传感器网络中的节点，该传感器网络的区域覆盖范围被相邻的节点所覆盖以及像临时聚集头一样标记。然后，该算法形成两个多跳通信层。涉及内部集群通信的底层和涉及集群通信之间的顶层都涉及临时聚集头。性能研究表明，该算法有效地解决负载平衡的问题，以及更能有效地形成从过滤器和增强版过滤器中的能源消耗。关键词：集群路由，高效集群间路由，能源效率路由，基于路由的覆盖面。1.介绍由于在微电气机械系统无线电通信领域的最新研究进展已经使计算和通信在比较短的距离里形成微小的节点能力的感知成为可能。如果监测传感器都不能给出精确的结果，这些节点可以完成传感协作。它们能够形成一个无人管理的自主智能网络。麻省理工学院的科技评论和全球化未来指明传感技术是十大新兴技术之一，它能够改变世界。一个无线传感器网络根据拓扑学和与外面世界通信的渠道划分是由传感节点、计算节点和通信能力连接节点组成。该网络能监测活动和现象，这些活动和现象是不能被人类容易地监测，例如网站的核事故，某些化学领域的监测和长时间段的环境监测。这些网络的总体特征是拓扑结构不断变化，由于网络中的节点安排在不同的状态，例如在网络中睡眠或是醒着的状态以及失去活力的节点，网络的密集部署，自主智能网络管理，多集通信，有限的节点能量和有限的带宽。由于无线电通信的短距离和能量消耗与距离的平方成正比的事实使多集通信代替直接通信将能够节省能源。在无线传感器网络中，每一个节点都试图对本地数据执行计算，因此数据需要被转凝聚。因为在无线传感器网络中计算比数据传输更便宜。例如，计算节点数据样本的中位数比传送数据样本和计算水槽的中位数更有效率。无线传感器网络是数据中心网络，并且由于节点的数据多，因此不能有效地给予唯一的ID给传感器节点。这些节点通常被称作类型或数据，它们正在处理的范围。这些网络具有很高的应用特性，因此协议操作种类的结构从应用到应用程序各不相同。一个路由算法可能很擅长定期监测，但是也可能执行的不好，可能将会产生持续的数据传感。本文的其余部分组织如下。第二部分简要介绍了无线传感器网络在各个领域的应用。第三部分给出了各种聚类算法的简要概述。第四部分包括对相关研究工作的详细调查。该算法是针对第五部分和第六部分讨论的仿真和第七部分它的最终结果。2.应用本节介绍了无线传感器网络可以有效地运用的少数地区，无线传感器网络能够监测的应用的系统包括温度、湿度、压力、闪电条件、土壤组成、物质的存在、机械压力、速度、方向和物体的大小。典型的应用包括监测和军事，农业和环境的战场空间监测，例如，伯克利大学的研究人员和在缅因州上的大鸭岛上部署传感器。这些网络监测微气候里面和周围的被用作海燕的筑巢的洞穴。这样做的目的是为了形成一个生态环境监测组件，它能够使来自全世界的研究者从事于非入侵性的和非破坏性的敏感的野生动物和栖息地的监测。工程应用包括维修的大型工业厂房或是民用建筑的监测，现代化建筑的规定都是依据温度，湿度等等。其他的应用包括林火探测，洪水监测等等。3.无线传感器网络分群的挑战和问题尽管该算法具有巨大的潜力和优势，换句话说，就是分布式局部计算，通信中一个网络的某一部分发生故障，不影响其他部分的网络，更长距离的覆盖范围，极端环境监控，无线传感器网络的构成都对研究团体形成了挑战。本节简要的概述无线传感器网络监测所面临的一些重大挑战。3.1网络部署在无线传感器网络中的节点部署即是固定的也是随机的，它依据其应用。网络的固定部署是部署在固定的位置，在网络的随机部署中，产生的分布可以是统一的或是不统一的。在这种情况下，网络的认真管理是必须的，为了通过网络确保覆盖全部的范围和确保能源消耗的统一。3.2异构网络该无线传感器网络并不是一直统一的，在很多情况下，一个网络是异构的，它包括节点的不同能量层次。一些节点比其他节点少些能量约束。通常能量约束小的节点的一小部分都是很小的。在这种类型的网络能量越少约束的节点都是被选作聚集头和能量约束的节点都是集群的工作节点。这种网络的问题出现在当网络被随机部署时和所有的聚集头都被集中于某些特定的网络部分，并导致不平衡的聚集形成和使某些网络的部分变得不可能实现。此外，如果集群产生的分配头是均匀的，并且如果我们使用多跳通信，靠近聚集头的节点都会承受一个巨大的负载，就好像所有的通信量都是通过聚集头的相邻节点从网络的不同区域到聚集头路由来的，这将导致在聚集头的邻近部分的节点快速死亡，并导致聚集头之间的差距，减小网络的大小和增加网络的能量消耗。异构传感器网络需要群组仔细的管理，为了避免不平衡聚集头分布导致的问题和确保通过网络的能量消耗是均匀的。3.3网络扩展当一个无线传感器网络被部署时，有的时候新的节点需要被附加到该网络中，为了覆盖更多的区域和延长即时网络的生命。在这两种情况下，聚类方案应该能够适应网络拓扑的改变。其关键点是设计，这样的管理解决方案应该能够适用该算法是本地的并且是动态的，它将更容易适应拓扑的改变3.4统一的能量消耗在无线传感器网络中的传输相对于传感器而言是需要更多的能量消耗，因此，执行数据传输到基地台的功能的聚集头相对于其他空闲的节点需要更多的能量。为了平衡网络的能量消耗，聚类方案应该确保通过网络的能量损耗平衡和该聚集头应该能够旋转。3.5多跳或单跳通信这种通信形式对于无线传感器网络的使用者即是单跳的也是多跳的。因为在无线系统中的能量消耗是与距离的平方成正比的。因为依据能源消耗，跳通信是昂贵的。大多数的路由算法都是使用多跳通信形式，因为根据能量消耗，它更加的有能源效率，它的多跳通信更靠近聚集头的节点都承受很大的负载，并且当它们的能量终止时它能够创造空白在附近的聚集头。3.6基于定址的属性由于节点的数目太多，因此，在无线传感器网络中它是不能给每个节点分配ID的。数据进入节点是通过属性而不是通过ID。这样使得它侵入系统更加的简单，并且实施安全机制更加的简单。3.7群集动力学群集动力学的意思就是群集的不同的参数都是如何被决定的，例如，在某一特定的网络群集的数量。在某些情况下，这些数量是被预先指定的，在某些情况下，它是动态的。这些聚集头执行压缩的功能和数据传输一样。聚集头之间的距离是一个重大的问题，它可能是动态的，也可能被设定成一致和一些最小价值。假设是动态的，有可能形成不平衡的集群。然而限制它的一些情况，有最小距离可能是有效地在某些情况下，但是这是一个开放的研究问题，聚集头部分可能是中心的或是非中心的，它有优点也有缺点。集群的数量可能是固定的，也可能是动态的。集群的固定数量导致少量的超支，在这样的网络中将不能够重复的通过集群的设置阶段的形成。依据其可扩展行它是贫穷的。4.相关研究首先，在无线传感器网络中的路由是一个具有挑战性的任务，因为总寻址方案的缺乏。其次，来自多跳路径的数据资源是单一的资源。最后，由于数据冗余和能量，以及网络能量约束。当应用到无线传感器网络中时，常规的路由选择算法不是有效的。对于无线传感器网络，现有的路由选择算法的性能从应用到应用程序是多种多样的，由于不同应用需求的多样性。路由技术发展的强烈需要，能够在更广泛的应用中发挥作用。基于网络结构和第二基于协议操作，大致路由协议可以分为两个类型。网络结构可进一步分为平坦网络路由，分层网络路由和基于位置的路由。协议操作能够被分作谈判的基础，多路径的基础，查询的基础，基础服务和一致的基础路由。剩下的部分简要的描述了基于网络结构的路由协议和更具体的分层路由算法。在无线传感器网络中的集群基础路由收到分层路由种类的影响。分层路由涉及集群信息，在这里节点分配的传感的任务，它有低能量和传输任务的节点有更高的能量。这样做的目的是为了执行能量效率路由。该集群头可能是一个拥有更高能量的特殊节点或者是依赖算法和应用的普通节点。还聚集头也执行计算功能，例如为了减少基于基站节约能量的传输数量的数据收集和数据压缩。它的一个基本的优势是集群的延迟将会减少相对于基于基站缺失能量来到达的平坦路由。在无线传感器网络中，基于聚类的算法被认为是最有效的路由算法。其效率的基本原则是运作时根据分离和侵占的规律。在能源消耗方面的聚类是通过减少碰撞来提高的。在无线传感器网络中目前的工作是能源效率，它将决定聚集头的选择，聚集头之间的距离，集群的类型和集群间和内部集群通信，它们部署的环境类型，网络组织的建立和稳定性都是考虑制定一套基于路由算法的高效的集群主要的因素。在接下来的章节里，我们在共同的聚类算法方面做一个简单的介绍。传感器网络的第一层路由方法之一就是过滤。大部分的聚类算法都来自于这种算法。该协议仅仅使用了两个通信层。一个是集群间的通信，另外一个是集群头之间的通信。在这里聚集头的选择是随机的，并且聚集头角色的转变是为了平衡整个网络的能源消耗。集群的形成取决于每个节点接受该广告信息的信号强度。节点将会去信号最强的那个集群，并且它也为网络计算集群头总数。根据过滤工作是整个网络的5%，并且其仿真结果表明过滤形成超过了7耗能单位为基础的路由，如直接扩散。Leach协议最主要的问题在于聚集头的随机选择。聚集头的随机选择存在一个聚集头形成的不平衡，并且可能制作某些网站无法访问的可能性。Leach协议的扩展使用集中聚集形成算法。该算法的执行是从第一次接收所有关于每个节点它们位置和能级的信息的基站开始，然后它运行该算法，用于形成集群头和集群。在这里集群的数量是有限的，并且集群头的选择也是随机的，但是基站确保一个节点能量较小，就不会成为聚集头。LeachC的难题在于在更大的网络中，它是不可行的，因为节点远离基站将会导致节点发送它们的位置到基站变得困难，并且由于聚集头角色开始转变，远距离节点将可能无法及时到达基站。这将会导致通信延迟的增加，并且延迟也将放大。Leach的路由算法基于两个阶段，建立阶段和稳定阶段。在建立阶段聚集头是随机选择的，稳定阶段既是数据传输阶段。Leachf采用的想法是如果集群保持不变，并且仅仅只是在集群中转变聚集头的角色，这将节约大量的能源和提高系统吞吐量，然而缺点就是缺乏可扩展性的网络，这就意味着不能增加新的节点。Teen原则上是给时间的关键应用及时的对感应数据突然的变化做出响应。这里的节点感应数据是不断的与数据传输进行比较的，这是唯一在数据的兴趣范围的用户。这里的聚集头使用两种价值阀值，一个是硬阀值和其它软阀值。硬阀值是属性的最小价值，触发的传输是从一个节点的聚集头开始的，它是在这个意义上价值属性的微小变化。当属性变化的数额等于或大于软阀值时该节点将会发送。软阀值减少进一步的传输，如果属性值没有显著意义的变化。这个方案的最大优点就是它适合于关键应用的时间，大大减少了传输次数，并且为用户提供了属性值准确性的控制权，当用户正在通过改变软阀值来收集时。Apteen协议是Teen的扩展，它是一个既定期收集数据的混合协议，也是一个对关键数据进行实时采集的协议。这里的聚集头广播了四种类型的信息给节点。阀值，属性值和一个节点的调度方案的TDMA允许每一个节点进行传输仿真，它的仿真结果表明Teen和Apteen执行的更好，然而Leach在能源消耗方面是最节约的。比较Leach、Teen和Apteen，Teen表现优于其他两个。它的缺点是由于在Teen和Apteen间存在多层次聚类，将会导致多层次聚类更加复杂和产生间接费用。这个协议提出了一个多网关架构来保障大区域的利益，而不会降低系统的大面积的利益服务。该算法平衡在不同集群之间的负载的密度的均匀。该网络采用两种类型的节点：能源约束的传感节点和能量约束更少的网关节点。网关保持传感器收集数据的状态和设置多跳路由的状态。基于MAC的节点TDMA被用作聚集头之间的通信。它的缺点就是由于聚集头是静态的，其节点能量约束又低于其余的节点，它们在网络中是终身固定的，因此节点接近集群头将会比其它的节点更早的失去作用，从而导致与附近聚集头之间的差距，减少了网络连接。此外，如果网络的部署是随机的，将很可能导致聚集头之间的不平衡分配。集中式协议提出通过复杂的计算能力是基站的重要组成部分。基站使用的所有高能量消费的决定，像聚集头的选择，路线计算等等。这种算法主要有两个主要的阶段，第一个阶段是安装阶段，第二个阶段是数据通信。在安装集群的形成阶段，选择聚集头和为每个集群做安排。此外基站接收来自所有节点的能量并计算产生能量的平均值，然后当节点的能量水平高于节点能量的平均水平值时，聚集头将会选择该种设置。第二步是使保留的节点在聚集头中结群，然后通过反复的过程，直至达到形成集群所需要的集群数量，这个过程也保证了选择集群头是均匀分布的，数据通信阶段包括以下活动：数据采集数据融合数据路由仿真结果表明，BCDCP其性能优于Leach，LeachC和PEGASIS还形成于CH到CH的路径，其计划是转移数据融合到基站。该协议的缺点是它需要在网络中的所有节点的信息在聚集头选择之前，如果不是这样将会导致无法正常工作，因为它使用了集群集中管理的方式。由汉森，诺兰和约克曼的文献可以看出通过分离聚集头可以降低多少能量消耗在传感器网络中。该集群的形成在同一个LeachC。为了尽量减少能集群节点的量消耗，当传输数据到达集群头时，该算法随机选择一个节点适应聚集头的选择，与此同时还可以确保节点与其他集群的最小间隔在同一时间上。这个节点应该有能量级，包括网络中的平均能量级。当聚集头得选择过程结束后，集群也完成了形成在同一时间内同一个Leach上。仿真结果表明，最小间隔距离提高了能量效率，通过基站接受邮件的数量来衡量，这也表明它比不使用最小间隔距离要好1.5倍。在IsrarandAwan,2006中，我们提出的多跳路由集群间通信的算法，该算法是一个多层次多跳路由算法，它的工作原则是分离、战胜和为了在下载和能源效率方面形成平衡。该算法的目的是利用该传感器网络的冗余特性，它会选择网络节点很小的一部分，并标记它们作为临时集群头，并使用这些节点，使集群间多跳。该算法的问题是它选择临时聚集头是随机的，这样将会影响网络。这种算法修改后的版本作为临时聚集头的附加保证，作为临时集群头选择的节点的覆盖面积只有这些节点。此外，该算法形成两个层次的通信，底层是检测数据的节点，并参与内部集群的通信，第二层包括聚集头和临时聚集头，无论层之间的通信是多跳的，我们都可以使接下来关于网络模型的消耗所取的做如下假设：网络由100个传感节点组成；所有的节点都具有相同的电池电量和结构；该网络在500平方米的区域内是随机部署的；我们假设该网络是嘈杂的和没有错误的；能量消耗的假设都低于50nj/bit，在运行的同时发送和接受100Pj/bit的传输电路；我们并没用对网络同步，无线传输范围和有关控制信息做任何假设；每个节点它通过一些GPS系统或使用一些定位算法，知道每个节点的位置信息和邻节点信息；每个节点都有相关的覆盖范围。5.MCLB（多跳聚类的负载平衡算法）该MCLB包括两个不同的阶段，安装阶段和稳定阶段。在安装阶段聚集头和临时聚集头之间相互选择跟随稳定阶段，在稳定阶段就是数据传输的阶段。在安装阶段，该算法首先将过滤器中的所有节点涵盖在一定的网络覆盖范围内，相邻的覆盖范围是通过该算法决定的，如果我们结合起来，通过接触两个不同的区域和节点本身，将会产生更大的传感节点范围。有的时候，传感范围也包括不同的感测范围，因为它们拥有不同的电源能量，但是在该算法中，我们并不考虑它的区域类型。图2描述了临时聚集头形成的整体运作，在这里节点5的传感范围