徐紅霞 孔志周

1(濟源職業(yè)技術學院 河南 濟源 459000 )2(湖南大學 湖南 長沙 410082)

0 引 言

目前，移動云計算領域有兩種體系結構，一種是遠程云[1]，即由功能強大的服務器和計算機軟硬件集群構成，通過WAN向移動設備提供服務。此時，移動設備通過蜂窩網絡或訪問點訪問云端資源。然而，遠程云因為過高的通信延時使得執(zhí)行實時應用并不會帶來較高的響應。另一種是移動微云(Cloudlet，也稱朵云)結構[2]，由鄰近的移動設備以無線方式構成，可以支持實時應用的執(zhí)行。這種體系結構中，移動設備可以移動Ad hoc網絡的形式訪問節(jié)點的計算資源。

移動微云中，任務遷移[3]即是將移動節(jié)點上的任務遷移至目標處理節(jié)點上，從而實現任務調度問題的收益最優(yōu)。任務遷移決策由多個參數影響：信道帶寬、計算能力、功率系數以及所有參與節(jié)點的排隊延時。任務調度的優(yōu)化目標之一是滿足移動系統(tǒng)對于響應時間的需求，尤其對于實時應用，如對象識別[4]、災難預警[5]、實時視頻編碼[6]、語音識別[7]等。任務遷移與調度的另一目標是改善移動設備的能效。盡管電池技術發(fā)展迅猛，但計算密集型移動應用的執(zhí)行仍然令移動設備的電量消耗太快，因此，此時移動云中的任務遷移與調度可以通過將計算型任務卸載至能效更高的設備上執(zhí)行來提高能效。

已提出過多種類型的調度用于任務遷移決策以降低任務的完成時間，并滿足服務質量需求，或節(jié)省電池能量[8-12]。通常，任務算法可分為集中式和分布式調度方法。集中式調度方法中，調度決策基于所有參與節(jié)點的已有信息，在中心控制器中制定，這種方法容易遭受單點失效和移動節(jié)點不合理部署的影響。分布式調度算法中，每個節(jié)點自主作出調度決策，可以使得移動微云具有更好的可擴展性和靈活性。

此外，多數先前的工作僅僅局限于單個移動設備下的任務處理場景，而在移動云系統(tǒng)中，可能存在有多個源設備和多個處理節(jié)點的場景。文獻[13]提出了一種移動系統(tǒng)中的分布式動態(tài)調度算法，算法將包括遷移需求的任務信息發(fā)送至鄰居節(jié)點，鄰居節(jié)點對其消息進行響應并執(zhí)行任務。而在多個不同源節(jié)點生成多個請求時，算法僅僅依據最短的任務響應時間選擇任務的處理節(jié)點，導致部分節(jié)點負載過重。然而，文獻在如何獲取實時的資源信息上并未給出具體方案。在移動云場景中，鄰近資源信息的發(fā)現方式有兩種：主動式和被動式。文獻[14]以一種被動式方式請求其他節(jié)點資源信息，雖然資源發(fā)現開銷較短，但其響應時間過長，無法滿足實時任務的需求。主動式資源發(fā)現周期性收集不同節(jié)點的資源狀態(tài)，基于當前資源信息更快的作出調度決策，對于時間約束型任務更加有利，便相對的資源開銷較大。文獻[15]設計一種主動式鄰近異構資源的資源發(fā)現路由策略，該策略添加了CPU類型、占用率、內存以及能量等級等參數至控制信息中，以周期性的廣播使得所有節(jié)點能夠獲取相互的資源信息。但是，控制信息的收發(fā)頻率在文中并沒有得到研究，使得任務調度與遷移的決策過程中沒有考慮資源發(fā)現的過大開銷，而這對于最終的任務調度結果是至關重要的。

總結目前的主要研究內容，當前在移動云中已有的分布式調度決策方法依然具有一些限制：1)多數調度問題受限于單源移動設備下的任務調度；2)在處理節(jié)點上的任務隊列長度和功率系數等參數下作出了過多不合理的假設，使得節(jié)點的資源信息一直可知。

