移動計(jì)算中自適應(yīng)負(fù)載轉(zhuǎn)移決策模型研究.pdf

1、以智能手機(jī)為代表的移動設(shè)備，受限于設(shè)備自身的尺寸、大容量電池制造工藝的滯后、無線通信網(wǎng)絡(luò)的不穩(wěn)定，已經(jīng)越來越難以滿足移動用戶對智能手機(jī)執(zhí)行功能更加復(fù)雜、能耗需求更高應(yīng)用的需求。移動設(shè)備系統(tǒng)電能消耗與電池容量增長速度的不一致，系統(tǒng)能提供的計(jì)算能力與新應(yīng)用的需求增長速度的不一致是移動設(shè)備發(fā)展中面臨的挑戰(zhàn)。移動負(fù)載轉(zhuǎn)移思想，提出移動設(shè)備可以與服務(wù)器構(gòu)成一個(gè)協(xié)作系統(tǒng)，通過負(fù)載轉(zhuǎn)移的方式將部分應(yīng)用功能(任務(wù))轉(zhuǎn)移至(協(xié)作)服務(wù)器端遠(yuǎn)程執(zhí)行，提升應(yīng)

2、用執(zhí)行的性能，如減少執(zhí)行時(shí)間、減少設(shè)備能耗、提高執(zhí)行結(jié)果質(zhì)量等。
　　 與之對應(yīng)的移動協(xié)作應(yīng)用由多個(gè)任務(wù)組成，包括若干個(gè)可負(fù)載轉(zhuǎn)移任務(wù)，即該任務(wù)既可以在移動設(shè)備本地執(zhí)行，也可以在協(xié)作服務(wù)器端執(zhí)行。移動負(fù)載轉(zhuǎn)移的核心問題是如何使得移動協(xié)作應(yīng)用，一方面可以盡可能地通過遠(yuǎn)程協(xié)作提升執(zhí)行性能；另一方面又盡可能地減少由于資源可用性變化造成的執(zhí)行延遲或者失敗。例如，減小移動設(shè)備到協(xié)作服務(wù)器之間端到端的帶寬波動對數(shù)據(jù)傳輸時(shí)間的影響，減小服務(wù)器

3、負(fù)載變化對執(zhí)行時(shí)間的影響等。移動負(fù)載轉(zhuǎn)移決策引擎的任務(wù)就是根據(jù)協(xié)作系統(tǒng)的資源可用性和移動應(yīng)用執(zhí)行性能要求，動態(tài)決定移動協(xié)作應(yīng)用中，每一個(gè)可負(fù)載轉(zhuǎn)移任務(wù)的執(zhí)行位置?，F(xiàn)有的決策引擎多采用“靜態(tài)決策策略”，采用靜態(tài)決策策略的決策引擎僅僅在應(yīng)用執(zhí)行前啟動，為應(yīng)用的每一個(gè)任務(wù)選擇執(zhí)行位置后即停止。在應(yīng)用執(zhí)行過程中，決策引擎不對協(xié)作系統(tǒng)資源可用性變化進(jìn)行跟蹤，不對應(yīng)用執(zhí)行進(jìn)度進(jìn)行跟蹤，不再調(diào)整任務(wù)執(zhí)行位置，直至執(zhí)行完成或者確認(rèn)失敗。靜態(tài)決策策略缺乏

4、應(yīng)對資源變化的靈活，可能導(dǎo)致應(yīng)用執(zhí)行的延遲、失敗，或增加移動設(shè)備額外的能量開銷。
　　 本文的工作1圍繞如何使得移動負(fù)載轉(zhuǎn)移決策引擎更加靈活地，自適應(yīng)地應(yīng)對協(xié)作系統(tǒng)資源可用性的變化，提高決策的準(zhǔn)確性，提高應(yīng)用執(zhí)行的性能而展開。本文提出“執(zhí)行路徑”的概念描述移動協(xié)作應(yīng)用中各個(gè)任務(wù)在遠(yuǎn)程或本地執(zhí)行的不同組合，采用圖論的方法對移動協(xié)作應(yīng)用的執(zhí)行過程進(jìn)行建模。采用“應(yīng)用執(zhí)行路徑圖”描述一個(gè)移動協(xié)作應(yīng)用各種不同的執(zhí)行組合以及與之對應(yīng)的執(zhí)行

5、路徑。決策引擎的任務(wù)是根據(jù)協(xié)作系統(tǒng)資源可用性情況，目標(biāo)函數(shù)(減少執(zhí)行時(shí)間、減少設(shè)備能耗等)，應(yīng)用執(zhí)行性能要求等為應(yīng)用選擇一條最優(yōu)的執(zhí)行路徑。一方面可以盡可能地有效利用系統(tǒng)資源，提升應(yīng)用執(zhí)行性能，同時(shí)也盡量減小執(zhí)行延遲和失敗的風(fēng)險(xiǎn)。為了改進(jìn)“靜態(tài)決策策略”的不足，本文提出一組“自適應(yīng)決策策略”，具體而言，本文
　　 1.提出“動態(tài)決策策略”。動態(tài)決策策略允許決策引擎在應(yīng)用執(zhí)行的全過程中，跟蹤協(xié)作系統(tǒng)資源可用性情況變化和應(yīng)用執(zhí)行進(jìn)度

