物联网环境下基于用户满意度的实时调度算法*

2015-03-27王永炎

计算机工程与科学 2015年1期

关键词：评判服务质量联网

王盖，王永炎

(中国科学院软件研究所，北京 100190)

物联网环境下基于用户满意度的实时调度算法*

王盖，王永炎

(中国科学院软件研究所，北京 100190)

随着3G网络和移动技术的发展，物联网已经深入到人们的工作和生活中，提供无所不在的服务。用户作为服务对象，以追求满意的高品质服务为目标，对服务具有选择权，对服务品质具有最直接、最重要的评判权。系统作为服务提供者，其服务品质取决于每个用户的满意度。因此，如何通过调度算法合理分配系统资源，让每个用户获得满意度更高的服务，成为了研究的重点。首先，构建个人满意度和系统满意度的评价标准；其次，依据用户期望的服务水平，为任务分配优先级；最后，通过反馈调节机制来调整任务优先级的分配，让更多用户对服务满意。实验表明，物联网环境下基于用户满意度的实时调度算法能够根据用户的需求，为用户提供满意的差别化服务，并提高系统满意度。

用户满意度;服务质量;物联网;反馈调节;模糊综合评判;实时调度

1 引言

1999年Ashton K提出的物联网[1]概念，在世界范围内掀起了一场新的网络革命。随后各国投入了高度的热情与努力。经过多年的探索与研究，物联网的内涵和外延都有了极大的提升，但是，至今仍未能就其定义达成一个共识。不过，物联网无处不在的“交流”以及为人类提供便捷服务的本质是不容质疑的。怀着对这种思想的追问与反思，许多研究开始着力于物联网的落地。RFID(Radio Frequency IDentification)、无线传感网络WSN(Wireless Sensor Network)、RFID传感网络RSN(RFID Sensor Network)[2]的提出和兴起为物联网的发展和部署奠定了坚实的基础，同时也带来了一些不可回避的挑战。实时调度就是其中重要的一个。物联网节点的普遍存在与广泛应用，导致数据量的急速飙升。在互联网时代，人类一共产生了大约50 PB的数据[1],然而在物联网时代，仅一个中等规模的RFID应用每天将产生10亿字节数量级的RFID数据。因此，如何及时地调度任务，将海量的数据发送给接收端进行处理，是一个亟待解决的难题。

传统的单处理器实时调度算法，如最优的静态优先级调度算法—单调速率调度算法RMS(Rate-Monotonic Scheduling)；最优的动态调度算法—最早死线优先算法EDF(Earliest Deadline First)，或者它们的变体与改进，如文献[3,4]，大都是在排队论的基础上，对任务按照一定的标准(任务周期、死线等)进行排序，并依据排序先后进行调度。这些算法，在理论上可以达到或者接近最优，但是，它们忽略了物联网数据的海量性特点，在排序过程中产生了巨大的时间和资源浪费，导致大量的调度延迟，甚至失效。为解决这个问题，文献[5]提出了基于多队列的调度算法，该算法通过队列将任务划分为不同的优先级，采用相应的策略进行队列的调度，从而达到快速、合理的任务分发和处理。但是，这些算法忽略了人在其中的作用。文献[6～9]开始从QoS(Quality of Service)的角度探讨差异化的服务，但仍未能彻底把握住用户的视角。物联网应用的价值主要表现为让物体更有智慧，改变人类的生产和生活方式。正如文献[10]中所说“今后，物联网服务将作为一种商品，并像传统商品一样出售和使用”，用户将成为决定物联网服务质量的关键。所以，物联网环境下的调度算法需要更多地从用户的观点考虑任务的调度，满足用户对服务的期望与需求。

本文将从用户的观点出发，以用户满意度为标准，探索物联网环境下的实时调度算法。物联网服务为数以亿计的用户提供海量信息的订阅、发布与查询，并及时地对用户请求做出响应，满足用户的不同需求。在此过程中，由于不同用户投入的资金及操作不同，对服务质量的要求也各不相同，但最终的目的都是获取满意的服务。本文将在物联网环境下，构建一个基于用户满意度的实时调度算法，在保证用户满意度的同时，通过合理的调度方式，为不同的用户提供差异化的服务，并通过反馈调节调整任务调度顺序，获取较高的系统满意度。

