基于馬爾科夫決策過程的高能效任務調度算法

龍 浩 張書奎 張 力

1(蘇州大學計算機科學與技術學院 江蘇 蘇州 215006)2(徐州工業職業技術學院信息與電氣工程學院 江蘇 徐州 221002)

0 引 言

智能手機已經成為人們日常生活中必不可缺少的一部分。智能手機都配備了各種嵌入式傳感器，包括麥克風、攝像頭、GPS、加速度計、陀螺儀、Wi-Fi/3G/4G接口等。嵌入了傳感器的智能手機可以在空氣監測、社交網絡、醫療保健、交通運輸和安全等多個領域提供應用和感知服務[1]。群智感知系統中，任務發布者通過感知平臺將感知任務采用競標的方式分配給任務參與者。收到感知任務后，參與者通過智能手機從一個或多個傳感器收集感知數據，并將感知數據發送給感知平臺，這是一個支持多種傳感應用的多任務的系統。一方面，傳感器任務被分派到許多智能手機上收集數據；另一方面，智能手機承擔著為多個應用程序生成的許多不同的感知任務。

一般來說，從智能手機傳感器收集數據是非常耗能的。如果傳感器活動沒有以節能的方式仔細管理，智能手機有限的電量可能很快就會耗盡。具體地說，它需要智能手機主動執行掃描，以獲得一些傳感器的(如Wi-Fi接口)狀態；同時，它還需要產生一個線程來獲取一些其他傳感器(如加速度計)的讀數。此外，一些傳感器(如GPS)是一直消耗電量的。為了最大限度地減少能源消耗，文獻[2]提出了一些特定于應用程序的算法，這些算法可以阻止針對特定應用程序控制特定傳感器(如GPS)的采樣和能源使用。此外，文獻[3]還研究了在群智感知系統中如何生成并分配感知任務給參與的智能手機。然而，以最小化傳感能耗為目標的智能手機傳感任務調度問題一直沒有得到足夠的重視。為了解決這一問題，一方面利用馬爾可夫決策過程制定有效的任務調度策略，將傳感器耗能與智能手機當前電量考慮在內，并將基于MDP的策略感知與其他直觀策略(如隨機或連續感知)的性能進行比較。另一方面，由于多個傳感器任務可能在同一時刻或相似時刻向同一個傳感器請求數據，我們可以在它們之間共享傳感器數據，以避免重復工作。

1 相關工作

感知任務調度和優化問題已經在特定的群智感知應用程序中得到了解決。文獻[4]中設計了一個模擬器，根據能源需求比較了不同的數據收集架構。然而，移動群智感知架構旨在盡量減少能源消耗，以便鼓勵更多的用戶參與。文獻[5]提出了一種自適應的位置感知框架，顯著提高了運行基于位置應用的智能手機的能源效率。該框架的基本設計原則包括替代、抑制、承載和應用定位感知請求的適應，以節約能源。文獻[6]解決了群體感知應用程序所消耗的能源問題。作者指出，在室內人群感知的情況下，該設備收集位置數據和感知數據。提出了服務器端定位技術，通過分析智能手機與服務器端無線接入點(APs)的信標交換來定位智能手機。因此，只需要發送傳感數據，從而節省了發送位置數據所消耗的能源。然而這種技術很大程度上依賴于基礎設施，可能會減少安全問題。通過調度使能量消耗最小化的方法在少數文獻中得到了討論。文獻[7]討論了能量消耗的感知數據量是最重要的問題之一。通過對數據的調度，可以減少對數據的感知和傳輸所消耗的能量。文獻[8]研究了分配給智能手機的各種感知任務的調度問題，目的是在感知的同時最小化所消耗的能量，并保持感知數據的質量(QoSS)。在文獻[9]中，作者對覆蓋給定地理區域的非受控移動傳感器的信息報告速率給出了分析結果。文獻[10]引入了自動映射城市區域的機制，為應用程序提供了一個虛擬傳感器抽象，并提出了用于測量獲取數據質量的時空覆蓋度量標準。文獻[11]提出了高效節能的傳感調度算法，并通過仿真表明，通過聯合實驗室傳感可以實現顯著的節電。

2 算法設計

