異構(gòu)網(wǎng)絡(luò)中丟包隸屬度函數(shù)的構(gòu)建方法

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

(北京郵電大學(xué)信息與通信工程學(xué)院 北京 海淀區(qū) 100876)

異構(gòu)網(wǎng)絡(luò)中丟包隸屬度函數(shù)的構(gòu)建方法

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

(北京郵電大學(xué)信息與通信工程學(xué)院 北京 海淀區(qū) 100876)

異構(gòu)網(wǎng)絡(luò)中TCP丟包區(qū)分機(jī)制對(duì)無(wú)線網(wǎng)絡(luò)的穩(wěn)定性起著重要的作用，包對(duì)探測(cè)包的單向傳輸時(shí)延(ROD)作為區(qū)分參數(shù)對(duì)不同丟包類(lèi)型進(jìn)行區(qū)分，算法的準(zhǔn)確度依賴(lài)于ROD樣本的隸屬度函數(shù)及其參數(shù)估算。為了更加準(zhǔn)確地區(qū)分丟包類(lèi)型，通過(guò)對(duì)傳統(tǒng)高斯混合模型的EM算法進(jìn)行分析，提出了基于勢(shì)函數(shù)的初始化方法，并且在網(wǎng)絡(luò)擁塞和無(wú)線誤碼同時(shí)存在的情況下，將改進(jìn)的EM算法(PEM)應(yīng)用于不同丟包模式下隸屬度函數(shù)的構(gòu)建中。仿真驗(yàn)證了該算法具有較好的收斂特性和穩(wěn)定性，并且對(duì)不同丟包模式隸屬度函數(shù)的確定達(dá)到了很好的構(gòu)建效果。

EM算法; 高斯分布；異構(gòu)網(wǎng)絡(luò); 隸屬度函數(shù); 勢(shì)函數(shù)

隨著無(wú)線應(yīng)用技術(shù)的快速發(fā)展，無(wú)線廣域網(wǎng)(GPRS、UMTS等)、無(wú)線局域網(wǎng)(IEEE802.11)、衛(wèi)星通信網(wǎng)、藍(lán)牙網(wǎng)絡(luò)等多種無(wú)線網(wǎng)絡(luò)系統(tǒng)正逐步代替?zhèn)鹘y(tǒng)有線網(wǎng)絡(luò)成為互聯(lián)網(wǎng)接入的最后一跳。TCP是目前Internet中廣泛使用的端到端傳輸控制協(xié)議，在有線/無(wú)線融合的異構(gòu)網(wǎng)絡(luò)環(huán)境中，由于無(wú)線網(wǎng)絡(luò)中存在高誤碼率、信號(hào)衰落、切換等原因，網(wǎng)絡(luò)擁塞不是引起TCP分組丟失的唯一原因，無(wú)線誤碼也會(huì)引起分組的丟失[1-2]。而傳統(tǒng)的TCP協(xié)議把所有的分組丟失簡(jiǎn)單地歸因于網(wǎng)絡(luò)擁塞，就會(huì)造成盲目減小發(fā)送速率，降低帶寬利用率，導(dǎo)致TCP性能的無(wú)謂惡化[3-4]。因此，只有正確區(qū)分無(wú)線誤碼所造成的丟包和網(wǎng)絡(luò)擁塞所造成的丟包，分別采取不同的控制策略，才能提高網(wǎng)絡(luò)的效率。

文獻(xiàn)[5]采用包對(duì)(packet pair)探測(cè)包的ROD作為區(qū)分參數(shù)對(duì)不同丟包類(lèi)型進(jìn)行區(qū)分，采用條件概率構(gòu)造不同丟包模式下的隸屬度函數(shù)，從而按照最大隸屬度原則進(jìn)行丟包區(qū)分，提出了異構(gòu)網(wǎng)絡(luò)下基于Fuzzy模式識(shí)別的丟包區(qū)分算法，該算法的準(zhǔn)確度依賴(lài)于ROD樣本的隸屬度函數(shù)及其參數(shù)估算。

