高允翔，王健雄，肖創(chuàng)柏

(1. 中訊郵電咨詢?cè)O(shè)計(jì)院有限公司 信息技術(shù)部，北京 100048; 2. 重慶大學(xué) 計(jì)算機(jī)學(xué)院，重慶 400044;3. 北京工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，北京 100124)

?

一種移動(dòng)即時(shí)通訊消息重傳改進(jìn)機(jī)制

高允翔1，王健雄2，肖創(chuàng)柏3

(1. 中訊郵電咨詢?cè)O(shè)計(jì)院有限公司 信息技術(shù)部，北京 100048; 2. 重慶大學(xué) 計(jì)算機(jī)學(xué)院，重慶 400044;3. 北京工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，北京 100124)

摘要：為應(yīng)對(duì)移動(dòng)即時(shí)通訊(instant messaging，IM)消息頻繁重傳給服務(wù)器和網(wǎng)絡(luò)造成的負(fù)荷，基于隨機(jī)過程的更新理論，提出移動(dòng)即時(shí)通訊消息重傳模型來研究消息重傳性能。仿真實(shí)驗(yàn)結(jié)果表明，平均消息重傳數(shù)為1.22次，與重傳模型分析結(jié)果1.25次非常接近，取得比同類型模型更好的描述能力?；诮７治鼋Y(jié)果提出一種移動(dòng)即時(shí)通訊消息重傳改進(jìn)機(jī)制，采用固定重傳間隔，設(shè)置重傳計(jì)數(shù)器控制最大嘗試次數(shù)，相關(guān)仿真結(jié)果表明該機(jī)制能有效減少消息重傳次數(shù)，同時(shí)又不顯著增加消息傳遞時(shí)間。最后利用概率論中獨(dú)立同分布的中心極限定理分析消息重傳機(jī)制如何影響移動(dòng)即時(shí)通訊消息傳遞的總體服務(wù)質(zhì)量，并給出調(diào)整重傳間隔參數(shù)等服務(wù)優(yōu)化建議。

關(guān)鍵詞：即時(shí)通訊；消息重傳；可擴(kuò)展通訊和表示協(xié)議(XMPP)

0引言

即時(shí)通訊(instant messaging， IM)已經(jīng)成為繼電話、電子郵件之后又一流行的通信手段。近年來，隨著移動(dòng)網(wǎng)絡(luò)和移動(dòng)終端技術(shù)的快速發(fā)展，IM技術(shù)在移動(dòng)平臺(tái)上獲得了大規(guī)模的應(yīng)用，微信就是最成功的移動(dòng)互聯(lián)網(wǎng)應(yīng)用案例。移動(dòng)網(wǎng)絡(luò)環(huán)境相比因特網(wǎng)有一些新的特點(diǎn)，使得原有技術(shù)必須得到改進(jìn)才能滿足移動(dòng)用戶需求。當(dāng)前的IM協(xié)議主要規(guī)定了通信基本規(guī)則，并未對(duì)一些具體的性能處理算法進(jìn)行詳細(xì)描述，而這些算法是保障應(yīng)用成功的關(guān)鍵因素。業(yè)界技術(shù)領(lǐng)先的移動(dòng)IM應(yīng)用在這方面做了很多工作，比如，騰訊在IM領(lǐng)域多次榮獲專利大獎(jiǎng)，近年來累計(jì)取得數(shù)千項(xiàng)專利。但是這些專利內(nèi)容大多還未公開，所以本文研究工作的相關(guān)基礎(chǔ)只有少數(shù)研究機(jī)構(gòu)的一些科研成果。

本文選取移動(dòng)IM中的標(biāo)準(zhǔn)解決方案之一可擴(kuò)展通訊和表示協(xié)議(extensible messaging and presence protocol，XMPP)[1-7]作為研究對(duì)象，對(duì)移動(dòng)IM中消息重傳這個(gè)關(guān)鍵技術(shù)進(jìn)行深入的建模研究，提出有針對(duì)性的改進(jìn)方案，并借助相關(guān)仿真實(shí)驗(yàn)證明該方案的有效性。

目前相關(guān)研究領(lǐng)域已經(jīng)有一些關(guān)于消息重傳的分析模型，比如短消息重傳(short message retransmission，SMR)模型是用來分析短消息重傳過程的[8]。蓋革I型計(jì)數(shù)器[9]是一種記錄脈沖的科學(xué)儀器，蓋革模型對(duì)信號(hào)記錄過程進(jìn)行分析。但是，截止目前還沒有描述分析移動(dòng)IM即時(shí)消息傳遞過程的數(shù)學(xué)模型，本文嘗試建立這樣的分析模型，為移動(dòng)IM性能建模分析相關(guān)工作的開展打下一定的基礎(chǔ)。隨后進(jìn)行的仿真實(shí)驗(yàn)將驗(yàn)證本文提出的移動(dòng)IM即時(shí)消息重傳模型的有效性。

