一種移動(dòng)邊緣計(jì)算環(huán)境中服務(wù)QoS的預(yù)測(cè)方法

任麗芳，王文劍

1(山西財(cái)經(jīng)大學(xué)信息學(xué)院，太原030006)

2(山西大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院，太原030006)

1 引 言

移動(dòng)邊緣計(jì)算(Mobile Edge Computing，MEC)通過在終端設(shè)備和云之間引入邊緣設(shè)備，將云服務(wù)擴(kuò)展到網(wǎng)絡(luò)邊緣，實(shí)現(xiàn)了在移動(dòng)用戶附近提供服務(wù)，降低云服務(wù)器的計(jì)算負(fù)載，減緩網(wǎng)絡(luò)帶寬的壓力［1，2］.隨著智能移動(dòng)終端的日益普及，可以在移動(dòng)設(shè)備上運(yùn)行的移動(dòng)服務(wù)已經(jīng)被大量開發(fā)，并通過訪問移動(dòng)邊緣服務(wù)器被調(diào)用［2］.因此，為用戶推薦服務(wù)或者為服務(wù)組合選擇組件服務(wù)就需要在這種移動(dòng)邊緣計(jì)算環(huán)境中進(jìn)行考慮，而服務(wù)選擇與推薦又以服務(wù)QoS (quality of service，服務(wù)質(zhì)量)為依據(jù).服務(wù)的QoS 屬性主要包括:可用性、響應(yīng)時(shí)間、吞吐率等一組性能指標(biāo)，其中每個(gè)QoS 屬性都用于表征服務(wù)在某一方面的質(zhì)量信息.因此，服務(wù)QoS 值的預(yù)測(cè)成為服務(wù)推薦與服務(wù)選擇中重要的基礎(chǔ)工作.在移動(dòng)邊緣計(jì)算環(huán)境中，由于移動(dòng)用戶在各個(gè)邊緣節(jié)點(diǎn)之間的移動(dòng)，導(dǎo)致所訪問的邊緣服務(wù)器隨時(shí)可能發(fā)生切換，使得邊緣計(jì)算環(huán)境中的服務(wù)QoS 預(yù)測(cè)成為了一個(gè)挑戰(zhàn)［3］.

已有不少工作致力于服務(wù)QoS 預(yù)測(cè)，現(xiàn)有的方法主要是基于協(xié)同過濾(collaborative filtering，CF)的，這些方法又可分為基于內(nèi)存的(memory-based)方法［4-7］和基于模型的(modelbased)方法［8-12］.在協(xié)同過濾方法的基礎(chǔ)上，又發(fā)展起了情境感知的服務(wù)QoS 預(yù)測(cè)方法［12-20］.

基于內(nèi)存的方法根據(jù)歷史QoS 數(shù)據(jù)挖掘用戶之間和服務(wù)之間的相似性，基于與當(dāng)前用戶相似的用戶對(duì)目標(biāo)服務(wù)的QoS 和當(dāng)前用戶對(duì)與目標(biāo)服務(wù)相似的服務(wù)的QoS 對(duì)當(dāng)前用戶使用目標(biāo)服務(wù)的 Q oS 做出預(yù)測(cè).如 S hao 等人［4］基于用戶在相同的服務(wù)上的相似經(jīng)歷提出了基于相似用戶的個(gè)性化服務(wù)預(yù)測(cè)方法.Zheng 等人［5］集成了用戶和服務(wù)的相似性對(duì)當(dāng)前用戶調(diào)用目標(biāo)服務(wù)的QoS 進(jìn)行預(yù)測(cè).Jiang 等人［6］在度量用戶或服務(wù)的相似性時(shí)考慮了共同用戶或者共同服務(wù)的標(biāo)準(zhǔn)差.李昆侖等人［7］通過將用戶評(píng)分的均值差引入對(duì)用戶相似度的計(jì)算，將相似的兩個(gè)向量的均值引入對(duì)向量缺失值的填充并實(shí)現(xiàn)降維，基于改進(jìn)的用戶相似性度量和評(píng)分預(yù)測(cè)的提出了一種協(xié)同過濾推薦算法.這類基于內(nèi)存的服務(wù)QoS 預(yù)測(cè)方法有較強(qiáng)的可解釋性，然而在實(shí)踐中，由于歷史QoS 數(shù)據(jù)極其稀疏，相似用戶或相似服務(wù)很難找到.

