智能电网中基于平衡树的无线Mesh接入网络路由算法

赵彦平,唐国琦,李 良,全明睿

(1.国网山西省电力公司检修分公司, 山西 太原 030032; 2.北京邮电大学, 北京 100876; 3.北京智芯微电子科技有限公司, 北京 100192)

0 引 言

智能电网的发展为智慧城市的建设创造了必要的基础条件，是智慧城市建设不可或缺的重要组成部分，同时是电力产业发展的必然趋势[1]。近年来，由于现有电网中的业务种类繁多，且不同的业务对网络性能有不同的要求[2]，无线Mesh网络在智能电网的发展中得到了广泛的应用，它可以将多种不同类型的无线网络集中在一起进行统一管理，为智能电网中不同的业务类型提供多种不同的无线通信服务。无线Mesh网络同时具有WLAN(wireless local area networks)和Ad hoc二者的优势，支持多点对多点的网状通信模式[3]，具有电磁辐射小、多跳、自组织、自平衡、分布式控制等优点，是一种传输速率高、网络容量大和覆盖范围广的无线网络，它的出现为解决智能电网“最后一公里”接入问题提供了新的思路[4]，因此，如何更有效地利用无线Mesh网络成为发展智能电网的当务之急。

针对上述问题，研究者对无线Mesh网络作出了深入的研究，在路由算法方面，针对当前智能电网中存在的大量智能组件，M.S.Kemal等[5]提出了MTFW(maximum traffic flow weight)算法[5]，用以解决Mesh网络在智能电网中网关数据的收集问题。文献[6]提出了一种直线路由算法，使用接近于直线的路径向源节点和出口网关发送简要报文，为Mesh骨干网络提供了一个实用的解决方案。文献[7]深入研究了GPSR(greedy perimeter stateless routing)和RPL(routing protocol for low power and lossy networks)路由算法在智能电网无线Mesh领域网中的应用特性，证明了这2种路由算法是无线Mesh领域网络中最合适的路由算法。文献[8]基于传统的AODV(ad hoc on-demand distance vector routing)路由算法设计了一种AODV -UU(AODV-uppsala university)路由算法，并将该算法应用到智能电网的监管系统中，结果表明，该算法可以有效地提高系统的吞吐量，降低网络的通信时延。文献[9]基于链路质量和负载感知提出了一种预期路径带宽路由度量模型EPBW(expected path bandwidth)，实验结果表明基于该度量模型的路由算法可以大大提高无线Mesh网络的性能。文献[10]提出了一种改进的、基于路径稳定性的路由算法RS-MAODV(multicast AODV base on path stability)，利用链路间的相关性，选择最稳定的链路进行数据传输，数据结果表明，该算法可以有效降低系统的丢包率和通信时延。

以上算法虽然可以一定程度提高网络性能，但在无线Mesh网络中，当节点的数据缓存队列过长时，以上算法均不能根据实际情况均衡节点的数据流，最终将导致节点数据拥塞，致使系统丢包率和传输时延上升[11]。针对上述问题，本文使用平衡树模型，综合考虑节点剩余容量和数据转发所需跳数建立路由判据模型，提出了一种基于平衡树的无线Mesh网络路由算法AODV-BT(AODA-balance tree)，仿真结果表明，AODV-BT算法能有效地解决智能电网中存在的数据拥塞问题，提高Mesh网络的吞吐量和可靠性，降低系统的通信时延和丢包率，有效提高网络的整体性能。

1 系统结构

1.1 智能电网中的无线Mesh网络结构

无线Mesh网络在智能电网中的网络拓扑如图1所示。该网络结构采用典型的混合Mesh网络结构[12]，每个Mesh用户终端除了要传输自己的数据之外，还要为其他节点提供路由功能。无线Mesh网络在智能电网中的主要功能是为电网中的实时监控系统和控制系统提供无线接入服务。由于不同的无线Mesh用户终端会分布在不同的地理位置，智能电网中的无线Mesh网络结构通常分为2层：第1层是Mesh骨干网，由Mesh主网关构成，其主要功能是将Mesh子网关收集的数据进行汇聚并上传至核心网络；第2层是Mesh接入网，由Mesh子网关和Mesh用户终端构成。Mesh子网关主要提供无线网关和路由功能，即收集Mesh用户的数据并将数据上传给Mesh主网关，同时作为路由器为Mesh用户提供数据转发和路由功能。Mesh用户终端的功能主要是作为主机和路由器。作为主机，负责采集并上传用户信息数据；作为路由器运行路由发现、路由维护等基本的路由协议，为其他用户提供路由和数据转发服务。

