物聯(lián)網(wǎng)環(huán)境下基于用戶滿意度的實時調(diào)度算法*

王 蓋，王永炎

(中國科學(xué)院軟件研究所，北京 100190)

物聯(lián)網(wǎng)環(huán)境下基于用戶滿意度的實時調(diào)度算法*

王 蓋，王永炎

(中國科學(xué)院軟件研究所，北京 100190)

隨著3G網(wǎng)絡(luò)和移動技術(shù)的發(fā)展，物聯(lián)網(wǎng)已經(jīng)深入到人們的工作和生活中，提供無所不在的服務(wù)。用戶作為服務(wù)對象，以追求滿意的高品質(zhì)服務(wù)為目標，對服務(wù)具有選擇權(quán)，對服務(wù)品質(zhì)具有最直接、最重要的評判權(quán)。系統(tǒng)作為服務(wù)提供者，其服務(wù)品質(zhì)取決于每個用戶的滿意度。因此，如何通過調(diào)度算法合理分配系統(tǒng)資源，讓每個用戶獲得滿意度更高的服務(wù)，成為了研究的重點。首先，構(gòu)建個人滿意度和系統(tǒng)滿意度的評價標準；其次，依據(jù)用戶期望的服務(wù)水平，為任務(wù)分配優(yōu)先級；最后，通過反饋調(diào)節(jié)機制來調(diào)整任務(wù)優(yōu)先級的分配，讓更多用戶對服務(wù)滿意。實驗表明，物聯(lián)網(wǎng)環(huán)境下基于用戶滿意度的實時調(diào)度算法能夠根據(jù)用戶的需求，為用戶提供滿意的差別化服務(wù)，并提高系統(tǒng)滿意度。

用戶滿意度;服務(wù)質(zhì)量;物聯(lián)網(wǎng);反饋調(diào)節(jié);模糊綜合評判;實時調(diào)度

1 引言

1999年Ashton K提出的物聯(lián)網(wǎng)[1]概念，在世界范圍內(nèi)掀起了一場新的網(wǎng)絡(luò)革命。隨后各國投入了高度的熱情與努力。經(jīng)過多年的探索與研究，物聯(lián)網(wǎng)的內(nèi)涵和外延都有了極大的提升，但是，至今仍未能就其定義達成一個共識。不過，物聯(lián)網(wǎng)無處不在的“交流”以及為人類提供便捷服務(wù)的本質(zhì)是不容質(zhì)疑的。懷著對這種思想的追問與反思，許多研究開始著力于物聯(lián)網(wǎng)的落地。RFID(Radio Frequency IDentification)、無線傳感網(wǎng)絡(luò)WSN(Wireless Sensor Network)、RFID傳感網(wǎng)絡(luò)RSN(RFID Sensor Network)[2]的提出和興起為物聯(lián)網(wǎng)的發(fā)展和部署奠定了堅實的基礎(chǔ)，同時也帶來了一些不可回避的挑戰(zhàn)。實時調(diào)度就是其中重要的一個。物聯(lián)網(wǎng)節(jié)點的普遍存在與廣泛應(yīng)用，導(dǎo)致數(shù)據(jù)量的急速飆升。在互聯(lián)網(wǎng)時代，人類一共產(chǎn)生了大約50 PB的數(shù)據(jù)[1],然而在物聯(lián)網(wǎng)時代，僅一個中等規(guī)模的RFID應(yīng)用每天將產(chǎn)生10億字節(jié)數(shù)量級的RFID數(shù)據(jù)。因此，如何及時地調(diào)度任務(wù)，將海量的數(shù)據(jù)發(fā)送給接收端進行處理，是一個亟待解決的難題。