為了解決以上問題，本文提出一種分布式自適應概率調度算法，可將來自于多源節(jié)點上的任務調度至微云中的鄰近處理節(jié)點，在滿足任務時間期限的同時，維持較低的能量消耗。算法首先估算任務在每個參與處理節(jié)點上的完成時間和能耗；然后，調度當前任務至以概率計算方式得到的能效最高的節(jié)點上執(zhí)行；同時，在不可預測的網絡條件下自適應調整時間余量參數，盡可能實現更高的任務完成率。

1 系統(tǒng)模型

1.1 網絡模型

令V表示移動微云中所有無線節(jié)點集合，E表示移動微云中所有無線鏈路集合，G(V,E)表示由于節(jié)點集V和邊集E組成的無向拓撲圖，P表示移動微云中所有處理節(jié)點集，P為V的子集，S表示移動微云中所有源節(jié)點集，也為V的子集，J表示到達V的任務集。

定義1一個微云由若干無線節(jié)點以無向通信圖G(V,E)的形式構成。給定節(jié)點u∈V和v∈V，當且僅當dis(u,v)≤rt(dis(u,v)為節(jié)點u與v間的歐氏距離)時，則有edge(u,v)∈E。即：若兩個節(jié)點間建立一條直接通信鏈路，則兩個節(jié)點間的距離需在其廣播通信范圍rt內。

處理節(jié)點u的計算能力表示為mipsu(每秒百萬指令數)，本文假設CPU執(zhí)行單個指令的能耗eu與其速率的平方成正比，即：

(1)

對于每個節(jié)點u，tq,u表示排隊延時，即任務置入隊列尾部直到任務被處理的等待時間。節(jié)點按其計算能力劃分為兩類：第一類為僅能處理自身任務的弱功能源節(jié)點，另一類為可處理其他節(jié)點任務的強功能處理節(jié)點。

假設J中的任務為計算密集型，且相互獨立，可執(zhí)行于任一微云中的節(jié)點。一旦任務到達，即可調度至處理節(jié)點上執(zhí)行。任務完成后，其結果集中返回至任務發(fā)送源節(jié)點。從源節(jié)點傳輸至目標節(jié)點的數據量Dj(字節(jié))與從目標節(jié)點返回的數據量是相同的。同時，假設所有節(jié)點的傳輸功率et、接收功率er和傳輸范圍rt是相同的，最大傳輸帶寬Bmax在鄰接節(jié)點間共享。微云中的節(jié)點隨機分布，任意兩個節(jié)點間或直接相連，或以Ad hoc方式連接。

1.2 任務模型

對于節(jié)點j∈J(源節(jié)點的任務隊列中的任務)，具有以下屬性：

1)Dj：在源節(jié)點與處理節(jié)點間傳輸的數據量；

2)Cj：處理的計算量；

3)Tj：任務j的時間約束。

任務j的所有屬性在任務j到達隊列時對于源節(jié)點是可知的。與相關文獻中模型不同的是，本文在任務調度與遷移上加入了截止時間的約束，對于不滿足截止時間約束的調度方案均視為不可行方案。因此，在調度算法設計過程中，必須將資源發(fā)現開銷考慮進來，對于響應時間過長和開銷過大的資源發(fā)現方式，勢必會導致最終的任務調度時間超過截止時間約束，進而導致任務失效。

1.3 問題描述

在網絡和任務模型下，可以計算任務執(zhí)行的能耗和完成時間。執(zhí)行任務的能耗包括兩個部分：

1) 計算能耗：表示處理節(jié)點u執(zhí)行任務帶來的能耗，定義為：

ComputationEneryj=eu×Cj

(2)

2) 通信能耗：表示任務從源節(jié)點遷移至目標節(jié)點處理時的能耗。通信能耗正比于數據傳輸量，令H(j)表示源節(jié)點至處理節(jié)點間的跳數，則：

CommunicationEneryj=H(j)×(et+er)×Dj

(3)

則任務j的執(zhí)行總能耗為：

TaskEnergyj=ComputationEneryj+CommunicationEneryj

(4)

所有n個任務總能耗為：

(5)

任務的完成時間由三個部分組成：

1)tq,u：處理節(jié)點u的排隊時間，即任務執(zhí)行前的等待時間；

2)texecution：任務在處理節(jié)點上的執(zhí)行時間：

(6)

3)ttransmition：源節(jié)點與處理節(jié)點間的數據傳輸時間：

