黃 超，董育寧

南京郵電大學(xué) 通信與信息工程學(xué)院，南京 210003

一種改進(jìn)的3G無線網(wǎng)絡(luò)丟包模型及仿真方法

黃 超，董育寧

南京郵電大學(xué) 通信與信息工程學(xué)院，南京 210003

1 引言

無線和移動性逐漸成為終端設(shè)備的基本要求，越來越多的應(yīng)用和服務(wù)要求接入到可靠的信道中。但是由于無線移動信道容易受干擾，所以通信容易發(fā)生錯誤。為了達(dá)到通信的可靠性要求，在設(shè)計這些新應(yīng)用和服務(wù)的時候就需要將信道特性考慮進(jìn)去。那么，如果能夠建立一個較為準(zhǔn)確的信道模型，就可以不完全依靠實際的網(wǎng)絡(luò)而進(jìn)行相關(guān)的分析實驗了。通信系統(tǒng)的建模和仿真可以使我們更快地評價端到端的通信性能，優(yōu)化終端和網(wǎng)絡(luò)的參數(shù)。

通常使用平均丟包率來描述網(wǎng)絡(luò)狀況，但是數(shù)據(jù)包的丟失情況往往和當(dāng)前的網(wǎng)絡(luò)狀況有關(guān)。實際的網(wǎng)絡(luò)中可能一段時間連續(xù)丟包，接下去一段時間所有數(shù)據(jù)包都能正確接收。文獻(xiàn)[1]對這種相關(guān)性進(jìn)行了分析，認(rèn)為數(shù)據(jù)包丟失事件之間是有相關(guān)性的，即實際的網(wǎng)絡(luò)信道是有記憶的。所以僅使用平均丟包率作為模型參數(shù)并不能準(zhǔn)確描述網(wǎng)絡(luò)的丟包特性，對于像NS2[2]這樣的仿真軟件，需要準(zhǔn)確的模型來描述網(wǎng)絡(luò)的丟包過程。

如果用隨機變量Xi表示第i個數(shù)據(jù)包的丟失情況，設(shè)Xi=0表示數(shù)據(jù)包正確接受，Xi=1表示數(shù)據(jù)包丟失。假設(shè)當(dāng)前數(shù)據(jù)包的丟失狀況和它前面的k個數(shù)據(jù)包相關(guān)，那么{Xi}就是一個k階馬爾可夫鏈，有2k個狀態(tài)。k值越大，階數(shù)越高，則模型復(fù)雜度越高。文獻(xiàn)[3]中使用馬爾可夫鏈模型來分析單路復(fù)用模型鏈路，描述了有線網(wǎng)絡(luò)單瓶頸節(jié)點的網(wǎng)絡(luò)情況。

當(dāng)k=0表示每個數(shù)據(jù)包的丟失情況都是獨立的，也就是伯努利模型，該模型以丟包率PL作為唯一參數(shù)。這種情況下包丟失密度：

表示在連續(xù)的n個數(shù)據(jù)包中丟失 j個數(shù)據(jù)包的概率。

Gilbert模型[4]是一種簡單的馬爾可夫模型，由EN Gilbert于1960年提出，可以用兩個獨立的事件概率 p和q來完整地描述。該模型可以用來描述網(wǎng)絡(luò)中的丟包現(xiàn)象，文獻(xiàn)[5-6]中都使用了該模型。文獻(xiàn)[7]中對該模型進(jìn)行了詳細(xì)分析，并給出了基于該模型的計算機仿真方法。文獻(xiàn)[8]中提出一種用于視頻數(shù)據(jù)在無線網(wǎng)絡(luò)上傳輸?shù)膩G包模型。該模型也基于Gilbert模型。雖然Gilbert模型簡單、容易實現(xiàn)，但是其精確性仍有待提高。

