楊文青，劉廣鐘

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

0 引 言

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

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

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

該文將提出的服務(wù)組合策略作為一種通用框架引入改進蟻群算法及QOE評價模型為用戶選擇最優(yōu)服務(wù)組合。將服務(wù)組合問題映射到DCOP模型中，針對蟻群算法不足之處進行修繕，結(jié)合服務(wù)中的QOE屬性改進狀態(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)三個元素組成。其工作原理是：物聯(lián)網(wǎng)傳感器不斷感知和收集來自各個服務(wù)供應(yīng)商的服務(wù)和流量信息，所有的服務(wù)提供商使用JSON消息中的RESTful Web服務(wù)在CSCC中注冊，注冊之后可以將服務(wù)描述信息發(fā)布到注冊中心。CSCC以一定的方式存儲和管理服務(wù)描述。該模型中以JSON格式響應(yīng)初始請求，當接收到一組抽象服務(wù)AS={A1，A2，…，An},CSCC會為每一個抽象服務(wù)Ai在智慧城市數(shù)據(jù)庫中找到一組具體服務(wù)CS,并返回一個解決方案CS={CS1，CS2，…，CSn}。

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

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

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

(1)

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

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

(2)

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

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

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

(3)

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

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

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

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

(4)

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

(5)

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

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

(6)

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

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

(7)

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

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

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

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

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

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

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

3 QOE的預(yù)測和評價方法

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

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

圖2 QOE層次化評價模型

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

(8)

假設(shè)層次化模型的最底層有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獲取到用戶對這些服務(wù)的偏好順序后，便可根據(jù)式(12)量化評估，最終確定特定服務(wù)提供給用戶。

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

4.1 仿真實驗設(shè)計

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

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

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

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

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

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

//為每個服務(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;

}

}

}

}

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

for (each si1in si )

{

if(tag(si1)==False)

{

tag(si1)=True;

}

else continue;

}

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

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))中的服務(wù)偏好

}

}

//量化評估候選服務(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 實 驗

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

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

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

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

5 結(jié)束語

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