(7)

當任務被遷移至節(jié)點u時任務j的完成時間即為三個部分之和：

TaskCompletionTimej=tq,u+texecution+ttransmition

(8)

若任務在其時間期限內完成，即滿足式(9)，也即認為任務成功調度；否則，任務調度失敗。

TaskCompletionTimej≤Tj

(9)

令n為任務總量，定義兩個指標評估任務調度結果，一個是任務完成率，一個是成功調度任務的平均能耗，分別定義為：

(10)

(11)

本文的最優(yōu)化問題可定義為：給定由源節(jié)點集S和待調度任務集J構成的微云系統(tǒng)G(V,E)，將任務從一個或多個源節(jié)點上調度至處理節(jié)點上，并實現能效的最優(yōu)化，即：

minAverageEnergyPerSucessfulTask

約束條件為：

Bu,v≤Bmax?e=(u,v)∈E

(12)

(13)

P?V,S?V,P∩S=?,P∪S=V

(14)

式(12)確保節(jié)點間的通信不能超過最大帶寬；式(13)確保僅能被調度一次；式(14)表明微云中的節(jié)點或為源節(jié)點，或為處理節(jié)點。

2 自適應概率調度算法設計

為了求解以上的任務調度問題，本文設計一種分布式的自適應概率調度算法，算法由兩個階段組成：資源發(fā)現階段和自適應概率調度階段。資源發(fā)現階段中，源節(jié)點周期性地收集鄰居處理節(jié)點的資源信息；自適應概率調度階段中，在每個源節(jié)點上，一旦任務j到達，調度器即選擇一個處理節(jié)點執(zhí)行任務j，并滿足時間約束以及能耗最優(yōu)的需求。

2.1 資源發(fā)現階段

階段一基于QoS OLSR[16]設計資源發(fā)現策略，利用兩類控制信息以獲得資源信息：

1) 修改的Hello Message：該消息在局部(即廣播至一跳鄰居節(jié)點)發(fā)送以使得節(jié)點發(fā)現其局部鄰居(類似于OLSR協(xié)議中的HELLO消息)；

2) 修改的拓撲控制Topology Control(TC)消息：通過多跳中繼節(jié)點(Multipoint Relay,MPR)發(fā)送至整個網絡，以使得拓撲分布和資源信息可以給所有節(jié)點間共享。

兩種消息類型周期性發(fā)送。消息發(fā)送間隔是一個變量，與網絡狀態(tài)變化快慢相關。網絡狀態(tài)變化越快，消息發(fā)送間隔相應越短。相關研究表明，初始的Hello消息和TC消息發(fā)送間隔為2 s和5 s。

本文通過在控制消息中向每個鄰居ID添加以下參數(擴充4個字節(jié))對路由表進行了擴展：

1) 設備參數：包括節(jié)點u的處理速度mipsu和功率系數eu；

2) 隊列長度：節(jié)點u當前的排隊時間tq,u。

從MPR節(jié)點發(fā)送的修改TC消息將攜帶其鄰居節(jié)點ID和其資源信息。一旦接收到修改的控制消息，每個源節(jié)點將更新其鄰居列表，該列表記錄了所有參與處理節(jié)點的資源信息。分布式資源發(fā)現過程如算法1所示。

算法1Resource Discovery Algorithm

輸入:Initial neighbor table of nodeu

輸出:Neighbor table of nodeu

功能：操作控制信息并更新節(jié)點u的鄰居列表

1. listen control message

//節(jié)點監(jiān)聽網絡中的控制信息

2. if(nodeureceives a control message from nodev) then

3. if(Message Type==HELLO_MESSAGE) then

4. updatau’s neighbor table by adding/updating nodevand its parameters

//更新鄰居列表

5. if(nodeuis an MPR node) then

6. construct/update TC message

//構造/更新TC消息

7. else if(Message Type==TC_MESSAGE) then

8. updateu’s neighbor table by adding/updating the nodes and their parameters in the TC message

//更新TC消息中節(jié)點的鄰居列表

9. if(nodeuis an MPR node) then

10.forward the TC message to all of its neighbors

//將TC消息中繼發(fā)送至其所有鄰居節(jié)點

11. returnu’s neighbor table

