李 靖，任麗芳，王文劍,3

(1.山西大學(xué) 計算機(jī)與信息技術(shù)學(xué)院 山西 太原 030006；2.山西財經(jīng)大學(xué) 信息學(xué)院 山西 太原 030006；3.山西大學(xué) 計算智能與中文信息處理教育部重點(diǎn)實(shí)驗室 山西 太原 030006)

0 引言

隨著云計算和移動互聯(lián)網(wǎng)的結(jié)合，用戶可以在移動環(huán)境中隨時隨地使用智能手機(jī)等終端設(shè)備訪問網(wǎng)絡(luò)中的云端服務(wù)[1]。由于越來越多的服務(wù)提供商進(jìn)入網(wǎng)絡(luò)服務(wù)市場，導(dǎo)致同一功能的任務(wù)可以由越來越多的服務(wù)實(shí)現(xiàn)，然而這些服務(wù)通常具有不同的服務(wù)質(zhì)量(quality of service, QoS)，如響應(yīng)時間、價格、吞吐量、可靠性等。網(wǎng)絡(luò)服務(wù)的功能簡單、門類繁多、屬性各異，用戶需要從數(shù)量巨大、QoS迥異的服務(wù)中選擇適用的組件服務(wù)，并進(jìn)一步實(shí)現(xiàn)服務(wù)組合以完成較為復(fù)雜的業(yè)務(wù)[2]。因此，如何快速找到QoS最優(yōu)的組合服務(wù)成為亟須解決的問題。傳統(tǒng)的服務(wù)選擇方法是對每個任務(wù)選擇QoS最優(yōu)的服務(wù)，但在移動環(huán)境中，用戶要調(diào)用服務(wù)時既需要考慮初始信息(例如用戶所處位置、調(diào)用時刻以及設(shè)備類型)，又需要考慮用戶的移動性，這導(dǎo)致服務(wù)選擇變得更加困難。移動環(huán)境中用戶的位置不固定，且響應(yīng)時間屬性受用戶移動的影響較大，使得響應(yīng)時間感知的移動服務(wù)組合方法研究成為移動服務(wù)計算領(lǐng)域的一個重要方向。近年來，已經(jīng)有很多研究致力于解決QoS感知的服務(wù)組合問題[3]，大致可分為全局最優(yōu)方法和局部最優(yōu)方法兩類。全局最優(yōu)方法是從所有的服務(wù)組合中找到最優(yōu)的組合服務(wù)，其典型方法是將滿足用戶QoS約束的服務(wù)組合問題建模為一個整數(shù)規(guī)劃問題[4]，但這類方法求解難度很大，因此最常用的是局部最優(yōu)方法，即選擇最優(yōu)的組件服務(wù)進(jìn)行組合。文獻(xiàn)[5]提出一種模糊線性規(guī)劃方法來識別候選服務(wù)的差異，可以幫助服務(wù)使用者通過考慮他們的要求和偏好來選擇最合適的服務(wù)。這類方法在傳統(tǒng)的Internet環(huán)境中取得了較好的效果，然而在移動環(huán)境中由于用戶在調(diào)用服務(wù)的過程中位置不固定，而且不同位置的網(wǎng)絡(luò)信號質(zhì)量可能不同，這導(dǎo)致由最優(yōu)組件服務(wù)組成的組合服務(wù)的全局QoS不一定是最優(yōu)的。因此，移動環(huán)境中的服務(wù)選擇與組合需要考慮用戶的移動性。

