張倩 齊德昱

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

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

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

考慮到云制造資源服務(wù)的分布性、自治性和動態(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ù)雜的用戶搜索，文中從制造資源服務(wù)的注冊與部署角度出發(fā)，提出了基于DHT和分層的資源服務(wù)組織模型，并設(shè)計(jì)了支持5種查詢方式的云制造資源服務(wù)發(fā)現(xiàn)算法．

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

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

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

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

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

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

定義5 服務(wù)注冊節(jié)點(diǎn)(SRN)是指制造資源發(fā)布和查詢的入口，主要職能包括:管理多個(gè)SDN、實(shí)現(xiàn)MRS的注冊和檢索、與其他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)行日志來同步數(shù)據(jù)，同時(shí)選出新的備份節(jié)點(diǎn)．上層為由負(fù)責(zé)MRS注冊的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)行范圍查詢和多屬性查詢，需要一個(gè)自治域中能盡量存儲屬性相似的資源服務(wù)．利用基于局部性敏感的哈希(LSH)函數(shù)［11-12］能將相似的資源服務(wù)映射到標(biāo)識相同或相近的節(jié)點(diǎn)上．如圖2所示，節(jié)點(diǎn)和資源服務(wù)均被映射到一個(gè)大小為2l的環(huán)狀標(biāo)識空間(文中取l=160)，利用哈希函數(shù)(如SHA-1［13］)將SRN的IP地址和端口號映射到標(biāo)識空間，這樣，每個(gè)SRN將管理與他相鄰的前一個(gè)節(jié)點(diǎn)之間的區(qū)間．MRS的關(guān)鍵屬性(將在1．3．2節(jié)中詳細(xì)介紹)經(jīng)過LSH函數(shù)(如Simhash［12］)映射到同一標(biāo)識空間．根據(jù)LSH的特性，相似的MRS將以高概率映射到相同的SRN中．文中采用Chord協(xié)議來實(shí)現(xiàn)這種映射關(guān)系，資源服務(wù)標(biāo)識i將被映射到沿Chord環(huán)順時(shí)針方向所找到的第一個(gè)節(jié)點(diǎn)，即節(jié)點(diǎn)標(biāo)識大于等于i的第一個(gè)節(jié)點(diǎn)上．

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

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

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

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

每個(gè)自治域的SRN起著極其重要的作用，既要負(fù)責(zé)覆蓋網(wǎng)的拓?fù)渚S護(hù)和各種信息的路由，又要負(fù)責(zé)SDN的管理，以及資源服務(wù)的注冊和查找工作．同樣，SRN的離開也分為正常退出和異常退出兩種情況．當(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)行日志，一旦檢測到SRN失效，便可切換到備份節(jié)點(diǎn)并依次運(yùn)行日志來同步數(shù)據(jù)，同時(shí)選出新的備份節(jié)點(diǎn)，這樣可將SRN的失效影響限制在本AD內(nèi)，同時(shí)維持覆蓋網(wǎng)的拓?fù)浣Y(jié)構(gòu)．

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

文中采用基于屬性的方法對MRS進(jìn)行描述，每個(gè)屬性用一組〈屬性名稱，屬性值〉來描述．以模具加工外協(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)行注冊，當(dāng)屬性的數(shù)量較多時(shí)，資源服務(wù)的索引維護(hù)開銷將很大．制造資源服務(wù)一般具有多個(gè)屬性，而用戶往往只對其中的一小部分屬性感興趣，文中將用戶感興趣且最能代表制造資源服務(wù)能力的屬性作為關(guān)鍵屬性．如可選擇資源服務(wù)的名稱、服務(wù)質(zhì)量、尺寸精度和表面粗糙度作為模具加工外協(xié)資源服務(wù)的關(guān)鍵屬性．實(shí)際中制造資源服務(wù)的關(guān)鍵屬性及其個(gè)數(shù)m可以根據(jù)資源服務(wù)類型靈活定義．任何制造資源服務(wù)均可以動態(tài)地加入和退出，故其維護(hù)包括資源服務(wù)的注冊和退出過程．

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

