基于貝葉斯網(wǎng)的移動互聯(lián)網(wǎng)應(yīng)用部署算法研究

張驥先

(云南大學(xué)信息學(xué)院，云南昆明650092)

移動互聯(lián)網(wǎng)應(yīng)用已經(jīng)引發(fā)了信息產(chǎn)業(yè)的深度變革，具有分布性廣、移動性強(qiáng)的特點(diǎn)［1－2］.一個移動互聯(lián)網(wǎng)應(yīng)用完整的業(yè)務(wù)流程一般會涉及到終端和服務(wù)端交互，例如蘋果手機(jī)的智能語音助手Siri，手機(jī)終端采集用戶的語音并進(jìn)行識別，然后將識別后的信息傳輸至服務(wù)端，服務(wù)端將這類信息進(jìn)行識別后的得到了用戶意圖，然后根據(jù)此意圖進(jìn)行知識搜索，并將搜索得到的結(jié)果傳回手機(jī)終端展現(xiàn)給客戶.在這個業(yè)務(wù)流程當(dāng)中，手機(jī)終端負(fù)責(zé)采集用戶的語音并進(jìn)行識別，以及最后結(jié)果的展示.但是同樣是語音助手，基于Android系統(tǒng)的大部分手機(jī)都是將語音流傳輸?shù)椒?wù)器，在服務(wù)器上完成語音的識別.其中最主要的原因在于如果在手機(jī)終端完成語音識會耗費(fèi)手機(jī)大量的CPU資源及電量;而如果將語音流傳輸至服務(wù)器的話可以節(jié)省CPU資源及電量，但另一方面又會耗費(fèi)網(wǎng)絡(luò)通信帶寬［3－4］.

這個例子說明，一個移動互聯(lián)網(wǎng)應(yīng)用由多個功能模塊組成(如例子中的語音識別模塊，知識搜索模塊)，其中一部分功能模塊既可以在終端運(yùn)行，也可以在服務(wù)端運(yùn)行.應(yīng)用部署指的是根據(jù)終端目前狀態(tài)以及應(yīng)用本身復(fù)雜度來決定應(yīng)用中哪些功能模塊在服務(wù)端運(yùn)行，哪些功能模塊在終端運(yùn)行可以使應(yīng)用服務(wù)質(zhì)量最好，系統(tǒng)性能最優(yōu)［5］.當(dāng)前研究工作多是針對單一平臺上簡單應(yīng)用提出的應(yīng)用部署算法，且不適用于大型應(yīng)用.而這些方面正是移動互聯(lián)網(wǎng)應(yīng)用部署從理論走向?qū)嶋H所需要解決的關(guān)鍵問題，主要涉及到以下幾個方面:

1)應(yīng)用模型:一個應(yīng)用由若干個功能模塊組成，應(yīng)用模型反映出應(yīng)用中所包含各個模塊間的交互關(guān)系以及拓?fù)浣Y(jié)構(gòu).當(dāng)前的研究有幾種主流的觀點(diǎn)，分別是將應(yīng)用的功能模塊表示成圖的拓?fù)浣Y(jié)構(gòu)［6－9］、樹的拓?fù)浣Y(jié)構(gòu)［7］和彈性應(yīng)用模型［8］.但這幾類模型對簡單應(yīng)用較為適用，一旦應(yīng)用復(fù)雜度增加，應(yīng)用模塊間相關(guān)程度增大，其拓?fù)浣Y(jié)構(gòu)復(fù)雜度會增大，直接影響了應(yīng)用部署算法的效率及準(zhǔn)確性.

