面向电网监测的线状WSN节点中继次数均衡路由算法

魏振春， 汪国胜， 石 雷， 卫 星

（1.合肥工业大学 计算机与信息学院，安徽 合肥 230009；2.合肥工业大学 安全关键工业测控技术教育部工程研究中心，安徽 合肥230009）

随着超／特高压输电线路（500kV、750kV、1 000kV）开始大量建设，电网规模不断扩大，线路走廊需要穿越各种复杂的地理环境（如沼泽、丛林、戈壁和崇山峻岭等无人区），这些都使得电力线路的巡检工作更加困难；另一方面，供电企业对输电线路的管理维护向信息化和智能化方向发展，而依靠传统巡检方式获取的信息量非常有限，难以满足要求，因而急需一种有力的监控手段对输电线路进行实时监测。在高压输电线路上布置传感器节点，利用传感器采集高压输电线路的状态信息和自然物理信息，通过传感器节点组成的线状无线传感器网络［1］对采集到的数据进行传输，即可实现对高压输电线路的在线实时监测。

在线状无线传感器网络中，数据传输的方式由路由协议决定［2］，如果采集到的数据都是按照从节点到基站逐点中继传递，节点中继次数将呈现离基站越近中继次数越多的倒三角分布情况，导致节点中继次数的不均衡。本文通过将传感器网络中的节点划分为簇和簇群，建立了2层网络结构，提出一种节点中继次数均衡路由算法。

1 相关工作

基于无线传感网的高压输电线路监测系统的网络结构，如图1所示。通过在高压输电线路上均匀布置若干普通无线传感器节点，并按照特定距离D（与传感器节点最大传输距离有关）布置若干带有GPRS／CDMA通信模块的汇聚Sink节点，自组织后成为无线传感器网络。传感器节点采集高压输电线路的状况以及周边的环境状况，如温度、风速、导线的弧垂、跨距等，实时以无线多跳的方式将数据传输到汇聚节点，然后通过公网将信息发送到监测中心。用于高压输电线路监测的无线传感器网络沿着线路进行人工布置，铁塔安装后其位置信息已基本确定，因而无线传感器节点的定位问题比较容易解决。

文献［3］提出的 MERR（Minimum Energy Relay Routing，简称MERR）路由协议通过选择最优中继传输距离，然后通过中继节点转发信息，从而使整个线状网消耗的能量最小；而AMERR［4］（Adaptive Minimum Energy Relay Routing，简称AMERR）则在MERR基础之上调整了最优传输距离的计算方法。文献［5］提出的基于电网监测的无线传感器网络短路径路由算法则通过短路径场的建立来预留多条较短距离路径，并在实际数据转发时选择剩余能量最大的节点转发，从而提高了传输可靠性和网络生命周期；文献［6］提出的 REECR（Energy Efficient Routing Protocol Based on Residual Energy and Energy Consumption Rate，简称REECR）算法综合考虑所有节点的剩余能量和能量消耗率来选择簇头节点，以达到均匀消耗节点能量和延长网络生命周期的目的；文献［7］则在REECR的基础上将簇头间的距离也作为选择簇头节点的依据之一，与节点的剩余能量和能量消耗率一起来选择簇头，提出 D－REECR（Distance－based REECR，简称D－REECR）路由协议。以上协议均将能量问题作为首要约束条件，而高压输电线路监测系统中通过采用现场取电、无线电供电等技术解决能量问题，所以能量问题不再是首要的约束条件，本文摒弃能量利用的限制条件，重点考虑节点中继次数的均衡性问题，提出了线状WSN节点中继次数均衡路由算法。

图1 系统示意图

2 线状WSN节点中继次数均衡路由算法

由于通过汇聚节点将整个沿输电线路布置的WSN节点分割成最大距离为D的若干段，每段构成一个独立的 WSN网络，因此本文仅讨论距离D范围内节点的路由问题。距离D范围内线状WSN分层结构如图2所示。

假定图1中由单个铁塔周围的传感器节点组成一个簇，从每个簇中选择一个节点作为簇头，再将若干个簇组成一个簇群，每个簇群中含有若干个簇头节点，仅簇头节点参与中继路由任务。线状WSN节点中继次数均衡路由算法可以划分为节点分簇阶段、分簇组群阶段和路由阶段3个部分。