本文工作不同于以上文獻研究內容。首先不同于針對具體應用的節能傳感調度或優化研究，本文的研究目標是解決一般移動群智感知系統中的任務調度問題。其次目前算法主要研究如何將任務分配給一組參與者的問題，但我們考慮的問題是調度不同的傳感任務分配給智能手機不同傳感器。智能手機用于感知，取決于什么時候參與群智感知，取決于設備的條件。調度機制[7]可以解決這一問題，但評估設備的當前負載等現狀，充電概率在這里起著關鍵作用。在文獻[12-13]中，MDP被用于制定電池管理技術，形成不同的能耗任務之間的平衡，但沒有應用于群智感知。因此，該問題可以更好地利用馬爾可夫決策過程試圖根據不同的計算狀態和輸入概率動態地構造要采用的策略。因此，本文應用MDP根據設備上的電流負載、剩余能量和充電概率這三個因素提出了一種有效的感知任務調度策略。

我們設計了一種基于馬爾科夫決策過程的高能效任務調度算法。目前研究群智感知任務能耗問題主要基于兩個方面，第一方面是針對群智感知系統的整個架構和網絡硬件設備方面的改進；另一方面是針對感知任務和數據的傳輸和處理方面。這兩方面涉及的范圍比較廣，實現成本和難度都比較大。本文從感知任務實際使用的傳感器出發，綜合考慮智能手機設備的當前狀況和感知精度，計算出最佳任務調度時間序列，從而實現感知過程的節能。具體的創新有3個方面：

1) 定義了當前感知任務的狀態，包括當前手機的狀態和感知精度要求，并定義與感知能耗相關的獎勵值，為馬爾科夫決策計算感知任務的下一個狀態提供計算依據。

2) 構建感知精度模型，在滿足系統要求的感知精度條件下，通過迭代計算預測概率矩陣和獎勵矩陣，獲得最優任務調度序列，實現了能量消耗和感知精度的最優平衡。

3) 相對于現有節能算法，本文算法節能成本和計算復雜度都低于現有算法，平均節省能量75%以上。

3 模型構建

3.1 系統模型

本文的系統模型是基于兩層服務器-客戶端架構，其中客戶端智能手機應用程序通過網絡連接到群智感知服務器，智能手機定期檢測、匯總和發送收集的數據到服務器。問題的構建是智能手機調度任務使得最大化感知精度和最小化能量消耗成本達到平衡。我們考慮了一個通用的多任務移動群智感知系統，研究一種需要承擔一組涉及各種傳感器的感知任務的調度問題。感知任務由如下四元組給出：

Taskt=(j,Jj,St,Qt)

(1)

式中：j代表任務的編號，Jj表示多傳感器任務j中傳感器編號的集合，St表示手機當前的狀態，根據在某一t時刻，手機的剩余電量Et，目前的感知狀態Lt以及再充電的可能性Rt確定，Qt表示感知數據的質量。決策者觀察手機的當前狀態St，然后從給定的任務序列Task中調度任務，在t時刻的系統當前狀態可以表示為：

St=(Et,Lt,Rt)

(2)

式中：Et∈{0,1,2,…,N}表示智能手機在t時刻能量的可用狀態。Lt∈{0,1}，0表示系統運行了耗電量較低的應用程序，1表示系統運行了關鍵且耗電量大的應用程序。Rt∈{0,1}，0表示設備沒有連接充電電源，1表示設備連接了充電電源。

本文考慮了一個離散時間模型，該模型以單位長度為間隔，每個間隔的運行負載被認為是相同。由于智能手機操作系統使用了時分多路復用，因此這種推斷是合乎邏輯的。智能手機包含兩個狀態進程，即當前時刻狀態和下一個時刻狀態。兩個狀態進程用于關聯智能手機當前的操作負載，系統在下一個時間間隔執行重負載的可能為ph，非負載的可能則為1-ph。另外系統在下一個時間間隔執行一般負載的可能為pl，非負載的可能為1-pl。這里我們考慮0.5

(3)

式中：λt表示感知任務的平臺獎勵。式(3)包含4種情況，表示的是參與者獲得的獎勵由平臺的獎勵和參與者耗電成本的差值。為了最大化獎勵Λ(St,Taskt)，智能手機通過對任務進行調度從當前狀態St達到下一個狀態St+1=(Et+1,Lt+1,Rt+1)，其中：