2)應(yīng)用部署算法:基于應(yīng)用模型，應(yīng)用部署算法會根據(jù)終端接入應(yīng)用時的環(huán)境和狀態(tài)計算出最合適的部署方案，然后將應(yīng)用中的模塊按照此方案部署到移動端或服務(wù)端，以求達(dá)到最優(yōu)的用戶體驗和系統(tǒng)性能.部署算法主要分為靜態(tài)算法與動態(tài)算法兩種，靜態(tài)算法具有較高的準(zhǔn)確性，但計算量大，一般通過分類或聚類算法先期計算出預(yù)測模型，這意味著需要采集大量的用戶數(shù)據(jù)來完成機(jī)器學(xué)習(xí)，從而在新用戶接入應(yīng)用時服務(wù)端可以快速計算出最恰當(dāng)?shù)牟渴鸱桨?而動態(tài)算法不需要進(jìn)行前期學(xué)習(xí)，根據(jù)終端首次接入應(yīng)用時的狀態(tài)進(jìn)行實(shí)時的計算，性能及準(zhǔn)確性不高.應(yīng)用部署算法一般放在服務(wù)端執(zhí)行，文獻(xiàn)［6］屬于動態(tài)算法，其采用線性優(yōu)化進(jìn)行部署方案的實(shí)時計算，而且未考慮模塊節(jié)點(diǎn)的父節(jié)點(diǎn)對當(dāng)前應(yīng)用部署的影響，所得到的結(jié)果準(zhǔn)確性低，且效率較低;文獻(xiàn)［7－9］屬于靜態(tài)算法，其提出的應(yīng)用部署方案計算方法雖然考慮到了歷史數(shù)據(jù)因素，但是其基于樸素貝葉斯(naive Bayesian)的分類策略中存在特征屬性不獨(dú)立的問題，會降低結(jié)果的準(zhǔn)確性，且其分類器訓(xùn)練較為復(fù)雜.

1 國內(nèi)外研究現(xiàn)狀

目前國內(nèi)外對移動互聯(lián)網(wǎng)應(yīng)用部署的研究多是針對特定平臺上簡單應(yīng)用進(jìn)行的研究.

1.1 應(yīng)用模型的研究

應(yīng)用模型的一個主要研究內(nèi)容是應(yīng)用的拓?fù)浣Y(jié)構(gòu)，目前有幾種主流的觀點(diǎn)，分別是將應(yīng)用模塊間調(diào)用關(guān)系表示成圖的拓?fù)浣Y(jié)構(gòu)［6，9］、樹的拓?fù)浣Y(jié)構(gòu)［7］和彈性應(yīng)用模型［8］.

Giurgiu 等和 Shumao 等［6，9］提倡將應(yīng)用按模塊(如Java類)之間的調(diào)用關(guān)系表示為有向無環(huán)圖，G={B，E}，其中節(jié)點(diǎn)B代表模塊;邊E代表模塊間交互.將應(yīng)用模型表示為圖拓?fù)浣Y(jié)構(gòu)的好處是比較適合于面向?qū)ο蟮膽?yīng)用開發(fā)方式，基本可以涵蓋所有的應(yīng)用，缺點(diǎn)是當(dāng)應(yīng)用結(jié)構(gòu)變得復(fù)雜的時候，圖也會相應(yīng)變得復(fù)雜，直接影響到應(yīng)用部署及遷移算法的效率.

Intel Labs Berkeley 的 Chun 等［7］提出了克隆云(clone cloud)的概念，為應(yīng)用模型提出了一種新的思路，通過分析應(yīng)用中函數(shù)調(diào)用關(guān)系，將應(yīng)用體現(xiàn)為樹的拓?fù)浣Y(jié)構(gòu)(profile tree)，樹中每個節(jié)點(diǎn)代表一個函數(shù)，而邊代表調(diào)用關(guān)系.樹的拓?fù)浣Y(jié)構(gòu)比較適合于面向過程的應(yīng)用開發(fā)方式，模塊粒度多為函數(shù)級別，優(yōu)點(diǎn)是較易分離出造成性能瓶頸的函數(shù);缺點(diǎn)是此類應(yīng)用的設(shè)計與實(shí)現(xiàn)不便，且模塊間相互調(diào)用關(guān)系不易處理，樹的拓?fù)浣Y(jié)構(gòu)并不適合于描述目前大多數(shù)的應(yīng)用.

Samsung實(shí)驗室的Zhang等［8］提出了彈性應(yīng)用模型(elasticity patterns)的概念，應(yīng)用中各模塊叫做Weblet，并且支持在運(yùn)行時對Weblet進(jìn)行動態(tài)配置，旨在無縫并且透明地使用服務(wù)端來擴(kuò)展移動設(shè)備受限的計算及存儲能力.彈性應(yīng)用模型會因不同的應(yīng)用配置體現(xiàn)出不同的運(yùn)行時行為，比如能量消耗、資費(fèi)開銷、應(yīng)用性能，甚至安全與隱私特性，雖體現(xiàn)了應(yīng)用部署的動態(tài)性但也存在一些缺陷，如Weblet在需要時才計算執(zhí)行的位置，也帶來了額外的開銷，影響應(yīng)用執(zhí)行的效率.

