張倩 齊德昱

(華南理工大學(xué)計(jì)算機(jī)系統(tǒng)研究所，廣東廣州510006)

云制造的目標(biāo)之一是實(shí)現(xiàn)制造資源的全面共享，其中制造資源服務(wù)的組織與發(fā)現(xiàn)是獲得共享制造資源的關(guān)鍵．制造資源服務(wù)的分布性、自治性和動(dòng)態(tài)性等特點(diǎn)，以及云制造資源服務(wù)用戶(hù)請(qǐng)求的異構(gòu)性和復(fù)雜性，使得云制造模式下的資源服務(wù)組織與發(fā)現(xiàn)面臨著挑戰(zhàn)．

已有的資源服務(wù)發(fā)現(xiàn)系統(tǒng)大多采用集中式、層次式、對(duì)等式(P2P)以及混合式等機(jī)制對(duì)資源服務(wù)進(jìn)行組織，并設(shè)計(jì)相應(yīng)的資源服務(wù)發(fā)現(xiàn)算法．但這些算法主要研究網(wǎng)格模式下計(jì)算資源、文件資源、制造資源的發(fā)現(xiàn)機(jī)制，因此只能起到一定的借鑒作用，不能完全照搬遷移到云制造資源服務(wù)的組織與發(fā)現(xiàn)中．至今已有許多學(xué)者針對(duì)云制造模式下制造資源服務(wù)的組織與發(fā)現(xiàn)機(jī)制進(jìn)行了研究．文獻(xiàn)［1］中提出了一種基于分布式哈希表(DHT)的自組織云制造資源聚集方法，并設(shè)計(jì)了基于四叉樹(shù)的多維屬性區(qū)間搜索方法;文獻(xiàn)［2］中提出了基于語(yǔ)義Web和本體知識(shí)的制造資源發(fā)現(xiàn)框架，該框架構(gòu)建在集中式的統(tǒng)一描述、發(fā)現(xiàn)和集成協(xié)議(UDDI)注冊(cè)中心之上;文獻(xiàn)［3］中提出了一種智能化的云制造服務(wù)搜索與匹配方法，通過(guò)分級(jí)匹配策略來(lái)實(shí)現(xiàn)云制造服務(wù)的高效精確匹配;文獻(xiàn)［4］中提出了基于資源云服務(wù)(RVCS)的云制造資源封裝、發(fā)布和發(fā)現(xiàn)模型;文獻(xiàn)［5］中提出了云制造服務(wù)語(yǔ)義匹配模型，通過(guò)參數(shù)匹配、屬性匹配、綜合匹配和量化匹配程度來(lái)實(shí)現(xiàn)云制造服務(wù)的智能匹配;文獻(xiàn)［6］中將云制造資源服務(wù)匹配看作是一個(gè)復(fù)雜的多屬性決策優(yōu)化過(guò)程，提出了基于模糊積分的云制造資源服務(wù)匹配方法．然而，這些研究大多從服務(wù)發(fā)現(xiàn)角度進(jìn)行研究，較少考慮到制造資源服務(wù)的組織方式;除文獻(xiàn)［1］外，其他研究不支持制造資源服務(wù)屬性值的范圍查詢(xún)．

考慮到云制造資源服務(wù)的分布性、自治性和動(dòng)態(tài)性等特點(diǎn)，基于P2P的資源服務(wù)組織與發(fā)現(xiàn)機(jī)制是一種較為理想的解決方案．作為一種實(shí)現(xiàn)P2P的結(jié)構(gòu)，DHT技術(shù)得到了廣泛的研究與應(yīng)用．但目前基于DHT的資源服務(wù)發(fā)現(xiàn)中，基于關(guān)鍵字的精確匹配的研究居多，而云制造需要基于制造資源服務(wù)的屬性值進(jìn)行查找．為有效地組織云制造資源服務(wù)和支持復(fù)雜的用戶(hù)搜索，文中從制造資源服務(wù)的注冊(cè)與部署角度出發(fā)，提出了基于DHT和分層的資源服務(wù)組織模型，并設(shè)計(jì)了支持5種查詢(xún)方式的云制造資源服務(wù)發(fā)現(xiàn)算法．

1 基于DHT和分層的資源服務(wù)組織模型

1．1 相關(guān)定義

定義1 制造資源服務(wù)(MRS)是指已經(jīng)虛擬化封裝為服務(wù)，并注冊(cè)和發(fā)布到云制造服務(wù)平臺(tái)的邏輯制造資源．根據(jù)部署方式的不同，制造資源服務(wù)可分為托管型和本地型兩類(lèi)．