Et+1=Et+dt-et

(4)

式中：dt是重新充電的電量，dt=Rtqr+(1-Rt)(1-qr)。下一階段系統的感知狀態Lt+1=Ltph+(1-Lt)(1-pl)。et是感知過程耗費的電量，et=e1+e2+e3，其中e1表示智能手機保持活動狀態所需的最低電量，低于該電量設備將停止工作，e2表示由感知應用消耗的電量，e3表示智能手機系統消耗的電量。

3.2 多任務調度算法

為了節約能源，我們認為傳感器感知可能不需要精確地在系統要求的時間內進行，因為一些傳感器(如光、溫度等)的讀數可能會隨著時間的推移而緩慢地變化。它們可以在與請求的條件稍有不同的時間瞬間收集。然而，我們需要確保Qt保持在一個可以接受的范圍。如果智能手機被要求在t時刻從傳感器收集讀數，但數據是在t′時刻收集的，則這個感知動作的準確性是ΓC(t,t′)∈[0,1]。t′越接近t，ΓC(t,t′)的值就越大，感知數據也就越準確。在此，我們構建了一種通用的ΓC(t,t′)模型，以便其他方法都可以用它來估計感知精度。與文獻[14]類似，具體模型函數如下所示，取值范圍在0到1之間：

(5)

式中：σ用來構建不同的傳感器讀數。假設感知任務Taskt在t′時刻采集感知數據，其ΓC(t,t′)≥Qt，我們就可以認為該任務的完成達到了感知平臺的要求。由于不同的應用程序可能需要不同的感知精度，Qt被定義為特定任務的參數，該參數隨感知任務的不同而變化。因此任務的調度問題就變成了尋找此類時間瞬間的“最佳”子集的問題。多傳感器多任務調度問題定義如下：

(6)

根據3.1節中系統模型，在任意時刻t，當前手機狀態St到下一時刻的手機狀態St+1的預測概率可以用矩陣Pt=PEt→Et+1×PLt→Lt+1×PRt→Rt+1來表示。每一個狀態根據式(3)獲得對應可能的獎勵，并構成獎勵矩陣Rt。通過值迭代函數構建MDP公式，針對任意平穩策略π=(π0,π1,…)，狀態值函數在狀態x∈X滿足貝爾曼方程[15]:

Vπ(x)=R(x,π(x))+γ∑yP(y|x,π(x))Vπ(y)

(7)

(8)

調度算法整個流程的工作流程及其實現如圖1所示。MDP公式構建后，預測概率矩陣Pt和獎勵矩陣Rt被代入值迭代函數，迭代計算后獲得三個值，包括最大利用率、實現目標的決策和耗費時間。根據最終迭代計算結果，獲得式(6)中最優任務調度序列。因此，可以根據這種預先計算的策略制定戰略決策，通過任務調度使感知任務能量消耗和感知精度獲得最優平衡。

圖1 任務調度流程圖

根據MDP制定可行的策略，智能手機應用程序會根據當前狀態調整到最佳的任務調度策略。具體任務調度算法如算法1所示。

算法1基于馬爾科夫決策過程的高能效任務調度算法

輸入:ph,pl,pr,γ,,{λ1,λ2,…}

輸出: Task={Task1,Task2,…,Taskn}

1:tij←{?};Vi∈{1,…,N};Vj∈{1,…,M};Task←{?}

//任務調度問題的構建

2: 感知數據正確精度Qt的構建

4:w←w∪wj

//w為傳感器能耗的集合

5: min(w)

//尋找任務調度的最佳時間集合

6: end

//任務調度序列的構建(min函數)

7: 矩陣Pt和Rt的構建

8: for (i=1 to N) do

9: for (j=1 to M) do

10: if (maxs|Vt+1(S)-Vt(S)|<)

11:Task←Task∪Taskt

12: end

13: return Task

算法主要分為兩個部分，第一部分構建評價任務感知數據的精度模型，通過感知數據的精度模型構建尋找任務調度的最小傳感器能耗和最大感知精度的最佳任務調度時間序列。第二部分min函數的實現，通過馬爾科夫決策過程迭代計算出下一時刻最佳任務調度時間，將該任務加入到調度序列。

4 仿真與性能分析

