一种移动即时通讯消息重传改进机制

高允翔，王健雄，肖创柏

(1. 中讯邮电咨询设计院有限公司 信息技术部，北京 100048; 2. 重庆大学 计算机学院，重庆 400044;3. 北京工业大学 计算机学院，北京 100124)



一种移动即时通讯消息重传改进机制

高允翔1，王健雄2，肖创柏3

(1. 中讯邮电咨询设计院有限公司 信息技术部，北京 100048; 2. 重庆大学 计算机学院，重庆 400044;3. 北京工业大学 计算机学院，北京 100124)

摘要：为应对移动即时通讯(instant messaging，IM)消息频繁重传给服务器和网络造成的负荷，基于随机过程的更新理论，提出移动即时通讯消息重传模型来研究消息重传性能。仿真实验结果表明，平均消息重传数为1.22次，与重传模型分析结果1.25次非常接近，取得比同类型模型更好的描述能力。基于建模分析结果提出一种移动即时通讯消息重传改进机制，采用固定重传间隔，设置重传计数器控制最大尝试次数，相关仿真结果表明该机制能有效减少消息重传次数，同时又不显著增加消息传递时间。最后利用概率论中独立同分布的中心极限定理分析消息重传机制如何影响移动即时通讯消息传递的总体服务质量，并给出调整重传间隔参数等服务优化建议。

关键词：即时通讯；消息重传；可扩展通讯和表示协议(XMPP)

0引言

即时通讯(instant messaging， IM)已经成为继电话、电子邮件之后又一流行的通信手段。近年来，随着移动网络和移动终端技术的快速发展，IM技术在移动平台上获得了大规模的应用，微信就是最成功的移动互联网应用案例。移动网络环境相比因特网有一些新的特点，使得原有技术必须得到改进才能满足移动用户需求。当前的IM协议主要规定了通信基本规则，并未对一些具体的性能处理算法进行详细描述，而这些算法是保障应用成功的关键因素。业界技术领先的移动IM应用在这方面做了很多工作，比如，腾讯在IM领域多次荣获专利大奖，近年来累计取得数千项专利。但是这些专利内容大多还未公开，所以本文研究工作的相关基础只有少数研究机构的一些科研成果。

本文选取移动IM中的标准解决方案之一可扩展通讯和表示协议(extensible messaging and presence protocol，XMPP)[1-7]作为研究对象，对移动IM中消息重传这个关键技术进行深入的建模研究，提出有针对性的改进方案，并借助相关仿真实验证明该方案的有效性。

目前相关研究领域已经有一些关于消息重传的分析模型，比如短消息重传(short message retransmission，SMR)模型是用来分析短消息重传过程的[8]。盖革I型计数器[9]是一种记录脉冲的科学仪器，盖革模型对信号记录过程进行分析。但是，截止目前还没有描述分析移动IM即时消息传递过程的数学模型，本文尝试建立这样的分析模型，为移动IM性能建模分析相关工作的开展打下一定的基础。随后进行的仿真实验将验证本文提出的移动IM即时消息重传模型的有效性。

1消息重传

由于移动用户行为特点和无线环境下时常出现掉线等情况，移动即时通讯消息(简称移动即时消息)时常会出现初次传递失败的情况。假如这种情况出现，移动IM后台服务器应该间隔一段时间后重新传递该条即时消息[8]。无线连接建立时间一般很短，而且由于高峰值比特率等特性，传输移动即时消息仅需几毫秒，因此，发送这些消息的信道利用率一般非常低。但是如果这个移动用户所处位置无线网络信号不好，或者处于高速移动之中，就会经常发生移动即时消息传递失败的情况，从而频繁触发消息重传机制。由于无线环境中的这些特点，消息频繁重传给服务器和网络造成较大负荷[10]。所以，需要考虑制定一种移动即时消息重传机制，以保证消息尽快送达，同时又尽可能减少重传的代价。