傳統(tǒng)的參數(shù)估計(jì)方法如最大似然估計(jì)、最小二乘法等是在先驗(yàn)知識(shí)和類(lèi)標(biāo)號(hào)已知的條件下進(jìn)行的。但在異構(gòu)網(wǎng)絡(luò)丟包區(qū)分的應(yīng)用領(lǐng)域里，會(huì)出現(xiàn)對(duì)丟包分類(lèi)不了解，即沒(méi)有先驗(yàn)知識(shí)的情況，因此需要借助無(wú)監(jiān)督的分類(lèi)技術(shù)。聚類(lèi)分析就是在沒(méi)有任何關(guān)于分類(lèi)先驗(yàn)知識(shí)的情況下，依據(jù)數(shù)據(jù)的相似性劃分?jǐn)?shù)據(jù)的類(lèi)[6]。目前主要的聚類(lèi)技術(shù)有以下幾類(lèi)：劃分方法、層次方法、基于密度的方法、基于網(wǎng)格的方法、基于模型的方法等[7]。這些方法采用不同的方式確定聚類(lèi)中心，但都有各自的局限性。如劃分方法算法簡(jiǎn)單，但只適用于識(shí)別中小規(guī)模具有相近尺寸和密度的球狀類(lèi)數(shù)據(jù)集，對(duì)大規(guī)模的數(shù)據(jù)集以及復(fù)雜形狀的聚類(lèi)，需要進(jìn)一步地?cái)U(kuò)展。層次方法的局限性在于合并點(diǎn)或分類(lèi)點(diǎn)的選擇，如果在某一步?jīng)]有很好地做出合并或分裂的決定，可能會(huì)導(dǎo)致低質(zhì)量的聚類(lèi)結(jié)果?；诿芏鹊姆椒軌蛟谟性肼暤目臻g數(shù)據(jù)庫(kù)中發(fā)現(xiàn)任意形狀的聚類(lèi)，但對(duì)于密度分布不均的數(shù)據(jù)集得不到滿意的聚類(lèi)效果；此外，其對(duì)于密度函數(shù)參數(shù)的設(shè)置也比較敏感?；诰W(wǎng)格的方法處理速度較快，但該算法精確性較低?；谀Ｐ偷木垲?lèi)方法是為每一類(lèi)假定一個(gè)模型，然后尋找數(shù)據(jù)對(duì)給定模型的最佳擬合。因此，聚類(lèi)算法的選擇依賴(lài)于可用數(shù)據(jù)的類(lèi)型和應(yīng)用的特定目標(biāo)，有些情況可以根據(jù)聚類(lèi)標(biāo)準(zhǔn)綜合多種聚類(lèi)技術(shù)。

由文獻(xiàn)[5]和大量仿真實(shí)驗(yàn)可知，包對(duì)探測(cè)包的ROD樣本在不同丟包模式下的隸屬度函數(shù)符合高斯混合分布，每一類(lèi)都可以用參數(shù)概率分布數(shù)學(xué)描述。對(duì)不同丟包模式隸屬度函數(shù)的構(gòu)建即確定隸屬度函數(shù)的參數(shù)，基于模型的聚類(lèi)方法正是試圖優(yōu)化給定數(shù)據(jù)和某數(shù)學(xué)模型之間的擬合，因此選取基于模型的聚類(lèi)方法即可描述不同丟包模式下的隸屬度函數(shù)。傳統(tǒng)的EM算法[8]是一種基于統(tǒng)計(jì)模型進(jìn)行期望最大化分析的算法，對(duì)初始值的選擇具有很強(qiáng)的依賴(lài)性。本文通過(guò)對(duì)傳統(tǒng)高斯混合模型的EM算法進(jìn)行分析，提出了基于勢(shì)函數(shù)[9]的方法確定聚類(lèi)中心，并且在網(wǎng)絡(luò)擁塞和無(wú)線誤碼同時(shí)存在的情況下，將改進(jìn)后的PEM算法運(yùn)用到不同丟包模式下隸屬度函數(shù)的構(gòu)建中。仿真驗(yàn)證PEM算法比傳統(tǒng)EM算法具有較好的穩(wěn)定性和收斂特性，對(duì)不同丟包模式的隸屬度函數(shù)可以達(dá)到很好的區(qū)分效果，具有很好的實(shí)際應(yīng)用價(jià)值。