基于模型的方法從歷史QoS 或者評(píng)分?jǐn)?shù)據(jù)中學(xué)習(xí)隱藏在數(shù)據(jù)背后的QoS 或者評(píng)分模式，并建立模型對(duì)未知QoS 進(jìn)行預(yù)測(cè).Yu 等人［8］基于QoS 矩陣是低秩的或者近似低秩的假設(shè)提出了基范數(shù)正則化的矩陣分解方法對(duì)未知QoS 進(jìn)行預(yù)測(cè).Zhang 等人［9］提出了非負(fù)張量分解的方法來對(duì)基于時(shí)間的QoS 進(jìn)行預(yù)測(cè).Zheng 等人［10］集成了基于相似用戶的方法與矩陣分解的方法對(duì)未知服務(wù)QoS 進(jìn)行個(gè)性化預(yù)測(cè).Ren和Wang［11］提出了基于SVM 的協(xié)同過濾方法SVM4SR 對(duì)未知服務(wù)的評(píng)分排序進(jìn)行預(yù)測(cè)，進(jìn)而實(shí)現(xiàn)服務(wù)推薦.文獻(xiàn)［12］通過粒化思想對(duì)SVM4SR 進(jìn)行優(yōu)化，進(jìn)一步提升模型的精度與效率.基于模型的方法總會(huì)在模型復(fù)雜度和預(yù)測(cè)準(zhǔn)確度之間權(quán)衡，為了提升預(yù)測(cè)準(zhǔn)確度而使用越來越復(fù)雜的模型.

情境感知的方法將用戶-服務(wù)QoS 或評(píng)分?jǐn)?shù)據(jù)之外的信息包含到協(xié)同過濾的方法中以進(jìn)一步提高預(yù)測(cè)的準(zhǔn)確度.如Chen 等人［13］利用位置信息對(duì)用戶和服務(wù)聚類，基于聚類結(jié)果對(duì)QoS 進(jìn)行個(gè)性化預(yù)測(cè).唐明董等人［14］基于QoS 屬性受用戶位置影響的事實(shí)，提出了位置感知的Web 服務(wù)QoS 預(yù)測(cè)方法.Qiu 等人［15］基于歷史數(shù)據(jù)感知用戶的信任，識(shí)別并排除掉不可信用戶，提高了 Q oS 值預(yù)測(cè)的準(zhǔn)確度.Wang 等人［16］通過采用累積和控制圖檢測(cè)惡意反饋的等級(jí)，然后提出Bloom 過濾惡意反饋，減少信譽(yù)度量中的偏差.朱文強(qiáng)等人［17］、Deng 等人［18］通過評(píng)估用戶在社區(qū)網(wǎng)絡(luò)的信任關(guān)系，增強(qiáng)服務(wù)推薦的可信度.張鵬程等人［19］、申利民等人［20］感知環(huán)境要素隨時(shí)間變化導(dǎo)致服務(wù)QoS 波動(dòng)，分別提出一種基于時(shí)間序列分析的QoS 預(yù)測(cè)方法.情境感知的方法就各自所關(guān)心所感知的方面預(yù)測(cè)精度都有所提高.

綜上所述，這些研究都是非常有意義的工作，為提升未知服務(wù)的個(gè)性化QoS 預(yù)測(cè)的準(zhǔn)確性做出了很大貢獻(xiàn).然而，這些研究主要針對(duì)傳統(tǒng)的Internet 環(huán)境，認(rèn)為同一個(gè)用戶使用相同的服務(wù)其QoS 值就是確定的.然而，在移動(dòng)環(huán)境中，由于用戶的位置移動(dòng)可能引起邊緣服務(wù)器的切換，使得接收信號(hào)發(fā)生變化，導(dǎo)致同一用戶多次使用相同的服務(wù)其QoS 也不盡相同，因此傳統(tǒng)方法的 Q oS 預(yù)測(cè)值就會(huì)出現(xiàn)較大的偏差［21，22］.

邊緣計(jì)算模型將原有云計(jì)算模型執(zhí)行的部分或者全部計(jì)算任務(wù)遷移到邊緣設(shè)備上，為移動(dòng)計(jì)算等相關(guān)技術(shù)提供了一個(gè)更好的計(jì)算平臺(tái)［1］.因此，本文考慮邊到緣計(jì)算環(huán)境中移動(dòng)用戶位置的改變會(huì)導(dǎo)致所訪問的邊緣服務(wù)器的切換，提出了移動(dòng)邊緣計(jì)算環(huán)境中服務(wù)QoS 預(yù)測(cè)方法(EQoSP，Edgecomputing QoS Prediction)，在對(duì)服務(wù)的QoS 值進(jìn)行預(yù)測(cè)時(shí)考慮當(dāng)前用戶所訪問的邊緣服務(wù)器.希望能得到更準(zhǔn)確的QoS預(yù)測(cè)值，為移動(dòng)邊緣環(huán)境中服務(wù)推薦和服務(wù)選擇提供依據(jù).

2 相關(guān)工作