傳統(tǒng)的單處理器實時調(diào)度算法，如最優(yōu)的靜態(tài)優(yōu)先級調(diào)度算法—單調(diào)速率調(diào)度算法RMS(Rate-Monotonic Scheduling)；最優(yōu)的動態(tài)調(diào)度算法—最早死線優(yōu)先算法EDF(Earliest Deadline First)，或者它們的變體與改進，如文獻[3,4]，大都是在排隊論的基礎(chǔ)上，對任務(wù)按照一定的標準(任務(wù)周期、死線等)進行排序，并依據(jù)排序先后進行調(diào)度。這些算法，在理論上可以達到或者接近最優(yōu)，但是，它們忽略了物聯(lián)網(wǎng)數(shù)據(jù)的海量性特點，在排序過程中產(chǎn)生了巨大的時間和資源浪費，導(dǎo)致大量的調(diào)度延遲，甚至失效。為解決這個問題，文獻[5]提出了基于多隊列的調(diào)度算法，該算法通過隊列將任務(wù)劃分為不同的優(yōu)先級，采用相應(yīng)的策略進行隊列的調(diào)度，從而達到快速、合理的任務(wù)分發(fā)和處理。但是，這些算法忽略了人在其中的作用。文獻[6～9]開始從QoS(Quality of Service)的角度探討差異化的服務(wù)，但仍未能徹底把握住用戶的視角。物聯(lián)網(wǎng)應(yīng)用的價值主要表現(xiàn)為讓物體更有智慧，改變?nèi)祟惖纳a(chǎn)和生活方式。正如文獻[10]中所說“今后，物聯(lián)網(wǎng)服務(wù)將作為一種商品，并像傳統(tǒng)商品一樣出售和使用”，用戶將成為決定物聯(lián)網(wǎng)服務(wù)質(zhì)量的關(guān)鍵。所以，物聯(lián)網(wǎng)環(huán)境下的調(diào)度算法需要更多地從用戶的觀點考慮任務(wù)的調(diào)度，滿足用戶對服務(wù)的期望與需求。

本文將從用戶的觀點出發(fā)，以用戶滿意度為標準，探索物聯(lián)網(wǎng)環(huán)境下的實時調(diào)度算法。物聯(lián)網(wǎng)服務(wù)為數(shù)以億計的用戶提供海量信息的訂閱、發(fā)布與查詢，并及時地對用戶請求做出響應(yīng)，滿足用戶的不同需求。在此過程中，由于不同用戶投入的資金及操作不同，對服務(wù)質(zhì)量的要求也各不相同，但最終的目的都是獲取滿意的服務(wù)。本文將在物聯(lián)網(wǎng)環(huán)境下，構(gòu)建一個基于用戶滿意度的實時調(diào)度算法，在保證用戶滿意度的同時，通過合理的調(diào)度方式，為不同的用戶提供差異化的服務(wù)，并通過反饋調(diào)節(jié)調(diào)整任務(wù)調(diào)度順序，獲取較高的系統(tǒng)滿意度。

2 相關(guān)工作

2.1 服務(wù)質(zhì)量

服務(wù)的本質(zhì)是 “以滿足客戶需求為目的”。這個極富主觀性的目標也決定了服務(wù)質(zhì)量度量的困難性。服務(wù)質(zhì)量作為“一種衡量企業(yè)服務(wù)水平能否滿足顧客期望程度的工具”[11]，取決于顧客對服務(wù)質(zhì)量的期望(即期望服務(wù)質(zhì)量)與實際感知的服務(wù)水平(即體驗的服務(wù)質(zhì)量)的對比[12]。然而，無論期望服務(wù)質(zhì)量還是體驗的服務(wù)質(zhì)量，都極大地依賴于用戶的主觀感受與評價，為科學(xué)的評價與客觀的計算帶來了困難。SERVQUAL模型[13]的提出為服務(wù)質(zhì)量的度量帶來了巨大的進步。SERVQUAL將服務(wù)質(zhì)量劃分為基本的服務(wù)質(zhì)量要素，以“期望-感知”模型為核心計算出SERVQUAL分數(shù)，進而推測出服務(wù)質(zhì)量的高低。但是，該方法是建立在對三個行業(yè)中的五家公司調(diào)查樣本的基礎(chǔ)上，樣本容量的有限導(dǎo)致了SERVQUAL模型缺乏通用性；對服務(wù)質(zhì)量要素劃分的主觀性又導(dǎo)致了客觀性的缺失。因此，需要一種更加適合將主觀評價轉(zhuǎn)化為定量評價的方案與模型。模糊綜合評判法就是一個很好的選擇。

2.2 模糊綜合評判

在人們思維中存在著許多模糊的概念，如年輕、暖和等，這些概念很難用具體的數(shù)字表示，如何度量這些概念正是計算機面臨的一個挑戰(zhàn)。1965年Zadeh提出了以隸屬度為中心的模糊集合，用以描述不確定的模糊問題。不同于普通集合非此即彼的隸屬關(guān)系，模糊集合用一個值域為[0,1]的隸屬函數(shù)描述一個集合元素隸屬于該模糊集合的程度，兼顧了描述對象的模糊性和客觀性，更好地表示了真實世界中模糊不清的事物與標準。在此基礎(chǔ)上，汪培莊在20世紀80年代中期提出了模糊綜合評判模型[14]，用于復(fù)雜的多因素評判。

