基于服務功能價值的物聯網信息服務組合

楊 臻，李德識，2

（1.武漢大學 電子信息學院，湖北 武漢430070；2.武漢大學 深圳研究院，廣東 深圳518000）

0 引 言

物聯網信息服務主要為用戶提供來自RFID 標簽、傳感器等設備的感知數據［1］。隨著面向服務的體系結構思想（service－oriented architecture，SOA）引入物聯網［2］，每一個感知設備的功能都可以作為服務被其它物理實體發現和調用。

為滿足復雜的用戶需求，需要將位置信息、感知信息不同的多個設備的數據信息進行組合。目前服務組合的研究多基于互聯網，側重驗證服務組合的可行性和邏輯性［3］，而物聯網信息服務旨在為用戶提供感知信息，各感知設備之間相互獨立，無嚴格的邏輯前驅、后繼關系，側重服務體驗最優化。互聯網以人工方式產生語音、文本、多媒體文件等服務數據，QoS性能主要包括服務可靠性、可用性、信譽度等［4］，而物聯網主要處理電子標簽、傳感器等設備生成的數據，服務性能還需考慮感知設備的地理位置信息。因此研究物聯網環境下的信息服務組合十分必要。

Li Kun提出了基于上下文的服務組合方法［5］，利用上下文精簡候選服務集，再選擇各功能屬類下QoS評分最優的服務進行組合，這種組合方式缺乏全局約束，是局部意義的最優；Jin Liu 等提出搜索全局QoS 最優的組合方案［6］，但未體現不同功能信息對用戶的價值差異；Xinming Li等提出從空間、時間與功能相似性匹配的角度，準確地衡量候選服務與用戶需求的匹配程度，將匹配度最高的服務組合定義為最優方案［7］，但該方法未涉及服務組合的QoS性能。

文章提出了一個物聯網QoS模型，定義了服務的功能信息對用戶的價值，將其作為評價服務的用戶偏好，應用改進的遺傳算法搜索最佳組合方案，能篩選出更符合用戶需求的感知數據。

1 服務組合流程

信息服務組合應考慮從局部、全局上兩階段擇優。局部上，將初始候選服務集按功能分簇。為了提高服務組合效率，可評比同一功能屬類下不同服務的QoS性能，選取QoS性能較好的k個服務作為該功能屬類下的最終候選服務。在最終候選服務集中，任選多個功能不同的信息服務進行組合，即可構成一個服務組合方案。全局上，將服務組合的擇優問題，轉化為給定約束條件下求解目標函數最優值的優化問題，利用改進的遺傳算法全局尋優，獲得QoS性能、功能需求匹配程度最佳的服務組合。

物聯網信息服務的組合過程主要包括需求分析、服務發現、單個服務選擇、服務組合選擇4個階段。服務組合尋優流程如圖1所示。

圖1 用戶請求處理流程

（1）分析用戶需求。分析用戶需求描述文檔，能獲得目標服務的功能需求與非功能需求，功能需求由功能關鍵詞集合表述；非功能信息包括QoS屬性值，以及用戶對QoS各個屬性的偏好程度。統計各功能關鍵詞在Google知識庫中的索引數目，定量評價該功能對用戶的價值。

（2）服務發現。在用戶指定的信息獲取地為中心的一定地域范圍內，搜索能滿足各子功能需求的原子信息服務。多個功能不同、位置信息不同的感知設備，構成初始候選服務集合。

（3）單個服務評分。根據功能信息將候選服務分簇，基于多屬性決策對同一功能屬類下的初始候選服務子集進行細粒度個性化評分，擇優選擇評分排名前k個服務作為最終候選服務，為組合服務的選擇打下基礎。

（4）服務組合擇優。采用全局優化算法，搜索QoS性能與功能信息更滿足用戶需求的組合方案，為用戶提供相應感知數據。

2 服務組合匹配

用戶需求可分為功能需求和非功能需求。功能需求表征用戶希望獲得何種感知數據，非功能需求表征用戶對服務性能的需求，是對功能需求的個性化補充。功能需求可能是簡單的原子需求，也可能是復雜需求。原子需求定義為構成服務需求的最小單元，不可細分，復雜需求由多個原子需求組合而成。在基于SOA 的物聯網中，信息服務往往是功能細化的原子服務，但用戶需求往往是粗粒度的復雜需求，為了充分利用物聯網服務資源，更好地滿足用戶需求，需要對各功能細化的原子服務進行組合。

