智慧城市中QOE感知服務組合策略的研究

楊文青，劉廣鐘

(上海海事大學 信息工程學院，上海 201306)

0 引 言

物聯(lián)網(wǎng)是互聯(lián)網(wǎng)通過傳感器向物理世界的延伸，其目的是對物理世界實現(xiàn)智能化管理，一個城市只需要配置相應的物理設備和基本的運行參數(shù)，服務便可應用于每個城市[1-2]。但是由于物聯(lián)網(wǎng)服務的不斷完善，服務數(shù)量指數(shù)增長，相同或相似功能的服務增加導致請求者對服務質(zhì)量提出了要求[3]。針對物聯(lián)網(wǎng)服務在實際應用過程中存在的問題，研究人員通過研究不同側(cè)重點的服務組合方法取得了不盡相同的研究成果。例如，Bidi S A H等人提出了一種城市組合服務策略，用于提供日常城市任務調(diào)度的解決方案[4]；Han S N等人提出了基于實時web協(xié)議的IP智能對象服務組合，以“智能家居”為例，實現(xiàn)從起床、吃飯到上下班、休息的全過程[5]。文獻[6]擬議了一個配有RESTful物聯(lián)網(wǎng)的服務組合架構(gòu)，使用該架構(gòu)可以以最佳的方式接收城市服務商提供的城市交通信息。

蟻群算法自1991年被提出至今，成功解決了大量的服務選擇問題，但是由于服務組合過程中的動態(tài)性、不穩(wěn)定性、服務質(zhì)量屬性受限等問題[7]，很多學者選擇對蟻群算法進行改進。王秀亭等將服務組合映射為選擇起始服務到終止服務的最優(yōu)路徑選擇，并將服務的非功能屬性作為參數(shù)加入到ACO的啟發(fā)函數(shù)計算中，從而保證服務之間代價相等[8]；文獻[9]對ACO中的信息素更新方式進行了改進，另外還將改進ACO與其他仿生優(yōu)化算法融合，從而解決了ACO本身的停滯問題；為了克服傳統(tǒng)ACO易陷入局部最優(yōu)的問題，李東星等人分別從局部和全局尋優(yōu)兩個方面討論了狀態(tài)轉(zhuǎn)移概率的計算方法，并在此基礎上尋得全局最優(yōu)服務鏈[10]。

由于服務組合涉及大量影響因素建模問題，故相關(guān)學者普遍采用層次化的評分模型，將用戶偏好與評分聚合到滿意度函數(shù)中，從而提高用戶體驗質(zhì)量[11-12]；文獻[13]中建立了QOE多屬性評價模型，并給出了該評價模型在四種常用的執(zhí)行模式(分別是順序、平行、選擇和循環(huán))下的計算公式，為服務組合優(yōu)化問題提供了一定的理論支撐。

該文將提出的服務組合策略作為一種通用框架引入改進蟻群算法及QOE評價模型為用戶選擇最優(yōu)服務組合。將服務組合問題映射到DCOP模型中，針對蟻群算法不足之處進行修繕，結(jié)合服務中的QOE屬性改進狀態(tài)轉(zhuǎn)移概率公式和信息素更新方式，形成基于QOE影響因素的HA-ACO算法。該策略使全局搜索最優(yōu)服務的能力增加，從而提高了尋得最優(yōu)解的概率。

1 擬議的服務組合策略

1.1 基于RESTful物聯(lián)網(wǎng)的服務選擇模型

圖1是基于RESTful物聯(lián)網(wǎng)的服務選擇模型，該模型由用戶、服務提供商和中央智能城市控制器(central smart city controller，CSCC)三個元素組成。其工作原理是：物聯(lián)網(wǎng)傳感器不斷感知和收集來自各個服務供應商的服務和流量信息，所有的服務提供商使用JSON消息中的RESTful Web服務在CSCC中注冊，注冊之后可以將服務描述信息發(fā)布到注冊中心。CSCC以一定的方式存儲和管理服務描述。該模型中以JSON格式響應初始請求，當接收到一組抽象服務AS={A1，A2，…，An},CSCC會為每一個抽象服務Ai在智慧城市數(shù)據(jù)庫中找到一組具體服務CS,并返回一個解決方案CS={CS1，CS2，…，CSn}。

1.2 使用DCOP模型描述服務組合問題

表1 服務選擇問題與DCOP

在DCOP框架中，為了收斂到最優(yōu)解，代理之間必須相互通信，對于任意兩個服務，局部變量的最優(yōu)值導致全局變量的最優(yōu)值，每兩個變量的局部成本之和cij共享一個約束。