模糊綜合評判模型包含兩個基本的論域：因素集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}, 并確定對應(yīng)影響因素ui的閾值T={t1,t2,…,tm};

②采用半梯形和梯形分布構(gòu)造影響因素在評判集上的隸屬函數(shù)M1,M2,…,Mm;

③通過隸屬函數(shù)，計算單因素的隸屬度，歸一化后，得到隸屬度r={r1,r2,…,rm}。

這樣就建立起從影響因素ui到評判集V的映射Fi，即ui→(ri1,ri2,…,rim)。

(2)通過Fi構(gòu)建評判矩陣R。

將每個因素ui到評判集的映射結(jié)果作為矩陣的一行，最終構(gòu)建一個因素集U到評判集V的模糊關(guān)系，即評判矩陣：

(4)最終的綜合評判結(jié)果就是權(quán)值A(chǔ)與評判矩陣R的合成，即：

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

其中B代表了被評判對象在評判集上的結(jié)果。

(5)對結(jié)果集B利用最大隸屬度原則，得到被評判對象的服務(wù)質(zhì)量。

2.3 用戶滿意度

用戶滿意度描述了用戶對服務(wù)質(zhì)量的看法，是服務(wù)質(zhì)量的間接體現(xiàn)。它從用戶的角度出發(fā)，對接受的服務(wù)質(zhì)量進行判斷與度量，得到一個客觀而真實的結(jié)果。

要使用這個度量標準，首先必須建立用戶滿意度與其它參數(shù)之間的關(guān)系：

(1) 用戶滿意度和服務(wù)質(zhì)量之間存在著一個正相關(guān)的對應(yīng)關(guān)系。在一定范圍內(nèi)，用戶滿意度隨著服務(wù)質(zhì)量的提升而增加，當超出范圍后，用戶滿意度將趨于平穩(wěn)。

(2) 用戶滿意度與用戶的屬性(即用戶的投入或用戶等級等)密不可分。如要達到相同的用戶滿意度，投入較高的用戶需要得到更多的資源，以獲得更好的服務(wù)質(zhì)量。

Sigmoid函數(shù)憑借曲線特征與上述關(guān)系的高度吻合性，可用來近似地表示用戶滿意度和服務(wù)質(zhì)量之間的關(guān)系。用戶滿意度的描述公式可表示為：

(1)

其中,變量x表示用戶得到的服務(wù)質(zhì)量，α表示與用戶的屬性(即用戶的投入或用戶等級等)相關(guān)的常量，β作為一個調(diào)整參數(shù)。由用戶屬性和用戶滿意度兩者之間的關(guān)系知，用戶投入越多、需求越高，越不易得到滿足，其對應(yīng)的α也就越小。

3 調(diào)度策略

3.1 主要參數(shù)

在物聯(lián)網(wǎng)中一個任務(wù)的重要程度取決于任務(wù)的價值、用戶的影響和系統(tǒng)的反饋三個因素。因此，本文將作如下定義：

定義1(任務(wù)的優(yōu)先權(quán)值) 在物聯(lián)網(wǎng)中由于應(yīng)用范圍的不同，任務(wù)具有不同的價值，對處理次序具有不同的需求，如監(jiān)控報警類任務(wù)的價值往往要高于數(shù)據(jù)收集類任務(wù)，需要優(yōu)先處理。因此，將任務(wù)的價值定義為任務(wù)的優(yōu)先權(quán)值，記作Porg。

定義2(用戶影響) 將用戶為獲取期望的服務(wù)質(zhì)量而付出的金錢、人力、時間等定義為用戶影響，記作xa。xa反映了用戶期望獲取的服務(wù)質(zhì)量，直接影響了任務(wù)的調(diào)度次序。

定義3(反饋調(diào)節(jié)因子) 將系統(tǒng)用于調(diào)節(jié)資源分配的反饋值定義為反饋調(diào)節(jié)因子，記作μ，其初始值定義為0。

