异构网络中丢包隶属度函数的构建方法

甄雁翔，苏 放，寇明延，徐惠民

(北京邮电大学信息与通信工程学院 北京 海淀区 100876)

异构网络中丢包隶属度函数的构建方法

甄雁翔，苏 放，寇明延，徐惠民

(北京邮电大学信息与通信工程学院 北京 海淀区 100876)

异构网络中TCP丢包区分机制对无线网络的稳定性起着重要的作用，包对探测包的单向传输时延(ROD)作为区分参数对不同丢包类型进行区分，算法的准确度依赖于ROD样本的隶属度函数及其参数估算。为了更加准确地区分丢包类型，通过对传统高斯混合模型的EM算法进行分析，提出了基于势函数的初始化方法，并且在网络拥塞和无线误码同时存在的情况下，将改进的EM算法(PEM)应用于不同丢包模式下隶属度函数的构建中。仿真验证了该算法具有较好的收敛特性和稳定性，并且对不同丢包模式隶属度函数的确定达到了很好的构建效果。

EM算法; 高斯分布；异构网络; 隶属度函数; 势函数

随着无线应用技术的快速发展，无线广域网(GPRS、UMTS等)、无线局域网(IEEE802.11)、卫星通信网、蓝牙网络等多种无线网络系统正逐步代替传统有线网络成为互联网接入的最后一跳。TCP是目前Internet中广泛使用的端到端传输控制协议，在有线/无线融合的异构网络环境中，由于无线网络中存在高误码率、信号衰落、切换等原因，网络拥塞不是引起TCP分组丢失的唯一原因，无线误码也会引起分组的丢失[1-2]。而传统的TCP协议把所有的分组丢失简单地归因于网络拥塞，就会造成盲目减小发送速率，降低带宽利用率，导致TCP性能的无谓恶化[3-4]。因此，只有正确区分无线误码所造成的丢包和网络拥塞所造成的丢包，分别采取不同的控制策略，才能提高网络的效率。

文献[5]采用包对(packet pair)探测包的ROD作为区分参数对不同丢包类型进行区分，采用条件概率构造不同丢包模式下的隶属度函数，从而按照最大隶属度原则进行丢包区分，提出了异构网络下基于Fuzzy模式识别的丢包区分算法，该算法的准确度依赖于ROD样本的隶属度函数及其参数估算。

传统的参数估计方法如最大似然估计、最小二乘法等是在先验知识和类标号已知的条件下进行的。但在异构网络丢包区分的应用领域里，会出现对丢包分类不了解，即没有先验知识的情况，因此需要借助无监督的分类技术。聚类分析就是在没有任何关于分类先验知识的情况下，依据数据的相似性划分数据的类[6]。目前主要的聚类技术有以下几类：划分方法、层次方法、基于密度的方法、基于网格的方法、基于模型的方法等[7]。这些方法采用不同的方式确定聚类中心，但都有各自的局限性。如划分方法算法简单，但只适用于识别中小规模具有相近尺寸和密度的球状类数据集，对大规模的数据集以及复杂形状的聚类，需要进一步地扩展。层次方法的局限性在于合并点或分类点的选择，如果在某一步没有很好地做出合并或分裂的决定，可能会导致低质量的聚类结果。基于密度的方法能够在有噪声的空间数据库中发现任意形状的聚类，但对于密度分布不均的数据集得不到满意的聚类效果；此外，其对于密度函数参数的设置也比较敏感。基于网格的方法处理速度较快，但该算法精确性较低。基于模型的聚类方法是为每一类假定一个模型，然后寻找数据对给定模型的最佳拟合。因此，聚类算法的选择依赖于可用数据的类型和应用的特定目标，有些情况可以根据聚类标准综合多种聚类技术。