自頂而下［8，9］組合匹配是一種服務自動組合方式，原理是將復雜的功能需求分解為多個功能語義相關的子功能需求，通過對子需求的共同滿足來實現復雜需求的滿足。這種組合方法以單服務的本體語義匹配為基礎，實現簡單，能很好地解決子需求的服務匹配問題，但是未充分利用已發布的服務，組合靈活性受限。自底而上［10，11］組合匹配則是根據用戶需求，在服務庫中選擇多個原子服務自由組合，判斷組合與用戶需求的功能匹配度。這種組合方法充分利用了已發布的服務資源，非常適合服務挖掘，但由于物聯網服務資源豐富，組合方案搜索空間龐大，不僅增加了組合匹配實現的難度，還不能保證搜索效率。本文結合以上兩種方法的優勢進行需求分析與服務匹配。

在需求分析方面，對用戶提出的復雜功能需求，采用自頂而下思想進行需求分解，得到多個較粗粒度的子功能需求，將組合匹配轉變成對各子需求的服務發現、匹配，能篩選掉服務庫中一部分不滿足功能需求的服務，減小搜索范圍。

在服務匹配方面，可以犧牲一部分語義匹配精度，換取服務挖掘的能力。因為物聯網感知信息多涉及細粒度的專業概念，而用戶描述可能是大語義范圍的語言描述，根據本體庫計算得到的語義相似度，能反映候選服務功能與用戶描述的概念之間的語義距離，但不能完全反映該服務的功能對用戶的重要性程度。可在服務數據庫中，搜索服務功能描述與用戶功能需求滿足一定語義相似度的服務，這些服務的功能構成服務組合的功能關鍵詞集，權衡各個服務的功能對用戶的價值，用以衡量候選服務對用戶的重要性。考慮到關鍵詞在Google知識庫中的索引數目一定程度上能反映當前社會對該關鍵詞的關注程度，索引越多反映該功能信息對用戶的價值越大，文中統計各功能關鍵詞在Google知識庫中的索引數目，定量地表征各服務功能的相對重要性。

例如用戶輸入的功能需求為 “空氣污染”，在服務庫中搜索與該概念語義相關的服務，獲得服務組合關鍵詞集為CO2、SO2、PM2.5、CO、CFCs、碳 氫 化 合 物、PM10、NO2。在Google中分別將以上8個關鍵詞連同與 “空氣污染”一同搜索，獲得索引數目約為：v ［8］＝｛9，8，42，6，4，4，5，7｝ （單位：十萬個），用無量綱數值表征相應的功能價值，各個功能之間的相對重要性就能明確地區分開來。

3 物聯網服務QoS建模與評價

隨著物聯網的發展，各行業應用需求推動各種類型的傳感器節點廣泛應用。每個傳感器能提供某一特定功能的感知數據，表示為原子信息服務。大量的物聯網信息服務功能相同或相似，但服務QoS不同，因此服務組合需要考慮QoS性能的優劣。

QoS概念源于通信網絡，主要描述數據傳輸中的質量特性，關鍵指標通常有代價、響應時間、信譽度等，但物聯網的特點決定了物聯網信息服務還需考慮實體設備的資源有限性、網絡環境動態性及其物理語境與應用場景。結合以上分析，可將物聯網信息服務的QoS關鍵指標建模為五元組：代價、響應時間、可靠性、地理距離與剩余能量，各指標的定義和量化方法描述如下。

代價：用戶發起一次感知信息查詢需要支付給服務提供商的費用。

響應時間：從用戶提交請求到接受到服務響應之間的時間間隔，包括用戶請求處理時間和感知設備的采樣、處理、傳輸時延，常以一段時間內的歷史響應時間的平均值衡量。

可靠性：物聯網感知設備的軟硬件環境、通信網絡環境會影響信息服務的成功率，一定時間內為用戶提供感知數據的成功率能衡量信息服務的可靠性。

地理距離：感知設備的數據信息與設備所在的地理環境密切相關。若用戶指定的感知地附近已部署了感知設備，感知數據必然精準，但往往感知設備與用戶指定的感知地之間存在距離差，可能導致信息數據誤差。測定每個候選服務的設備地理位置與用戶指定感知地之間的距離差，將其作為物理距離參數值。距離差越小，代表感知數據更貼近用戶需求。

剩余能量：與互聯網服務設備不同，物聯網底層傳感設備能量受限。傳感器的可持續服務時間與剩余能量成正比。剩余能量低的傳感器在一段時間后電池能量耗盡，會導致服務失效，無法繼續提供感知數據。將每個傳感器的剩余能量納入評價標準，優先將剩余服務時間長的傳感器加入組合，能增加服務組合的可重用性。

