物聯網環境下QoS驅動的服務組合能量優化研究

付 佳，李愛萍，段利國，王舒漫，趙菊敏

(太原理工大學 信息與計算機學院，太原 030000)

E-mail：tyutli@163.com

1 引 言

隨著新一代信息技術的發展，物聯網成為繼計算機、互聯網之后信息發展的又一次變革[1]，面對物聯網設備及環境都具有動態變化的特點[2]，在將物聯網設備根據其功能封裝為服務的同時[3，4]，如何實現物聯網服務的動態組合以達到最優配置是目前的主要挑戰之一.

2018物聯網白皮書指出，據IDC數據統計，到2022年，將有超過500億的終端與設備聯網，形成一個高密度的物聯網環境[5].這將導致服務組合中候選服務的數量規模宏大.可能存在許多功能相同或相似但非功能屬性QoS(Quality of Service)不同的原子服務，所以物聯網環境下QoS的優選仍是主要的研究方向之一.

當前，大量文獻研究主要基于QoS進行物聯網環境下的服務選擇[6]，然而，在實際應用中，物聯網服務的提供受到周圍環境的影響和相關的制約因素較多[7]，導致物聯網服務是高度資源受限服務，隨著服務類別及數量的增加，選擇服務時候選服務所消耗的能量也使得服務組合中的總體能耗隨之增長.因此，不同于傳統的web服務組合只進行最大化整體的QoS單元的策略，物聯網環境下的服務組合，旨在能量消耗和QoS之間尋找平衡以延長網絡生存周期.

2 相關工作

針對上述挑戰，國內外已經有許多研究人員對物聯網環境下的服務組合問題進行了深入研究.Zhou等人[8，9]提出了一種基于能源效率的無線傳感器網絡智能對象服務發現鏈和選擇方法，該方法采用多目標遺傳算法優化，根據傳感器設備的功能和適合度對傳感器設備進行分類，選擇最優的組合服務.在此基礎上，Sun等人[10]提出利用遺傳算法、蟻群算法、粒子群算法對服務類鏈進行實例化.以上方法對網絡的能耗進行了詳細的考量，但是沒有考慮到在實際應用中，由于規模宏大的原子服務數量，可能存在很多功能相同或者功能相似的服務，所以物聯網的服務組合方法必須同時考慮組合對象的QoS屬性值和能源效率.

楊臻等人[11]提出一種基于功能價值擇優的信息服務組合方法，結合物聯網中數據信息與地理位置密切相關、設備資源受限的特點，將剩余能量考慮為QoS的一個屬性值，建立物聯網QoS模型，進行加權計算.但是，該方法沒有單獨評估在動態配置過程中能量消耗對海量服務的影響.

Tong等人[12]將服務能量引入到無線傳感器網絡的工作流管理中，給出了服務能量的計算方法，并對傳統的QoS模型進行了擴展，采用QoS約束分解的方法，通過同時考慮QoS和服務能量，將工作流的全局質量約束分解為原子服務的一組局部質量約束，實現高效的本地服務選擇，提出了一種動態工作流適應機制.Alsaryrah等人[13]將物聯網服務組合的QoS水平與消耗能量之間的最優平衡問題簡化為雙目標最短路徑優化問題，并采用脈沖算法求解.上述研究只簡單考慮了QoS水平和能源效率問題，沒有針對物聯網服務組合動態配置中不同時期對QoS和能源的不同要求進行衡量.

綜上所述，針對物聯網環境下原子服務數量宏大、設備資源高度受限、服務組合過程動態變化的特點，本文提出一種改進的自適應方法，綜合考慮QoS屬性值和能源效率，解決服務組合過程中對能耗的不同要求，構建不同的目標函數；結合物聯網數據信息與地理位置密切相關的特點，利用位置信息進行局部優選，縮小候選服務范圍；最后利用多目標優化算法在可行服務組合空間中全局尋優.

3 能量優化建模

3.1 概念定義

定義1.(物聯網服務)：一個服務Service是一個三元組Service=(name，desc，QoS)，其中：

1.name是服務名稱；

2.desc是服務的語義描述；