由文献[5]和大量仿真实验可知，包对探测包的ROD样本在不同丢包模式下的隶属度函数符合高斯混合分布，每一类都可以用参数概率分布数学描述。对不同丢包模式隶属度函数的构建即确定隶属度函数的参数，基于模型的聚类方法正是试图优化给定数据和某数学模型之间的拟合，因此选取基于模型的聚类方法即可描述不同丢包模式下的隶属度函数。传统的EM算法[8]是一种基于统计模型进行期望最大化分析的算法，对初始值的选择具有很强的依赖性。本文通过对传统高斯混合模型的EM算法进行分析，提出了基于势函数[9]的方法确定聚类中心，并且在网络拥塞和无线误码同时存在的情况下，将改进后的PEM算法运用到不同丢包模式下隶属度函数的构建中。仿真验证PEM算法比传统EM算法具有较好的稳定性和收敛特性，对不同丢包模式的隶属度函数可以达到很好的区分效果，具有很好的实际应用价值。

1 高斯混合模型的EM算法

1.1 算法描述

1.2 算法分析

由以上算法描述可知，EM算法的核心是根据一个代表隶属度概率的权值将每个对象指派到类中，并不断迭代使之收敛于某个最优值。运用EM算法实现高斯混合模型聚类，如何初始化参数是一个关键问题，EM算法收敛的优劣很大程度上取决于其初始参数[10]。

对于高斯混合模型，参数的初始化主要包括每一类的均值kμ、方差2kσ、权重kπ和类的个数M。对于中心值的选取，目前常用的方法是随机选取，然后通过不断迭代调整达到最优。该种随机选取的方法虽然操作简单，但对于算法的收敛稳定性有一定的影响，有时会收敛于局部最小值，而不能得到全局最优解，使得聚类效果受到影响；在数据规模较大的情况下，效率也很低，耗时长且需要较大的存储空间。本文提出了基于势函数的方法选取聚类中心，仿真验证，在达到同样精度的条件下，该算法具有较好的收敛速度和稳定性。

1.3 PEM算法

基于势函数的方法确定聚类中心值，算法步骤如下。

(1)计算每个样本点的初始势值，定义初始势函数为：

由上述势函数公式可知，样本点的势值不仅与样本点间的距离有关，还与样本点发生的次数有关。当样本点发生的概率比较大，且具有足够高的密度，其势值就会相对较大。利用上述迭代公式，可以依次找到样本的最密集点1μ，次密集点2μ、μ2、、Mμ，这些点可以作为高斯混合模型中每个高斯分布的初始均值。

1.4 仿真验证

在Matlab7仿真平台上，随机产生几类高斯混合分布，由势函数的方法确定出聚类中心，如表1所示。由势函数确定的聚类中心可以近似表示为每个高斯分布的均值，从而验证了算法的有效性。

表1 由势函数确定的聚类中心值

对理论构造的高斯混合分布数据，选取不同类数的样本集合，采用不同的初始化方法进行聚类仿真。通过大量仿真实验可知，达到相同的精度，随机选取聚类中心迭代次数不稳定，具有很大的随机性。基于势函数的方法选取聚类中心迭代次数稳定且收敛速度快，表2为不同初始化方法的平均迭代次数比较。

表2 理论样本不同初始化方法平均迭代次数比较

2 不同丢包模式隶属度函数的构建

2.1 不同丢包模式隶属度函数的特点

在网络拥塞和无线误码同时存在的情况下，通过对文献[5]和大量包对探测包的ROD样本进行分析可知，拥塞丢包模式下ROD的隶属度函数为高斯混合分布，瓶颈的个数即为高斯混合分布类的个数。无线误码丢包模式下ROD的隶属度函数也为高斯混合分布，但与误码率有关。误码率较大时，由误码引起的丢包概率增大，由TCP协议[11]可知，拥塞窗口会不断进行减半调整，发生拥塞的概率减小；当误码率较小时，发生拥塞的概率增大，拥塞丢包的特征变得明显。因此，无线误码模式下丢包隶属度函数随误码率的变化而变化[12]。

2.2 不同丢包模式下隶属度函数的确定

