論文題目：A Multi-queue Approach of Energy Efficient Task Scheduling for Sensor Hubs

錄用時(shí)間：2020年5月21日

錄用期刊：Chinese Journal of Electronics（JCR Q4）

作者列表：

（1）黃霽崴，中國(guó)石油大學(xué)（北京），信息科學(xué)與工程學(xué)院，教授

（2）張陳祥，中國(guó)石油大學(xué)（北京），信息科學(xué)與工程學(xué)院，2015級(jí)本科生

（3）張建兵，中國(guó)石油大學(xué)（北京），信息科學(xué)與工程學(xué)院，講師

DOI鏈接：http://dx.doi.org/10.1049/cje.2020.02.001

摘要：

隨著物聯(lián)網(wǎng)（IoT）的出現(xiàn)，將不同傳感器的數(shù)據(jù)集成在一起的傳感器集線(xiàn)器發(fā)揮著越來(lái)越重要的作用。能源效率是傳感器集線(xiàn)器最需要考慮的問(wèn)題之一。為了應(yīng)對(duì)這一挑戰(zhàn)，本文提出了一種傳感器集線(xiàn)器任務(wù)調(diào)度方案，來(lái)提高集線(xiàn)器的能效。本文設(shè)計(jì)了一種基于多隊(duì)列的框架，給出了理論模型和數(shù)學(xué)分析。利用李雅普諾夫優(yōu)化技術(shù)對(duì)模型進(jìn)行優(yōu)化，提出了一種傳感器集線(xiàn)器的節(jié)能任務(wù)調(diào)度算法。最后，基于車(chē)聯(lián)網(wǎng)環(huán)境下的真實(shí)數(shù)據(jù)進(jìn)行了仿真實(shí)驗(yàn)，驗(yàn)證了該方法的有效性。

背景與動(dòng)機(jī)：

隨著物聯(lián)網(wǎng)(IoT)的出現(xiàn)，傳感器的數(shù)量呈指數(shù)級(jí)增長(zhǎng)。為了更高效地連接和管理傳感器或設(shè)備，通過(guò)設(shè)計(jì)和部署傳感器集線(xiàn)器集成來(lái)自不同傳感器的數(shù)據(jù)，從而節(jié)省能耗。因此，傳感器集線(xiàn)器在現(xiàn)實(shí)中得到了廣泛的應(yīng)用，從個(gè)人智能手機(jī)(如Apple iPhone，Google Nexus)到大型物聯(lián)網(wǎng)(IoT)系統(tǒng)。

通常，有多個(gè)感應(yīng)設(shè)備連接到一個(gè)感應(yīng)集線(xiàn)器。在傳感器集線(xiàn)器中，來(lái)自傳感器的數(shù)據(jù)首先被緩沖，等待單片機(jī)(MCU)進(jìn)一步的處理，直到緩沖區(qū)中積累了一定數(shù)量的數(shù)據(jù)。傳感數(shù)據(jù)可以由傳感器集線(xiàn)器批量處理或上傳到連接到傳感器集線(xiàn)器的服務(wù)器上。

隨著傳感器集線(xiàn)器的增加，能效成為一個(gè)重要問(wèn)題。有些傳感器集線(xiàn)器采用嵌入式電池供電，要求電池能耗低并且處理效率高。除了同步集成傳感器數(shù)據(jù)外，傳感器集線(xiàn)器還可以通過(guò)在空閑時(shí)關(guān)閉電源來(lái)減少能源消耗。然而，如何根據(jù)工作負(fù)載動(dòng)態(tài)地確定傳感器集線(xiàn)器的工作狀態(tài)，以實(shí)現(xiàn)性能穩(wěn)定性和能耗之間的權(quán)衡，仍是一個(gè)很大的問(wèn)題。

為此，我們?cè)O(shè)計(jì)了一種任務(wù)調(diào)度方案，該方案能夠根據(jù)傳感器集線(xiàn)器的工作負(fù)荷動(dòng)態(tài)調(diào)整傳感器集線(xiàn)器的工作狀態(tài)，在性能穩(wěn)定性和能耗之間實(shí)現(xiàn)最優(yōu)平衡。

設(shè)計(jì)與實(shí)現(xiàn)：

1）任務(wù)調(diào)度優(yōu)化模型

圖1. 多隊(duì)列任務(wù)調(diào)度模型