1消息重傳

由于移動(dòng)用戶行為特點(diǎn)和無線環(huán)境下時(shí)常出現(xiàn)掉線等情況，移動(dòng)即時(shí)通訊消息(簡(jiǎn)稱移動(dòng)即時(shí)消息)時(shí)常會(huì)出現(xiàn)初次傳遞失敗的情況。假如這種情況出現(xiàn)，移動(dòng)IM后臺(tái)服務(wù)器應(yīng)該間隔一段時(shí)間后重新傳遞該條即時(shí)消息[8]。無線連接建立時(shí)間一般很短，而且由于高峰值比特率等特性，傳輸移動(dòng)即時(shí)消息僅需幾毫秒，因此，發(fā)送這些消息的信道利用率一般非常低。但是如果這個(gè)移動(dòng)用戶所處位置無線網(wǎng)絡(luò)信號(hào)不好，或者處于高速移動(dòng)之中，就會(huì)經(jīng)常發(fā)生移動(dòng)即時(shí)消息傳遞失敗的情況，從而頻繁觸發(fā)消息重傳機(jī)制。由于無線環(huán)境中的這些特點(diǎn)，消息頻繁重傳給服務(wù)器和網(wǎng)絡(luò)造成較大負(fù)荷[10]。所以，需要考慮制定一種移動(dòng)即時(shí)消息重傳機(jī)制，以保證消息盡快送達(dá)，同時(shí)又盡可能減少重傳的代價(jià)。

移動(dòng)即時(shí)消息重傳機(jī)制具體指：移動(dòng)IM后臺(tái)服務(wù)器準(zhǔn)備給移動(dòng)用戶發(fā)送消息時(shí)，由于接收用戶的無線信號(hào)質(zhì)量欠佳，導(dǎo)致即時(shí)消息不能通過一次傳遞而成功，需要重新傳遞這些即時(shí)消息，并制定相應(yīng)的重傳機(jī)制來保證消息重傳的效率。這種重傳機(jī)制一般需要規(guī)定消息重傳的頻率、兩次傳遞之間的時(shí)間間隔等重要參數(shù)。另外，需要特別說明的一個(gè)情況是，從消息接收者的角度來看，存在2種消息重傳情況。

情況1消息接收用戶上線，相應(yīng)的用戶狀態(tài)轉(zhuǎn)為“在線”，移動(dòng)IM后臺(tái)服務(wù)器向其發(fā)送即時(shí)消息(屬于延遲發(fā)送)。

情況2消息接收用戶當(dāng)前在線，移動(dòng)IM后臺(tái)服務(wù)器可以向接收者發(fā)送各種類型的移動(dòng)即時(shí)消息。

下面介紹“情況1”中提到的被延遲發(fā)送的即時(shí)消息和“情況2”中提到的移動(dòng)即時(shí)消息類型。移動(dòng)即時(shí)通訊業(yè)務(wù)的關(guān)鍵部件就是消息延遲發(fā)送功能[11]。當(dāng)移動(dòng)IM用戶狀態(tài)異常，或者不在線時(shí)，移動(dòng)即時(shí)消息將被延遲發(fā)送。此時(shí)，移動(dòng)即時(shí)消息被存儲(chǔ)在移動(dòng)IM后臺(tái)服務(wù)器中，延遲一段時(shí)間后被重新發(fā)送給接收用戶[12]。對(duì)移動(dòng)IM用戶群內(nèi)的會(huì)話消息的處理方法也與此類似[13]。本章討論的移動(dòng)即時(shí)消息重傳過程中涉及的“消息”指廣義范疇內(nèi)的移動(dòng)即時(shí)消息，包含所有主要的類別，如會(huì)話消息、狀態(tài)消息、控制消息等。

當(dāng)前的XMPP版本[4-5]并沒有對(duì)無線環(huán)境下的即時(shí)消息重新傳遞過程做出特別規(guī)定，所以采用XMPP的移動(dòng)IM服務(wù)中涉及的消息重傳機(jī)制是：移動(dòng)IM后臺(tái)服務(wù)器向用戶發(fā)出即時(shí)消息后，一旦收到無線網(wǎng)絡(luò)返回傳遞失敗的錯(cuò)誤提示后，立即觸發(fā)消息重傳過程。通過上面對(duì)基于無線網(wǎng)絡(luò)進(jìn)行即時(shí)消息傳遞過程特點(diǎn)的分析，可以推知這種立即重傳的機(jī)制將會(huì)引發(fā)很高的傳遞代價(jià)，需要我們認(rèn)真分析移動(dòng)即時(shí)消息重傳過程，制定效率更高的移動(dòng)即時(shí)消息重傳機(jī)制。

