一種多興趣聚類的p2p網(wǎng)絡(luò)模型

一種多興趣聚類的p2p網(wǎng)絡(luò)模型

0基于多興趣聚類的mikad搜索算法在p2p網(wǎng)絡(luò)中，每個(gè)節(jié)點(diǎn)都具有相同的狀態(tài)，并且可以交換信息。Freenet傳統(tǒng)的Kademlia針對(duì)上述方案的不足,本文提出一種基于多興趣聚類的搜索方法MIKAD,使DHT和興趣聚類相結(jié)合,將具有相同或相似興趣的節(jié)點(diǎn)聚類到一起來改善查詢效率,特別考慮了節(jié)點(diǎn)的多個(gè)興趣。該模型與傳統(tǒng)Kademlia模型相比有更高的檢索效率和更小的路由延遲,相比較其他聚類模型有較好的實(shí)用性和擴(kuò)展性,為有組織的P2P系統(tǒng)提供了一種高效的數(shù)據(jù)查詢方法。1距離的計(jì)算Kademlia是一種典型的結(jié)構(gòu)化P2P網(wǎng)絡(luò)模型,其有較好的可擴(kuò)展性、容錯(cuò)性和完全自組等特點(diǎn)。它在樹狀空間上利用DHT來實(shí)現(xiàn)定位,使用異或(XOR)算法度量?jī)蓚€(gè)節(jié)點(diǎn)之間的距離,這樣就將網(wǎng)絡(luò)中所有的節(jié)點(diǎn)全部處理成一棵二叉樹的葉子。MIKAD是由Kademlia模型改進(jìn)而來,其在原有的結(jié)構(gòu)化網(wǎng)絡(luò)基礎(chǔ)上再疊加一層虛擬二叉樹結(jié)構(gòu),每個(gè)興趣聚類都是這棵虛擬二叉樹的葉子節(jié)點(diǎn)且其ID的最短前綴確定了聚類的位置,并且網(wǎng)絡(luò)中的距離也是通過異或運(yùn)算來計(jì)算。MIKAD假設(shè)每個(gè)普通節(jié)點(diǎn)都有一個(gè)或多個(gè)子興趣,節(jié)點(diǎn)將自身的文件信息通過聚類算法分割成多個(gè)子興趣,然后通過DHT將每個(gè)子興趣關(guān)鍵詞hash為一個(gè)160bit的ID值,這個(gè)關(guān)鍵詞ID與相關(guān)興趣聚類的ID相同,代表了聚類內(nèi)部與該興趣相關(guān)的所有文件信息。擁有同樣子興趣的節(jié)點(diǎn)都會(huì)被hash到同一個(gè)興趣聚類中。興趣聚類通過超級(jí)節(jié)點(diǎn)的方式組織,每一個(gè)興趣聚類中可能有多個(gè)超級(jí)節(jié)點(diǎn),超級(jí)節(jié)點(diǎn)維護(hù)著除了與普通節(jié)點(diǎn)相同路由表外,還需要存儲(chǔ)本興趣域內(nèi)節(jié)點(diǎn)的文件索引和其他超級(jí)節(jié)點(diǎn)的路由信息。此時(shí)網(wǎng)絡(luò)中就存在兩個(gè)不同的虛擬網(wǎng)絡(luò)結(jié)構(gòu):興趣聚類組成的虛擬二叉樹結(jié)構(gòu)和普通節(jié)點(diǎn)組成的Kademlia網(wǎng)絡(luò)結(jié)構(gòu)。由于節(jié)點(diǎn)子興趣的不斷變化,在不同時(shí)刻不同興趣域內(nèi)節(jié)點(diǎn)數(shù)量也是動(dòng)態(tài)變化的,興趣聚類的數(shù)量也一直在更新。網(wǎng)絡(luò)中數(shù)據(jù)存儲(chǔ)在每個(gè)節(jié)點(diǎn)中,每個(gè)超級(jí)節(jié)點(diǎn)索引本興趣聚類中的相關(guān)文件信息,所以想要檢索內(nèi)容必須先確定查詢內(nèi)容的興趣值,然后查看自身是否加入這一興趣聚類。如果加入則直接找到這一興趣域內(nèi)的超級(jí)節(jié)點(diǎn)并向其發(fā)送查詢請(qǐng)求,超級(jí)節(jié)點(diǎn)查詢自身索引內(nèi)容然后返回查詢結(jié)果;如果節(jié)點(diǎn)沒有加入對(duì)應(yīng)興趣聚類,那么通過異或(XOR)運(yùn)算計(jì)算出與目標(biāo)興趣ID距離最近的已連接超級(jí)節(jié)點(diǎn)S,通過S找到目的興趣聚類,再向其超級(jí)節(jié)點(diǎn)查詢。如果超級(jí)節(jié)點(diǎn)索引了需要的內(nèi)容則直接返回。下面將分別對(duì)節(jié)點(diǎn)狀態(tài)、路由算法、節(jié)點(diǎn)的加入、節(jié)點(diǎn)信息的更新、超級(jí)節(jié)點(diǎn)的選擇和節(jié)點(diǎn)的離開進(jìn)行描述。1.1節(jié)點(diǎn)狀態(tài)節(jié)點(diǎn)度增加時(shí),節(jié)點(diǎn)對(duì)興趣表的索引MIKAD中依舊使用每個(gè)節(jié)點(diǎn)興趣表只在興趣聚類中查詢時(shí)使用。為控制節(jié)點(diǎn)興趣表的大小以及興趣增多引起的節(jié)點(diǎn)度的增加,興趣表只索引了有興趣的(即與子興趣ID相關(guān)的)文件。其中,序號(hào)表示節(jié)點(diǎn)子興趣重要程度的排序,即更感興趣的類別會(huì)排在上面;子興趣ID表示節(jié)點(diǎn)通過聚類算法計(jì)算出的子興趣經(jīng)過hash之后得到的160bit的值,相關(guān)文件即是節(jié)點(diǎn)內(nèi)存儲(chǔ)的對(duì)應(yīng)子興趣的文件集。超級(jí)節(jié)點(diǎn)除rpc接收算法MIKAD包括五種遠(yuǎn)程過程調(diào)用(remoteprocedurecall,RPC):PING、STORE、FING_SNODE、FIND_VALUE和QUIT如表3所示。為了防止地址偽造,接收RPC操作的節(jié)點(diǎn)都需要響應(yīng)一個(gè)隨機(jī)的160bit的RPCID。除此之外,為了確定源節(jié)點(diǎn)的網(wǎng)絡(luò)地址,在回復(fù)RPC消息時(shí)接收節(jié)點(diǎn)還可以附帶一個(gè)PING操作。1.2路由機(jī)制的詳細(xì)設(shè)計(jì)MIKAD網(wǎng)絡(luò)中的路由就是源節(jié)點(diǎn)到一棵虛擬二叉樹中的目標(biāo)興趣聚類的路由和普通的節(jié)點(diǎn)之間的路由之和。由于興趣聚類中使用超級(jí)節(jié)點(diǎn)進(jìn)行組織,如果假設(shè)網(wǎng)絡(luò)狀態(tài)理想,那么單個(gè)節(jié)點(diǎn)的一個(gè)查詢請(qǐng)求最多會(huì)在兩跳內(nèi)返回結(jié)果。MIKAD網(wǎng)絡(luò)擁有兩個(gè)不同的虛擬結(jié)構(gòu),所以路由機(jī)制也在這兩個(gè)虛擬結(jié)構(gòu)中進(jìn)行,下面是路由算法的詳細(xì)過程:a)當(dāng)節(jié)點(diǎn)有查詢請(qǐng)求時(shí),首先通過SHA-1算法計(jì)算出需要查詢信息的興趣ID,選擇相應(yīng)興趣聚類的超級(jí)節(jié)點(diǎn)發(fā)送查詢消息。若節(jié)點(diǎn)已經(jīng)加入對(duì)應(yīng)興趣域,則直接將查詢消息發(fā)給已知的對(duì)應(yīng)超級(jí)節(jié)點(diǎn);否則將興趣ID與已知所有興趣聚類ID值進(jìn)行異或(XOR)運(yùn)算,計(jì)算出與目標(biāo)聚類距離最近的已連接超級(jí)節(jié)點(diǎn)SNODE并向其發(fā)送FIND_SNODE消息;SNODE接收到消息后返回已知匹配的或最近超級(jí)節(jié)點(diǎn)信息。重復(fù)這一過程直到找到對(duì)應(yīng)超級(jí)節(jié)點(diǎn)或TTL=0。b)超級(jí)節(jié)點(diǎn)收到查詢消息后查詢索引表,將索引表中匹配內(nèi)容返回給源節(jié)點(diǎn),源節(jié)點(diǎn)通過返回信息得到目標(biāo)節(jié)點(diǎn),查詢結(jié)束。路由過程的偽代碼如下:圖1為MIKAD中一個(gè)節(jié)點(diǎn)查詢數(shù)據(jù)的過程。1.3網(wǎng)絡(luò)興趣聚類的確定對(duì)于節(jié)點(diǎn)的文件中可能包含多個(gè)興趣類別的文件,此節(jié)點(diǎn)加入網(wǎng)絡(luò)時(shí)應(yīng)先對(duì)所有文件進(jìn)行聚類,從而發(fā)現(xiàn)節(jié)點(diǎn)的多個(gè)子興趣,并且通過文件變化對(duì)節(jié)點(diǎn)興趣集進(jìn)行動(dòng)態(tài)的更新、完善。新節(jié)點(diǎn)A加入網(wǎng)絡(luò)的過程是通過網(wǎng)絡(luò)中已存在的鄰居節(jié)點(diǎn)B完成的。A首先計(jì)算出自身子興趣,通過B連接的超級(jí)節(jié)點(diǎn)找到與自身各個(gè)子興趣對(duì)應(yīng)的興趣聚類,將自身子興趣對(duì)應(yīng)的文件信息發(fā)給每個(gè)聚類中的超級(jí)節(jié)點(diǎn)并互相更新路由表。具體過程如下:a)節(jié)點(diǎn)A通過對(duì)自身文件進(jìn)行聚類計(jì)算出本節(jié)點(diǎn)的b)超級(jí)節(jié)點(diǎn)S分析消息得到A節(jié)點(diǎn)的子興趣信息,將自身路由表中與A的子興趣ID吻合或距離最近的的超級(jí)節(jié)點(diǎn)S’的信息返回給A。c)若S’與子興趣ID不匹配,則重復(fù)步驟b);否則,A將自身子興趣文件信息發(fā)送給S’,S’索引A的文件信息,加入興趣聚類成功。若此時(shí)A加入的興趣聚類數(shù)等于K,則A成功加入網(wǎng)絡(luò);否則跳到步驟d)。d)A通過S節(jié)點(diǎn)返回的信息,向距離子興趣ID最近的超級(jí)節(jié)點(diǎn)發(fā)送FIND_SNODE消息,重復(fù)b)～c),直到加入的興趣聚類數(shù)等于K或TTL=0。若TTL=0,則認(rèn)為網(wǎng)絡(luò)中不存在子興趣對(duì)應(yīng)的興趣聚類:如果A不是其他聚類的超級(jí)節(jié)點(diǎn)并且該興趣有關(guān)文件數(shù)達(dá)到一定閾值時(shí),則自身成為該子興趣聚類的超級(jí)節(jié)點(diǎn),并同鄰居超級(jí)節(jié)點(diǎn)相互更新路由表;否則等待下一次更新自身興趣時(shí)重新加入聚類。為保證網(wǎng)絡(luò)服務(wù)質(zhì)量,限制每個(gè)超級(jí)節(jié)點(diǎn)能夠管理的普通節(jié)點(diǎn)數(shù)量,如果節(jié)點(diǎn)加入時(shí)該興趣聚類容量已滿,這時(shí)將會(huì)產(chǎn)生一個(gè)子聚類用來管理新加入的節(jié)點(diǎn),子聚類的超級(jí)節(jié)點(diǎn)通過父聚類選舉產(chǎn)生并由父超級(jí)節(jié)點(diǎn)統(tǒng)一管理;如果新節(jié)點(diǎn)在父聚類已滿時(shí)加入網(wǎng)絡(luò),那么父超級(jí)節(jié)點(diǎn)將子超級(jí)節(jié)點(diǎn)信息返回給新節(jié)點(diǎn),新節(jié)點(diǎn)通過步驟b)～d)繼續(xù)加入網(wǎng)絡(luò)。1.4加入網(wǎng)絡(luò)時(shí)的聚類更新為了保持節(jié)點(diǎn)路由信息有效,節(jié)點(diǎn)之間每隔一段時(shí)間將會(huì)互相更新路由信息,另外新節(jié)點(diǎn)的加入與節(jié)點(diǎn)的離開也會(huì)導(dǎo)致節(jié)點(diǎn)信息的更新。節(jié)點(diǎn)信息的更新分為節(jié)點(diǎn)興趣的更新和路由信息的更新。a)節(jié)點(diǎn)興趣的更新。文獻(xiàn)b)路由信息的更新。網(wǎng)絡(luò)中路由信息更新的情況如下:(a)節(jié)點(diǎn)P加入網(wǎng)絡(luò)或子興趣的變化可能引起節(jié)點(diǎn)興趣表的更新,向?qū)?yīng)超級(jí)節(jié)點(diǎn)發(fā)送加入或退出聚類的消息,對(duì)應(yīng)超級(jí)節(jié)點(diǎn)更新自身維護(hù)的聚類文件索引表。(b)若P加入網(wǎng)絡(luò)或子興趣的變化時(shí)對(duì)應(yīng)興趣聚類已滿,引起對(duì)應(yīng)聚類產(chǎn)生子聚類,相應(yīng)超級(jí)節(jié)點(diǎn)將新加入節(jié)點(diǎn)路由到子超級(jí)節(jié)點(diǎn)上,子超級(jí)節(jié)點(diǎn)更新聚類文件索引表,節(jié)點(diǎn)P更新自身興趣表。(c)P加入網(wǎng)絡(luò)時(shí)需要?jiǎng)?chuàng)建新的興趣聚類,創(chuàng)建聚類文件索引表并索引自身文件,向鄰居超級(jí)節(jié)點(diǎn)發(fā)送一個(gè)FIND_SNODE消息,然后根據(jù)接收到的信息來更新自身的路由表。(d)興趣聚類內(nèi)超級(jí)節(jié)點(diǎn)按照Kademlia規(guī)則與對(duì)等超級(jí)節(jié)點(diǎn)相互更新路由表。(e)當(dāng)某一聚類內(nèi)文件數(shù)量低于某個(gè)閾值時(shí),超級(jí)節(jié)點(diǎn)通知聚類內(nèi)所有節(jié)點(diǎn)更新興趣表,該聚類解散,超級(jí)節(jié)點(diǎn)轉(zhuǎn)變?yōu)槠胀ü?jié)點(diǎn)。一般說來,最穩(wěn)定的超級(jí)節(jié)點(diǎn)信息更有可能留在其他超級(jí)節(jié)點(diǎn)的路由表中。也就是說,節(jié)點(diǎn)更容易找到相對(duì)穩(wěn)定的興趣聚類,使興趣相關(guān)文件更容易被節(jié)點(diǎn)查詢到,這樣可以在保持系統(tǒng)穩(wěn)定性的同時(shí)減少節(jié)點(diǎn)的路由維護(hù)代價(jià)。為防止路由表老化,若要所有路由表在一定時(shí)間內(nèi)無更新操作,節(jié)點(diǎn)會(huì)分別從路由表中選擇一些路由表項(xiàng)發(fā)送PING消息,根據(jù)返回消息更新路由表。此外,節(jié)點(diǎn)還會(huì)利用流經(jīng)自己的查詢消息來維護(hù)自身路由信息。1.5信譽(yù)度高的節(jié)點(diǎn)為避免惡意節(jié)點(diǎn)成為超級(jí)節(jié)點(diǎn),提高網(wǎng)絡(luò)整體可用性,在節(jié)點(diǎn)能力相同的情況下信譽(yù)度高的節(jié)點(diǎn)將優(yōu)先成為興趣聚類的超級(jí)節(jié)點(diǎn)。MIKAD使用EigenTrust(1)其中:當(dāng)系統(tǒng)不斷擴(kuò)展時(shí),超級(jí)節(jié)點(diǎn)的處理能力、穩(wěn)定性和信譽(yù)都會(huì)不斷地提升,系統(tǒng)也會(huì)更趨于穩(wěn)定。1.6該節(jié)點(diǎn)的文件信息標(biāo)記普通節(jié)點(diǎn)離開網(wǎng)絡(luò)時(shí)需要向其連接的每個(gè)超級(jí)節(jié)點(diǎn)發(fā)送QUIT消息。超級(jí)節(jié)點(diǎn)收到消息后返回一個(gè)PING消息,確認(rèn)節(jié)點(diǎn)離開網(wǎng)絡(luò)后在索引表中將該節(jié)點(diǎn)文件信息標(biāo)記為不可用。一般地,每個(gè)興趣聚類都會(huì)在內(nèi)部節(jié)點(diǎn)數(shù)量達(dá)到一定規(guī)模時(shí)產(chǎn)生一個(gè)或多個(gè)備用超級(jí)節(jié)點(diǎn)。備用超級(jí)節(jié)點(diǎn)與超級(jí)節(jié)點(diǎn)擁有同樣的路由表和索引表,這樣超級(jí)節(jié)點(diǎn)離開網(wǎng)絡(luò)時(shí)啟用備用超級(jí)節(jié)點(diǎn),備用超級(jí)節(jié)點(diǎn)通知聚類內(nèi)節(jié)點(diǎn)修改興趣表,然后通知鄰居超級(jí)節(jié)點(diǎn)更新其路由表并向其發(fā)送一個(gè)FIND_SNODE消息,然后根據(jù)接收到的信息來更新自身的路由表。2節(jié)點(diǎn)數(shù)目對(duì)網(wǎng)絡(luò)延遲的影響MIKAD是一種具有強(qiáng)移植性的網(wǎng)絡(luò)結(jié)構(gòu)模型,它可以將虛擬興趣聚類空間移植到大多數(shù)P2P網(wǎng)絡(luò)中,以實(shí)現(xiàn)良好的路由效率。根據(jù)本模型的特點(diǎn),基于PeerSim為分析興趣聚類數(shù)目對(duì)網(wǎng)絡(luò)中消息數(shù)量的影響,設(shè)置1000個(gè)節(jié)點(diǎn)并不斷增加網(wǎng)絡(luò)中的聚類數(shù)目,設(shè)置最多150個(gè)興趣聚類,每個(gè)節(jié)點(diǎn)最少2個(gè)、最多4個(gè)興趣,仿真結(jié)果如圖2所示?？梢钥闯?在MIKAD中消息數(shù)量會(huì)隨著聚類數(shù)目的增加而增加。為比較MIKAD和Kademlia的路由效率,分別模擬了1000個(gè)節(jié)點(diǎn)在兩種網(wǎng)絡(luò)中的平均路由延遲和平均路由跳數(shù)。圖3比較了MIKAD和Kademlia中的平均路由延遲。這里的平均路由延遲是經(jīng)過三次查詢后取得的延遲數(shù)平均值?？梢钥闯?隨著網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)目的增加,網(wǎng)絡(luò)中的平均路由延遲不斷增加,MIKAD中延遲增長(zhǎng)不明顯,與Kademlia相比有較短的路由延遲。從圖4可以看出,MIKAD相比Kademlia有較好