一種面向移動終端的自適應消息推送策略＊

劉永玲，劉 兀，郭克華

（中南大學信息科學與工程學院，湖南 長沙 410083）

1 引言

隨著互聯(lián)網(wǎng)信息技術的快速發(fā)展、網(wǎng)絡技術的不斷成熟，人們逐漸將互聯(lián)網(wǎng)作為信息獲取的主要平臺和途徑。傳統(tǒng)的消息拉?。≒ull）技術已經(jīng)不能滿足目前用戶的需求，與之對應的消息推送技術（Push）成為消息獲取的新的發(fā)展趨勢。消息推送方式與消息拉取方式完全不同，消息推送方式是一種由服務器主動將消息推到客戶端的技術，其最主要的特點是由服務器主動推送消息，不需要用戶不停刷新來檢查更新。其優(yōu)勢在于消息的主動性和及時性，可隨時將消息推送到用戶面前。

與傳統(tǒng)PC方式訪問互聯(lián)網(wǎng)相比，移動終端的操作便利性和瀏覽器的用戶體驗較差，其對流量和電量敏感以及網(wǎng)絡變化頻繁，并且在移動網(wǎng)絡中，移動終端作為一種通信設備，受到諸多因素的制約。而Push技術，將消息主動推送給用戶，無疑會大大地方便用戶，降低終端設備上資源的消耗，因此，推送技術在移動終端領域的優(yōu)越性得到越來越多的重視[1]。比較典型的基于移動終端的推送技術，如：加拿大RIM 公司BlackBerry 手機的Push Mail[2]服務，將傳統(tǒng)的電子郵件轉(zhuǎn)移到移動終端上，提供隨時隨地收發(fā)郵件的一種移動郵件業(yè)務。Push Mail服務利用移動終端的便攜性主動推送消息，使用戶在任何地方都能在第一時間接收和處理電子郵件。

基于移動終端的消息推送方式有兩類：輪詢和長連接。輪詢[3]是客戶端定期地向服務器發(fā)起請求，以檢測是否有新的數(shù)據(jù)，該方式的實現(xiàn)比較簡單。長連接是通過客戶端軟件與服務器間維持一個持續(xù)的TCP／IP連接來實現(xiàn)推送。

輪詢的工作原理如圖1所示，客戶端向服務器發(fā)送一個請求，服務器立刻響應并斷開連接，客戶端等待一個時間間隔（Interval）后再次向服務器發(fā)送請求。長連接的工作原理如圖2所示，客戶端在發(fā)起一次請求后立即掛起，一直到服務器端有更新時，服務器主動推送消息到客戶端，客戶端與服務器端的連接永不關閉，直到其中一方發(fā)送“關閉連接”的消息或有超時或網(wǎng)絡錯誤。

Figure 1 Principle of the polling圖1 輪詢工作原理

Figure 2 Principle of long connection圖2 長連接工作原理

輪詢方式中客戶端設置Interval值越大，輪詢的頻率越慢。如果輪詢的頻率過慢，可能導致獲取的消息已經(jīng)過時或數(shù)據(jù)丟失[4]；如果輪詢的頻率過快，過于頻繁地建立和關閉連接、分配系統(tǒng)資源，將耗費服務器大量的CPU 時間和內(nèi)存資源，同時也會耗費手機電量和流量，尤其在服務器無更新數(shù)據(jù)時，輪詢也會消耗較多無意義的流量和電量。長連接方式采用與服務器保持一個持久的長連接，客戶端采用心跳方式保持該IP 連接，可以解決由輪詢帶來的性能問題。