2 相关工作

2.1 服务质量

服务的本质是 “以满足客户需求为目的”。这个极富主观性的目标也决定了服务质量度量的困难性。服务质量作为“一种衡量企业服务水平能否满足顾客期望程度的工具”[11]，取决于顾客对服务质量的期望(即期望服务质量)与实际感知的服务水平(即体验的服务质量)的对比[12]。然而，无论期望服务质量还是体验的服务质量，都极大地依赖于用户的主观感受与评价，为科学的评价与客观的计算带来了困难。SERVQUAL模型[13]的提出为服务质量的度量带来了巨大的进步。SERVQUAL将服务质量划分为基本的服务质量要素，以“期望-感知”模型为核心计算出SERVQUAL分数，进而推测出服务质量的高低。但是，该方法是建立在对三个行业中的五家公司调查样本的基础上，样本容量的有限导致了SERVQUAL模型缺乏通用性；对服务质量要素划分的主观性又导致了客观性的缺失。因此，需要一种更加适合将主观评价转化为定量评价的方案与模型。模糊综合评判法就是一个很好的选择。

2.2 模糊综合评判

在人们思维中存在着许多模糊的概念，如年轻、暖和等，这些概念很难用具体的数字表示，如何度量这些概念正是计算机面临的一个挑战。1965年Zadeh提出了以隶属度为中心的模糊集合，用以描述不确定的模糊问题。不同于普通集合非此即彼的隶属关系，模糊集合用一个值域为[0,1]的隶属函数描述一个集合元素隶属于该模糊集合的程度，兼顾了描述对象的模糊性和客观性，更好地表示了真实世界中模糊不清的事物与标准。在此基础上，汪培庄在20世纪80年代中期提出了模糊综合评判模型[14]，用于复杂的多因素评判。

模糊综合评判模型包含两个基本的论域：因素集U={u1,u2,…,un}和评判集V={v1,v2,…,vm}。其中U代表了被评判对象的各个影响因素的集合，ui代表影响被评判对象的第i个影响因素；V代表了被评判对象的评语集合，它是主观的评判标准，vi表示第i个评语。建立模糊综合评判模型的过程就是将U映射到V的过程。模糊综合评判法的步骤如下[15]：

(1)确定单因素评判，建立从影响因素ui到评判集V的映射Fi;

①划分评判集V={v1,v2,…,vm}, 并确定对应影响因素ui的阈值T={t1,t2,…,tm};

②采用半梯形和梯形分布构造影响因素在评判集上的隶属函数M1,M2,…,Mm;

③通过隶属函数，计算单因素的隶属度，归一化后，得到隶属度r={r1,r2,…,rm}。

这样就建立起从影响因素ui到评判集V的映射Fi，即ui→(ri1,ri2,…,rim)。

(2)通过Fi构建评判矩阵R。

将每个因素ui到评判集的映射结果作为矩阵的一行，最终构建一个因素集U到评判集V的模糊关系，即评判矩阵：

(4)最终的综合评判结果就是权值A与评判矩阵R的合成，即：

A∘R=B={b1,b2,…,bn}

其中B代表了被评判对象在评判集上的结果。

(5)对结果集B利用最大隶属度原则，得到被评判对象的服务质量。

2.3 用户满意度

用户满意度描述了用户对服务质量的看法，是服务质量的间接体现。它从用户的角度出发，对接受的服务质量进行判断与度量，得到一个客观而真实的结果。

要使用这个度量标准，首先必须建立用户满意度与其它参数之间的关系：

(1) 用户满意度和服务质量之间存在着一个正相关的对应关系。在一定范围内，用户满意度随着服务质量的提升而增加，当超出范围后，用户满意度将趋于平稳。

(2) 用户满意度与用户的属性(即用户的投入或用户等级等)密不可分。如要达到相同的用户满意度，投入较高的用户需要得到更多的资源，以获得更好的服务质量。

Sigmoid函数凭借曲线特征与上述关系的高度吻合性，可用来近似地表示用户满意度和服务质量之间的关系。用户满意度的描述公式可表示为：

(1)

其中,变量x表示用户得到的服务质量，α表示与用户的属性(即用户的投入或用户等级等)相关的常量，β作为一个调整参数。由用户属性和用户满意度两者之间的关系知，用户投入越多、需求越高，越不易得到满足，其对应的α也就越小。