文獻(xiàn)[9]中作者分析發(fā)現(xiàn)Gilbert模型可以較精確地描述長時間下網(wǎng)絡(luò)的平均丟包情況，但是不能較好地反應(yīng)網(wǎng)絡(luò)狀況的變化，對突發(fā)性估計不足。另外對于應(yīng)用越來越廣泛的無線網(wǎng)絡(luò)，由于其易受周圍環(huán)境的影響，網(wǎng)絡(luò)不穩(wěn)定，所以Gilbert模型更不能準(zhǔn)確地描述無線網(wǎng)絡(luò)的信道情況。作者提出了一種擴(kuò)展的Gilbert模型，能更好地描述突發(fā)丟包。對于k階擴(kuò)展Gilbert模型共有k+1個狀態(tài){S0，S1，…，Sk}，對于每一個狀態(tài)的下標(biāo)表示當(dāng)前的接收長度至少是k，如果在狀態(tài)i時出現(xiàn)數(shù)據(jù)包丟失，那么系統(tǒng)狀態(tài)會轉(zhuǎn)到S0。每正確接收一個數(shù)據(jù)包都會使系統(tǒng)狀態(tài)向后轉(zhuǎn)移，直到Sk，如果這時仍收到數(shù)據(jù)包，則保持狀態(tài)不變。任何時刻出現(xiàn)數(shù)據(jù)包丟失都會導(dǎo)致系統(tǒng)將狀態(tài)轉(zhuǎn)到S0（丟失狀態(tài)），這時的數(shù)據(jù)包接收狀況之間的相關(guān)性消失，重新開始記錄。雖然擴(kuò)展馬爾可夫鏈的狀態(tài)可以提高一定的準(zhǔn)確性，但是文獻(xiàn)[10]中作者實驗研究發(fā)現(xiàn)增加狀態(tài)對于性能的提高并不是很大。另外增加狀態(tài)數(shù)的同時也使系統(tǒng)更加復(fù)雜，計算和存儲需求更高。文獻(xiàn)[11]作者使用隱馬爾可夫模型來描述比特信息在信道上的傳輸，文獻(xiàn)[12]中作者將該模型應(yīng)用到包層，根據(jù)丟包長度和丟包率將突發(fā)情況分類，使用隱馬爾可夫模型來描述UMTS（）網(wǎng)絡(luò)可能發(fā)生差錯的狀態(tài)。

文獻(xiàn)[13-14]提出了基于馬爾可夫Gap模型的丟包描述方法及網(wǎng)絡(luò)仿真技術(shù)，該方法較Gilbert模型能更好地描述網(wǎng)絡(luò)的丟包狀況。但是該方法在Gap區(qū)間劃分時對于所有Gap均做相同處理，使得在信道誤碼率增加時模型的準(zhǔn)確性下降。雖然增加劃分的區(qū)間數(shù)也可以提高精確性，但是這樣會加大計算量和存儲空間。

針對上述問題，本文研究改進(jìn)的3G無線網(wǎng)絡(luò)丟包模型，并進(jìn)行仿真實驗分析。本文的主要貢獻(xiàn)是：針對現(xiàn)有方法中在區(qū)間劃分時對于所有Gap均做相同處理，導(dǎo)致在信道誤碼率增加時模型的準(zhǔn)確性下降的缺點，提出一種改進(jìn)的基于Gap的3G無線網(wǎng)絡(luò)丟包模型。該模型設(shè)計了一種非均等的Gap區(qū)間劃分方法，不僅考慮了長時間的網(wǎng)絡(luò)丟包狀況，同時考慮了相鄰Gap之間的相關(guān)性。改進(jìn)后的模型生成的丟包序列能夠比現(xiàn)有模型更加準(zhǔn)確地描述3G網(wǎng)絡(luò)的丟包特性。

2 改進(jìn)的基于Gap的網(wǎng)絡(luò)丟包模型

下面通過研究3G網(wǎng)絡(luò)中不同網(wǎng)絡(luò)狀況下數(shù)據(jù)包的丟失特性，提出一種改進(jìn)的基于Gap的網(wǎng)絡(luò)丟包模型和仿真方法。該方法使用真實的網(wǎng)絡(luò)丟包序列訓(xùn)練出模型中涉及的參數(shù)，再用模型來生成丟包序列，并用于網(wǎng)絡(luò)仿真。此方法不僅描述了長時間的網(wǎng)絡(luò)丟包狀況，同時考慮了相鄰丟包之間的相互關(guān)系，計算較簡單，并且能夠更加準(zhǔn)確地描述3G網(wǎng)絡(luò)的丟包特性。

根據(jù)馬爾可夫間隔模型，設(shè)二進(jìn)制序列{ei}表示數(shù)據(jù)的接收情況，ei=1表示第i個比特出錯，ei=0表示第i個比特正確接收。一個間隔（Gap）就是兩個錯誤比特之間一連串未出錯的比特序列，用{Xk}表示二進(jìn)制序列{ei}中各間隔的長度。該間隔模型可用來描述數(shù)據(jù)的差錯情況。

