一种面向移动终端的自适应消息推送策略＊

刘永玲，刘 兀，郭克华

（中南大学信息科学与工程学院，湖南 长沙 410083）

1 引言

随着互联网信息技术的快速发展、网络技术的不断成熟，人们逐渐将互联网作为信息获取的主要平台和途径。传统的消息拉取（Pull）技术已经不能满足目前用户的需求，与之对应的消息推送技术（Push）成为消息获取的新的发展趋势。消息推送方式与消息拉取方式完全不同，消息推送方式是一种由服务器主动将消息推到客户端的技术，其最主要的特点是由服务器主动推送消息，不需要用户不停刷新来检查更新。其优势在于消息的主动性和及时性，可随时将消息推送到用户面前。

与传统PC方式访问互联网相比，移动终端的操作便利性和浏览器的用户体验较差，其对流量和电量敏感以及网络变化频繁，并且在移动网络中，移动终端作为一种通信设备，受到诸多因素的制约。而Push技术，将消息主动推送给用户，无疑会大大地方便用户，降低终端设备上资源的消耗，因此，推送技术在移动终端领域的优越性得到越来越多的重视[1]。比较典型的基于移动终端的推送技术，如：加拿大RIM 公司BlackBerry 手机的Push Mail[2]服务，将传统的电子邮件转移到移动终端上，提供随时随地收发邮件的一种移动邮件业务。Push Mail服务利用移动终端的便携性主动推送消息，使用户在任何地方都能在第一时间接收和处理电子邮件。

基于移动终端的消息推送方式有两类：轮询和长连接。轮询[3]是客户端定期地向服务器发起请求，以检测是否有新的数据，该方式的实现比较简单。长连接是通过客户端软件与服务器间维持一个持续的TCP／IP连接来实现推送。

轮询的工作原理如图1所示，客户端向服务器发送一个请求，服务器立刻响应并断开连接，客户端等待一个时间间隔（Interval）后再次向服务器发送请求。长连接的工作原理如图2所示，客户端在发起一次请求后立即挂起，一直到服务器端有更新时，服务器主动推送消息到客户端，客户端与服务器端的连接永不关闭，直到其中一方发送“关闭连接”的消息或有超时或网络错误。

Figure 1 Principle of the polling图1 轮询工作原理

Figure 2 Principle of long connection图2 长连接工作原理

轮询方式中客户端设置Interval值越大，轮询的频率越慢。如果轮询的频率过慢，可能导致获取的消息已经过时或数据丢失[4]；如果轮询的频率过快，过于频繁地建立和关闭连接、分配系统资源，将耗费服务器大量的CPU 时间和内存资源，同时也会耗费手机电量和流量，尤其在服务器无更新数据时，轮询也会消耗较多无意义的流量和电量。长连接方式采用与服务器保持一个持久的长连接，客户端采用心跳方式保持该IP 连接，可以解决由轮询带来的性能问题。

轮询是客户端定期与服务器建立一次连接，接收响应后断开连接，因此占用服务器的资源较少，在非共振现象（所有客户端同一时刻请求服务器）时，轮询对服务器的内存要求较低，节省服务器资源。轮询适合于事件频率固定、实时性要求低的场景。长连接方式中服务器与客户端保持较长时间的连接，会占用服务器端的资源，随着连接数增加，服务器的压力增大，可能会导致服务器崩溃。与服务器保持长久的连接，将耗费大量的手机电量，同时长连接服务与手机的操作系统类型有关，因此一种服务需要做多次开发。现流行的基于移动终端的长连接推送方式有苹果的APNS（Apple Push Notification Service）服务[5]、微软的 Windows Phone Push Notifications[6]、RIM 的Push Mail[2]、Google的GCM 服务[7]（第二代的G2DM）以及IBM 的MQTT 协议[8～10]等。