图2 网络分层及路由示意图

2.1 节点分簇阶段

假设线状无线传感器网络节点i到Sink的距离为Si，两铁塔间距为d，若

则规定节点i位于第k个簇中。簇中簇头节点的选择参考LEACH［8］，具体选择过程如下。

节点随机产生一个0～1之间的数，如果这个随机数小于阈值P（m），则认为自己即为簇头。如果在本轮中已经当选过簇头节点，则把P（m）置为0，之后此节点在本轮中就不会再次当选为簇头。随着已当选过簇头节点数目的增加，剩余节点当选为簇头的阈值随之增大，因此产生的随机数小于阈值的概率随之增大，当只剩一个节点未当选时，则该节点一定当选。当所有节点都当选过簇头时，则进行新一轮簇头的选择。其阈值计算公式为：

其中，p为簇头数与总节点数的百分比；r为当前的轮数；C为最近1／p轮中非簇头节点集。

2.2 分簇组群阶段

从离Sink最远端开始按簇的个数将相邻的若干个簇组成簇群，设j号簇群所含簇的个数为Nj，采用2种方案进行分簇组群。

方案1分簇组群依据如下：

方案2分簇组群依据如下：

其中，β为簇群增长系数。

2.3 路由阶段

路由协议采用分层网络结构，并通过统计每个传感器节点的中继路由次数使其达到均衡的目的。每个节点均保存有本簇群内所有簇头节点的中继次数表，中继次数表中包括节点的ID标识和中继次数。具体路由过程如下：所有节点的中继次数路由表均为空，当有数据传输任务到达时，节点首先判断自己是否为簇头节点，如果不是则直接丢弃该数据包，否则根据数据包ID判断此数据包是否为上游相邻簇群传来的，如果是则搜索本节点中继次数表，如果本节点的中继次数最少，则转发此数据包，并加上自己的ID标识，否则直接丢弃数据包。如果中继次数表中最小中继次数不唯一，则节点ID标识最小的节点参与本数据包的路由传递任务。

节点作为中继节点传递数据后，广播本节点的ID，相同簇群内的簇头节点收到此ID的数据包后，更新各自的中继次数表。每个节点收到数据包后所执行的算法如下：

（1）节点A接收到数据包。

（2）判断节点A是否为簇头节点，如果是转到步骤（3），否则转到步骤（8）。

（3）判断数据包中的ID标识是否为节点A的上游簇群内节点的ID，如果是转到步骤（4），否则转到步骤（8）。

（4）检索节点A的中继次数路由表。判断节点A的中继次数是否最少，如果是转到步骤（5），否则转到步骤（8）。

（5）判断节点A的中继次数路由表内最少中继次数的节点个数是否为1，如果为1转到步骤（7），否则转到步骤（6）。

（6）寻找节点A的中继次数表中的中继次数最小且ID标识最小的节点，判断其ID是否为节点A的ID，如果是转到步骤（7），否则转到步骤（8）。

（7）中继数据包，更新中继次数路由表。

（8）丢弃数据包。

（9）结束。

3 仿真实验

GPSR［9］（Greedy Perimeter Stateless Routing，简称GPSR）算法也是不把能量问题作为首要的约束条件，与本文的研究背景类似，因此选择和GPSR进行比较。GPSR仅仅依靠相邻节点位置信息选择路由，只能实现局部最优，用于线状传感器网络时容易出现中继次数呈现离基站越近中继次数越多的倒三角分布情况，导致节点中继次数的不均衡。而在本文提出的簇群选取方案1的路由算法中假设每个节点产生r个数据包，则每个簇群中的每个簇j内节点作为中继路由的平均次数为：

从而达到了中继次数均衡的目标。同时方案2的选取综合考虑GPSR和方案1，避免了GPSR算法中继次数增长过快以及方案1中离Sink节点最近的簇群内中继节点单跳距离过长的问题。

