王新穎，李 敏，熊 偉

1(湖北文理學(xué)院 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，湖北 襄陽 441053) 2(湖北文理學(xué)院理工學(xué)院 電子科學(xué)與信息工程系，湖北 襄陽 441025) E-mail:wxy200888@126.com

1 引 言

隨著Ad Hoc網(wǎng)絡(luò)應(yīng)用規(guī)模的持續(xù)快速增長，針對用戶個性化需求的按需服務(wù)發(fā)現(xiàn)需求日益旺盛，因而，對高精度的Ad Hoc網(wǎng)絡(luò)服務(wù)發(fā)現(xiàn)的理論和方法進(jìn)行深入研究有著極其重要的現(xiàn)實(shí)意義.由于Ad Hoc網(wǎng)絡(luò)所處的網(wǎng)絡(luò)環(huán)境容易受到復(fù)雜多變因素的影響，使得傳統(tǒng)的服務(wù)發(fā)現(xiàn)方法在Ad Hoc網(wǎng)絡(luò)環(huán)境下難以獲得較高精度[1-4]，不適合在Ad Hoc網(wǎng)絡(luò)中應(yīng)用.

近年來，為了解決在Ad Hoc網(wǎng)絡(luò)中存在的復(fù)雜多樣的服務(wù)發(fā)現(xiàn)問題，國內(nèi)外該領(lǐng)域的研究人員做了大量的研究工作.文獻(xiàn)[5]基于對等的通信模式，提出一種完全分布式的Ad Hoc網(wǎng)絡(luò)服務(wù)發(fā)現(xiàn)機(jī)制.文獻(xiàn)[6]提出一種CSDM服務(wù)發(fā)現(xiàn)方法，該機(jī)制將簇頭節(jié)點(diǎn)列表中全部的服務(wù)請求按照優(yōu)先級級別實(shí)施動態(tài)區(qū)分管理操作，不僅較好的改善了服務(wù)發(fā)現(xiàn)的性能，也提高了整個系統(tǒng)的穩(wěn)定性.文獻(xiàn)[7]提出一個基于上下文的Ad Hoc網(wǎng)絡(luò)服務(wù)發(fā)現(xiàn)機(jī)制，在該機(jī)制中，服務(wù)發(fā)現(xiàn)的執(zhí)行策略由服務(wù)節(jié)點(diǎn)周圍的環(huán)境來決定.文獻(xiàn)[8]基于蟻群算法，提出一種基于可信度的服務(wù)發(fā)現(xiàn)機(jī)制，該機(jī)制根據(jù)節(jié)點(diǎn)在網(wǎng)絡(luò)中的相互作用和行為計(jì)算它們的可信度，并根據(jù)可信度進(jìn)行服務(wù)發(fā)現(xiàn).文獻(xiàn)[9]提出一種健壯、可伸縮的服務(wù)發(fā)現(xiàn)方案，該方案通過一致性管理機(jī)制，實(shí)現(xiàn)了服務(wù)發(fā)現(xiàn)的健壯性；通過多層次的目標(biāo)本體，解決了Ad Hoc網(wǎng)絡(luò)的知識表示問題，實(shí)現(xiàn)了服務(wù)發(fā)現(xiàn)的可擴(kuò)展性.文獻(xiàn)[10]提出一種SSD服務(wù)發(fā)現(xiàn)方法，該方法考慮了服務(wù)節(jié)點(diǎn)的計(jì)算能力、存儲能力、通信能力、剩余電量、位置和網(wǎng)絡(luò)狀態(tài)等屬性，具有較高的查準(zhǔn)率和較好的服務(wù)質(zhì)量.

以上幾種服務(wù)發(fā)現(xiàn)機(jī)制廣泛存在的不足是：沒有合理的考慮功能屬性以外的其它因素，即服務(wù)情景等非功能屬性[11]，服務(wù)發(fā)現(xiàn)的質(zhì)量還需要更進(jìn)一步的提高.在Ad Hoc網(wǎng)絡(luò)環(huán)境下，針對具有相同功能的服務(wù)，對用戶而言，它們在移動性、剩余電量、響應(yīng)時(shí)間和丟包率等服務(wù)情景上的表現(xiàn)有所不同，而只有當(dāng)服務(wù)能夠滿足用戶在這些方面的要求時(shí)，用戶才會考慮這個服務(wù)所提供的功能.因此，在Ad Hoc網(wǎng)絡(luò)應(yīng)用中，研究基于服務(wù)情境的服務(wù)發(fā)現(xiàn)機(jī)制顯得尤為重要.

