一种智能电网中基于优先充电机制的节能汇聚路由方案

谈

(南京信息工程大学 计算机与软件学院,南京 210044)

0 概述

在智能电网中,安全性、可靠性和高效性是电力服务的目标,无线传感器网络(Wireless Sensor Network,WSN)在监测范围、成本、监测粒度、鲁棒性等方面都能很好地满足需求,但其存在无线传感器节点电池能量受限的问题。要将无线传感器网络应用于智能电网中,就需要研究能量效率和能量捕获的相关技术。

能量捕获技术对智能电网的长期发展具有重要意义。但智能电网中的主电源很难直接被无线传感器节点使用。目前有很多文献针对无线传感器网络的节能问题提出了解决方案。在能量捕获方面的研究包括利用风能、太阳能、震动能量、射频(Radio Frequency,RF)能量等实现能量转换[1-4]。考虑到能量转换的便利性和无线传感器节点的特性,RF能量捕获技术理论上可以为节点永久性供能,对能量捕获中的溢出情况进行监测[5],提高智能电网的自主性并用于对其进行长期监测[6]。

在利用RF给无线传感器网络充电的研究方面,文献[7]研究了RFID标签充电时最小化网络中的静态阅读器数量问题。文献[8]论述了在RF充电器访问每个节点时,如何实现该类功率发射器的最优路径问题。在文献[9]研究的移动充电器方案中,在有鲁棒性充电要求时实现了访问移动充电器的地标数最小化。以上文献尚未综合考虑数据传输效率和RF能量捕获的优先机制问题。

在RF能量捕获技术中,无线传感器网络中节点的部署及传输中的路由选择会影响到能量捕获及数据传输效果。在多跳路由拓扑中,每个中继节点都会因为负载增加而受影响,能量开销将比其源头节点更大,因此,需要为其设计能量优化策略。构建数据汇聚树可以让无线传感器网络的数据传输更加节能和高效,尤其是在节点需要通过RF捕能方式来充电的场合,更需要对路由进行优化。

在WSN中利用数据汇聚来延长网络寿命是一种常见的优化方法[10],这类方法主要分为2类:基于树型结构的方法和基于簇状结构的方法。前者的典型案例是TAG协议,后者的典型案例是LEACH或改进的LEACH算法[11-12]。另外还可以利用数据汇聚树来提升服务质量,如在保持网络寿命优势的同时减小数据延迟[13-14]。如何在能量捕获过程中构建数据汇聚树,文献[15]提出了一种提高网络生存期的数据汇聚树构造策略,但没有考虑数据传输率和充电的实际情况。本文在此基础上,针对智能电网的无线传感器网络布网特点,设计一种基于优先充电机制的数据汇聚型节能路由方案,综合考虑路由优化、RF充电与数据传输率之间的关系。

1 网络模型

在无线能量捕获的能量转换中,径损主要取决于信号频率。为了简化问题,本文所讨论的智能电网监测网络将采用自由空间径损模型。该模型是无线电波传播最简单的模型,无需考虑衰减和多径等问题,比较适合无线路由建模。在直径R的圆形范围内,相应的接收功率为:

其中,Gr是接收方的线性天线增益,PtGt是发射功率,λ是波长。实际捕获到的功率是接收功率经过一定的电路损耗之后的函数。

从式(1)可以看出功率传输范围很小,仅利用蜂窝基站(在智能电网中是主电源降压后的设备)补充能量,将不足以为传感器节点充电。因此,除了主供电设备外,本文将进一步利用移动式备选供能节点为汇聚路由中数据传输任务较重的捕能节点提供优先充电,这些供能节点的成本比主设备(基站)低得多。在本文所提出的支撑树节能路由算法中,这些供能节点不参与数据汇聚树的构建和数据传输。

优先充电网络模型如图1所示,网络包括一个主电源(扮演基站B的角色)、能量转换设备,这里扮演供能节点(Energy Providing Node,EPN)的角色;传输节点包括捕能节点(Energy Harvesting Node,EHN)和普通节点(Ordinary Node,ON),其中供能节点仅与捕能节点通信。由于备选供能节点不需要提前在全网部署且分配灵活,因此在图1中并未体现。

图1 优先充电网络模型

