基于融合判决的智能用电无线传感器网络拥塞避免路由算法

冯 森，唐良瑞，郝建红

(1.华北电力大学新能源电力系统国家重点实验室，北京 102206;2.华北电力大学电气与电子工程学院，北京 102206)

0 引言

近年来，随着智能电网技术的不断发展，其在用电侧的业务应用系统也逐步完善，对智能用电通信网传输带宽、时延和可靠性等方面提出了更高的要求［1，2］。因此，具有低成本、低功耗、自组织、灵活性、可靠性及可扩展性强等特点的无线传感器网络(Wireless Sensor Networks，WSN)便成为一种面向智能用电可以选择的重要技术手段［3］。

在WSN 中，节点的能量、计算和通信能力极其有限，因此无线传感器网络面临较大的能量和带宽等资源压力［4］，如何高效均衡地使用节点能量，延长网络生命周期是路由算法设计的主要目标［5，6］。然而节点大规模密集部署的传感器网络具有多对一的流量模式，且其拓扑结构和无线链路质量动态变化，以及事件触发导致流量突发性等，这些都容易引起网络发生拥塞，从而导致丢包率和节点能耗增加，严重影响网络的服务质量和生命周期。因此，基于拥塞控制的路由算法成为WSN 的研究热点［7］。在WSN 拥塞控制研究中速率控制被广泛采用。CODA［8］研究了WSN中拥塞检测及避免，同时采用了闭环源调节机制，但是这种基于缓存长度的拥塞检测方法带来了额外的开销和网络流量。此外还有ESRT［9］、UCC［10］等基于速率控制的拥塞路由算法。总之，速率限制机制需要节点不间断地观察它们父节点的发送行为以决定何时生成令牌，这一连续性监控代价过高且耗能大。除了上述流量控制方法，还有一些研究探索了其他避免拥塞的机制，比如基于流量调度的路由算法。NCCAR［11］通过节点的区域拥塞度值选取路由，并结合网格编码方法提高数据传输的可靠性，合理地避免拥塞。TADR［12］通过由空闲或低负载的节点构成的多路径来分散过多的包，采用动态路由技术来减轻拥塞以便降低静态多径路由的额外开销，然而其系数取值具有不确定性并且对路由的能效性考虑不周。同时TADR 在面临拥塞时会有较大的端到端延时，并且每次当深度改变时计算深度开销过大。

为了克服TADR 的上述缺陷，本文提出一种基于融合判决的拥塞避免路由算法。算法基于主动避免拥塞的设计思想，综合考虑节点到Sink 距离，节点剩余能量和缓冲区队列长度作为路由下一跳评价标准，建立隶属度函数并进行融合判决，根据判决结果选取下一跳节点使数据包转发避开拥塞节点最终到达Sink。实验表明，算法有效地避免了节点拥塞，提升网络的吞吐量同时均衡全网节点能耗，延长了网络的生命周期。

本文后续部分安排如下:第一节详细描述所提出的算法;第二节进行实验仿真分析;第三节给出结论。

1 基于融合判决的拥塞避免路由算法

1.1 系统模型及问题描述

智能用电通信网承载了大量多元化业务，其中用电基本业务与用电扩展性业务这类业务数据对实时性要求虽然不高，但具有周期性质，在整点上报时业务量突增。此外，在面向智能用电的WSN 拓扑结构中，多个源节点采集业务数据并通过中继节点中转，以多跳的方式发送到集中器。可以看出这种基于事件驱动的WSN 中的数据传输存在“多对一”的特性。在流量突发的情况下，这种流量模式会引起网络发生拥塞进而增加网络延迟和丢包率，由此造成的数据包重传还会极大地消耗节点的能量，缩短网络生命周期。因此，节点的缓冲区占用情况作为一个可靠的拥塞检测指标，在建立路由时考虑这一指标避开缓存队列状况不佳的节点将有效地转移网络流量至空闲或负载较轻的节点，从而减轻网络拥塞。此外，由无线传播能耗模型可知无线传感器网络节点在传送数据时的能量消耗与传播距离的平方或四次方呈正比，在源节点远离Sink 的情况下，如何缩短数据传输路径长度及均衡节点能量消耗成为延长无线传感器网络生命周期的关键，因此节点剩余能量及到基站距离仍是建立路由时需要考虑的关键因素。

为了解决以上问题，本文提出的算法采用主动的拥塞避免机制建立路由。首先依据前向传播邻居节点的缓存队列长度、剩余能量和到基站距离3 个特征参量对路由下一跳节点选择的不同影响，将其归一化以建立合适的隶属度函数，从而直观地反映这些指标对选择下一跳节点的决定作用。然后利用算子将隶属度函数进行融合以得到最后的判决信度，根据最后的判决信度确定路由的下一跳节点。

