黃 超，董育寧

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

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

黃 超，董育寧

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

1 引言

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

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

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

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

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

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

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

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

針對(duì)上述問題，本文研究改進(jìn)的3G無(wú)線網(wǎng)絡(luò)丟包模型，并進(jìn)行仿真實(shí)驗(yàn)分析。本文的主要貢獻(xiàn)是：針對(duì)現(xiàn)有方法中在區(qū)間劃分時(shí)對(duì)于所有Gap均做相同處理，導(dǎo)致在信道誤碼率增加時(shí)模型的準(zhǔn)確性下降的缺點(diǎn)，提出一種改進(jìn)的基于Gap的3G無(wú)線網(wǎng)絡(luò)丟包模型。該模型設(shè)計(jì)了一種非均等的Gap區(qū)間劃分方法，不僅考慮了長(zhǎng)時(shí)間的網(wǎng)絡(luò)丟包狀況，同時(shí)考慮了相鄰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ò)丟包模型和仿真方法。該方法使用真實(shí)的網(wǎng)絡(luò)丟包序列訓(xùn)練出模型中涉及的參數(shù)，再用模型來生成丟包序列，并用于網(wǎng)絡(luò)仿真。此方法不僅描述了長(zhǎng)時(shí)間的網(wǎng)絡(luò)丟包狀況，同時(shí)考慮了相鄰丟包之間的相互關(guān)系，計(jì)算較簡(jiǎn)單，并且能夠更加準(zhǔn)確地描述3G網(wǎng)絡(luò)的丟包特性。

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

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

圖1 trace文件中的Gap和Cluster

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

圖2 trace文件中的Gap序列

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

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

很顯然有P(0)=1。

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

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

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

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

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

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

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

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

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

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

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

仿真部分（生成隨機(jī)丟包序列）：

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

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

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

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

3 仿真實(shí)驗(yàn)及結(jié)果分析

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

圖3 Gap的條件概率分布

從圖3可以看出，前一個(gè)時(shí)刻的Gap長(zhǎng)度越長(zhǎng)，下一個(gè)時(shí)刻生成長(zhǎng)Gap的概率就越大。

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

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

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

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

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

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

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

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

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

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

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

4 總結(jié)

本文研究了3G無(wú)線信道不同錯(cuò)誤率下數(shù)據(jù)包的丟失特性，提出了一種改進(jìn)的網(wǎng)絡(luò)數(shù)據(jù)包丟失模型和仿真方法。該方法不僅考慮了長(zhǎng)時(shí)間的網(wǎng)絡(luò)丟包狀況，同時(shí)考慮了相鄰丟包之間的相互關(guān)系，能夠比現(xiàn)有模型更加準(zhǔn)確地描述3G網(wǎng)絡(luò)的丟包特性，該模型還可用于NS2等網(wǎng)絡(luò)仿真軟件。本模型不僅適用于3G網(wǎng)絡(luò)，對(duì)于其他類型的網(wǎng)絡(luò)本模型也適用，只需對(duì)相關(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].計(jì)算機(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ú)線網(wǎng)絡(luò)的丟包問題是網(wǎng)絡(luò)應(yīng)用研究中比較重要的問題。通過對(duì)通信信道建模，利用計(jì)算機(jī)進(jìn)行信道仿真，可以不完全依靠實(shí)際的網(wǎng)絡(luò)而進(jìn)行相關(guān)網(wǎng)絡(luò)應(yīng)用的分析實(shí)驗(yàn)。基于馬爾可夫Gap模型，提出了一種改進(jìn)的網(wǎng)絡(luò)丟包模型，并基于該模型進(jìn)行了分析和仿真實(shí)驗(yàn)。該方法不僅考慮了長(zhǎng)時(shí)間的網(wǎng)絡(luò)丟包狀況，同時(shí)考慮了相鄰丟包之間的相互關(guān)系，能夠比現(xiàn)有模型更加準(zhǔn)確地描述3G網(wǎng)絡(luò)的丟包特性。

信道模型；丟包；計(jì)算機(jī)仿真

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.

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

黃超（1988—），男，碩士研究生，研究領(lǐng)域?yàn)闊o(wú)線多媒體通信；董育寧（1955—），男，博士，教授，研究領(lǐng)域?yàn)槎嗝襟w通信、無(wú)線通信網(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