圖1中的二進(jìn)制序列{Li}表示數(shù)據(jù)包的接收情況，“1”表示數(shù)據(jù)包丟失，“0”表示數(shù)據(jù)包正確接收到。將序列分成兩類，間隔（Gap）和簇（Cluster），間隔表示沒有丟包的一段序列，用整數(shù)序列{Gk}表示{Li}中間隔的長度；簇表示連續(xù)丟包的一段序列，用整數(shù)序列{Ck}表示{Li}中簇的長度。

圖1 trace文件中的Gap和Cluster

前面定義的間隔表示沒有丟包的序列，為了能用間隔同時表示間隔序列和簇序列，定義間隔為0時表示一個丟包，如圖2所示。

圖2 trace文件中的Gap序列

得到一個用間隔序列表示的丟包模型。

間隔的概率p(m)定義如下：

很顯然有P(0)=1。

由上面兩個公式可得：為了簡化模型減少計算量，把間隔長度分成r個區(qū)間，rj表示區(qū)間[nj，nj+1)。

那么間隔的條件分布如公式（6）所示，表示第k個Gap長度落入第r個區(qū)間內(nèi)的條件下，下一個Gap長度大于等于m的概率。

馬爾可夫間隔模型假設(shè)間隔的長度序列{Gk}是一個離散時間整數(shù)取值的馬爾可夫過程且條件概率分布為P(m|nj≤n≤nj+1)，這樣模型中的狀態(tài)個數(shù)就減小為r個[nj，nj+1)這樣的區(qū)間。

原方法中Gap區(qū)間的劃分是以Gap均勻分布為準(zhǔn)則，也就是區(qū)間劃分好以后，每個區(qū)間中Gap的個數(shù)是相等的。本文改進(jìn)Gap區(qū)間的劃分方法，對于長度較短的Gap（如：0，1，2等）作較為精細(xì)的劃分，其他的Gap作較為粗略的劃分，以使能更好地描述連續(xù)丟包的情況。具體的區(qū)間劃分范圍需要在模型訓(xùn)練時對丟包記錄文件分析后確定。

根據(jù)上面描述的條件概率分布來生成丟包序列，由于在兩個相鄰的間隔之間引入了相關(guān)性，所以改進(jìn)后的馬爾可夫間隔模型能夠更好地描述網(wǎng)絡(luò)上的丟包情況。

本方法的建模過程包括模型訓(xùn)練和仿真序列生成兩部分，分別敘述如下。

訓(xùn)練部分（模型參數(shù)確定）：

（1）輸入Trace文件（包含0、1（byte）序列的二進(jìn)制文件）。

（2）統(tǒng)計Trace文件中不同長度Gap的個數(shù)，設(shè)最長Gap的長度為maxLength。

（3）劃分Gap區(qū)間（劃分為r個區(qū)間），對于長度較短的Gap（如：0，1，2等）作較為精細(xì)的劃分，其他的Gap作較為粗略的劃分。

（4）按步驟（3）中劃分的區(qū)間根據(jù)公式（6）求條件概率，這樣求得一個大小為r×(maxLength+1)的轉(zhuǎn)移矩陣P。

仿真部分（生成隨機丟包序列）：

（1）參考轉(zhuǎn)移矩陣P生成下一個Gap長度n，并令i=0；

（2）下一個數(shù)據(jù)包到達(dá)

該數(shù)據(jù)包正確接收，i++，重復(fù)步驟（2）else

該數(shù)據(jù)包丟失，返回步驟（1）

3 仿真實驗及結(jié)果分析

文獻(xiàn)[15]給出了實際3G信道的丟包記錄文件，本文仿真實驗使用了其中丟包率分別為3.19%、5.55%、11.16%的三個丟包記錄文件。三個丟包記錄文件均記錄了超過10 000個數(shù)據(jù)包的接收情況。通過分析其中一個丟包率為5.55%的丟包記錄文件，得到其P(m|nj≤n≤nj+1)分布如圖3所示。

圖3 Gap的條件概率分布

從圖3可以看出，前一個時刻的Gap長度越長，下一個時刻生成長Gap的概率就越大。