3 调度策略

3.1 主要参数

在物联网中一个任务的重要程度取决于任务的价值、用户的影响和系统的反馈三个因素。因此，本文将作如下定义：

定义1(任务的优先权值) 在物联网中由于应用范围的不同，任务具有不同的价值，对处理次序具有不同的需求，如监控报警类任务的价值往往要高于数据收集类任务，需要优先处理。因此，将任务的价值定义为任务的优先权值，记作Porg。

定义2(用户影响) 将用户为获取期望的服务质量而付出的金钱、人力、时间等定义为用户影响，记作xa。xa反映了用户期望获取的服务质量，直接影响了任务的调度次序。

定义3(反馈调节因子) 将系统用于调节资源分配的反馈值定义为反馈调节因子，记作μ，其初始值定义为0。

在物联网中，服务往往是由多个相关的任务组成，任务完成的结果直接关系到服务水平的高低。因此，用户对服务的满意程度也可细分为用户对单个任务的满意度、用户对某服务所有任务的满意度以及用户对系统的满意度。因此，本文作如下定义：

定义4(任务满意度) 将用户对单个任务执行情况的满意程度定义为任务满意度，记作Ds，可由公式(1)计算得出。

定义6(系统满意度) 将系统中所有任务满意度的加权平均值定义为系统满意度，记作Usys。可由公式:

(2)

计算得出，其中xai表示第i个任务对应的用户影响，Dsi表示第i个任务的任务满意度，j表示已完成的调度数量。

服务质量是对系统提供的服务水平的描述，直接反映了系统的资源分配情况，为系统的反馈调节提供了参考。因此，本文对服务质量的相关参数进行了如下定义：

定义7(理想服务质量) 将任务满意度等于或者接近于1时的服务质量定义为理想服务质量，记作Sideal。反映了达到最高任务满意度所需的最低服务质量。

定义8(实际服务质量) 将系统为用户实际提供的服务质量定义为实际服务质量，记作Sp。描述了用户实际获得的服务质量，可通过模糊综合评判法进行量化计算。

定义9(剩余服务质量) 将实际服务质量超出理想服务质量的值定义为剩余服务质量，记作ΔS。可根据公式:

ΔS=Sp-λSideal

(3)

计算得出。可作为调节系统资源分配时的参考。

3.2 调度算法模型

本文在物联网环境下构建的基于用户满意度的实时调度算法模型如图1所示。它由四个部分组成，分别为：任务分配器、任务队列、任务调度器和服务计算器。

Figure 1 Schedule model

3.2.1 任务分配器

任务分配器根据用户影响xa、任务的优先权值Porg和反馈调节因子μ，计算出任务的综合优先级P，并以此为依据，将任务分配到相应的任务队列中。

3.2.2 任务队列

任务队列由n个具有不同优先级的队列组成。其中1表示最低优先级，n表示最高优先级。任务队列用于接收并缓存任务分配器分配的任务，供任务调度器调度。

3.2.3 任务调度器

任务调度器根据队列的优先级，由高到低依次对任务队列中的队列进行调度，将其中的任务发送给相应的处理端。在各个队列的内部采用先进先出的调度方式。

3.2.4 服务计算器

对任务调度器的调度服务进行计算，得到相应的服务质量、任务满意度、个人满意度、系统满意度和反馈调节因子。

3.3 主要流程

(1)根据用户影响xa、任务的优先权值Porg和反馈调节因子μ，通过公式：

P=ω1×xa+ω2×Porg+ω3×μ

计算待调度任务的综合优先级P，并以此为依据，将任务保存到具有优先级的队列中，其中,ωi为权值，且ω1>ω2>ω3)。

(2)按从高到底的优先级，依次调度(1)中的非空队列，将任务发送给对应的处理端。

(3)通过专家分析法，确定服务质量的因素集U和评判集V，根据模糊综合评判法，求出实际服务质量Sp，并将其规范化到预定范围内。

(4)若延迟小于或等于用户的最大容忍延迟dtolerate，根据公式(1)，求出相应的任务满意度Ds；否则，设置任务满意度Ds=0。

(5)若任务满意度Ds大于或等于阈值d0，则记为用户满意，并转入(6)，否则，进入(7)。