輪詢是客戶端定期與服務器建立一次連接，接收響應后斷開連接，因此占用服務器的資源較少，在非共振現(xiàn)象（所有客戶端同一時刻請求服務器）時，輪詢對服務器的內(nèi)存要求較低，節(jié)省服務器資源。輪詢適合于事件頻率固定、實時性要求低的場景。長連接方式中服務器與客戶端保持較長時間的連接，會占用服務器端的資源，隨著連接數(shù)增加，服務器的壓力增大，可能會導致服務器崩潰。與服務器保持長久的連接，將耗費大量的手機電量，同時長連接服務與手機的操作系統(tǒng)類型有關，因此一種服務需要做多次開發(fā)。現(xiàn)流行的基于移動終端的長連接推送方式有蘋果的APNS（Apple Push Notification Service）服務[5]、微軟的 Windows Phone Push Notifications[6]、RIM 的Push Mail[2]、Google的GCM 服務[7]（第二代的G2DM）以及IBM 的MQTT 協(xié)議[8～10]等。

兩類推送方式在消息實時性方面，長連接方式優(yōu)于輪詢方式；在消耗移動終端電量方面，長連接方式高于輪詢方式；在消耗網(wǎng)絡流量方面，長連接方式低于輪詢方式；在移動終端操作系統(tǒng)多樣性方面，輪詢方式支持移動終端操作系統(tǒng)多樣性，而長連接方式一種服務需要多次開發(fā)。長連接方式和輪詢方式各有優(yōu)缺點，本文將長連接方式和輪詢方式結合[11～13]，分析移動終端的運行參數(shù)，采用本文設計的自適應調(diào)度算法為移動終端動態(tài)分配推送方式，在適應移動終端多樣性的同時，不僅降低了移動終端的耗電量，節(jié)省了網(wǎng)絡流量，而且還保證了消息實時性，提高了消息推送的服務質(zhì)量。

2 自適應消息推送策略

自適應消息推送策略的核心是自適應調(diào)度算法ASA（Adaptive Scheduling Algorithm）[14]。該算法在用戶向服務器發(fā)送連接請求時，獲取移動終端的運行參數(shù)，分析參數(shù)，根據(jù)分析結果為移動終端分配推送方式；當用戶刷新時，重新獲取運行參數(shù)，然后分析參數(shù)，根據(jù)分析結果重新為移動終端分配推送方式。采用動態(tài)分配推送方式的推送策略，在電量能夠保證移動終端正常運行的前提下，保證了用戶更快地獲得推送消息，即保證了消息的實時性。

2.1 參數(shù)定義

為了方便ASA 算法的描述，特進行如下定義：

定義1 支持的操作系統(tǒng)集合L-S：該集合專為長連接方式設計的，用來記錄服務器提供的長連接服務支持的操作系統(tǒng)類型，即L-S＝｛L-s1，L-s2，L-s3，…，L-si，…，L-sn｝，其中｛L-si｜L-si＝0或L-si＝1，L-si＝1表示長連接服務支持該類型的操作系統(tǒng)｝。

定義2 長連接集合Conn：客戶端請求連接時，服務器創(chuàng)建的長連接集合，即Conn＝｛c1，c2，c3，…，ci，…，cn｝，其中｛ci｜ci＝0或ci＝1｝。

定義3 最大連接數(shù)Nmax：服務器支持的最大長連接數(shù)。

定義4 已用連接數(shù)Nu：服務器正在保持的長連接數(shù)，即集合Conn中元素值為1的元素個數(shù)。

定義5 輪詢請求周期T：客戶端第一次輪詢結束到第二次輪詢開始所用的時間。

定義6 推送調(diào)度閾值Pt：服務器保持的長連接數(shù)達到Pt時，后來的連接請求建立輪詢方式，Pt是長連接數(shù)目，算法中設置Pt的值為 0.66 N，即向上取整[15]。

定義7 非空輪詢：客戶端與服務器建立輪詢方式，一次輪詢中客戶端請求獲取的數(shù)據(jù)不為空。

定義8 非空輪詢閾值Qt：當最近t時間內(nèi)連續(xù)x 次非空輪詢消耗的流量不小于t 時間內(nèi)長連接方式消耗的流量，取x 的最小值記為Qt，其中t＝x＊T，根據(jù)實驗數(shù)據(jù)，算法中設置Qt的值為5。