在物聯(lián)網(wǎng)中，服務(wù)往往是由多個相關(guān)的任務(wù)組成，任務(wù)完成的結(jié)果直接關(guān)系到服務(wù)水平的高低。因此，用戶對服務(wù)的滿意程度也可細分為用戶對單個任務(wù)的滿意度、用戶對某服務(wù)所有任務(wù)的滿意度以及用戶對系統(tǒng)的滿意度。因此，本文作如下定義：

定義4(任務(wù)滿意度) 將用戶對單個任務(wù)執(zhí)行情況的滿意程度定義為任務(wù)滿意度，記作Ds，可由公式(1)計算得出。

定義6(系統(tǒng)滿意度) 將系統(tǒng)中所有任務(wù)滿意度的加權(quán)平均值定義為系統(tǒng)滿意度，記作Usys?？捎晒?

(2)

計算得出，其中xai表示第i個任務(wù)對應(yīng)的用戶影響，Dsi表示第i個任務(wù)的任務(wù)滿意度，j表示已完成的調(diào)度數(shù)量。

服務(wù)質(zhì)量是對系統(tǒng)提供的服務(wù)水平的描述，直接反映了系統(tǒng)的資源分配情況，為系統(tǒng)的反饋調(diào)節(jié)提供了參考。因此，本文對服務(wù)質(zhì)量的相關(guān)參數(shù)進行了如下定義：

定義7(理想服務(wù)質(zhì)量) 將任務(wù)滿意度等于或者接近于1時的服務(wù)質(zhì)量定義為理想服務(wù)質(zhì)量，記作Sideal。反映了達到最高任務(wù)滿意度所需的最低服務(wù)質(zhì)量。

定義8(實際服務(wù)質(zhì)量) 將系統(tǒng)為用戶實際提供的服務(wù)質(zhì)量定義為實際服務(wù)質(zhì)量，記作Sp。描述了用戶實際獲得的服務(wù)質(zhì)量，可通過模糊綜合評判法進行量化計算。

定義9(剩余服務(wù)質(zhì)量) 將實際服務(wù)質(zhì)量超出理想服務(wù)質(zhì)量的值定義為剩余服務(wù)質(zhì)量，記作ΔS?？筛鶕?jù)公式:

ΔS=Sp-λSideal

(3)

計算得出?？勺鳛檎{(diào)節(jié)系統(tǒng)資源分配時的參考。

3.2 調(diào)度算法模型

本文在物聯(lián)網(wǎng)環(huán)境下構(gòu)建的基于用戶滿意度的實時調(diào)度算法模型如圖1所示。它由四個部分組成，分別為：任務(wù)分配器、任務(wù)隊列、任務(wù)調(diào)度器和服務(wù)計算器。

Figure 1 Schedule model

3.2.1 任務(wù)分配器

任務(wù)分配器根據(jù)用戶影響xa、任務(wù)的優(yōu)先權(quán)值Porg和反饋調(diào)節(jié)因子μ，計算出任務(wù)的綜合優(yōu)先級P，并以此為依據(jù)，將任務(wù)分配到相應(yīng)的任務(wù)隊列中。

3.2.2 任務(wù)隊列

任務(wù)隊列由n個具有不同優(yōu)先級的隊列組成。其中1表示最低優(yōu)先級，n表示最高優(yōu)先級。任務(wù)隊列用于接收并緩存任務(wù)分配器分配的任務(wù)，供任務(wù)調(diào)度器調(diào)度。

3.2.3 任務(wù)調(diào)度器

任務(wù)調(diào)度器根據(jù)隊列的優(yōu)先級，由高到低依次對任務(wù)隊列中的隊列進行調(diào)度，將其中的任務(wù)發(fā)送給相應(yīng)的處理端。在各個隊列的內(nèi)部采用先進先出的調(diào)度方式。

3.2.4 服務(wù)計算器

對任務(wù)調(diào)度器的調(diào)度服務(wù)進行計算，得到相應(yīng)的服務(wù)質(zhì)量、任務(wù)滿意度、個人滿意度、系統(tǒng)滿意度和反饋調(diào)節(jié)因子。

3.3 主要流程

(1)根據(jù)用戶影響xa、任務(wù)的優(yōu)先權(quán)值Porg和反饋調(diào)節(jié)因子μ，通過公式：

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

計算待調(diào)度任務(wù)的綜合優(yōu)先級P，并以此為依據(jù)，將任務(wù)保存到具有優(yōu)先級的隊列中，其中,ωi為權(quán)值，且ω1>ω2>ω3)。