无线Mesh网络实现了Mesh用户之间的互联，同时使所有Mesh用户可以共享核心网络的资源。在上述的Mesh网络结构中，由于接入层有大量的用户，需要传输大量数据，使其成为整个网络结构的核心。在Mesh网络中，距离Mesh子网关较远的用户节点需要以多跳的方式将数据传至Mesh子网关，因此，靠近网关的用户终端需要转发数据会相对较多，容易使该用户终端的数据缓存队列排队等待时间过长，进而会造成网络数据拥塞，影响系统的吞吐量、时延和可靠性。所以，深入研究和分析接入网的特点和性能是解决无线Mesh网络问题的第一步。

1.2 智能电网接入层无线Mesh网络建模

为了更好地分析接入网的网络结构特点以及其中可能存在的问题和风险，本文建立了接入网的网络模型，如图2所示。

无线Mesh接入子网的网络拓扑由至少一个Mesh子网关(sub mesh gateway, SMG)和多个Mesh用户终端构成。为了保证任意的Mesh用户终端都可以将自己的数据上传至子网关，本文假设，每个Mesh用户到网络中子网关的距离小于hmax，hmax表示在Mesh子网关有效通信范围内，距离其最远的Mesh用户终端到该子网关的跳数。则在图2中n需满足n≤hmax，以确保第n层用户节点可以将数据传至Mesh子网关。此外，根据Mesh用户终端到Mesh子网关的最小跳数，对接入网进行分层：①与Mesh子网直接相邻的Mesh用户终端即到Mesh子网关最小跳数为1的用户终端为第1层；②与第1层用户终端直接相邻且到Mesh子网关最小跳数为2的Mesh用户为第2层。以此类推，定义第n层节点与第n-1层节点直接相邻且到Mesh子网关的最小跳数为n。这样，以Mesh子网关为中心，以到Mesh子网关最小跳数为半径，建立一个多层次的智能电网接入层网络模型，并假设第1层节点可以和Mesh子网关进行直接通信，而第i层(i≥2)的节点只能通过其之前的节点将数据转发至Mesh子网关。

图1 无线Mesh网络在智能电网中的结构Fig.1 Wireless mesh network in smart grid

本文将接入网的结构表示为(N,L)，其中，N表示所有Mesh终端所组成的集合，L表示所有可用链路组成的集合，则对于任意节点u,v∈N，(u,v)表示从节点u到节点v的所有链路。接入网络模型如图2所示。图2中，当第3层的节点i,j,k到第2层节点的链路分别为(i,v)，(j,v)和(k,v)，即节点i,j,k均选择第2层的v节点作为他们的转发节点时，便将节点v看作是关键节点，而随着v节点转发的数据包不断增多，其缓存队列会不断增加，当其剩余的数据缓存队列长度为0时，就称该节点为拥塞节点。当节点v变成拥塞节点后，节点i,j,k的数据缓存队列便会迅速增加，进而成为新的拥塞节点，以此类推，第4层中以i,j,k为下一跳的节点也会成为新的拥塞节点，即这种拥塞现象会反向传播，最终导致整个网络的吞吐量下降、通信时延和丢包率增加。而且，越靠近Mesh子网关的通信节点由于其转发的数据量多，越容易成为拥塞节点，导致网络数据拥塞。同时，由于每个Mesh用户终端都可以为其他用户转发数据，任何一个终端都有可能成为拥塞节点。因此，根据电力数据传输特点设计适合无线Mesh网络的路由算法是有效利用Mesh网络解决智能电网“最后一公里”接入问题的关键。

图2 接入层网络模型Fig.2 Access network model

2 基于平衡树的无线Mesh网络数据转发机制

针对智能电网无线Mesh网络中由于数据流过度集中造成的网络数据拥塞问题，本文在传统AODV路由算法的基础上，引入平衡树模型，综合考虑节点剩余容量和转发数据所需跳数作为主要路由判据，提出了一种基于平衡树的无线Mesh网络路由算法AODV-BT，通过分析节点的剩余容量，平衡智能电网中各节点之间的流量，减少了关键节点的数据流负载，有效地解决网络数据拥塞的问题，提高了网络吞吐量，降低了网络时延和丢包率。