通過上述研究可以發(fā)現(xiàn)，應(yīng)用模型的主要工作是將應(yīng)用描述為相互獨(dú)立的功能模塊.模塊的粒度可能是函數(shù)、類、或者對象，采用圖或樹的方式來表現(xiàn)應(yīng)用拓?fù)浣Y(jié)構(gòu)，并抽象出屬性因素，建立應(yīng)用代價模型.但隨著移動應(yīng)用的發(fā)展，應(yīng)用模型會日趨復(fù)雜，之前的研究對如何簡化應(yīng)用拓?fù)浣Y(jié)構(gòu)并沒有提出較好的方法，所以，簡化應(yīng)用拓?fù)浣Y(jié)構(gòu)是本文的主要的研究內(nèi)容之一.

1.2 應(yīng)用部署算法的研究

應(yīng)用部署算法主要包括靜態(tài)算法與動態(tài)算法2種，靜態(tài)算法具有較高的準(zhǔn)確性，但計算量大，一般通過分類或聚類算法先期計算出預(yù)測模型，這意味著需要采集大量的用戶數(shù)據(jù)來完成機(jī)器學(xué)習(xí)，從而在新用戶接入應(yīng)用時給出較優(yōu)的部署方案;而動態(tài)算法不需要進(jìn)行前期學(xué)習(xí)，根據(jù)終端首次接入應(yīng)用時的狀態(tài)進(jìn)行實(shí)時的計算，性能及準(zhǔn)確性不高.目前的研究成果主要包括有遍歷法［6］、線性規(guī)劃法［7］、統(tǒng)計分類法［8］、最小生成樹法［9］等幾種方式來實(shí)現(xiàn)，其中文獻(xiàn)［6］屬于動態(tài)算法，文獻(xiàn)［7－9］屬于靜態(tài)算法.

Giurgiu等［6］提出了適用于離線應(yīng)用的ALL算法和適用于在線應(yīng)用的K－step算法.前者通過遍歷應(yīng)用模型產(chǎn)生所有可用的部署方案，并找出其中執(zhí)行時間最短的一個方案.后者選定一個入口功能模塊作為初始子集，然后計算與當(dāng)前子集距離為K的所有集合，并在上述集合中再選取執(zhí)行時間最短的一個，將其作為新的子集迭代計算，直至應(yīng)用模型遍歷結(jié)束或達(dá)到移動終端限制.ALL算法的優(yōu)點(diǎn)是可靠性高，缺點(diǎn)是耗時長，計算量大，并不適合實(shí)時的進(jìn)行;K－step算法通過局部最優(yōu)策略計算的應(yīng)用部署方案，優(yōu)點(diǎn)是計算速度快，計算量可控，缺點(diǎn)是隨著應(yīng)用功能模塊的增多，算法計算量增大，且準(zhǔn)確性下降.Giurgiu等通過測試指出在實(shí)際應(yīng)用中功能模塊之間的調(diào)用次數(shù)會直接影響結(jié)果，但并沒有提出相應(yīng)的解決方案.2種算法僅在應(yīng)用運(yùn)行前進(jìn)行計算，無法實(shí)時、動態(tài)的調(diào)整.基于遍歷法的應(yīng)用部署方案計算方式需要對應(yīng)用所有可能的部署方案進(jìn)行實(shí)時計算，計算量相當(dāng)大，即使對于服務(wù)端來說也是不能忽略的.

Chun等［7］在計算應(yīng)用部署方案時不僅考慮到了應(yīng)用的執(zhí)行時間也考慮到了移動終端執(zhí)行時的電量消耗，其應(yīng)用部署方案的計算包括靜態(tài)分析(static analyzer)、動態(tài)分析(dynamic profile)、優(yōu)化配置(optimization Solver)3個部分組成.靜態(tài)分析通過分析應(yīng)用間函數(shù)調(diào)用關(guān)系，在代碼中構(gòu)建遷移點(diǎn)和還原點(diǎn)，決定哪些函數(shù)可以遷移到服務(wù)端執(zhí)行，遷移點(diǎn)和還原點(diǎn)的構(gòu)建也有一些限制;在動態(tài)分析中通過大量隨機(jī)用例的執(zhí)行，搜集應(yīng)用中各個函數(shù)在移動終端以及在服務(wù)端執(zhí)行時的代價情況，最后通過整數(shù)線性規(guī)劃(ILP)算法得到應(yīng)用最優(yōu)的結(jié)果.但該算法計算量大，而且輸入用例是隨機(jī)產(chǎn)生的，并不能保證對應(yīng)用中各函數(shù)完整的覆蓋度.