1.2 算法描述

基于融合判决的拥塞避免路由算法共分为3个阶段:(1)邻居节点发现阶段;(2)最优路径确定阶段;(3)数据传输阶段。

1.2.1 邻居节点发现阶段

无线传感器网络中任意节点i 都维护一个自身信息列表list(i)，其中包含节点i 在网络中的标识id(i)，节点i 当前的剩余能量eres(i)，节点i 到基站的距离dbs(i)，节点当前的缓存队列长度q(i)以及节点i 的下一跳邻居节点列表nbr(i)。

由Sink 发起邻居节点发现消息广播，其中包含Sink 自身的id(s)和位置信息。任意节点a 收到Sink 的消息后，更新自身消息列表，并将Sink的id 加入到自己的下一跳邻居节点列表中，继续广播包含自身id 的消息。任意节点j 收到来自非Sink 节点k 的消息后，若dbs(j)＞dbs(k)则更新自身消息列表，添加k 的消息到nbr(j)，即节点k 为j的前向传播邻居节点，继续广播直到所有节点接收到消息并更新，则邻居发现阶段结束。

1.2.2 最优路径确定阶段

此阶段根据融合判决结果由源节点起逐跳选取下一跳节点从而确定出最优路径。

算法在选取下一跳节点时综合考虑节点的剩余能量，节点到基站距离和节点缓存队列长度这3点因素作为评价指标。在节点剩余能量相同的情况下，节点到基站的距离越小节点传输数据消耗的能量越小，所以在节点剩余能量相同的情况下，优先选择距离基站近的节点担任转发节点;在节点到基站距离相同的情况下，为了避免剩余能量小的节点率先失效，优先选择剩余能量多的节点作为下一跳;而在节点剩余能量、节点到基站距离均相同的情况下，缓存队列长度小的节点负载轻，优先选作下一跳节点可以有效避免发生拥塞。而现实情况下，同时考虑节点的3 个评价指标的情况较为复杂，为了消除3 种评价指标下判决结果的不一致性，CARF 算法为单个指标建立隶属度函数，反映其对选择下一跳的判决影响，然后将各个评价指标隶属度函数进行融合判决，得到最终的判决信度，由此选出最合适的下一跳节点。

在下一跳节点选取中，节点缓存队列长度越小对成为下一跳节点的贡献就越大。qmax作为节点i 的最大缓存，q(i)为节点i 的当前缓存队列长度，则归一化后的节点i 的缓存占用率Fq(i)为

可见节点当前缓存队列长度越小则缓存占用率越小，说明该节点流量负载较轻，不易发生拥塞，适合作为路由下一跳节点进行数据包转发，因此本文采用高斯函数为其建立隶属度函数，如式(2)所示

式中:σ，c 为调节隶属度函数的常数参量，修改此常数可控制隶属度函数曲线。本文中取σ = 0.5，c =－0.1 。μq(i)越大，说明该节点隶属于下一跳节点的概率越大，否则隶属于下一跳节点的概率越小。其曲线如图1所示。

图1 节点缓存占用率指标隶属度函数曲线Fig.1 The membership function curve of node cache usage

由能量模型计算公式可知，为使全网节点减少消耗的能量，则在下一跳节点选取时距离基站越近的节点越优。因此，节点距离基站越近则其成为下一跳节点的概率越大，将节点到基站的距离值归一化后作为该节点成为下一跳可能性的判决信度，同样可采用高斯函数为其建立隶属度函数:

式中:dbs(i)为节点i 到Sink 的距离;dmax为离Sink最远节点的距离。

为了均衡全网节点的能耗，优先选取剩余能量高的节点作为下一跳。将节点的剩余能量值归一化后作为该节点成为下一跳可能性的判决信度，为了使其符合上述两个评价指标对节点隶属度的影响，令

式中:eres(i)为节点i 当前剩余能量;e0为节点初始能量。

由上述分析可知，三个评价指标进行归一化后都变为成本型属性，根据其对路由下一跳选择的判决影响，均采用高斯函数建立隶属度函数。

为了较好地融合节点缓存队列长度、节点到基站距离和节点剩余能量对该节点成为下一跳节点隶属度的影响，本文采用下式对其进行融合:

不难发现，该式可实现3 个评价指标的加强性和调和性并满足以下特性:

(1)是一个缩维映射F:[0，1]2→ [0，1]

(2)F(0，0，0)= 0，F(1，1，1)= 1

(3)F(a，b，c)≤F(d，e，f)，a ≤d，b ≤e，c ≤f

(4)F(a，b，c)= F(b，a，c)= F(a，c，b)=F(c，b，a)