2有關(guān)消息重傳的分析模型

2.1蓋革計(jì)數(shù)器模型

計(jì)數(shù)器是一種記錄脈沖的科學(xué)儀器。計(jì)數(shù)器存在功能不完善的情況，在進(jìn)行調(diào)整的時(shí)間段(閉鎖時(shí)間)內(nèi)無法記錄到達(dá)的信號(hào)。計(jì)數(shù)器模型根據(jù)這種閉鎖情況的不同可以分為2種類型，下面簡(jiǎn)要介紹對(duì)分析移動(dòng)IM消息重傳過程有幫助的蓋革I型計(jì)數(shù)器模型[9]。

假設(shè)待記錄信號(hào)到達(dá)計(jì)數(shù)器的過程是一個(gè)更新過程(參見隨機(jī)過程的更新理論[9])，間隔為Xn,n≥1，服從分布F。計(jì)數(shù)器閉鎖時(shí)間記為Yn,n≥1，服從分布G，并且與信號(hào)到達(dá)過程互相獨(dú)立。一個(gè)信號(hào)在時(shí)刻0的到達(dá)事件使得蓋革計(jì)數(shù)器產(chǎn)生一段閉鎖時(shí)間Y1。假設(shè)Zn,n≥1表示計(jì)數(shù)過程(這也構(gòu)成了一個(gè)更新過程)。

在計(jì)數(shù)器長(zhǎng)時(shí)間運(yùn)行后，單位時(shí)間內(nèi)平均到達(dá)1/E[Xi]個(gè)信號(hào)，平均計(jì)數(shù)1/E[Zi]次。所以，信號(hào)發(fā)送總數(shù)與記錄成功數(shù)的比例是

(1)

如果信號(hào)到達(dá)過程是一個(gè)泊松過程，信號(hào)到達(dá)間隔服從指數(shù)分布，則

(2)

逐次計(jì)數(shù)同上面描述一樣，形成另一個(gè)更新過程，并且在(0,t)內(nèi)計(jì)數(shù)次數(shù)是漸進(jìn)正態(tài)的。

蓋革I型計(jì)數(shù)器非常類似于準(zhǔn)備接收移動(dòng)即時(shí)消息的手機(jī)終端，計(jì)數(shù)器的閉鎖期類似于手機(jī)終端的無服務(wù)期，到達(dá)計(jì)數(shù)器的信號(hào)類似于移動(dòng)IM后臺(tái)服務(wù)器發(fā)給手機(jī)終端的即時(shí)消息。如果從上述角度出發(fā)進(jìn)行分析，移動(dòng)IM重傳過程可以借助蓋革I型計(jì)數(shù)器模型來進(jìn)行分析。下面將在分析和實(shí)驗(yàn)過程中參考蓋革計(jì)數(shù)器模型的分析值。

2.2SMR模型

SMR模型是用來分析移動(dòng)短消息重傳過程的[8]，移動(dòng)短消息傳遞過程與移動(dòng)IM消息傳遞過程具有很大的相似性，與這兩種業(yè)務(wù)分別關(guān)聯(lián)的用戶情況、網(wǎng)絡(luò)情況，以及消息傳遞情況大致相似?；谶@種相似性，本文借助SMR模型進(jìn)行移動(dòng)IM重傳過程分析。首先，介紹一下SMR模型中使用的參數(shù)：N表示消息重傳數(shù)，M表示消息最大重傳數(shù)，T表示消息傳遞時(shí)間，p表示消息重傳失敗概率，c表示連接區(qū)間長(zhǎng)度均值，d表示斷開區(qū)間長(zhǎng)度均值，1/λ表示重傳間隔均值。

SMR模型的輸出項(xiàng)是平均消息重傳數(shù)E[N]、平均消息傳遞時(shí)間E[T]、消息重傳失敗概率p。為了使分析模型輸出結(jié)果表達(dá)式更加清晰簡(jiǎn)潔，本文進(jìn)行如下假設(shè)

k=c+d+λcd，

(3)

下面依次給出SMR分析模型3個(gè)輸出項(xiàng)的表達(dá)式，其中，平均消息重傳數(shù)為

(4)

平均消息傳遞時(shí)間為

(5)

重傳失敗概率為

(6)

2.3移動(dòng)IM即時(shí)消息重傳模型