(1)

賦值變量Af將變量xi，xj映射到di∈Di中。

對于物聯(lián)網(wǎng)中的服務組合問題，需要擴展DCOP以滿足用戶指定的全局約束，主要體現(xiàn)在QOS屬性的約束上。QOS屬性的約束向量可以表示為：Bound=(Bound1,Bound2,…,BoundL)，L表示約束的數(shù)量，同時定義如下布爾函數(shù)CONSTRAINT(Vr,Boundr,Opr)來驗證用戶指定的第r次約束是否滿足，Vr表示在第r次獲得一個可行的解決方案的值，通過如下表達式獲得：

(2)

其中，qr(a),qr(b)表示具體服務a,b在第r次得到的QOS屬性值；運算符Opr可以是>，<，≤，≥。因此解決服務選擇問題是要為抽象服務asi選擇一組具體服務CS={CS1,CS2,…,CSn}并且滿足如下要求：

(1)式(2)中定義的全局成本最?。?/p>

(2)具體服務CS的全局質(zhì)量的QOS屬性值(Vr)必須滿足用戶約束(Boundr)：

(3)

2 面向QOE約束的仿生學服務選擇算法

使用DCOP模型描述完服務組合問題后，需要結(jié)合用戶約束來選擇服務組合。智慧城市中的服務之間存在差異，QOE屬性目標之間沒有統(tǒng)一的標準，因此選擇最優(yōu)服務組合本質(zhì)上就是QOE的多目標優(yōu)化問題。同時，物聯(lián)網(wǎng)服務大多依附在移動設備上，智能主體往往根據(jù)客觀環(huán)境變化做出相應改變。鑒于上述問題，借用群體仿生學優(yōu)化算法可以巧妙地提出應對策略。故該文針對物聯(lián)網(wǎng)服務的特點和現(xiàn)有服務選擇方法的不足，提出了改進的蟻群算法——HA-ACO。ACO的主要任務是從大量的候選服務中選擇符合用戶偏好需求的組合序列，旨在從一系列組合問題中找到最優(yōu)解[14]。HA-ACO克服傳統(tǒng)服務選擇類算法只考慮單一服務屬性的問題，實現(xiàn)動態(tài)服務組合的最優(yōu)QOE。

2.1 HA-ACO的信息素更新方式

與窮舉搜索法、貪婪法相比，ACO效率更高的原因在于該算法的信息素更新規(guī)則。而在選擇服務時，路徑上殘留的信息素濃度會隨時間揮發(fā)而減少，因此為了避免信息素濃度改變對路徑選擇造成影響，需要更新信息素濃度。該文基于式(4)改進信息素更新方式：

(4)

具體改進方法如下：設S為路徑(i，j)的一個服務，該服務共有n個QOS屬性Q1，Q2，…，Qn，這些屬性對應的量化值轉(zhuǎn)換函數(shù)為Q1(S)，Q2(S),…，Qn(S)，則算法中服務S的第r個QOS屬性對應的信息素計算公式為：

(5)

2.2 HA-ACO的狀態(tài)轉(zhuǎn)移概率公式

螞蟻的移動過程是ACO解決服務選擇問題的核心。根據(jù)ACO的覓食原理，每當螞蟻經(jīng)過一個服務類，都必須計算從當前服務到下一服務類的每一個服務的轉(zhuǎn)移概率。這一過程確保了尋得最佳路徑的有效概率和算法的多樣性。狀態(tài)轉(zhuǎn)移概率公式如下：

(6)

其中，cij(t)為(i,j)邊上的信息素濃度，ηij(t)為服務i轉(zhuǎn)移到服務j的啟發(fā)式因子，a,b分別為信息素和啟發(fā)式因子的相對重要程度，ak為螞蟻接下來可以訪問的服務集。

在搜索過程中，螞蟻除了根據(jù)信息素濃度cij(t)來確定狀態(tài)轉(zhuǎn)移概率外，啟發(fā)函數(shù)ηij(t)也會對算法的收斂速度和收斂性產(chǎn)生影響。因此在利用蟻群算法選擇服務時，為了滿足客戶的體驗質(zhì)量，不能只考慮當前服務的選擇，而應側(cè)重于整體的服務解集。故在HA-ACO算法中，將后一服務的非功能屬性值加入到啟發(fā)函數(shù)ηij(t)中，這樣可以平衡當前服務到后面任一服務的代價。計算公式如式(7)所示：

(7)

