劉永玲，劉 兀，郭克華

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

1 引言

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

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

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

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

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

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

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

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

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

2 自適應(yīng)消息推送策略

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

2.1 參數(shù)定義

為了方便ASA 算法的描述，特進(jìn)行如下定義：

定義1 支持的操作系統(tǒng)集合L-S：該集合專為長連接方式設(shè)計的，用來記錄服務(wù)器提供的長連接服務(wù)支持的操作系統(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表示長連接服務(wù)支持該類型的操作系統(tǒng)｝。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

用戶初次登錄，客戶端向服務(wù)器發(fā)送連接請求，如果同時滿足以下三個條件：L-si＝1，Nu＜Pt，且Er＞Et（L），則為用戶分配長連接推送方式，否則分配輪詢方式。當(dāng)用戶刷新時，若采用長連接方式且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）是基于移動終端接收到消息的實(shí)時性（用R 表示）、消耗的流量（用F 表示）、消耗的電量（用E 表示）以及移動終端的操作系統(tǒng)類型（用S 表示）等四方面來設(shè)計的。

3.1 消息實(shí)時性

3.2 流量消耗

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

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

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

3.3 電量消耗

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

其中，A 為常量。

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

3.4 移動終端多樣性

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

3.5 評估參數(shù)分析

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

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

4 實(shí)驗(yàn)結(jié)果

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

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

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

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

Figure 4 Prototype structure圖4 原型結(jié)構(gòu)圖

4.2 實(shí)驗(yàn)結(jié)果比較分析

原型系統(tǒng)的實(shí)驗(yàn)在消息實(shí)時性、流量消耗、電量消耗及移動終端多樣性四個方面比較輪詢方式、長連接方式和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 方式和輪詢方式支持各種類型的操作類型，長連接方式只支持提供相應(yīng)服務(wù)的操作系統(tǒng)。

5 結(jié)束語

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

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

[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）

附中文參考文獻(xiàn)

[14]官荷卿，張文博，魏峻，等.一種應(yīng)用敏感的Web 服務(wù)請求調(diào)度策略[J].計算機(jī)學(xué)報，2006，2.（7）：1189-1198.

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