智能电表网状网中的机会路由

张华峰，党 倩，崔 亮，曾玮妮

（1.国网甘肃省电力公司 科技信通部，甘肃 兰州730000；2.国网甘肃省电力公司信息通信公司，甘肃 兰州730050；3.中国人民银行兰州中心支行，甘肃 兰州730000；4.中国船舶重工集团公司第716研究所，江苏 连云港222006）

0 引 言

智能电网［1］中不仅存在电流网络，还存在着信息流的网络，用于上传采集的用电量数据和下达控制命令等。智能电网为采集数据，在控制中心和智能电表 （automated metering infrastructure，AMI）之间需要进行频繁的控制命令和数据交互。为了传输信息，智能电网可选择3种不同网络通信类型进行组网［2］：低功耗电力线通信 （power line communication，PLC）、有线网络 （光纤、铜缆等）和无线网络。有线网络部署成本高，电力线不一定能覆盖大规模用户，无线网络部署方便，因此本文主要考虑多跳无线网络的组网方式。在多跳无线网络组网方式下，智能电表之间通过无线互联，并且能为别的智能电表转发信息，构成一个智能电表网状网 （AMI mesh network）［3］。

无线传输面临信号衰减，噪音，路径损耗问题，导致链路高丢失率。为了解决链路高丢失率问题，提升吞吐量和可靠性，机会路由［4］被用在智能电网的传输上［5－8］。机会路由是无线多跳网络中有效提升传输可靠性的新兴路由方式，智能电表网状网是一个典型的无线多跳网络，而且智能电表一旦安装位置不再发生变化、网络的拓扑固定不变，很符合机会路由要求的无线网络环境。

Yoon等［5］则在电力线网络中使用机会路由；Gormus等［6－8］在智能电表网状网中给低功耗有损网络路由协议引入机会通信概念，提出机会低功耗有损网络路由协议。他们都是采用链路信号强度、期望任意传输次数来选择候选节点集，没有最优化地选择候选节点，无法有效发挥机会路由特性，进一步提升网络性能，尽快完成采集数据的传输。

为了解决上述问题，我们根据智能电网汇聚收集数据的特点，提出尽快完成采集数据传输的机会路由问题 （opportunistic routing in smart grid，ORSG），将机会路由候选节点选择问题建模，求解得到最优的候选节点集。仿真结果表明，与基于期望传输次数 （expected transmission number，ETX）［9］、期望任意传输次数 （expected anycast transmission，EAX）［10］的机会路由和多并发流的机会路由协议（opportunistic routing for multi－flow，ORMf）［11］相 比，我们的方法在最小流的完成时间降低39%、30%和400%，汇聚延时降低21%、12%和36%，汇聚吞吐量比ETX、EAX 高24%和29%，低于ORMf。

1 机会路由原理和相关工作

1.1 机会路由原理

机会路由是一种新的路由方法，它充分利用不可靠的无线链路和无线媒介的广播特性，来提升传输的可靠性和吞吐量。利用图1中的例子来阐述它的主要思想。图1是一个4个节点的多跳无线网络，链路的包投递率 （packet delivery ratio，PDR），即数据包通过此链路正确接收的概率，标记在边上。如节点0 到节点1 的包投递率为90%，节点0到节点2的包投递率为40%。统计一定时间范围内，目的节点正确接收数据包数量和发送节点发送的所有数据包数量可以计算得到PDR。其它参数一致情况下，距离越远链路包投递率越低。目前，节点0需要发送数据给节点3。

图1 机会路由基本原理

如果使用传统路由 （traditional routing，TR）可以有多种不同路径的可选择。例如一跳路径，节点0直接发送到节点3，如果链路发生丢包需要为每个包发送多次；或者三跳路径，节点0 经过节点1 和2 发送到节点3，因为多跳，每个包也需要传输多次。

选择一跳路径时，节点0直接发送给节点3，节点3可能没有正确收到。因为无线广播媒介的特性，节点1、2有可能正确偷听 （overhear）到数据包，而且节点1、2 和3是否正确收到数据包是相互独立的，即多用户分集特性。由正确偷听到数据包的节点1或节点2重发数据包给节点3，要比节点0重发更好。

选择三跳路径时，节点2甚至节点3可能正确偷听到节点0给节点1发送的部分数据包，如果节点1再转发这些数据包给它们就造成了冗余，导致信道资源的浪费。