(2)按從高到底的優(yōu)先級，依次調(diào)度(1)中的非空隊列，將任務(wù)發(fā)送給對應(yīng)的處理端。

(3)通過專家分析法，確定服務(wù)質(zhì)量的因素集U和評判集V，根據(jù)模糊綜合評判法，求出實際服務(wù)質(zhì)量Sp，并將其規(guī)范化到預(yù)定范圍內(nèi)。

(4)若延遲小于或等于用戶的最大容忍延遲dtolerate，根據(jù)公式(1)，求出相應(yīng)的任務(wù)滿意度Ds；否則，設(shè)置任務(wù)滿意度Ds=0。

(5)若任務(wù)滿意度Ds大于或等于閾值d0，則記為用戶滿意，并轉(zhuǎn)入(6)，否則，進入(7)。

(6)通過公式(3)計算用戶的剩余服務(wù)質(zhì)量，獲取并記錄反饋調(diào)節(jié)因子μ的大小。

(7)標記任務(wù)失敗，執(zhí)行反饋調(diào)節(jié)。

(8)計算個人滿意度。

(9)通過公式(2)計算系統(tǒng)滿意度。

3.4 關(guān)鍵流程詳述

在上述流程中有兩點需要特別地說明：任務(wù)滿意度計算和反饋調(diào)節(jié)。

3.4.1 任務(wù)滿意度計算

由1.3節(jié)可知，公式(1)中的參數(shù)α最終會受到用戶影響xa的影響。用戶影響越大，說明用戶的投入越多，所期望的服務(wù)質(zhì)量較高。因此，在服務(wù)質(zhì)量相同的前提下，xa越大，用戶越難得到滿足，任務(wù)滿意度Ds越小。由Sigmod曲線性質(zhì)知，用戶影響大的，對應(yīng)的α較小。

3.4.2 反饋調(diào)節(jié)

任務(wù)滿意度大于或等于閾值，意味著在調(diào)度中獲取了足夠或超額的服務(wù)質(zhì)量。而反饋調(diào)節(jié)的目的在于充分利用剩余服務(wù)質(zhì)量去彌補資源不足的失敗調(diào)度，從而在盡量保證原有任務(wù)滿意度和個人滿意度的基礎(chǔ)上，提升系統(tǒng)滿意度。

由1.3節(jié)可知，當服務(wù)質(zhì)量達到一定水平后，任務(wù)滿意度將趨于穩(wěn)定，此時的服務(wù)質(zhì)量為理想服務(wù)質(zhì)量。因此，令公式(1)中的U(x)=1，求得理想服務(wù)質(zhì)量Sideal=x。若用戶獲得的實際服務(wù)質(zhì)量Sp>Sideal，說明該任務(wù)存在剩余服務(wù)質(zhì)量，可通過公式(3)計算得到(通過設(shè)置λ>1來盡量保證任務(wù)讓出系統(tǒng)資源后仍能滿足用戶需求)。之后，通過公式μ=ΔS/100×a(其中a為反饋調(diào)節(jié)因子的最大值)，即可求得反饋調(diào)節(jié)因子μ。

當一個任務(wù)失敗或者未達到任務(wù)滿意度的閾值時，它將選取當前最大的反饋調(diào)節(jié)因子(其對應(yīng)的任務(wù)被稱為“被借貸者”)，用于下一次綜合優(yōu)先級的計算，從而提高任務(wù)優(yōu)先級，以獲取更好的服務(wù)。同時，相應(yīng)的“被借貸者”將在下一次綜合優(yōu)先級的計算中減去相應(yīng)的量，讓出多余的系統(tǒng)資源。

4 實驗分析