資源服務(wù)注冊算法的主要思想為:①每個(gè)資源服務(wù)將被注冊到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注冊算法描述了當(dāng)資源服務(wù)在節(jié)點(diǎn)n發(fā)起注冊請求時(shí)，資源服務(wù)部署和建立索引的過程．L-MRS的注冊無需部署，只需在對應(yīng)的SRN中建立索引信息．基于T-MRS算法易得到支持L-MRS的注冊算法，這里不再贅述．

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

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

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

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

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

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

算法描述如下:

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

2．2 算法分析

文中采用搜索延遲和消息開銷兩個(gè)指標(biāo)對資源服務(wù)發(fā)現(xiàn)算法的性能進(jìn)行分析．搜索延遲是指查詢消息從發(fā)起節(jié)點(diǎn)到達(dá)目標(biāo)節(jié)點(diǎn)需要經(jīng)歷的跳數(shù);消息開銷是指一個(gè)資源服務(wù)發(fā)現(xiàn)請求在覆蓋網(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)文中多屬性單值搜索的思路是:若查詢q個(gè)關(guān)鍵屬性，則對每個(gè)關(guān)鍵屬性分別使用單值查詢算法進(jìn)行并行查找，最后將結(jié)果匯總．可見，s2算法的搜索延遲是q個(gè)單屬性單值搜索延遲中的最大值，為O(log2N)．

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

(4)s4算法是在多個(gè)單屬性中進(jì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的消息開銷下界為 O(log2N)，上界為O(tlog2N)，其中t為搜索范圍的劃分粒度．

證明 根據(jù)定理1中的分析，s1算法的消息開銷為DHT消息開銷O(log2N)．s2算法的消息開銷為q個(gè)單屬性單值查詢消息開銷的總和，即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條查詢請求即可檢索到該范圍內(nèi)的所有資源服務(wù)，等同于單屬性單值搜索，因此s3算法的消息開銷下界為O(log2N);在最壞情況下，即t個(gè)連續(xù)整數(shù)值映射到t個(gè)不同的SRN節(jié)點(diǎn)上，則需發(fā)送t條不同的查詢請求才能檢索出所有滿足條件的資源服務(wù)，因此s3算法的消息開銷上界為O(tlog2N)．證畢．

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

從以上分析可以看出，隨著q、t取值的增大，系統(tǒng)的存儲負(fù)擔(dān)和查詢消息開銷有所增加．但在文中提出的云制造資源服務(wù)組織模型中，大部分發(fā)布的數(shù)據(jù)都是資源服務(wù)的索引，每個(gè)數(shù)據(jù)的信息只有幾千字節(jié)，因此不會給系統(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í)確定的．可見，第1步的定位機(jī)制對服務(wù)平臺查準(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í)，對應(yīng)的關(guān)鍵詞較少，由查準(zhǔn)率分析可知，集合M也較小;當(dāng)搜索范圍的劃分粒度為t'時(shí)，劃分粒度細(xì)，關(guān)鍵詞較多，則增加了資源服務(wù)加入到集合M的概率，即增加了M'＞M的概率．由此可見，提高搜索范圍的劃分粒度，在一定程度上可提高資源服務(wù)發(fā)現(xiàn)算法的查全率．

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

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

3．1 搜索延遲分析

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

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

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

3．2 消息開銷分析

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

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

4 結(jié)語

云制造資源服務(wù)的組織與發(fā)現(xiàn)是實(shí)現(xiàn)制造資源共享的前提，具有重要的研究意義．文中提出了基于DHT和分層的云制造資源服務(wù)組織與發(fā)現(xiàn)機(jī)制，該機(jī)制將基于DHT的覆蓋網(wǎng)作為基本的拓?fù)浣Y(jié)構(gòu)，提供了一定的容錯機(jī)制，支持常見的5種查詢:單屬性單值查詢、多屬性單值查詢、單屬性范圍查詢、多屬性范圍查詢和Top-k查詢，有效地解決了分布式云制造資源服務(wù)的組織和搜索問題．下一步將在公共云制造服務(wù)平臺系統(tǒng)的開發(fā)中具體實(shí)現(xiàn)文中提出的算法，并逐步解決實(shí)際開發(fā)中遇到的各種問題，進(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)，宋長剛．制造云服務(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］朱李楠，趙燕偉，王萬良．基于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ù)語義匹配方法［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．