[發(fā)明專利]基于de Bruijn圖的大規(guī)模網(wǎng)絡(luò)資源搜索方法

無效

• 申請?zhí)枺?/td>: 201010158376.7
• 申請日: 2010-04-28
• 公開（公告）號(hào): CN101854383A
• 公開（公告）日: 2010-10-06
• 發(fā)明（設(shè)計(jì)）人: 盧錫城;張一鳴;李東升
• 申請（專利權(quán)）人: 中國人民解放軍國防科學(xué)技術(shù)大學(xué)
• 主分類號(hào): H04L29/08
• 分類號(hào): H04L29/08;H04L12/24;G06F17/30
• 代理公司: 國防科技大學(xué)專利服務(wù)中心 43202
• 代理人: 郭敏

1.一種基于de?Bruijn圖的大規(guī)模網(wǎng)絡(luò)資源搜索方法，其特征在于包括以下步驟：

第一步，為資源對(duì)象命名：對(duì)每個(gè)結(jié)點(diǎn)和資源對(duì)象，采用MD5算法進(jìn)行命名；

第二步，采用de?Bruijn圖實(shí)現(xiàn)網(wǎng)絡(luò)拓?fù)洌翰捎靡还苫膁e?Bruijn圖定義：令GB(d，n)代表基為d和結(jié)點(diǎn)個(gè)數(shù)為n的一股化de?Bruijn圖，那么其點(diǎn)集V(GB(d，n))和邊集E(GB(d，n))分別為

V(GB(d，n))＝{0，1，L，n-1}，???????(1)

E(GB(d，n))＝{[i，(d×i+α)mod?n]|0≤α≤d-1}，?????(2)

一股化de?Bruijn圖的點(diǎn)對(duì)應(yīng)網(wǎng)絡(luò)拓?fù)渲械慕Y(jié)點(diǎn)，邊對(duì)應(yīng)網(wǎng)絡(luò)拓?fù)渲械慕Y(jié)點(diǎn)間連接，即得到相應(yīng)的網(wǎng)絡(luò)拓?fù)洌?/p>

第三步，采用“標(biāo)識(shí)分裂合并法”處理結(jié)點(diǎn)的加入退出事件：當(dāng)新結(jié)點(diǎn)P加入時(shí)，首先選取網(wǎng)絡(luò)中滿足下列條件的任一結(jié)點(diǎn)V：V的結(jié)點(diǎn)標(biāo)識(shí)長度不大于其任一鄰居結(jié)點(diǎn)；然后結(jié)點(diǎn)V進(jìn)行分裂，設(shè)結(jié)點(diǎn)V標(biāo)識(shí)為vlv2...vk，則結(jié)點(diǎn)P加入后，vlv2...vk分裂為v₁v₂...v_k0和v₁v₂...v_k1，結(jié)點(diǎn)V的標(biāo)識(shí)變?yōu)関₁v₂...v_k0，新結(jié)點(diǎn)P的標(biāo)識(shí)設(shè)置為v₁v₂...v_k1；進(jìn)而根據(jù)一股化de?Bruijn圖更新P、V以及相關(guān)結(jié)點(diǎn)的路由表，即各結(jié)點(diǎn)的連接關(guān)系滿足式(2)；當(dāng)檢測到結(jié)點(diǎn)Q離開時(shí)，首先選取網(wǎng)絡(luò)中某一對(duì)滿足下列條件的兄弟結(jié)點(diǎn)Y＝y(tǒng)ly2...yp-10和Y’＝y(tǒng)ly2...yp-11：Y和Y’的標(biāo)識(shí)長度都不小于其各自的鄰居；然后將結(jié)點(diǎn)Y的標(biāo)識(shí)改為Q的標(biāo)識(shí)，Y’的標(biāo)識(shí)改為yly2...yp-1；并根據(jù)一股化de?Bruijn圖更新相關(guān)結(jié)點(diǎn)的路由表；

第四步，采用“逐位匹配”方式實(shí)現(xiàn)資源的搜索：資源搜索通過結(jié)點(diǎn)間轉(zhuǎn)發(fā)搜索消息來完成；首先定義“前后匹配值”：對(duì)任意兩個(gè)字符串u＝u₁u₂...u_m和v＝v₁v₂...v_n，u和v的前后匹配值，記為QH(u，v)＝x，是指u的后x位與v的前x位相同，各結(jié)點(diǎn)在接收到資源對(duì)象搜索消息后，計(jì)算自己和目標(biāo)資源對(duì)象的前后匹配值x，然后在路由表中選擇與目標(biāo)資源對(duì)象的前后匹配值為x+1的鄰居進(jìn)行轉(zhuǎn)發(fā)；

第五步，采用“前后匹配”規(guī)則判斷是否完成搜索：結(jié)點(diǎn)u＝u₁u₂...u_m擁有資源s＝s₁s₂...s_r，當(dāng)且僅當(dāng)：QH(u，s)＝|u|，或者QH(u，s)＝|u|-1∧u₁＝s_r，當(dāng)滿足前后匹配規(guī)則時(shí)，說明完成資源的搜索，結(jié)束；否則轉(zhuǎn)第四步繼續(xù)進(jìn)行搜索。

2.如權(quán)利要求1所述的基于de?Bruijn圖的大規(guī)模網(wǎng)絡(luò)資源搜索方法，其特征在于一股化de?Bruijn圖中的點(diǎn)的標(biāo)識(shí)以二進(jìn)制數(shù)表示。