圖1是移動(dòng)IM即時(shí)消息重傳時(shí)序圖。移動(dòng)終端在t0，t4時(shí)刻連接到移動(dòng)網(wǎng)絡(luò)處于連線狀態(tài)，其中，Ci=t1-t0，Ci+1=t6-t4。移動(dòng)終端在t1，t6時(shí)刻斷開與移動(dòng)網(wǎng)絡(luò)的連接處于掉線狀態(tài)，其中，Di=t4-t1，Di+1=t7-t6。移動(dòng)IM即時(shí)消息重傳事件發(fā)生在t2，t3，t5時(shí)刻。其中，后臺(tái)服務(wù)器在t2，t3時(shí)刻發(fā)送的即時(shí)消息，由于移動(dòng)終端處于斷網(wǎng)狀態(tài)，傳送失敗，所以繼續(xù)觸發(fā)即時(shí)消息的下一次重傳。在t5時(shí)刻發(fā)送的即時(shí)消息，由于移動(dòng)終端處于連網(wǎng)狀態(tài)，傳送成功，一次即時(shí)消息傳遞過程結(jié)束。Ti=t7-t0表示一次即時(shí)消息傳遞過程，也代表一次傳輸時(shí)間窗口。圖例中傳輸時(shí)間窗口內(nèi)共包含3次即時(shí)消息重傳事件(3次重傳事件的時(shí)間間隔分別為Ri=t2-t0，Ri+1=t3-t2，Ri+2=t5-t3)，所以在[t0,t7]，N=3(N表示消息重傳數(shù))。

圖1　移動(dòng)IM即時(shí)消息重傳時(shí)序圖Fig.1　Timing diagram for message retransmission

假設(shè)移動(dòng)IM即時(shí)消息重新傳遞的過程是一個(gè)更新過程，間隔為Ri,i≥1，服從分布E1；移動(dòng)終端連線區(qū)間記為Ci,i≥1，服從分布E2；移動(dòng)終端掉線區(qū)間記為Di,i≥1，服從分布E3；移動(dòng)IM即時(shí)消息成功發(fā)送的計(jì)數(shù)過程記為Si,i≥1，服從分布E4。上述的幾個(gè)更新過程之間相互獨(dú)立。

假設(shè)T表示消息傳輸時(shí)間窗口，N表示一個(gè)傳輸時(shí)間窗口內(nèi)的消息重傳數(shù)，p表示在一個(gè)傳輸時(shí)間窗口內(nèi)消息傳遞失敗概率，1/χ=E[Ci]表示連接區(qū)間長(zhǎng)度均值，1/δ=E[Di]表示斷開區(qū)間長(zhǎng)度均值，1/λ=E[Ri]表示重傳間隔均值，1/γ=E[T]表示傳輸時(shí)間窗口長(zhǎng)度均值，1/η=E[Si]表示成功傳遞間隔均值。

一個(gè)即時(shí)消息傳輸時(shí)間窗口標(biāo)志著一次更新循環(huán)。由隨機(jī)過程的更新理論可知

(7)

假設(shè)關(guān)于N的更新函數(shù)為m(t)=E[N]，對(duì)(7)式兩邊取拉普拉斯變化后得

(8)

由拉普拉斯變換卷積性質(zhì)可得

(9)

假設(shè)即時(shí)消息重傳分布服從均值為u，方差為V的伽瑪分布，其拉普拉斯變化為

(10)

代入(9)式可得

(11)

為考察重傳分布屬性對(duì)重傳模型的影響，假設(shè)V=u2(仿真實(shí)驗(yàn)會(huì)考察其它比例關(guān)系對(duì)結(jié)果的影響)，代入(11)式可得

(12)

取拉普拉斯反變換得

(13)

在移動(dòng)IM后臺(tái)服務(wù)器運(yùn)行一段時(shí)間后，單位時(shí)間內(nèi)平均傳送λ個(gè)即時(shí)消息，平均成功傳送η個(gè)即時(shí)消息。所以，移動(dòng)IM即時(shí)消息發(fā)送總數(shù)與發(fā)送成功數(shù)的比例是λ/η。

由于移動(dòng)IM后臺(tái)服務(wù)器成功傳送即時(shí)消息依賴于移動(dòng)終端連線區(qū)間長(zhǎng)度，移動(dòng)終端在線區(qū)間越長(zhǎng)，后臺(tái)服務(wù)器給移動(dòng)終端傳遞即時(shí)消息成功概率也越大；反之，移動(dòng)終端在線區(qū)間越短，后臺(tái)服務(wù)器給移動(dòng)終端傳遞即時(shí)消息失敗概率也越大。所以，移動(dòng)終端連線區(qū)間長(zhǎng)度均值與移動(dòng)IM后臺(tái)服務(wù)器傳送即時(shí)消息平均成功數(shù)具有同方向、同比例變化關(guān)系，所以有E[N]=λ/χ。

