基于双超平面的电力通信网业务QoS评价方法

李荣荣，唐良瑞

(华北电力大学 新能源国家重点实验室，北京　102206)



基于双超平面的电力通信网业务QoS评价方法

李荣荣，唐良瑞

(华北电力大学 新能源国家重点实验室，北京102206)

摘要：为解决传统业务服务质量(Quality of Services, QoS)评价算法客观性不足、评价效率低等问题，将业务QoS评价映射为业务QoS等级分类，提出了一种基于双超平面(Double Decision Hyperplane, DDH)决策图的电力通信网业务实时QoS评价方法。该方法提取业务网络层特征来表征业务的服务质量，以QoS等级已知的现有业务作为分类器的训练样本，由分类器的构造顺序来确定决策图的形成。此外，算法对传统类间耦合度进行了重新定义，并在决策图各层按照最小类间耦合度原则依次构造分类双超平面，实现业务QoS等级的不完全三分类，避免了传统多分类决策图低层结点“误差崩盘”，自适应性低及决策图结构固定等问题。仿真结果证明，DDH决策图在电力业务QoS评价中比经典DAG-SVM方法具有更短判决时间和更优分类性能，可更好地实现电力业务QoS实时准确评价。

关键词：电力通信网；业务服务质量；双超平面；类间耦合度；DAG-SVM

0引言

作为电力系统中第二个实体网络，电力通信网依托于电网建设，是保证电力系统安全稳定运行的基础[1]，是电力系统中的支撑和保障体系，不仅承担着电力系统的生产指挥和调度，同时也为行政管理和自动化信息的传输提供服务[2]。随着智能电网的发展及电力ICT水平的提升，电力通信网近几年发展迅猛，网络规模不断扩大，结构也日趋复杂，电力通信业务需求量和要求均在提高，电力通信网维护单位已经越来越重视其业务服务质量(QoS)的保证和服务水平的提高。虽然电力通信网和公共通信网同属于通信网络，但承载在电力通信网上的业务不同于公网业务，具有很强的行业特殊性[3]，对业务的各项指标的要求更加严格，新一代电力通信网业务要实现“高可靠、全方位、多元化、网络化”，因此亟需在分析电力系统业务特性及需求的基础上，采用有效的评价方法来对电力通信网业务QoS进行实时准确可靠的评价。

目前国内外对电力通信网业务QoS评价方面的研究稍显不足。现有QoS评价方法[3-8]多采用传统的多属性单目标决策算法，客观性不足，且不具备机器学习算法高效性、智能化等优点。实际上，现有电力通信网业务在网内运行情况的优劣是电网专家经验已知的，实际要进行的业务QoS评价是针对电力通信网未来会出现的新业务以及随网络状况变化而运行质量发生变化的现有业务。从分类的角度来看，基于监督的分类器思想可以很好的实现从未知业务QoS到已知业务QoS的映射。其中，基于SVM的层次分类器具有诸多优势，如分类性能优良、分类效率高等。因此，本文借鉴了SVM分类算法中决策超平面的思想，并对其加以改进，使得新算法的分类性能得到进一步提升。

基本SVM只能解决二分类问题，在解决多分类问题时，常采取构造多个层次二分类器的方法来实现，常用的SVM多分类算法有OAA (One-against-all)，OAO (one-against-one)，DT-SVM (decision tree SVM)[9]和DAG-SVM (direct acyclic graphSVM)[10]。文献[11]利用无类别标识的样本的聚类特征，提出一种基于半监督分类算法的SVM分类机，充分利用了聚类算法和分类算法的优势；文献[12]对5种可处理大规模样本分类问题的支持向量机训练算法的分类性能进行了分析和比较，尤其是算法收敛速度、可扩展性和分类准确度；文献[13-14]针对训练样本特征数目众多而导致决策超平面训练时间过长的问题，采用相应的算法对样本特征进行筛选，得到样本的最优特征集，改进了传统的支持向量机，减短了分类机的训练时间；为解决训练样本有限的问题，文献[15]通过在训练集内增加已正确分类的样本，同时去除分类偏差较大的样本，从而保证了随着分类的进行，训练样本数目趋于稳定且分类超平面趋于确定。然而，上述策略的本质仍然是基本的二分类SVM，虽然相关的改进可以缩短分类器的训练时间，但决策图一旦经训练得到，新的样本会沿着决策图的走向进行类别判定，即实际上，分类器的训练时间并不会影响样本分类速度。同时，某些样本的类别属性非常明显，采用基本的二分类SVM会导致这些样本在分类时历经比实际需要更多的分类器，增加了样本分类的平均时间和分类错误率。