(6)通过公式(3)计算用户的剩余服务质量，获取并记录反馈调节因子μ的大小。

(7)标记任务失败，执行反馈调节。

(8)计算个人满意度。

(9)通过公式(2)计算系统满意度。

3.4 关键流程详述

在上述流程中有两点需要特别地说明：任务满意度计算和反馈调节。

3.4.1 任务满意度计算

由1.3节可知，公式(1)中的参数α最终会受到用户影响xa的影响。用户影响越大，说明用户的投入越多，所期望的服务质量较高。因此，在服务质量相同的前提下，xa越大，用户越难得到满足，任务满意度Ds越小。由Sigmod曲线性质知，用户影响大的，对应的α较小。

3.4.2 反馈调节

任务满意度大于或等于阈值，意味着在调度中获取了足够或超额的服务质量。而反馈调节的目的在于充分利用剩余服务质量去弥补资源不足的失败调度，从而在尽量保证原有任务满意度和个人满意度的基础上，提升系统满意度。

由1.3节可知，当服务质量达到一定水平后，任务满意度将趋于稳定，此时的服务质量为理想服务质量。因此，令公式(1)中的U(x)=1，求得理想服务质量Sideal=x。若用户获得的实际服务质量Sp>Sideal，说明该任务存在剩余服务质量，可通过公式(3)计算得到(通过设置λ>1来尽量保证任务让出系统资源后仍能满足用户需求)。之后，通过公式μ=ΔS/100×a(其中a为反馈调节因子的最大值)，即可求得反馈调节因子μ。

当一个任务失败或者未达到任务满意度的阈值时，它将选取当前最大的反馈调节因子(其对应的任务被称为“被借贷者”)，用于下一次综合优先级的计算，从而提高任务优先级，以获取更好的服务。同时，相应的“被借贷者”将在下一次综合优先级的计算中减去相应的量，让出多余的系统资源。

4 实验分析

本节将使用一个模拟实验对算法进行验证，并通过与FIFO算法和EDF算法对比，说明本文提出的调度算法能够保证用户的个人满意度，同时提升系统满意度。由上文可知，任务的优先级取决于用户影响xa和任务的优先权值Porg。任务调度器根据任务的优先级对任务进行调度，实现差异化的处理。在现实环境中，用户在获取某项服务时，所能支付的资源(如金钱等)各不相同，导致了用户影响的差异。为了更好地展示本文提出的调度算法对不同“用户影响”的差异化服务，本实验根据用户影响的不同将用户划分为等量的三组，并分别标记为高影响用户、中影响用户和低影响用户三个等级。其中高影响用户的用户影响最大，低影响用户的最小，三个等级的用户影响分别设置为5、2、1。同时由上文可知，用户影响越大，代表用户投入越多、需求越高，越不易得到满足，其对应的α值也就越小，因此，本实验假设高、中、低三个等级的用户对应的α值分别设置为0.1、0.2和0.4。在实际环境中，不同的任务因应用场景的不同，对处理的次序具有不同的需求。为了体现这种差异化的需求，本实验假设所有设备共产生三种不同的任务类型，每个设备属于一个单独的用户，且等概率地产生任一种任务类型。本文假设用户的付出(即用户影响xa)对优先级的影响始终不小于任务自身的优先级(即任务的优先级Porg)，所以，假设三种任务类型的价值分别为3、2、1。为了简化实验场景，本实验假设网络条件是理想的，即不存在任何因网络传输而造成的延迟。本实验还为每个任务设置了一个容忍上限，一旦超出容忍上限，相应的任务满意度将被置为零；否则，只要超出预定义的任务满意度阈值(此实验定义为90%)即认为任务满意度达标。由于个人满意度等于它对应的任务满意度的平均值，因此个人满意度阈值也为90%。本实验在装有IntelCore2QuadQ9550处理器和配置4GB内存的Windows7系统中，进行了10轮模拟实验，每轮分两次调度100 000个任务。记录并统计每轮的失败次数、各用户获得的服务质量、个人满意度、系统满意度。通过这些参数的比较，说明本文提出的调度算法确实为不同“用户影响”的用户提供了差异化服务，并且保证了个人满意度和较高的系统满意度。