每个EHN至少配置一个EPN进行充电,对于路由中承担更大量数据传输任务的EHN,增加PEPN实现优先充电。该PEPN为移动式工作,可根据汇聚树中的路由变化及数据传输率情况而做相应的位置调整,实现基于动态优先充电的节能汇聚路由。本文利用ILP模型实现全网ON节点的子节点数最小化,假设所有的供能节点发射范围都一样。

2 节能路由方案

利用上述3类节点,即普通节点(ON)、供能节点(EPN)和捕能节点(EHN),首先在网络中部署初始的ON和EHN,在EHN周围设置至少一个EPN。采用整数线性规划(Integer Linear Programming,ILP)和最小权重捕获支撑树路由算法实现节能的数据传输。这里的ILP即最小-最大模型,用以实现普通节点的下游节点上限的最小化(数据汇聚自下游节点往上游节点)。最小权重捕获支撑树路由算法旨在加速汇聚树构建的速度,并降低其复杂度。对构建好的汇聚拓朴树再进行回溯,直至找到最优汇聚拓朴树。为了实现优化充电,对其中的重载EHN,通过增加EPN提高捕能的便利性和有效性。

2.1 初始模型

汇聚路由在文献[15]的基础上改进。本文简化了汇聚过程,并增加优先充电环节。汇聚路由主要基于图论方法,构建一棵最小权重支撑树,要求路由中不含闭合环,因此,需要实现从带环到去环的过程。

构建的数据汇聚树基本模型如图2所示,其中不包含EPN和PEPN。

图2 充电型数据汇聚树基本模型

该模型描述为:在网络中一共有K个节点,其中基站为B,整个树中有n个顶点,最多有n-1条边。而汇聚路由中进入B的数据流有K-1条(这也要求构建的树中有向边的数量不应该小于该数)边集合M中所有的边是由2个能直接通信的节点之间的连线构成。EHN节点集H⊆N,ON节点集O,也即N{H∪S}。为了简化问题,EPN节点不在N中体现,也即数据汇聚树中并不出现EPN。

由于各捕能节点的传输数据率不同,对能量需求不同,因此在构建好的汇聚树中,在较重传输任务的捕能节点旁增加一个备选的供能节点。该供能节点仅为捕能节点提供RF能量,对汇聚路由不产生影响。构建了该拓扑树后,图2可以抽象为有向拓扑形式,其中忽略了非直接通信的节点之间的边。

假设每个待汇聚拓扑树中的节点可以处理从其子节点接收到的全部数据包,在此基础上再生成一个自身的数据包。为了节省能量,节点仅在有数据收发活动时才激活射频。因此,子节点的数量对网络寿命会产生重要影响。考虑到EHN节点可以进行RF能量补充,网络寿命主要受ON节点的影响,需要在全网中实现ON节点的最大子节点数最小化。

基于IPL的汇聚路由(Aggressive Routing-IPL,AR-ILP)旨在减少ON的子节点数,以增加WSN寿命。AR-ILP模型构建如下:模型的有向拓扑图源于基站B,每个节点有一个权重,定义ON权重为1,其他节点(EHN节点和B)权重为0。设置一个决策布尔变量X,若节点i(不含B)选择j作为父节点(即数据汇聚的上游节点),则Xij=1。整型流矩阵Fij表示从i到j的数据流构成的矩阵,若Xij为0,则Fij亦为0。通过Fij进行优化后将获得一个连接拓扑。假定每个节点(除B之外)有且仅有一个父节点,在WSN中所有ON节点的孩子数最少可以表示为:

s.t. ∀(i,j)∈M,i∈N-{S},0≤Fij≤K-1

(2)

其中,n(j)是节点i射频范围内的所有通信节点。

假设到基站B的所有数据流有K-1条,从基站B只有流入的数据流,没有流出的数据流,B为整棵树的根。每个数据流都有单一的传输方向,在树中,每个最下游的叶节点发送一个数据包,中继节点在收到的数据包基础上再加一个包,最终所有数据到达B,WSN的数据传输基于该汇聚树完成路由过程。

2.2 基于优先充电机制的节能路由算法