本節(jié)將使用一個模擬實驗對算法進行驗證，并通過與FIFO算法和EDF算法對比，說明本文提出的調(diào)度算法能夠保證用戶的個人滿意度，同時提升系統(tǒng)滿意度。由上文可知，任務(wù)的優(yōu)先級取決于用戶影響xa和任務(wù)的優(yōu)先權(quán)值Porg。任務(wù)調(diào)度器根據(jù)任務(wù)的優(yōu)先級對任務(wù)進行調(diào)度，實現(xiàn)差異化的處理。在現(xiàn)實環(huán)境中，用戶在獲取某項服務(wù)時，所能支付的資源(如金錢等)各不相同，導(dǎo)致了用戶影響的差異。為了更好地展示本文提出的調(diào)度算法對不同“用戶影響”的差異化服務(wù)，本實驗根據(jù)用戶影響的不同將用戶劃分為等量的三組，并分別標記為高影響用戶、中影響用戶和低影響用戶三個等級。其中高影響用戶的用戶影響最大，低影響用戶的最小，三個等級的用戶影響分別設(shè)置為5、2、1。同時由上文可知，用戶影響越大，代表用戶投入越多、需求越高，越不易得到滿足，其對應(yīng)的α值也就越小，因此，本實驗假設(shè)高、中、低三個等級的用戶對應(yīng)的α值分別設(shè)置為0.1、0.2和0.4。在實際環(huán)境中，不同的任務(wù)因應(yīng)用場景的不同，對處理的次序具有不同的需求。為了體現(xiàn)這種差異化的需求，本實驗假設(shè)所有設(shè)備共產(chǎn)生三種不同的任務(wù)類型，每個設(shè)備屬于一個單獨的用戶，且等概率地產(chǎn)生任一種任務(wù)類型。本文假設(shè)用戶的付出(即用戶影響xa)對優(yōu)先級的影響始終不小于任務(wù)自身的優(yōu)先級(即任務(wù)的優(yōu)先級Porg)，所以，假設(shè)三種任務(wù)類型的價值分別為3、2、1。為了簡化實驗場景，本實驗假設(shè)網(wǎng)絡(luò)條件是理想的，即不存在任何因網(wǎng)絡(luò)傳輸而造成的延遲。本實驗還為每個任務(wù)設(shè)置了一個容忍上限，一旦超出容忍上限，相應(yīng)的任務(wù)滿意度將被置為零；否則，只要超出預(yù)定義的任務(wù)滿意度閾值(此實驗定義為90%)即認為任務(wù)滿意度達標。由于個人滿意度等于它對應(yīng)的任務(wù)滿意度的平均值，因此個人滿意度閾值也為90%。本實驗在裝有IntelCore2QuadQ9550處理器和配置4GB內(nèi)存的Windows7系統(tǒng)中，進行了10輪模擬實驗，每輪分兩次調(diào)度100 000個任務(wù)。記錄并統(tǒng)計每輪的失敗次數(shù)、各用戶獲得的服務(wù)質(zhì)量、個人滿意度、系統(tǒng)滿意度。通過這些參數(shù)的比較，說明本文提出的調(diào)度算法確實為不同“用戶影響”的用戶提供了差異化服務(wù)，并且保證了個人滿意度和較高的系統(tǒng)滿意度。

圖2顯示了不同調(diào)度算法對個人滿意度的影響。從圖2中可以看出，使用本文提出的算法后，個人滿意度始終處于閾值之上，即系統(tǒng)提供了用戶滿意的服務(wù)；而使用FIFO算法和EDF算法時，個人滿意度始終處于閾值之下，即系統(tǒng)無法保證滿足用戶需求。這是由于FIFO算法沒有考慮用戶的差異化需求，僅僅按照到達順序進行調(diào)度，增大了高優(yōu)先級任務(wù)的延遲。EDF算法在排序中耗費了大量的時間，每個任務(wù)的到來都會導(dǎo)致所有待調(diào)度任務(wù)的重新排序，且EDF沒有考慮用戶影響對任務(wù)優(yōu)先級的作用，增大了用戶影響較大的任務(wù)延遲。

本文提出的調(diào)度算法以用戶滿意度為中心，綜合考慮了影響任務(wù)優(yōu)先級的各個因素，并通過合理調(diào)度與反饋調(diào)節(jié)，保證了用戶獲取所需的服務(wù)質(zhì)量，從而確保個人滿意度達標。

Figure 2 Schedule algorithms’ affection on personal satisfaction

圖3顯示了不同調(diào)度算法對系統(tǒng)滿意度的影響。從圖3中可以看出，采用本文提出的調(diào)度算法，系統(tǒng)滿意度始終高于采用FIFO算法和EDF算法時的情況。這是由于系統(tǒng)滿意度取決于所有任務(wù)滿意度加權(quán)和的平均值，本文提出的調(diào)度算法為用戶影響較高的任務(wù)賦予較大的優(yōu)先級，優(yōu)先滿足用戶影響較高的任務(wù)需求，同時通過反饋調(diào)節(jié)機制，保證了盡可能多的任務(wù)在調(diào)度過程獲取滿意的服務(wù)質(zhì)量。而FIFO算法和EDF算法并沒有考慮用戶的影響，增加了用戶影響較大的任務(wù)的延遲，降低了相應(yīng)的任務(wù)滿意度。因此，使用本文提出的算法時，系統(tǒng)滿意度高于其他兩種調(diào)度算法。