基于以上分析，本文提出一种基于DDH决策图的电力通信网业务QoS评价方法，从网络现行状况中提取已知QoS等级的业务特征作为机器学习的学习集，在决策图的每个结点依据最小类间耦合度原则确定分类双超平面构造的次序，逐层自动构建分类机形成决策图。同时由于决策超平面的构造取决于学习集样本的分布状况，使得决策图的结构具有自适应性，在保证训练和分类效率的同时，使分类性能达到最优(或近优)。理论分析和实验结果证明，DDH方法比多分类DAG-SVM方法具有更高的分类精度和效率，可更好地实现电力业务QoS的动态实时评价。

1基于DDH的业务QoS评价方法

1.1类间耦合度

在构造多分类各层分类机时，需采用一定的准则度量类间距离的大小，将可分性最好的两类先分离出来，以此来尽可能降低分类错误率。通常采用类间分离度来保证每个决策结点处类间隔尽可能大。所谓类间分离度，是对类与类之间可分程度的度量，分离度越大两类越易分开。类i与类j间的分离度[16]定义为

(1)

式中：dij=‖ci-cj‖表示类i与类j中心距离，ci与cj分别为类i与类j的样本中心，si与sj分别为类i与类j的标准差。类中心距离反映类间样本分布情况，类方差反映类内样本分布情况。

类间分离度在一定程度上反映了类间可分性能，但是对于如图1所示情况，如果采用上述类间分离度定义，那么这两种情况下类i与类j的分离度是一样的，但很明显图1右图中类i与类j间的空白区域(Margin)大，在此区域更易构建得到最优超平面，即决定最优超平面构造难易程度的是类间绝对距离，而非类间相对距离。

图1　类间分离度Fig.1　The inter-class separation degree

(1) 类i与类j的样本中心分别为ci与cj，类中心距离dij=‖ci-cj‖；

(3) 经过(2)筛选得到类i样本数减少为Pi，类j样本数减少为Pj，计算Pi个样本与Pj个样本的平均距离，该平均距离的倒数即定义为类间耦合度，该值越小，类间耦合度越弱，类间绝对距离越大，越利于最优超平面的构造。

(2)

式中：m=1,2,…,Pi；n=1,2,…,Pj。

1.2DDH的构造

DDH方法在每个分类层都采用1-a-1方式来构造决策超平面，但采取的分类策略是不完全的三分类而非传统的二分类。假设已知QoS等级的现有电力业务共N个，业务特征指标共M个，其构成一个M维业务特征空间L，每个业务用M维特征向量xi(xi1,xi2, …,xiM)∈L表示，其中i=1, 2, …, N，j=1, 2, …, M，xij表示业务i的指标j，所有N个业务就对应于M维特征空间L内的N个点。根据业务i的特征向量xi，可将所有业务分为优、中和差三类，分别用+1、0、-1表示，设xi的类别标号为yi，则yi∈{-1, 0, +1}，那么定义M+1维空间内的点(xi,yi)就代表业务i。

在这N个特征向量线性可分的情况下，如果可以找到两个决策超平面

(3)

使得-1类点与+1类点分别几乎全部位于G1(x)与G2(x)的两侧，0类点大部分位于超平面G1(x)与G2(x)之间，少量的点位于G1(x)与G2(x)两侧，即可实现训练点集的不完全三分类，其中，t1和t2应为可调参数且t2>0>t1，用来调整0类点范围的大小，如图2所示，○代表“+1”，△代表“0”，□代表“-1”。

图2　DDH不完全三分类示意图Fig.2　The schematic diagram of DDH incomplete ternary classification

由分析可知，一旦找到超平面：

(4)

并确定t1和t2的值，就相当于确定了两个决策超平面；而超平面G(x)就是SVM对训练样本进行分类时构造的，在此实际需要确定的是t1和t2的值。