1 高斯混合模型的EM算法

1.1 算法描述

1.2 算法分析

由以上算法描述可知，EM算法的核心是根據(jù)一個(gè)代表隸屬度概率的權(quán)值將每個(gè)對(duì)象指派到類(lèi)中，并不斷迭代使之收斂于某個(gè)最優(yōu)值。運(yùn)用EM算法實(shí)現(xiàn)高斯混合模型聚類(lèi)，如何初始化參數(shù)是一個(gè)關(guān)鍵問(wèn)題，EM算法收斂的優(yōu)劣很大程度上取決于其初始參數(shù)[10]。

對(duì)于高斯混合模型，參數(shù)的初始化主要包括每一類(lèi)的均值kμ、方差2kσ、權(quán)重kπ和類(lèi)的個(gè)數(shù)M。對(duì)于中心值的選取，目前常用的方法是隨機(jī)選取，然后通過(guò)不斷迭代調(diào)整達(dá)到最優(yōu)。該種隨機(jī)選取的方法雖然操作簡(jiǎn)單，但對(duì)于算法的收斂穩(wěn)定性有一定的影響，有時(shí)會(huì)收斂于局部最小值，而不能得到全局最優(yōu)解，使得聚類(lèi)效果受到影響；在數(shù)據(jù)規(guī)模較大的情況下，效率也很低，耗時(shí)長(zhǎng)且需要較大的存儲(chǔ)空間。本文提出了基于勢(shì)函數(shù)的方法選取聚類(lèi)中心，仿真驗(yàn)證，在達(dá)到同樣精度的條件下，該算法具有較好的收斂速度和穩(wěn)定性。

1.3 PEM算法

基于勢(shì)函數(shù)的方法確定聚類(lèi)中心值，算法步驟如下。

(1)計(jì)算每個(gè)樣本點(diǎn)的初始勢(shì)值，定義初始勢(shì)函數(shù)為：

由上述勢(shì)函數(shù)公式可知，樣本點(diǎn)的勢(shì)值不僅與樣本點(diǎn)間的距離有關(guān)，還與樣本點(diǎn)發(fā)生的次數(shù)有關(guān)。當(dāng)樣本點(diǎn)發(fā)生的概率比較大，且具有足夠高的密度，其勢(shì)值就會(huì)相對(duì)較大。利用上述迭代公式，可以依次找到樣本的最密集點(diǎn)1μ，次密集點(diǎn)2μ、μ2、、Mμ，這些點(diǎn)可以作為高斯混合模型中每個(gè)高斯分布的初始均值。

1.4 仿真驗(yàn)證

在Matlab7仿真平臺(tái)上，隨機(jī)產(chǎn)生幾類(lèi)高斯混合分布，由勢(shì)函數(shù)的方法確定出聚類(lèi)中心，如表1所示。由勢(shì)函數(shù)確定的聚類(lèi)中心可以近似表示為每個(gè)高斯分布的均值，從而驗(yàn)證了算法的有效性。

表1 由勢(shì)函數(shù)確定的聚類(lèi)中心值

對(duì)理論構(gòu)造的高斯混合分布數(shù)據(jù)，選取不同類(lèi)數(shù)的樣本集合，采用不同的初始化方法進(jìn)行聚類(lèi)仿真。通過(guò)大量仿真實(shí)驗(yàn)可知，達(dá)到相同的精度，隨機(jī)選取聚類(lèi)中心迭代次數(shù)不穩(wěn)定，具有很大的隨機(jī)性?；趧?shì)函數(shù)的方法選取聚類(lèi)中心迭代次數(shù)穩(wěn)定且收斂速度快，表2為不同初始化方法的平均迭代次數(shù)比較。