目前，已有一些研究工作對移動環(huán)境中服務(wù)組合問題進(jìn)行探討。文獻(xiàn)[6]為減少服務(wù)請求的組件任務(wù)分配給邊緣服務(wù)器和云服務(wù)器的時間延遲，提出一種用于移動邊緣系統(tǒng)中服務(wù)選擇的組合遺傳算法和模擬退火算法。文獻(xiàn)[7]介紹了一種針對無線移動自組織網(wǎng)絡(luò)中可靠的服務(wù)組合問題的移動性預(yù)測方法，其目標(biāo)是可以忽略服務(wù)提供商的移動性來組合服務(wù)。文獻(xiàn)[8]針對移動應(yīng)用領(lǐng)域的特點(diǎn)，提出一種探索式服務(wù)組合方法，通過感知上下文變化為用戶構(gòu)造當(dāng)前環(huán)境下可用的服務(wù)集合，并通過交互將用戶選擇的服務(wù)及時組合到應(yīng)用中。上述工作豐富了移動服務(wù)組合的研究，但都存在不同程度的局限性。一方面，在實(shí)際移動環(huán)境中網(wǎng)絡(luò)信號質(zhì)量是動態(tài)變化的，一般很難用顯式函數(shù)來表示，而現(xiàn)有研究中網(wǎng)絡(luò)信號質(zhì)量通常由分段函數(shù)或余弦函數(shù)來表示，雖然這兩個函數(shù)都能體現(xiàn)出網(wǎng)絡(luò)質(zhì)量是變化的，但不能準(zhǔn)確體現(xiàn)其分布。另一方面，這些方法都是通過一些啟發(fā)式算法來搜索最優(yōu)的組合服務(wù)，當(dāng)組合服務(wù)越接近最優(yōu)時，需要的迭代次數(shù)就越多，效率就會越低。本文在一個真實(shí)的移動仿真環(huán)境下獲取了各個位置的網(wǎng)絡(luò)信號強(qiáng)度，提出一種響應(yīng)時間感知的移動服務(wù)組合方法，根據(jù)用戶實(shí)時移動位置準(zhǔn)確地選擇最優(yōu)組件服務(wù)，完成服務(wù)組合。該方法每次迭代計算的是組合服務(wù)響應(yīng)時間的預(yù)測值和真實(shí)值的均方誤差，可大大縮短模型訓(xùn)練時間。

1 移動模型

1.1 模型定義

在移動環(huán)境中，用戶在調(diào)用服務(wù)時位置可能會變化。用戶在移動時，移動網(wǎng)絡(luò)中的數(shù)據(jù)傳輸率會根據(jù)用戶的位置而動態(tài)變化。

定義1用戶的移動路徑。用戶的移動路徑用一個四元組ump=(Location,Direction,Time,Speed)表示，其中Location表示用戶調(diào)用服務(wù)時的起始位置；Direction表示用戶的移動方向；Time表示用戶的移動時間；Speed表示用戶的移動速率。一般假設(shè)用戶是勻速運(yùn)動，所以用戶下一時刻的位置可通過計算得到。

定義2組件服務(wù)。一個服務(wù)將被建模為一個四元組s=(Sid,Input,Output,Q)，其中Sid表示服務(wù)的編號；Input表示服務(wù)的輸入；Output表示服務(wù)的輸出；Q表示服務(wù)的QoS。

定義3組合服務(wù)。為滿足用戶的功能需求，將不同功能的組件服務(wù)按照一定的邏輯進(jìn)行集成，形成可擴(kuò)展的增值服務(wù)。這樣，組合服務(wù)就可以形式化地表示為一個序列sc=(s1,s2,…,sn),其中si(i=1,2,…,n)為依次組成組合服務(wù)的組件Sid，n為組合服務(wù)中組件服務(wù)的個數(shù)。

定義4響應(yīng)時間。組件服務(wù)的響應(yīng)時間定義為參數(shù)輸入時間、服務(wù)執(zhí)行時間以及結(jié)果輸出時間之和；組合服務(wù)的響應(yīng)時間定義為所有組件服務(wù)的響應(yīng)時間之和。

1.2 響應(yīng)時間計算

1.2.1移動網(wǎng)絡(luò)質(zhì)量 移動網(wǎng)絡(luò)質(zhì)量通常指一個特定位置的移動信號強(qiáng)度，本文將數(shù)據(jù)傳輸率作為移動網(wǎng)絡(luò)質(zhì)量的度量指標(biāo)。雖然數(shù)據(jù)傳輸率在數(shù)據(jù)傳輸過程中不可能一直保持恒定，但在短距離內(nèi)變化并不明顯，因為每個任務(wù)在數(shù)據(jù)傳輸上花費(fèi)的時間非常短，通常只有幾秒鐘，而步行用戶在數(shù)據(jù)傳輸?shù)臅r間內(nèi)移動的路程也僅僅只有幾米。目前常用的宏基站的覆蓋范圍有幾百米，用戶在數(shù)據(jù)傳輸?shù)臅r間內(nèi)不換基站的概率非常大。因此，假設(shè)每個任務(wù)在進(jìn)行數(shù)據(jù)傳輸時移動網(wǎng)絡(luò)質(zhì)量保持恒定。