由于將一個圖劃分成為K+1個滿足預(yù)先設(shè)置條件的部分，各部分之間通信量最小這個命題已被證明是一個NP－Complete問題［10］，Shumao等提出的K+1 Coarse partition應(yīng)用部署算法旨在找到符合限制條件的一種應(yīng)用部署方案［9］，并不要求此方案是最優(yōu)的.其算法的核心是HELVM(heavy edge light vertex)算法，HELVM 算法改進(jìn)自RM、HEM 和LEM 算法［11－12］，是一種基于最小生成樹的算法.其優(yōu)點(diǎn)在于不僅考慮了邊的權(quán)值(功能模塊間交互)，也考慮了節(jié)點(diǎn)的權(quán)值(功能模塊特性如所占空間及運(yùn)行內(nèi)存等)，使得帶有終端限制的應(yīng)用部署方案會更加合理.但是HELVM算法不是每次都能將恰好將圖劃分成K+1個部分，每部分恰好滿足預(yù)先定義的限制(事實(shí)上大部分情況下不能)，一般需要多次執(zhí)行才能得到理想的結(jié)果.此算法的復(fù)雜度是，計算量較大.

2 改進(jìn)方案

應(yīng)用部署需要客戶端和服務(wù)端完成一系列的交互，其流程描述如下圖所示:

2.1 應(yīng)用模型及服務(wù)模型

傳統(tǒng)的觀念將一個應(yīng)用中的模塊以及模塊之間的聯(lián)系看做應(yīng)用的拓?fù)浣Y(jié)構(gòu)，并稱之為應(yīng)用模型，但隨著移動應(yīng)用的發(fā)展，應(yīng)用模型會日趨復(fù)雜，之前的研究對如何簡化應(yīng)用模型并沒有提出較好的方法，本文提出服務(wù)模型的概念，將一個應(yīng)用表示為若干個服務(wù)模型的合集，并針對服務(wù)模型進(jìn)行分析處理，簡化了應(yīng)用拓?fù)浣Y(jié)構(gòu).例如在一個手機(jī)應(yīng)用當(dāng)中，可能有網(wǎng)絡(luò)通信模塊，圖形渲染模塊，圖片解碼模塊，語音采集模塊，而這些模塊之間會有數(shù)據(jù)通信，例如語音采集模塊會將采集到的語音傳送給網(wǎng)絡(luò)通信模塊進(jìn)行網(wǎng)絡(luò)傳輸.將這些模塊和模塊間通信抽象出來表示就形成了應(yīng)用模型.應(yīng)用模型指的是應(yīng)用中功能模塊的拓?fù)鋱D結(jié)構(gòu)，是一種有向無環(huán)圖，其中應(yīng)用功能模塊代表有向無環(huán)圖中的節(jié)點(diǎn)，功能模塊之間的數(shù)據(jù)交互代表有向無環(huán)圖中的邊.如果兩功能模塊之間有數(shù)據(jù)通信是單向的，則邊的表示具有方向性.

移動應(yīng)用的發(fā)展使得一個應(yīng)用可能包含多個服務(wù)，例如手機(jī)微信應(yīng)用具有聊天服務(wù)，朋友圈服務(wù)，掃二維碼服務(wù)，(簡單類應(yīng)用可視為提供單一服務(wù)).此類應(yīng)用有幾個顯著的特點(diǎn):

1)應(yīng)用所提供各服務(wù)相對獨(dú)立;

2)應(yīng)用功能模塊多、交互復(fù)雜，且一個功能模塊可能被多個服務(wù)共享;

3)應(yīng)用即使具有多個服務(wù)，用戶同時也只能訪問一個服務(wù).

這種情況下對應(yīng)用的所有功能模塊進(jìn)行應(yīng)用部署方案計算尋找最優(yōu)配置是非常耗時且基本不能完成的，所以，本文擬采用子圖的方式來簡化應(yīng)用模型.其原理是以應(yīng)用中的各服務(wù)為單位構(gòu)建服務(wù)模型，各服務(wù)模型的并集組成完整的應(yīng)用模型.服務(wù)模型是應(yīng)用模型的一個子集，也是由應(yīng)用功能模塊代表的節(jié)點(diǎn)以及功能模塊間交互代表的邊組成，體現(xiàn)了部分的應(yīng)用功能模塊的拓?fù)鋱D結(jié)構(gòu).