移动即时消息重传机制具体指：移动IM后台服务器准备给移动用户发送消息时，由于接收用户的无线信号质量欠佳，导致即时消息不能通过一次传递而成功，需要重新传递这些即时消息，并制定相应的重传机制来保证消息重传的效率。这种重传机制一般需要规定消息重传的频率、两次传递之间的时间间隔等重要参数。另外，需要特别说明的一个情况是，从消息接收者的角度来看，存在2种消息重传情况。

情况1消息接收用户上线，相应的用户状态转为“在线”，移动IM后台服务器向其发送即时消息(属于延迟发送)。

情况2消息接收用户当前在线，移动IM后台服务器可以向接收者发送各种类型的移动即时消息。

下面介绍“情况1”中提到的被延迟发送的即时消息和“情况2”中提到的移动即时消息类型。移动即时通讯业务的关键部件就是消息延迟发送功能[11]。当移动IM用户状态异常，或者不在线时，移动即时消息将被延迟发送。此时，移动即时消息被存储在移动IM后台服务器中，延迟一段时间后被重新发送给接收用户[12]。对移动IM用户群内的会话消息的处理方法也与此类似[13]。本章讨论的移动即时消息重传过程中涉及的“消息”指广义范畴内的移动即时消息，包含所有主要的类别，如会话消息、状态消息、控制消息等。

当前的XMPP版本[4-5]并没有对无线环境下的即时消息重新传递过程做出特别规定，所以采用XMPP的移动IM服务中涉及的消息重传机制是：移动IM后台服务器向用户发出即时消息后，一旦收到无线网络返回传递失败的错误提示后，立即触发消息重传过程。通过上面对基于无线网络进行即时消息传递过程特点的分析，可以推知这种立即重传的机制将会引发很高的传递代价，需要我们认真分析移动即时消息重传过程，制定效率更高的移动即时消息重传机制。

2有关消息重传的分析模型

2.1盖革计数器模型

计数器是一种记录脉冲的科学仪器。计数器存在功能不完善的情况，在进行调整的时间段(闭锁时间)内无法记录到达的信号。计数器模型根据这种闭锁情况的不同可以分为2种类型，下面简要介绍对分析移动IM消息重传过程有帮助的盖革I型计数器模型[9]。

假设待记录信号到达计数器的过程是一个更新过程(参见随机过程的更新理论[9])，间隔为Xn,n≥1，服从分布F。计数器闭锁时间记为Yn,n≥1，服从分布G，并且与信号到达过程互相独立。一个信号在时刻0的到达事件使得盖革计数器产生一段闭锁时间Y1。假设Zn,n≥1表示计数过程(这也构成了一个更新过程)。

在计数器长时间运行后，单位时间内平均到达1/E[Xi]个信号，平均计数1/E[Zi]次。所以，信号发送总数与记录成功数的比例是

(1)

如果信号到达过程是一个泊松过程，信号到达间隔服从指数分布，则

(2)

逐次计数同上面描述一样，形成另一个更新过程，并且在(0,t)内计数次数是渐进正态的。

盖革I型计数器非常类似于准备接收移动即时消息的手机终端，计数器的闭锁期类似于手机终端的无服务期，到达计数器的信号类似于移动IM后台服务器发给手机终端的即时消息。如果从上述角度出发进行分析，移动IM重传过程可以借助盖革I型计数器模型来进行分析。下面将在分析和实验过程中参考盖革计数器模型的分析值。

2.2SMR模型

SMR模型是用来分析移动短消息重传过程的[8]，移动短消息传递过程与移动IM消息传递过程具有很大的相似性，与这两种业务分别关联的用户情况、网络情况，以及消息传递情况大致相似。基于这种相似性，本文借助SMR模型进行移动IM重传过程分析。首先，介绍一下SMR模型中使用的参数：N表示消息重传数，M表示消息最大重传数，T表示消息传递时间，p表示消息重传失败概率，c表示连接区间长度均值，d表示断开区间长度均值，1/λ表示重传间隔均值。

SMR模型的输出项是平均消息重传数E[N]、平均消息传递时间E[T]、消息重传失败概率p。为了使分析模型输出结果表达式更加清晰简洁，本文进行如下假设

k=c+d+λcd，

(3)

下面依次给出SMR分析模型3个输出项的表达式，其中，平均消息重传数为

(4)

平均消息传递时间为