两类推送方式在消息实时性方面，长连接方式优于轮询方式；在消耗移动终端电量方面，长连接方式高于轮询方式；在消耗网络流量方面，长连接方式低于轮询方式；在移动终端操作系统多样性方面，轮询方式支持移动终端操作系统多样性，而长连接方式一种服务需要多次开发。长连接方式和轮询方式各有优缺点，本文将长连接方式和轮询方式结合[11～13]，分析移动终端的运行参数，采用本文设计的自适应调度算法为移动终端动态分配推送方式，在适应移动终端多样性的同时，不仅降低了移动终端的耗电量，节省了网络流量，而且还保证了消息实时性，提高了消息推送的服务质量。

2 自适应消息推送策略

自适应消息推送策略的核心是自适应调度算法ASA（Adaptive Scheduling Algorithm）[14]。该算法在用户向服务器发送连接请求时，获取移动终端的运行参数，分析参数，根据分析结果为移动终端分配推送方式；当用户刷新时，重新获取运行参数，然后分析参数，根据分析结果重新为移动终端分配推送方式。采用动态分配推送方式的推送策略，在电量能够保证移动终端正常运行的前提下，保证了用户更快地获得推送消息，即保证了消息的实时性。

2.1 参数定义

为了方便ASA 算法的描述，特进行如下定义：

定义1 支持的操作系统集合L-S：该集合专为长连接方式设计的，用来记录服务器提供的长连接服务支持的操作系统类型，即L-S＝｛L-s1，L-s2，L-s3，…，L-si，…，L-sn｝，其中｛L-si｜L-si＝0或L-si＝1，L-si＝1表示长连接服务支持该类型的操作系统｝。

定义2 长连接集合Conn：客户端请求连接时，服务器创建的长连接集合，即Conn＝｛c1，c2，c3，…，ci，…，cn｝，其中｛ci｜ci＝0或ci＝1｝。

定义3 最大连接数Nmax：服务器支持的最大长连接数。

定义4 已用连接数Nu：服务器正在保持的长连接数，即集合Conn中元素值为1的元素个数。

定义5 轮询请求周期T：客户端第一次轮询结束到第二次轮询开始所用的时间。

定义6 推送调度阈值Pt：服务器保持的长连接数达到Pt时，后来的连接请求建立轮询方式，Pt是长连接数目，算法中设置Pt的值为 0.66 N，即向上取整[15]。

定义7 非空轮询：客户端与服务器建立轮询方式，一次轮询中客户端请求获取的数据不为空。

定义8 非空轮询阈值Qt：当最近t时间内连续x 次非空轮询消耗的流量不小于t 时间内长连接方式消耗的流量，取x 的最小值记为Qt，其中t＝x＊T，根据实验数据，算法中设置Qt的值为5。

定义9 非空轮询集合Q1（t）：客户端在t时间内连续非空轮询的次数。

定义10 空轮询集合Q0（t）：客户端在t时间内连续空轮询的次数。

定义11 电量阈值Et：能保证一种推送方式正常运行1小时的电量。长连接方式的电量阈值能保证长连接方式正常运行1小时，记为Et（L）。轮询方式的电量阈值能保证轮询方式正常运行1小时的电量，记为Et（P）。根据实验数据，算法中设置Et（L）的值为20%，设置Et（P）的值为10%。

定义12 电池电量Er：移动终端的电池剩余的电量，以电量百分比计算。

2.2 自适应调度算法ASA

ASA 算法是从消息的实时性、流量的消耗量、电量的消耗量以及支持的操作系统类型四个方面考虑，以使自适应消息推送策略提供的推送服务达到消息实时性高于轮询方式、消耗流量低于长连接方式、消耗电量低于轮询方式、支持移动终端操作系统多样性的目的。

ASA 算法中服务器在用户初次登录或用户刷新时分配推送方式，如果移动终端的运行参数符合长连接方式，则长连接方式为首选推送方式，以保证消息的实时性。算法的具体流程如图3所示。

Figure 3 ASA algorithm flowchart图3 ASA 算法流程图

用户初次登录，客户端向服务器发送连接请求，如果同时满足以下三个条件：L-si＝1，Nu＜Pt，且Er＞Et（L），则为用户分配长连接推送方式，否则分配轮询方式。当用户刷新时，若采用长连接方式且Er＜Et（P），则长连接方式调度为轮询方式；若采用轮询方式且同时满足以下四个条件：L-si＝1，Nu＜Pt，Er＞Et（L），Q1（t）≥Qt，则轮询方式调度为长连接方式；若采用轮询方式且Q0（t）≥Qt，则将T 调整为2T。