圖2左側(cè)的應(yīng)用模型是由右側(cè)的兩個服務(wù)模型構(gòu)成的，有些功能模塊被不同的服務(wù)共享，如1，3，6，8等功能模塊，而有些功能模塊則只存在于某一服務(wù)中，如16，17，18等功能模塊.由此可見，服務(wù)模型較為獨(dú)立，更容易分析，可以有效降低分析整個應(yīng)用模型的復(fù)雜度，提高應(yīng)用部署算法效率，而對服務(wù)模型中各功能模塊統(tǒng)計數(shù)據(jù)的匯總可以從應(yīng)用層面清晰的觀察到性能瓶頸或設(shè)計問題.

應(yīng)用部署的最終目的是終端接入應(yīng)用時根據(jù)終端當(dāng)前狀態(tài)(所處位置，網(wǎng)絡(luò)狀況，電量)決策應(yīng)用模型或服務(wù)模型中哪些功能模塊在服務(wù)端執(zhí)行，哪些功能模塊在終端執(zhí)行.所以首先終端需要搜集當(dāng)前的狀態(tài)信息傳輸至服務(wù)器(圖1中的step1)，服務(wù)器會根據(jù)這些信息結(jié)合應(yīng)用模型信息計算出恰當(dāng)?shù)牟渴鸱桨?圖1中的step2)，服務(wù)端在計算部署方案時需要以下幾類信息:

功能模塊基本信息:

1)功能模塊的類型(可移動的還是不可移動的，可移動的功能模塊可以在服務(wù)端或終端執(zhí)行);

2)當(dāng)前模塊所處服務(wù)模型;

3)功能模塊的所占用的存儲空間;

4)功能模塊的運(yùn)行時所占用的內(nèi)存空間;

5)功能模塊在移動終端運(yùn)行時所耗電量統(tǒng)計;

6)功能模塊的移動終端運(yùn)行累計時間;

7)功能模塊的數(shù)據(jù)輸入量

8)功能模塊的數(shù)據(jù)輸出量

終端實(shí)時狀態(tài)信息進(jìn)行搜集，主要包括:

1)終端所接入的服務(wù)器;

2)終端當(dāng)前電量;

3)終端當(dāng)前網(wǎng)絡(luò)狀況;

4)終端當(dāng)前CPU負(fù)載;

5)終端當(dāng)前可用的內(nèi)存及存儲空間.

在終端上，這些信息采集后會被保存為XML格式的描述，然后在應(yīng)用首次運(yùn)行時發(fā)送到服務(wù)端.

2.2 基于貝葉斯網(wǎng)絡(luò)預(yù)測模型的應(yīng)用部署算法

移動終端接入應(yīng)用后，會從服務(wù)端獲得適用于當(dāng)前情況的應(yīng)用部署方案(圖1中step3)，部署方案是服務(wù)端根據(jù)終端當(dāng)前的狀況通過一定算法運(yùn)算得到的結(jié)果.本文中使用貝葉斯網(wǎng)絡(luò)預(yù)測模型來獲得應(yīng)用的部署方案，基于貝葉斯網(wǎng)絡(luò)預(yù)測模型獲取應(yīng)用部署方案是一種靜態(tài)算法，需要預(yù)先通過大量的數(shù)據(jù)采用機(jī)器學(xué)習(xí)過程形成預(yù)測模型，當(dāng)新終端接入的時候可以根據(jù)終端當(dāng)前狀態(tài)結(jié)合預(yù)測模型來確定每個功能模塊的運(yùn)行位置.貝葉斯網(wǎng)絡(luò)依賴于穩(wěn)定的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，本文使用2.1中描述的應(yīng)用模型或服務(wù)模型來做為穩(wěn)定的拓?fù)浣Y(jié)構(gòu);之后貝葉斯網(wǎng)絡(luò)采集大量的數(shù)據(jù)進(jìn)行機(jī)器學(xué)習(xí)，通過這些數(shù)據(jù)，可以更新每個功能模塊在在不同位置運(yùn)行的概率(后稱之為預(yù)測模型).當(dāng)有新的終端接入應(yīng)用時，服務(wù)端會根據(jù)此終端當(dāng)前的狀態(tài)以及最新的預(yù)測模型計算出每個應(yīng)用功能模塊最適合的執(zhí)行位置，以求達(dá)到最好的用戶體驗.這里需要指出的是服務(wù)端在首次運(yùn)行時需要事先定義初始的預(yù)測模型.