(5)

重传失败概率为

(6)

2.3移动IM即时消息重传模型

图1是移动IM即时消息重传时序图。移动终端在t0，t4时刻连接到移动网络处于连线状态，其中，Ci=t1-t0，Ci+1=t6-t4。移动终端在t1，t6时刻断开与移动网络的连接处于掉线状态，其中，Di=t4-t1，Di+1=t7-t6。移动IM即时消息重传事件发生在t2，t3，t5时刻。其中，后台服务器在t2，t3时刻发送的即时消息，由于移动终端处于断网状态，传送失败，所以继续触发即时消息的下一次重传。在t5时刻发送的即时消息，由于移动终端处于连网状态，传送成功，一次即时消息传递过程结束。Ti=t7-t0表示一次即时消息传递过程，也代表一次传输时间窗口。图例中传输时间窗口内共包含3次即时消息重传事件(3次重传事件的时间间隔分别为Ri=t2-t0，Ri+1=t3-t2，Ri+2=t5-t3)，所以在[t0,t7]，N=3(N表示消息重传数)。

图1　移动IM即时消息重传时序图Fig.1　Timing diagram for message retransmission

假设移动IM即时消息重新传递的过程是一个更新过程，间隔为Ri,i≥1，服从分布E1；移动终端连线区间记为Ci,i≥1，服从分布E2；移动终端掉线区间记为Di,i≥1，服从分布E3；移动IM即时消息成功发送的计数过程记为Si,i≥1，服从分布E4。上述的几个更新过程之间相互独立。

假设T表示消息传输时间窗口，N表示一个传输时间窗口内的消息重传数，p表示在一个传输时间窗口内消息传递失败概率，1/χ=E[Ci]表示连接区间长度均值，1/δ=E[Di]表示断开区间长度均值，1/λ=E[Ri]表示重传间隔均值，1/γ=E[T]表示传输时间窗口长度均值，1/η=E[Si]表示成功传递间隔均值。

一个即时消息传输时间窗口标志着一次更新循环。由随机过程的更新理论可知

(7)

假设关于N的更新函数为m(t)=E[N]，对(7)式两边取拉普拉斯变化后得

(8)

由拉普拉斯变换卷积性质可得

(9)

假设即时消息重传分布服从均值为u，方差为V的伽玛分布，其拉普拉斯变化为

(10)

代入(9)式可得

(11)

为考察重传分布属性对重传模型的影响，假设V=u2(仿真实验会考察其它比例关系对结果的影响)，代入(11)式可得

(12)

取拉普拉斯反变换得

(13)

在移动IM后台服务器运行一段时间后，单位时间内平均传送λ个即时消息，平均成功传送η个即时消息。所以，移动IM即时消息发送总数与发送成功数的比例是λ/η。

由于移动IM后台服务器成功传送即时消息依赖于移动终端连线区间长度，移动终端在线区间越长，后台服务器给移动终端传递即时消息成功概率也越大；反之，移动终端在线区间越短，后台服务器给移动终端传递即时消息失败概率也越大。所以，移动终端连线区间长度均值与移动IM后台服务器传送即时消息平均成功数具有同方向、同比例变化关系，所以有E[N]=λ/χ。

假设随机向量(Ci,Di),i≥1，独立同分布，因此，随机变量序列{Ci}与{Di}都是独立同分布的，设F是Ci+Di,i≥1的分布，Ci与Di随着移动终端连线、掉线的动作进行交替，可知它们构成一个交替更新过程。由交替更新定理可知

(14)

3仿真实验及结果分析

3.1实验设计

移动IM重传性能实验环境为一台IBM System x3400 M3服务器，Xeon E5506 2.13 GHz、四线程CPU，操作系统为Windows Server 2003。本文用C++实现了仿真程序，模拟消息达到、用户在线状态改变等随机事件，验证上述分析模型的有效性。移动IM重传实验设计方案中的3个关键点是：

1)按照特定分布规律产生消息到达、消息重传、手机终端状态改变这3种事件；

2)设计一个事件队列以便让上述3种随机事件按预设时间戳的先后顺序产生；