(5)F(a，b，c)≥max(a，b，c)，a ≥0.5，b ≥0.5，c≥0.5 或F(a，b，c)≤min(a，b，c)，a ≤0.5，b ≤0.5，c ≤0.5

(6)min(a，b，c)＜ F(a，b，c) ＜ max(a，b，c)，a ＞0.5 ＞b ＞c 或a ＞b ＞0.5 ＞c

其中a，b，c，d，e，f∈(0，1)。

因此将式(7)的融合结果作为最后的判决信度，确定隶属度函数值μ(i)最大的节点为路由下一跳节点。

1.2.3 路由维护阶段

最优路径确定以后，随着数据传输轮数的增加，网络中节点的拥塞情况和剩余能量发生变化，但频繁执行算法选取最优路径会产生过大的控制开销，造成能量浪费。因此，本文为传输路径上的节点设定拥塞阈值，若路径上任意节点i 的缓存占用率超过这一阈值或者由于能量耗尽失效，则节点发送路由维护请求，算法立即重启最优路径的选取过程。

2 仿真结果及分析

本文采用MATLAB 进行实验仿真，选取经典的路由算法DD［13］和TADR 作为基本对比算法。仿真中固定个数节点随机均匀分布在边长为100 m 的正方形区域中，汇聚节点位于(0，0)处，所有节点一旦放置就不再移动，每个节点的初始能量为0.5 J，具体仿真参数设置如表1所示。

本文使用的仿真场景中配置有1 个Sink 和4 个源节点，其中Sink 位于坐标轴原点，而源节点处于区域边缘，远离汇聚节点。这样的设置使得路由算法选取的路径需经过WSN 中大面积区域。

表1 仿真环境参数Tab.1 Simulation environment parameters

在无线传感器网络中，数据传输的可靠性是WSN 的重要性能评价指标，吞吐率在一定程度上反应了网络可靠程度。传感器节点因拥塞将会导致数据重传，而多次重传不成功时，数据包就有可能被丢弃。分别执行DD、TADR 和CARF 协议，统计得到网络吞吐率随节点总数的变化关系，如图2所示。由图2 可知，当节点数量从100 到300 变化时，执行CARF 算法的网络吞吐率最高，而DD 算法由于没有拥塞控制机制表现最差。CARF 算法建立了基于节点缓冲区包队列长度的隶属度函数，这一主动转移流量的路由策略很大程度上避免了拥塞的发生，降低了网络丢包率。虽然TADR算法考虑下一跳节点的拥塞状态，即通过节点缓冲区队列长度来检测拥塞，然而由于采用线性加权的局限性及权重系数选择的不确定性，其对网络性能改有限。本文提出的CARF 算法采用融合判决方法获得最终判决信度，实现拥塞避免路由机制，进一步提高了网络吞吐率等性能。

图2 网络吞吐率与节点数量的关系Fig.2 The relationship between the network throughput and the number of nodes

此外，网络生命周期和节点平均能耗也是衡量拥塞控制路由算法性能的重要指标。其中，WSN 网络生命周期的精确定义是由具体应用环境来决定的，有些应用场景可以容许相当一部分的节点失效，而有的应用中任一节点死亡都会对网络产生至关重要的影响。本文选择首个节点死亡时数据发送轮数定义为WSN 网络生命周期。由图3 可以看出，CARF 算法与DD、TADR 算法相比有效提高了网络生命周期。CARF 算法在路由下一跳节点选择时结合节点缓冲区队列长度、节点到汇聚节点距离和剩余能量水平3 个评价指标，得到了避免拥塞及优化网络能耗和生命周期的实验结果。并且不难看出随着网络规模的增大，CARF 算法的优势愈发明显。这说明了CARF 算法在不同的网络规模中性能表现都更为优异。

图3 网络生命周期与节点数量的关系Fig.3 The relationship between the network lifetime and the number of nodes

实验仿真结果与本文算法设计初衷相吻合，即全面考虑影响WSN 网络拥塞及能耗的因素，将其通过隶属度函数建立起与下一跳节点选择的关系，并利用融合判决方法确定最优路径，优化全网能量消耗，有效延长WSN 网络的生命周期。