服務(wù)端運(yùn)行的貝葉斯網(wǎng)絡(luò)預(yù)測模型算法實(shí)現(xiàn)如下，首先，我們假定每個可移動的功能模塊的執(zhí)行位置C依賴于此功能模塊的基本信息r、終端狀態(tài)信息s，圖3說明了一個可移動的功能模塊執(zhí)行位置的決策依據(jù)，在此功能模塊的基本信息r1以及終端當(dāng)前狀態(tài)信息s1的條件下，通過概率表可得出該功能模塊在終端執(zhí)行的概率是0.8，在服務(wù)端執(zhí)行的概率是0.2，所以此功能模塊適合在終端執(zhí)行.

根據(jù)圖4以及貝葉斯網(wǎng)絡(luò)基本算法，我們可以得到任意一個功能模塊在服務(wù)端或終端執(zhí)行的概率如公式1.其中，OC代表具有r，s條件的功能模塊在服務(wù)端或者終端執(zhí)行的概率，cl代表功能模塊所有可能的執(zhí)行位置，在這里只用考慮在終端或服務(wù)端執(zhí)行2種情況;ri代表功能模塊的基本信息;sj代表終端狀態(tài)信息s;而L、M分別表示，L個功能模塊的基本信息及M個終端狀態(tài)信息.終端首次接入應(yīng)用時，服務(wù)端會根據(jù)終端此時的狀態(tài)計算出適合于此終端的應(yīng)用功能模塊部署方案，并將此方案傳輸?shù)浇K端，終端會根據(jù)此部署方案來對應(yīng)用功能模塊進(jìn)行部署.

預(yù)測模型的更新是一個機(jī)器學(xué)習(xí)的過程，預(yù)測模型包括每個功能模塊在在不同位置運(yùn)行的概率數(shù)據(jù)，服務(wù)端在首次運(yùn)行時需要事先定義初始的預(yù)測模型，初始的預(yù)測模型通過人為設(shè)置每個應(yīng)用模塊在客戶端和服務(wù)端運(yùn)行的概率表，然后通過應(yīng)用上傳的數(shù)據(jù)進(jìn)行更新，應(yīng)用運(yùn)營開始的一段時間，預(yù)測模型可能會更新的比較頻繁，但隨著應(yīng)用運(yùn)營的時間增長，預(yù)測模型會逐步穩(wěn)定下來.預(yù)測模型是提供給所有終端進(jìn)行部署方案的依據(jù).少量終端運(yùn)行時上傳的信息并不會對預(yù)測模型造成很大影響，只有大量終端運(yùn)行時數(shù)據(jù)呈現(xiàn)出同樣變化趨勢(如大量終端上傳的數(shù)據(jù)表明某應(yīng)用模塊在移動設(shè)備上運(yùn)行時間過長)時才會對預(yù)測模型造成影響，例如有超過30%的終端上傳的數(shù)據(jù)表明某應(yīng)用模塊在移動設(shè)備上運(yùn)行時間長于一定值時，就會更新預(yù)測模型中概率表的數(shù)據(jù).

3 應(yīng)用原型及測試

我們搭建了一個移動應(yīng)用框架來模擬現(xiàn)有移動互聯(lián)網(wǎng)應(yīng)用場景以及實(shí)現(xiàn)應(yīng)用模塊的跨平臺運(yùn)行，框架分為前后端2部分.前端基于Android平臺實(shí)現(xiàn)，后臺使用J2EE框架搭建服務(wù)器，應(yīng)用模塊跨平臺運(yùn)行方案例如 Rellermeyer 等的 R － OSGi［13－14］，Houacine等［15］的 MCC － OSGi，我們最后采用了改進(jìn)的R－OSGi實(shí)現(xiàn)，一方面R－OSGi較為成熟穩(wěn)定，開源支持也比較好.在應(yīng)用中每個模塊均由一個R－OSGi Bundle構(gòu)成，不同的Bundle可以在手機(jī)中運(yùn)行也可以在服務(wù)器上運(yùn)行，對應(yīng)用模型提供了良好的支撐.圖4是實(shí)驗終端和服務(wù)端系統(tǒng)框架圖.