1.2.2組件服務(wù)響應(yīng)時間 移動環(huán)境中QoS描述了移動環(huán)境中組件服務(wù)的性能。不同路徑的網(wǎng)絡(luò)質(zhì)量有所差異，導(dǎo)致用戶在不同位置調(diào)用組件服務(wù)時影響了服務(wù)的輸入、輸出數(shù)據(jù)量的傳輸時間。組件服務(wù)s的響應(yīng)時間可以表示為

RT_CSs=tvodi+Es+tvodo，

(1)

其中：tvodi代表組件服務(wù)s傳輸輸入數(shù)據(jù)所需的時間；Es代表組件服務(wù)s的執(zhí)行時間；tvodo代表組件服務(wù)s傳輸輸出數(shù)據(jù)所需的時間。tvodi可以表示為

(2)

其中：vodi表示輸入的數(shù)據(jù)量(數(shù)據(jù)集中給定服務(wù)的數(shù)據(jù)量)；QoMNi表示用戶在剛開始輸入數(shù)據(jù)時所在位置的移動網(wǎng)絡(luò)質(zhì)量。根據(jù)同樣的方法可以計算出tvodo。

1.2.3組合服務(wù)響應(yīng)時間 具有循環(huán)、分支和并行結(jié)構(gòu)的服務(wù)組合都能轉(zhuǎn)化為一種順序結(jié)構(gòu)[9]，本文主要解決業(yè)務(wù)邏輯的過程模型為順序結(jié)構(gòu)的服務(wù)組合問題。QoS表示整個組合服務(wù)的性能，組合服務(wù)的響應(yīng)時間可以表示為

(3)

其中：sc表示組合服務(wù)中所有組件服務(wù)的執(zhí)行序列。

2 移動服務(wù)組合方法

本文提出的NNSC算法，其目標(biāo)是在移動環(huán)境中從所有的服務(wù)組合中找到響應(yīng)時間最短的組合服務(wù)。NNSC算法由兩部分組成：一是通過隨機(jī)森林分類算法過濾掉響應(yīng)時間較長的組合服務(wù)；二是通過前饋神經(jīng)網(wǎng)絡(luò)建立移動組合服務(wù)與其響應(yīng)時間的回歸模型。圖1描述了服務(wù)組合的一般過程。首先將任務(wù)按照條件、循環(huán)等控制語句組合成復(fù)雜的任務(wù)，然后再為每個任務(wù)找到合適的候選服務(wù)，此過程即為服務(wù)發(fā)現(xiàn)，服務(wù)發(fā)現(xiàn)通常由虛擬服務(wù)提供商來完成。最后進(jìn)行服務(wù)選擇，即對每個任務(wù)從候選服務(wù)中選擇一個合適的服務(wù)，將這些服務(wù)進(jìn)行組合，組合時的控制語句與任務(wù)組合時的控制語句相同。

圖1 服務(wù)組合的一般過程

2.1 組合服務(wù)分類

當(dāng)子任務(wù)的候選服務(wù)數(shù)量一定時，組合服務(wù)的數(shù)量與子任務(wù)數(shù)呈指數(shù)級關(guān)系，使得選擇最優(yōu)組合服務(wù)成為一個NP-hard問題。此外，這些組合服務(wù)的響應(yīng)時間差異較大，響應(yīng)時間較短的組合服務(wù)只占小部分。為了縮小解空間，提出了組合服務(wù)分類算法，用來過濾掉響應(yīng)時間較長的組合服務(wù)。首先，初始化需要用到的集合，并根據(jù)比例選取訓(xùn)練集。其次，計算訓(xùn)練集中組合服務(wù)的響應(yīng)時間，然后設(shè)定閾值，并根據(jù)閾值為組合服務(wù)設(shè)置標(biāo)簽。在此基礎(chǔ)上，對訓(xùn)練集進(jìn)行訓(xùn)練得到分類模型。最后，使用訓(xùn)練好的分類器預(yù)測服務(wù)集，返回響應(yīng)時間較短的組合服務(wù)集。組合服務(wù)分類算法的主要步驟如下。

