龍 浩 張書奎 張 力

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

0 引 言

智能手機已經(jīng)成為人們?nèi)粘Ｉ钪斜夭豢扇鄙俚囊徊糠帧Ｖ悄苁謾C都配備了各種嵌入式傳感器，包括麥克風(fēng)、攝像頭、GPS、加速度計、陀螺儀、Wi-Fi/3G/4G接口等。嵌入了傳感器的智能手機可以在空氣監(jiān)測、社交網(wǎng)絡(luò)、醫(yī)療保健、交通運輸和安全等多個領(lǐng)域提供應(yīng)用和感知服務(wù)[1]。群智感知系統(tǒng)中，任務(wù)發(fā)布者通過感知平臺將感知任務(wù)采用競標的方式分配給任務(wù)參與者。收到感知任務(wù)后，參與者通過智能手機從一個或多個傳感器收集感知數(shù)據(jù)，并將感知數(shù)據(jù)發(fā)送給感知平臺，這是一個支持多種傳感應(yīng)用的多任務(wù)的系統(tǒng)。一方面，傳感器任務(wù)被分派到許多智能手機上收集數(shù)據(jù)；另一方面，智能手機承擔(dān)著為多個應(yīng)用程序生成的許多不同的感知任務(wù)。

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

1 相關(guān)工作

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

2 算法設(shè)計

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

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

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

2) 構(gòu)建感知精度模型，在滿足系統(tǒng)要求的感知精度條件下，通過迭代計算預(yù)測概率矩陣和獎勵矩陣，獲得最優(yōu)任務(wù)調(diào)度序列，實現(xiàn)了能量消耗和感知精度的最優(yōu)平衡。

3) 相對于現(xiàn)有節(jié)能算法，本文算法節(jié)能成本和計算復(fù)雜度都低于現(xiàn)有算法，平均節(jié)省能量75%以上。

3 模型構(gòu)建

3.1 系統(tǒng)模型

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

Taskt=(j,Jj,St,Qt)

(1)

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

St=(Et,Lt,Rt)

(2)

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

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

(3)

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

Et+1=Et+dt-et

(4)

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

3.2 多任務(wù)調(diào)度算法

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

(5)

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

(6)

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

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

(7)

(8)

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

圖1 任務(wù)調(diào)度流程圖

根據(jù)MDP制定可行的策略，智能手機應(yīng)用程序會根據(jù)當前狀態(tài)調(diào)整到最佳的任務(wù)調(diào)度策略。具體任務(wù)調(diào)度算法如算法1所示。

算法1基于馬爾科夫決策過程的高能效任務(wù)調(diào)度算法

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

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

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

//任務(wù)調(diào)度問題的構(gòu)建

2: 感知數(shù)據(jù)正確精度Qt的構(gòu)建

4:w←w∪wj

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

5: min(w)

//尋找任務(wù)調(diào)度的最佳時間集合

6: end

//任務(wù)調(diào)度序列的構(gòu)建(min函數(shù))

7: 矩陣Pt和Rt的構(gòu)建

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

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

4 仿真與性能分析

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

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

圖2 不同任務(wù)數(shù)量下智能手機耗能

圖3為三種算法在不同任務(wù)持續(xù)時間下的智能手機能耗?？梢钥闯觯S著任務(wù)持續(xù)時間的增加，手機的能耗呈單調(diào)增長。感知任務(wù)的持續(xù)時間越長收集的數(shù)據(jù)就越多，消耗的能量也會增加。本文算法與Baseline方法相比節(jié)能效果明顯，也優(yōu)于Opt-MESS方法。

圖3 不同任務(wù)持續(xù)時間下智能手機能耗

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

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

圖5為三種算法在不同任務(wù)感知周期下的智能手機能耗?？梢钥闯?，我們的算法相比Baseline方法和Opt-MESS方法平均節(jié)能75.2%和17.3%。此外，當傳感周期較短時，節(jié)能效果更顯著。這是因為在較短的感知時間內(nèi)，感知任務(wù)更有可能在相同或相似的時間內(nèi)請求普通傳感器的數(shù)據(jù)。因此，本文算法可以實現(xiàn)更好的節(jié)能。

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

5 結(jié) 語

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