傳統(tǒng)的服務(wù)QoS 預(yù)測(cè)方法，沒有考慮移動(dòng)邊緣計(jì)算環(huán)境中用戶通過訪問不同的邊緣服務(wù)器使用同一服務(wù)，預(yù)測(cè)QoS值的偏差可能較大.為解決這一問題，已有不少研究致力于移動(dòng)網(wǎng)絡(luò)環(huán)境的服務(wù)QoS 預(yù)測(cè).

Chen 等人［13］提出了區(qū)域相似性的概念，并通過 I P 地址來檢索相似用戶的位置，利用位置信息和QoS 值對(duì)用戶和服務(wù)進(jìn)行聚類，并根據(jù)聚類結(jié)果對(duì)用戶進(jìn)行個(gè)性化服務(wù)推薦，IP地址的引入體現(xiàn)了該方法對(duì)網(wǎng)絡(luò)位置的感知，從而為用戶推薦其所在位置QoS 最優(yōu)的服務(wù).Deng 等人［21］感知用戶移動(dòng)導(dǎo)致接收的網(wǎng)絡(luò)信號(hào)的變化，在對(duì)移動(dòng)服務(wù)QoS 的計(jì)算模型中考慮了輸入輸出所需的時(shí)間，提出了移動(dòng)環(huán)境下服務(wù)組合中的組件選擇的方法，該方法感知用戶移動(dòng)中接收到的網(wǎng)絡(luò)信號(hào)強(qiáng)弱不同，導(dǎo)致輸入輸出的時(shí)間不同，從而選擇最適合當(dāng)前位置的組件服務(wù).Wang 等［22］為實(shí)現(xiàn)邊緣服務(wù)器計(jì)算環(huán)境下的移動(dòng)服務(wù)推薦，基于用戶的移動(dòng)性，通過相似用戶和相似邊緣服務(wù)器的歷史QoS 數(shù)據(jù)對(duì)用戶位置發(fā)生移動(dòng)后的服務(wù)QoS 進(jìn)行預(yù)測(cè).文中的相似用戶和相似服務(wù)器都采用Top-k個(gè)，然而實(shí)踐中固定的k 值如果太小容易損失部分相似信息，反之如果k 值太大就會(huì)將一些并不相似信息考慮在內(nèi)，影響QoS 預(yù)測(cè)的準(zhǔn)確性.

不同于上述研究，本文不使用傳統(tǒng)的固定的Top-k 相似用戶和相似服務(wù)的個(gè)數(shù)，而是基于歷史QoS 通過聚類自然地個(gè)性化地為每個(gè)用戶和邊緣服務(wù)器確定相似用戶和相似邊緣服務(wù)器的個(gè)數(shù)，以求更準(zhǔn)確的服務(wù)QoS 預(yù)測(cè).

3 本文方法

本文首先通過聚類分析為當(dāng)前用戶/邊緣服務(wù)器尋找相似用戶/邊緣服務(wù)器，然后計(jì)算相似用戶與當(dāng)前用戶及相似邊緣服務(wù)器與當(dāng)前邊緣服務(wù)器之間的相似度，最后基于相似用戶/邊緣服務(wù)器的歷史QoS 數(shù)據(jù)對(duì)當(dāng)前用戶在當(dāng)前邊緣服務(wù)器附近使用目標(biāo)服務(wù)的QoS 進(jìn)行預(yù)測(cè).

本節(jié)首先通過一個(gè)情景案例說明邊緣計(jì)算環(huán)境的QoS 預(yù)測(cè)的兩種不同情形，然后給出模型定義，通過聚類確定相似用戶/邊緣服務(wù)器的方法，以及用戶之間/邊緣服務(wù)器之間相似性的度量方法，最后給出兩種不同情況下未知QoS 的預(yù)測(cè)方法.

3.1 情景案例

設(shè)想用戶u 經(jīng)常用手機(jī)通過訪問邊緣服務(wù)器e1來調(diào)用服務(wù)s，現(xiàn)在用戶u 來到另一個(gè)邊緣服務(wù)器e2的附近，但他仍然想用服務(wù)s.我們需要通過對(duì)用戶在邊緣服務(wù)器e2附近使用服務(wù)s 的QoS 預(yù)測(cè)，決定訪問邊緣服務(wù)器e2還是周圍其他邊緣服務(wù)服務(wù)器.此時(shí)，有如下兩種情況［22］.

情況1.邊緣服務(wù)器e2上有服務(wù)s 的調(diào)用歷史QoS 數(shù)據(jù);此時(shí)，我們需要通過e2上s 的歷史QoS 值預(yù)測(cè)用戶使用服務(wù)s 的 Q oS 值.