表2 理論樣本不同初始化方法平均迭代次數(shù)比較

2 不同丟包模式隸屬度函數(shù)的構(gòu)建

2.1 不同丟包模式隸屬度函數(shù)的特點(diǎn)

在網(wǎng)絡(luò)擁塞和無(wú)線誤碼同時(shí)存在的情況下，通過(guò)對(duì)文獻(xiàn)[5]和大量包對(duì)探測(cè)包的ROD樣本進(jìn)行分析可知，擁塞丟包模式下ROD的隸屬度函數(shù)為高斯混合分布，瓶頸的個(gè)數(shù)即為高斯混合分布類(lèi)的個(gè)數(shù)。無(wú)線誤碼丟包模式下ROD的隸屬度函數(shù)也為高斯混合分布，但與誤碼率有關(guān)。誤碼率較大時(shí)，由誤碼引起的丟包概率增大，由TCP協(xié)議[11]可知，擁塞窗口會(huì)不斷進(jìn)行減半調(diào)整，發(fā)生擁塞的概率減?。划?dāng)誤碼率較小時(shí)，發(fā)生擁塞的概率增大，擁塞丟包的特征變得明顯。因此，無(wú)線誤碼模式下丟包隸屬度函數(shù)隨誤碼率的變化而變化[12]。

2.2 不同丟包模式下隸屬度函數(shù)的確定

擁塞丟包模式下，由于網(wǎng)絡(luò)中可能會(huì)有多個(gè)瓶頸，通過(guò)大量仿真實(shí)驗(yàn)可知，每個(gè)瓶頸處包對(duì)探測(cè)包的ROD樣本可以用一個(gè)高斯分布來(lái)描述。當(dāng)瓶頸數(shù)大于兩個(gè)時(shí)，瓶頸處的ROD樣本的次數(shù)很少，在高斯混合分布中的權(quán)重也很小，與瓶頸為兩個(gè)的ROD分布特征近似。因此，擁塞模式的隸屬度函數(shù)可以由一個(gè)類(lèi)數(shù)為2的高斯混合分布來(lái)描述。

無(wú)線誤碼丟包模式下，通過(guò)大量仿真實(shí)驗(yàn)可知，當(dāng)誤碼率較大時(shí)，隸屬度函數(shù)的均值和方差都比較小，當(dāng)誤碼率較小的時(shí)候，隸屬度函數(shù)的方差比較大。由于無(wú)線誤碼丟包具有很大的隨機(jī)性，所以ROD分布具有重尾現(xiàn)象[13]。高斯混合模型的EM算法對(duì)重尾數(shù)據(jù)的描述是用一個(gè)方差比較大的高斯分布進(jìn)行擬合。因此，無(wú)線誤碼模式的隸屬度函數(shù)可以由一個(gè)類(lèi)數(shù)為2的高斯混合分布來(lái)描述。

由以上分析可知，在網(wǎng)絡(luò)擁塞和無(wú)線誤碼同時(shí)存在的情況下，類(lèi)的個(gè)數(shù)為4。因此，在利用勢(shì)函數(shù)的方法確定聚類(lèi)中心時(shí)，選取4類(lèi)進(jìn)行迭代。

類(lèi)個(gè)數(shù)確定后，定義由PEM算法描述不同丟包模式的隸屬度函數(shù)為：

式中 PC為擁塞丟包模式的隸屬度函數(shù)；PW為無(wú)線誤碼丟包模式的隸屬度函數(shù)。

采用PEM算法估算出4個(gè)高斯分布的參數(shù)，然后根據(jù)不同丟包模式下隸屬度函數(shù)的特點(diǎn)，將估算出的高斯分布的均值kμ和方差2kσ作為不同丟包模式的區(qū)分參數(shù)進(jìn)行分類(lèi)。