下面利用本文提出的丟包模型和仿真方法在計算機上生成丟包序列，并將其和原始數(shù)據(jù)、現(xiàn)有的Gilbert模型[6]和Gap模型[10]生成的丟包序列進(jìn)行了比較。為了評價模型的準(zhǔn)確性，實驗中使用了多種統(tǒng)計方法，除了平均丟包率和平均丟包長度，還使用了塊丟失率P(m，n)，表示在一個長度為n的數(shù)據(jù)包塊中丟包個數(shù)大于等于m的概率，實驗中使用的塊長度為12。

實驗場景一：使用丟包率為3.19%的丟包記錄文件，平均丟包長度為1.038 339，Gap長度均勻劃分為6個區(qū)間，各區(qū)間分別為0～3，4～10，11～19，20～32，33～54，55…仿真結(jié)果如表1和圖4所示。其中，“3GPP數(shù)據(jù)”表示真實值。

圖4 場景一塊丟失率仿真結(jié)果比較

表1 數(shù)據(jù)1相關(guān)統(tǒng)計量

實驗場景二：使用丟包率為5.55%的丟包記錄文件，平均丟包長度為1.134。根據(jù)建模過程訓(xùn)練部分第3步中Gap長度區(qū)間的劃分方法，將Gap長度區(qū)間劃分為0，1～2，3～6，7～14，15～28，29…仿真結(jié)果如表2和圖5所示。

圖5 場景二塊丟失率仿真結(jié)果比較

表2 數(shù)據(jù)2相關(guān)統(tǒng)計量

實驗場景三：使用丟包率為11.16%的丟包記錄文件，平均丟包長度為1.175 457。根據(jù)建模過程訓(xùn)練部分第3步中Gap長度區(qū)間的劃分方法，將Gap長度區(qū)間劃分為0，1，2，3，7～11，12…仿真結(jié)果如表3和圖6所示。

圖6 場景三塊丟失率仿真結(jié)果比較

表3 數(shù)據(jù)3相關(guān)統(tǒng)計量

本文仿真實驗的復(fù)雜度和計算量均和文獻(xiàn)[14]中方法相同。從表1～3中可以看出，在不同的丟包率下各模型都能較好地描述丟包率和平均丟包長度。下面考慮塊丟失率，從實驗場景一圖4中可以發(fā)現(xiàn)，當(dāng)丟包率較小的時候，Gilbert和Gap模型均能較好地描述信道的狀況。而當(dāng)丟包率變大時（圖5和圖6），Gilbert模型對于連續(xù)丟包情況的描述準(zhǔn)確性下降，Gap模型有了一定的改進(jìn)，但是本文模型可以更好地仿真信道的真實情況（與真實值最接近）。

4 總結(jié)

本文研究了3G無線信道不同錯誤率下數(shù)據(jù)包的丟失特性，提出了一種改進(jìn)的網(wǎng)絡(luò)數(shù)據(jù)包丟失模型和仿真方法。該方法不僅考慮了長時間的網(wǎng)絡(luò)丟包狀況，同時考慮了相鄰丟包之間的相互關(guān)系，能夠比現(xiàn)有模型更加準(zhǔn)確地描述3G網(wǎng)絡(luò)的丟包特性，該模型還可用于NS2等網(wǎng)絡(luò)仿真軟件。本模型不僅適用于3G網(wǎng)絡(luò)，對于其他類型的網(wǎng)絡(luò)本模型也適用，只需對相關(guān)網(wǎng)絡(luò)的丟包序列記錄文件進(jìn)行訓(xùn)練建模，就能得到適用于該網(wǎng)絡(luò)的丟包模型。

[1]Yajnik M，Moon S，Kurose J，et al.Measurement and modeling of the temporal dependence in packet loss[C]//Joint Conf IEEE Computer Communication，1999：345-353.

[2]The network simulator NS-2[EB/OL].[2012-11-10].http：// www.isi.edu/nsnam/ns/.

[3]Yu Xunqi，Modestino J W，Tian Xusheng.The accuracy of Markov chain models in predicting packet-loss statistics for a single multiplexer[J].IEEE Transactions on Information Theory，2008，54（1）：489-501.

[4]Gilbert E N.Capacity of a burst-noise channel[J].Bell System Tech Journal，1960，39：1253-1266.