图2显示了不同调度算法对个人满意度的影响。从图2中可以看出，使用本文提出的算法后，个人满意度始终处于阈值之上，即系统提供了用户满意的服务；而使用FIFO算法和EDF算法时，个人满意度始终处于阈值之下，即系统无法保证满足用户需求。这是由于FIFO算法没有考虑用户的差异化需求，仅仅按照到达顺序进行调度，增大了高优先级任务的延迟。EDF算法在排序中耗费了大量的时间，每个任务的到来都会导致所有待调度任务的重新排序，且EDF没有考虑用户影响对任务优先级的作用，增大了用户影响较大的任务延迟。

本文提出的调度算法以用户满意度为中心，综合考虑了影响任务优先级的各个因素，并通过合理调度与反馈调节，保证了用户获取所需的服务质量，从而确保个人满意度达标。

Figure 2 Schedule algorithms’ affection on personal satisfaction

图3显示了不同调度算法对系统满意度的影响。从图3中可以看出，采用本文提出的调度算法，系统满意度始终高于采用FIFO算法和EDF算法时的情况。这是由于系统满意度取决于所有任务满意度加权和的平均值，本文提出的调度算法为用户影响较高的任务赋予较大的优先级，优先满足用户影响较高的任务需求，同时通过反馈调节机制，保证了尽可能多的任务在调度过程获取满意的服务质量。而FIFO算法和EDF算法并没有考虑用户的影响，增加了用户影响较大的任务的延迟，降低了相应的任务满意度。因此，使用本文提出的算法时，系统满意度高于其他两种调度算法。

Figure 3 Schedule algorithms’ affection on system satisfaction

图4显示了用户影响与服务质量的关系。通过在实验结果中选取个人满意度达标的任务，展示中级用户和高级用户的服务质量的差异。从图4中可以看出，在个人满意度达标的情况下，高级用户的服务质量要明显高于中级用户。这是由于高级用户付出了更多的金钱和资源，它要求在达到同等个人满意度的情况下，系统提供更高、更好的服务质量。这也契合了本文调度算法提出的背景及实现方案。

Figure 4 Relationship between user affection and service quality

图5显示了失败次数对个人满意度的影响。它是将实验结果按失败次数递增的顺序绘制而成的。从图5中可以看出，高级用户的个人满意度随着失败次数的增加而减小，但是，始终高于阈值；低级用户的个人满意度随失败次数的增加而快速降低，并且当失败数大于某值时，个人满意度低于阈值。这是由于在资源有限的情况下，当失败次数大于某值时，必须通过牺牲低级用户对应的任务满意度，来保障高级用户的任务满意度，从而在降低低级用户个人满意度，保证高级用户个人满意度的基础上，获得较高的系统满意度。

Figure 5 Relationship between fail times and personal satisfaction

5 结束语

本文在物联网背景下，以用户为中心，根据用户影响和任务的优先权值对任务进行综合调度，同时，通过反馈调节因子调整任务优先级,最终达到为用户提供满意的差异化服务的目的。实验表明，本文提出的物联网环境下基于用户满意度的实时调度算法，能够针对物联网数据海量、实时的特性与需求，根据用户影响，分配所需的系统资源，为不同的用户提供满意的服务，并提高系统满意度。

在物联网中，一个任务的状态可能受到多个用户的综合影响，并随用户状态、投入的变化而改变。如一个数据更新与发布任务，会受到关注它的用户的综合影响，并随着关注人数、关注者等级的变化而变化。因此，如何在多个用户的动态影响下合理地分配任务优先级，从而获取用户满意的服务质量，将是下一步研究的方向。

[1]AshtonK.That‘internetofthings’thing[J].RFIDJournal, 2009, 22:97-114.

[2]AtzoriL,IeraA,MorabitoG.TheInternetofThings:Asurvey[J].ComputerNetworks, 2010, 54(15):2787-2805.

[3]XuJ,GuoC,LiWX,etal.Apacket-schedulingstrategyforheterogeneoustrafficofInternetofThings[C]∥Procof2012 2ndInternationalConferenceonConsumerElectronics,CommunicationsandNetworks(CECNet), 2012:1557-1560.

[4]GuangqianZ,LiZ,XinL,etal.Real-timeeventschedulingmodelofCEP-basedRFIDdataprocessingsystem[C]∥ProcofInternationalForumonInformationTechnologyandApplications, 2009:772-775.