為了實現和檢查策略的有效性，我們設計了一個基于Android的群智感知應用程序，并與廣泛使用的Baseline方法和Opt-MESS方法進行性能比較，以驗證所提出算法的有效性。Baseline方法安排傳感器在要求的時間內準確地收集讀數，Opt-MESS方法要求傳感器在線性規劃和貪婪計算后的時間點收集數據，本文算法由于考慮節能，在保證感知精度的某一個時間點收集數據。仿真實驗通過隨機生成傳感器任務在不同的時間點收集數據，并計算傳感器功耗作為感知任務消耗的能耗，因此將能耗作為性能評價的主要指標。我們考慮了6個常用的嵌入傳感器，包括GPS、光傳感器、加速度計、陀螺儀、Wi-Fi和4G。首先，使用從谷歌Nexus 4[16]智能手機的功率分布圖中獲得這些傳感器功耗的真實數據，將其乘以估計的持續時間得到功耗。然后，設置感知數據收集時間點，將感知調度周期設置為12小時(比如從早上8點到晚上8點)，以2分鐘為間隔，獲得一個均勻等間隔的時間序列，可以根據此序列收集感知數據。最后隨機生成傳感器任務，從6個傳感器中隨機選擇傳感器集。每個任務的持續時間從1小時到6小時變化，從[1,6]中隨機選擇開始時間，使其結束時間不超過12小時。精度要求從0.5到1進行變換，任務數量從5到30改變，步驟大小為5。我們通過改變任務的數量、任務的持續時間和任務感知精度的要求，對提出的算法進行了全面的性能評估。實驗結果取100輪的平均值。

圖2為三種算法在不同任務數量下的智能手機能耗。可以看出，無論使用哪種算法，能量消耗都是隨著任務數量的單調增加而增加的。這是因為，感知任務越多，感知所需的時間瞬間越多，無論進行何種優化，都會導致更高的能耗。與Baseline方法相比，本文算法的手機能耗平均降低75.8%；與目前最新提出的Opt-MESS方法相比，能耗平均降低18.4%。此外，當感知任務數量變得越來越大時，能源節約變得越來越重要。本文算法在移動群智感知系統中，根據任務的需求，有策略地調度任務收集數據，可以在不犧牲太多感知精度的情況下實現顯著節能。

圖2 不同任務數量下智能手機耗能

圖3為三種算法在不同任務持續時間下的智能手機能耗。可以看出，隨著任務持續時間的增加，手機的能耗呈單調增長。感知任務的持續時間越長收集的數據就越多，消耗的能量也會增加。本文算法與Baseline方法相比節能效果明顯，也優于Opt-MESS方法。

圖3 不同任務持續時間下智能手機能耗

圖4為三種算法在不同感知精度下的智能手機能耗。可以看出，能量消耗和任務感知精度之間的權衡：無論使用哪種算法，能源消耗都隨著感知精度的需求單調增長，但增長非常緩慢。增加感知精度需求無疑會增加能源消耗，因為需要在更多的時刻收集更多的讀數來滿足需求。無論如何，將感知精度需求設置為相對合適的值(比如0.8或0.9)才能取得最佳的能耗，因為這樣做不會導致過度的能耗增加。當所有任務的感知精度需求為1時，三種算法的能耗都非常接近。

圖4 不同任務感知精度下智能手機能耗

圖5為三種算法在不同任務感知周期下的智能手機能耗。可以看出，我們的算法相比Baseline方法和Opt-MESS方法平均節能75.2%和17.3%。此外，當傳感周期較短時，節能效果更顯著。這是因為在較短的感知時間內，感知任務更有可能在相同或相似的時間內請求普通傳感器的數據。因此，本文算法可以實現更好的節能。

圖5 不同任務感知周期下智能手機能耗

5 結 語

智能手機提供了傳感、通信和計算的獨特設備，開啟了移動群智感知的新興應用范例。群智感知應用通常會消耗相當數量的手機能量。因此，本文提出了一 種基于MDP 的高效節能群智感知任務調度策略。通 過對公式的求解，提出了一種根據設備狀態動態確定 群智感知任務調度的算法。在Android 應用程序中實 現了用于不同任務數量、任務持續時間和任務感知精 度數據的收集。大量的仿真結果表明，與其他策略相 比，發現基于MDP 的策略可以在不同負載條件下平均 節省能量75%以上。