本文的仿真条件是在线状区域上，均匀分布128个簇，每个簇包括5个传感器节点，每个节点产生50个数据包，MAC层采用802.11协议，其中方案2中的β取3，使用网络仿真器NS－2进行仿真实验。采用不同方案时，0～11号簇的簇内节点平均中继次数对比如图3所示。

图3 0～11号簇内节点平均中继次数对比

仿真实验结果表明，GPSR算法中到Sink距离越近的节点中继次数越多，并且呈线性增长，且增长幅度非常明显；采用方案2时，虽然中继次数仍然线性增长，但增长幅度比较缓慢；而采用簇群选取方案1的路由算法时，簇内节点平均中继次数为48次，和每个节点产生的数据包数基本相当，从而使节点的平均中继次数达到均衡，避免了由于某些节点中继任务过重而提前失效死亡，从而延长了网络的生命周期。

假设无线传感器节点的最大传输距离为S，铁塔间距为d，从而得到方案1中距离D的最大值MAXD的计算方法为：

方案2中距离D的最大值MAXD的计算方法为：

当β取3、d取50m，分别采用方案1与方案2时，对应不同的节点最大传输距离所得到的距离D的最大值MAXD的对比，如图4所示。从图4可以看出，由于在分簇群时方案1的簇群内节点个数增长幅度比方案2要大，所以当S≥850m以后，在节点最大传输距离相等的情况下，方案2的距离D的最大值MAXD要比方案1大，从而得到方案2的网络覆盖范围比方案1大。而在高压输电线路中铁塔间距是固定的，所以传感器节点总体均匀分布，同时为了避免方案1导致离Sink节点最近的簇群内中继节点单跳距离过长，以及尽量保证网络覆盖范围更大、中继次数均衡，因此方案2的路由算法更适合高压输电线路监测这类线状无线传感器网络。

图4 距离D的最大值MAXD对比

4 结束语

高压输电线路监测系统中通过采用现场取电、无线电供电等技术，能量问题不再是首要约束条件，因此研究中主要考虑线状无线传感网中节点的中继次数，本文提出了一种节点中继次数均衡路由算法。该算法使得整个网络节点的中继次数达到均衡，从而有效延长网络的生命周期。同时，综合考虑高压输电线路的特殊结构以及方案1后认为方案2更适合本文的研究背景。受传感器节点无线最大传输距离的限制，本文提出的路由算法更适用于短距离密集型线状无线传感器网络。

［1］王文光，刘士兴，谢武军.无线传感器网络概述［J］.合肥工业大学学报：自然科学版，2010，33（9）：1416－1419，1437.

［2］彭 静，刘光祜，谢世欢.无线传感器网络路由协议研究现状与趋势［J］.计算机应用研究，2007（2）：4－9.

［3］Zimmerling M，Dargie W，Reason J M.Energy－efficient routing in linear wireless sensor networks［C］／／Proc IEEE International Conference on Mobile Ad－Hoc and Sensor Systems，2007：1－3.

［4］Zimmerling M，Dargie W，Reason J M.Localized power－aware routing in linear wireless sensor networks［C］／／Proceedings of the 2nd ACM International Conference on Context－awareness for Self－Managing Systems，2008：24－33.

［5］郑更生，贺贵明，谢治平.基于电网监测的无线传感器网络短路径路由算法［J］.武汉大学学报：工学版，2007，40（2）：121－124.

［6］Li Xiaoya，Huang Daoping，Yang Jian.Energy efficient routing protocol based on residual energy and energy Consumption rate for heterogeneous wireless sensor networks［C］／／Proceedings of the 26th Chinese Control Conference，2007：587－590.

［7］李小亚，黄道平，孙宗海.一种异构传感器网络的能量有效路由算法［J］.计算机科学，2008，35（5）：60－63.

［8］Heinzelman W，Chandrakasan A，Balakrishnan H.Energyefficient communication protocol for wireless microsensor networks［C］／／Proceedings of the 33rd Annual Hawaii International Conference on System Sciences，2002：3005－3014.

［9］Karp B，Kung H.GPSR：Greedy perimeter stateless routing for wireless networks［C］／／Proceedings of the 6th Annual Int Conf on Mobile Computing and Networking，2000：243－254.