定義9 非空輪詢集合Q1（t）：客戶端在t時間內(nèi)連續(xù)非空輪詢的次數(shù)。

定義10 空輪詢集合Q0（t）：客戶端在t時間內(nèi)連續(xù)空輪詢的次數(shù)。

定義11 電量閾值Et：能保證一種推送方式正常運行1小時的電量。長連接方式的電量閾值能保證長連接方式正常運行1小時，記為Et（L）。輪詢方式的電量閾值能保證輪詢方式正常運行1小時的電量，記為Et（P）。根據(jù)實驗數(shù)據(jù)，算法中設置Et（L）的值為20%，設置Et（P）的值為10%。

定義12 電池電量Er：移動終端的電池剩余的電量，以電量百分比計算。

2.2 自適應調(diào)度算法ASA

ASA 算法是從消息的實時性、流量的消耗量、電量的消耗量以及支持的操作系統(tǒng)類型四個方面考慮，以使自適應消息推送策略提供的推送服務達到消息實時性高于輪詢方式、消耗流量低于長連接方式、消耗電量低于輪詢方式、支持移動終端操作系統(tǒng)多樣性的目的。

ASA 算法中服務器在用戶初次登錄或用戶刷新時分配推送方式，如果移動終端的運行參數(shù)符合長連接方式，則長連接方式為首選推送方式，以保證消息的實時性。算法的具體流程如圖3所示。

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

用戶初次登錄，客戶端向服務器發(fā)送連接請求，如果同時滿足以下三個條件：L-si＝1，Nu＜Pt，且Er＞Et（L），則為用戶分配長連接推送方式，否則分配輪詢方式。當用戶刷新時，若采用長連接方式且Er＜Et（P），則長連接方式調(diào)度為輪詢方式；若采用輪詢方式且同時滿足以下四個條件：L-si＝1，Nu＜Pt，Er＞Et（L），Q1（t）≥Qt，則輪詢方式調(diào)度為長連接方式；若采用輪詢方式且Q0（t）≥Qt，則將T 調(diào)整為2T。

3 性能評估參數(shù)模型

性能評估函數(shù)F（R，F(xiàn)，E，S）是基于移動終端接收到消息的實時性（用R 表示）、消耗的流量（用F 表示）、消耗的電量（用E 表示）以及移動終端的操作系統(tǒng)類型（用S 表示）等四方面來設計的。

3.1 消息實時性

3.2 流量消耗

流量消耗是通過測試單位時間內(nèi)平均消耗的流量來判斷的。本文以分鐘為單位時間，通過測試N 個小時中消耗的流量，每隔10分鐘記錄一次流量消耗值，然后求每分鐘平均消耗的流量。F 的評估模型可以表示為：

其中，fi表示第i個樣本在ti時間內(nèi)消耗的流量，單位為KB。

由于輪詢方式和長連接方式耗費的流量不同，因此客戶端采用本文提出的自適應推送方式，在相同時間中接收等量的消息消耗的流量會不同。為了保證性能評估的準確性，本文在測試流量時采用多次測試一部手機從固定的電量至電量耗盡為止的測試方式，記錄每10分鐘耗費的流量，然后求出每分鐘平均消耗的流量，精確到小數(shù)點后兩位。

3.3 電量消耗

電量消耗是測試一部手機從固定電量到電量耗盡所用的時間tt（單位為分鐘）來判斷的。tt越大則耗費的電量越少。E 的評估模型可以表示為：

其中，A 為常量。

在ASA 算法中觸發(fā)推送方式調(diào)度轉(zhuǎn)換的因素之一是移動終端的電量，采用長連接方式的客戶端，在移動終端電量低于10%后將轉(zhuǎn)為輪詢方式。為了保證性能評估的準確性，本文在測試電量時采用多次測試一部手機從某一固定電量（即為A 的值）至0%電量所用的時間（單位為分鐘），然后求平均值即為tt的值。

3.4 移動終端多樣性