//返回鄰居列表

考慮到應用任務較緊的時間期限，修改的Hello消息和修改的TC消息需進一步縮短。QoS OLSR協(xié)議的控制信息在本文算法實現過程中添加了額外比特。原始QoS OLSR中，默認的Hello消息間隔為2 s，TC消息間隔為5 s。修改的QoS OSLR中，Hello消息間隔為TC消息間隔的一半，這可以確保MPR節(jié)點將帶有鄰居信息的TC消息發(fā)送至整個網絡。后面的實驗中也將研究消息發(fā)送間隔對算法調度性能的影響。

2.2 自適應概率調度階段

一個源節(jié)點u每次接收一個局部用戶任務j時，會估算任務在每個潛在處理節(jié)點v∈P上的能耗TaskEnergyj,v和完成時間TaskCompletionTimej,v。這兩個變量分別通過式(4)和式(8)求得。

調度器維持一個滿足式(15)的處理節(jié)點集合P′，并從該集合中隨機選擇一個處理節(jié)點。節(jié)點v∈P′被選擇為處理節(jié)點的概率為ρv。

TaskCompletionTimej,v

(15)

(16)

在動態(tài)的無線網絡環(huán)境中，無法確保任務能夠在時間期限內完成。理由在于：1) 可能多個源節(jié)點同時將任務調度至同一個處理節(jié)點。由于在處理節(jié)點上的排隊延時，實際的執(zhí)行時間將大于估計的完成時間，導致無法滿足時間期限約束；2) 通信帶寬在多個數據傳輸間共享，使得無法給出精確的傳輸時間。

若無法滿足時間期限，調度器將增加tmargin值以避免連續(xù)的任務調度失效。若連續(xù)a1個任務調度失效，時間余量增加△t1。在接收a2個連續(xù)成功調度的任務后，調度器將減少時間余量△t2。仿真實驗中將a1和a2初始化為2，這表明若出現2個連續(xù)失效任務，調度器將以能耗增加為代價選擇計算能力更強的處理節(jié)點，從而實現成功的任務調度(滿足時間期限約束)，反之亦然。仿真實驗中△t1和△t2初始為0.05 s，且與任務的時間期限相關。對于越長的時間期限，△t1和△t2也相應越長。以上所有四個參數可以反映出自適應度概率調度算法在出現任務失效時的適應性，并作出相應優(yōu)化。例如：若調度器以確保任務完成率為目標，算法將選擇較小的a1和較大的△t1。算法2是自適應概率調度過程，并假設每個到達的任務將被置入開始時間t_start的隊列J。

算法2Adative Probability Scheduling Algorithm

輸入:neighbor table of node u from algorithm 1 and task queueJ

輸出:tasks scheduling results

功能：微云中任務與處理節(jié)點間的映射關系

1. set the number of consecutive successful tasksns=0

//設置連續(xù)成功調度任務的數量

2. set the number of consecutive failed tasksnf=0

//設置連續(xù)失效任務的數量

3.tmargin=0

//初始化時間余量

4. while (J≠?) do

//隊列不為空則從隊列中提取一個任務

5. extract taskjfromJ

6.P′← ?

//將處理節(jié)點集初始化為空

7.Pis initialized as all the processing nodes in the neighbor table

//將P初始化為鄰居列表中所有處理節(jié)點

//步驟1：尋找合格的處理節(jié)點

8. for eachv∈P

9. estimatedtaskcompletiontimej,v=tq,v+texecution+ttransmition

10. TaskEnergyj,v=ComputationEnergyj,v+CommunicationEnergyj,v