定義2 托管型制造資源服務(wù)(T-MRS)是指資源提供方發(fā)布的資源將部署到云制造服務(wù)平臺(tái)管理的服務(wù)器中，并提供服務(wù)器IP地址和一定的帶寬給資源提供方，資源提供方只需采用遠(yuǎn)程管理方式對(duì)制造資源服務(wù)進(jìn)行維護(hù)．

定義3 本地型制造資源服務(wù)(L-MRS)是指制造資源服務(wù)仍部署在資源提供方本地的服務(wù)器中，云制造服務(wù)平臺(tái)只需建立該資源服務(wù)的索引．

定義4 服務(wù)部署節(jié)點(diǎn)(SDN)是指T-MRS的宿主節(jié)點(diǎn)．

定義5 服務(wù)注冊(cè)節(jié)點(diǎn)(SRN)是指制造資源發(fā)布和查詢(xún)的入口，主要職能包括:管理多個(gè)SDN、實(shí)現(xiàn)MRS的注冊(cè)和檢索、與其他SRN進(jìn)行通信．

定義6 自治域(AD)是指由一個(gè)SRN和多個(gè)SDN構(gòu)成的自治管理的制造資源服務(wù)域．

1．2 云制造資源服務(wù)組織模型

圖1 基于DHT和分層的云制造資源服務(wù)組織模型Fig．1 Organization model of cloud manufacture resource services based on DHT and layered structure

如圖1所示，文中提出的分布式云制造資源服務(wù)組織模型采用分層的管理方式，邏輯上分為3層．下層是資源服務(wù)層，由各種T-MRS組成．中間層由若干AD組成，L-MRS只需在SRN中登記其索引信息．每個(gè)自治域可根據(jù)處理能力和可用性指標(biāo)選出SRN，同時(shí)選出備份節(jié)點(diǎn)，隨時(shí)監(jiān)控SRN并保存其運(yùn)行日志，一旦SRN失效，便切換到備份節(jié)點(diǎn)并依次運(yùn)行日志來(lái)同步數(shù)據(jù)，同時(shí)選出新的備份節(jié)點(diǎn)．上層為由負(fù)責(zé)MRS注冊(cè)的SRN組成的基于DHT的覆蓋網(wǎng)，可采用比較成熟的 Chord［7］、Pastry［8］、CAN［9］或Tapestry［10］等DHT協(xié)議，文中采用Chord協(xié)議．

1．3 云制造資源服務(wù)的組織結(jié)構(gòu)形成機(jī)制

為便于進(jìn)行范圍查詢(xún)和多屬性查詢(xún)，需要一個(gè)自治域中能盡量存儲(chǔ)屬性相似的資源服務(wù)．利用基于局部性敏感的哈希(LSH)函數(shù)［11-12］能將相似的資源服務(wù)映射到標(biāo)識(shí)相同或相近的節(jié)點(diǎn)上．如圖2所示，節(jié)點(diǎn)和資源服務(wù)均被映射到一個(gè)大小為2l的環(huán)狀標(biāo)識(shí)空間(文中取l=160)，利用哈希函數(shù)(如SHA-1［13］)將SRN的IP地址和端口號(hào)映射到標(biāo)識(shí)空間，這樣，每個(gè)SRN將管理與他相鄰的前一個(gè)節(jié)點(diǎn)之間的區(qū)間．MRS的關(guān)鍵屬性(將在1．3．2節(jié)中詳細(xì)介紹)經(jīng)過(guò)LSH函數(shù)(如Simhash［12］)映射到同一標(biāo)識(shí)空間．根據(jù)LSH的特性，相似的MRS將以高概率映射到相同的SRN中．文中采用Chord協(xié)議來(lái)實(shí)現(xiàn)這種映射關(guān)系，資源服務(wù)標(biāo)識(shí)i將被映射到沿Chord環(huán)順時(shí)針?lè)较蛩业降牡谝粋€(gè)節(jié)點(diǎn)，即節(jié)點(diǎn)標(biāo)識(shí)大于等于i的第一個(gè)節(jié)點(diǎn)上．

圖2 DHT的結(jié)構(gòu)Fig．2 Structure of DHT

1．3．1 節(jié)點(diǎn)的加入和離開(kāi)