3)通过间隔时间随机数组来生成3种事件的预设时间戳。

移动IM重传性能实验需要的输入参数如下：连接区间长度分布采用服从指数分布的测试数据，连接区间长度均值取17，连接区间长度样本数取1 000；断开区间长度分布采用服从指数分布的测试数据，断开区间长度均值取15，断开区间长度样本数取1 000；重传间隔分布取固定值，而不服从任何一种随机分布，重传间隔均值取14，重传间隔样本数取1，访问事件总数取1 000；移动IM重传性能实验流程如图2所示。

图2　消息重传性能实验流程图Fig.2　Experimental flow chart about message retransmission

3.2结果分析及重传机制建议

图3是移动IM重传性能仿真实验在测试消息总数为1 000时，针对消息重传数的测试结果。目前只进行了连接区间长度、断开区间长度服从指数分布时的仿真实验，下一步准备考虑服从泊松分布等更多种类的情况，并使用2.1小节中的其他分析模型来与实验结果进行比较验证。

图3　平均消息重传数Fig.3　Average number of message retransmissions

经过与前述分析模型的计算结果进行比较，仿真结果与分析结果基本一致，如表1所示。仿真实验结果验证了SMR分析模型、盖革分析模型，以及本文提出的移动IM模型对即时消息重传过程的描述与分析能力，说明可以进一步使用这些分析模型来协助改进移动即时消息重传机制。表1中的实验数据也表明移动IM模型分析结果在仿真实验中更接近于仿真结果，取得比其他模型更好的分析效果。

表1　比较分析和仿真结果

表1中的“盖革分析”是指利用盖革I型计数器模型进行分析计算得到的结果值，具体使用的模型计算公式是(1)式。

根据上述仿真实验结果及分析，并结合Sou等人的分析结论[8]，我们可以给出一些改进移动即时消息重传机制的建议。

1)消息重传间隔取固定值时的实验表现略好于重传间隔服从指数分布的情况。移动IM运营商可以根据这个分析结果在制定消息重传机制时，采用一个固定值来作为移动即时消息重传时间间隔。

2)移动IM后台服务器可以为每条待发送的即时消息指定最大尝试重传次数(通过设置重传计数器实现)，比如10次(具体最大尝试次数可以根据移动IM业务运营情况进行调整)。仿真实验结果说明设定最大尝试重传次数比不设定重传次数限制取得更高的传递效率。

结合以上建议可以给出一个具体的移动即时消息重传改进机制：移动IM后台服务器给在线用户发送移动即时消息，当无线网络返回传送失败的结果时，后台服务器开启即时消息重传过程，具体的重传策略可以设置为：每10 s进行一次消息重传，最多尝试重传10次，如果消息仍未送达则做丢弃处理，并向消息发送者返回传送失败提示。其中，移动IM重传时间间隔和服务器最大重传尝试次数可以根据业务具体运营情况进行优化调整。

图4反映了即时消息传输窗口和即时消息重传分布的方差变化对N的影响。图中的B表示传输窗口长度基数，在实验中取为10。由(13)式可知E[N]跟传输窗口均值h一起增大，结果图反映了这个分析结果，同时还显示E[N]随着重传分布的方差V的增大而减小。当V增大，重传间隔分布变得更加不规则时，会出现重传事件分布变得稀疏的情况，这也使得传输窗口内重传消息数减少。

图4　T和V对N的影响Fig.4　Effects of T and V on N

实验结果显示，重传分布的方差变得非常大(重传分布变得非常不规则)时，重传消息数会显著下降。图4中，“EXP”表示消息传递窗口服从指数分布，实验结果显示当服从指数分布的传递窗口均值与固定传递窗口长度取值相等时，指数分布传递窗口条件下的E[N]大于固定传递窗口条件下的E[N]。这一结果表明，如果运营商想减少即时消息重传流量，那么应该选用固定传递窗口。分析模型计算结果表明的即时消息重传流量增加的程度可供运营商在制定策略时参考。

4重传机制分析

下面分析上文提出的移动IM重传改进机制如何影响移动IM消息传递的总体服务质量。首先介绍独立同分布的中心极限定理。假设X1,…,Xn为独立同分布的随机变量，E(Xi)=μ，D(Xi)=σ2，对任意实数x，