服務組合的QoS平均性能受組合內各原子服務QoS性能的影響。在本文的物聯網QoS模型中，可靠性、剩余能量是效益型屬性，而代價、響應時間、地理距離是成本型屬性。不同屬性量綱不同、數量級不同，因此需要對各個屬性值進行標準化。采用極差變換法式 （1）、式 （2），能分別將成本型屬性與效益型屬性標準化，從而消除量綱與數量級的影響［12］。式 （1）、式 （2）中i表示服務編號，j表示服務的第j 種QoS屬性，qij表示第i 個服務、第j種屬性的值，maxqj與minqj分別表示所有服務中第j 種QoS屬性的最大、最小值，sij表示第i個服務、第j種屬性的歸一化評分。

加權算術平均式 （3）能計算各候選服務的綜合評分，這種計算方法允許數據之間線性補償，強調整體數據影響，Qij值越大，表示服務的QoS性能越佳。ωi是用戶對各屬性相對重要性的偏好估計，可采用熵值法等主、客觀賦權方法測定［12］。為了提高服務組合的搜索效率，在每個功能屬類下，擇優選取Qij值排名前k 個服務，作為最終候選服務集

4 服務組合優化求解

根據用戶需求描述文檔能獲得服務組合的功能關鍵詞集，表示如圖2所示F1，F2，…，Fm。依據QoS評分精簡初始候選服務集后，每個功能屬類下存在多個候選服務實例BSij（i＝1，2，...m，j＝1，2，…，k）。由于各查詢請求之間不存在嚴格的前驅、后繼邏輯關系，只要符合功能需求、滿足總代價約束的任意服務實例都可加入組合，因此存在大量的備選方案。

圖2 服務組合

組合尋優求解方法有窮舉搜索、貪婪算法、回溯法、動態規劃法、遺傳算法等。窮舉搜索一定能發現最優組合，但搜索時間及空間代價都很大；貪婪算法計算復雜度低，但不能保證得到最優解；回溯法與動態規劃算法的求解耗時會根據問題規模呈冪級數增加；遺傳算法不需要與應用背景相關的啟發式知識，搜索代價相對較小，只需要目標函數和相應適應值函數即可高效、健壯地求解大規模組合問題，被廣泛用于求解最優化問題。

基于以上分析，文章采用遺傳算法思想全局優化。傳統的遺傳算法通過交叉、變異操作不斷產生新染色體，直到滿足迭代次數N ＝Nmax 后算法才停止。歷來研究者們更傾向從避免遺傳算法過早收斂、保持種群多樣性方面改進遺傳算法，加大搜索空間。但對于物聯網中某些特定的應用場景，用戶對物聯網信息服務的實時性要求較高，服務組合決策時間對信息服務的感知數據準確性有直接影響，適當加快種群收斂，根據種群收斂狀態適時終止迭代，提高最優化求解的效率顯得更為重要。采用精英保留策略，并將種群相似度加入算法終止條件有助于解決這個問題。

種群相似度可定義為式 （4），sim（G）為第G 次迭代種群的相似度，SimF（G）是在當前種群中適應度值相同的染色體個數，Gnum 是種群的規模。當種群相似度值在 ［r，1］區間 （相似度閾值r可取0～0.9 之間的數）內時，表示種群中絕大多數的染色體相同，算法已收斂，可終止種群迭代

從用戶角度，兼顧QoS性能與功能價值的服務組合才是最好的選擇。根據遺傳算法的思想，適應度函數與約束條件可定義為式 （5）。將各個待組合的候選服務按功能關鍵詞分簇，實現第i種功能的服務對用戶的價值為vi。實現第i種功能的第j 個服務實例的QoS評分值為Qij，耗費代價為cij。bi是標志位，取 “0”表示服務組合中不包含實現第i個功能的服務；取 “j”表示將第i種功能的第j 個服務實例BSij加入組合。 （b1b2b3...bm）組成一個染色實數編碼碼串，各基因位的取值形象地反應了各功能相應服務實例的選取狀態。在滿足總代價約束時，功能價值加權的QoS總評分越高，相應的服務組合與用戶需求的匹配程度越高

采用改進遺傳算法全局尋優，流程如圖3 所示。實數編碼使遺傳算法能靈活地在大候選服務空間中尋優，基于效益貪心策略的可行性檢查能修正不可行的組合方案，交叉和變異能維持種群多樣性，精英保留策略與種群相似度檢查能加快算法收斂。