假設(shè)隨機(jī)向量(Ci,Di),i≥1，獨(dú)立同分布，因此，隨機(jī)變量序列{Ci}與{Di}都是獨(dú)立同分布的，設(shè)F是Ci+Di,i≥1的分布，Ci與Di隨著移動(dòng)終端連線、掉線的動(dòng)作進(jìn)行交替，可知它們構(gòu)成一個(gè)交替更新過程。由交替更新定理可知

(14)

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

3.1實(shí)驗(yàn)設(shè)計(jì)

移動(dòng)IM重傳性能實(shí)驗(yàn)環(huán)境為一臺(tái)IBM System x3400 M3服務(wù)器，Xeon E5506 2.13 GHz、四線程CPU，操作系統(tǒng)為Windows Server 2003。本文用C++實(shí)現(xiàn)了仿真程序，模擬消息達(dá)到、用戶在線狀態(tài)改變等隨機(jī)事件，驗(yàn)證上述分析模型的有效性。移動(dòng)IM重傳實(shí)驗(yàn)設(shè)計(jì)方案中的3個(gè)關(guān)鍵點(diǎn)是：

1)按照特定分布規(guī)律產(chǎn)生消息到達(dá)、消息重傳、手機(jī)終端狀態(tài)改變這3種事件；

2)設(shè)計(jì)一個(gè)事件隊(duì)列以便讓上述3種隨機(jī)事件按預(yù)設(shè)時(shí)間戳的先后順序產(chǎn)生；

3)通過間隔時(shí)間隨機(jī)數(shù)組來生成3種事件的預(yù)設(shè)時(shí)間戳。

移動(dòng)IM重傳性能實(shí)驗(yàn)需要的輸入?yún)?shù)如下：連接區(qū)間長(zhǎng)度分布采用服從指數(shù)分布的測(cè)試數(shù)據(jù)，連接區(qū)間長(zhǎng)度均值取17，連接區(qū)間長(zhǎng)度樣本數(shù)取1 000；斷開區(qū)間長(zhǎng)度分布采用服從指數(shù)分布的測(cè)試數(shù)據(jù)，斷開區(qū)間長(zhǎng)度均值取15，斷開區(qū)間長(zhǎng)度樣本數(shù)取1 000；重傳間隔分布取固定值，而不服從任何一種隨機(jī)分布，重傳間隔均值取14，重傳間隔樣本數(shù)取1，訪問事件總數(shù)取1 000；移動(dòng)IM重傳性能實(shí)驗(yàn)流程如圖2所示。

圖2　消息重傳性能實(shí)驗(yàn)流程圖Fig.2　Experimental flow chart about message retransmission

3.2結(jié)果分析及重傳機(jī)制建議

圖3是移動(dòng)IM重傳性能仿真實(shí)驗(yàn)在測(cè)試消息總數(shù)為1 000時(shí)，針對(duì)消息重傳數(shù)的測(cè)試結(jié)果。目前只進(jìn)行了連接區(qū)間長(zhǎng)度、斷開區(qū)間長(zhǎng)度服從指數(shù)分布時(shí)的仿真實(shí)驗(yàn)，下一步準(zhǔn)備考慮服從泊松分布等更多種類的情況，并使用2.1小節(jié)中的其他分析模型來與實(shí)驗(yàn)結(jié)果進(jìn)行比較驗(yàn)證。

圖3　平均消息重傳數(shù)Fig.3　Average number of message retransmissions

經(jīng)過與前述分析模型的計(jì)算結(jié)果進(jìn)行比較，仿真結(jié)果與分析結(jié)果基本一致，如表1所示。仿真實(shí)驗(yàn)結(jié)果驗(yàn)證了SMR分析模型、蓋革分析模型，以及本文提出的移動(dòng)IM模型對(duì)即時(shí)消息重傳過程的描述與分析能力，說明可以進(jìn)一步使用這些分析模型來協(xié)助改進(jìn)移動(dòng)即時(shí)消息重傳機(jī)制。表1中的實(shí)驗(yàn)數(shù)據(jù)也表明移動(dòng)IM模型分析結(jié)果在仿真實(shí)驗(yàn)中更接近于仿真結(jié)果，取得比其他模型更好的分析效果。

表1　比較分析和仿真結(jié)果

表1中的“蓋革分析”是指利用蓋革I型計(jì)數(shù)器模型進(jìn)行分析計(jì)算得到的結(jié)果值，具體使用的模型計(jì)算公式是(1)式。

根據(jù)上述仿真實(shí)驗(yàn)結(jié)果及分析，并結(jié)合Sou等人的分析結(jié)論[8]，我們可以給出一些改進(jìn)移動(dòng)即時(shí)消息重傳機(jī)制的建議。