拥塞丢包模式下，由于网络中可能会有多个瓶颈，通过大量仿真实验可知，每个瓶颈处包对探测包的ROD样本可以用一个高斯分布来描述。当瓶颈数大于两个时，瓶颈处的ROD样本的次数很少，在高斯混合分布中的权重也很小，与瓶颈为两个的ROD分布特征近似。因此，拥塞模式的隶属度函数可以由一个类数为2的高斯混合分布来描述。

无线误码丢包模式下，通过大量仿真实验可知，当误码率较大时，隶属度函数的均值和方差都比较小，当误码率较小的时候，隶属度函数的方差比较大。由于无线误码丢包具有很大的随机性，所以ROD分布具有重尾现象[13]。高斯混合模型的EM算法对重尾数据的描述是用一个方差比较大的高斯分布进行拟合。因此，无线误码模式的隶属度函数可以由一个类数为2的高斯混合分布来描述。

由以上分析可知，在网络拥塞和无线误码同时存在的情况下，类的个数为4。因此，在利用势函数的方法确定聚类中心时，选取4类进行迭代。

类个数确定后，定义由PEM算法描述不同丢包模式的隶属度函数为：

式中 PC为拥塞丢包模式的隶属度函数；PW为无线误码丢包模式的隶属度函数。

采用PEM算法估算出4个高斯分布的参数，然后根据不同丢包模式下隶属度函数的特点，将估算出的高斯分布的均值kμ和方差2kσ作为不同丢包模式的区分参数进行分类。

(1)比较方差：选取方差最大的一类高斯分布作为无线误码丢包的隶属度函数。

(2)比较均值：对其余3类高斯分布比较均值，选取均值最小的作为无线误码丢包的隶属度函数，其余两类即为网络拥塞丢包的隶属度函数。

由以上步骤即可确定式(6)不同丢包模式的隶属度函数。

2.3 仿真验证

利用Matlab7进行仿真，表3为不同网络条件下丢包隶属度函数统计参数表，表4为不同初始化方法平均迭代次数的比较。

表3 不同网络条件下丢包隶属度函数统计参数表

表4 ROD样本不同初始化方法平均迭代次数比较

可以看出，对于ROD样本，PEM算法比传统EM算法具有较好的稳定性和收敛特性。图1为不同网络条件下ROD样本分布及隶属度函数对比图。比较ROD样本分布图和由PEM算法确定的隶属度函数，可以看出隶属度函数能近似表示实际样本的概率分布，从而验证了该方法模型的有效性。

图1 不同网络条件下ROD样本分布与隶属度函数对比图

3 结 束 语

本文通过对传统高斯混合模型的EM算法进行分析，针对传统EM算法在收敛速度和稳定性上的问题，在保持算法迭代简单的前提下，提出了基于势函数的方法来确定初始聚类中心，从而达到更稳定的聚类效果。并在网络拥塞和无线误码同时存在的情况下，将PEM算法运用到异构网络条件下不同丢包模式隶属度函数参数的估算中。仿真验证该算法具有很好的收敛速度和稳定性，对不同丢包模式的隶属度函数可以达到很好的区分效果，进而可以更加准确地区分丢包类型，提高网络的效率。

本文的研究工作得到了华为高校科技基金(YJCB2005055WL)的资助，在此表示感谢！

[1]范英磊, 郑培超, 苏 放, 等. 异构网络中的视频传输服务质量框架[J]. 电子科技大学学报, 2008, 37(1): 90-93.

FAN Ying-lei, ZHENG Pei-chao, SU Fang, et al. An QoS framework for video delivery over heterogeneous Networks[J]. Journal of University of Electronic Science and Technology of China, 2008, 37(1): 90-93.

[2]CHEN Ming-hua, ZAKHOR A. Rate control for streaming video over wireless[C]//INFOCOM 2004. Hong Kong,China: IEEE, 2004: 2(2): 1181-1190.

[3]TODOROVIC M, Lopez-Benitez N. Efficiency study of TCP protocols in infrastructured wireless networks[C]//ICNS’06: International Conference on Networking and Services. Slicon Valley CA: IEEE Computer Society Press,2006: 103-108.