本文提出一種基于服務(wù)情景的Ad Hoc網(wǎng)絡(luò)服務(wù)發(fā)現(xiàn)方法——SDSS.該Ad Hoc網(wǎng)絡(luò)服務(wù)發(fā)現(xiàn)方法在基于語義推理進(jìn)行功能匹配的基礎(chǔ)之上，對符合功能匹配所得到的候選服務(wù)集，進(jìn)一步執(zhí)行了基于服務(wù)情景約束的服務(wù)篩選操作和基于服務(wù)情景評價(jià)的服務(wù)排序操作，不僅在一定程度上提高了Ad Hoc網(wǎng)絡(luò)服務(wù)發(fā)現(xiàn)的查準(zhǔn)率，其服務(wù)質(zhì)量也得到了有效改善.

本文第2節(jié)詳細(xì)分析了SDSS服務(wù)發(fā)現(xiàn)機(jī)制，第3節(jié)對提出的Ad Hoc網(wǎng)絡(luò)服務(wù)發(fā)現(xiàn)機(jī)制進(jìn)行了實(shí)驗(yàn)驗(yàn)證，最后是全文的總結(jié).

2 SDSS服務(wù)發(fā)現(xiàn)機(jī)制

2.1 基于服務(wù)情景的Ad Hoc網(wǎng)絡(luò)服務(wù)模型

在Ad Hoc網(wǎng)絡(luò)中，考慮到服務(wù)情景等非功能屬性對服務(wù)的服務(wù)質(zhì)量(QoS)影響巨大，課題組將Ad Hoc網(wǎng)絡(luò)的服務(wù)模型形式化定義為：

定義1.服務(wù)

S=

(1)

在公式(1)中，F(xiàn)P用來代表在Ad Hoc網(wǎng)絡(luò)中服務(wù)的功能屬性，具體包含服務(wù)名稱(SN)、服務(wù)描述(SD)、輸入信息(SI)及輸出信息(SO)等四種功能屬性，如公式(2)所示.

FP=

(2)

考慮到服務(wù)的輸入信息(SI)和輸出信息(SO)都是信息的集合，因此，本文用SI={i1,i2…,in}表示服務(wù)的輸入信息，用SO={o1,o2…,on}表示服務(wù)的輸出信息.

SP代表Ad Hoc網(wǎng)絡(luò)中服務(wù)的情景屬性，具體包含移動性(MO)、剩余電量(RE)、響應(yīng)時(shí)間(RT)、丟包率(PL)等四種服務(wù)情景屬性，如公式(3)所示.

SP=

(3)

2.2 Ad Hoc網(wǎng)絡(luò)服務(wù)發(fā)現(xiàn)架構(gòu)

本文提出的Ad Hoc網(wǎng)絡(luò)服務(wù)發(fā)現(xiàn)架構(gòu)分散部署在Ad Hoc網(wǎng)絡(luò)中的簇頭節(jié)點(diǎn).如圖1所示，該Ad Hoc網(wǎng)絡(luò)服務(wù)發(fā)現(xiàn)架構(gòu)由服務(wù)發(fā)現(xiàn)模塊、注冊模塊及服務(wù)平臺模塊等三部分構(gòu)成.當(dāng)服務(wù)發(fā)現(xiàn)模塊接收到Ad Hoc網(wǎng)絡(luò)中服務(wù)的注冊信息后，該模塊中的解析器首先對服務(wù)注冊信息進(jìn)行解析操作處理，然后，注冊模塊負(fù)責(zé)將服務(wù)信息(包含功能屬性信息和情景屬性信息)存儲在服務(wù)平臺的數(shù)據(jù)庫中；當(dāng)服務(wù)發(fā)現(xiàn)模塊接收到Ad Hoc網(wǎng)絡(luò)中的服務(wù)請求信息后，由服務(wù)匹配子模塊執(zhí)行服務(wù)匹配過程并進(jìn)行服務(wù)回復(fù).