1)消息重傳間隔取固定值時(shí)的實(shí)驗(yàn)表現(xiàn)略好于重傳間隔服從指數(shù)分布的情況。移動(dòng)IM運(yùn)營商可以根據(jù)這個(gè)分析結(jié)果在制定消息重傳機(jī)制時(shí)，采用一個(gè)固定值來作為移動(dòng)即時(shí)消息重傳時(shí)間間隔。

2)移動(dòng)IM后臺(tái)服務(wù)器可以為每條待發(fā)送的即時(shí)消息指定最大嘗試重傳次數(shù)(通過設(shè)置重傳計(jì)數(shù)器實(shí)現(xiàn))，比如10次(具體最大嘗試次數(shù)可以根據(jù)移動(dòng)IM業(yè)務(wù)運(yùn)營情況進(jìn)行調(diào)整)。仿真實(shí)驗(yàn)結(jié)果說明設(shè)定最大嘗試重傳次數(shù)比不設(shè)定重傳次數(shù)限制取得更高的傳遞效率。

結(jié)合以上建議可以給出一個(gè)具體的移動(dòng)即時(shí)消息重傳改進(jìn)機(jī)制：移動(dòng)IM后臺(tái)服務(wù)器給在線用戶發(fā)送移動(dòng)即時(shí)消息，當(dāng)無線網(wǎng)絡(luò)返回傳送失敗的結(jié)果時(shí)，后臺(tái)服務(wù)器開啟即時(shí)消息重傳過程，具體的重傳策略可以設(shè)置為：每10 s進(jìn)行一次消息重傳，最多嘗試重傳10次，如果消息仍未送達(dá)則做丟棄處理，并向消息發(fā)送者返回傳送失敗提示。其中，移動(dòng)IM重傳時(shí)間間隔和服務(wù)器最大重傳嘗試次數(shù)可以根據(jù)業(yè)務(wù)具體運(yùn)營情況進(jìn)行優(yōu)化調(diào)整。

圖4反映了即時(shí)消息傳輸窗口和即時(shí)消息重傳分布的方差變化對(duì)N的影響。圖中的B表示傳輸窗口長(zhǎng)度基數(shù)，在實(shí)驗(yàn)中取為10。由(13)式可知E[N]跟傳輸窗口均值h一起增大，結(jié)果圖反映了這個(gè)分析結(jié)果，同時(shí)還顯示E[N]隨著重傳分布的方差V的增大而減小。當(dāng)V增大，重傳間隔分布變得更加不規(guī)則時(shí)，會(huì)出現(xiàn)重傳事件分布變得稀疏的情況，這也使得傳輸窗口內(nèi)重傳消息數(shù)減少。

圖4　T和V對(duì)N的影響Fig.4　Effects of T and V on N

實(shí)驗(yàn)結(jié)果顯示，重傳分布的方差變得非常大(重傳分布變得非常不規(guī)則)時(shí)，重傳消息數(shù)會(huì)顯著下降。圖4中，“EXP”表示消息傳遞窗口服從指數(shù)分布，實(shí)驗(yàn)結(jié)果顯示當(dāng)服從指數(shù)分布的傳遞窗口均值與固定傳遞窗口長(zhǎng)度取值相等時(shí)，指數(shù)分布傳遞窗口條件下的E[N]大于固定傳遞窗口條件下的E[N]。這一結(jié)果表明，如果運(yùn)營商想減少即時(shí)消息重傳流量，那么應(yīng)該選用固定傳遞窗口。分析模型計(jì)算結(jié)果表明的即時(shí)消息重傳流量增加的程度可供運(yùn)營商在制定策略時(shí)參考。

4重傳機(jī)制分析

下面分析上文提出的移動(dòng)IM重傳改進(jìn)機(jī)制如何影響移動(dòng)IM消息傳遞的總體服務(wù)質(zhì)量。首先介紹獨(dú)立同分布的中心極限定理。假設(shè)X1,…,Xn為獨(dú)立同分布的隨機(jī)變量，E(Xi)=μ，D(Xi)=σ2，對(duì)任意實(shí)數(shù)x，

當(dāng)n充分大時(shí)，

并且對(duì)任意實(shí)數(shù)x1,x2(x1≤x2)，

(15)

由3.1節(jié)重傳實(shí)驗(yàn)輸入?yún)?shù)和(6)式可知，M=8時(shí)，p≈0.017，M=10時(shí)，p≈0.007 35(M=10是上文建議的消息重傳改進(jìn)機(jī)制里預(yù)設(shè)的消息最大嘗試重傳數(shù))。

下面來分析一下消息重傳失敗概率對(duì)消息傳遞失敗總概率的影響。假設(shè)移動(dòng)IM后臺(tái)服務(wù)器要傳遞106條消息，設(shè)

i=1,2,…,106