基于DHT的覆蓋網(wǎng)的建立和維護(hù)是一個(gè)動(dòng)態(tài)的過(guò)程，節(jié)點(diǎn)可以隨時(shí)加入和退出．節(jié)點(diǎn)的加入包括SRN的加入和SDN的加入．其中，SRN的加入算法可利用Chord協(xié)議中的節(jié)點(diǎn)加入算法，這里不再闡述．當(dāng)SDN加入時(shí)，可向與之最近的SRN發(fā)送加入其自治域的申請(qǐng)信息，SRN確認(rèn)接收后，與之建立連接，并更新其SDN管理表．

SDN的離開(kāi)分為正常退出和異常退出兩種情況:①當(dāng)SDN正常退出時(shí)，只需更新其域內(nèi)SRN中的SDN管理表和MRS索引表，并將其內(nèi)部署的資源服務(wù)進(jìn)行重新注冊(cè)．此過(guò)程不會(huì)影響域內(nèi)SRN的路由表中的信息，可有效降低節(jié)點(diǎn)頻繁離開(kāi)覆蓋網(wǎng)所引起的波動(dòng)．②當(dāng)SDN異常退出時(shí)，SRN通過(guò)周期的SDN狀態(tài)監(jiān)測(cè)進(jìn)程可截獲此異常，從而進(jìn)行信息更新．

每個(gè)自治域的SRN起著極其重要的作用，既要負(fù)責(zé)覆蓋網(wǎng)的拓?fù)渚S護(hù)和各種信息的路由，又要負(fù)責(zé)SDN的管理，以及資源服務(wù)的注冊(cè)和查找工作．同樣，SRN的離開(kāi)也分為正常退出和異常退出兩種情況．當(dāng)SRN正常退出時(shí)，將SRN管理的自治域內(nèi)的SDN及其內(nèi)部署的資源服務(wù)一起遷移到SRN的后繼節(jié)點(diǎn)中，更新后繼節(jié)點(diǎn)的SDN管理表和MRS索引表，并調(diào)用Chord協(xié)議中的節(jié)點(diǎn)退出算法修改SRN的前驅(qū)和后繼節(jié)點(diǎn)中的信息．SRN的備份節(jié)點(diǎn)實(shí)時(shí)監(jiān)控SRN并保存其運(yùn)行日志，一旦檢測(cè)到SRN失效，便可切換到備份節(jié)點(diǎn)并依次運(yùn)行日志來(lái)同步數(shù)據(jù)，同時(shí)選出新的備份節(jié)點(diǎn)，這樣可將SRN的失效影響限制在本AD內(nèi)，同時(shí)維持覆蓋網(wǎng)的拓?fù)浣Y(jié)構(gòu)．

1．3．2 資源服務(wù)的維護(hù)

文中采用基于屬性的方法對(duì)MRS進(jìn)行描述，每個(gè)屬性用一組〈屬性名稱(chēng)，屬性值〉來(lái)描述．以模具加工外協(xié)服務(wù)為例［1］，該服務(wù)可描述為屬性集合C:{Service Name=模具加工，Service Quality=98%，Dimensional Precision=1T6，Surface Roughness=Ra 0．2μm，Service Duration=3 個(gè)月，… }．如果將資源服務(wù)的每個(gè)屬性分別進(jìn)行注冊(cè)，當(dāng)屬性的數(shù)量較多時(shí)，資源服務(wù)的索引維護(hù)開(kāi)銷(xiāo)將很大．制造資源服務(wù)一般具有多個(gè)屬性，而用戶(hù)往往只對(duì)其中的一小部分屬性感興趣，文中將用戶(hù)感興趣且最能代表制造資源服務(wù)能力的屬性作為關(guān)鍵屬性．如可選擇資源服務(wù)的名稱(chēng)、服務(wù)質(zhì)量、尺寸精度和表面粗糙度作為模具加工外協(xié)資源服務(wù)的關(guān)鍵屬性．實(shí)際中制造資源服務(wù)的關(guān)鍵屬性及其個(gè)數(shù)m可以根據(jù)資源服務(wù)類(lèi)型靈活定義．任何制造資源服務(wù)均可以動(dòng)態(tài)地加入和退出，故其維護(hù)包括資源服務(wù)的注冊(cè)和退出過(guò)程．

(1)資源服務(wù)的注冊(cè)．根據(jù)資源服務(wù)部署方式的不同，資源服務(wù)注冊(cè)可分為T(mén)-MRS注冊(cè)和L-MRS注冊(cè)．假設(shè)選定的資源服務(wù)關(guān)鍵屬性為 key［］={key1，key2，…，keym}，文中分別給出這兩種情況下的資源服務(wù)注冊(cè)算法．T-MRS注冊(cè)算法描述如下:

資源服務(wù)注冊(cè)算法的主要思想為:①每個(gè)資源服務(wù)將被注冊(cè)到m個(gè)目標(biāo)SRN中，即在m個(gè)SRN中建立該資源服務(wù)的索引;②資源服務(wù)實(shí)際上至多被部署到K個(gè)SDN中，且該SDN有足夠的能力(部署和運(yùn)行T-MRS所需的CPU、內(nèi)存、帶寬等)接受新資源服務(wù)的部署．

T-MRS注冊(cè)算法描述了當(dāng)資源服務(wù)在節(jié)點(diǎn)n發(fā)起注冊(cè)請(qǐng)求時(shí)，資源服務(wù)部署和建立索引的過(guò)程．L-MRS的注冊(cè)無(wú)需部署，只需在對(duì)應(yīng)的SRN中建立索引信息．基于T-MRS算法易得到支持L-MRS的注冊(cè)算法，這里不再贅述．

(2)資源服務(wù)的退出．當(dāng)T-MRS正常退出時(shí)，向其所在的SRN發(fā)送退出請(qǐng)求，SRN收到資源服務(wù)退出請(qǐng)求后，刪除此資源服務(wù)的索引信息及SDN中的部署信息，并通知其他存有此資源服務(wù)索引的SRN以及部署此資源服務(wù)的SDN進(jìn)行相應(yīng)地刪除．由于T-MRS被部署到k個(gè)不同的SDN中，因此，只有在副本均失效的情況下，資源服務(wù)才會(huì)變得不可用．

當(dāng)L-MRS正常退出時(shí)，只需刪除各關(guān)鍵屬性對(duì)應(yīng)SRN中的該資源服務(wù)的索引信息．若m個(gè)資源服務(wù)的索引均失效，則將無(wú)法訪(fǎng)問(wèn)該資源服務(wù)．

2 云制造資源服務(wù)發(fā)現(xiàn)算法與分析

2．1 資源服務(wù)發(fā)現(xiàn)算法

從查詢(xún)請(qǐng)求中屬性的個(gè)數(shù)和查詢(xún)條件的范圍來(lái)看，資源服務(wù)發(fā)現(xiàn)可分為5類(lèi):①單屬性單值查詢(xún)(s1)，如“Service Name=模具加工”;②多屬性單值查詢(xún)(s2)，如“Service Name=模具加工and Service Quality=98%”;③單屬性范圍查詢(xún)(s3)，如“Service Quality＞98%”;④多屬性范圍查詢(xún)(s4)，如“Service Quality＞98%and Surface Roughness ＜Ra 0．2μm”;⑤Top-k查詢(xún)(s5)，如“滿(mǎn)足Service Name=模具加工and Surface Roughness＜Ra 0．2μm的k個(gè)資源”．

文中僅給出s4查詢(xún)算法，其他4種查詢(xún)算法可根據(jù)s4查詢(xún)算法修改得到，此處不再贅述．s4查詢(xún)

算法描述如下:

在s4查詢(xún)算法中，搜索范圍被劃分為多個(gè)連續(xù)整數(shù)值，對(duì)每個(gè)單值進(jìn)行基于DHT的查找定位，多個(gè)單值查詢(xún)結(jié)果的匯總即為滿(mǎn)足范圍查詢(xún)條件的資源服務(wù)．Top-k查詢(xún)算法只需在查詢(xún)節(jié)點(diǎn)按照某種優(yōu)化選擇算法對(duì)匯集的查詢(xún)結(jié)果進(jìn)行排序，進(jìn)而獲得最優(yōu)的前k個(gè)資源服務(wù)．此外，每個(gè)SRN維護(hù)一個(gè)緩存以保存由此節(jié)點(diǎn)產(chǎn)生的查詢(xún)結(jié)果，可提高檢索效率．緩存的容量有限，其內(nèi)運(yùn)行LRU替換算法．資源服務(wù)的動(dòng)態(tài)性可能導(dǎo)致緩存內(nèi)容與實(shí)際的資源服務(wù)索引信息不一致，為避免向用戶(hù)提供不可用的資源服務(wù)，需要周期性地檢測(cè)緩存中的內(nèi)容是否可用，當(dāng)資源服務(wù)退出時(shí)，應(yīng)及時(shí)刪除緩存中對(duì)應(yīng)的項(xiàng)．

2．2 算法分析