輸入: 移動路徑及起始位置、服務(wù)集、訓(xùn)練集占服務(wù)集的比例k。

輸出：較優(yōu)的組合服務(wù)集。

Step 1 按服務(wù)組合過程進(jìn)行服務(wù)組合，并創(chuàng)建響應(yīng)時間、組合服務(wù)標(biāo)簽、較優(yōu)服務(wù)集三個空集合；

Step 2 根據(jù)比例k從服務(wù)集中選擇訓(xùn)練集；

Step 3 FOR 組合服務(wù) IN訓(xùn)練集：

通過式(3)計算出用戶在該路徑中起始位置調(diào)用組合服務(wù)的響應(yīng)時間，并將結(jié)果存入響應(yīng)時間集合中；

END FOR

Step 4 設(shè)置閾值為響應(yīng)時間中最大值與最小值的平均值；

∥ 組合服務(wù)對應(yīng)的標(biāo)簽為1時，表示其響應(yīng)時間較短；標(biāo)簽為0時，表示其響應(yīng)時間較長。

Step 5 FORtIN 響應(yīng)時間:

IFt<閾值

將1添加到組合服務(wù)標(biāo)簽中；

ELSE

將0添加到組合服務(wù)標(biāo)簽中；

END IF

END FOR

Step 6 使用隨機(jī)森林分類器訓(xùn)練得到模型；

∥result用于存放分類結(jié)果0或1，1表示該組合服務(wù)的響應(yīng)時間較短；0表示該組合服務(wù)的響應(yīng)時間較長。

Step 7 使用該模型預(yù)測服務(wù)集，并將分類結(jié)果存入result中；

Step 8 FOR EACHres∈resultDO:

IFres==1

將該組合服務(wù)添加到較優(yōu)服務(wù)集；

END IF

END FOR

Step 9 RETURN 較優(yōu)服務(wù)集。

2.2 響應(yīng)時間預(yù)測

在識別出響應(yīng)時間較短的組合服務(wù)之后，為了找到響應(yīng)時間最短的組合服務(wù)，提出了組合服務(wù)響應(yīng)時間預(yù)測算法。組合服務(wù)與響應(yīng)時間之間是非線性關(guān)系，而神經(jīng)網(wǎng)絡(luò)處理非線性模型有較大的優(yōu)勢。因此，通過tensorflow搭建了如圖2所示的前饋神經(jīng)網(wǎng)絡(luò)模型。圖2的神經(jīng)網(wǎng)絡(luò)模型包含輸入層、2個隱藏層、輸出層。輸入層包含12個神經(jīng)元，第一隱藏層包含10個神經(jīng)元，第二隱藏層包含4個神經(jīng)元，輸出層包含1個神經(jīng)元。在此模型中將預(yù)測值與真實(shí)值的均方誤差作為損失函數(shù)，并通過Adam算法來優(yōu)化損失函數(shù)。為緩解梯度消失的情形，激活函數(shù)采用ReLU函數(shù)。當(dāng)?shù)螖?shù)小于最大迭代次數(shù)時，使用該神經(jīng)網(wǎng)絡(luò)訓(xùn)練數(shù)據(jù)集，直到模型收斂或者達(dá)到最大迭代次數(shù)，然后通過訓(xùn)練好的神經(jīng)網(wǎng)絡(luò)進(jìn)行預(yù)測。

圖2 前饋神經(jīng)網(wǎng)絡(luò)模型

3 實(shí)驗設(shè)計

實(shí)驗環(huán)境配置為Intel(R)Core(TM)i7-7700 3.60 GHz 處理器，內(nèi)存為16.0 GB，Windows 10操作系統(tǒng)，Python 3.7版本。

3.1 實(shí)驗部分