圖3 改進遺傳算法流程

算法實現流程可表述為：

（1）隨機產生規模為M 的初始種群，采用實數編碼隨機生成染色體碼串，定義式 （4）所示的適應度函數與約束條件。

（2）基于效益貪心策略，檢查種群內M 條染色體的合法性。種群迭代的過程中必然會產生部分不滿足總代價約束的染色體，在值非0的基因位中，優先選取功能價值最低的位，將服務組合中實現功能Fi的服務用代價更小的服務替代，直至染色體合法。

（3）檢查當前迭代次數與種群相似度。當滿足最大迭代次數或種群相似度達到閾值時，停止種群迭代，返回當前最優解。

（4）采用賭輪法產生M 條父染色體復制到交配池，進行單點交叉、變異。變異是以一定的概率在染色體中隨機選擇一個基因位，在取值區間內隨機改變bi的值，生成新染色體，保證盡量多的服務組合方案能加入尋優過程。

（5）采用精英保留策略。在父代種群中選取適應度值較大的部分染色體作為精英保留，直接代替子代種群中同比例適應度值小的染色體，共同構成新種群，避免優秀染色體在下一輪迭代的選擇、交叉操作中丟失。

重復上述過程直至迭代終止，最終搜索到總價值最大的最優解決方案。

5 實例分析

基于VS2008仿真服務組合的狀態，將本文的方法與基于QoS約束的傳統服務組合方法進行對比。開發環境為Intel Core 3.3GHz處理器，3.4GB內存，操作系統為Windows XP。遺傳算法初始配置為：交叉概率為0.8 （一般為0.4－0.9），變異概率為0.09 （一般為0.01－0.1），父代精英比例20%，最大迭代次數為300，種群相似度閾值為0.8，基于C＋＋編程。

設定服務需求為某地的 “空氣污染”信息。假設在感知目的地附近區域共部署了CO2、SO2、PM2.5、CO、CFCs、碳氫化合物、PM10、NO2共24個傳感器節點，每個傳感器對應一個提供感知信息的候選服務。各服務的代價與QoS評分值在一定范圍內隨機生成，用二維數組表示，代價為Cost［8］［3］＝ ｛｛3，2，2｝，｛1，5，3｝，｛1，4，2｝，｛1，3，5｝，｛2，4，3｝，｛1，2，3｝，｛1，1，3｝，｛2，2，1｝｝，QoS評分為QoS［8］［3］＝｛｛0.88，0.85，0.81｝，｛0.87，0.84，0.92｝， ｛0.72，0.61，0.88｝， ｛0.88，0.90，0.90｝，｛0.65，0.85，0.98｝，｛0.85，0.80，0.90｝，｛0.90，0.86，0.96｝，｛0.80，0.89，0.99｝｝。在Google知識庫中統計8種功能的索引數目，得到功能價值：v ［8］＝ ｛9，8，42，6，4，4，5，7｝。

Qiufen Wang采用與貪心策略相結合、二進制編碼的遺傳算法，在迭代次數N＝Nmax后停止算法［13］。為了滿足服務組合的需要，將遺傳算法的編碼改變為實數編碼，其它策略不變。在候選服務的功能種類規模不同時，比較加速收斂的遺傳算法與自然收斂的遺傳算法［13］的求解效率。預先設定功能種類個數分別為8，12，16，20，24，28，每種功能都擁有3個候選服務供選擇，采用遺傳算法獨立運行30次，統計組合優化求解的平均耗時，結果如圖4所示。實驗結果表明，為遺傳算法添加精英保留策略與收斂性判定準則后，在可行服務組合方案達428種時，服務組合優化求解都能在12.8ms內完成；而自然收斂的遺傳算法［13］求解耗時達31.33 ms，這是因為無論種群是否收斂，算法依然要迭代300次，增加了執行時間。

圖4 組合求解耗時比較

將功能價值與QoS相結合的擇優策略與僅基于QoS的擇優策略［13］作對比，應用相同的遺傳算法搜索全局優化解，實驗結果見表1。

表1 實驗結果對比

若用戶能承受的最大服務組合代價為10 （單位：元），在不考慮信息服務之間的功能價值差異時，最優染色體的基因位b1＝0，代表服務組合僅不提供CO2感知信息，但此功能價值對用戶的重要性排名第二，明顯是用戶不希望丟失的信息。而本文應用功能價值與QoS雙重標準進行組合匹配，最優染色體的基因位b5＝0，表示服務組合僅不提供CFCs感知信息，此功能對用戶的重要性相對最低，與前種方法相比更好地保留了用戶最需要的功能信息，同時服務組合的QoS平均性能也相差不大。