3 性能评估参数模型

性能评估函数F（R，F，E，S）是基于移动终端接收到消息的实时性（用R 表示）、消耗的流量（用F 表示）、消耗的电量（用E 表示）以及移动终端的操作系统类型（用S 表示）等四方面来设计的。

3.1 消息实时性

3.2 流量消耗

流量消耗是通过测试单位时间内平均消耗的流量来判断的。本文以分钟为单位时间，通过测试N 个小时中消耗的流量，每隔10分钟记录一次流量消耗值，然后求每分钟平均消耗的流量。F 的评估模型可以表示为：

其中，fi表示第i个样本在ti时间内消耗的流量，单位为KB。

由于轮询方式和长连接方式耗费的流量不同，因此客户端采用本文提出的自适应推送方式，在相同时间中接收等量的消息消耗的流量会不同。为了保证性能评估的准确性，本文在测试流量时采用多次测试一部手机从固定的电量至电量耗尽为止的测试方式，记录每10分钟耗费的流量，然后求出每分钟平均消耗的流量，精确到小数点后两位。

3.3 电量消耗

电量消耗是测试一部手机从固定电量到电量耗尽所用的时间tt（单位为分钟）来判断的。tt越大则耗费的电量越少。E 的评估模型可以表示为：

其中，A 为常量。

在ASA 算法中触发推送方式调度转换的因素之一是移动终端的电量，采用长连接方式的客户端，在移动终端电量低于10%后将转为轮询方式。为了保证性能评估的准确性，本文在测试电量时采用多次测试一部手机从某一固定电量（即为A 的值）至0%电量所用的时间（单位为分钟），然后求平均值即为tt的值。

3.4 移动终端多样性

移动终端多样性是指移动终端操作系统多样性，是通过测试服务器可以支持的移动终端操作系统类型种类来判断的。长连接方式与移动终端的操作系统类型有关，一种服务需要多次开发。如果服务器只提供长连接服务，则不支持新型的移动终端操作系统。而本文提供的自适应推送方式，将轮询方式和长连接方式结合，新型操作系统的移动终端可以采用轮询方式接收推送消息。S 的评估模型可以表示为：

3.5 评估参数分析

性能评估参数R、F、E、S 中：R 的值越小，则客户端接收的消息的实时性越好；F 的值越小，则消耗移动终端的流量越少，即节省流量；E 的值越小，则消耗移动终端的电量越少，能保证移动终端正常工作的时间越长；S 的值越大，则服务器支持的移动终端类型越多。

在理论上，本文设计的自适应推送方式的消息实时性与长连接方式接近，消耗移动终端的流量不高于轮询方式，保证移动终端正常使用的时间大于长连接方式，支持的移动终端类型与轮询方式相同。

4 实验结果

为验证本文提出的自适应消息推送策略，本文通过消息推送平台来验证该策略的可行性，一方面与采用轮询方式的消息推送平台做比较分析，另一方面与采用长连接方式的消息推送平台做比较分析。

4.1 原型系统设计

本文选择三星9100（系统版本Android 4.0）、HT-I710（系统版本Android 2.3.5）、iPhone4S和Nokia 510（WindowsPhone 7.5）为实验移动终端平台，在服务器上提供自适应消息推送服务。为了保证实验与真实场景接近，服务器推送消息时间随机生成。用户在移动终端上可以完成三个基本操作：与服务器建立连接、接收消息和断开连接。原型系统结构如图4所示。

用户启动客户端后，客户端向服务器发送连接请求，同时将手机的IP 地址、电池剩余电量、操作系统类型等参数传给服务器，服务器根据以上参数提供合适的推送方式。

Figure 4 Prototype structure图4 原型结构图

4.2 实验结果比较分析

原型系统的实验在消息实时性、流量消耗、电量消耗及移动终端多样性四个方面比较轮询方式、长连接方式和ASA 方式。轮询方式中，T 取值为5秒，测试电量消耗时取A＝30%，测试延迟和流量消耗时取N＝1。

