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

錄用時間：2020年5月21日

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

作者列表：

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

（2）張陳祥，中國石油大學（北京），信息科學與工程學院，2015級本科生

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

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

摘要：

隨著物聯網（IoT）的出現，將不同傳感器的數據集成在一起的傳感器集線器發揮著越來越重要的作用。能源效率是傳感器集線器最需要考慮的問題之一。為了應對這一挑戰，本文提出了一種傳感器集線器任務調度方案，來提高集線器的能效。本文設計了一種基于多隊列的框架，給出了理論模型和數學分析。利用李雅普諾夫優化技術對模型進行優化，提出了一種傳感器集線器的節能任務調度算法。最后，基于車聯網環境下的真實數據進行了仿真實驗，驗證了該方法的有效性。

背景與動機：

隨著物聯網(IoT)的出現，傳感器的數量呈指數級增長。為了更高效地連接和管理傳感器或設備，通過設計和部署傳感器集線器集成來自不同傳感器的數據，從而節省能耗。因此，傳感器集線器在現實中得到了廣泛的應用，從個人智能手機(如Apple iPhone，Google Nexus)到大型物聯網(IoT)系統。

通常，有多個感應設備連接到一個感應集線器。在傳感器集線器中，來自傳感器的數據首先被緩沖，等待單片機(MCU)進一步的處理，直到緩沖區中積累了一定數量的數據。傳感數據可以由傳感器集線器批量處理或上傳到連接到傳感器集線器的服務器上。

隨著傳感器集線器的增加，能效成為一個重要問題。有些傳感器集線器采用嵌入式電池供電，要求電池能耗低并且處理效率高。除了同步集成傳感器數據外，傳感器集線器還可以通過在空閑時關閉電源來減少能源消耗。然而，如何根據工作負載動態地確定傳感器集線器的工作狀態，以實現性能穩定性和能耗之間的權衡，仍是一個很大的問題。

為此，我們設計了一種任務調度方案，該方案能夠根據傳感器集線器的工作負荷動態調整傳感器集線器的工作狀態，在性能穩定性和能耗之間實現最優平衡。

設計與實現：

1）任務調度優化模型

圖1. 多隊列任務調度模型

首先，我們考慮一個多隊列任務調度模型。如圖1所示。所有的傳感器集線器都有一個或多個緩沖區，到達傳感器集線器的任務將被分配到不同的隊列中。設為t-1到t區間內到達第i個隊列的任務數，為到達傳感器集線器的任務總數。表示第i個隊列的狀態，即該隊列中緩沖的請求數量。在每個決策時期，我們的方案控制傳感器集線器的工作狀態，它決定了每個隊列中提交或處理的數據量。設表示從t-1到t第i個隊列上傳或處理的請求數量，為當前狀態下該時間間隔內上傳請求數據的上限。

在每個決策時期，第i個隊列的狀態通過聯合考慮其之前的狀態、任務到達和完成的工作來更新。于是我們可以得到隊列的更新公式：

為了保證隊列的穩定性，每個隊列在穩態(當隊列趨于無窮大時)的狀態都應該是有界的。從理論上講，這種穩定約束可以表示為:

為了優化傳感器集線器的能效，我們首先定義了t到t+1這段時間內的獎勵效益函數，如式(3)所示。即任務到達的總和除以功耗。

其中，p(t)表示t到t+1時間間隔的功耗。我們的目標是通過合理設置電源狀態、隊列之間的任務分配以及每個隊列的上傳或處理的請求數量，優化系統的長期獎勵。換句話說，期望在穩態(即t趨于無窮時)下，傳感器集線器的獎勵最大化。綜上所述，傳感器集線器節能任務調度的數學優化模型可以表示為:

2）任務調度優化算法：

我們將利用李雅普諾夫優化技術解決所提出的優化目標。首先，我們將定義為隊列狀態的向量，即公式(5)。將表示為李雅普諾夫函數，定義為公式(6)，表示隊列的擁塞狀態，函數值越大，隊列越擁塞。

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

利用李雅普諾夫優化技術以及排隊模型，我們可以得到W的上界：

因此，我們將原優化問題轉化為上界極小化問題：

通過整理，可以將上述優化目標轉化為求解(11)和(12)兩個優化問題來確定決策變量和的值。這兩個優化問題可以用線性規劃的算法來進行求解。

根據上述公式和分析，我們就能得到傳感器集線器的節能任務調度算法，如算法1所示。

3）實驗評估

為了驗證我們的方法在現實環境中的有效性，我們基于真實的數據集“T-Drive”在車聯網的環境中進行了模擬實驗。根據“T-Drive”數據集中的信息生成任務，實現調度算法，并對實驗數據進行采集和分析。

圖2. 參數V與獎勵值的關系

圖3. 參數V與損失率的關系

圖2給出了不同參數V的獎勵值的實驗結果。由圖可知，隨著V的增加，獎勵就會增加。但當V足夠大(即大于30)時，V的增加對獎勵的影響就不那么顯著了。原因是，當V值較大時，隊列狀態對決策變量的影響較小，使得調度算法總是試圖填滿緩沖區。圖3給出參數V和損失率的關系。隨著V的增大，損失率增大。說明當我們的方案試圖在V變大時填滿緩沖區時，更有可能導致隊列擁擠，從而導致更高的丟失率。

圖4. 不同算法的比較

最后，我們將我們的方法與現實中廣泛應用的一些算法進行了比較。第一種算法是“Autofit”，即根據隊列狀態動態調整功率狀態，但忽略了未來隊列擁塞的可能性。第二種算法是固定傳感器集線器的CPU或MCU，保持最大的功耗。實驗結果如圖4所示。實驗結果表明，我們的方法能夠實現最高的獎勵值。該算法的性能優于其他兩種算法，驗證了該算法的有效性。

作者簡介

黃霽崴博士，教授，博士生導師，石油數據挖掘北京市重點實驗室主任，中國石油大學（北京）計算機科學與技術系主任。2015年度北京市優秀人才，2018年度中國石油大學（北京）優秀青年學者，2020年度北京市科技新星。分別在2009年和2014年于清華大學計算機科學與技術系獲得工學學士和工學博士學位，2012-2013年國家公派赴美國佐治亞理工學院聯合培養。研究方向包括：系統性能評價和優化、隨機模型理論和應用、服務質量測量與保障技術、服務計算和物聯網等。擔任中國計算機學會（CCF）服務計算專委會委員，CCF高級會員，IEEE、ACM會員。已主持國家自然科學基金、北京市自然科學基金等科研項目13項，在國內外著名期刊和會議發表論文五十余篇，出版學術專著1部，獲得國家發明專利5項、軟件著作權3項，擔任多個國際頂級期刊和知名會議審稿人。聯系郵箱：huangjw@cup.edu.cn。

99亚洲综合精品