文中采用搜索延遲和消息開(kāi)銷(xiāo)兩個(gè)指標(biāo)對(duì)資源服務(wù)發(fā)現(xiàn)算法的性能進(jìn)行分析．搜索延遲是指查詢(xún)消息從發(fā)起節(jié)點(diǎn)到達(dá)目標(biāo)節(jié)點(diǎn)需要經(jīng)歷的跳數(shù);消息開(kāi)銷(xiāo)是指一個(gè)資源服務(wù)發(fā)現(xiàn)請(qǐng)求在覆蓋網(wǎng)中產(chǎn)生的搜索消息總數(shù)．

定理1 在N個(gè)SRN節(jié)點(diǎn)組成的覆蓋網(wǎng)中，資源服務(wù)發(fā)現(xiàn)算法的搜索延遲為O(log2N)．

證明 (1)s1算法的搜索延遲為DHT搜索延遲O(log2N)．

(2)文中多屬性單值搜索的思路是:若查詢(xún)q個(gè)關(guān)鍵屬性，則對(duì)每個(gè)關(guān)鍵屬性分別使用單值查詢(xún)算法進(jìn)行并行查找，最后將結(jié)果匯總．可見(jiàn)，s2算法的搜索延遲是q個(gè)單屬性單值搜索延遲中的最大值，為O(log2N)．

(3)在s3算法中，查詢(xún)范圍被劃分為t個(gè)連續(xù)整數(shù)值，可看成是t個(gè)單屬性單值的并行查詢(xún)．因此，s3算法的搜索延遲是t個(gè)單屬性單值搜索延遲中的最大值，即O(log2N)．

(4)s4算法是在多個(gè)單屬性中進(jìn)行單值范圍查詢(xún)，故s4算法的搜索延遲仍為O(log2N)．

(5)s5算法是在上述算法的基礎(chǔ)上再利用某種優(yōu)化算法進(jìn)行選取，因此其搜索延遲亦為O(log2N)．

綜上可得，文中提出的資源服務(wù)發(fā)現(xiàn)算法的搜索延遲為O(log2N)．證畢．

定理2 在N個(gè)SRN組成的覆蓋網(wǎng)中，資源服務(wù)發(fā)現(xiàn)算法s3的消息開(kāi)銷(xiāo)下界為 O(log2N)，上界為O(tlog2N)，其中t為搜索范圍的劃分粒度．

證明 根據(jù)定理1中的分析，s1算法的消息開(kāi)銷(xiāo)為DHT消息開(kāi)銷(xiāo)O(log2N)．s2算法的消息開(kāi)銷(xiāo)為q個(gè)單屬性單值查詢(xún)消息開(kāi)銷(xiāo)的總和，即O(qlog2N)．

在s3算法中，搜索范圍被劃分為t個(gè)連續(xù)整數(shù)值，根據(jù)局部哈希函數(shù)的性質(zhì)，這t個(gè)連續(xù)整數(shù)值將以高概率映射到同一個(gè)SRN節(jié)點(diǎn)上．在最好情況下，即t個(gè)連續(xù)整數(shù)值映射到同一個(gè)SRN節(jié)點(diǎn)上，則只需發(fā)送1條查詢(xún)請(qǐng)求即可檢索到該范圍內(nèi)的所有資源服務(wù)，等同于單屬性單值搜索，因此s3算法的消息開(kāi)銷(xiāo)下界為O(log2N);在最壞情況下，即t個(gè)連續(xù)整數(shù)值映射到t個(gè)不同的SRN節(jié)點(diǎn)上，則需發(fā)送t條不同的查詢(xún)請(qǐng)求才能檢索出所有滿(mǎn)足條件的資源服務(wù)，因此s3算法的消息開(kāi)銷(xiāo)上界為O(tlog2N)．證畢．

由定理1中的分析可知，s4算法是在多個(gè)單屬性中進(jìn)行單值范圍查詢(xún)，結(jié)合定理2，可得到s4算法的消息開(kāi)銷(xiāo)下界為O(qlog2N)，上界為O(qtlog2N)．

從以上分析可以看出，隨著q、t取值的增大，系統(tǒng)的存儲(chǔ)負(fù)擔(dān)和查詢(xún)消息開(kāi)銷(xiāo)有所增加．但在文中提出的云制造資源服務(wù)組織模型中，大部分發(fā)布的數(shù)據(jù)都是資源服務(wù)的索引，每個(gè)數(shù)據(jù)的信息只有幾千字節(jié)，因此不會(huì)給系統(tǒng)增加太多負(fù)擔(dān)．同時(shí)，雖然資源服務(wù)部署的信息較大，但資源服務(wù)副本的增多保證了資源服務(wù)的可用性和健壯性．在實(shí)際應(yīng)用中，可根據(jù)需要合理地設(shè)置q和t的取值．