情況2.邊緣服務(wù)器e2上不存在服務(wù)s 的調(diào)用歷史QoS記錄.此時(shí)，我們需要通過周邊其他邊緣服務(wù)器預(yù)測(cè)用戶訪問服務(wù)s的QoS值.

3.2 模型定義

定義1.用戶(User)在這里是一個(gè)廣義的概念，指移動(dòng)邊緣計(jì)算環(huán)境中的所有終端設(shè)備，包含移動(dòng)設(shè)備，可移動(dòng)的物聯(lián)網(wǎng)設(shè)備等.一個(gè)用戶可以被形式化為一個(gè)二元組(ui，UQo-Si)，其中:

ui是用戶i 的標(biāo)識(shí)，通過用戶標(biāo)識(shí)可以唯一地確定一個(gè)用戶;

UQoSi是用戶i 在移動(dòng)邊緣計(jì)算環(huán)境中使用服務(wù)的歷史QoS 記錄.

定義2.服務(wù)(Service)在這里特指可以通過移動(dòng)終端設(shè)備訪問的資源.一個(gè)服務(wù)可以形式化為一個(gè)三元組(si，fun，SQoSi)，其中:

si是服務(wù)i 的標(biāo)識(shí)，通過服務(wù)標(biāo)識(shí)可以唯一地確定一個(gè)服務(wù);

fun 是服務(wù)的功能分類號(hào)，通過fun 可以確定調(diào)用該服務(wù)可以實(shí)現(xiàn)的功能;

SQoSi是服務(wù)i 在移動(dòng)邊緣計(jì)算環(huán)境中被用戶調(diào)用的歷史QoS 記錄.

定義3.邊緣服務(wù)器(Edge Server)是分布在終端設(shè)備和云之間靠近移動(dòng)終端的邊緣節(jié)點(diǎn).一個(gè)邊緣服務(wù)器可以被形式化為一個(gè)三元組(ei，Loc，EQoSi)，其中:

ei是邊緣服務(wù)器i 的標(biāo)識(shí)，通過邊緣服務(wù)器標(biāo)識(shí)可以唯一地確定一個(gè)邊緣服務(wù)器;

Loc 是邊緣服務(wù)器的部署位置，位置決定邊緣服務(wù)器的服務(wù)覆蓋范圍;

EQoSi是通過訪問邊緣服務(wù)器i 調(diào)用服務(wù)的QoS 歷史記錄.

3.3 相似用戶/邊緣服務(wù)器的確定

本文采用k-means++聚類的方式分別對(duì)用戶空間和邊緣服務(wù)器空間進(jìn)的歷史數(shù)據(jù)進(jìn)行分析.

K-means 算法因?qū)崿F(xiàn)簡(jiǎn)單且運(yùn)算速度快，成為一種最常用的無監(jiān)督聚類算法，其基本思想是:按照樣本之間的距離大小，將給定的樣本集劃分為k 個(gè)簇(cluster)，力求簇內(nèi)樣本點(diǎn)盡量緊密，而簇間距離盡量大.設(shè)樣本集被劃分為k 個(gè)簇Ci(i=1，2，…，k)，則 k-means 算法的目標(biāo)是最小化平方誤差，其中是簇 Ci的質(zhì)心.質(zhì)心的選擇對(duì)最后的聚類效果和運(yùn)行時(shí)間有很大的影響，如果僅僅是完全隨機(jī)地去選擇，有可能導(dǎo)致算法收斂很慢.因此，本文采用k-means++算法，隨機(jī)地選取第一個(gè)質(zhì)心，在選取第n+1 個(gè)聚類中心時(shí)，距離當(dāng)前n 個(gè)聚類中心越遠(yuǎn)的點(diǎn)會(huì)有更高的概率被選為第n+1 個(gè)聚類中心，優(yōu)化對(duì)質(zhì)心的選擇.此外，類簇個(gè)數(shù)k 值的確定也是這類算法的關(guān)鍵.由于在聚類之前用戶和邊緣服務(wù)器可能的類簇個(gè)數(shù)并不確定，因此，本文采用如式(1)定義的 DB 指數(shù)(Davies-Bouldin Index，DBI)作為聚類的優(yōu)化目標(biāo).

其中，avg(Ci)代表類簇Ci內(nèi)樣本間的平均距離，d(μi，μj)是類簇Ci與Cj的質(zhì)心μi與μj之間的距離.可以看出，類內(nèi)距離越小而類間距離越大時(shí)DBI 越小，因此，本文選擇使DBI 取最小值的k 作為類簇個(gè)數(shù).