(1)比較方差：選取方差最大的一類(lèi)高斯分布作為無(wú)線誤碼丟包的隸屬度函數(shù)。

(2)比較均值：對(duì)其余3類(lèi)高斯分布比較均值，選取均值最小的作為無(wú)線誤碼丟包的隸屬度函數(shù)，其余兩類(lèi)即為網(wǎng)絡(luò)擁塞丟包的隸屬度函數(shù)。

由以上步驟即可確定式(6)不同丟包模式的隸屬度函數(shù)。

2.3 仿真驗(yàn)證

利用Matlab7進(jìn)行仿真，表3為不同網(wǎng)絡(luò)條件下丟包隸屬度函數(shù)統(tǒng)計(jì)參數(shù)表，表4為不同初始化方法平均迭代次數(shù)的比較。

表3 不同網(wǎng)絡(luò)條件下丟包隸屬度函數(shù)統(tǒng)計(jì)參數(shù)表

表4 ROD樣本不同初始化方法平均迭代次數(shù)比較

可以看出，對(duì)于ROD樣本，PEM算法比傳統(tǒng)EM算法具有較好的穩(wěn)定性和收斂特性。圖1為不同網(wǎng)絡(luò)條件下ROD樣本分布及隸屬度函數(shù)對(duì)比圖。比較ROD樣本分布圖和由PEM算法確定的隸屬度函數(shù)，可以看出隸屬度函數(shù)能近似表示實(shí)際樣本的概率分布，從而驗(yàn)證了該方法模型的有效性。

圖1 不同網(wǎng)絡(luò)條件下ROD樣本分布與隸屬度函數(shù)對(duì)比圖

3 結(jié) 束 語(yǔ)

本文通過(guò)對(duì)傳統(tǒng)高斯混合模型的EM算法進(jìn)行分析，針對(duì)傳統(tǒng)EM算法在收斂速度和穩(wěn)定性上的問(wèn)題，在保持算法迭代簡(jiǎn)單的前提下，提出了基于勢(shì)函數(shù)的方法來(lái)確定初始聚類(lèi)中心，從而達(dá)到更穩(wěn)定的聚類(lèi)效果。并在網(wǎng)絡(luò)擁塞和無(wú)線誤碼同時(shí)存在的情況下，將PEM算法運(yùn)用到異構(gòu)網(wǎng)絡(luò)條件下不同丟包模式隸屬度函數(shù)參數(shù)的估算中。仿真驗(yàn)證該算法具有很好的收斂速度和穩(wěn)定性，對(duì)不同丟包模式的隸屬度函數(shù)可以達(dá)到很好的區(qū)分效果，進(jìn)而可以更加準(zhǔn)確地區(qū)分丟包類(lèi)型，提高網(wǎng)絡(luò)的效率。

本文的研究工作得到了華為高?？萍蓟?YJCB2005055WL)的資助，在此表示感謝！

[1]范英磊, 鄭培超, 蘇 放, 等. 異構(gòu)網(wǎng)絡(luò)中的視頻傳輸服務(wù)質(zhì)量框架[J]. 電子科技大學(xué)學(xué)報(bào), 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丟包區(qū)分的TCP擁塞控制算法[J]. 系統(tǒng)仿真學(xué)報(bào), 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]高新波. 模糊聚類(lèi)分析及其應(yīng)用[M]. 西安: 西安電子科技大學(xué)出版社, 2004: 37-60.

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

[7]韓家煒, 堪 博. 數(shù)據(jù)挖掘概念與技術(shù)[M]. 范 明, 孟小峰, 譯. 第2版. 北京: 機(jī)械工業(yè)出版社, 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: 協(xié)議[M]. 范建華, 胥光輝，張 濤, 等, 譯. 北京: 機(jī)械工業(yè)出版社, 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

國(guó)家自然科學(xué)基金(60572122)

甄雁翔(1982- )，女，博士，主要從事無(wú)線多媒體應(yīng)用方面的研究.