3.1.1移動仿真環(huán)境 為了使移動環(huán)境中各個位置的網(wǎng)絡(luò)質(zhì)量相對真實(shí)，選取了一個真實(shí)的移動環(huán)境，如圖3所示。由于條件限制，選取了長約1 000 m、寬約500 m的區(qū)域，真實(shí)環(huán)境中基站分布如圖4所示。

圖3 一個真實(shí)的移動環(huán)境

圖4 真實(shí)環(huán)境中基站分布

圖3和圖4中的三角形表示環(huán)境中基站的位置，數(shù)字1、2、3、4分別表示四條路徑，區(qū)域中共有1-2、2-1、1-3-4、4-3-1、2-3-4、4-3-2 六條路徑。圖5給出了這六條路徑中各位置的網(wǎng)絡(luò)質(zhì)量(用網(wǎng)絡(luò)傳輸速度表示)。根據(jù)基站的位置，通過模型cost231-hata計算出基站到用戶當(dāng)前位置的路徑損耗?；镜目偣β蕼p去路徑損耗、車輛穿透損耗、建筑穿透損耗等，即為各位置的網(wǎng)絡(luò)質(zhì)量?？梢钥闯觯W(wǎng)絡(luò)信號質(zhì)量的變化不是由分段函數(shù)或余弦函數(shù)等簡單函數(shù)表示的。

圖5 路徑中各位置的網(wǎng)絡(luò)傳輸速度

3.1.2實(shí)驗數(shù)據(jù)集 實(shí)驗數(shù)據(jù)集為文獻(xiàn)[10]使用的某些服務(wù)器的日志文件，該數(shù)據(jù)集是由阿里巴巴與浙江大學(xué)搜集的，可從www.bruceluo.net網(wǎng)站中下載，其中一個組合服務(wù)樣例如表1所示。表1中每一行表示一個服務(wù)，用輸入量、輸出量、執(zhí)行時間這三項來描述。如第一行表示該組件服務(wù)接受1 697 kB的輸入，2.84 s執(zhí)行完該服務(wù)，并有1 686 kB的輸出，然后發(fā)送到下一個組件服務(wù)。對于每一個任務(wù)都有很多候選服務(wù)，每個服務(wù)執(zhí)行時間不同，服務(wù)的執(zhí)行時間從均勻分布中隨機(jī)生成。為避免其他因素影響評估結(jié)果，假設(shè)每個任務(wù)的候選服務(wù)的輸入和輸出數(shù)據(jù)量相同。

表1 組合服務(wù)樣例

3.2 實(shí)驗結(jié)果及分析

3.2.1參數(shù)的選擇k為訓(xùn)練集占服務(wù)集的比例，k值越大，算法的執(zhí)行時間就越長。選擇k的起始值是8%，逐漸增加至12%，觀察其尋找到的最優(yōu)組合服務(wù)的執(zhí)行時間。在不同的位置處，對于每個k值，實(shí)驗執(zhí)行20次，結(jié)果取多次執(zhí)行時間的平均值，實(shí)驗結(jié)果如圖6 所示。圖6中每個柱形圖都由兩部分組成，上面較窄的部分表示執(zhí)行算法找到最優(yōu)組合服務(wù)所用的時間，剩余部分表示最優(yōu)組合服務(wù)的執(zhí)行時間?？梢钥闯?，當(dāng)k值為10%時，算法找到的最優(yōu)組合服務(wù)的執(zhí)行時間相對較短。因此，后續(xù)實(shí)驗中選擇k值為10%。

圖6 不同k值時算法的執(zhí)行時間

3.2.2算法的性能 為了驗證NNSC算法的有效性，從神經(jīng)網(wǎng)絡(luò)的收斂速度方面來考慮方法的效率。圖7為不同候選服務(wù)數(shù)時的收斂速度,圖8為不同任務(wù)數(shù)時的收斂速度。可以看出，當(dāng)任務(wù)數(shù)不變時，前饋神經(jīng)網(wǎng)絡(luò)模型很容易收斂。候選服務(wù)數(shù)相同，當(dāng)任務(wù)數(shù)不超過5時，收斂速度較快。

圖7 不同候選服務(wù)數(shù)時的收斂速度

圖8 不同任務(wù)數(shù)時的收斂速度