在進(jìn)行聚類前，本文首先構(gòu)造用戶數(shù)據(jù)集U.歷史QoS 數(shù)據(jù)集HQoS 是一個(gè)m×n×l 的3 階張量，其中第1 維代表 m個(gè)用戶，第2 維代表n 個(gè)服務(wù)，第3 維表示l 個(gè)邊緣服務(wù)器.其每個(gè)元素 HQoSi，j，f表示在第 f 個(gè)邊緣服務(wù)器上用戶 i 調(diào)用服務(wù)j 的QoS 值，沒有調(diào)用記錄的記為0.可以將張量HQoS轉(zhuǎn)換成矩陣U，其中U 的每一行ui由HQoS 中用戶i 在不同邊緣服務(wù)器上對(duì)每一個(gè)服務(wù)調(diào)用的QoS 記錄構(gòu)成，故ui是一個(gè)包含n×l 個(gè)元素的行向量.所以，算法1 的輸入U(xiǎn) 是一個(gè)m行n×l列的矩陣.

對(duì)于邊緣服務(wù)器空間的聚類，我們首先通過 qes=求該邊緣服務(wù)器每個(gè)服務(wù)的平均QoS 值，其中qus是用戶u 通過邊緣服務(wù)器e 訪問過服務(wù)s 的QoS 值.由各服務(wù)的平均QoS 值構(gòu)成該邊緣服務(wù)器的樣本數(shù)據(jù)，故邊緣服務(wù)器聚類的輸入數(shù)據(jù)為l 行n 列的QoS 矩陣.聚類方法與用戶空間聚類的方法類似，不再贅述.

3.4 相似性計(jì)算

對(duì)于情況1 所描述的情景，邊緣服務(wù)器e2上有服務(wù)s 的歷史QoS 記錄.此時(shí)，用戶u 在邊緣服務(wù)器e1上使用服務(wù)s的歷史QoS 數(shù)據(jù)已經(jīng)失效，我們需要在邊緣服務(wù)器e2的歷史記錄中為用戶u 找相似用戶，根據(jù)相似用戶使用服務(wù)s 的QoS 預(yù)測(cè)用戶u 使用服務(wù)s 的QoS 值.

在邊緣服務(wù)器e2的歷史記錄中查找使用過服務(wù)s 的用戶，在這些用戶中過濾出當(dāng)前用戶u 的同一類簇的相似用戶，用如式(2)所示的改進(jìn)的PCC(Pearson correlation coefficient，皮爾遜相關(guān)系數(shù))來計(jì)算用戶a 與用戶u 之間的相似度.

對(duì)于情況2 所描述的情景，邊緣服務(wù)器e2上沒有服務(wù)s的調(diào)用記錄.此時(shí)，我們需要在邊緣服務(wù)器e2附近搜索與邊緣服務(wù)器e1相似且存有服務(wù)s 的歷史QoS 數(shù)據(jù)的邊緣服務(wù)器，根據(jù)相似邊緣服務(wù)器上相似用戶使用服務(wù)s 的QoS 記錄預(yù)測(cè)用戶u 使用服務(wù)s 的QoS 值.

搜索邊緣服務(wù)器e2周邊的其他邊緣服務(wù)器，這里可以根據(jù)實(shí)際情況設(shè)置一個(gè)半徑閾值r 確定搜索范圍.在這些邊緣服務(wù)器中過濾出與邊緣服務(wù)器e1同一類簇且存有服務(wù)s 的QoS 記錄的邊緣服務(wù)器.用如式(3)所示改進(jìn)的PCC 來計(jì)算邊緣服務(wù)器b 與邊緣服務(wù)器e 之間的相似度.

3.5 QoS 預(yù)測(cè)

對(duì)于情況1 所描述的情景，能為預(yù)測(cè)用戶u 調(diào)用服務(wù)s提供數(shù)據(jù)的用戶a，需要既是用戶u 的同類簇用戶C(u)中的用戶，又是通過邊緣服務(wù)器e2訪問過服務(wù)s 的用戶U(e2，s)中的用戶.因此，用戶u 通過邊緣服務(wù)器e2訪問服務(wù)s 的QoS值可以通過式(4)進(jìn)行預(yù)測(cè).

對(duì)于情況2 所描述的情景，能提供數(shù)據(jù)的邊緣服務(wù)器b，需要滿足既是邊緣服務(wù)器e1的同類簇邊緣服務(wù)器，又是在邊緣服務(wù)器e2附近且存有服務(wù)s 的訪問記錄的邊緣服務(wù)器.因此，此時(shí)根據(jù)相似邊緣服務(wù)器對(duì)用戶u 使用服務(wù)s 的QoS 值可以通過式(5)進(jìn)行預(yù)測(cè).