3.QoS={ QoS1，QoS2…QoSn}是服務的服務質量屬性值集合.

定義2.(QoS)：服務質量QoS是反映服務性能的指標，是服務組合的主要依據，2003年，W3C提出了13種可能通用的QoS指標[14]，截止到目前為止，已經提出的QoS屬性指標有30余種[15].結合物聯網的特點，物聯網環境下的服務需要考慮每個設備的動態變化特性以及應用環境，所以本文取用代價、響應時間、可用性和可靠性四種屬性構建QoS模型：QoSij(S)=(Cost，Response Time，Availability，Reli-ability).

1.Cost表示響應一次服務，用戶需支付的成本花銷，由服務提供商給出；

2.Response Time表示用戶請求服務和用戶接收回答的時間間隔；

3.Availability表示一個服務在一定時間間隔可訪問的時間比；

4.Reliability表示一個服務正確和穩定的行為能力.

定義3.(服務請求)：服務請求r是一個三元組r=(I，O，w)，其中：

1.I是用戶能夠提供的輸入集合；

2.O是用戶期待得到的輸出集合；

3.0

3.2 能量模型

在本研究中，整個網絡生存周期內主要考慮的能量消耗包括環境感知、發送數據和接收數據的消耗，本研究中的能量消耗計算模型采用一階無線電模型[16]，表1表示的是該模型中各參數的含義.

表1 能量模型參數含義Table 1 Meaning of the energy model parameters

PSense表示的是節點環境感知消耗的能量，PTx和PRx表示的是將一個b比特的數據包傳送r的距離的過程中的傳輸耗能和接收耗能，公式如下所示：

PSense=α1b

(1)

PTx=(β1+β2rn)b

(2)

PRx=γ1b

(3)

n為傳播衰減系數，數值范圍為2-5，n的取值取決于設備的環境，假設在當前物聯網環境下，設備在傳輸數據包時是無障礙物的，將n的值定為2[17].根據一階無線電模型，一些典型的參數值如下公式所示：

α1=60*10-9J/bit

(4)

β1=45*10-9J/bit

(5)

β2=10*10-12J/bit/m2

(6)

γ1=135*10-9J/bit

(7)

4 物聯網服務組合流程

在基于用戶需求QoS限制的物聯網服務組合應主要從局部、全局兩個階段上考慮.局部上，引入語義網的相關技術，實現QoS的語義化；全局上，計算QoS的屬性值對服務進行選擇.

物聯網服務組合過程主要包括用戶需求分析、服務發現、服務匹配、服務選擇和服務組合五個階段，處理流程如圖1所示.

4.1 服務匹配

通過需求分解單元將用戶需求分解為功能性需求和非功能性需求，根據功能性需求，利用語義相似度計算方法，從服務庫中選取符合要求的候選服務集[18，19].

圖1 用戶請求處理框圖Fig.1 Processing block diagram of the user′s request

為提高求解效率，利用每個服務的位置信息，采用局部優選方法，從候選服務集中，為每個抽象服務優選出優秀候選服務集.

4.2 服務選擇

針對優秀候選服務集中服務的選擇，在全局最優策略中，不能只考慮當前功能環節的QoS和能量計算，需要考慮各個功能節點聚合后的QoS和能量評價值，使組合方案整體的QoS和能量滿足限制條件.而具體的QoS的聚合計算和服務組合的執行路徑有著密不可分的關系，一般存在四種基本結構，即并行結構、串行結構、分支結構和循環結構[19]，如圖2所示.

圖2 四種基本工作流Fig.2 Four basic workflows

根據不同QoS屬性的特點，給出每個QoS屬性在四種工作流下的不同計算方法，如表2所示.

表2 四種工作流下QoS計算方法Table 2 QoS calculation methods under four kinds of workflows

4.3 服務組合實例化

4.3.1 服務組合目標函數

1.最小化目標

f1=Econsumption

(8)

EConsumption=PSense+PTx+PRx

(9)

2.最大化目標

f2=QoS′i,j(S)

(10)

(11)

3.目標函數

(12)