文中提出的資源服務(wù)發(fā)現(xiàn)算法可以看成是由兩步完成:①定位到可能含有資源服務(wù)的SRN節(jié)點(diǎn);②基于關(guān)鍵詞的匹配．某個(gè)資源服務(wù)是否屬于集合M是在關(guān)鍵詞匹配時(shí)確定的．可見(jiàn)，第1步的定位機(jī)制對(duì)服務(wù)平臺(tái)查準(zhǔn)率不造成影響，第2步采用基于關(guān)鍵詞的精確匹配方法，因此，文中算法的查準(zhǔn)率為基于關(guān)鍵詞匹配的查準(zhǔn)率．

設(shè)搜索范圍的劃分粒度為t時(shí)，返回的制造資源服務(wù)集為M;搜索范圍的劃分粒度為t'(t'＞t)時(shí)，返回的制造資源服務(wù)集為M'．當(dāng)搜索范圍的劃分粒度為t時(shí)，對(duì)應(yīng)的關(guān)鍵詞較少，由查準(zhǔn)率分析可知，集合M也較小;當(dāng)搜索范圍的劃分粒度為t'時(shí)，劃分粒度細(xì)，關(guān)鍵詞較多，則增加了資源服務(wù)加入到集合M的概率，即增加了M'＞M的概率．由此可見(jiàn)，提高搜索范圍的劃分粒度，在一定程度上可提高資源服務(wù)發(fā)現(xiàn)算法的查全率．

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

仿真實(shí)驗(yàn)采用開(kāi)源 P2P模擬器 Peersim［14］，使用Chord協(xié)議構(gòu)建覆蓋網(wǎng)的拓?fù)浣Y(jié)構(gòu)，并以事件驅(qū)動(dòng)方式對(duì)文中提出的模型和算法進(jìn)行模擬實(shí)現(xiàn)及性能分析．為了簡(jiǎn)化問(wèn)題和便于仿真實(shí)現(xiàn)，文中忽略在一次資源服務(wù)搜索過(guò)程中SRN拓?fù)浣Y(jié)構(gòu)以及資源服務(wù)的變化．資源服務(wù)發(fā)現(xiàn)請(qǐng)求由系統(tǒng)隨機(jī)選擇一個(gè)SRN發(fā)起，實(shí)驗(yàn)結(jié)果為獨(dú)立重復(fù)1000次實(shí)驗(yàn)的平均測(cè)試結(jié)果．

3．1 搜索延遲分析

首先評(píng)估不同網(wǎng)絡(luò)規(guī)模下各種資源服務(wù)發(fā)現(xiàn)算法的搜索延遲．實(shí)驗(yàn)中SRN節(jié)點(diǎn)數(shù)N從1000增加到10000，每次增加1000個(gè)節(jié)點(diǎn);資源服務(wù)關(guān)鍵屬性個(gè)數(shù)q分別取值為1、2、10;搜索范圍為任意兩個(gè)相鄰節(jié)點(diǎn)之間的間隔，劃分粒度t=10．實(shí)驗(yàn)結(jié)果如圖3所示．

圖3 搜索延遲與SRN節(jié)點(diǎn)數(shù)的關(guān)系Fig．3 Search delay versus number of SRN

由圖3可以看出，平均搜索延遲隨著SRN節(jié)點(diǎn)數(shù)的增加大致呈對(duì)數(shù)級(jí)速度增長(zhǎng)．當(dāng)q=1時(shí)，平均搜索延遲小于，該結(jié)果與Chord算法的精確匹配查詢(xún)結(jié)果一致［7］．圖3表明，在多屬性查詢(xún)情況下，隨著資源服務(wù)的關(guān)鍵屬性個(gè)數(shù)的增多，算法的平均搜索延遲也在增加．這主要是因?yàn)槎鄬傩圆樵?xún)的搜索延遲是q個(gè)單屬性搜索延遲中的最大值，增加了高搜索延遲取值的概率，因此降低了算法的搜索效率．在關(guān)鍵屬性個(gè)數(shù)相同的查詢(xún)情況下，雖然單屬性范圍查詢(xún)的搜索延遲是t個(gè)單屬性單值搜索延遲中的最大值，但這t個(gè)單屬性單值搜索將以高概率映射到標(biāo)識(shí)相同或相近的SRN節(jié)點(diǎn)上，因此，關(guān)鍵屬性個(gè)數(shù)相同的單值查詢(xún)的平均搜索延遲與范圍查詢(xún)的平均搜索延遲大致相同(見(jiàn)圖3)．

