基于D-S理论融合方法的网络质量评价
周宇,周红琼,叶庆卫,王晓东
(宁波大学 信息科学与工程学院,浙江 宁波,315211)
摘要:针对现有网络质量评估方法只能给出综合评价结果、不能给出评估结果的确定性和不确定性度量、无法处理评估中的未知因素等缺点,将D-S证据理论引入网络评价领域,以网络应用为导向,建立一种互联网质量评价层次结构,利用两级D-S结构进行证据融合得到网络质量评价结果。经计算可知,两级的D-S证据融合推理模型极大限度地消除了不确定性,提高了网络评价的准确性和可靠性。
关键词:IP网络质量;D-S证据理论;不确定性度量;数据融合
中图分类号:TP393 文献标志码:A 文章编号:1672-7207(2011)S1-0684-05
Evaluation of network quality based on D-S theory fusion method
ZHOU Yu, ZHOU Hong-qiong, YE Qing-wei, WANG Xiao-dong
(Faculty of Information Science and Engineering, Ningbo University, Ningbo 315211, China)
Abstract: Only one comprehensive result can be gotten from existing methods for evaluating network quality, which cannot provide the certainty or uncertainty of the result. Therefore, we do not know how to deal with the unknown factors in the process of evaluating. In this paper, D-S evidence theory is introduced into network evaluation area. Take the network application as guide, an Internet quality evaluation hierarchical structure is established. The network quality evaluation results are obtained by using the two levels of the D-S structure to fuse evidence. The calculated results show that the model using two levels of D-S structure to fuse evidence eliminates the uncertainty to a great extent, and the accuracy and reliability of the network evaluation are improved effectively.
Key words: quality of IP network; Dempster-Shafer theory of evidence; uncertainty measurement; data fusion
全网IP化是通信网络发展的一种趋势。在Internet变得日益庞大和复杂的同时,作为各种业务网络的承载基础网络,IP网络质量问题一直是一个热门课题。如何在现有网络环境基础上提高网络性能,以及如何为下一代互联网设计出具有更好的运行效率和更高性能的网络互联协议等问题,目前已成为国内外研究的热点。而这些问题的解决都要求对网络质量进行有效的评价与分析。但是,目前的IP网络并不完善,由于网络规模扩大,网络带宽增加,复杂性不断提高,网络新业务不断出现,人们对互连网络的流量、性能特征及网络行为模型缺乏理解和精确描述的问题日益突出,Internet性能的可知性越来越低,因此,需建立一套可行的网络性能评价方法和体系,用于对网络包括安全性、稳定型及实用型等进行评估,以便为用户提供具有较高可信度的网络服务[1-2]。网络质量分析评价己经成为一个独立并且不可忽视的研究领域,并且从今后实际应用的角度将对网络的完善和优化提供重要的依据。
国际上,IETF[3]和ITU-T[4]制定了相应网络性能指标,但没有建立宏观的评估模型;刘怀亮等[5]以图论为基础,构造了一种端到端网络性能分析算法;张冬艳等[1]提出了一种基于测量方法的网络性能评估模型,采用加权平均方法计算路径性能评估值;蒋序 平[6]提出了从全局性或整体性角度评估网络性能的方法;Hershey等[7]对网络监测和管理的指标进行了分类;阙伟科等[8]提出了结合网络健康度和路由器健康度的综合性能评估模型;陈小帅[9]提出从维度、空间和时间3方面的综合化来评估网络运行质量的方法。但这些方法都只能给出一个综合评估结果,却不能给出评估结果的确定性和不确定性度量。另外,这些方法不能体现和处理评估中的未知性信息。为此,本文基于D-S证据理论来尝试解决这些问题,提出基于D-S证据融合方法的IP网络质量评价模型,建立一种互联网评价层次结构,利用D-S证据理论进行两级数据融合,为网络质量的科学评价提供可靠理论依据。
1 D-S证据的数据融合基本原理
数据融合的方法很多,其中Dempster-Shafer证据理论是应用的最多的一种。Dempster-Shafer证据理论是一种不精确推理理论,是贝叶斯方法的扩展,但贝叶斯方法必须给出先验概率,而证据理论则能够处理这种由不知道引起的不确定性[10-11]。
设Θ表示所要研究的问题所有可能取值的集合,且所有在Θ内的元素间互不相容,在D-S理论中,则称Θ为问题的一个识别框架[12]。
定义1 设Θ为一识别框架,m:2Θ→[0,1],A表示识别框架Θ的任一子集在满足下列条件时:
(1)
称m(A)为事件A 的基本概率赋值(BPA)。
定义2 设Θ为一识别框架,m:2Θ→[0,1]是Θ上的基本概率赋值,定义函数:
(2)
称该函数为A的信任函数,它表示证据对A为真的信任程度。
定义3 若识别框架Θ的一子集A,具有m(A)>0,则称A为信任函数Bel的焦元,所有焦元的并称为核。
定义4 设Θ为一识别框架,定义Pl:2Θ→[0,1]为:
(3)
Pl称为似然函数。式(3)说明似然函数Pl(A)包含所有与A相容的集合(命题)的基本置信度。
定义5 设Bel1和Bel2是同一识别框架Θ上的2个信任函数,m1和m2分别是其对应的基本概率赋值,焦元分别为A1,…,Ak和B1,…,Br,又设
(4)
则
(5)
式(4)中,若K1≠1,则m确定一个基本概率赋值;若K1=1,则认为m1和m2矛盾,不能对基本概率赋值进行组合。上面定义的证据组合规则称为Dempster组合规则。对于多个证据的组合,可采用Dempster 组合规则对证据进行两两综合。
D-S证据理论最吸引人的地方是它能够很好地表示未知信息的程度。D-S不确定性区间如图1所示。
图1 D-S不确定性区间
Fig.1 Uncertainty interval of D-S
图1中:Bel和Pl分别代表信任函数和似然函数,表示对某个子集信任度的下限和上限。有了上述的定义和不确定性区间,运用D-S证据推理进行融合决策。多传感器信息融合的一般过程是如图2所示:
(1) 分别计算各传感器的基本概率赋值、信任函数和似然函数;
(2) 合成。利用D-S合并规则,求得所有传感器联合作用下的基本概率赋值、信任函数和似然函数;
(3) 推断。在一定决策规则下,选择具有最大支持度的目标。
图2 D-S证据理论决策过程
Fig.2 Decision-making process of D-S evidence theory
2 基于D-S理论的网络质量评价
在网络质量评价中,主要使用延迟、丢包率、带宽和流量等多项指标对所测量的网络进行性能评价。这种指标虽能全面反映某一个事物的发展状况,但是不符合当今网络发展要求。例如,在比较甲、乙2个网络同一时刻的性能优劣时,往往会遇到这样的情况,甲网络有几项性能指标优于乙网络,同时,乙网络又有另外几项性能测量指标优于甲网络,这时无法判断甲、乙2个网络性能的优劣。同样,在分析比较同一网络不同时刻性能的发展变化时,也会遇到类似的情况[1]。
针对这一不足,再由于网络最终承载的是各类应用,应用业务在网络上使用的好坏直观地反映了网络的质量。本文作者以网络应用为划分,使用两级D-S证据融合,实现对网络性能的综合评价。利用多个不同指标运算综合,最终得到一个评价数值,反映网络整体的性能状况,既有全面性,又有综合性。
不同的网络应用对网络有不同的运行质量要求。例如,语音业务对网络的要求主要体现在丢包率、时延和时延抖动等方面,带宽只要达到一个固定值就可以;与语音业务同为CBR业务的视频点播业务对网络的要求则主要体现在带宽和丢包率等方面。因为语音业务特点是占用带宽小而固定、需要双方或多方交互,如果丢包率较大,会严重影响语音质量,如果时延和时延抖动较大,会严重降低发生业务两方或多方的用户体验,时延达到400 ms以上将无法忍受;而视频业务的特点是带宽固定且较大、业务单向性,由于可以在视频播放端引入缓冲区,时延和时延抖动对业务不会带来严重影响。
不同的网络业务对网络有不同的要求,基于前期相关研究,如图3所示,分别选取不同应用关注的网络指标——元指标,作为第一级D-S证据的输入,经证据合成后得到本应用对网络质量评价的分类结果;再通过第二级融合中心的D-S证据推理模型对各应用证据推理的结果进行融合;最后,得到融合所选应用全部信息后可信度最高的网络质量评价分类结果。
依据图3的评价层次以及D-S证据推理原理,构建网络质量评估方法如下:
(1) 构建网络质量评价问题的识别框架
将作为网络质量评价问题的识别框架。式中,A表示网络质量非常好,B表示网络质量一般,C表示网络质量差,D表示网络质量非常差。选取几类典型应用,每一个应用相当于一个框架函数,可表示为m1,m2,…,mn,n为评价网络主要承载的业务类型种类的数目。
(2) 选定评价元指标作为多个传感器数据
选取读者熟知并且经常接触的几个网络应用作为第一级融合对象:浏览网页,在线视频和网络语音业务。针对这些应用对网络延迟、丢包、吞吐量、抖动及连通率等不同网络指标的敏感程度和反应现象,构成D-S融合定量的推理信息。
(3) 第一级D-S融合模型
第一级融合推理过程及结果如表1所示。选取丢包率、延时及延时抖动为语音业务的评价元指标,构成第一级融合系统的证据。m1,m2和m3分别是不同元指标相应的框架函数。
(4) 第二级D-S融合模型
对所选3个第一级证据推理融合模型就各自的证据进行融合处理后,整体网络的第二级将对这些数据进行进一步融合,得到最终用于判决的结果。
图3 基于D-S证据理论的网络质量评价层次示意图
Fig.3 Internet quality evaluation hierarchical structure based on D-S evidence theory
3 算法实现与结果分析
3.1 计算实例
以语音业务为例说明第一级D-S数据融合推理。通过大量的网络仿真数据,并参考语音质量评价相关标准,选择丢包率、IP包传输时延和IP包时延抖动3项指标作为传感器信息输入,如表1所示。
从表1中可知,m1,m2和m3的不确定性分别为0.035,0.045和0.035。对不同特征的支持程度难以进行特征分类。
在m′计算过程中,首先根据式(4),有
代入计算可得
K1=0.638,1-K1=0.362
然后根据
类推,依次计算出m′(B),m′(C),m′(D),m′(θ)=1- m′(A)-m′(B)-m′(C)-m′(D)。
表1 语音业务数据融合特征分类
Table 1 Feature classification of data fusion for voice services
对m′与m3进行融合得到m″。由表1的结果可以看到,通过证据的融合,分类结果的不确定概率赋值降低到了0.001,比较融合前数值大幅降低,融合之后的分类结果m″(A)可信度为0.789,比证据对其他特征的支持有着明显优势,可以判定为网络状态为非常好的情况。
第二级的数据融合推理结果如表2所示。
识别框架为。
表2 第二级D-S融合分类结果
Table 2 The second level of D-S fusion classification results
表2中,m1为语音业务,m2为在线视频,m3为浏览网页,m′=m1m2,m″=m′m3,计算过程如上述语音数据融合分类。从表2的结果可以看出,融合后不确定性降低到0,m″(A)的可信度为0.988,分类结果“非常好”的可信度得到大幅提高。
3.2 算法性能分析
D-S证据理论是一种广义的Bayes推理方法,克服了Bayes推理需要先验概率和条件概率密度的困难,将“不知道”和“不确定”区分开来,有效地进行推理识别。本文作者使用的两级D-S融合比单一证据融合决策具备更一致的描述和解释,极大限度地消除了不确定性。
4 结论
IP网络的质量是互联网运营商、互联网服务提供商及网络用户十分关注的问题。针对现有网络质量评价只能给出综合评估结果、不能给出评估结果的确定性和不确定性度量的情况,将D-S证据理论引入网络管理评价中,体现并处理评估中的未知性信息。以常见网络应用为导向,建立网络质量评价的两级D-S证据融合推理模型,极大限度地削减了不确定性因素的影响,提高了网络评价的准确性和可靠性。
参考文献:
[1] 张冬艳, 胡铭曾, 张宏莉. 基于测量的网络性能评价方法研究[J]. 通信学报, 2006, 27(10): 74-79.
ZHANG Dong-yan, HU Ming-zeng, ZHANG Hong-li. Study on network performance evaluation method based on measurement[J]. Journal on Communications, 2006, 27(10): 74-79.
[2] 谈杰, 李星. 网络测量综述[J]. 计算机应用研究, 2006, 23(2): 5-8.
TAN Jie, LI Xing. Review of network measurement[J]. Application Research of Computer, 2006, 23(2): 5-8.
[3] IETF. IP performance metrics(IPPM) metrics registry, RFC4148[R]. 2005.
[4] ITU-T. Network performance objectives for IP-based services, Y.1514[R]. 2006.
[5] 刘怀亮, 王东, 徐国华. 一种基于流量工程的网络端到端性能分析算法[J]. 系统工程与电子技术, 2003, 25(9): 1165-1168.
LIU Huai-liang, WANG Dong, XU Guo-hua. An algorithm for network performance analysis based on traffic engineering[J]. Systems Engineering and Electronics, 2003, 25(9): 1165-1168.
[6] 蒋序平. 网络性能综合评估方法IEMONP的设计和实现[J]. 海军工程大学学报, 2006, 18(5): 74-78.
JIANG Xu-ping. Design and realization of an integrated evaluation method of network performance[J]. Journal of Naval University of Engineering, 2006, 18(5): 74-78.
[7] Hershey P, Runyon D, Wang Y W. Metrics for end-to-end monitoring and management of enterprise systems[C]//Proc 2007 IEEE military communication conference(MILCOM2007). Orlando, IEEE Press, 2007: 1-7.
[8] 阙伟科, 张国清, 魏郑浩. IP网络综合性能评估模型[J]. 计算机工程, 2008, 34: 99-101.
QUE Wei-ke, ZHANG Guo-qing, WEI Zheng-hao. Model for IP network synthetical performance evaluation[J]. Computer Engineering, 2008, 34: 99-101.
[9] 陈小帅. IP网络运行质量分析与系统实现[D]. 北京: 北京邮电大学, 2008.
CHEN Xiao-shuai. IP network runtime performance evaluation and system implementation[D]. Beijing: Beijing University of Posts and Telecommunications, 2008.
[10] 曹菊英, 赵跃龙. 基于DS证据推理的信息安全风险评估方法研究[J]. 计算机工程与应用, 2009, 45(11): 129-131.
CAO Ju-ying, ZHAO Yue-long. Novel method for information security risk assessment based on Dempster-Shafer evidence reasoning[J]. Computer Engineering and Applications, 2009, 45(11): 129-131.
[11] 倪国强, 梁好臣. 基于Dempster-Shafer证据理论的数据融合技术研究[J]. 北京理工大学学报, 2001, 21(5): 603-609.
NI Guo-qiang, LIANG Hao-cheng. Data fusion technique based on Dempster-Shafer evidence theory[J]. Journal of Beijing Institute of Technology, 2001, 21(5): 603-609.
[12] 杨风暴, 王肖霞. D-S证据理论的冲突证据合成方法[M]. 北京: 国防工业出版社, 2010.
YANG Feng-bao, WANG Xiao-xia. Combination method of conflictive evidences in D-S evidence theory[M]. Beijing: National Defense Industry Press, 2010.
(编辑 陈卫萍)
收稿日期:2011-04-15;修回日期:2011-06-15
基金项目:国家自然科学基金(61071198);浙江省自然科学基金资助项目(Y1110161);浙江省大学生创新创业孵化项目(2010R405064)
通信作者:周红琼(1986-),女,安徽黄山人,硕士研究生,从事互联网质量评价研究;电话:15258258239;E-mail:zhouhq1212@sohu.com