假設(shè)每條消息初次傳遞失敗的概率為0.01，經(jīng)過重新傳遞后還是失敗的概率為0.01，由于Xi和Yi獨(dú)立同分布，所以Xi～B(1,0.01)，由全概率公式可以推出

0.01×0.01=0.000 1

即Yi～B(1,0.000 1)，同時(shí)

(16)

將(16)式代入(15)式得

上述結(jié)果表示106條移動(dòng)IM消息經(jīng)過初次傳遞和后續(xù)可能發(fā)生的消息重傳過程后，消息傳遞失敗總數(shù)小于等于120條的概率是0.977 2?，F(xiàn)在考慮消息重傳失敗概率改變后對(duì)傳遞失敗總概率的影響。假設(shè)消息重傳失敗概率變?yōu)?.011，則

0.01×0.011=

0.000 11

即Yi～B(1,0.000 11)，同時(shí)

(17)

將(17)式代入(15)式得

上述結(jié)果表示106條即時(shí)消息經(jīng)過初次傳遞和后續(xù)可能發(fā)生的消息重傳過程后，消息傳遞失敗總數(shù)小于等于120條的概率是0.971 3。依據(jù)上述方法可以計(jì)算出當(dāng)消息重傳失敗概率變?yōu)?.015后，106條即時(shí)消息經(jīng)過初次傳遞和消息重傳兩個(gè)過程后，失敗總數(shù)小于等于120條的概率是0.948 4。上述計(jì)算結(jié)果對(duì)比情況如表2所示。

表 2　消息傳遞失敗概率分析

表2中，“失敗總數(shù)達(dá)標(biāo)的概率”是指106條即時(shí)消息經(jīng)過初次傳遞和可能的消息重傳過程后，失敗總數(shù)小于等于120條的概率。通過觀察表2中所列數(shù)據(jù)可以發(fā)現(xiàn)，移動(dòng)即時(shí)消息傳遞失敗總次數(shù)隨著重傳失敗概率的增大而增加。

移動(dòng)IM業(yè)務(wù)運(yùn)營商關(guān)心和需要控制的是即時(shí)消息傳遞過程中產(chǎn)生的傳遞失敗概率(等同于一百萬條即時(shí)消息的傳遞失敗總數(shù))。這個(gè)重要指標(biāo)取決于兩個(gè)因素：消息初次傳遞失敗概率和消息重傳失敗概率。本文研究分析的是消息重傳失敗概率，借助前面已經(jīng)給出的分析模型及其對(duì)應(yīng)的計(jì)算公式，移動(dòng)IM運(yùn)營商可以通過采取必要措施來使模型參數(shù)取值改變，以達(dá)到調(diào)節(jié)消息重傳失敗概率的目的，進(jìn)而達(dá)到控制總體消息傳遞失敗概率的最終目標(biāo)。消息重傳失敗概率分析模型中包含3個(gè)重要參數(shù)：連接區(qū)間長(zhǎng)度均值、斷開區(qū)間長(zhǎng)度均值、消息重傳間隔均值，其中取值容易改變的參數(shù)是消息重傳間隔均值，移動(dòng)IM運(yùn)營商可以通過改變它的具體取值來達(dá)到控制移動(dòng)IM消息傳遞總體服務(wù)質(zhì)量的最終目標(biāo)。

5結(jié)論

在無線環(huán)境中，如果用戶所處位置網(wǎng)絡(luò)狀況不好或處于高速移動(dòng)中，將會(huì)使移動(dòng)IM服務(wù)器傳遞消息失敗次數(shù)大大提高，從而使得重傳頻率非常高。由于無線網(wǎng)絡(luò)的一些特點(diǎn)，移動(dòng)IM消息重傳代價(jià)將變得很高。本文提出一種新的移動(dòng)IM即時(shí)消息重傳模型，并結(jié)合使用同類型的模型對(duì)移動(dòng)IM消息重傳過程進(jìn)行建模分析。根據(jù)建模分析及仿真實(shí)驗(yàn)結(jié)果提出一種移動(dòng)IM消息重傳改進(jìn)機(jī)制應(yīng)對(duì)用戶經(jīng)常掉線等情況。仿真實(shí)驗(yàn)證明了改進(jìn)機(jī)制能減少消息重傳次數(shù)，同時(shí)又不顯著增加系統(tǒng)負(fù)荷和即時(shí)消息傳遞總時(shí)間。本文最后分析了重傳改進(jìn)機(jī)制對(duì)移動(dòng)IM消息傳遞服務(wù)質(zhì)量的影響，并給出控制總體服務(wù)質(zhì)量的方法建議。

參考文獻(xiàn)：