为了进一步加速该汇聚树过程,可以让B发挥更大的作用,基于该汇聚树根B构建反向支撑树,数据流的方向与数据传输方向相反,采取从B起始一直到叶节点的方式。在构建反向汇聚支撑树的过程中,利用反向拓扑控制、权重控制和破环法使ON节点的子节点数最小化过程更快。其基本思路为:按照与汇聚树中数据流相反的方向,从B出发,把进入B的边全部去掉,进一步找出其他每个节点的入边和出边。边的选择根据节点的权重进行。B和EHN节点的权重为0,ON节点的权重为1。有向边的权重设为出发节点的权重。每个节点选择最小权重的入边来构建树(使ON及EHN节点更多地选择B和EHN节点作为父节点)。这样便构建起初始时的反向汇聚支撑树,同时检查其中是否有环路(环主是由NHN节点造成,因其既有入边,又有出边)。若存在环路,则利用将涉及环路的EHN节点合并的方式将环打破,再重新确定树中的边(规则与前文一样)。检查新图中的含环情况,若有环,继续用合并EHN节点的方式破环,直到树中无环为止。最后把合并节点拆开,再次确定树中的边,形成无环的反向支撑树。将这棵反向汇聚支撑树再恢复成正常数据传输的汇聚树只要将反向支撑树中边的方向取反即可。

在上述加速的反向支撑树汇聚路由中,个别ON的子节点数可能会不稳定,其原因是在建树过程中最初基于最小权重选择边的过程不唯一,而破环过程中合并节点时基于最小权重选择边的过程也不唯一。因为在权重相等且存在有向边时,并没有限定必须选择哪个ON节点作为父节点,这就导致了一些ON节点的孩子数超过1。因此,对这种非最优拓扑树需要反复进行边的优化选择操作,直至找到最优数据汇聚路由。该加速过程是本文的重要创新点,能够给节能处理带来更高的效率。

反向支撑树汇聚路由原始拓扑如图3所示。其中,EHN节点用双线圆圈表示,B为基站,其他节点为ON节点。

图3 反向支撑树汇聚路由原始拓扑

下面结合图例给出具体的算法步骤。

步骤1在所有ON节点、EHN节点、B节点构成的无向图中构造出带权有向图,并在其中找到每个节点。权重设置为:ON节点权重为1,EHN节点及B节点权重为0,若u为ON节点,以u为起点、连接u和v的有向边权重设置为w[u,v]=1,若u为EHN节点或B节点,则对应w[u,v]=0。这种设置保证了从EHN和B节点出发的有向边权重为0,更有利于ON将其选为入射边,因为数据汇聚树基于最小权重选择有向边。在构建反向支撑汇聚树的过程中,基站B的优先级最高,其他节点选择入射边时以B作为入射边首选。作为整棵树的根,基站B只有出射边,其入射边全部去掉。规定每个EHN节点至少要有一条入射边,而ON节点有多条入射边备选。该过程所形成的拓扑不唯一,图4给出了某次选择的结果。

图4 初步构造的带权有向图

步骤2检查上一步结果中的含环情况。若无环,直接得到反向数据汇聚拓扑树。进入步骤4。若存在环,对其进行破坏。将包含在环中的EHN节点进行合并,形成一个新的合并节点。再次,基于最小权重选择每个节点(含合并节点)的入射边,构成一个新的最小权重拓扑树。重复该步骤的操作,检查新树中包含环的情况并进行相应的处理,直至最后的树中不含环。破环的过程如图5、图6所示。

图5 合并节点基于最小权重定边的结果

图6 继续合并节点并基于最小权重定边后的最终结果

步骤3分离上一步的合并节点,并确定图中每个节点(除B)的入射边,得到相应的反向汇聚拓扑树,如图7所示。该过程形成的拓扑树不唯一。

图7 拆分节点并确定相应边的示意图

步骤4将反向支撑汇聚拓扑树的各边进行反向处理,得到与数据传输一致的支撑树汇聚路由,如图8所示。

图8 反向确定支持汇聚路由的拓扑树

步骤5重复步骤1～步骤4,获取其他可能的支撑树汇聚路由,并进行对比,以期得到最优数据汇聚路由。

为了使模型更具可行性,在智能电网的监测网络实际运行时,该监测网络寿命与传输范围、部署区域、ON节点周围的节点密度、EPN节点和EHN节点的部署、RF能量搜集的效率有密切的关系,并不能按理想方式(比如每个节点仅产生一个数据包并将其传输给其上游节点)来传输。因此,要区别对待EHN,在构造的最优数据汇聚路由中,对那些传输任务较重的EHN节点给予更高的优先级,利用移动式EPN,在这些重载EHN节点旁设置一个PEPN节点。