6、，并且可以根據(jù)協(xié)作系統(tǒng)資源可用性變化，調(diào)整協(xié)作應(yīng)用的執(zhí)行路徑。
　　 2.提出“冗余路徑執(zhí)行”。與現(xiàn)有的“靜態(tài)決策策略”中，移動協(xié)作應(yīng)用只能采取一條路徑執(zhí)行不同。冗余路徑執(zhí)行允許協(xié)作應(yīng)用同時(shí)采用多條執(zhí)行路徑同時(shí)執(zhí)行，最早返回的結(jié)果將被使用。同時(shí)，決策引擎通過引入概率風(fēng)險(xiǎn)模型，評估因?yàn)閷f(xié)作系統(tǒng)資源可用性估值偏差造成錯(cuò)誤決策的概率和相應(yīng)的風(fēng)險(xiǎn)，輔助應(yīng)用執(zhí)行路徑、單路徑執(zhí)行或者冗余路徑執(zhí)行方案的選擇。
　　 3.提出“聯(lián)合決

7、策策略”。聯(lián)合決策策略允許協(xié)作服務(wù)器一起參與移動設(shè)備的負(fù)載轉(zhuǎn)移決策過程。移動設(shè)備可以共享應(yīng)用執(zhí)行的性能要求，如執(zhí)行完成的時(shí)間期限、最低執(zhí)行結(jié)果質(zhì)量要求等。當(dāng)協(xié)作服務(wù)器接收到移動設(shè)備的任務(wù)數(shù)據(jù)和執(zhí)行要求后，可以根據(jù)自身負(fù)載情況動態(tài)調(diào)整，如在負(fù)載條件允許下，提供更高質(zhì)量的執(zhí)行結(jié)果等。
　　 4.提出“漸進(jìn)式數(shù)據(jù)傳輸”模式，以減少網(wǎng)絡(luò)波動對于數(shù)據(jù)傳輸?shù)挠绊?。由于在服?wù)器端，計(jì)算處理和網(wǎng)絡(luò)傳輸通常不會造成資源重疊，漸進(jìn)式數(shù)據(jù)傳輸不會影響

8、應(yīng)用執(zhí)行時(shí)間。先前數(shù)據(jù)傳遞時(shí)候的網(wǎng)絡(luò)帶寬測試數(shù)據(jù)，也可以作為后續(xù)傳送時(shí)，估算傳送時(shí)間的依據(jù)。
　　 評估實(shí)驗(yàn)采用移動人臉識別應(yīng)用(mobile face detection)和移動全景圖應(yīng)用(mobile panorama)作為目標(biāo)應(yīng)用。在運(yùn)行安卓(Android)操作系統(tǒng)的Nexus S智能手機(jī)上，分別實(shí)現(xiàn)了基于動態(tài)決策策略和支持冗余路徑執(zhí)行方案的Wing負(fù)載轉(zhuǎn)移決策系統(tǒng)，以及基于聯(lián)合自適應(yīng)決策策略和支持漸進(jìn)式數(shù)據(jù)傳輸模式的M

9、ind負(fù)載轉(zhuǎn)移決策系統(tǒng)。
　　 評估實(shí)驗(yàn)采用控制變量的方法，評估自適應(yīng)決策策略在應(yīng)對協(xié)作服務(wù)器負(fù)載波動時(shí)的決策質(zhì)量。實(shí)驗(yàn)結(jié)果顯示，相比靜態(tài)決策策略，采用單路徑執(zhí)行的動態(tài)決策策略可以減少30％(50％)左右的應(yīng)用執(zhí)行時(shí)間，30％(50％)左右的設(shè)備能耗。同時(shí)，Wing系統(tǒng)在執(zhí)行動態(tài)決策時(shí)候的決策時(shí)間開銷很小，與采用靜態(tài)決策策略的時(shí)間開銷相似。
　　 評估實(shí)驗(yàn)采用基于網(wǎng)絡(luò)Trace數(shù)據(jù)的模擬實(shí)驗(yàn)方法，評估自適應(yīng)決策策略在應(yīng)對

10、移動設(shè)備到服務(wù)器之間端到端網(wǎng)絡(luò)連接質(zhì)量波動時(shí)的決策質(zhì)量。網(wǎng)絡(luò)Trace數(shù)據(jù)集合包括約2400分鐘的WiFi網(wǎng)絡(luò)Trace數(shù)據(jù)，涵蓋靜態(tài)應(yīng)用場景和移動(步行)應(yīng)用場景，總計(jì)約1萬多條數(shù)據(jù)記錄(上行帶寬、下行帶寬、往返時(shí)延等)，提供了約1萬多個(gè)決策評估點(diǎn)。實(shí)驗(yàn)評估還采用了4種常見的基本網(wǎng)絡(luò)帶寬估值模型。評估結(jié)果顯示，與靜態(tài)決策策略相比，采用單路徑執(zhí)行的動態(tài)決策策略平均可以降低40-50％的錯(cuò)誤決策概率，同時(shí)減少30%左右的應(yīng)用執(zhí)行時(shí)間，40