因此，對(duì)于情況1，用戶當(dāng)前所在邊緣服務(wù)器e2上存在服務(wù)s 的調(diào)用記錄，則從用戶u 所在的類簇中挑選所有通過邊緣服務(wù)器調(diào)用過服務(wù)s 的用戶，基于他們使用服務(wù)s 的QoS 值 ，預(yù)測(cè)用戶u 使用服務(wù)s 的QoS 值.對(duì)于情況2，用戶當(dāng)前所在邊緣服務(wù)器e2上存在服務(wù)s 的調(diào)用記錄，則從邊緣服務(wù)器e1所在的類簇中挑選所有與邊緣服務(wù)器e2的距離小于r，且有服務(wù)s 的調(diào)用QoS 數(shù)據(jù)的邊緣服務(wù)器，基于這些邊緣服務(wù)器上服務(wù) s 的的 QoS 值，預(yù)測(cè)用戶使用服務(wù) s 的 QoS 值.

據(jù)算法2，在用戶位置發(fā)生移動(dòng)，邊緣服務(wù)器發(fā)生切換后，可對(duì)用戶在新位置能夠得到的QoS 進(jìn)行預(yù)測(cè).

3.6 一個(gè)例子

本節(jié)用一個(gè)簡(jiǎn)單的例子，進(jìn)一步闡釋本文的方法.

假如有 5 個(gè)用戶{u1，u2，u3，u4，u5}，3 個(gè)服務(wù){(diào)s1，s2，s3}，以及4 個(gè)邊緣服務(wù)器{e1，e2，e3，e4}，每個(gè)邊緣服務(wù)器上的QoS 歷史數(shù)據(jù)分別為:

用戶u4之前使用過服務(wù)s1和s2，現(xiàn)在用戶到了邊緣服務(wù)器e4附近，需要調(diào)用服務(wù)s2，可以看到用戶u4沒有通過e4調(diào)用過服務(wù)s2，但是服務(wù)s2有通過邊緣服務(wù)器e4使用的記錄，符合情況1 的場(chǎng)景.

經(jīng)用戶空間聚類得用戶u4的相似用戶為u3和u5.根據(jù)式(2)求得用戶u4與相似用戶u3、u5的相似度分別為:sim'(u3，u4)=0.5227，sim'(u5，u4)=0.7379，帶入式(4)可以計(jì)算出用戶 u4通過訪問 e4調(diào)用服務(wù) s2的預(yù)測(cè) QoS 值為:.

現(xiàn)在用戶u4又到了邊緣服務(wù)器e2附近，想調(diào)用服務(wù)s1，可以看出在邊緣服務(wù)器e2上沒有服務(wù)s1的使用記錄，符合情況2 的場(chǎng)景.

經(jīng)邊緣服務(wù)器空間聚類，邊緣服務(wù)器e2與邊緣服務(wù)器e1與e3均相似，假設(shè)邊緣服務(wù)器e1與e2相距較遠(yuǎn)，因此只能根據(jù)距離較近的邊緣服務(wù)器e3上服務(wù)s1的歷史QoS 記錄進(jìn)行預(yù)測(cè)，依次將數(shù)據(jù)代入式(3)與式(5)，求得用戶u4在邊緣服務(wù)器 e2附近調(diào)用服務(wù) s1的預(yù)測(cè) QoS 值為.

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

為了驗(yàn)證EQoSP 的有效性，實(shí)驗(yàn)部分首先通過聚類分析確定相似用戶和相似邊緣服務(wù)器，然后與幾種典型的QoS 預(yù)測(cè)方法比較預(yù)測(cè)的準(zhǔn)確度.

仿真實(shí)驗(yàn)在MATLAB R2018a 環(huán)境運(yùn)行，操作系統(tǒng)Windows 10 64 位，處理器是 Intel Core i7，3.6GHz，內(nèi)存 16GB.

4.1 數(shù)據(jù)集描述

因?yàn)轫憫?yīng)時(shí)間是QoS 屬性中受移動(dòng)環(huán)境最大的屬性，所以本文采用香港中文大學(xué)博士鄭子彬等人的研究成果WSDREAM 數(shù)據(jù)集中的Dataset 3［8］中響應(yīng)時(shí)間數(shù)據(jù) rtRate 作為QoS 數(shù)據(jù).該數(shù)據(jù)集包括142 個(gè)用戶在64 個(gè)不同的時(shí)間對(duì)1500 個(gè)Web 服務(wù)訪問的響應(yīng)時(shí)間記錄，每一個(gè)的訪問時(shí)間，都形成一個(gè)142×1500 的響應(yīng)時(shí)間矩陣.本文將該數(shù)據(jù)集稀疏化為不同的數(shù)據(jù)密度5%、10%、15%和20%，以模擬真實(shí)環(huán)境中的QoS 數(shù)據(jù)，同時(shí)，本文將每個(gè)不同的時(shí)刻的數(shù)據(jù)當(dāng)作不同邊緣服務(wù)器的數(shù)據(jù)，并且將訪問時(shí)間的鄰近關(guān)系當(dāng)成邊緣服務(wù)器的鄰近關(guān)系.