2.3 算法复杂度分析

算法复杂度分析步骤为:

步骤1确定树中的顶点权重(复杂度为O|N|)和每条边的权重(复杂度为O|M|),以及在所有有向边中移除到基站B的边(复杂度为O|M|))。

步骤2分析得到递归的破环过程复杂度为O(Nlog|N|+|M|)。

步骤3合并节点的分离,因为破环和合并节点的思路与Edmond有向最小支撑树算法思路相近,借鉴其有向最小支撑树算法所得到的结果,其复杂度为O(|N|-1),即O|N|。

由以上分析得出算法总的复杂度为O(3|M|+Nlog|N|+2|N|)。

对比文献[14]的APAL算法,本文算法增加了优先充电和加速过程,算法复杂度没有明显增加,在节点数量中等及以下时,可以得到更好的复杂度性能。

3 仿真与结果分析

为了验证本文算法的性能,本节进行仿真实验并分析结果。主要考察网络寿命,以第1个ON节点耗尽电池的时间为准,利用Matlab和开源的整数规划工具Ipsolve进行混合编程,通过Matlab调用Ipsolve解决IPL最优化问题,其求解效率较高。其他IPL求解工具有的是商业软件,如GPLEX,有的操作复杂,如GLPK。

设计3个仿真过程。第1个实验设计为当ρ和R不变时(分别设置为20和20%),改变K值,观察网络寿命T的变化情况;第2个实验设计为当K和R不变时(分别设置为400和20%),改变K值,观察网络寿命T的变化情况;第3个实验设计为当ρ和K不变时(分别设置为20和400),改变K值,观察网络寿命T的变化情况。为了研究优先充电机制的性能,增加能耗排在前10%(假设能耗仅与传输连接数相关)的EHN节点作为优先充电节点。在以上3种实验条件下比较具有优先充电机制和没有优先充电机制的节能汇聚路由方案在网络寿命方面的性能。

图9～图11分别给出了3个实验的仿真结果,并对2种方案进行了横向对比。

图9 节点数与网络寿命的关系

图10 网络传输密度与网络寿命的关系

图11 EHN节点百分比与网络寿命的关系

仿真结果表明,网络寿命T与K、ρ以及R都有关系。总体情况为:当K增加时,T会下降;当网络传输密度ρ上升时,T也同步提升。但当ρ增长到一定程度时,T几乎不再增加;当R上升时,T也增长,但R必须达到足够的百分比才能体现出其优势。这说明在汇聚路由算法中,随着传输距离增加(对应传输密度ρ),网络中能够及时找到足够的下游节点进行数据传输,确保了数据传输的有效性。

而优先充电节点增加了备用供能节点后,网络性能发生了一定变化,主要表现为:在第1个实验中,网络寿命T的下降趋势有所缓和,会更早进入T的稳定状态;在第2个实验中,备用供能节点为NHN提供的优先充电效果在r较小时更明显,此时ON节点需要更多的EHN用于中继,因此,需要消耗更多的能量;在第3个实验中,当EHN节点增加时,优先充电机制能够使其更好地工作,网络寿命T的优势也更明显。这说明具有优先充电机制的汇聚路由算法在节能和延长网络寿命方面具有更好的性能表现。

在为智能电网监控服务的无线传感器网络中,由于监控流量变化不大,因此重负载捕能节点数量也相对较少,其对优先供能节点的需求保持在一个较小的范围,优先充电的额外成本可控。各个节点的传输距离在较小的条件下,可以更好地协调好数据传输效率和网络寿命的性能。

4 结束语

为提高智能电网监测网络的数据传输有效性并延长网络寿命,本文提出了一种具有能量捕获功能的无线传感器网络节能汇聚路由数据传输方案,并设计了一种基于优先充电机制的数据汇聚树路由算法。利用整型线性编码和最小权重捕获支撑树路由算法实现节能的数据传输,并对重载捕能节点进行优先充电,从而实现网络寿命延长和有效数据传输的目的。该路由方案具有较小的算法复杂度,仿真结果表明,其能够提高数据传输的有效性,优先充电机制也能更合理地提高网络寿命。

在下一步的研究中将重点考虑如何甄选优先充电的重载EHN节点,以及提高EHN节点和优先充电节点在所有节点中的比例。