其中，w1和 w2都是權重因子，均為大于0的正數，分別表示f1和f2所占比的重要程度，并且w1+ w2=1.在本文中，考慮網絡負載均衡的要求，采用如下自適應方法自動地調節權重因子的值：

(13)

其中，Emax為節點能量的最大值，Eres為節點能量的剩余值，Eave為節點能量的平均值，0≤k1,k2≤1為常數.

4.3.2 服務組合優化方法

啟發式算法可以有效解決大規模問題及NP難問題[20]，因此在本文研究過程中引入了遺傳算法和粒子群算法，其步驟如下：

1.遺傳算法

遺傳算法是一種通過模擬自然進化過程尋找優化解的算法，它包括：選擇、交叉、變異.在本文中，基因表示為物聯網服務，染色體表示為不同的服務組合，染色體的適應度反映了群體個體的適應度.

算法1.遺傳算法

輸入：

MAX：最大迭代次數

N：初始種群中染色體的數量

輸出：一條相對優化的染色體序列

1.while 迭代次數

2.for i

3.采用輪盤賭選擇法選擇種群中的染色體，將其加入到下一代種群中，其中具有較大適應度函數值的個體更容易被選擇

4.采用單點交叉方法進化下一代染色體

5.采用變異算子進化下一代染色體

6.end for

7.基于適應度將子代插入到新種群中

8.end while

算法1是遺傳算法的具體流程，在產生初始種群后，計算其適應度函數值，采用輪盤賭選擇法選擇當前種群中的染色體，并加入到下一代種群中(第3行).采用單點交叉和變異(第4、5行)，對種群中的染色體進化處理.基于適應度函數值將進化后的個體插入到下一代種群中(第7行).不斷重復上述過程，直到找到最優染色體或達到最大迭代次數時循環終止.

2.粒子群算法

粒子群算法是受鳥群覓食行為啟發的一種優化算法，粒子代表的是不同的服務組合.在該算法的每一次迭代中，粒子通過兩個極值進行更新：1)粒子局部最優解pBest；2)目前整個種群中全局最優解gBest.粒子更新d維速度和位置時遵循如下公式：

popv(i，:)=w*popv(i，:)+c1*rand*(pBest(i，:)-
popx(i，:))+c2*rand*(gBest-popx(i，:))

(14)

popx(i，:)=popx(i，:)+popv(i，:)

(15)

其中，w叫慣性權重，c1、c2為學習因子popv(i，：)為粒子的當前速度.

算法2.粒子群算法

輸入：

MAXGEN：最大迭代次數

M：初始種群中粒子的數量

輸出：一條相對優化的粒子序列

1.for i

2.計算每個粒子的適應度，并初始化個體最優解pBest和整體最優解gBest

3.end for

4.while 迭代次數

5.for i

6.利用公式(14)、公式(15)更新個體的位置和速度

7.計算目標函數值

8.更新pBest和gBest

9.end for

10.找到最優解粒子

11.end while

算法2是粒子群算法的具體流程，在產生初始種群后，計算每個粒子的適應度，并對個體最優解和整體最優解進行初始化(第2行).根據公式14和公式15更新粒子的速度和位置(第6行)，計算目標函數值并更新pBest和gBest.不斷重復上述過程直到達到最大迭代次數時循環終止.

5 實驗及仿真結果

5.1 實驗仿真

實驗模擬500m×700m的網絡區域中的空氣污染環境感知，其中部署了PM2.5，PM10，CO，SO2，O3，NO2六個服務類共1200個傳感器節點，采用隨機分布方式，獲取每個節點的地理位置值，圖3表示的是PM2.5的節點部署位置.

假設每個節點上只封裝一個服務.在本次實驗中，我們設置每個節點的初始能量為0.01J，為求取某一地點的空氣污染程度，模擬工作流如圖4所示，實驗采用Al-Masri E等人[21]提供的數據集，如圖5所示，設定每個節點的服務質量屬性值，通過Matlab平臺來驗證本文算法的可行性和有效性.

圖3 PM2.5節點部署情況Fig.3 PM2.5 node deployment

圖4 模擬工作流Fig.4 Simulation workflow