11. if (Estimatedtaskcompletiontimej,v

12.P′=P′∪v

//滿足式(15)則更新處理節(jié)點集

//步驟2：計算合格的處理節(jié)點選擇為處理節(jié)點的概率

13.for eachv∈P′

14. computingρvusing Equ.(16)

//計算處理節(jié)點選擇概率

15.randomly select processing nodew∈P′ based on probabiligyρw

//基于概率選擇處理節(jié)點

//步驟3：將任務j調度至處理節(jié)點w，并更新節(jié)點w的估

//算隊列時間

16. send taskjtow

//將任務j發(fā)送至處理節(jié)點w

17.tq,w=tq,w+Cj/mipsw

//更新鄰居列表中的tq,w

//步驟4：接收處理節(jié)點w中任務j的結果，并記錄當前時

//間t_completej

18. if (receive taskj’s result) then

19.taskcompletiontimej=t_complete-t_startj

20. if (taskcompletiontimej≤Tj) then

21.ns++

22.nf=0

23. else

24.nf++

25.ns=0

//步驟5：自適應調整時間余量tmargin

26. if (nf>a1) then

27.tmargin=tmargin+△t1

28.nf=0

29. if (ns>a2) then

30.tmargin=tmargin-△t2

31.ns=0

32. else goto line 4

自適應概率調度方法基于節(jié)點作為處理節(jié)點概率的方式選擇處理節(jié)點，并且以為節(jié)點帶來的能耗來計算概率，進而以自適應的方式調整其時間余量參數，在不可預知的網絡條件下改善任務調度性能。這種自適應的概率計算方式所選的處理節(jié)點不僅可以維持較高的任務調度成功率，還可以降低任務的平均執(zhí)行能耗。

選擇三種算法與本文算法進行了比較，包括輪轉調度算法RR、貪婪調度算法GSA以及概率調度算法PSA。RR算法以輪循環(huán)方式進行任務調度，第一個任務到達后，調度至P的第一個節(jié)點，第二任務到達即調度至P的第二個節(jié)點，依此類推。GSA算法總是將任務調度至所估計的完成時間在時間期限內的能效最高的節(jié)點上。PSA算法維持一個滿足TaskCompletionTimej,v

2.3 算例說明

利用圖3所示的節(jié)點結構組成的微云說明不同調度算法的結果，表2是相關參數配置。算例由一個語音識別應用生成。圖中有兩個源節(jié)點s0和s1，四個處理節(jié)點n0、n1、n2和n3。一個任務的數據量為4 000字節(jié)，信道帶寬為11 Mbit/s。

圖1 移動微云結構

表1 參數配置說明

參數取值情況任務到達間隔0.5 s任務數據量4 000 bytes任務計算量200 MI任務時間期限1 seno/en1/en2/en30.25/0.16/0.09/0.04 J/MImipsno/mipsn1/mipsn2/mipsn3500/400/300/200 MI/s

開始時間t=0 s，兩個源節(jié)點s0和s1開始接收任務。每0.5 s每個源節(jié)點接收一個任務。對于本文提出的自適應概率調度算法，tmargin初始化為0。若一個任務未被成功調度，則tmargin增加0.5 s；否則，tmargin減小0.5 s。由于通信能耗比計算能耗相對較小，算例分析通信能耗。根據式(5)，在處理節(jié)點n0、n1、n2和n3上執(zhí)行任務的能耗分別為50 J、32 J、18 J和8 J。

圖2是四種調度算法得到的調度結果。粗線代表s0的任務，細線代表s1的任務。實線代表執(zhí)行時間，虛線代表在處理節(jié)點上的等待時間。每條線的長度即為任務的完成時間。若線的長度大于1 s，則任務執(zhí)行失效。算例統(tǒng)計了算法得到每個任務的完成時間和能耗。利用輪轉算法RR和貪婪算法GSA，兩個源節(jié)點總是將任務調度到相同處理節(jié)點上。RR算法將任務調度至計算能力更強的節(jié)點(n0,n1)上，導致了很高的任務完成率和能耗。GSA算法總是將任務調度至能效最高的節(jié)點以滿足時間約束。因此，可能出現長時間的隊列等待，這也導致了GSA算法總是擁有最低的任務完成率。利用概率調度算法PSA，基于式(16)可將兩個源節(jié)點的任務調度至不同的處理節(jié)點上，比較GSA算法，在分配給每個處理節(jié)點的任務數量上，PSA算法僅有一個任務調度至n1，而不在n3上。然而，使用概率調度方法的確改進了很大的性能。本文的自適應概率調度算法當出現第一個失效任務時在t=1.5 s時將增加tmargin。對于s1，n2不再滿足式(15)的時間約束。因此，在t=1.5 s時，s1將任務調度至n1。這樣使得自適應概率調度算法成功地避免了一次任務失效，且其每個成功調度任務的平均能耗也得到了改進。

具體地，對于RR算法，任務完成率為75%，能耗為36 J/task；對于GSA算法，任務完成率為37.5%，能耗為34.6 J/task；對于PSA算法，任務完成率為62.5%，能耗為25.6 J/task；對于本文算法，任務完成率為75%，能耗為23.6 J/task。

(a) RR算法調度結果

(b) GSA算法調度結果

(c) PSA算法調度結果

3 仿真實驗

3.1 環(huán)境搭建

為了評估算法性能，在OMNET++[17]仿真平臺下搭建一個移動微云任務調度系統(tǒng)，由若干節(jié)點構成，其拓撲結構隨機生成，每個節(jié)點的傳輸信號范圍為40米，且具有11 Mbit/s 802.11g的無線信道傳播能力。部署三種具有不同節(jié)點密度的網絡場景進行仿真。場景1為小規(guī)模網絡，隨機在200 m×200 m的區(qū)域中部署10個節(jié)點，其中2個為源節(jié)點，8個處理節(jié)點。場景2為中規(guī)模網絡，隨機在200 m×200 m的區(qū)域中部署20個節(jié)點，其中4個為源節(jié)點，16個處理節(jié)點。場景3為大規(guī)模網絡，隨機在200 m×200 m的區(qū)域中部署40個節(jié)點，其中8個為源節(jié)點，32個處理節(jié)點。任務到達時間服從泊松分布。任務總的數據量處于[2 000,16 000] bytes之間，其他實驗參數如表2所示。

表2 仿真實驗參數配置說明

在構建移動微云任務調度系統(tǒng)時，關于節(jié)點的移動模型，OMNET++支持兩種形式的節(jié)點移動。第一種是固定網絡形式，其所有節(jié)點是固定的。第二種是移動網絡形態(tài)，其每個移動節(jié)點根據以下模式在指定區(qū)域內可以移動。其移動周期為一個隨機數，服從均值為5 s和標準差為0.1 s的均勻分布。當節(jié)點移動出現轉彎時，其移動的新方向同樣服從與之前移動相同的均勻分布。移動節(jié)點的運行速率服從[1 m/s,3 m/s]間的均勻分布。所有節(jié)點可按照隨機方向在區(qū)域內以均勻分布的速率進行移動。同時，所有節(jié)點擁有相同的初始能量等級，僅當節(jié)點在處理任務或節(jié)點處于發(fā)送/接收消息狀態(tài)時才開始消耗能量，計算能耗可用式(2)-式(4)進行計算。對于移動微云系統(tǒng)，顯然需要采用第二種移動網絡形態(tài)。此外，由于OMNET++中已有對于最優(yōu)狀態(tài)鏈路路由協(xié)議OLSR協(xié)議的擴展，本文僅需要對現有的OLSR內核進行擴展，進而實現資源發(fā)現路由過程即可。具體實現過程中，為了減少移動節(jié)點間的信息轉發(fā)數量，資源發(fā)現協(xié)議中的鏈路狀態(tài)狀態(tài)都由MRP節(jié)點產生，以便控制移動網絡中的洪泛信息傳播。

選取以下性能指標評估算性能：

1) 任務完成率：即式(10)；