另一路由算法仿真评价参数为节点能量消耗，它衡量将一个数据包由源节点转发至Sink 时节点的平均消耗能量，其反映了WSN 网络的能量有效性水平。本文取各路由算法运行至最大生命周期轮数时每个节点每轮的平均能耗做出分析与比较。图4 展示了不同拓扑设置场景下的节点能耗仿真结果。可以看出本文的CARF 算法相较DD、TADR 算法拥有最低的节点能耗水平。DD 算法下数据包的发送建立在Sink 发布查询的基础上，而Sink 还要在发布查询的过程中建立梯度场，由于网络通信状态的动态性，无法保证按已建立的路径在能耗方面最优，此外随着网络负载提高丢包率大幅上升，重传造成大量的能量消耗。TADR 算法能耗代价明显优于DD，其在WSN 区域根据普通节点到汇聚节点的通信距离将其分成逐跳增加的固定区域，并建立基于节点跳数的深度虚拟势能场，但这种方法使得所建路由的势能场值是离散的，并且每次当深度改变时计算深度开销过大，而本文算法中根据节点到Sink 的距离建立隶属度函数，更为精确直接地反映距离因素与能量消耗的关系，并且许多情况下跳数灵活变化的路由要优于固定跳数路由。此外，TADR 算法只建立了基于跳数的深度势能场和基于节点队列长度的势能场，造成算法只是单一的保证了最小跳数路由的建立并且可能产生节点回传情况，从而忽略了网络整体能耗的均衡性。CARF 算法中路由的建立使得数据包的发送为正向距离传播，有效地避免了节点回传和局部环传递等问题，从而降低了网络节点整体能耗，使得网络平均节点能耗稳定地维持在一个较低的水平。同时，与其他路由算法相比其性能受到网络规模变化的影响也最小。

图4 网络平均节点能耗与节点数量的关系Fig.4 The relationship between the average energy consumption and the number of nodes

3 结论

结合智能用电通信业务的流量特点，针对已有拥塞控制路由算法的不足，本文提出一种无线传感器网络中的基于融合判决的拥塞避免路由算法。该算法考虑节点缓存队列长度、节点到基站距离和节点剩余能量三个影响WSN 网络性能的重要因素，建立隶属度函数并通过融合算子得到最终判决信度来确定路由下一跳节点选择。实验仿真结果表明，CARF 算法相比DD、TADR 算法更有效地提升了网络吞吐率，并且具有更高的节点能效性和均衡性，使无线传感器网络获得了更长的生命周期。

［1］Aggarwal A，Kunta S，Verma P K.A proposed communications infrastructure for the Smart Grid［C］.Innovative Smart Grid Technologies (ISGT)，Gaithersburg，MD，USA，19－21 Jan.，2010:1－5.

［2］郭云鹏，刘伟佳，文福拴.智能配电系统的发展现状与展望［J］.华北电力大学学报，2014，41(5):74－81.

［3］Gungor V C，Lu B，Hancke G P.Opportunities and challenges of wireless sensor networks in smart grid［J］.IEEE Transactions on Industrial Electronics，2010，57 (10):3557－3564.

［4］Sergiou C，Vassiliou V.Estimating maximum traffic volume in wireless sensor networks using fluid dynamics principles［J］.IEEE Communications Letters，2013，17 (2):257－260.

［5］Uster H，Lin H.Integrated topology control and routing in wireless sensor networks for prolonged network lifetime［J］.Ad Hoc Networks，2011，9 (5):835－851.

［6］Padilla P，Camacho J，MaciáFernández G，et al.On the influence of the propagation channel in the performance of energy-efficient geographic routing algorithms for wireless sensor networks［J］.Wireless Personal Communications，2013，70 (1):15－38.

［7］孙利民，李波，周新运.无线传感器网络的拥塞控制技术［J］.计算机研究与发展，2008，45 (1):63－72.

［8］Wan C Y，Eisenman S B，Campbell A T.CODA:Congestion Detection and Avoidance in Sensor Networks［C］.Proceedings of the First International Conference on Embedded Networked Sensor Systems (SenSys ’03)，Los Angeles，CA，US，5－7 November，2003:266－279.

［9］Hull B，Jamieson K，Balakrishnan H.Mitigating Congestion in Wireless Sensor Networks［C］.Proc.Int’l Conf.Embedded Networked Sensor Systems (SenSys ’04)，Baltimore，MA，US，3－ 5 November，2004:134－147.

［10］张玉鹏，刘凯，王广学.基于无线传感器网络的跨层拥塞控制协议［J］.电子学报，2011，39 (10):2258－2262.

［11］付彬，李仁发，刘彩苹，等.无线传感器网络中一种基于网络编码的拥塞感知路由协议［J］.计算机研究与发展，2011，48 (6):991－999.

［12］Ren F Y，He T，Das S K，et al.Traffic-Aware Dynamic Routing to Alleviate Congestion in Wireless Sensor Networks［J］.IEEE Transactions on Parallel and Distributed Systems，2011，22 (9):1585－1599.

［13］Intanagonwiwat C，Govindan R，Estrin D，et al.Directed diffusion for wireless sensor networking［J］.IEEE/ACM Transactions on Networking，2003，11(1):2－16.