[1]Network Working Group. RFC3920: Extensible Messaging and Presence Protocol (XMPP): Core[S]. Reston, USA: IETF, 2004.

[2]Network Working Group. RFC3921: Extensible Messaging and Presence Protocol (XMPP): Instant Messaging and Presence[S]. Reston, USA: IETF, 2004.

[3]LEAVITT N. Instant Messaging: A New Target for Hackers[J]. Computer, 2005, 38(7): 20-23.

[4]Network Working Group. RFC6120: Extensible Messaging and Presence Protocol (XMPP): Core[S]. Reston, USA: IETF, 2011.

[5]Network Working Group. RFC6121: Extensible Messaging and Presence Protocol (XMPP): Instant Messaging and Presence[S]. Reston, USA: IETF, 2011.

[6]SAINT A P. XMPP: Lessons Learned From Ten Years of XML Messaging[J]. IEEE Communications Magazine, 2009, 47(4): 92-96.

[7]SAINT A P, SMITH K, TRONCON R. XMPP: The Definitive Guide[M]. Sebastopol, CA: O’Reilly Media, 2009: 31-44.

[8]SOU S I, LIN Y B, LUO C L. Cost Analysis of Short Message Retransmissions[J]. IEEE Transactions on Mobile Computing. 2010, 9(2): 215-225.

[9]KARLIN S , TAYLOR M H. 隨機(jī)過程初級(jí)教程[M]. 北京：人民郵電出版社, 2007: 149-173.

KARLIN S， TAYLOR M H. A First Course in Stochastic Processes[M]. Beijing:People Post Press, 2007: 149-173.

[10] CHAKRABORTY S. 基于蜂窩系統(tǒng)的IMS——融合電信領(lǐng)域的VoIP演進(jìn)[M]. 北京：機(jī)械工業(yè)出版社, 2009: 280-309.

CHAKRABORTY S. IMS Multimedia Telephony over Cellular Systems VoIP Evolution in a Converged Telecommunication World[M]. Beijing:Machinery Industry Press, 2009: 280-309.

[11] XSF. Xep-0203: Delayed Delivery[EB/OL].[2011-03-09]. http://xmpp.org/extensions/xep-0203.html.

[12] CAMARILLO G,GARCIA-MARTIN M A. Instant Messaging On the Internet[M]. Hoboken, USA: John Wiley & Sons, 2008: 453-476.

[13] XSF. Xep-0045: Multi-User Chat[EB/OL].[2011-03-09]. http://xmpp.org/extensions/xep-0045.html.

An improved message retransmission mechanism of mobile instant messaging

GAO Yunxiang1, WANG Jianxiong2, XIAO Chuangbai3

(1. IT Department, China Information Technology Designing & Consulting Institute Ltd., Beijing 100048, P.R.China;2. College of Computer Science, Chongqing University, Chongqing 400044, P.R.China;3. College of Computer Science, Beijing University of Technology, Beijing 100124, P.R.China)

Abstract:Frequent instant message retransmissions significantly increase server load and network traffic. We analyze the message retransmission process, define the stochastic events, do the timing analysis, and propose an analytic model to investigate the performance of message retransmission by update theory of stochastic processes. Simulation results show that average message retransmissions is 1.22 times. The result is very close to the retransmission model result, 1.25 times. This comparison illustrates the retransmission model can achieve the better ability to describe the retransmission process than the same type of models. We improve the retransmission mechanism based on the modeling analysis results. The new mechanism takes the fixed retransmission interval and uses the retransmission counter to control the maximum number of attempts. The simulation results show the new mechanism can effectively reduce message traffic without significantly increase message delivery time. Finally, we use the central limit theorem with independent and identical distributions in probability theory to analyze how the retransmission mechanism affects the service quality of mobile instant messaging. We give some optimization suggestions such as adjusting retransmission interval.

Keywords：instant messaging; message retransmission; extensible messaging and presence protocol

DOI：10.3979/j.issn.1673-825X.2016.03.013

收稿日期：2015-04-28

修訂日期：2016-04-12通訊作者：高允翔 gaoyunxiang21@163.com

基金項(xiàng)目：北京市自然科學(xué)基金(4110001)

Foundation Item：The Beijing Natural Science Foundation (4110001)

中圖分類號(hào)：TN929.5; TP393

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1673-825X(2016)03-0360-07

作者簡(jiǎn)介：

高允翔(1979-)，男，河北雄縣人，高級(jí)工程師，博士，研究方向?yàn)橐苿?dòng)即時(shí)通訊、云計(jì)算技術(shù)。E-mail：gaoyunxiang21@163.com。

王健雄(1994-)，男，重慶人，本科生，研究方向?yàn)橐苿?dòng)即時(shí)通訊。E-mail：formaland@sohu.com。

(編輯：張誠)