圖1 Ad Hoc網(wǎng)絡(luò)服務(wù)發(fā)現(xiàn)架構(gòu)Fig.1 Architecture of service discovery for Ad Hoc networks

2.3 服務(wù)發(fā)現(xiàn)

基于服務(wù)情景的Ad Hoc網(wǎng)絡(luò)服務(wù)發(fā)現(xiàn)由四個階段組成：

1)依據(jù)Ad Hoc網(wǎng)絡(luò)中服務(wù)的功能屬性，進(jìn)行基于語義的功能匹配，得到符合功能匹配的候選服務(wù)集；

2)在候選服務(wù)集中進(jìn)行基于服務(wù)情景約束的服務(wù)篩選操作，刪除那些不滿足用戶服務(wù)情景約束的服務(wù)；

3)執(zhí)行基于服務(wù)情景的無量綱化處理過程，消除量綱因素對服務(wù)情景評價(jià)結(jié)果所造成的負(fù)面影響；

4)執(zhí)行基于服務(wù)情景評價(jià)的服務(wù)排序操作，進(jìn)而從上面的候選服務(wù)集中得到最優(yōu)的服務(wù).

2.3.1 基于語義的功能匹配

在公式(2)的基礎(chǔ)上，項(xiàng)目組利用服務(wù)相似度的方法對Ad Hoc網(wǎng)絡(luò)中的服務(wù)進(jìn)行功能匹配，進(jìn)而得到候選服務(wù)集.其服務(wù)相似度的形式化定義為：

定義2.服務(wù)相似度

SimS(S,SR)=α*SimSN(SN,SNR)+

β*SimSD(SD,SDR)+

(4)

γ*SimSI(SI,SIR)+

φ*SimSO(SO,SOR)

在公式(4)中，服務(wù)和服務(wù)請求的相似度由SimS(S,SR)表示，其中，服務(wù)名稱的相似度值用SimSN(SN,SNR)來進(jìn)行表示，用α表示它的權(quán)重因子，用SN表示Ad Hoc網(wǎng)絡(luò)中服務(wù)的服務(wù)名稱信息，用SNR表示用戶服務(wù)請求的服務(wù)名稱信息；服務(wù)描述的相似度值用SimSD(SD,SDR)來進(jìn)行表示，用β表示它的權(quán)重，用SD表示Ad Hoc網(wǎng)絡(luò)中服務(wù)的服務(wù)描述，用SDR表示用戶服務(wù)請求的服務(wù)描述；服務(wù)輸入信息的相似度值用SimSI(SI,SIR)來進(jìn)行表示，用γ表示它的權(quán)重因子，用SI表示服務(wù)的輸入信息集合，用SIR表示服務(wù)請求的輸入信息集合；服務(wù)輸出信息的相似度值用SimSO(SO,SOR)來進(jìn)行表示，用φ表示它的權(quán)重因子，用SO表示服務(wù)的輸出信息集合，用SOR表示服務(wù)請求的輸出信息集合.在本文中，利用文獻(xiàn)[12]的方法來計(jì)算公式(4)中各項(xiàng)的相似度值，四個權(quán)重因子滿足α+β+γ+φ=1.

2.3.2 基于服務(wù)情景約束的服務(wù)篩選

在Ad Hoc網(wǎng)絡(luò)服務(wù)發(fā)現(xiàn)過程中，可能存在多個滿足功能匹配的服務(wù)，但用戶感知的QoS服務(wù)情景各不相同.公式(3)定義了單個服務(wù)的服務(wù)情景模型，假設(shè)有n個滿足條件的候選服務(wù)，則它們的服務(wù)情景模型可以表示為：

(5)

在公式(5)中，將全部滿足功能匹配的服務(wù)情景屬性描述成為一個矩陣，該矩陣的列代表不同服務(wù)的某個情景屬性的屬性值，該矩陣的行代表候選服務(wù)集中的服務(wù).公式(5)支持對Ad Hoc網(wǎng)絡(luò)服務(wù)的服務(wù)情景屬性的擴(kuò)展，如果在Ad Hoc網(wǎng)絡(luò)服務(wù)中增加一個服務(wù)情景屬性，只需要在上述矩陣中增加一列.

