无线传感器网络簇路由算法浅谈范文

《贵州师范大学学报》2016年第5期

摘要:

面向智能电网的无线传感器网络是由多个以电塔为中心的区域组成，使得这种WSN呈窄长的拓扑结构，根据这种拓扑结构设计了一种基于分簇的路由算法FCHR。FCHR首先采用分布式的方法生成候选簇头，然后在候选簇头中产生每个区域的簇头，进而生成由所有簇头组成的路由。仿真显示FCHR算法产生的簇头是LEACH算法的25.4%，而网络的生命周期提高了近40%。

关键词:

远程监控;候选簇头;簇头;数据报文;生命周期

0引言

智能电网技术通过传感器和通信网络远程监控电网的运行状态，这个监控网络能否可靠传输现场状态数据到控制中心是关键。由于电网所处的地理环境非单一性并且范围较广，使得整个电网环境数据采集点分布不集中，而且很多监测点所处的环境比较恶劣，布置光纤之类的监控网络设施难度大、成本高。WSN成本低、组网灵活，并且能适应复杂环境下数据采集，可以弥补光纤网络在一些地区布网难度大的问题。而且，由于有些监控区域受基站所处位置的影响会产生覆盖盲区，WSN也可以弥补无线宽带接入方案的信号盲区问题。WSN可提供灵活而经济的监控网络的解决方案。但是，如何保证传输实时性好而且可靠的数据，设计性能良好的WSN路由协议是提供可靠通信保证的关键问题之一。很多研究者已经提出了各种WSN路由协议。根据电网的分布特点，采用分簇路由算法比较适合智能电网的WSN路由构造，分簇路由算法是在簇头的基础上实现的，产生簇头是簇路由算法的关键。近年来，有许多关于WSN的簇路由算法的研究。LEACH算法［1］采用等概率方式随机选择簇头，每个节点根据随机数自主决定是否当选簇头，每轮产生的簇头没有确定的数量和位置，平均分配整个网络的能量负载，达到降低网络能耗，从而延长网络生命周期。HeinzelmanW提出了一种集中式产生簇头的LEACH-C算法［2］和LEACH-F算法［2］，这种算法由中心节点选择簇头，每个节点必须告知所在的地理位置以及剩余能量给中心节点，中心节点通过计算平均剩余能量，选择剩余能量不低于平均剩余能量的节点作为候选簇头，再采用模拟退火算法从候选节点中选出合适数量的簇头集合。LEACH．F则是LEACH的改变，按照LEACH-C的簇形成方式，但每个簇都有一个当选簇头的节点轮流表。GREES-L算法［3］和GREES-M算法［3］是两种利用地理路由和能量路由技术相结合的路由协议，这种路由协议节点能从环境中获得能量为前提，虽然算法的路由决策速度快比较快，但这种协议没有考虑网络拥塞的问题。Chipara，Z．等人提出一种能量感知QoS路由协议［4］，这种路由协议通过发现能耗和延迟低的链路保证实时数据的传输。RPAR［5］算法是一种实时能量感知的路由协议，这协议通过动态调节发送能量和路由判决解决低能耗的实时通信，通过能量感知的上游策略和有效的邻居节点管理器优化资源受限的WSN。对于有损链路、可伸缩性、内存及其有限以及带宽受限的WSN也提供了一种路由选择机制的解决方案。AODV算法［6］通过估算传感器节点向sink传输数据包所需消耗的能量，提出一种基于分层结构的分簇低能耗路由协议，利用随机循环选择簇头节点，将整个网络的能量负载平均分配到每个传感器节点中，达到降低网络能耗来提高网络整体生存时间的目的。与一般的基于平面结构的路由协议和静态的基于多簇结构的路由协议相比，这些路由协议在高能效的基础上可以有效减少端到端的数据传输延迟。通过在网络运行前由终端用户将布置的网络节点划分成多个簇的方式，MohamedYounis等人提出了WSN三层结构的路由协议［7］，这种协议必须将簇头标识和成员节点的位置告知每个簇头，再由簇头根据本簇内节点的状态数据监测各节点的能量变化。路由选择以代价函数和节点间数据传输链路成本来确定，代价函数包含了节点间距离、能量消耗、传输延迟等因素这些参数，这种协议具有能效较高、通信延迟较低以及能进行拥塞控制的特点。