机会路由的主要思想是：不预先设定一个固定的下一跳转发节点，而是设定多个候选节点或候选转发节点（candidate forwarder）。在发送数据包后，根据候选节点的实际接收数据包情况，在所有正确接收的候选节点中选择距离目的节点最近的候选节点作为真正的转发节点。本例中节点3、2和1都是节点0的候选节点。当节点0发送某个数据包后，节点2 和1 正确接收但节点3 未正确接收，距离目的节点最近的节点2成为这个数据包真正的转发节点。当节点0发送下一个数据包后，节点3和1都正确接收，节点3就是目的节点本身就不需要再转发。它发掘多用户间的差异性，充分利用传输的机会，以达到减少传输次数提高吞吐量的目的。

1.2 相关工作

Yoon等［5］在电力线网络中使用机会路由。Gormus等［6－8］在智能电表网状网中给低功耗有损网络路由协议（routing protocol for low power and lossy networks，RPL）引入机会通信概念提出机会低功耗有损网络路由协议 （opportunistic RPL，ORPL）协议。RPL通过构建以汇聚节点为根节点的树结构，来为每个节点确定传输路径。每个节点有一个父节点负责上传数据。而ORPL 为每个节点选择一个默认父节点后，再选择备份的一个到3个父节点作为候选节点。当默认父节点没有正确收到数据包后，由候选节点中离根节点最近的节点来转发。但他们都是采用链路信号强度、期望任意传输次数来选择候选节点集，没有最优化地选择候选节点，无法有效发挥机会路由特性，进一步提升网络性能，尽快完成采集数据的传输。

He等［11］在多并发流的无线网络场景下，分析了机会路由的最优候选节点选择和转发速率分配问题 （opportunistic routing for multi－flow，ORMf），但 是 他 们 考 虑 的 并发流是多对多的流量模型，不是智能电网中多对一的汇聚流量模型。而且他们的优化目标是保障数据流之间的公平性同时最大化所有流的吞吐量，不一定能较快完成收集数据的传输。因此我们提出以尽快完成收集数据的传输为目标的最优候选节点选择问题。

2 系统模型

智能电网通过无线多跳网络来实现数据收集，即智能电表网状网如图2 所示。假设BS 节点是信息汇聚目的节点，负责收集数据。BS节点知道在线的节点个数和网络的拓扑结构。每个终端节点安装智能电表负责测量用电量数据，并且为与它们互联的别的节点转发信息。假设所有的终端节点又相同的处理和存储能力。BS和节点之间的无线链路具有噪声并信号衰减，这样数据包传输过程中可能会丢失。智能电表以固定频率 （如15分钟）向BS上传数据。

图2 智能电表网状网

智能电表网状网可描述成一个无向图G＝ （V，E），包含N 个节点，其中V 为N 个节点集，E为表示节点间链路的矩阵。只有当两节点间的链路包投递率大于某阈值才认为它们之间的直接链路存在，互为邻居。也就是说对于任何一条链路l（u，v）∈E 都有一个对应的链路包投递率p（u，v），表示在无干扰情况下链路正确接收数据包成功率，这个值可以通过传播模型计算获得。假设任意节点的链路包投递率都是独立的。定义节点u 的一跳的邻居R（u）为p（u，v）≥P0的节点集合，其中P0＜＜1。对于剩下的任何不属于R（u）的节点v，链路包投递率为0，即p（u，v）＝0。

在智能电表网状网中，存在N－1 条流，除了BS 节点，别的节点都是发送节点。源节点集为 ｛sk，k＝1..N－1｝，目的节点集为 ｛dk＝BS，k＝1..N－1｝。每条流的发送量是相同的。要解决的问题是为这N－1条流寻找机会路由的路径和每个候选节点为每条流的最优转发速率，以尽快完成收集数据的传输。

3 问题描述

我们对问题进行形式化描述，先定义参数，然后依据文献 ［11］给出机会路由约束，提出优化目标和形式化表述。假设每条流需要传输的数据量相同，为Len Kbtye。定义两个二进制参数αkuv和βku 来表示对候选节点和链路的选择。表示节点u是否作为流k的候选转发节点。如式 （1）所示，节点u作为流k的候选转发节点，则β为1；否则为0

只有当节点u 和节点v 同时作为流k 的转发节点，且节点u和v 互为邻居时，节点u和v 间的链路才会被流k 所使用，如式 （3）所示

其中，BHuv表示节点u 和v 的邻居关系，互为邻居时BHuv值为1；否则为0。

3.1 机会路由相关约束

与机会路由相关的约束有3个：流守恒约束、MAC 层广播速率约束和编码约束，下面分别说明。

3.1.1 流守恒约束

流守恒约束指每一条流的中间节点流出的流速率等于流入的流速率，是网络中每个节点必须满足的。而源节点流出的流速率是该流的吞吐量，目的节点流入的流速率是该流的吞吐量，方向相反