Figure 3 Schedule algorithms’ affection on system satisfaction

圖4顯示了用戶影響與服務(wù)質(zhì)量的關(guān)系。通過在實驗結(jié)果中選取個人滿意度達標的任務(wù)，展示中級用戶和高級用戶的服務(wù)質(zhì)量的差異。從圖4中可以看出，在個人滿意度達標的情況下，高級用戶的服務(wù)質(zhì)量要明顯高于中級用戶。這是由于高級用戶付出了更多的金錢和資源，它要求在達到同等個人滿意度的情況下，系統(tǒng)提供更高、更好的服務(wù)質(zhì)量。這也契合了本文調(diào)度算法提出的背景及實現(xiàn)方案。

Figure 4 Relationship between user affection and service quality

圖5顯示了失敗次數(shù)對個人滿意度的影響。它是將實驗結(jié)果按失敗次數(shù)遞增的順序繪制而成的。從圖5中可以看出，高級用戶的個人滿意度隨著失敗次數(shù)的增加而減小，但是，始終高于閾值；低級用戶的個人滿意度隨失敗次數(shù)的增加而快速降低，并且當失敗數(shù)大于某值時，個人滿意度低于閾值。這是由于在資源有限的情況下，當失敗次數(shù)大于某值時，必須通過犧牲低級用戶對應(yīng)的任務(wù)滿意度，來保障高級用戶的任務(wù)滿意度，從而在降低低級用戶個人滿意度，保證高級用戶個人滿意度的基礎(chǔ)上，獲得較高的系統(tǒng)滿意度。

Figure 5 Relationship between fail times and personal satisfaction

5 結(jié)束語

本文在物聯(lián)網(wǎng)背景下，以用戶為中心，根據(jù)用戶影響和任務(wù)的優(yōu)先權(quán)值對任務(wù)進行綜合調(diào)度，同時，通過反饋調(diào)節(jié)因子調(diào)整任務(wù)優(yōu)先級,最終達到為用戶提供滿意的差異化服務(wù)的目的。實驗表明，本文提出的物聯(lián)網(wǎng)環(huán)境下基于用戶滿意度的實時調(diào)度算法，能夠針對物聯(lián)網(wǎng)數(shù)據(jù)海量、實時的特性與需求，根據(jù)用戶影響，分配所需的系統(tǒng)資源，為不同的用戶提供滿意的服務(wù)，并提高系統(tǒng)滿意度。

在物聯(lián)網(wǎng)中，一個任務(wù)的狀態(tài)可能受到多個用戶的綜合影響，并隨用戶狀態(tài)、投入的變化而改變。如一個數(shù)據(jù)更新與發(fā)布任務(wù)，會受到關(guān)注它的用戶的綜合影響，并隨著關(guān)注人數(shù)、關(guān)注者等級的變化而變化。因此，如何在多個用戶的動態(tài)影響下合理地分配任務(wù)優(yōu)先級，從而獲取用戶滿意的服務(wù)質(zhì)量，將是下一步研究的方向。

[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] 汪培莊. 模糊數(shù)學(xué)及其應(yīng)用[J]. 河南師大學(xué)報 (自然科學(xué)版), 1983,6(2):1-20.

[15] 周津慧, 王宗, 楊宗奎, 等. 基于模糊評價方法的軟件質(zhì)量評價研究[J]. 系統(tǒng)工程與電子技術(shù), 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-),男,福建永定人，博士，高級工程師，研究方向為實時系統(tǒng)、實時數(shù)據(jù)庫和傳感器數(shù)據(jù)管理。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基金項目：國家自然科學(xué)基金面上資助項目(61273080)；國家科技重大項目(2012ZX01039-004)

TP301.6

A

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

王蓋(1989-),男，安徽宿州人，碩士生，研究方向為物聯(lián)網(wǎng)任務(wù)調(diào)度和數(shù)據(jù)處理。E-mail:jia.heaven@163.com

通信地址：100190 北京市海淀區(qū)中關(guān)村南四街4號中科院軟件研究所人機交互實驗室

Address:Institute of Software,Chinese Academy of Sciences,4 Zhongguancun South 4 St,Haidian District,Beijing 100190,P.R.China