[4]SONG C, COSMAN P C, VOELKER G M. End-to-end differentiation of congestion and wireless losses[J].Networking, IEEE/ACM Transactions on networking, 2003,11(5): 703-717.

[5]苏 放, 范英磊. 一种基于Fuzzy丢包区分的TCP拥塞控制算法[J]. 系统仿真学报, 2008, 20(7): 1904-1908, 1911.

SU Fang, FAN Ying-lei. TCP congestion control algorithm based on fuzzy loss differentiating[J]. Journal of System Simulation, 2008, 20(7): 1904-1908, 1911.

[6]高新波. 模糊聚类分析及其应用[M]. 西安: 西安电子科技大学出版社, 2004: 37-60.

GAO Xin-bo. Fuzzy cluster analysis and its applications[M].Xian: Xidian University Press, 2004: 37-60.

[7]韩家炜, 堪 博. 数据挖掘概念与技术[M]. 范 明, 孟小峰, 译. 第2版. 北京: 机械工业出版社, 2008.HAN Jia-wei, KAMBE Micheline. Data mining concepts and techniques[M]. Translated by FAN Ming, MENG Xiao-feng.2nd ed. Beijing: China Machine Press, 2008.

[8]BILMES J A. A gentle tutorial of the EM algorithm and its application to parameter estimation for Gaussian mixture and hidden Markov models[DB/OL]. [2009-01-08].http://ssli.ee.washington.edu/people/bulyko/papers/em.pdf.

[9]CHIU S L. A cluster estimation method with extension to fuzzy model identification[C]//Proceedings of the Third IEEE Conference on Fuzzy Systems. Orlando FL: IEEE Congress on Computational Intelligence, 1994, 2:1240-1245.

[10]REDMOND S J, HENEGHAN C. A method for initializing the K-means clustering algorithm using kd-trees[J]. Pattern Recognition Letters, 2007, 28(8): 965-973.

[11]史蒂文斯. TCP/IP详解卷1: 协议[M]. 范建华, 胥光辉，张 涛, 等, 译. 北京: 机械工业出版社, 2000: 209-244.

STEVENS W R. TCP/IP illstrated volume 1: the protocols[M]. Translated by FAN Jian-hua, XU Guang-hui,ZHANG Tao, et al. Beijing: China Machine Press, 2000:209-244.

[12]BI Jing-ping, WU Qi, LI Zhong-cheng. Packet delay and packet loss in the Internet[C]//Proceedings of Seventh International Symposium on Computers and Communications. Taormina Italy: IEEE Computer Society Press, 2002: 3-8.

[13]RIZVI A A, HUSSAIN A. Analysis of single server queueing systems with heavy tail distributions[C]//7th International Multi Topic Conference. Islamabad: IEEE INMIC, 2003: 176-181.

编 辑 漆 蓉

Construction Method of Packet Loss Membership Function in Heterogeneous Networks

ZHEN Yan-xiang, SU Fang, KOU Ming-yan, and XU Hui-min

(School of Information and Communication Engineering, Beijing University of Posts and Telecommunications Haidian Beijing 100876)

The packet loss differentiating mechanism of TCP for heterogeneous networks plays an important role in the stability of wireless networks, relative one-way delay (ROD)of packet pair is used as the differentiating parameter to distinguish the loss type. The accuracy of this algorithm depends on ROD samples membership functions and parameters estimation. In order to differentiate the packet loss pattern more accurately, the initialization method based on potential functions is proposed by analyzing the traditional expectation maximization (EM)algorithm in Gaussian mixture model. Then the improved EM (PEM)algorithm is applied in the construction of different packet loss membership functions in the situation when the network congestion and wireless error coexist. The simulation results indicate that this algorithm has better convergence characteristics and stability, and has well building effect in the construction of different packet loss pattern membership functions.

EM algorithm; Gaussian distribution; heterogeneous networks; membership functions;potential functions

TN913

A

10.3969/j.issn.1001-0548.2010.06.009

2009- 06- 10;

2009- 10- 14

国家自然科学基金(60572122)

甄雁翔(1982- )，女，博士，主要从事无线多媒体应用方面的研究.