4.2 度量標(biāo)準(zhǔn)

平均絕對(duì)誤差MAE(Mean absolute error)和均方根誤差RMSE(root mean squared error)是最常用來度量預(yù)測(cè)值與真實(shí)值之間的差異的兩個(gè)指標(biāo).本文采用MAE 和RMSE 來評(píng)估所提出的QoS 預(yù)測(cè)方法的準(zhǔn)確性.MAE 和RMSE 的定義分別如式(6)和式(7)所示:

其中，qu，s是用戶 u 使用服務(wù) s 的真實(shí) QoS 值，表示用戶u 使用服務(wù)s 的QoS 的預(yù)測(cè)值，N 是所預(yù)測(cè)的QoS 值的個(gè)數(shù).MAE 和RMSE 的值越小表示預(yù)測(cè)值越準(zhǔn)確.

4.3 聚類個(gè)數(shù)的確定

為了根據(jù)數(shù)據(jù)本身的特性自然地確定相似用戶和相似邊緣服務(wù)器的個(gè)數(shù)，本文首先對(duì)用戶空間和邊緣服務(wù)器空間進(jìn)行聚類.為確定合適的類簇個(gè)數(shù)，本文采用如式(1)所示的DBI 作為聚類的度量指標(biāo)，DBI 越小說明類內(nèi)聚類越小而類間距離越大，說明聚類效果越好.

由于實(shí)際情況中QoS 數(shù)據(jù)非常稀疏［10］，類簇個(gè)數(shù)太多可能導(dǎo)致某些用戶很難找到相似用戶或者相似邊緣服務(wù)器，所以本文讓類簇個(gè)數(shù)k 從2 變到20.圖1 是用戶空間的聚類結(jié)果.從圖1 可以看出 k=15 時(shí)，DBI 最小，其值為 0.0716，聚類效果最好，因此本文后續(xù)實(shí)驗(yàn)中，相似用戶的確定以k=15時(shí)的聚類結(jié)果為依據(jù).

圖1 不同用戶類簇個(gè)數(shù)時(shí)的DBI 值Fig.1 DBI of different numbers of user clusters

圖2 不同邊緣服務(wù)器類簇個(gè)數(shù)的DBI 值Fig.2 DBI of different numbers of edge sever clusters

圖2 是邊緣服務(wù)器空間的聚類結(jié)果.由于邊緣服務(wù)器個(gè)數(shù)較少，所以本文讓類簇個(gè)數(shù)k 從2 變到20.從圖2 可以看出k=7 時(shí)，DBI 最小，其值為 0.0026，聚類效果最好，因此本文后續(xù)實(shí)驗(yàn)中，邊緣服務(wù)器的聚類個(gè)數(shù)k 值取7.

4.4 預(yù)測(cè)準(zhǔn)確性比較

本文以MAE 與RSME 作為預(yù)測(cè)QoS 值準(zhǔn)確性的度量.與本文方法進(jìn)行比較的方法如下:

UPCC［4］是基于相似用戶的協(xié)同過慮預(yù)測(cè)方法，用戶之間的相似度以PCC 來度量.利用當(dāng)前用戶的相似用戶使用目標(biāo)服務(wù)的QoS 值來對(duì)當(dāng)前用戶使用目標(biāo)服務(wù)的QoS 進(jìn)行預(yù)測(cè).

UIPCC［5］以PCC 來度量用戶之間和服務(wù)之間的相似度，并利用當(dāng)前用戶對(duì)與目標(biāo)服務(wù)相似的服務(wù)的調(diào)用QoS 值和與當(dāng)前用戶相似的用戶對(duì)目標(biāo)服務(wù)調(diào)用的QoS 值對(duì)當(dāng)前用戶使用目標(biāo)服務(wù)的QoS 進(jìn)行預(yù)測(cè).

UEPCC［22］是針對(duì)邊緣計(jì)算環(huán)境下的 QoS 預(yù)測(cè)方法，該方法同時(shí)考慮用戶之間和邊緣服務(wù)器之間的相似性.取Topk 相似用戶和相似邊緣服務(wù)器提供的數(shù)據(jù)預(yù)測(cè)移動(dòng)用戶位置發(fā)生移動(dòng)后使用目標(biāo)服務(wù)可能獲得的QoS 值.