由于样本点在空间L内并不一定是线性可分的。为保证总能找到一个线性的超平面将其区分开来，可以通过非线性映射j: Rn→Rs, s>n，将x映射到一个高维空间中，即z=j(x)，使得在这个高维空间Rs内存在线性的决策超平面，可以对z进行区分。映射后，式(4)即变为

(5)

那么一旦t1和t2确定，那么对于空间L内的所有点，就有

(6)

式中：αi是拉格朗日乘子；K()为核函数；xi为第i个支持向量；yi为支持向量xi的类别标签；x为待分类的向量；b为常数。

(1) 计算训练集F中各类间耦合度Oij，i=1,2,…,N，j=1,2,…,i；

(2) 将类间耦合度按升序排列，提取出类间耦合度最小的两类k与l，F1=F-{xk}，F2=F-{xl}；

(3) 选择适当的核函数，训练分类机，得到决策超平面

(7)

优化参数t1和t2构造出超平面G1(x)与G2(x)；

(4) 对新训练集F1与F2重复(1)、(2)、(3)，直到生成整个图结构为止。

1.3QoS等级判定

依据上述规则进行训练，定义SVMij代表由i类与j类训练而得的分类机，对于4分类训练样本就得到了如图3所示DDH决策图。对于待评价业务，其特征向量为x，那么该业务的QoS评价过程则首先在DDH决策图根结点利用首层SVM14分类，x到超平面G(x)=0的距离可以表示为

(8)

将d定义为决策距离，可正可负，其表征业务当前的QoS等级。具体判决方法如下：

(1) 若d≤t1，代表x属于非4类，即业务QoS属于1、2、3类中的一类，则下一步执行二层左侧SVM13；

(2) 若d≥t2，代表x属于非1类，即业务QoS属于2、3、4类中的一类，则下一步执行二层右侧SVM24；

(3) 若t1

(4) 在新的判决层，重复(1)、(2)、(3)过程，直至到达最底层结点判决出业务QoS所属的类别，则等级判定过程结束。

图3　一种四分类DDH结构图Fig.3　Structure diagram of DDH for four classes

2仿真与结果分析

为了验证算法的性能，本文用Matlab对DDH算法、最小耦合度DAG-SVM算法以及最大可分度DAG-SVM算法进行了对比仿真实验，仿真环境为IntelPenium4CPU2.93GHz，512M内存台式机。训练样本为已知QoS等级的电力业务共7 500个(96个劣、294个差、1 698个中、3 117个良、2 295个优)，其中随机按比例选取2 500个(32个劣、98个差、566个中，1 039个良，765个优)业务作为训练样本，剩下样本中随机选取2 500为测试样本，以“1”“2”“3”“4”“5”为类别标签来代表QoS等级的“劣”“差”“中”“良”“优”，选取业务端到端时延、带宽、吞吐率，误码率、抖动与误信率这6项指标作为样本特征。表1所示为两种多分类方法训练及分类复杂度比较。

表1两种多分类方法训练及分类复杂度比较

Tab.1The efficiency and accuracy comparison in two multi-classification methods

DAG-SVMDDH分层依据最大可分度最小耦合度基本分类机训练方法二分类不完全三分类组合策略投票法决策图决策图需训练SVM个数K(K-1)《K(K-1)分类所需遍历SVM平均个数K-1《K-1

基于类间最大可分度的DAG-SVM逐层构造分类机，形成有向无环图结构，如图4(a)所示，由于SVM为二分类，每个样本都需要进行4次分类，所需遍历的SVM平均个数较多，分类效率比较低且分类准确度不高；本文提出的DDH依据类间最小耦合度逐层构造分类机，如图4(b)所示，由于SVM为不完全三分类，存在跨层直分情况，每个样本最多进行4次分类，最少进行2次分类，所需遍历的SVM平均个数大幅减少，具有较高的分类效率与准确度。

图4　DAG-SVM与DDH决策图对比Fig.4　Comparison of decision graph of DAG-SVM and DDH