接下來(lái)考察搜索延遲與搜索范圍的關(guān)系．實(shí)驗(yàn)中SRN節(jié)點(diǎn)數(shù)N=10000，假設(shè)所有節(jié)點(diǎn)標(biāo)識(shí)均勻分布在Chord環(huán)中，搜索范圍取任意兩個(gè)相鄰節(jié)點(diǎn)之間的間隔，其大小從50倍間隔變化到400倍;搜索范圍劃分粒度 t分別取值為 10、50、100、150、200．在不同的搜索范圍大小下，s3算法的平均搜索延遲見(jiàn)圖4．實(shí)驗(yàn)表明:①在搜索范圍一定的情況下，算法的平均搜索延遲隨t的增大而增加，直到t等于搜索范圍的大小時(shí)趨向平穩(wěn)．這主要是因?yàn)閠較小時(shí)，隨著t的增大，搜索請(qǐng)求映射到標(biāo)識(shí)不同SRN節(jié)點(diǎn)上的概率增加，即增加了高搜索延遲取值的概率;但當(dāng)t大于搜索范圍的大小時(shí)，搜索請(qǐng)求映射到標(biāo)識(shí)相同SRN節(jié)點(diǎn)上的概率增加，因此搜索延遲趨向平穩(wěn)．②在t一定的情況下，算法的平均搜索延遲隨搜索范圍的增大而增加，直到搜索范圍的大小等于t時(shí)趨向平穩(wěn)．這是因?yàn)閠值一定、搜索范圍較小時(shí)，搜索請(qǐng)求映射到標(biāo)識(shí)相同的SRN節(jié)點(diǎn)上的概率較大;但隨著搜索范圍的增大，搜索請(qǐng)求映射到標(biāo)識(shí)不同的SRN節(jié)點(diǎn)上的概率增加，因而增加了高搜索延遲取值的概率;在最壞情況下，搜索請(qǐng)求會(huì)映射到t個(gè)標(biāo)識(shí)不同的SRN節(jié)點(diǎn)上．因此，當(dāng)搜索范圍的大小大于t時(shí)，不會(huì)增加高搜索延遲取值的概率．

圖4 搜索延遲與搜索范圍的關(guān)系Fig．4 Search delay versus search range

3．2 消息開(kāi)銷(xiāo)分析

實(shí)驗(yàn)條件與3．1節(jié)中考察搜索延遲與搜索范圍關(guān)系的實(shí)驗(yàn)條件相同．單屬性范圍查詢(xún)s3算法的平均消息開(kāi)銷(xiāo)如圖5所示．由實(shí)驗(yàn)結(jié)果可以看出，當(dāng)搜索范圍一定時(shí)，算法的平均消息開(kāi)銷(xiāo)隨t的增大而增加，直到t等于搜索范圍的大小時(shí)趨向平穩(wěn);當(dāng)t一定時(shí)，算法的平均消息開(kāi)銷(xiāo)隨搜索范圍的增大而增加，直到搜索范圍的大小等于t時(shí)趨向平穩(wěn)．產(chǎn)生上述結(jié)果的原因分析與3．1節(jié)中搜索延遲與搜索范圍關(guān)系的實(shí)驗(yàn)分析類(lèi)似，這里不再贅述．由于多屬性范圍查詢(xún)算法是在多個(gè)單屬性中進(jìn)行單值范圍查詢(xún)的，因而其消息開(kāi)銷(xiāo)與單屬性范圍查詢(xún)算法的消息開(kāi)銷(xiāo)成正比，文中沒(méi)有對(duì)多屬性范圍查詢(xún)進(jìn)行比較．

圖5 消息開(kāi)銷(xiāo)與搜索范圍的關(guān)系Fig．5 Search message overhead versus search range

4 結(jié)語(yǔ)

云制造資源服務(wù)的組織與發(fā)現(xiàn)是實(shí)現(xiàn)制造資源共享的前提，具有重要的研究意義．文中提出了基于DHT和分層的云制造資源服務(wù)組織與發(fā)現(xiàn)機(jī)制，該機(jī)制將基于DHT的覆蓋網(wǎng)作為基本的拓?fù)浣Y(jié)構(gòu)，提供了一定的容錯(cuò)機(jī)制，支持常見(jiàn)的5種查詢(xún):單屬性單值查詢(xún)、多屬性單值查詢(xún)、單屬性范圍查詢(xún)、多屬性范圍查詢(xún)和Top-k查詢(xún)，有效地解決了分布式云制造資源服務(wù)的組織和搜索問(wèn)題．下一步將在公共云制造服務(wù)平臺(tái)系統(tǒng)的開(kāi)發(fā)中具體實(shí)現(xiàn)文中提出的算法，并逐步解決實(shí)際開(kāi)發(fā)中遇到的各種問(wèn)題，進(jìn)一步完善云制造資源服務(wù)組織與發(fā)現(xiàn)機(jī)制．