實(shí)驗(yàn)中，本文從數(shù)據(jù)集中隨機(jī)地選擇兩個(gè)邊緣服務(wù)器作為邊緣服務(wù)器e1和e2，對(duì)e1上已知而e2上未知的用戶-服務(wù)QoS 數(shù)據(jù)進(jìn)行預(yù)測(cè).表1 是本文方法EQoSP 與上述方法的MAE 與 MRSE 值的比較.

表1 預(yù)測(cè)QoS 值準(zhǔn)確度比較Table 1 Accuracy comparison of predicted QoS values

從表1 可以看出，隨著矩陣密度從5%增加到20%，所有的方法的MAE 值與MRSE 值都在逐漸減小，說明已知數(shù)據(jù)越多，預(yù)測(cè)值越來越準(zhǔn)確.固定矩陣密度為5%，10%，15%和20%可以看出，相比較而言，本文的方法的MAE 和MRSE 值都是最小的.這是因?yàn)楸疚姆椒瓤紤]了用戶的移動(dòng)性，又能依據(jù)數(shù)據(jù)本身的特性以一種較為自然的方式個(gè)性化地確定相似用戶和相似邊緣服務(wù)器.

4.5 仿真實(shí)驗(yàn)

為了驗(yàn)證所提出方法在真實(shí)環(huán)境下的有效性，進(jìn)行了如下仿真實(shí)驗(yàn).17 個(gè)用戶在山西大學(xué)校園分布的8 個(gè)基站(模擬邊緣服務(wù)器)附近分別訪問計(jì)算中心的服務(wù)器，記錄響應(yīng)時(shí)間.所采集的有效數(shù)據(jù)構(gòu)成的響應(yīng)時(shí)間矩陣密度為d=35.29%.

圖3 用戶/邊緣服務(wù)器聚類情況Fig.3 DBI of differentnumber of clusters

圖4 不同方法的預(yù)測(cè)準(zhǔn)確度比較Fig.4 Accuracy comparison of different methods

圖3 是仿真數(shù)據(jù)集上分別對(duì)邊緣服務(wù)器和用戶的聚類情況.用戶和邊緣服務(wù)器聚類個(gè)數(shù)分別采用k=2，3，4，5.

從圖3 可以看出，當(dāng)k=2 時(shí)，邊緣服務(wù)器的聚類效果最優(yōu)，k=3 時(shí)用戶的聚類效果最優(yōu).因此，后續(xù)實(shí)驗(yàn)中服務(wù)器分成2 類，用戶分成3 類.

圖4 所示是上述幾種方法在仿真數(shù)據(jù)集上預(yù)測(cè)QoS 的MAE 和 RSME.

從圖4 可以看出，UEPCC 和EQoSP 的預(yù)測(cè)值誤差都有較小，這兩種方法都是針對(duì)邊緣計(jì)算環(huán)境的QoS 的預(yù)測(cè).而本文提出的EQoSP 的MAE 和RSME 比UEPCC 方法的MAE和RSME 又小一些，這是因?yàn)镋QoSP 沒有采用固定個(gè)數(shù)的對(duì)相似用戶和相似邊緣服務(wù)器，而是通過對(duì)歷史數(shù)據(jù)的聚類分析，根據(jù)數(shù)據(jù)本身的特性自然地確定相似用戶和相似邊緣服務(wù)器，從而使得QoS 預(yù)測(cè)值更加準(zhǔn)確.

5 結(jié) 論

本文提出了一種邊緣計(jì)算環(huán)境中的移動(dòng)服務(wù)QoS 預(yù)測(cè)方法.考慮到移動(dòng)用戶的位置改變會(huì)導(dǎo)致所訪問的邊緣服務(wù)器切換.當(dāng)用戶位置發(fā)生移動(dòng)時(shí)，本文根據(jù)切換后的邊緣服務(wù)器上是否有目標(biāo)服務(wù)的訪問記錄，分兩種不同的情況對(duì)用戶使用服務(wù)的QoS 進(jìn)行預(yù)測(cè).此外，不同于以往的固定的Top-k個(gè)相似用戶和相似服務(wù)器的方法，本文通過用戶空間和邊緣服務(wù)器空間的聚類，提出一種按照數(shù)據(jù)本身特性自然地確定相似用戶和相似邊緣服務(wù)器的方法.在真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，本文的方法有更高的QoS 預(yù)測(cè)精度.

盡管本文的方法在仿真環(huán)境下提高了邊緣服務(wù)器環(huán)境下服務(wù)QoS 值預(yù)測(cè)的準(zhǔn)確度，然而實(shí)際的邊緣計(jì)算環(huán)境更為復(fù)雜，比如服務(wù)QoS 不可能是固定值，可能會(huì)隨著時(shí)間發(fā)生演化.在未來的研究中，我們將把時(shí)間因素考慮在模型之中，提高模型在真實(shí)環(huán)境中的適應(yīng)性.