当n充分大时，

并且对任意实数x1,x2(x1≤x2)，

(15)

由3.1节重传实验输入参数和(6)式可知，M=8时，p≈0.017，M=10时，p≈0.007 35(M=10是上文建议的消息重传改进机制里预设的消息最大尝试重传数)。

下面来分析一下消息重传失败概率对消息传递失败总概率的影响。假设移动IM后台服务器要传递106条消息，设

i=1,2,…,106

假设每条消息初次传递失败的概率为0.01，经过重新传递后还是失败的概率为0.01，由于Xi和Yi独立同分布，所以Xi～B(1,0.01)，由全概率公式可以推出

0.01×0.01=0.000 1

即Yi～B(1,0.000 1)，同时

(16)

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

上述结果表示106条移动IM消息经过初次传递和后续可能发生的消息重传过程后，消息传递失败总数小于等于120条的概率是0.977 2。现在考虑消息重传失败概率改变后对传递失败总概率的影响。假设消息重传失败概率变为0.011，则

0.01×0.011=

0.000 11

即Yi～B(1,0.000 11)，同时

(17)

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

上述结果表示106条即时消息经过初次传递和后续可能发生的消息重传过程后，消息传递失败总数小于等于120条的概率是0.971 3。依据上述方法可以计算出当消息重传失败概率变为0.015后，106条即时消息经过初次传递和消息重传两个过程后，失败总数小于等于120条的概率是0.948 4。上述计算结果对比情况如表2所示。

表 2　消息传递失败概率分析

表2中，“失败总数达标的概率”是指106条即时消息经过初次传递和可能的消息重传过程后，失败总数小于等于120条的概率。通过观察表2中所列数据可以发现，移动即时消息传递失败总次数随着重传失败概率的增大而增加。

移动IM业务运营商关心和需要控制的是即时消息传递过程中产生的传递失败概率(等同于一百万条即时消息的传递失败总数)。这个重要指标取决于两个因素：消息初次传递失败概率和消息重传失败概率。本文研究分析的是消息重传失败概率，借助前面已经给出的分析模型及其对应的计算公式，移动IM运营商可以通过采取必要措施来使模型参数取值改变，以达到调节消息重传失败概率的目的，进而达到控制总体消息传递失败概率的最终目标。消息重传失败概率分析模型中包含3个重要参数：连接区间长度均值、断开区间长度均值、消息重传间隔均值，其中取值容易改变的参数是消息重传间隔均值，移动IM运营商可以通过改变它的具体取值来达到控制移动IM消息传递总体服务质量的最终目标。

5结论

在无线环境中，如果用户所处位置网络状况不好或处于高速移动中，将会使移动IM服务器传递消息失败次数大大提高，从而使得重传频率非常高。由于无线网络的一些特点，移动IM消息重传代价将变得很高。本文提出一种新的移动IM即时消息重传模型，并结合使用同类型的模型对移动IM消息重传过程进行建模分析。根据建模分析及仿真实验结果提出一种移动IM消息重传改进机制应对用户经常掉线等情况。仿真实验证明了改进机制能减少消息重传次数，同时又不显著增加系统负荷和即时消息传递总时间。本文最后分析了重传改进机制对移动IM消息传递服务质量的影响，并给出控制总体服务质量的方法建议。

参考文献：

[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. 随机过程初级教程[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. 基于蜂窝系统的IMS——融合电信领域的VoIP演进[M]. 北京：机械工业出版社, 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

基金项目：北京市自然科学基金(4110001)

Foundation Item：The Beijing Natural Science Foundation (4110001)

中图分类号：TN929.5; TP393

文献标志码：A

文章编号：1673-825X(2016)03-0360-07

作者简介：

高允翔(1979-)，男，河北雄县人，高级工程师，博士，研究方向为移动即时通讯、云计算技术。E-mail：gaoyunxiang21@163.com。

王健雄(1994-)，男，重庆人，本科生，研究方向为移动即时通讯。E-mail：formaland@sohu.com。

(编辑：张诚)