圖5 數據集Fig.5 Data set

5.2 性能參數

1.網絡生命周期

網絡生命周期定義為從整個網絡開始響應用戶請求到任一用戶請求無法響應為止.根據節點的最小剩余能量判斷網絡的生命周期，網絡中節點的最小剩余能量越充足，網絡生命周期越長.

2.剩余能量方差

根據整個網絡中節點的剩余能量方差大小，判斷網絡的負載均衡情況.方差值越小，說明該網絡中節點的使用越平均.

5.3 實驗結果

首先，將本文提出的自適應方法控制目標函數的方法在遺傳算法和粒子群算法下與只考慮能耗的目標函數和只考慮QoS屬性值的目標函數的方法分別執行30次后進行比較，如圖6、圖7所示.

從圖6、圖7中可以看出，利用遺傳算法和粒子群算法進行服務組合實例化時，本文提出的方法QoS屬性值變化接近于只考慮QoS性能的目標函數方法下屬性值的變化，能耗變化接近于只考慮能耗的目標函數方法下能耗的變化.這說明本文方法在保證低能耗的同時，也能保證QoS屬性值的優選.

圖6 本文方法與只考慮能耗的目標函數方法分別執行30次能量消耗的變化Fig.6 Energy consumption value for the method of this paper and the objective function method considering onlyenergy consumption when the algorithms are executed in 30 contiguous time slots

圖7 本文方法與只考慮QoS值的目標函數方法分別執行30次能量消耗的變化Fig.7 Energy consumption value for the method of this paper and the objective function method considering onlyQoS value when the algorithms are executed in 30 contiguous time slots

其次，將本文提出的自適應控制目標函數的方法在遺傳算法和粒子群算法下與固定目標函數的方法進行比較，如圖8所示.

圖8 本文方法與固定目標函數的方法在整個網絡生命周期中剩余能量方差的變化Fig.8 Variance of the residual energy of the methods proposed in this study and the methods offixed objective functions throughout the network life cycle

從圖8(a)中可以看出，利用遺傳算法進行服務組合實例化時，在整個網絡生命周期中，固定目標函數的方法可以執行1352次服務請求，本文提出的自適應控制目標函數的方法可以執行1491次服務請求.從圖8(b)中可以看出，利用粒子群算法進行服務組合實例化時，在整個網絡生命周期中，固定目標函數的方法可以執行1212次服務請求，本文提出的自適應控制目標函數的方法可以執行1309次服務請求.在圖8中，本文的方法和固定目標函數的方法方差變化基本一致，并且本文的方法的方差比固定目標函數的方法的方差小.說明改進的算法能更好維持QoS和能耗的平衡，進而延長網絡生存周期.

再將本文與參考文獻[11]Yang等人提出的方法和參考文獻[13]Alsaryrah等人提出的方法進行對比，如圖9所示.

圖9 本文方法與參考文獻[11，13]在整個網絡生命周期中剩余能量方差的變化Fig.9 Variance of the residual energy of the methodsproposed in this study and the method proposed inreferences[11，13] throughout the network life cycle

從圖9中可以看出，在整個網絡生命周期中，本文提出的自適應控制目標函數的方法可以執行1491次服務請求，Yang等人的方法可以執行1295次服務請求，Alsaryrah等人的方法可以執行1346次服務請求.三種方法的方差變化基本一致，并且本文方法的方差小于其他兩種方法的方差，隨著服務請求次數的增加，本文方法的方差與其他兩種方法的方差差距逐漸明顯，說明改進的算法能更好的避免某一節點的過度使用，進而延長網絡生命周期.

6 總 結

物聯網環境下服務組合要求兼顧服務的時空約束條件、功能約束條件和能量約束條件，以及每個智能設備的地理位置、應用環境、網絡延遲和剩余能量等因素，以確保網絡中的設備能量負載均衡.本文基于網絡生命周期不同階段對節點能耗的不同要求，提出一種自適應方法來動態地構建目標函數，實驗結果表明，本文的算法提供了QoS屬性值和能源效率更好的平衡，避免了單個節點的過度消耗，延長了整個網絡生存周期.