1基于FCHR算法的WSN的特点

智能电网远程监控系统的WSN由人工部署，感知范围、通信半径以及节点布置的位置可预先规划，在网络生命周期内可以保证WSN的连通性和可靠性。如图1所示，WSN部署在电塔或者输电线上沿着电网呈窄长链状拓扑结构。根据智能电网的WSN网络的特点，考虑n个传感器节点S={s1s2…sn}分布在电塔及其邻近区域A内，WSN模型的基本假设如下:●传感器节点发送功率可调，通过调节发射功率，每个传感器节点都能与其相邻的电塔上的传感器节点通信;●每个节点知道自身的位置及其上、下行方向;●每个节点在布置时已知区域A内每个节点ID。由以上假设可知相邻电塔间的传感器节点是全连通图，其拓扑如图2所示。

2FCHR算法描述

根据智能电网的WSN的拓扑结构特点，为了提高网络的生命周期和可靠性，必须设计一种合适的分簇路由协议来满足面向智能电网的WSN的应用要求。智能电网的WSN簇可按照以电塔为中心的所有邻接节点划分，如图1中的A和B，可以在布置时让每个节点保存本簇节点成员表。通过路由算法将网络中的节点划分为如图3所示的簇头和普通节点，簇头负责收集本簇内普通节点转发的数据。这些数据经过数据融合后再发往其上游的簇头，最后到达sink;同时，簇头还负责转发来自监控中心的指令以及来自其下游簇头的数据包。由此可知，簇头节点是数据包的转发和数据融合中心，能量消耗较大，特别是越临近sink的簇头，通信负荷越重，能量消耗也越大。为了平衡网络在其生命周期内的负载均衡，延长网络的生命周期，设计面向智能电网的WSN的路由算法时应尽可能避免反复选举同一个节点作为簇头。根据上述要求设计的FCHR算法由决定候选簇头选举、簇头选举和路由生成三个步骤组成。

2．1候选簇头选举

首先，各节点采用分布式算法决定是否候选簇头，所谓候选簇头，当且仅当Thresh≥K，其中K为一个给定范围内的随机数，阈值Thresh按照下列方式设置:Thread=Eu－kd3uEu()02－ω(1)在(1)式中:ω表示节点u已被选为簇头的次数，Eu表示节点u的剩余能量，Eu0表示节点u的初始能量，du表示节点u到上游电塔中心点的距离，考虑到发射功率与传输距离是2～5次方，k表示与发射频率相关的比例常数。当节点u为候选簇头时，就向预设的簇内所有成员发送CANDIDATE报文，将自己的初始能量、剩余能量、到上游电塔中心点的距离以及已被选为簇头的次数告知其它的候选簇头，非候选簇头则丢弃CANDIDATE报文。其中CANDIDATE报文格式如下:

2．2簇头选举

当候选簇头的选举完成后，每个候选簇头都保存了一份本簇其它候选簇头信息表，然后根据这些信息选举簇头。候选簇头能否当选为簇头由是否能发送CLUSTERHEAD报文来决定。簇头选举阶段分候选簇头和普通节点两种情况处理。

1)对于普通节点，当接收到的第一个CLUS-TERHEAD报文时，即将发送该报文的节点作为其簇头。