基于类间最大可分度的DAG-SVM首先对5类与2类进行分类，而基于最小耦合度的DAG-SVM则首先对5类与1类进行分类，两种算法对各类别样本分类准确率的仿真结果如图5所示，在本仿真样本情况下，两种算法的平均分类时间大致相当，分别为42.279 4 ms与42.002 5 ms，但分类准确度有所差异。这是由于第2类样本分布比较集中造成的，并不能保证类间空白区域最大化，而最小耦合度表征的就是两类间空白区域的实际大小，因此使得分类依据更加合理，总分类准确率有所提高；但由于两种多分类算法中，业务等级判定时所需遍历的SVM数目始终为4，所需平均时间较长且相差不多，无法满足短时间内多业务的QoS等级判定，效率较低。

图5　两种方法的仿真结果Fig.5　The simulation results of two multi-classification methods

在DDH决策图方法中，t1与t2的取值决定了跨层直分第三类的比例，其绝对值越大，跨层直分的样本越多，从而导致训练时间缩短，但如果取值过大，会导致第一类与第二类点被误认为可跨层直分的点，从而导致分类准确率的下降，为简便起见，取-t1=t2，在上述样本情况下，多次训练发现，-t1与t2取值在[0.65 0.8]之间时，分类时间较短且准确率也较高，仿真结果如图6所示。

图6　DDH中t2取值与判定时间与准确率的关系Fig.6　The relationship between t2 and decision time and accuracy in DDH

由图6可知，当t2的取值在[0.65 0.8]之间时，分类准确度几乎不变，但分类所需的平均时间变化很大。经过反复优化，得到在上述样本下，t2=0.75时，分类性能达到最优，此时通过3种算法得到的各类的准确率如图7所示，单业务QoS等级判决所需平均时间与总准确率如表2所示。仿真结果表明，基于不完全三分类的DDH算法在分类性能上优于DAG-SVM，这是由于很大一部分样本分类所需遍历的SVM个数都少于4个，这大大减少了判决所需要的时间，且由于遍历的SVM个数减少且参数t1与t2选择恰当，在保证了分类依据正确的情况下减少了可能错分的次数，使得整体分类性能得到较好的提升。

表2三种多分类方法的效率及准确率

Tab.2The efficiency and accuracy of three multi-classification methods

多分类方法分类准确率/%单个业务QoS判定所需平均时间/ms基于最小耦合度的DAG-SVM98.4342.2794基于最大可分度的DAG-SVM96.9842.0025DDH(t2=0.75)98.6528.3134

图7　三种方法对各类别的分类准确率Fig.7　The classification accuracy for each category in three multi-classification methods

3结论

本文提出一种基于DDH的电力通信网业务QoS评价方法，从网络现行状况中提取已知QoS等级的业务运行特征作为机器学习的学习集，在决策图的每个节点利用最小类间耦合度进行分类决策优化，基于双判断超平面决定图径走向，逐层自动构建分类机形成决策图。同时由于决策超平面的构造取决于学习集样本的分布状况，使得决策图的结构具有自适应性，在保证训练和分类效率的同时，使分类性能达到最优(或近优)。理论分析和实验结果表明，本文提出的新方法比多分类DAG-SVM方法具有更高的分类精度和分类效率。

参考文献：

[1] Ye Yan, YiQian, HamidS,et al. Asurvey on smart grid communication infrastructure：motivations，requirements and challenges[J]. IEEE Communications Surveys and Tutorials, 2013, 15(1): 5-20.

[2] 李春华, 冉静学, 高会生. 基于离差最大化方法的电力通信网传输部分的综合评估[J]. 电力系统保护与控制, 2008, 36(15): 33-36.

[3] Shah G A, Gungor V C, Akan O B.A Cross-Layer QoS-Aware Communication Framework in Cognitive Radio Sensor Networks for Smart Grid Applications[J]. Industrial Informatics, IEEE Transactions on, 2013, 9(3): 1477-1485.

[4] AL Tameemi O A, Chatterjee M, Kwiat K.Vector Quantization based QoS Evaluation in Cognitive Radio Networks[C]. Wireless and Optical Communication Conference (WOCC), 2014,23rd:1-6.

[5] Yosra M, Ayari A,Ayadi M.A Novel Approach for Mobile Network QoS Evaluation[C].Networks, Computers and Communications, The 2014 International Symposium on.IEEE,2014: 1-6.

[6] Dogman A, Saatchi R,Al-Khayatt S. Evaluation of Computer Network Quality of Service Using Neural Networks[C]. Business, Engineering and Industrial Applications (ISBEIA), 2012 IEEE Symposium on.IEEE, 2012: 217-222.