在通過功能匹配而獲得的候選服務(wù)集中，它們的非功能屬性各有差異，并不是全部的服務(wù)都可以滿足服務(wù)請求者的約束型需求和偏好型需求，需要刪減掉那些不符合請求者需求條件要求的服務(wù).因此，如果一個服務(wù)的某個具體的情景屬性值沒有滿足服務(wù)請求者的服務(wù)情景約束條件，則從候選服務(wù)集中將該服務(wù)刪減.對應(yīng)公式(5)，就是在矩陣中去掉不滿足服務(wù)情景屬性的行.

2.3.3 基于服務(wù)情景的無量綱化處理

為了消除量綱和數(shù)量級對服務(wù)情景的影響，需要對公式(5)中各個服務(wù)的服務(wù)情景屬性值進(jìn)行無量綱化處理.本文依據(jù)服務(wù)情景屬性矩陣自身的特點(diǎn)，采用線性函數(shù)歸一化方法[13]將服務(wù)情景屬性值轉(zhuǎn)換到[0,1]的區(qū)間內(nèi)，具體歸一化公式為：

(6)

在公式(6)中，v代表某個服務(wù)情景的屬性值，vmin與vmax分別代表某個服務(wù)情景的最小屬性值和最大屬性值.

公式(5)經(jīng)過線性函數(shù)歸一化方法處理之后，得到服務(wù)情景的歸一化權(quán)值矩陣，用公式(7)表示.

(7)

2.3.4 基于服務(wù)情景評價(jià)的服務(wù)排序

為了從多個符合服務(wù)請求者約束型需求條件和偏好型需求條件的候選服務(wù)集中發(fā)現(xiàn)適合的QoS最優(yōu)的Ad Hoc網(wǎng)絡(luò)服務(wù)，需要首先計(jì)算每個服務(wù)的綜合服務(wù)情景值，用公式(8)表示.

(8)

在公式(8)中，用v(si)來表示服務(wù)si的綜合服務(wù)情景值，用vij來表示服務(wù)si的某一個具體的服務(wù)情景屬性值，用wj來表示服務(wù)si的某個服務(wù)情景屬性值所對應(yīng)的權(quán)重.在本文中，權(quán)重wj的和為1.

在公式(8)的基礎(chǔ)上，計(jì)算各個服務(wù)的綜合服務(wù)情景值并進(jìn)行排序，得到最優(yōu)的服務(wù).

3 實(shí)驗(yàn)分析

為了評價(jià)本文提出的SDSS服務(wù)發(fā)現(xiàn)方法的性能指標(biāo)，本文在OMNet++[14]工具中仿真Ad Hoc網(wǎng)絡(luò)來進(jìn)行實(shí)驗(yàn)分析，分別與CSDM(文獻(xiàn)[6]提出的服務(wù)發(fā)現(xiàn)方法)和SSD(文獻(xiàn)[10]提出的服務(wù)發(fā)現(xiàn)方法)進(jìn)行性能對比.仿真實(shí)驗(yàn)參數(shù)如表1所示.

表1 仿真實(shí)驗(yàn)參數(shù)Table 1 Simulation experimental parameters

在仿真實(shí)驗(yàn)中，Ad Hoc網(wǎng)絡(luò)中的服務(wù)請求節(jié)點(diǎn)或服務(wù)提供節(jié)點(diǎn)隨機(jī)選擇，分別仿真了服務(wù)發(fā)現(xiàn)的查準(zhǔn)率、時(shí)延、消息開銷與節(jié)點(diǎn)數(shù)量的關(guān)系.

圖2 服務(wù)發(fā)現(xiàn)的查準(zhǔn)率與節(jié)點(diǎn)數(shù)量的關(guān)系Fig.2 Precision ratio of service discovery vs．number of nodes