Q(t)代表下一個服務j的響應時間、服務代價和服務的可行性等屬性的綜合值。要特別說明：單個服務可行性以倒數(shù)的形式呈現(xiàn)，這樣在量化過程中，服務的響應時間、服務代價越小，可行性越大，啟發(fā)信息就越大，在螞蟻選擇下一服務中的受重視程度也就越大。

2.3 HA-ACO算法實現(xiàn)

基于HA-ACO算法選擇最優(yōu)服務組合流程如下：

(1)初始化循環(huán)次數(shù)：N=0，最大循環(huán)次數(shù)Nmax，本次循環(huán)螞蟻走過的路徑列表Lk，螞蟻數(shù)量K=0，最大螞蟻數(shù)量Kmax，單次循環(huán)最優(yōu)組合列表I，最優(yōu)服務組合列表L。

(2)N=N+1，若循環(huán)次數(shù)N大于Nmax，轉(zhuǎn)至步驟7。

(3)K=K+1，若螞蟻數(shù)量K大于Kmax，轉(zhuǎn)至步驟6。

(4)螞蟻移動到下一節(jié)點的概率根據(jù)信息素濃度和啟發(fā)式函數(shù)確立。再利用輪盤賭算法選出要走的路徑，并將相關(guān)的路徑信息寫入路徑表和禁忌表。螞蟻移動至下一個服務類。

(5)判斷螞蟻所在的節(jié)點，如果它是末端節(jié)點，則將本次循環(huán)的服務路徑與I中的信息素濃度比較，如果前者更優(yōu)，則替換I中的服務類，執(zhí)行下一步。否則轉(zhuǎn)至步驟4。

(6)計算本次循環(huán)路徑表Lk中的信息素增量，更新所有路徑信息素濃度。轉(zhuǎn)至步驟2。

(7)比較信息素濃度最高的服務路徑和單次循環(huán)最優(yōu)組合列表I中的路徑，若相同，則輸出L中信息素濃度最高的服務組合方案給用戶；若不同，則輸出I中結(jié)果。算法結(jié)束。

3 QOE的預測和評價方法

使用HA-ACO選擇服務組合后，中央智能城市控制器需要判斷是否將該服務分配給用戶，因此涉及到QOE的評價問題。起初，QOE的概念主要用于衡量用戶對網(wǎng)絡層QOS的評價，而后ITU-T將QOE的衡量范圍擴展到服務層面，強調(diào)用戶對服務質(zhì)量的整體感知[15]。結(jié)合智慧城市中的應用服務豐富多樣、評價指標各不相同的特點，該文選擇具有可伸縮多層次的評價分析法來量化用戶滿意度。

圖2是結(jié)合物聯(lián)網(wǎng)服務的特點構(gòu)建的三層評分模型，該模型將服務提供商提供的服務擴展到多個評分層次，由最上層的總評分向下延伸，每個層次包含多個評分小項。其中，第一層為用戶對服務的滿意程度，也是最高總評分，受下兩層評分項的影響；第二層按影響因素細分為四個方面，分別是：服務商家的品牌、內(nèi)容、可訪問性、功能；第三層從QOS的角度又進一步細分出來更容易量化的評分項，比如將品牌展開為行業(yè)排名，可訪問性展開為網(wǎng)絡帶寬等等。

圖2 QOE層次化評價模型

建立QOE評分層次體系結(jié)構(gòu)之后，還需要確立與QOE相關(guān)的各個層次的評分權(quán)重，最后逐層向上追溯，便可確定最高層相較于底層的相對重要程度。

(8)

假設層次化模型的最底層有n個評分項，總評分為S，第i個評分項記為li，由于總評分和各子層之間存在線性關(guān)系，故總評分S可以寫成與li的關(guān)系式，即：

(9)

其中，βi與各層加權(quán)系數(shù)有關(guān)，∑βi=1。

層次化模型的最底層葉子節(jié)點給出的評分li來自用戶的主觀體驗，研究領(lǐng)域的專家會為每一個影響因素指定一個客觀的評分標準pi，由此可以得出用戶的主觀因素占基準評分的比例，用下式表示：li/pi=ηi，ηi為主觀評價因子，代表用戶的主觀體驗差異。

基于上述，可重寫式(9)中的關(guān)系式：

(10)

如果將主觀評價因子和各層加權(quán)系數(shù)合并為ωi=βiηi的表達式，則上式又可以重寫為：

(11)

其中，ωi為用戶對評分項i的偏好權(quán)重。

若采用矢量化的形式表示P=(p1,p2,…,pn),W=(ω1,ω2,…,ωn)，則式(11)可寫成：

S=P·WT

(12)

