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

楊文青，劉廣鐘

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

0 引 言

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

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

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

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

1 擬議的服務(wù)組合策略

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

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

1.2 使用DCOP模型描述服務(wù)組合問(wèn)題

表1 服務(wù)選擇問(wèn)題與DCOP

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

(1)

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

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

(2)

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

(1)式(2)中定義的全局成本最小；

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

(3)

2 面向QOE約束的仿生學(xué)服務(wù)選擇算法

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

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

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

(4)

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

(5)

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

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

(6)

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

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

(7)

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

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

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

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

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

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

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

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

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

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

3 QOE的預(yù)測(cè)和評(píng)價(jià)方法

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

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

圖2 QOE層次化評(píng)價(jià)模型

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

(8)

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

(9)

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

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

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

(10)

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

(11)

其中，ωi為用戶對(duì)評(píng)分項(xiàng)i的偏好權(quán)重。

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

S=P·WT

(12)

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

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

4 實(shí)驗(yàn)結(jié)果與分析

4.1 仿真實(shí)驗(yàn)設(shè)計(jì)

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

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

(2)利用改進(jìn)的蟻群算法HA-ACO選擇用戶對(duì)所請(qǐng)求服務(wù)的偏好排序；

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

(4)獲得用戶對(duì)所使用服務(wù)的評(píng)價(jià)，在數(shù)據(jù)庫(kù)中更新用戶的偏好以備下次進(jìn)行服務(wù)匹配。

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

//為每個(gè)服務(wù)添加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;

}

}

}

}

//標(biāo)注所有輸入節(jié)點(diǎn)；

for (each si1in si )

{

if(tag(si1)==False)

{

tag(si1)=True;

}

else continue;

}

//求出滿足用戶需求的候選服務(wù)

for(each si1->si2in kq)

{

if (si1不可達(dá)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))中的服務(wù)偏好

}

}

//量化評(píng)估候選服務(wù)

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 實(shí) 驗(yàn)

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

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

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

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

5 結(jié)束語(yǔ)

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