[7] 周静，熊素琴，苏斌，等．一种电力通信网络运行质量量化评估方法及应用[J]．电网技术，2012，36(9)：168-173．

[8] 陈翔, 吴润泽, 曹敏,等. 基于模糊AHP的电力ICT网络业务质量评价方法[J]. 电力系统通信,2011, 32(6):48-52.

[9] Moustakidis S, Mallinis G,Koutsias N,et al.SVM-Based Fuzzy Decision Trees for Classication of High Spatial Resolution Remote Sensing Images[J]. Geoscience and Remote Sensing, IEEE Transactions on, 2012, 50(1): 149-169.

[10] 黄振龙，郑骏，胡文心．基于类间可分性DAG-SVM的文本分类[J]．华东师范大学学报(自然科学版)，2013,(3)：209-218．

[11] Zhen Fengshao, Lei Zhang, Xi Ranzhou. A Novel Hierarchical Semi-supervised SVM for Classification of Hyper-spectral Images[J]. IEEE Geoscience and Remote Sensing Letter, 2014, 11(9): 1609-1613.

[12] Cumani S, Laface P. Analysis of Large-Scale SVM Training Algorithms for Language and Speaker Recognition[J]. IEEE Transactions on Audio Speech and Language Processing,2012, 20(5):1585-1596.

[13] Geebelen D, Suykens J A K,Vandewalle J.Reducing the Number of Support Vectors of SVM Classifiers Using the Smoothed Separable Case Approximation[J]. IEEE Transactions on Neural Networks and Learning Systems, 2012, 23(4): 682-688.

[14] Liu Xiaoming, Tang Jinshan. Mass Classification in Mammograms Using Selected Geometry and Texture Features, anda New SVM-Based Feature Selection Method[J]. IEEESystems Journal, 2014, 8(3): 910-920.

[15] Ghoggali N, Melgani F, Bazi Y. A multi-objective genetic SVM approach for classification problems with limited training samples[J]. Geoscience and Remote Sensing, IEEE Transactions on, 2009, 47(6):1707-1718.

[16] 邱婧, 夏靖波, 柏骏. 基于SVM决策树的网络流量分类[J]. 电光与控制, 2012, 19(6): 13-16.

QoS Evaluation Method Based on Double Decision Hyperplanes in Electric Power Communication Networks

LI Rongrong, TANG Liangrui

(State Key Laboratory of Alternate Electrical Power System with Renewable Energy Sources,North China Electric Power University, Beijing 102206, China)

Abstract:In order to solve the problems of the insufficient objectivity and low evaluation efficiency in traditional services quality (QoS) evaluation algorithms, a novel double decision hyperplanes (DDH) decision graph method，which mapped the QoS evaluation to the QoS level classification, was proposed to evaluate the real-time quality of services (QoS) in electric power communication networks. It extracted representative features to reveal services running conditions in the network layer and exploited the services whose QoS were known to train the classifiers. The decision graph structure was determined via the class grouping algorithm, which formed the groups of classes to be separated at each internal node. Moreover, a novel coupling degree between classes was presented and the double planes in each decision layer were created based on principle of the minimum coupling degree between classes. Since the node discriminations are implemented via incomplete ternary SVMs, the new method can well avoid problems of “error collapse” in low decision layer nodes, low adaptability and the fixed structure in conventional decision graph algorithms. Finally, simulation results show that, compared with other classic methods, the novel method exhibits a number of attractive merits such as enhanced classification accuracy, short decision time, as well as achieves a more real-time QoS evaluation for electric power communication network services.

Key words：electric power communication networks; quality of services; double decision hyperplane; coupling degree between classes; DAG-SVM

作者简介：李荣荣(1990-)，女，硕士研究生，主要研究方向为电力通信网业务质量评估及网络安全防护；唐良瑞(1966-)，男，教授，博士生导师，主要从事电力系统通信与信息处理、无线传感器网络与物联网技术等方面的研究。

中图分类号：TN91

文献标识码：A

文章编号：1007-2691(2016)01-0092-07

基金项目：国家高技术研究发展计划资助项目(2014AA01A701)；北京市自然基金资助项目(4142049).

收稿日期：2015-06-08.

doi:10.3969/j.ISSN.1007-2691.2016.01.16