首先，我們考慮一個(gè)多隊(duì)列任務(wù)調(diào)度模型。如圖1所示。所有的傳感器集線(xiàn)器都有一個(gè)或多個(gè)緩沖區(qū)，到達(dá)傳感器集線(xiàn)器的任務(wù)將被分配到不同的隊(duì)列中。設(shè)為t-1到t區(qū)間內(nèi)到達(dá)第i個(gè)隊(duì)列的任務(wù)數(shù)，為到達(dá)傳感器集線(xiàn)器的任務(wù)總數(shù)。表示第i個(gè)隊(duì)列的狀態(tài)，即該隊(duì)列中緩沖的請(qǐng)求數(shù)量。在每個(gè)決策時(shí)期，我們的方案控制傳感器集線(xiàn)器的工作狀態(tài)，它決定了每個(gè)隊(duì)列中提交或處理的數(shù)據(jù)量。設(shè)表示從t-1到t第i個(gè)隊(duì)列上傳或處理的請(qǐng)求數(shù)量，為當(dāng)前狀態(tài)下該時(shí)間間隔內(nèi)上傳請(qǐng)求數(shù)據(jù)的上限。

在每個(gè)決策時(shí)期，第i個(gè)隊(duì)列的狀態(tài)通過(guò)聯(lián)合考慮其之前的狀態(tài)、任務(wù)到達(dá)和完成的工作來(lái)更新。于是我們可以得到隊(duì)列的更新公式：

為了保證隊(duì)列的穩(wěn)定性，每個(gè)隊(duì)列在穩(wěn)態(tài)(當(dāng)隊(duì)列趨于無(wú)窮大時(shí))的狀態(tài)都應(yīng)該是有界的。從理論上講，這種穩(wěn)定約束可以表示為:

為了優(yōu)化傳感器集線(xiàn)器的能效，我們首先定義了t到t+1這段時(shí)間內(nèi)的獎(jiǎng)勵(lì)效益函數(shù)，如式(3)所示。即任務(wù)到達(dá)的總和除以功耗。

其中，p(t)表示t到t+1時(shí)間間隔的功耗。我們的目標(biāo)是通過(guò)合理設(shè)置電源狀態(tài)、隊(duì)列之間的任務(wù)分配以及每個(gè)隊(duì)列的上傳或處理的請(qǐng)求數(shù)量，優(yōu)化系統(tǒng)的長(zhǎng)期獎(jiǎng)勵(lì)。換句話(huà)說(shuō)，期望在穩(wěn)態(tài)(即t趨于無(wú)窮時(shí))下，傳感器集線(xiàn)器的獎(jiǎng)勵(lì)最大化。綜上所述，傳感器集線(xiàn)器節(jié)能任務(wù)調(diào)度的數(shù)學(xué)優(yōu)化模型可以表示為:

2）任務(wù)調(diào)度優(yōu)化算法：

我們將利用李雅普諾夫優(yōu)化技術(shù)解決所提出的優(yōu)化目標(biāo)。首先，我們將定義為隊(duì)列狀態(tài)的向量，即公式(5)。將表示為李雅普諾夫函數(shù)，定義為公式(6)，表示隊(duì)列的擁塞狀態(tài)，函數(shù)值越大，隊(duì)列越擁塞。

接下來(lái)，我們定義條件李雅普諾夫漂移函數(shù)，即（7）式，的值越小，隊(duì)列擁塞程度越小。然后定義李雅普諾夫漂移—懲罰函數(shù)，如公式(8)所示，其中V為權(quán)衡參數(shù)。為了保證在隊(duì)列穩(wěn)定的狀態(tài)下獎(jiǎng)勵(lì)值最大，我們期望W的值越小越好。

利用李雅普諾夫優(yōu)化技術(shù)以及排隊(duì)模型，我們可以得到W的上界：

因此，我們將原優(yōu)化問(wèn)題轉(zhuǎn)化為上界極小化問(wèn)題：

通過(guò)整理，可以將上述優(yōu)化目標(biāo)轉(zhuǎn)化為求解(11)和(12)兩個(gè)優(yōu)化問(wèn)題來(lái)確定決策變量和的值。這兩個(gè)優(yōu)化問(wèn)題可以用線(xiàn)性規(guī)劃的算法來(lái)進(jìn)行求解。

根據(jù)上述公式和分析，我們就能得到傳感器集線(xiàn)器的節(jié)能任務(wù)調(diào)度算法，如算法1所示。