［1］劉士軍，曲本科，武蕾，等．自組織云制造資源聚集框架與多維屬性區(qū)間搜索方法研究［J］．計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2012，24(3):299-307．Liu Shi-jun，Qu Ben-ke，Wu Lei，et al．Self-organizing resource integration framework and multi-dimensional range search of cloud manufacturing ［J］．Journal of Computer-Aided Design ＆ Computer Graphics，2012，24(3):299-307．

［2］Wang Weixing，Liu Fei．The research of cloud manufacturing resource discovery mechanism［C］∥Proceedings of the 7th International Conference on Computer Science＆ Education．Melbourne:IEEE，2012:188-191．

［3］李慧芳，董訓(xùn)，宋長(zhǎng)剛．制造云服務(wù)智能搜索與匹配方法［J］．計(jì)算機(jī)集成制造系統(tǒng)，2012，18(7):1485-1493．Li Hui-fang，Dong Xun，Song Chang-gang．Intelligent searching and matching approach for cloud manufacturing service［J］．Computer Integrated Manufacturing Systems，2012，18(7):1485-1493．

［4］朱李楠，趙燕偉，王萬(wàn)良．基于RVCS的云制造資源封裝、發(fā)布和發(fā)現(xiàn)模型［J］．計(jì)算機(jī)集成制造系統(tǒng)，2012，18(8):1829-1838．Zhu Li-nan，Zhao Yan-wei，Wang Wan-liang．Model of resource package，publication and discovery based on RVCS in cloud manufacturing ［J］．Computer Integrated Manufacturing Systems，2012，18(8):1829-1838．

［5］尹超，夏卿，黎振武．基于OWL-S的云制造服務(wù)語(yǔ)義匹配方法［J］．計(jì)算機(jī)集成制造系統(tǒng)，2012，18(7):1494-1502．Yin Chao，Xia Qing，Li Zhen-wu．Semantic matching technique of cloud manufacturing service based on OWL-S［J］．Computer Integrated Manufacturing Systems，2012，18(7):1494-1502．

［6］高一聰，馮毅雄，譚建榮，等．制造資源耦合映射與模糊匹配技術(shù)研究［J］．計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2012，24(3):290-298．Gao Yi-cong，F(xiàn)eng Yi-xiong，Tan Jian-rong，et al．Research on coupled mapping and service matching technology of cloud manufacturing based on fuzzy integral［J］．Journal of Computer-Aided Design ＆ Computer Graphics，2012，24(3):290-298．

［7］Stoica I，Morris R，Karger D，et al．Chord:a scalable peerto-peer lookup service for Internet applications［C］∥Proceeding of the 2001 Conference on Applications，Technologies，Architectures，and Protocols for Computer Communications．New York:ACM，2001:149-160．

［8］Ratnasamy S，F(xiàn)rancis P，Handley M，et al．A scalable content-addressable network［C］∥Proceedings of the 2001 Conference on Applications，Technologies，Architectures，and Protocols for Computer Communications．New York:ACM，2001:161-172．

［9］Rowstron A I T，Druschel P．Pastry:scalable，decentralized object location，and routing for large-scale peer-topeer systems［C］∥Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms．London:Springer，2001:329-350．

［10］Zhao B Y，Huang L，Stribling J，et al．Tapestry:a resilient global-scale overlay for service deployment［J］．IEEE Journal on Selected Areas in Communications，2004，22(1):41-53．

［11］Indyk P，Motwani R．Approximate nearest neighbor:towards removing the curse of dimensionality［C］∥Proceedings of the 30th Annual ACM Symposium on Theory of Computing．New York:ACM，1998:604-613．

［12］Charikar M S．Similarity estimation techniques from rounding algorithms ［C］∥Proceedingsofthe 34th Annual ACM Symposium on Theory of Computing．New York:ACM，2002:380-388．

［13］Federal Information Processing Standards Publication 180-1，Secure hash standard ［S］．

［14］Jelasity M，Montresor A，Jesi G P，et al．The peersim simulator［CP/OL］．(2011-07-23)［2013-01-07］．http:∥peersim．sf．net．