從圖2可以看出，在三種Ad Hoc網(wǎng)絡(luò)服務(wù)發(fā)現(xiàn)方法中，CSDM方法的查準(zhǔn)率不高，介于55%和63%之間，這是由于該方法依據(jù)關(guān)鍵詞的方式進(jìn)行服務(wù)發(fā)現(xiàn)，無法對查詢的服務(wù)進(jìn)行準(zhǔn)確表達(dá).同CSDM方法相比較，SSD方法的查準(zhǔn)率要高出31%左右，這是由于該方法依據(jù)語義推理來執(zhí)行服務(wù)發(fā)現(xiàn)過程，可以對請求者查詢的服務(wù)進(jìn)行準(zhǔn)確表達(dá).與前面兩種方法相比，SDSS方法的查準(zhǔn)率最高，原因是該方法在通過語義進(jìn)行功能匹配的基礎(chǔ)上，對滿足功能匹配獲得的候選服務(wù)集，又進(jìn)行了基于服務(wù)情景約束的服務(wù)篩選，從候選服務(wù)集中篩選掉了那些不滿足用戶服務(wù)情景約束的服務(wù)，在一定程度上提高了服務(wù)發(fā)現(xiàn)的查準(zhǔn)率.

圖3 時(shí)延與節(jié)點(diǎn)數(shù)量的關(guān)系Fig.3 Latency vs．number of nodes

從圖3可以看出，伴隨著Ad Hoc網(wǎng)絡(luò)中節(jié)點(diǎn)個數(shù)的逐漸增長，SDSS、CSDM和SSD三種服務(wù)發(fā)現(xiàn)方法的時(shí)延也相應(yīng)的不同程度增長，這是由于Ad Hoc網(wǎng)絡(luò)自身基于多跳的方式進(jìn)行消息傳遞，伴隨著Ad Hoc網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)目的增長，消息傳播在Ad Hoc網(wǎng)絡(luò)中需要經(jīng)歷的跳數(shù)也不同程度的增長，從而造成需要的時(shí)延也隨之增大.CSDM方法花費(fèi)的時(shí)延最小，這是由于該方法利用基于關(guān)鍵詞的匹配模式進(jìn)行服務(wù)發(fā)現(xiàn)，算法復(fù)雜度小，匹配效率最高.SSD方法的時(shí)延最大，這是由于該方法基于全部的服務(wù)信息(服務(wù)屬性、節(jié)點(diǎn)屬性和環(huán)境屬性)進(jìn)行基于語義的推理，算法較為復(fù)雜.SDSS方法的時(shí)延比SSD方法有所減少，這是由于該方法只對功能屬性進(jìn)行基于語義的服務(wù)匹配操作，在一定程度上提高了匹配效率.

從圖4可以看出，CSDM與SSD兩種方法的平均每秒消息數(shù)量這一指標(biāo)相差并不明顯.與CSDM、SSD兩種方法比較，SDSS方法的平均每秒消息數(shù)量最小，這是由于該方法在基于功能匹配的基礎(chǔ)上，利用節(jié)點(diǎn)的服務(wù)情景屬性，對候選服務(wù)集進(jìn)行了服務(wù)篩選，刪除了那些不滿足用戶服務(wù)情景的Ad Hoc網(wǎng)絡(luò)服務(wù)，從而降低了傳遞的消息數(shù)量.

圖4 消息數(shù)量與節(jié)點(diǎn)數(shù)量的關(guān)系Fig.4 Number of messages vs．number of nodes

4 結(jié) 語

在Ad Hoc網(wǎng)絡(luò)環(huán)境下，針對具有相同功能的服務(wù)，對用戶而言，它們在服務(wù)情景上的表現(xiàn)可能存在一定差異，而只有當(dāng)服務(wù)能夠滿足用戶在這些方面的要求時(shí)，用戶才會考慮該服務(wù)所具有的功能.本文提出一種基于服務(wù)情景的Ad Hoc網(wǎng)絡(luò)服務(wù)發(fā)現(xiàn)方法，該方法不僅使得Ad Hoc網(wǎng)絡(luò)服務(wù)發(fā)現(xiàn)的查準(zhǔn)率得到一定程度提高，服務(wù)發(fā)現(xiàn)的質(zhì)量也得到了有效改善.