论文题目：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。