移動終端多樣性是指移動終端操作系統(tǒng)多樣性，是通過測試服務器可以支持的移動終端操作系統(tǒng)類型種類來判斷的。長連接方式與移動終端的操作系統(tǒng)類型有關，一種服務需要多次開發(fā)。如果服務器只提供長連接服務，則不支持新型的移動終端操作系統(tǒng)。而本文提供的自適應推送方式，將輪詢方式和長連接方式結合，新型操作系統(tǒng)的移動終端可以采用輪詢方式接收推送消息。S 的評估模型可以表示為：

3.5 評估參數(shù)分析

性能評估參數(shù)R、F、E、S 中：R 的值越小，則客戶端接收的消息的實時性越好；F 的值越小，則消耗移動終端的流量越少，即節(jié)省流量；E 的值越小，則消耗移動終端的電量越少，能保證移動終端正常工作的時間越長；S 的值越大，則服務器支持的移動終端類型越多。

在理論上，本文設計的自適應推送方式的消息實時性與長連接方式接近，消耗移動終端的流量不高于輪詢方式，保證移動終端正常使用的時間大于長連接方式，支持的移動終端類型與輪詢方式相同。

4 實驗結果

為驗證本文提出的自適應消息推送策略，本文通過消息推送平臺來驗證該策略的可行性，一方面與采用輪詢方式的消息推送平臺做比較分析，另一方面與采用長連接方式的消息推送平臺做比較分析。

4.1 原型系統(tǒng)設計

本文選擇三星9100（系統(tǒng)版本Android 4.0）、HT-I710（系統(tǒng)版本Android 2.3.5）、iPhone4S和Nokia 510（WindowsPhone 7.5）為實驗移動終端平臺，在服務器上提供自適應消息推送服務。為了保證實驗與真實場景接近，服務器推送消息時間隨機生成。用戶在移動終端上可以完成三個基本操作：與服務器建立連接、接收消息和斷開連接。原型系統(tǒng)結構如圖4所示。

用戶啟動客戶端后，客戶端向服務器發(fā)送連接請求，同時將手機的IP 地址、電池剩余電量、操作系統(tǒng)類型等參數(shù)傳給服務器，服務器根據(jù)以上參數(shù)提供合適的推送方式。

Figure 4 Prototype structure圖4 原型結構圖

4.2 實驗結果比較分析

原型系統(tǒng)的實驗在消息實時性、流量消耗、電量消耗及移動終端多樣性四個方面比較輪詢方式、長連接方式和ASA 方式。輪詢方式中，T 取值為5秒，測試電量消耗時取A＝30%，測試延遲和流量消耗時取N＝1。

Table 1 Average delay schedule表1 平均延遲時間表 ms

流量消耗比較：由表2 可知，F(xiàn) （輪詢）＞F（ASA）＞F（長連接），ASA 推送方式消耗的流量低于輪詢方式。

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

電量消耗比較：由表3可知，E（長連接）＞E（ASA）＞E （輪詢），ASA 推送方式消耗的電量低于長連接方式。

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

移動終端多樣性比較：ASA 方式和輪詢方式支持各種類型的操作類型，長連接方式只支持提供相應服務的操作系統(tǒng)。

5 結束語

本文提出了一種面向移動終端的自適應消息推送策略，該策略分析移動終端的運行參數(shù)（操作系統(tǒng)類型、電量、推送方式等），為終端動態(tài)分配消息推送方式（長連接方式或輪詢方式）。原型系統(tǒng)實驗表明，該策略在適應終端多樣性的同時，與長連接方式相比降低了移動終端的耗電量，與輪詢方式相比節(jié)省了網(wǎng)絡流量，并保證了消息的實時性。

ASA 方式消耗的流量比長連接方式消耗的流量多，在未來工作中將改進ASA 算法，以節(jié)省更多的網(wǎng)絡流量。

[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 服務請求調(diào)度策略[J].計算機學報，2006，2.（7）：1189-1198.

[15]梅蕊.跨服務器消息發(fā)布與推送機制的研究[D].武漢：華中科技大學，2011.