3.2.3與其他算法的比較 最優(yōu)移動組合服務(wù)的選擇是組合優(yōu)化問題，該問題被證明是NP-hard問題，不存在多項式時間算法。目前，最優(yōu)組合服務(wù)的選擇常用一些近似算法或啟發(fā)式算法來求解，例如模擬退火算法、粒子群算法等。為了驗證NNSC算法的優(yōu)越性，與以下四種算法進(jìn)行了比較：① 支持向量機(jī)(SVM)。完成組合服務(wù)分類算法后，使用SVM建立組合服務(wù)與其響應(yīng)時間的回歸模型，從而預(yù)測其響應(yīng)時間。② 基于教與學(xué)的優(yōu)化算法(TLBO)。TLBO是基于教學(xué)過程的自然現(xiàn)象而開發(fā)的一種啟發(fā)式算法，已用于解決服務(wù)組合問題，并且具有很高的效率[11]。③ 粒子群優(yōu)化算法(PSO)。PSO是一種根據(jù)給定的質(zhì)量度量并通過反復(fù)迭代來改進(jìn)候選解決方案的優(yōu)化算法，已經(jīng)廣泛應(yīng)用于服務(wù)組合研究中[12]。④ 局部最優(yōu)方法(LOM)。對于每一個任務(wù)，LOM從候選服務(wù)中選擇響應(yīng)時間最短的服務(wù)進(jìn)行組合。任務(wù)數(shù)為4，在每個任務(wù)10個候選服務(wù)的情況下進(jìn)行實(shí)驗，在相同的實(shí)驗環(huán)境中實(shí)現(xiàn)了上述算法，并對每種算法進(jìn)行了參數(shù)優(yōu)化。

因為移動環(huán)境中各個位置周圍網(wǎng)絡(luò)質(zhì)量的變化程度不同，所以用戶在不同位置調(diào)用服務(wù)的響應(yīng)時間不同。為了驗證NNSC算法的有效性，在六條路徑中的初始點(diǎn)和極值點(diǎn)附近開始調(diào)用服務(wù)，觀察NNSC算法與其他算法所選出的最優(yōu)組合服務(wù)的執(zhí)行時間。圖9顯示了用戶在路徑1-2、路徑2-1、路徑1-3-4、路徑4-3-1、路徑2-3-4、路徑4-3-2 各極值點(diǎn)附近，調(diào)用通過不同算法得到的最優(yōu)組合服務(wù)的響應(yīng)時間。可以看出，通過傳統(tǒng)的局部最優(yōu)方法得到的組合服務(wù)的響應(yīng)時間普遍較長。結(jié)合圖5中各位置的網(wǎng)絡(luò)傳輸速度，發(fā)現(xiàn)在傳輸速度較慢的位置，這種差異更加明顯。這說明移動環(huán)境中網(wǎng)絡(luò)質(zhì)量的變化對服務(wù)選擇產(chǎn)生了重要的影響。本文NNSC算法在不同路徑多個位置處找到的最優(yōu)組合服務(wù)的執(zhí)行時間都是最短的。這是因為通過分類算法過濾掉響應(yīng)時間較長的組合服務(wù)的數(shù)量較大，并且不會將響應(yīng)時間近似最短的組合服務(wù)過濾掉。與啟發(fā)式算法相比，NNSC算法縮小了解空間，能獲得較高的效率。

圖9 路徑中不同位置響應(yīng)時間的比較

4 小結(jié)

本文首先建立了可計算的移動模型，其次根據(jù)此模型過濾掉響應(yīng)時間較長的組合服務(wù)，最后采用前饋神經(jīng)網(wǎng)絡(luò)建立組合服務(wù)與響應(yīng)時間的回歸模型來選擇出響應(yīng)時間最短的組合服務(wù)。結(jié)果表明，在相對真實(shí)的移動網(wǎng)絡(luò)環(huán)境中，本文方法的實(shí)驗效果優(yōu)于其他一些啟發(fā)式算法。由于只考慮了移動環(huán)境中服務(wù)的響應(yīng)時間這一最重要的QoS屬性，未來工作將綜合考慮QoS的其他屬性，為用戶推薦更合適的服務(wù)。