链路 （u，v）上的流速率，λk，sk，dk分别表示第k 条流的吞吐量、源节点和目的节点。

进一步，只有当链路参与流的传输，链路上的流速率才不为0；否则，链路的流速率一定为0。这一约束可用式（5）表达

3.1.2 MAC层广播速率约束

MAC层协议决定了节点占有信道资源的时间和广播速率。假设采用无竞争的基于时槽的MAC 广播。定义参数（u）表示节点u在第t 个时槽是否为第k 条流传输数据，1表示传输，0表示不传输。当节点u 未参与第k 条流，即为0时，因为节点u 不会在任何时槽为第k 条流传输数据，所以（u）一定为0。

为了不相互干扰，任何时刻节点u 的传输范围内只允许出现一个接收者，包括它自己，见式 （6）。因为源节点不用接收来自任何节点的数据，所以需要排除源节点

其中，R（u）为节点u 的一跳的邻居。考虑如果存在T 个调度时槽，根据式 （6）可以得到

其中，C 为MAC 层的容量是一个节点无干扰时的最大MAC层广播速率。节点的平均广播速率为bk（u）＝，那么式 （7）就可以写成

3.1.3 编码约束

考虑采用带编码的机会路由，节点的转发速率受对应链路的链路质量约束。所以链路的流速率必需小于发送节点的平均广播速率和链路包投递率之积，即满足式 （10）中的约束

其中，p（u，v）是链路（u，v）的包投递率。这一约束不是很严格，但也能近似描述一个实际无线网状网的行为。虽然还存在更精确的约束模型，但是指数性的将导致问题难于求解。

3.2 问题形式化描述

其中，决策参数包括r，b。

选择候选节点集通过求解式 （11）来决定，求解得到r和b 的值后，再通过式 （5）和式 （9）即可确定α，β。α，β只由r 和b 的取值决定，得到α，β也就得到每个流对候选节点和链路的选择。总结来说，节点是通过发送速率来决定自己是否参与到流中，是否成为流的候选节点为流转发。通过发送速率分配来实现候选节点的选择。

问题 （11）可以通过内点法、单纯型法求解。由于BS节点知道在线节点的个数和网络的拓扑结构，因此可以将问题 （11）在BS节点处求解后，将候选节点选择结果分发给所有节点。由于智能电网一般部署后就拓扑极少发生变化，这种集中式求解方法是可行的。

4 性能分析

用文献 ［11］中的方法，采用Lingo API［12］计算机会路由的传输性能。实验场景为在300＊300m 的区域内随机放置节点，只要两节点之间的投递率大于P0（P0＝0.1）就存在一条链路。传播模型使用shadowing模型，节点发送功率Pt为0.28183815W，频率freq为2.4e9Hz，系统损耗sysLoss为1.0，路径损耗指数pathlossExp＿为2.0，阴影偏离std＿db＿为4.0，参考距离dist0＿为1.0m，接收门限rxThresh＿为2.44547e－08W。根据设定的传播模型参数，节点通信范围为160 m。当两点之间距离到达160 m时，节点之间的包到达率就只为0.1，到达我们设定的阈值P0。最大MAC层广播速率C设置为11Mbps。每个节点数据发送的数据量Len为125Kbyte。

我们将ORSG 与采用期望传输次数 （expected transmission number，ETX）［9］指标的机会路由，采用期望任意传输次数（expected anycast transmission，EAX）［10］指标的机会路由（OPRL）［8］和多并发机会路由（ORMf）［11］进行比较。

比较的指标为不同路由选择方式下获得的最小流的完成时间、汇聚吞吐量和汇聚延时。最小流的完成时间：所有流中吞吐量最小的流的完成时间，数据量除以最小流的吞吐量。最小流的完成时间越小，所有流的完成时间下限越高，采集任务整体越快完成。汇聚吞吐量：所有流吞吐量之和。汇聚延时：所有流的延时之和。

考虑节点数目对性能的影响，随机分布16，25，36和49个节点。每个节点数目下随机产生4个拓扑，每个拓扑下除中心节点BS之外别的节点都为源节点，顺序使用4种机会路由方式可获得的最小流的完成时间、汇聚吞吐量和汇聚延时，然后取平均值。