位于終端的Monitor負(fù)責(zé)監(jiān)控終端狀態(tài)以及外界情況變化;客戶端的R－OSGi框架負(fù)責(zé)運(yùn)行本地Bundle或通過Bundleproxy接口調(diào)用服務(wù)端的Bundle.應(yīng)用服務(wù)器采用J2EE架構(gòu)，并包含了核心模塊Static Partitioner、Statistic、Application Manager 及Service Manager模塊;Static Partitioner模塊負(fù)責(zé)使用貝葉斯算法計算出符合終端當(dāng)前時刻狀態(tài)的應(yīng)用部署方案;Statistic模塊搜集每個終端接入應(yīng)用的狀態(tài)用于更新貝葉斯網(wǎng)絡(luò);Application Manager負(fù)責(zé)對不同的應(yīng)用進(jìn)行管理;Service Manager負(fù)責(zé)對應(yīng)用中的不同服務(wù)進(jìn)行管理.

為了驗證應(yīng)用部署策略中的各項理論，我們開發(fā)了一套全景人臉識別應(yīng)用進(jìn)行測試.該應(yīng)用包含多個方便移植的功能模塊，分別是:圖片拼接、圖片預(yù)處理以及人臉識別模塊，每個既可以在手機(jī)端運(yùn)行，也可以在服務(wù)端運(yùn)行.應(yīng)用需要在手機(jī)上通過水平方向旋轉(zhuǎn)拍攝3張照片，然后使將3張照片拼接成為一個全景照片，之后進(jìn)行圖像預(yù)處理如色彩均衡和膚色分隔，最后進(jìn)行人臉識別.這3個功能模塊的實(shí)現(xiàn)都來自于與OpenCV庫，OpenCV的開源性質(zhì)使得不同的功能模塊可以方便移植到不同的平臺上，是應(yīng)用模塊可以部署在客戶端和服務(wù)器的前提條件，應(yīng)用在運(yùn)行的時候會根據(jù)不同的狀況選擇每個應(yīng)用模塊執(zhí)行的位置，從而對應(yīng)用的執(zhí)行時間以及效率帶來不同的影響.為了使測試結(jié)果更具有說服力，我們對后臺的部署算法進(jìn)行了改進(jìn)，調(diào)整了客戶端不同狀態(tài)在貝葉斯網(wǎng)絡(luò)進(jìn)行概率計算時的權(quán)重，這會影響到最終的預(yù)測模型.我們分為2組共5種情況對應(yīng)用進(jìn)行了測試，表1是測試結(jié)果，我們將所有模塊都在終端運(yùn)行的狀態(tài)作為對比參考，在這種情況下，整個應(yīng)用完整運(yùn)行下來大概需要30 s左右.

我們首先對Wifi/4G網(wǎng)絡(luò)狀況下的應(yīng)用進(jìn)行了2種不同傾向性的測試，一種是性能優(yōu)先，即應(yīng)用運(yùn)行時間最少，在這種情況下，預(yù)測模型將全部模塊部署到服務(wù)端運(yùn)行，耗時約17 s左右，各個模塊在服務(wù)短端運(yùn)行的時間很快，時間主要消耗在將初始圖片傳輸至服務(wù)端以及服務(wù)端將識別的結(jié)果傳回終端這個過程;而在能耗優(yōu)先測試中，部署算法將圖片拼接和圖片預(yù)處理置于終端運(yùn)行，將人臉識別模塊置于服務(wù)端運(yùn)行，因為4G網(wǎng)絡(luò)傳輸帶來的電量消耗較大，而預(yù)處理后的圖片體積較小，利于傳輸，這種情況下程序運(yùn)行時間約28 s.

在2G網(wǎng)絡(luò)下，由于網(wǎng)絡(luò)傳輸速度很慢，所以在性能優(yōu)先的前提下，部署算法直接將所有模塊都部署到終端運(yùn)行;在節(jié)約能耗優(yōu)先的測試中，部署算法傾向于將所有的模塊都部署到服務(wù)端運(yùn)行，因為2G環(huán)境下，網(wǎng)絡(luò)傳輸?shù)哪芎妮^低，但是帶來的問題就是大量是時間被消耗在網(wǎng)絡(luò)數(shù)據(jù)傳輸?shù)倪^程中，這種情況下程序的運(yùn)行時間將近60 s.不同應(yīng)用部署方案測試結(jié)果如表1所示.

表1 不同應(yīng)用部署方案測試結(jié)果 s

可以看出，對應(yīng)用進(jìn)行恰當(dāng)?shù)哪K劃分并進(jìn)行合理的部署可以有效提高應(yīng)用運(yùn)行的效率，另一方面測試的結(jié)果也驗證了部署算法在不同傾向性的前提下對應(yīng)用的確起到了優(yōu)化作用.

4 結(jié)語