2.1 AODV路由算法

AODV是一种反应式路由协议，其路由发现和路由保持过程不需要记录节点每一跳的详细路由信息[13]。AODV路由算法以跳数作为度量值，设任意2个Mesh用户终端之间的权重为W，相邻2个终端之间的权重为1，则任意2个节点u,v之间的权重可表示为

W(u,v)=HOP(u,v)=

(1)

从源节点S到目的节点D的最优路由定义为转发数据通过最少跳数的路径。因此，在AODV路由协议中任意2节点间的路由判据M定义为

(2)

2.2 基于平衡树的路由判据模型

平衡树原指在一棵树中，任意节点的左右子树的高度差不超过1。本文将该思想扩展为在通信网络中相同层级的任意节点到根节点的路径权重应该相近或相等。

定义节点剩余容量为节点可以用来存储和转发的数据容量。假设任意节点v的数据缓存队列总容量为Cv，在某一时刻t已经被占用的容量为Uv(t)，则该节点在t时刻的节点剩余容量Ai(t)可表示为

(3)

综合考虑数据转发所需跳数(HOP)和节点剩余容量(A)作为路由判据，计算2个节点之间的权重ω为

ω(u,v)=α/Av(t)+(1-α)HOP(u,v)

(4)

(4)式中，α表示相应因素在权重中的比重，取值为0到1。由(3)式和(4)式得到任意2节点间的路由判据M为

(5)

2.3 AODV-BT路由算法

AODV-BT算法的流程如图3所示。该算法对路由表进行了修改，将节点维护的路由表中的路由判据字段替换成新的路由判决量，即将跳数字段替换成M来选择下一跳路由。

图3 AODV-BT路由算法流程Fig.3 AODV-BT routing algorithm process

在智能电网中，每个节点都是固定的，因此，无线通信链路质量相对稳定。节点间的链路一旦建立，在短时间内不会发生突发变化。本文根据这个特点，设计路由表中节点剩余容量的更新策略：节点剩余容量随着数据的传输发生改变，节点每传输完一次数据，其剩余容量就会增加一次，同时这个变化会立刻更新到路由表中，下一跳节点的剩余容量信息由路由请求回复数据包(route replies package,RREP)和HELLO数据包进行传递，只有当节点接收到RREP数据包或HELLO数据包时才会更新路由表中的路由判据。源节点根据更新后的路由判据M重新确定下一跳节点，以此保证在每次路由选择时都是基于最新的节点剩余容量信息。

3 数值结果分析

本文采用网络仿真软件OPNET，对AODV-BT和AODV路由算法进行仿真，并对其路由性能进行对比分析。主要性能包括：网络的吞吐量、通信时延以及网络丢包率。

3.1 参数设置

根据对无线Mesh接入网在智能电网中的网络结构及其网络模型的分析，在OPNET中搭建仿真场景，为了更好地分析路由算法的性能，仿真场景中的所有通信节点均使用静态IP地址。仿真参数设置如表1所示。

表1 仿真参数

3.2 仿真结果分析

图4是随网络运行时间变化，AODV-BT和AODV路由算法在相同场景下的数据平均吞吐量，结果表明：随着网络的运行2种算法的网络吞吐量均趋于稳定，AODV-BT路由算法的网络吞吐量明显高于AODV路由算法。

图4 Mesh网络平均吞吐量Fig.4 Average throughput of mesh network

图5为随网络运行时间的变化，AODV-BT和AODV路由算法在相同场景下的通信时延，结果表明：和传统AODV路由算法相比，AODV-BT路由算法可以有效降低网络的通信时延，并且时延抖动相对平缓。

图5 Mesh网络平均通信时延Fig.5 Average delay of mesh network

图6反映了AODV-BT和AODV路由算法在相同场景下的丢包率随网络运行时间的变化情况，结果表明 ，本文所提机制能够大大降低网络的丢包率，提高网络的可靠性。

图6 Mesh网络平均丢包率Fig.6 Average packet dropped of mesh network

通过以上仿真分析可以看出，本文提出的基于平衡树的AODV-BT算法，可以将网络中的数据流量均匀地分布在各个节点上，提高节点的数据传输效率，从而提高整个网络的吞吐量，同时，还能有效地减少网络的通信时延和误码率。

4 结束语