最小流的完成时间随节点个数从16到49的变化如图3所示。总体来看，不管在节点个数是多少情况下，ORSG的完成时间都是小于ETX、EAX 和ORMf。随着节点个数增加，最小流的任务完成时间值增加。这是因为相同范围内节点个数增加，流的数目也增加，每条流所能分配使用的带宽资源减少；而且随着流个数增加，带来更多的竞争，最小流所能竞争到的带宽资源降低。由于ORMf目标为最大化吞吐量，无法保障最小流，所以其完成时间随节点数目迅速增加。平均而言，ORSG 算法产生的最小流的完成时间比ETX、EAX 和ORMf低39%、30%和400%。

图3 最小流的完成时间

汇聚吞吐量和汇聚延时随节点个数从16到49的变化如图4和图5所示。随着节点个数和流的数目增加，汇聚吞吐量也逐步增加。ORSG 算法产生的汇聚吞吐量比ETX和EAX 高24%和29%，却低于ORMf。这是因为ORMf是以最大化吞吐量为目标来选择候选节点，所以其汇聚吞吐量略高于ORSG。但由于ORMf无法控制最小流的完成时间，虽然汇聚吞吐量较高，但其任务完成时间却低于ORSG。汇聚延时也随着节点个数和流的数目增加而增加，ORSG 的汇聚延时都比ETX、EAX 和ORMf低，平均比ETX、EAX 和ORMf低21%、12%和36%。

图4 汇聚吞吐量

5 结束语

智能电网数据采集中利用机会路由传输可提高传输效率。针对现有机会路由采用链路信号强度、期望任意传输次数来选择候选节点集，无法有效发挥机会路由特性，尽快完成采集数据的传输，提出了尽快完成采集数据的传输的机会路由问题，求解得到最优的候选节点集。仿真实验结果表明，与ETX、EAX 和ORMf相比，我们的方法在最小流的完成时间降低39%、30%和400%，汇聚延时降低21%、12%和36%，汇聚吞吐量比ETX、EAX 高24%和29%，低于ORMf。

图5 汇聚延时

［1］Fang X，Misra S，Xue G，et al.smart grid–the new and improved power grid：A survey ［J］.IEEE Communications Surveys Tutorials，2012，14 （4）：944－980.

［2］Rui Prior，Daniel E Lucani，Yannick Phulpin，et al.Network coding protocols for smart grid communications ［J］.IEEE Transactions on Smart Grid，2014，5 （3）：1523－1532.

［3］Parag Kulkarni，Sedat Gormus，Zhong Fan，et al.AMI mesh networks—A practical solution and its performance evaluation ［J］.IEEE Transactions on Smart Grid，2012，3 （3）：1469－1482.

［4］Bhorkar A A，Naghshvar M，Javidi T.Adaptive opportunistic routing for wireless ad hoc networks ［J］.IEEE／ACM Transaction on Networking，2012，20 （1）：243－257.

［5］Yoon Sung－Guk，Jang Seowoo，Kim Yong－Hwa，et al.Opportunistic routing for smart Grid with power line communication access networks［J］.IEEE Transactions on Smart Grid，2014，5 （1）：303－311.

［6］Gormus Sedat，Fan Zhong，Bocus Zubeir，et al.Opportunistic communications to improve reliability of AMI mesh networks［C］／／IEEE PES Innovative Smart Grid Technologies Europe Conference.NJ：IEEE Computer Society，2011：1－8

［7］Gormus Sedat，Tosato Filippo，Fan Zhong，et al.Opportunistic RPL for reliable AMI mesh networks［J］.Wireless Networks，2014，20 （8）：2147－2164.

［8］Gormus Sedat，Bocus Mohammud Zubeir.Efficient cooperative anycasting for AMI mesh networks［C］／／IEEE Global Communications Conference，GLOBECOM.IEEE Computer Society，2013：2661－2666.

［9］Sheshadri RK，Koutsonikolas D.An experimental study of routing metrics in 802.11n wireless mesh networks ［J］.IEEE Transaction on Mobile Computing，2013，12 （13）：2719－1733.

［10］Blocho M，Czech ZJ.A parallel EAX－based algorithm for minimizing the number of routes in the vehicle routing problem with time windows ［C］／／IEEE International Conference on High Performance Computing and Communication ＆IEEE In－ternational Conference on Embedded Software and Systems.NJ：IEEE Computer Society，2012：1239－1246.

［11］HE Shiming，ZHANG Dafang，XIE Kun，et al.Opportunistic routing for multi－flow in wireless mesh networks ［J］.ACTA Electronica Sinica，2014，42 （5）：1004－1008 （in Chinese）.［何施茗，张大方，谢鲲，等.多并发流无线网状网中的机会路由算法［J］.电子学报，2014，42 （5）：1004－1008.］

［12］LINGO API［DB／OL］.http：／／www.lingo.com，2014.