在以往移動互聯(lián)網(wǎng)應(yīng)用部署研究的基礎(chǔ)上，基于目前移動應(yīng)用復(fù)雜性、實(shí)時性、多樣性的發(fā)展趨勢針對應(yīng)用模型及應(yīng)用部署算法幾個方面進(jìn)行了研究:首先通過抽象服務(wù)模型的概念，簡化了應(yīng)用拓?fù)浣Y(jié)構(gòu)，降低應(yīng)用復(fù)雜度，解決了以往應(yīng)用模型用于復(fù)雜應(yīng)用時導(dǎo)致應(yīng)用部署方案計算執(zhí)行效率低的問題;其次基于應(yīng)用模型或服務(wù)模型結(jié)合貝葉斯網(wǎng)的分類算法使得在服務(wù)端執(zhí)行的應(yīng)用部署方案計算較以往的算法更加高效.

應(yīng)用模塊的部署是一個復(fù)雜的問題，在本文測試中的應(yīng)用比較簡單，模塊數(shù)量少，且是順序執(zhí)行的流程，不存在復(fù)用的問題，也不存在終端和服務(wù)器多次數(shù)據(jù)交互問題，所以測試結(jié)果較為理想;但是很多應(yīng)用的功能模塊數(shù)量多，應(yīng)用模型拓?fù)浣Y(jié)構(gòu)復(fù)雜，在這種情況下算法是否能夠取得很好的效果是我們將來的研究方向.

［1］工業(yè)和信息化部電信研究院.云計算白皮書［EB/OL］.(2014 －5 －12)［http://www.catr.cn/xwdt/kydt/201405/t20140512_1017555.htm］

［2］SATYANARAYANAN M.Mobile computing:the next decade［J］.ACM SIGMOBILE Mobile Computing and Communications Review，2011，15(2):2－10.

［3］ARMBRUST M，F(xiàn)OX A，GRIFFITH R，et al.A view of cloud computing［J］.Communications of the ACM，2010，53(4):50－58.

［4］KUMAR K，LU Y H.Cloud computing for mobile users:Can off loading computation save energy［J］.Computer，2010，43(4):51－56.

［5］徐光俠，陳蜀宇.面向移動云計算彈性應(yīng)用的安全模型［J］.計算機(jī)應(yīng)用，2011，31(4):952－955.

［6］GIURGIU I，RIVA O，JURIC D，et al.Calling the cloud:enabling mobile phones as interfaces to cloud applications［M］//Middleware 2009.Springer Berlin Heidelberg，2009:83－102.

［7］CHUN B G，IHM S，MANIATIS P，et al.Clonecloud:elastic execution between mobile device and cloud［C］//Proceedings of the sixth conference on computer systems.ACM，2011:301－314.

［8］ZHANG X，JEONG S，KUNJITHAPATHAM A，et al.Towards an elastic application model for augmenting computing capabilities of mobile platforms［M］//Mobile wireless middleware，operating systems，and applications.Springer Berlin Heidelberg，2010:161－174.

［9］OU S，YANG K，ZHANG J.An effective offloading middleware for pervasive services on mobile devices［J］.Pervasive and Mobile Computing，2007，3(4):362－385.

［10］MICHAEL R G，DAVID S J.Computers and intractability:a guide to the theory of NP － completeness［J］.WH Freeman ＆ Co，San Francisco，1979.

［11］KARYPIS G，KUMAR V.A fast and high quality multilevel scheme for partitioning irregular graphs［J］.SIAM Journal on scientific Computing，1998，20(1):359－392.

［12］KARYPIS G，KUMAR V.Parallel multilevel series k－way partitioning scheme for irregular graphs［J］.Siam Review，1999，41(2):278－300.

［13］RELLERMEYER J S，ALONSO G，ROSCOE T.R －OSGi:distributed applications through software modularization［C］//Proceedings of the ACM/IFIP/USENIX 2007 International Conference on Middleware.New York:Springer－Verlag，2007:1 －20.

［14］RELLERMEYER J S，RIVA O，ALONSO G.AlfredO:an architecture for flexible interaction with electronic devices［C］//Proceedings of the 9th ACM/IFIP/USENIX International Conference on Middleware.New York:Springer－Verlag，2008:22 －41.

［15］HOUACINE F，BOUZEFRANE S，LI L，et al.Mcc － osgi:An osgi－ based mobile cloud service model［C］//Autonomous Decentralized Systems(ISADS)，2013 IEEE Eleventh International Symposium on.IEEE，2013:1－8.