本文深入研究了无线Mesh网路在智能电网中的应用特点，对其网络结构进行了建模，分析了该网络结构中存在的问题。并针对无线Mesh网络中存在的节点数据拥塞问题设计了一种基于平衡树的AODV-BT路由算法。该算法将传统的AODV路由算法和平衡树模型相结合，引入节点剩余容量作为路由判据，使得无线Mesh网络中的数据流量能够均匀地分布在网络的各个节点而不会聚集在少数节点上，有效地解决了智能电网无线Mesh网络中存在的由于节点数据拥塞而导致整体网络性能下降的问题。最后，利用OPNET仿真平台对该路由算法进行仿真。仿真结果表明，相比传统的AODV路由算法，本文提出的AODV-BT路由算法能够有效地提高网络的吞吐量，降低通信时延和丢包率，增强网络的可靠性和有效性。但是，本文只针对单一场景进行仿真分析，并未考虑多接入点的情况，因此，在未来的研究中将结合节点内部的排队机制，进一步研究AODV-BT路由算法在复杂场景下的路由性能。

参考文献：

[1] VINEETHA C P， BABU C A, Smart grid Changes, Issues and Solutions, intellelligent green building and smart grid[C]//2014 International Conference on Intelligent Green Building and Smart Grid (IGBSG). Taipei, China:IEEE Press, 2014:1-4, 23-25.

[2] WU Dapeng, ZHANG Puning,WANG Honggang ,et al. Node Service Ability aware Packet Forwarding Mechanism in Intermittently Connected Wireless Networks[J] .IEEE Transaction on Wireless Communications, 2016, 15(12): 8169-8181.

[3] 胡伏湘.基于AODV的无线Mesh网络路由协议优化设计[J].湖南师范大学自然科学学报,2015,38(3):85-90.

HU Fuxiang.Optimization Design of Routing Protocol of Wireless Mesh Network Based on Aodv[J].Journal of Natural Science of Hunan Normal University,2015,38(3):85-90.

[4] GHARAVI H ， HU Bin. Multigate mesh routing for smart grid last mile communications [C]//In Wireless Communications and Networking Conference (WCNC).USA: IEEE Press,2011, 275-280.

[5] KEMAL M S， CEOCEA A， OLSEN R L. Gateway placement for wirless mesh networks in smart grid network planning[C]//2016 10th International Conference on Compatibility, Power Electronics and Power Engineering(CPE-POWERENG).Bydgoszcz, Poland:IEEE,2016:144-147.

[6] XU Yi , WANG Wenye. Wireless mesh network in smart grid: Modeling and analysis for time critical communications [J]. IEEE Transactions on Wireless Communications, 2013, 12(7): 3360-3371.

[7] HO Quangdung, GAO Yue , RAJALINGHAM G. Performance and applicability of candidate routing protocols for smart grid’s wireless mesh neighbor area networks [C]// IEEE International Conference on Communications.USA:IEEE Press, 2014:3682-3687.

[8] BABA A E,RUPPERT S A,JABER N,et al.AODV adaptation for semi-static smart grid monitoring systems[C]//2012 IEEE International Conference on Smart Grid Engineering(SGE).UOIT Oshawa,Canada:IEEE Press,2012.

[9] DENG Xiaoheng,LIU Qiang,LI Xu,et al.Channel Quality and Load Aware Routing in Wireless Liu Mesh Network[C]//IEEE Wireless Communications and Networking Conference (WCNC).USA:IEEE Press,2013:2068-2073.

[10] 李帅,蔡明.基于路径稳定性的MAODV路由协议的改进[J]. 现代电子技术, 2015, 38(5): 1-4.

LI Shuai , CAI Ming. MAODV routing protocol improvement based on stability of path [J]. Modern electronics technique, 2015, 38(5): 1-4.

[11] WU Dapeng, ZHANG Hongpei, WANG Honggang,et al. Quality of Protection (QoP)-Driven Data Forwarding for Intermittently Connected Wireless Networks[J]. IEEE Wireless Communication, 2015, 22(4): 66-73.

[12] METS K, OJEA J A, DEVELDER C . Combining power and communication network simulation for costeffective smart grid analysis[J]. Communications Surveys Tutorials, 2014, 16(3): 1771-1796.

[13] WU Dapeng, WANG Yanyan, WANG Honggang ,et al. Dynamic Coding Control in Social Intermittent Connectivity Wireless Networks[J]. IEEE Transactions on Vehicular Technology, 2016, 65(9): 7634-7646.