Table 1 Average delay schedule表1 平均延迟时间表 ms

流量消耗比较：由表2 可知，F （轮询）＞F（ASA）＞F（长连接），ASA 推送方式消耗的流量低于轮询方式。

Table 2 Flow consumption表2 流量消耗表 KB

电量消耗比较：由表3可知，E（长连接）＞E（ASA）＞E （轮询），ASA 推送方式消耗的电量低于长连接方式。

Table 3 Power consumption表3 电量消耗表 min

移动终端多样性比较：ASA 方式和轮询方式支持各种类型的操作类型，长连接方式只支持提供相应服务的操作系统。

5 结束语

本文提出了一种面向移动终端的自适应消息推送策略，该策略分析移动终端的运行参数（操作系统类型、电量、推送方式等），为终端动态分配消息推送方式（长连接方式或轮询方式）。原型系统实验表明，该策略在适应终端多样性的同时，与长连接方式相比降低了移动终端的耗电量，与轮询方式相比节省了网络流量，并保证了消息的实时性。

ASA 方式消耗的流量比长连接方式消耗的流量多，在未来工作中将改进ASA 算法，以节省更多的网络流量。

[1]Kim Y S，Lee J W，Park S R，et al.Mobile advertisement system using data push scheduling based on user preference[C]∥Proc of Wireless Telecommunications Symposium，2009：1-5.

[2]Ben Letaifa A，Tabbane S.Push mail：A real case of IP con-vergence in NGN networks[C]∥Proc of the 70th IEEE Vehicular Technology Conference Fall（VTC 2009-Fall），2009：1-5.

[3]Boon M A A，Van der Mei R D，Winands E M M.Applications of polling systems[J].Surveys in Operations Research and Management Science，2011，16（2）：67-82.

[4]Van der Mei R D，Winands E M M.A note on polling models with renewal arrivals and nonzero switch-over times[J].Operations Research Letters，2008，36（4）：500-505.

[5]Bell K M，Bleau D N，Davey J T.Push notification service：U.S.Patent 8，064，896[P].2011-11-22.

[6]Microsoft：Push notications for windows phone[EB／OL].[2011-10-01].http：／／msdn.microsoft.com／en-us／library／ff402537（v＝VS.92）.aspx.

[7]Hansen J，Grønli T M，Ghinea G.Towards cloud to device push messaging on Android：Technologies，possibilities and challenges[J].Internatioanl Journal of Communications，Network and System Sciences，2012，5（12）：839-849.

[8]IA92：WBI brokers-Java implementation of WebSphere MQ Telemetry transport[EB／OL].[2003-02-28].http：／／www-01.ibm.com／support／docview.wss？uid＝swg24006006.

[9]Pereira N，Tennina S，Tovar E.Building a microscope for the data center[M]∥Wireless Algorithms，Systems，and Applications.Berlin：Springer，2012：619-630.

[10]Stanford-Clark A J，Wightwick G R.The application of publish／subscribe messaging to environmental，monitoring，and control systems[J].IBM Journal of Research and Development，2010，54（4）：1-7.

[11]Winands E M M.On polling systems with large setups[J].Operations Research Letters，2007，35（5）：584-590.

[12]Winands E M M.Branching-type polling systems with large setups[J].OR Spectrum，2011，33（1）：77-97.

[13]Hsu C F，Liu C Y.An adaptive traffic-aware polling and scheduling algorithm for bluetooth piconets[J].IEEE Transactions on Vehicular Technology，2010，59（3）：1402-1414.

[14]Guan He-qing，Zhang Wen-bo，Wei Jun，et al.An application-aware web service requests scheduling strategy[J].Chinese Journal of Computers，2006，2.（7）：1189-1198.（in Chinese）

[15]Mei Rui.The research on cross-server messages publish and push mechanism[D].Wuhan：Huazhong University of Science and Technology，2011.（in Chinese）

附中文参考文献

[14]官荷卿，张文博，魏峻，等.一种应用敏感的Web 服务请求调度策略[J].计算机学报，2006，2.（7）：1189-1198.

[15]梅蕊.跨服务器消息发布与推送机制的研究[D].武汉：华中科技大学，2011.