[5]Sanneck H，Carle G A.Framework model for packet loss metric based on loss run length[C]//MMCN2000，2000：177-187.

[6]Jiang W，Schulzrinne H.Modeling of packet loss and delay and their effect on real-time multimedia service quality[C]// NOSSDAV2000，2000.

[7]蘭帆，張堯朝.基于Gilbert模型的網(wǎng)絡(luò)丟包仿真[J].計算機工程，2004（12）：200-203.

[8]Liu Fangqin，F(xiàn)an Yanfei，Shen Xuemin.An analytical model to study the packet loss burstiness over wireless channels[C]//Global Telecommunications Conference，2010：1-5.

[9]Carvalho L，Angeja J，Navarro A.A new packet loss model of the IEEE 802.11g wireless network for multimedia communications[J].Consumer Electronics IEEE，2005，51（3）：809-814.

[10]Cardoso K V.Accurate hidden Markov modeling of packet losses in indoor 802.11 networks[J].Communications Letters IEEE，2009，13（6）：417-419.

[11]Frías J G，Crespo M P.Hidden markov models for burst error characterization in indoor radio channels[J].IEEE Transactions on Vehicular Technology，1997，4（46）：1006-1020.

[12]Gomis V，Cabrera J，Plaza J C.Combined Markov model for packet loss characterization in UMTS channels[C]// IEEE 66th Vehicular Technology Conference，VTC 2007-Fall，Baltimore，MD，United States，2007：782-786.

[13]Haddad A，Tsai S，Goldberg B，et al.Markov gap Models for real communication channels[J].Communications IEEE，1975，23（11）：1189-1197.

[14]Lee H，Varshney P K.Gap-based modeling of packet losses over the Internet modeling[C]//MASCOTS，2002：507-510.

[15]Wenger S.VCEG Q15-I-16r1 Error patterns for Internet experiments[S].2002.

HUANG Chao,DONG Yuning

College of Telecommunication and Information Engineering,Nanjing University of Posts and Telecommunications,Nanjing 210003,China

Since the reliability of the communication system remains to be improved,packet loss is still a crucial issue in wireless network application research.Analysis experiments for network applications can be performed by computer simulation based on the communication channel model,not entirely rely on the actual network.An improved network packet loss model based on Gap model is proposed,and the simulation method is also described after the analysis of this model. Without complex calculation,the model can characterize the packet loss situation for long time and the interrelation between adjacent packet losses.It can simulate the packet loss characteristic of 3G network more accurate than existing models.

channel model;packet loss;computer simulation

通信系統(tǒng)的可靠性仍有待提高，無線網(wǎng)絡(luò)的丟包問題是網(wǎng)絡(luò)應(yīng)用研究中比較重要的問題。通過對通信信道建模，利用計算機進(jìn)行信道仿真，可以不完全依靠實際的網(wǎng)絡(luò)而進(jìn)行相關(guān)網(wǎng)絡(luò)應(yīng)用的分析實驗?；隈R爾可夫Gap模型，提出了一種改進(jìn)的網(wǎng)絡(luò)丟包模型，并基于該模型進(jìn)行了分析和仿真實驗。該方法不僅考慮了長時間的網(wǎng)絡(luò)丟包狀況，同時考慮了相鄰丟包之間的相互關(guān)系，能夠比現(xiàn)有模型更加準(zhǔn)確地描述3G網(wǎng)絡(luò)的丟包特性。

信道模型；丟包；計算機仿真

A

TP391

10.3778/j.issn.1002-8331.1301-0332

HUANG Chao,DONG Yuning.Improved packet loss model and simulation method for 3G network.Computer Engineering and Applications,2014,50（24）：100-103.

國家自然科學(xué)基金（No.60972038，No.61271233）；教育部高等學(xué)校博士學(xué)科點專項科研基金（No.20103223110001）。

黃超（1988—），男，碩士研究生，研究領(lǐng)域為無線多媒體通信；董育寧（1955—），男，博士，教授，研究領(lǐng)域為多媒體通信、無線通信網(wǎng)絡(luò)。E-mail：hc.huangch@gmail.com

2013-01-29

2013-06-07

1002-8331（2014）24-0100-04

CNKI網(wǎng)絡(luò)優(yōu)先出版：2013-07-03，http∶//www.cnki.net/kcms/detail/11.2127.TP.20130703.1142.005.html