无线传感器网络路由算法研究

无线传感器网络路由算法研究

无线传感器网络是计算机和技术应用的一个新领域。它结合了传感器技术、嵌入式控制技术、分布式数据处理技术、现代网络和无线通信技术等。通过各类微型传感器对目标信息进行实时监测,由嵌入式计算资源对信息进行处理,能够协作地实时监测、感知和采集各种环境信息。无线传感器网络具有十分广阔的应用前景,在军事国防、工农业控制、城市管理、生物医疗、环境监测、抢险救灾、防恐反恐和危险远程控制等许多领域都有重要的科研价值和巨大的实用价值。目前,对无线传感器网络的研究主要集中在网络层和链路层,而路由算法已成为无线传感器网络的核心技术之一。根据网络中各个节点的地位和功能是否相同,路由算法可以分成平面路由算法和分簇路由算法。LEACH(lowenergyadaptiveclusteringhierarchy)算法是比较成熟且常用的分簇路由算法,许多分簇路由算法如TEEN(thresholdsensitiveenergyefficientsensornetworkprotocol)、PEGASIS(powerefficientgatheringinsensorinformationsystems)等大部分都在它的基础上发展而来,因而选择LEACH算法作为探讨的对象具有较好的代表性。1打造网络空间链上的打造方法LEACH算法使用自适应成簇技术和簇头节点的轮换技术。LEACH算法中引入了轮的概念,操作是分轮进行的,每一轮包含簇建立和稳定运行这2个阶段。在簇建立阶段,将所有节点划分为若干簇,每个簇随机选举一个簇头。随机性确保簇头节点与基站之间数据传输的高能耗成本均匀地分摊到所有传感器节点。具体的产生机制是,各个传感器节点生成0到1之间的随机数,如果随机数小于某一个阈值T(n),那么这个节点就成为簇头节点。阈值T(n)定义为T(n)={p1−p×(rmod1p)n∈G0其他(1)Τ(n)={p1-p×(rmod1p)n∈G0其他(1)式中,p是网络中簇头节点所占总节点数目的百分比;r是已完成的轮数;G是一个集合,集合中的节点是前r轮中没有充当过簇头节点的节点。使用这个阈值,每个节点会在1/p轮操作内充当一次簇头节点,符号mod是求模运算符号。在第1轮的时候(r=0),每个节点充当簇头节点的概率为p。在第1轮充当过簇头节点的节点,在后面的轮中将不能再次充当簇头节点。这样,剩下的节点数目变少了,因此能够充当簇头节点的概率必须增加才能保证每一轮中簇的个数保持均衡。经过1/p-1轮以后,T(n)=1,此时还没有做过簇头节点的节点,都可以成为簇头节点,因为所有节点生成的随机数都是在0和1之间。等过了1/p轮以后,所有节点又可以重新充当簇头节点了。在簇头节点选定后,该簇头节点对网络中所有节点进行广播,广播数据包含该节点成为簇头节点的信息。一旦传感器节点收到广播数据包,根据接收到的各个簇头节点广播信号强度,该节点选择信号强度最大的簇头节点加入,并向其发送成为其成员的数据包。簇头节点收到成员节点的响应后,会产生一个TDMA时隙表,并向成员节点广播,告诉成员节点什么时刻可以发送数据。簇形成后进入稳定运行阶段,簇头节点开始接收簇内各节点采集的数据,然后采用数据融合技术进行处理,将融合后的数据传输给基站。LEACH算法作为一种典型的分簇式路由算法,相比平面路由算法,在路由的发现和数据的传递过程中,消耗的能量少,建立路径的时间短,可以将网络整体生存时间延长15%,利用分簇能得到更佳的资源分配,并有助于改进功率控制,是一个最优化能量使用效率的协议体系。2馅料没有随机产生(1)在LEACH算法中,簇头的选取采用阈值判定的方法。对于一个节点n来说,为n随机选取一个0到1之间的随机数,成为标志值。如果随机数小于某一个阈值T(n),那么这个节点就成为本轮的簇头节点。由于这是一个随机过程,只能从概率的角度研究簇头的产生,因此无法保证簇头数目的准确性。(2)LEACH算法是让网络中的节点自组织地形成簇,簇头是随机产生的,这种随机产生的方式无法保证簇头节点的合理分布。当簇头节点位置比较集中时,簇的覆盖区域将出现部分重叠的现象,网络拓扑结构不够优化;当簇头分布在边缘区域时,簇内节点到簇头的距离将变大,使得簇的载荷也相应变大。(3)LEACH算法忽略了被选簇头在网络内的分布状态和节点间不同的通信距离而导致的节点能量损耗的不平衡。在能量不均衡的网络下继续运行随机簇头选择策略,如果低能量级的节点当选为簇头,那么节点就会由于过重的载荷而加速其剩余能量的消耗,从而降低了网络的生存时间。3赔偿算法的改进3.1基于网络拓扑中心的个团头区分如前所述,LEACH协议中簇头的产生存在较大的随机性,在实际仿真中并不能保证每一轮都能选出固定数量的簇头节点。为了消除每轮簇头数的差异,对每个簇头节点产生的区域进行预先设定,使得每个区域产生一个簇头,从而实现每轮的簇头数严格一致。基于网络能耗最小的考虑,通过数学推导和仿真实验,一般选取簇头比例为5%。对于一个节点数为100的传感器区域,则最优簇头数为5。在网络初始化阶段,基站根据节点位置信息,生成节点拓扑图,确定网络拓扑中心。为了限定簇头节点产生的区域,围绕网络拓扑中心划分传感器区域,保证每个区域覆盖20个节点。区域内的节点携带所在区域的标志信息1、2、3、4和5,这样便将100个节点分摊到5个区域内,不同区域的节点通过标志信息进行区分。在簇头选取过程中,每一轮的5个簇头分别从5个区域中产生,这样便保证了每轮的簇头数严格为5,从而避免了簇头数量的随机性差异。3.2相邻簇头间距d的限定在LEACH算法中,簇头的产生是随机的,可能造成簇头位置比较集中或者簇头分布在边缘的情况。簇头分布不合理,簇内通信能耗不平衡,远距离的节点必然要消耗更多的能量,从而严重影响网络的生存周期。为此,考虑利用下面的方法对上述问题进行改进。对于传感器区域,当簇头分布较为合理时,簇的范围应尽量均匀覆盖整个区域。因此簇头之间的距离必须适中,不能太近或太远。相邻簇头的间距应该作为一个重要参数来进行分析。为了做到簇头的均匀分布,可以通过限定相邻簇头的间距来实现。设节点分布区域的面积为S,节点数为N,簇头产生比例为P,如果要覆盖整个节点区域,则要求簇的平均半径R满足R≥Sπ×N×P−−−−−−√(2)R≥Sπ×Ν×Ρ(2)设相邻簇头的间距为D,当D接近2R时,簇恰好可以将整个传感器区域覆盖,一般认为这种分布比较合理。实际操作中,D的取值范围在2R的某个邻域内。为了实现上述机制,在簇头选取阶段,将相邻簇头间距D进行限定,使得D满足以下条件:D∈[2R(1-a),2R(1+a)],a∈(0,1)(3)对于一个100m×100m的区域,节点数为100,簇头比例P为0.05,代入式(2)计算可得R≥25.2m(4)令R=26m,a=0.5,代入式(3),可求得D∈(26m,78m)(5)这样,在第一个簇头产生后,其余簇头的产生区域就会被限定在以第一个簇头为圆心,D为半径的环形区域内。最终,所有簇头的间距都被限定在一个合理的范围内,使得簇头的分布较为均匀。3.3层内节点能量分析在LEACH算法中,簇头的产生完全依赖于概率事件,没有考虑节点特性的差异。在簇头产生阶段,没有成为簇头的节点,都有机会成为簇头。有些节点能量偏低,也有可能成为簇头,这样这个节点的能量就会很快耗尽。因此,选取簇头时应该考虑节点的能量水平,让能量高的节点优先成为簇头。由此可见,剩余能量应该作为选取簇头的一个重要参数。剩余能量越大,成为簇头的可能性相应也越大。在具体操作中,当每轮结束,簇头要将簇内节点的能量信息发送给基站。基站对节点的能量进行分析,凡是能量低于阈值(系统设定为初始值的50%)的节点将不纳入簇头的考虑范畴。基于能量最大化考虑,在每个区域内选取能量最大的节点成为簇头节点。综合上述改进方案,得到LEACH的改进算法,其流程如图1所示。4簇头节点选取在无线传感器网络中,路由算法一直是研究热点。LEACH算法采用簇头轮换技术