2) 任務平均等待時間：即任務在處理節(jié)點上的等待與開始執(zhí)行的平均間隔時間；

3) 單個成功任務的平均能耗：即式(11)。

3.2 仿真結果

如前所述，QoS OLSR協(xié)議的控制信息在本文算法實現過程中添加了額外比特。原始QoS OLSR中，默認的Hello消息間隔為2 s，TC消息間隔為5 s。修改的QoS OSLR中，Hello消息間隔為TC消息間隔的一半，這可以確保MPR節(jié)點將帶有鄰居信息的TC消息發(fā)送至整個網絡。為了測量此時的開銷，實驗測量了小、大規(guī)模網絡中控制消息的比特數，包括HELLO消息和TC消息。平均流量開銷定義為在整個網絡中每秒傳輸控制消息的比特數，該指標可以顯示整個網絡帶寬被控制消息消耗的程度，圖3是實驗結果?？梢钥吹?，平均流量開銷幾乎隨著TC消息發(fā)送的頻率呈指數級增加。當TC消息間隔為0.2 s時，流量開銷在小、大規(guī)模網絡中約為600 KB/s和750 KB/s。在小規(guī)模網絡中，修改的QoS OLSR的流量只有輕微的增加，比原始QoS OLSR約增加2%。這是由于僅有4比特數據添加至每個Hello消息中，尤其在小規(guī)模網絡場景中，TC消息的鄰居列表的增加也是相當有限的。