2)对于候选簇头，在接收时间tu内接收CAN-DIDATE报文，然后按如下方式决定自己是否做簇头。假设接收了来自m个节点u1，u2，…，um发送的CANDIDATE报文，分别计算节点ui的剩余能量Eave=∑mi=1Ei/m、初始能量E0ave=∑mi=1E0i/m、m个候选簇头到上游电塔中心点的平均距离dave=∑mi=1di/m(其中:di表示节点ui到上游电塔中心点的距离)以及这m个候选簇头已当选簇头的平均次数ωave=∑mi=1ωi/m(其中:ωi表示节点ui当选簇头的次数)。根据上述结果，每个候选簇头按(2)式计算评价值σi:σi=［(Ei－Eave)－(E0i－E0ave)－k(di－dave)3］•2－(ωi－ωave)(2)然后通过求这m个候选簇头评价值最大者ElectValue=Max(σ1，σ2…，σm)决定是否当选簇头。如果σi=ElectValue，在等待一个随机后退时间ti后，节点ui向所在的电塔区域内的所有节点发送CLUSTERHEAD报文。如果ui在ti内接收到其它节点的CLUSTERHEAD报文，那么ui停止发送CLUSTERHEAD报文，并将接收到的第一个CLUS-TERHEAD报文的节点作为簇头。从式(2)可以看出，每个候选簇头评价值是由到上游电塔中心点的距离、当选簇头的次数以及剩余能量三个参数做为综合评价指标，这种方式是为了尽可能实现网内节点能耗均衡。CLUSTER-HEAD报文格式如下:MessageHeaduID为了提高网络的实时性，每个电塔所在区域内的所有节点在完成数据传输后，必须重新进行下一轮的簇头的选举。

2．3路由生成

经过候选簇头选举、簇头选举两个阶段，当选为簇头的节点再向其下游电塔所在区域内的簇头发送PRECEDING报文，告知自己的ID;每个下游簇头将接收到的第一个PRECEDING报文的簇头作为下一跳节点而建立路由表。PRECEDING报文格式如下:MessageHeaduID

3性能评估

本节通过仿真对FCHR算法的性能进行评估。考虑部署在二维平面上的静态WSN，100个传感器节点随机分布在两个50m×50m且相距200m的矩形区域，分别记作区域I和区域II，每个区域布置50个节点，这些节点的ID从1～100进行标识，区域I的节点ID从1～50，区域II标识从51～100。每个节点无线通信半径可从0～300m调节。仿真实验在NS2模拟平台进行。

3．1算法生成簇头的个数仿真实验

将FCHR算法与LEACH算法生成簇头的个数进行比较，实验进行20次，图4给出了FCHR算法与LEACH算法生成簇头个数在执行20次的比较。从仿真结果可以看出，FCHR算法每次产生的簇头个数平均为1.4个，而LEACH算法生成簇头个数平均为5.5个，因而FCHR算法与LEACH算法更有利于簇头的生成。对于只需要一个簇头与其上游簇头或者下游簇头即可通信的WSN，由单个簇头完成本簇成员数据融合并路由到上游簇头，可大大减少多个簇头节点转发数据造成的能耗，可有效提高网络的生命周期。

3．2网络的生命周期

对于一个簇的簇头节点，需要承担以下任务:1)采集现场物理数据，2)产生路由，3)接收并转发来自上一跳簇头的数据，4)接收并融合和发送本簇节点的数据。在仿真实验中，假设簇头在以上5方面消耗能量，并且当簇中有10%的节点死亡时，认为该网络的生命周期结束。假设每个节点的初始能量为1个能量单位，每个报文的长度为100字节，每接收1字节消耗的能量为1×10－5个能量单位，即每接收一个报文需要消耗1×10－3个能量单位。传感器节点发送数据所消耗的能量不仅与发送的字节数有关，而且与发送距离有关，假设每个节点发送数据每米每字节消耗1×10－6个能量单位，簇头节点每次用于数据融合消耗1×10－3的能量单位，每个传感器节点用于采集和处理数据每次消耗1×10－3的能量单位。从图5可以看出，FCHR算法在第43次时活跃节点数才降至10%以下，而LEACH算法在第22次时活跃节点数就降至10%以下。由于两种算法每次产生簇头数相差很大，造成电塔之间的簇头与簇头交换数据的次数更多，从而引起簇头能量消耗更快，说明FCHR算法可大大提高网络的生命周期。

4结束语

由于整个智能电网的WSN的节点不是集中布置在一个区域，而是由许多相隔较远的呈现成窄长的多个区域组成，根据应用的需要每个区域内节点比较密集。根据这种拓扑结构设计的基于分簇的路由算法FCHR，可以减少不同区域间的节点通信次数，从而提高全网的生命周期。通过仿真可以看出，利用FCHR算法产生的簇头是LEACH算法的25.4%，而网络的生命周期提高了将近40%。

作者:张鼎兴 单位:广东水利电力职业技术学院计算机信息工程系