3）實(shí)驗(yàn)評(píng)估

為了驗(yàn)證我們的方法在現(xiàn)實(shí)環(huán)境中的有效性，我們基于真實(shí)的數(shù)據(jù)集“T-Drive”在車(chē)聯(lián)網(wǎng)的環(huán)境中進(jìn)行了模擬實(shí)驗(yàn)。根據(jù)“T-Drive”數(shù)據(jù)集中的信息生成任務(wù)，實(shí)現(xiàn)調(diào)度算法，并對(duì)實(shí)驗(yàn)數(shù)據(jù)進(jìn)行采集和分析。

圖2. 參數(shù)V與獎(jiǎng)勵(lì)值的關(guān)系

圖3. 參數(shù)V與損失率的關(guān)系

圖2給出了不同參數(shù)V的獎(jiǎng)勵(lì)值的實(shí)驗(yàn)結(jié)果。由圖可知，隨著V的增加，獎(jiǎng)勵(lì)就會(huì)增加。但當(dāng)V足夠大(即大于30)時(shí)，V的增加對(duì)獎(jiǎng)勵(lì)的影響就不那么顯著了。原因是，當(dāng)V值較大時(shí)，隊(duì)列狀態(tài)對(duì)決策變量的影響較小，使得調(diào)度算法總是試圖填滿(mǎn)緩沖區(qū)。圖3給出參數(shù)V和損失率的關(guān)系。隨著V的增大，損失率增大。說(shuō)明當(dāng)我們的方案試圖在V變大時(shí)填滿(mǎn)緩沖區(qū)時(shí)，更有可能導(dǎo)致隊(duì)列擁擠，從而導(dǎo)致更高的丟失率。

圖4. 不同算法的比較

最后，我們將我們的方法與現(xiàn)實(shí)中廣泛應(yīng)用的一些算法進(jìn)行了比較。第一種算法是“Autofit”，即根據(jù)隊(duì)列狀態(tài)動(dòng)態(tài)調(diào)整功率狀態(tài)，但忽略了未來(lái)隊(duì)列擁塞的可能性。第二種算法是固定傳感器集線(xiàn)器的CPU或MCU，保持最大的功耗。實(shí)驗(yàn)結(jié)果如圖4所示。實(shí)驗(yàn)結(jié)果表明，我們的方法能夠?qū)崿F(xiàn)最高的獎(jiǎng)勵(lì)值。該算法的性能優(yōu)于其他兩種算法，驗(yàn)證了該算法的有效性。

作者簡(jiǎn)介

黃霽崴博士，教授，博士生導(dǎo)師，石油數(shù)據(jù)挖掘北京市重點(diǎn)實(shí)驗(yàn)室主任，中國(guó)石油大學(xué)（北京）計(jì)算機(jī)科學(xué)與技術(shù)系主任。2015年度北京市優(yōu)秀人才，2018年度中國(guó)石油大學(xué)（北京）優(yōu)秀青年學(xué)者，2020年度北京市科技新星。分別在2009年和2014年于清華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系獲得工學(xué)學(xué)士和工學(xué)博士學(xué)位，2012-2013年國(guó)家公派赴美國(guó)佐治亞理工學(xué)院聯(lián)合培養(yǎng)。研究方向包括：系統(tǒng)性能評(píng)價(jià)和優(yōu)化、隨機(jī)模型理論和應(yīng)用、服務(wù)質(zhì)量測(cè)量與保障技術(shù)、服務(wù)計(jì)算和物聯(lián)網(wǎng)等。擔(dān)任中國(guó)計(jì)算機(jī)學(xué)會(huì)（CCF）服務(wù)計(jì)算專(zhuān)委會(huì)委員，CCF高級(jí)會(huì)員，IEEE、ACM會(huì)員。已主持國(guó)家自然科學(xué)基金、北京市自然科學(xué)基金等科研項(xiàng)目13項(xiàng)，在國(guó)內(nèi)外著名期刊和會(huì)議發(fā)表論文五十余篇，出版學(xué)術(shù)專(zhuān)著1部，獲得國(guó)家發(fā)明專(zhuān)利5項(xiàng)、軟件著作權(quán)3項(xiàng)，擔(dān)任多個(gè)國(guó)際頂級(jí)期刊和知名會(huì)議審稿人。聯(lián)系郵箱：[email protected]。