式(12)稱為QOE的量化評估函數(shù)。

通過HA-ACO獲取到用戶對這些服務的偏好順序后，便可根據(jù)式(12)量化評估，最終確定特定服務提供給用戶。

4 實驗結(jié)果與分析

4.1 仿真實驗設計

為了在智慧城市中高效選擇滿足用戶需求的服務，該文提出了一種服務組合選擇策略。服務組合策略具體工作流程描述如下：

(1)用戶提出服務請求，CSCC在用戶數(shù)據(jù)庫中查找用戶的偏好。如果查找失敗，則后臺初始化一個用戶偏好；

(2)利用改進的蟻群算法HA-ACO選擇用戶對所請求服務的偏好排序；

(3)CSCC在第(2)步的基礎上后臺獲取服務組合的基準評分，基于式(12)中的滿意度函數(shù)得到服務的QOE值；選取最大QOE值的服務提供給用戶；

(4)獲得用戶對所使用服務的評價，在數(shù)據(jù)庫中更新用戶的偏好以備下次進行服務匹配。

以上服務選擇過程用MATLAB實現(xiàn)，執(zhí)行過程描述如下：

//為每個服務添加QOE屬性值

if(E is not null)

{

for(each e in E)

{

for (each service in service(e))

{

if(service_added is False)

{

Character_value=F(service);

Service_added=True;

}

}

}

}

//標注所有輸入節(jié)點；

for (each si1in si )

{

if(tag(si1)==False)

{

tag(si1)=True;

}

else continue;

}

//求出滿足用戶需求的候選服務

for(each si1->si2in kq)

{

if (si1不可達si2)

building new service ;

else {

if (only one path satisfied si1->si2and min(service(e)))

select service on this path;

else

利用HA-ACO算法求出所有min(service(e))中的服務偏好

}

}

//量化評估候選服務

if Ur-pref is not null

{

get the basic service rates ->service_stat;

QOE_value->Ur_prefT*service_stat;

ID of the service with max QOE_value->Svr_ID;

}

4.2 實 驗

本實驗全部運行在一臺win10 64bit操作系統(tǒng)、CPU為i5、內(nèi)存為8 GB的計算機上，使用MATLAB仿真實現(xiàn)。接入環(huán)境同時存在WIFI和4G網(wǎng)絡。實驗采用圖2所示的三層評分體系結(jié)構(gòu)，第三層對應所需服務的各屬性評分項，評分標準參考文獻[12]給出，每一個模擬用戶設置五種相應的偏好值，有五個級別的評判標準，即：V={Ⅰ級，Ⅱ級，Ⅲ級，Ⅳ級，Ⅴ}，等級越高，用戶對服務越滿意。

在服務選擇問題求解過程中，每一次算法的迭代時間太長都會造成服務組合問題求解速度慢的后果，即使最后尋得最優(yōu)解，也會因無法滿足實際問題需求而導致算法策略失效。為了驗證提出的服務組合策略的有效性，實驗通過對比不同服務規(guī)模觀察CPU的運行速度隨迭代次數(shù)變化的情況。首先將服務種群規(guī)模設定為三種類型，種群數(shù)量分別為5、10、15，借此來驗證服務種群規(guī)模對算法運行時間的影響。其次，設定算法的迭代次數(shù)分別為10、20、30和40，為了避免計算機穩(wěn)定性對算法結(jié)果造成影響，每種情況下分別運行10次，取平均值，如圖3所示。

圖3 服務組合策略的平均執(zhí)行時間

實驗結(jié)果表明：算法消耗的時間并沒有隨服務種群規(guī)模的增加而增大，在種群規(guī)模為10時，循環(huán)迭代40次所需要的時間僅12秒，這個運算速度能夠滿足大多數(shù)用戶在服務請求時的時間需求，因此服務組合策略的有效性非常明顯。

5 結(jié)束語

主要研究了求解智慧城市中服務組合選擇問題以及客戶QOE量化評估問題，分別提出了相應的解決方案并應用于仿真實例中，取得了良好的結(jié)果。雖然該服務組合策略表現(xiàn)出較優(yōu)的性能，但是仍存在許多不足之處，需要進一步改進和優(yōu)化。實驗仿真采用的數(shù)據(jù)是模擬真實的“服務請求→服務選擇→服務分派”流程，雖然真實性很高，但是仍然缺乏現(xiàn)實物聯(lián)網(wǎng)服務的大環(huán)境。下一步工作將應用服務組合選擇策略到真實的服務數(shù)據(jù)中，以保證該方法在實際城市生活中的可行性和普適性。