實驗結果表明，不論是從最優求解結果與用戶需求的匹配程度，還是從全局優化求解效率的角度，本文算法能更好地解決物聯網信息服務組合求解問題。

6 結束語

物聯網信息服務組合可看作兼顧功能需求匹配度、QoS性能、組合決策效率的全局優化問題。基于物聯網感知設備資源受限、感知信息與物理環境密切相關的特點，提出從服務質量與服務對用戶的價值兩方面評價候選服務與用戶需求的功能匹配度，結合物聯網QoS模型，應用效率提升的遺傳算法全局優化。實驗結果表明，將功能價值納入服務評價標準后所得的服務組合更符合用戶需求。目前直接采用關鍵詞在Google中的索引數目作為功能價值，簡單方便，未來可考慮采用大數據分析方法衡量功能價值，獲得更精確的功能價值。

［1］ZHANG Feizhou，YANG Dongkai，CHEN Zhi.An introduction to Internet of things technology ［M］.Beijing：Publishing House of Electronics Industry，2010：25－26 （in Chinese）.［張飛舟，楊東凱，陳智.物聯網技術導論 ［M］.北京：電子工業出版社，2010：25－26.］

［2］Guinard D.Interacting with the SOA－based Internet of things：Discovery，query，selection and on－demand provisioning of Web services［J］.IEEE Transactions on Services Computing，2010，3 （3）：223－235.

［3］TIAN Hao，FAN Hong.A semantic rule based method of phased semantic Web service discovery ［J］.Computer Engineering and Design，2012，33 （5）：1806－1810 （in Chinese）.［田浩，樊紅.基于語義規則的分階段語義Web服務發現方法［J］.計算機工程與設計，2012，33 （5）：1806－1810.］

［4］ZHANG Peiyun，HUANG Bo，SUN Yamin.A semantic and QoS－aware based Web service match mechanism ［J］.Computer Research and Development，2010，47 （5）：780－787 （in Chinese）. ［張佩云，黃波，孫亞民.一種基于語義與QoS感知的Web服務匹配機制 ［J］.計算機研究與發展，2010，47 （5）：780－787.］

［5］Li Kun.The research of Web services composition based on context in Internet of things ［J］.IEEE International Conference on Computer Science and Automation Engineering，2012，1：25－27.

［6］Liu Jin，Chen Yuxi，Chen Xu，et al.A cooperative evolution for QoS－driven IoT service composition ［J］.Automatika，2013，54 （4）：438－447.

［7］Li Xinming，Sun Yan.A service mining scheme based on semantic for Internet of things ［J］.Chinese Journal of Electronics，2014，23 （2）：236－242.

［8］WANG Yu，XIANG Chaocan，WANG Meng，et al.Research status and development of semantic Web service discovery ［J］.Application Research of Computers，2013，30 （1）：7－12 （in Chinese）.［王玨，向朝參，王萌，等.語義Web服務發現研究現狀與發展 ［J］.計算機應用研究，2013，30 （1）：7－12.］

［9］Tian YH，Su YL，Zhuang XF.Research on service identification methods based on SOA ［C］／／3rd International Conference on Advanced Computer Theory and Engineering，2010：V6－27－V6－31.

［10］Zheng Xiaolin，Lin Zhen，Yang Yanbo，et al.Research on context aware Web service composition based on the fluent caculus ［J］.Advances in Information Sciences and Service Sciences，2011，3 （7）：62－74.

［11］Anne HH Ngu，Michael P Carlson，Hye－young Paik，et al.Semantic－based mashup of composite applications ［J］.IEEE Transactions on Services Computing，2010，3 （1）：2－15.

［12］ZHANG Quan.Complex multiple attribute decision making research ［M］.Shengyang：Northeastern University Press，2008：16－56 （in Chinese）. ［張全.復雜多屬性決策研究［M］.沈陽：東北大學出版社，2008：16－56.］

［13］WANG Qiufen，LIANG Daolei.A heuristic genetic algorithm for solving 0－1knapsack problem ［J］.Computer Applications and Software，2013，30 （2）：33－37 （in Chinese）.［王秋芬，梁道雷.一種求解0－1背包問題的啟發式遺傳算法 ［J］.計算機應用與軟件，2013，30 （2）：33－37.］