圖3 控制信息的平均流量開銷

進一步觀察不同算法在不同TC消息間隔下的性能。如前所述，RR算法的TC間隔為2 s。圖4顯示，除了RR算法，其他三種算法的任務完成率首先會隨著TC消息間隔變短而增加，而在TC消息間隔達到0.2 s前則出現下降。這是由于在較長的TC消息間隔下，沒有足夠的控制消息攜帶資源信息，算法將無法獲取鄰居節(jié)點信息。當控制消息發(fā)送變頻繁時，在源節(jié)點上的資源信息將被更加頻繁地更新，進而使得任務完成率增加。然而，當流量開銷占據大部分網絡帶寬時(0.2 s的TC間隔)，算法將無法預測準確的傳輸時間。

圖4 任務完成率

RR算法并不依賴于實時的資源信息，該算法依次將任務發(fā)送至鄰居節(jié)點，因此其任務完成率是相同的。本文算法在所有情況下均具有最高的任務完成率，分別高于GSA算法和PSA算法16.6%和3.6%。因為增加tmargin，可使算法在出現任務失效時發(fā)送任務至計算能力更強的節(jié)點上，將更加可能在時間約束內完成任務。

進一步的結果如圖5所示，該圖給出了任務在處理節(jié)點上的平均等待時間。GSA算法是最高的，因為此時兩個源節(jié)點總是將任務遷移到能效最高的節(jié)點上執(zhí)行。PSA算法和本文算法通過選擇處理節(jié)點降低了多個任務在同一處理節(jié)點上的等待情況。若發(fā)生任務等待，本文算法也將選擇平均等待時間更低的節(jié)點執(zhí)行任務，此時約比GSA算法節(jié)省了2～4倍的時間。RR算法擁有最短的等待時間，因為它僅將任務均勻地發(fā)送至鄰近節(jié)點執(zhí)行。同時，圖5還表明了TC消息間隔對性能的影響。對于越短的TC消息間隔，將越能準確地獲取資源信息，因此所選擇的執(zhí)行節(jié)點越能得到更短的等待時間。

圖5 任務的平均等待時間

圖6顯示的是單個成功任務的平均能耗。除了RR算法，其他三種算法的平均能耗均是先隨著TC消息間隔的增加而增加，在TC消息間隔達到0.2 s前下降?？梢钥吹?，本文算法的平均能耗是最少的。當TC消息間隔為0.4 s時，本文算法擁有最高的任務完成率：95.14%，以及最少的能耗：1.6 J。

圖6 平均能耗

表3是大規(guī)模網絡場景下的仿真結果?？梢钥吹?，所有算法此時得到的任務完成率小于小規(guī)模網絡場景。理由在于：此時需要花更多時間在源節(jié)點與處理節(jié)點間進行數據傳輸，即：1) 多跳延時，每個中繼節(jié)點需要接收全部消息并重傳至下一跳節(jié)點；2) 信道訪問延時，更多的節(jié)點在同一時間發(fā)送數據從而導致?lián)砣Ｔ谳^短的TC消息間隔下，流量開銷更大，這也進一步影響傳輸時間。因此，任務完成率將隨著TC消息間隔變短而降低。

表3 大規(guī)模網絡場景下的實驗結果

4 結 語

基于移動微云環(huán)境，本文提出了一種基于自適應概率的任務調度算法。算法通過資源發(fā)現和自適應概率調度兩個階段尋找能效最高的任務調度解，資源發(fā)現階段通過修改原始的QoS OLSR協(xié)議中的控制信息，以發(fā)現和更新近鄰資源信息；自適應調度階段則通過概率計算方式將當前任務調度至合適的處理節(jié)點上。算法可以通過調整時間余量參數在未知的網絡條件下改進任務調度性能。仿真實驗結果表明，自適應概率調度算法在維持更高的任務完成率的情況下，可以降低單個任務成功執(zhí)行時的平均能耗。