[5]WongHT.Packetschedulingusingdualweightsinglepriorityqueue:U.S.Patent6,570,883[P]. 2003-05-27.

[6]AbdullahS,YangKun.AQoSawaremessageschedulingalgorithminInternetofThingsenvironment[C]∥ProcofOnlineConferenceonGreenCommunications(GreenCom), 2013:175-180.

[7]SunQ,WangS,ZouH,etal.QSSA:AQoS-awareserviceselectionapproach[J].InternationalJournalofWebandGridServices, 2011, 7(2):147-169.

[8]DuanR,ChenX,XingT.AQoSarchitectureforIoT[C]∥Procof2011InternationalConferenceonandthe4thInternationalConferenceonCyber,PhysicalandSocialComputing, 2011:717-720.

[9]LiangQ,WangY.AnalgorithmofserviceselectionbasedonQoSpreferenceinnetworkcomputingenvironment[C]∥ProcofInternationalConferenceonComputationalIntelligenceandNaturalComputing,2009:279-282.

[10]GubbiJ,BuyyaR,MarusicS,etal.InternetofThings(IoT):Avision,architecturalelements,andfuturedirections[J].FutureGenerationComputerSystems, 2013, 29(7):1645-1660.

[11]LewisRC,BoomsBH.Themarketingaspectsofservicequalityinemergingperspectivesonservicesmarketing[J].EmergingPerspectivesonServicesMarketing, 1983, 65(4):99-107.

[12]GronroosC.Marketinginservicecompanies[M].Malmo:Liber, 1983.

[13]NaikCNK,GantasalaSB,PrabhakarGV.Servicequality(Servqual)anditseffectoncustomersatisfactioninretailing[J].EuropeanJournalofSocialSciences, 2010, 16(2):231-243.

[14]WangPei-zhuang.Fuzzymathematicsandapplications[J].JournalofHenanNormalUniversity(NaturalScience), 1983,6(2):1-20.(inChinese)

[15]ZhouJin-hui,WangZong,YangZong-kui,etal.Researchonsoftwarequalityevaluationbasedonfuzzymethod[J].SystemsEngineeringandElectronics, 2004, 26(7):988-991.(inChinese)

附中文参考文献：

[14] 汪培庄. 模糊数学及其应用[J]. 河南师大学报 (自然科学版), 1983,6(2):1-20.

[15] 周津慧, 王宗, 杨宗奎, 等. 基于模糊评价方法的软件质量评价研究[J]. 系统工程与电子技术, 2004, 26(7):988-991.

WANG Gai,born in 1989,MS candidate,his research interests include task scheduling in Internet of Things, and data processing.

王永炎(1978-),男,福建永定人，博士，高级工程师，研究方向为实时系统、实时数据库和传感器数据管理。E-mail:yongyan@iscas.ac.cn

WANG Yong-yan,born in 1978,PhD,senior engineer,his research interests include real-time system, real-time database, and sensor data management.

Real-time scheduling algorithm for Internet of Things based on user satisfaction

WANG Gai，WANG Yong-yan

(Institute of Software,Chinese Academy of Sciences,Beijing 100190,China)

With the development of 3G networks and mobile telecommunications technology, Internet of Things (IoT) has penetrated into people’s life providing ubiquitous service. As the center of service, users always pursue service of high quality and they have the most direct and powerful right to evaluate a service. As service providers, computer systems’ service quality is based on the level of every user’s satisfaction. Therefore, it is crucial to construct a scheduling algorithm for allocating system resources reasonably to guarantee a better service. Firstly, we establish the quantitative evaluation standards for personal satisfaction and system satisfaction. Secondly, we assign priorities for tasks according to the service quality that users expect. Finally, we use feedback regulations to adjust task priority assignment, so that more users will be satisfied with the provided service. Experimental results show that the proposed algorithm can help computer systems offer differentiated services based on users’ needs and ensures a higher system satisfaction.

user satisfaction;service quality;Internet of Things;feedback regulation;fuzzy comprehensive evaluation method;real-time schedule

1007-130X(2015)01-0184-07

2014-07-30;

2014-09-14基金项目：国家自然科学基金面上资助项目(61273080)；国家科技重大项目(2012ZX01039-004)

TP301.6

10.3969/j.issn.1007-130X.2015.01.029