專(zhuān)利名稱(chēng)：一種面向大規(guī)模網(wǎng)絡(luò)環(huán)境的分布式k近鄰節(jié)點(diǎn)搜索方法
技術(shù)領(lǐng)域：
本發(fā)明涉及大規(guī)模網(wǎng)絡(luò)環(huán)境中的近鄰節(jié)點(diǎn)搜索方法，尤其是大規(guī)模網(wǎng)絡(luò)環(huán)境中的 分布式K近鄰節(jié)點(diǎn)搜索方法。
背景技術(shù)：
近鄰節(jié)點(diǎn)搜索是網(wǎng)絡(luò)計(jì)算領(lǐng)域亟待解決的核心問(wèn)題之一。近鄰節(jié)點(diǎn)搜索是目前廣 泛采用的節(jié)點(diǎn)鄰近性測(cè)量方法之一，它利用全部或者部分節(jié)點(diǎn)之間的網(wǎng)絡(luò)距離測(cè)量結(jié)果， 確定給定目標(biāo)節(jié)點(diǎn)的一個(gè)或者多個(gè)近鄰節(jié)點(diǎn)。許多網(wǎng)絡(luò)應(yīng)用系統(tǒng)的執(zhí)行策略是以節(jié)點(diǎn)鄰近 性為基礎(chǔ)的，近鄰節(jié)點(diǎn)搜索的精確度、穩(wěn)定性和效率將直接影響到節(jié)點(diǎn)鄰近性測(cè)量的效果， 從而影響網(wǎng)絡(luò)應(yīng)用系統(tǒng)的運(yùn)行效率。現(xiàn)有的近鄰節(jié)點(diǎn)搜索的典型方法主要包括兩類(lèi)(1)集中式近鄰節(jié)點(diǎn)搜索方法，它通過(guò)對(duì)目標(biāo)節(jié)點(diǎn)與其它節(jié)點(diǎn)之間的網(wǎng)絡(luò)距離進(jìn) 行排序，集中式搜索目標(biāo)節(jié)點(diǎn)的多個(gè)近鄰節(jié)點(diǎn)。集中式近鄰節(jié)點(diǎn)搜索方法需要集中維護(hù)所 有節(jié)點(diǎn)之間的網(wǎng)絡(luò)距離信息。在大規(guī)模網(wǎng)絡(luò)環(huán)境下，一方面，網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量龐大，使得完全 測(cè)量極易造成嚴(yán)重的帶寬消耗和網(wǎng)絡(luò)擁塞，同時(shí)引起巨大的通信開(kāi)銷(xiāo)；另一方面，網(wǎng)絡(luò)節(jié)點(diǎn) 具有高度動(dòng)態(tài)性、不可達(dá)性等特點(diǎn)，使得直接測(cè)量有時(shí)根本無(wú)法進(jìn)行，也很容易引起單點(diǎn)失 效問(wèn)題。所以，集中式近鄰節(jié)點(diǎn)搜索方法的可擴(kuò)展性較差，不適用于大規(guī)模網(wǎng)絡(luò)環(huán)境。(2)分布式近鄰節(jié)點(diǎn)搜索方法，它利用部分節(jié)點(diǎn)之間的網(wǎng)絡(luò)距離信息實(shí)現(xiàn)搜索信 息在各節(jié)點(diǎn)之間的轉(zhuǎn)發(fā)，最終找到近似最優(yōu)的最近鄰節(jié)點(diǎn)(即，近鄰節(jié)點(diǎn)數(shù)目K = 1)。分布 式近鄰節(jié)點(diǎn)搜索方法無(wú)需完全測(cè)量所有節(jié)點(diǎn)之間的網(wǎng)絡(luò)距離，并且分布維護(hù)節(jié)點(diǎn)之間的網(wǎng) 絡(luò)距離信息。分布式近鄰節(jié)點(diǎn)搜索方法的可擴(kuò)展性較好，對(duì)大規(guī)模網(wǎng)絡(luò)環(huán)境的適應(yīng)能力較 強(qiáng)。與集中式近鄰節(jié)點(diǎn)搜索方法相比，分布式近鄰節(jié)點(diǎn)搜索方法更加適用于大規(guī)模網(wǎng) 絡(luò)環(huán)境，逐漸成為低成本高精度實(shí)現(xiàn)近鄰節(jié)點(diǎn)搜索的主要技術(shù)途徑。但是，現(xiàn)有的分布式近 鄰節(jié)點(diǎn)搜索方法主要關(guān)注如何搜索最近鄰節(jié)點(diǎn)，難以有效支持K(K> 1)近鄰節(jié)點(diǎn)的搜索， 無(wú)法有效滿足網(wǎng)絡(luò)應(yīng)用對(duì)近鄰節(jié)點(diǎn)搜索的需求。因此，如何在大規(guī)模網(wǎng)絡(luò)環(huán)境中高效精確 地搜索K近鄰節(jié)點(diǎn)已經(jīng)成為網(wǎng)絡(luò)計(jì)算領(lǐng)域的熱點(diǎn)研究問(wèn)題。

發(fā)明內(nèi)容
本發(fā)明要解決的技術(shù)問(wèn)題是針對(duì)現(xiàn)有的分布式近鄰節(jié)點(diǎn)搜索方法無(wú)法有效實(shí)現(xiàn) K(K> 1)近鄰節(jié)點(diǎn)搜索的問(wèn)題，提出一種面向大規(guī)模網(wǎng)絡(luò)環(huán)境的分布式K近鄰節(jié)點(diǎn)搜索方 法，低成本高精度實(shí)現(xiàn)節(jié)點(diǎn)鄰近性的測(cè)量。本發(fā)明技術(shù)方案是采用直接測(cè)量方式為每個(gè)節(jié)點(diǎn)構(gòu)建鄰居集，并維護(hù)節(jié)點(diǎn)之間 的網(wǎng)絡(luò)距離信息；定期更新節(jié)點(diǎn)的鄰居集，擴(kuò)大鄰居集覆蓋范圍，降低搜索迭代次數(shù)，提高 搜索效率；基于回退思想，從與目標(biāo)節(jié)點(diǎn)網(wǎng)絡(luò)距離最遠(yuǎn)的節(jié)點(diǎn)開(kāi)始搜索最近鄰節(jié)點(diǎn)，為回退 搜索其余K-1個(gè)近鄰節(jié)點(diǎn)奠定基礎(chǔ)。
具體的技術(shù)方案是第一步，系統(tǒng)初始化。1. 1在系統(tǒng)初始狀態(tài)，對(duì)于任意節(jié)點(diǎn)0，將其初始鄰居集設(shè)置為除本節(jié)點(diǎn)0之外的 其它所有節(jié)點(diǎn)，并通過(guò)直接測(cè)量方式獲取節(jié)點(diǎn)之間的網(wǎng)絡(luò)距離。每個(gè)節(jié)點(diǎn)維護(hù)的鄰居集信 息包括鄰居節(jié)點(diǎn)IP和本節(jié)點(diǎn)與鄰居節(jié)點(diǎn)之間的網(wǎng)絡(luò)距離。1. 2隨機(jī)選擇節(jié)點(diǎn)E作為入口節(jié)點(diǎn)，便于新節(jié)點(diǎn)加入。第二步，為新加入節(jié)點(diǎn)創(chuàng)建鄰居集。2. 1假設(shè)A是新加入的節(jié)點(diǎn)，節(jié)點(diǎn)A向入口節(jié)點(diǎn)E發(fā)送加入請(qǐng)求。2. 2入口節(jié)點(diǎn)E從其鄰居集中隨機(jī)選擇I個(gè)節(jié)點(diǎn)，將這些節(jié)點(diǎn)的IP發(fā)送給新節(jié)點(diǎn) A。I為正整數(shù)，通常I的取值為5，I應(yīng)根據(jù)系統(tǒng)的擴(kuò)展性和維護(hù)開(kāi)銷(xiāo)進(jìn)行動(dòng)態(tài)調(diào)整。2. 3新節(jié)點(diǎn)A將入口節(jié)點(diǎn)E發(fā)送的I個(gè)節(jié)點(diǎn)設(shè)置為初始鄰居集，并通過(guò)直接測(cè)量方 式獲取本節(jié)點(diǎn)與鄰居節(jié)點(diǎn)之間的網(wǎng)絡(luò)距離。第三步，節(jié)點(diǎn)鄰居集更新。每個(gè)節(jié)點(diǎn)定期更新鄰居集，具體包括隨機(jī)更新和最近鄰更新兩部分。隨機(jī)更新的 周期為T(mén)R(TR通常取100s)，最近鄰更新的周期為T(mén)N(通常，TN = TR*10)。TR和TN應(yīng)根據(jù) 系統(tǒng)的擴(kuò)展性和維護(hù)開(kāi)銷(xiāo)進(jìn)行動(dòng)態(tài)調(diào)整，將正在更新的節(jié)點(diǎn)設(shè)為B，則3. 1隨機(jī)更新3. 1. 1節(jié)點(diǎn)B隨機(jī)選擇其鄰居集中的一個(gè)節(jié)點(diǎn)M，并向節(jié)點(diǎn)M發(fā)送請(qǐng)求消息。3. 1. 2節(jié)點(diǎn)M從其鄰居集中隨機(jī)選擇比例為P(P通常取5% )的鄰居節(jié)點(diǎn)構(gòu)成集 合S，并將集合S返回給節(jié)點(diǎn)B。3. 1. 3節(jié)點(diǎn)B通過(guò)直接測(cè)量方式獲取本節(jié)點(diǎn)與集合S中的各節(jié)點(diǎn)之間的網(wǎng)絡(luò)距離。3. 1. 4節(jié)點(diǎn)B將集合S中的節(jié)點(diǎn)添加到自己的鄰居集中。3. 2最近鄰更新3. 2. 1節(jié)點(diǎn)B采用最近鄰節(jié)點(diǎn)搜索方法搜索自己的最近鄰節(jié)點(diǎn)，得到最近鄰節(jié)點(diǎn)BN。最近鄰節(jié)點(diǎn)搜索方法的具體流程是(1)從入口節(jié)點(diǎn)E開(kāi)始搜索目標(biāo)節(jié)點(diǎn)T的最遠(yuǎn)鄰節(jié)點(diǎn)。(1. 1)節(jié)點(diǎn)E直接測(cè)量其與目標(biāo)節(jié)點(diǎn)T之間的網(wǎng)絡(luò)距離d。(1. 2)在節(jié)點(diǎn)E的鄰居集中選擇符合如下條件的節(jié)點(diǎn)X 節(jié)點(diǎn)E與節(jié)點(diǎn)X之間的網(wǎng) 絡(luò)距離在[(l_0)*d，(1+0 )*d]范圍內(nèi)，0為系統(tǒng)參數(shù)(0通常取10%)，符合條件的節(jié) 點(diǎn)構(gòu)成集合FS。(1. 3)直接測(cè)量集合FS中的各節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)T之間的網(wǎng)絡(luò)距離，確定與目標(biāo)節(jié) 點(diǎn)T距離最遠(yuǎn)的節(jié)點(diǎn)F，其與目標(biāo)節(jié)點(diǎn)T之間的網(wǎng)絡(luò)距離記為dF。(1. 4)如果dF > d，節(jié)點(diǎn)E向節(jié)點(diǎn)F發(fā)送搜索最遠(yuǎn)鄰節(jié)點(diǎn)的請(qǐng)求信息，E = F，然后 轉(zhuǎn)步驟(1. 1)繼續(xù)搜索最遠(yuǎn)鄰節(jié)點(diǎn)；否則，當(dāng)前節(jié)點(diǎn)E即為最遠(yuǎn)鄰節(jié)點(diǎn)，記為Q。(2)從最遠(yuǎn)鄰節(jié)點(diǎn)Q開(kāi)始搜索目標(biāo)節(jié)點(diǎn)T的最近鄰節(jié)點(diǎn)。(2. 1)節(jié)點(diǎn)Q直接測(cè)量其與目標(biāo)節(jié)點(diǎn)T之間的網(wǎng)絡(luò)距離1。(2. 2)在節(jié)點(diǎn)Q的鄰居集中選擇符合如下條件的節(jié)點(diǎn)Y 節(jié)點(diǎn)Q與節(jié)點(diǎn)Y之間的網(wǎng) 絡(luò)距離在[(1_0)*1，(1+日)*1]范圍內(nèi)，符合條件的節(jié)點(diǎn)構(gòu)成集合NS1。
(2.3)在節(jié)點(diǎn)Q的鄰居集中隨機(jī)選擇m個(gè)節(jié)點(diǎn)構(gòu)成集合NS2。m為正整數(shù)，通常m 的取值為5，m應(yīng)根據(jù)系統(tǒng)的擴(kuò)展性和維護(hù)開(kāi)銷(xiāo)進(jìn)行動(dòng)態(tài)調(diào)整。(2. 4)NS = NS1 U NS2。(2. 5)直接測(cè)量集合NS中的各節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)T之間的網(wǎng)絡(luò)距離，確定與目標(biāo)節(jié) 點(diǎn)T距離最近的節(jié)點(diǎn)N，其與目標(biāo)節(jié)點(diǎn)T之間的網(wǎng)絡(luò)距離記為1N。(2. 6)如果1N < 1，節(jié)點(diǎn)Q向節(jié)點(diǎn)N發(fā)送搜索最近鄰節(jié)點(diǎn)的請(qǐng)求信息，節(jié)點(diǎn)N將節(jié) 點(diǎn)Q記錄為其上一跳步節(jié)點(diǎn)，為實(shí)現(xiàn)回退搜索提供信息，Q = N，然后轉(zhuǎn)步驟(2. 1)繼續(xù)搜索最近鄰節(jié)點(diǎn)；否則，當(dāng)前節(jié)點(diǎn)Q即為最近鄰節(jié)點(diǎn)。3. 2. 2節(jié)點(diǎn)B將節(jié)點(diǎn)BN添加到其鄰居集中。第四步，當(dāng)接收到搜索目標(biāo)節(jié)點(diǎn)T的K近鄰節(jié)點(diǎn)的請(qǐng)求時(shí)(系統(tǒng)的節(jié)點(diǎn)數(shù)目 彡K彡1)，進(jìn)行回退搜索。4. 1采用步驟3. 2. 1中的最近鄰節(jié)點(diǎn)搜索方法搜索目標(biāo)節(jié)點(diǎn)T的最近鄰節(jié)點(diǎn)NN。4. 2目標(biāo)節(jié)點(diǎn)T的最近鄰節(jié)點(diǎn)NN向其上一跳步節(jié)點(diǎn)R發(fā)送最近鄰節(jié)點(diǎn)搜索請(qǐng)求和 當(dāng)前K近鄰節(jié)點(diǎn)集合KNSet = {NN}。4. 3采用步驟3. 2. 1中的最近鄰節(jié)點(diǎn)搜索方法從節(jié)點(diǎn)R開(kāi)始，E = R，在不包括當(dāng) 前K近鄰節(jié)點(diǎn)集合KNSet的節(jié)點(diǎn)范圍內(nèi)搜索目標(biāo)節(jié)點(diǎn)T的最近鄰節(jié)點(diǎn)Y，當(dāng)前K近鄰節(jié)點(diǎn)集 合更新為 KNSet = KNSet U {Y}。4. 4如果當(dāng)前K近鄰節(jié)點(diǎn)集合KNSet包含的節(jié)點(diǎn)數(shù)目等于K，那么，K近鄰節(jié)點(diǎn)搜 索結(jié)束；否則，節(jié)點(diǎn)Y向其上一跳步節(jié)點(diǎn)R’發(fā)送最近鄰節(jié)點(diǎn)搜索請(qǐng)求和當(dāng)前K近鄰節(jié)點(diǎn)集 合KNSet, R = R’，轉(zhuǎn)到第4. 3步，繼續(xù)回退搜索。與現(xiàn)有技術(shù)相比，采用本發(fā)明可達(dá)到以下技術(shù)效果1.采用隨機(jī)更新和最近鄰更新兩種方式定期更新節(jié)點(diǎn)的鄰居集，擴(kuò)大鄰居集覆蓋 范圍，有效降低搜索迭代次數(shù)，從而提高搜索效率。2.首先搜索目標(biāo)節(jié)點(diǎn)的最遠(yuǎn)鄰節(jié)點(diǎn)，然后從最遠(yuǎn)鄰節(jié)點(diǎn)開(kāi)始搜索目標(biāo)節(jié)點(diǎn)的最近 鄰節(jié)點(diǎn)，既保證從全局范圍搜索最近鄰節(jié)點(diǎn)，又為回退搜索其余(K-1)個(gè)近鄰節(jié)點(diǎn)提供相 關(guān)節(jié)點(diǎn)信息。3.采用回退思想分布式搜索K近鄰節(jié)點(diǎn)，通過(guò)記錄最近鄰節(jié)點(diǎn)搜索過(guò)程中的節(jié) 點(diǎn)，降低回退搜索的系統(tǒng)開(kāi)銷(xiāo)；通過(guò)在回退過(guò)程中不斷搜索當(dāng)前的最近鄰節(jié)點(diǎn)，提高回退搜 索的精確度，從而能夠低成本高精度實(shí)現(xiàn)節(jié)點(diǎn)鄰近性測(cè)量。


圖1是本發(fā)明總流程圖。圖2是本發(fā)明第三步進(jìn)行節(jié)點(diǎn)鄰居集隨機(jī)更新的流程圖。圖3是本發(fā)明第三步最近鄰節(jié)點(diǎn)搜索方法中從入口節(jié)點(diǎn)開(kāi)始搜索目標(biāo)節(jié)點(diǎn)的最 遠(yuǎn)鄰節(jié)點(diǎn)的流程圖。圖4是本發(fā)明第三步最近鄰節(jié)點(diǎn)搜索方法中從最遠(yuǎn)鄰節(jié)點(diǎn)開(kāi)始搜索目標(biāo)節(jié)點(diǎn)的 最近鄰節(jié)點(diǎn)的流程圖。
具體實(shí)施例方式圖1是采用本發(fā)明進(jìn)行分布式K近鄰節(jié)點(diǎn)搜索的總流程圖。具體流程如下第一步，系統(tǒng)初始化。1. 1將每個(gè)節(jié)點(diǎn)的初始鄰居集設(shè)置為除本節(jié)點(diǎn)之外的其它所有節(jié)點(diǎn)，通過(guò)直接測(cè) 量獲取節(jié)點(diǎn)之間的網(wǎng)絡(luò)距離。1.2確定入口節(jié)點(diǎn)。第二步，為新加入節(jié)點(diǎn)創(chuàng)建鄰居集。2. 1新加入節(jié)點(diǎn)向入口節(jié)點(diǎn)發(fā)送加入請(qǐng)求。2. 2入口節(jié)點(diǎn)從其鄰居集中隨機(jī)選擇I個(gè)節(jié)點(diǎn)發(fā)送給新加入節(jié)點(diǎn)作為其初始鄰居 集，I為正整數(shù)，通常I的取值為5，I應(yīng)根據(jù)系統(tǒng)的擴(kuò)展性和維護(hù)開(kāi)銷(xiāo)進(jìn)行動(dòng)態(tài)調(diào)整。2. 3新加入節(jié)點(diǎn)通過(guò)直接測(cè)量獲取本節(jié)點(diǎn)與鄰居節(jié)點(diǎn)之間的網(wǎng)絡(luò)距離。第三步，節(jié)點(diǎn)鄰居集更新。3. 1每個(gè)節(jié)點(diǎn)定期利用隨機(jī)選擇的鄰居節(jié)點(diǎn)進(jìn)行鄰居集更新。3. 2每個(gè)節(jié)點(diǎn)定期進(jìn)行最近鄰節(jié)點(diǎn)搜索，并利用得到的最近鄰節(jié)點(diǎn)進(jìn)行鄰居集更新。第四步，當(dāng)接收到搜索目標(biāo)節(jié)點(diǎn)T的K近鄰節(jié)點(diǎn)的請(qǐng)求時(shí)(系統(tǒng)的節(jié)點(diǎn)數(shù)目 彡K彡1)，進(jìn)行回退搜索。4. 1搜索目標(biāo)節(jié)點(diǎn)T的最近鄰節(jié)點(diǎn)NN。4. 2最近鄰節(jié)點(diǎn)NN向其上一跳步節(jié)點(diǎn)R發(fā)送最近鄰節(jié)點(diǎn)搜索請(qǐng)求和當(dāng)前K近鄰節(jié) 點(diǎn)集合 KNSet = {NN}。4. 3從節(jié)點(diǎn)R開(kāi)始在不包括當(dāng)前K近鄰節(jié)點(diǎn)集合KNSet的節(jié)點(diǎn)范圍內(nèi)搜索目標(biāo)節(jié) 點(diǎn)的最近鄰節(jié)點(diǎn)Y，當(dāng)前K近鄰節(jié)點(diǎn)集合更新為KNSet = KNSet U {Y}。4. 4如果當(dāng)前K近鄰節(jié)點(diǎn)集合KNSet包含的節(jié)點(diǎn)數(shù)目等于K，那么，K近鄰節(jié)點(diǎn)搜 索結(jié)束；否則，節(jié)點(diǎn)Y向其上一跳步節(jié)點(diǎn)R’發(fā)送最近鄰節(jié)點(diǎn)搜索請(qǐng)求和當(dāng)前K近鄰節(jié)點(diǎn)集 合KNSet, R = R’，轉(zhuǎn)到第4. 3步，繼續(xù)回退搜索。圖2是本發(fā)明第三步進(jìn)行節(jié)點(diǎn)鄰居集隨機(jī)更新的流程圖。具體流程如下1.節(jié)點(diǎn)B隨機(jī)選擇其鄰居集中的一個(gè)節(jié)點(diǎn)M。2.節(jié)點(diǎn)B向節(jié)點(diǎn)M發(fā)送請(qǐng)求消息。3.節(jié)點(diǎn)M從其鄰居集中隨機(jī)選擇比例為P(P通常取5% )的鄰居節(jié)點(diǎn)構(gòu)成集合S。4.節(jié)點(diǎn)M將集合S返回給節(jié)點(diǎn)B。5.節(jié)點(diǎn)B通過(guò)直接測(cè)量獲取本節(jié)點(diǎn)與集合S中的各節(jié)點(diǎn)之間的網(wǎng)絡(luò)距離。6.節(jié)點(diǎn)B將集合S中的節(jié)點(diǎn)添加到自己的鄰居集中。圖3是本發(fā)明第三步最近鄰節(jié)點(diǎn)搜索方法中從入口節(jié)點(diǎn)開(kāi)始搜索目標(biāo)節(jié)點(diǎn)的最 遠(yuǎn)鄰節(jié)點(diǎn)的流程圖。具體流程如下1.入口節(jié)點(diǎn)E直接測(cè)量其與目標(biāo)節(jié)點(diǎn)之間的網(wǎng)絡(luò)距離d。2.在節(jié)點(diǎn)E的鄰居集中選擇符合如下條件的節(jié)點(diǎn)X 節(jié)點(diǎn)E與節(jié)點(diǎn)X之間的網(wǎng)絡(luò) 距離在[(l_0)*d，(l+0)*d]范圍內(nèi)，0為系統(tǒng)參數(shù)，符合條件的節(jié)點(diǎn)構(gòu)成集合FS。3.節(jié)點(diǎn)E向集合FS中的各節(jié)點(diǎn)發(fā)送請(qǐng)求信息。4.集合FS中的各節(jié)點(diǎn)直接測(cè)量其與目標(biāo)節(jié)點(diǎn)之間的網(wǎng)絡(luò)距離。5.集合FS中的各節(jié)點(diǎn)將測(cè)量結(jié)果返回節(jié)點(diǎn)E。
6.節(jié)點(diǎn)E在集合FS中選出與目標(biāo)節(jié)點(diǎn)距離最遠(yuǎn)的節(jié)點(diǎn)F，節(jié)點(diǎn)F與目標(biāo)節(jié)點(diǎn)之間 的網(wǎng)絡(luò)距離記為dF。7.如果dF > d，則節(jié)點(diǎn)E向節(jié)點(diǎn)F發(fā)送搜索最遠(yuǎn)鄰節(jié)點(diǎn)的請(qǐng)求信息，E = F，然后 轉(zhuǎn)步驟1繼續(xù)搜索最遠(yuǎn)鄰節(jié)點(diǎn)；否則，當(dāng)前節(jié)點(diǎn)E即為最遠(yuǎn)鄰節(jié)點(diǎn)。圖4是本發(fā)明第三步最近鄰節(jié)點(diǎn)搜索方法中從最遠(yuǎn)鄰節(jié)點(diǎn)開(kāi)始搜索目標(biāo)節(jié)點(diǎn)的 最近鄰節(jié)點(diǎn)的流程圖。具體流程如下1.最遠(yuǎn)鄰節(jié)點(diǎn)Q直接測(cè)量其與目標(biāo)節(jié)點(diǎn)之間的網(wǎng)絡(luò)距離1。2.在節(jié)點(diǎn)Q的鄰居集中選擇符合如下條件的節(jié)點(diǎn)Y 節(jié)點(diǎn)Q與節(jié)點(diǎn)Y之間的網(wǎng)絡(luò) 距離在[(1_3)*1，(1+舊*1]范圍內(nèi)，3為系統(tǒng)參數(shù)，符合條件的節(jié)點(diǎn)構(gòu)成集合NS1 ；在節(jié) 點(diǎn)Q的鄰居集中隨機(jī)選擇m個(gè)節(jié)點(diǎn)構(gòu)成集合NS2 ；NS = NS1 U NS2。3.節(jié)點(diǎn)Q向集合NS中的各節(jié)點(diǎn)發(fā)送請(qǐng)求信息。4.集合NS中的各節(jié)點(diǎn)直接測(cè)量其與目標(biāo)節(jié)點(diǎn)之間的網(wǎng)絡(luò)距離。5.集合NS中的各節(jié)點(diǎn)將測(cè)量結(jié)果返回節(jié)點(diǎn)Q。6.節(jié)點(diǎn)Q在集合NS中選出與目標(biāo)節(jié)點(diǎn)距離最近的節(jié)點(diǎn)N，節(jié)點(diǎn)N與目標(biāo)節(jié)點(diǎn)之間 的網(wǎng)絡(luò)距離記為1N。7.如果1N < 1，則節(jié)點(diǎn)Q向節(jié)點(diǎn)N發(fā)送搜索最近鄰節(jié)點(diǎn)的請(qǐng)求信息，節(jié)點(diǎn)N將節(jié)點(diǎn) Q記錄為其上一跳步節(jié)點(diǎn)，為實(shí)現(xiàn)回退搜索提供信息，Q = N，然后轉(zhuǎn)步驟1繼續(xù)搜索最近鄰 節(jié)點(diǎn)；否則，當(dāng)前節(jié)點(diǎn)Q即為最近鄰節(jié)點(diǎn)。
權(quán)利要求
一種面向大規(guī)模網(wǎng)絡(luò)環(huán)境的分布式K近鄰節(jié)點(diǎn)搜索方法，其特征在于包括以下步驟第一步，系統(tǒng)初始化1.1在系統(tǒng)初始狀態(tài)，對(duì)于任意節(jié)點(diǎn)O，將其初始鄰居集設(shè)置為除本節(jié)點(diǎn)O之外的其它所有節(jié)點(diǎn)，并通過(guò)直接測(cè)量方式獲取節(jié)點(diǎn)之間的網(wǎng)絡(luò)距離，每個(gè)節(jié)點(diǎn)維護(hù)的鄰居集信息包括鄰居節(jié)點(diǎn)IP和本節(jié)點(diǎn)與鄰居節(jié)點(diǎn)之間的網(wǎng)絡(luò)距離；1.2隨機(jī)選擇節(jié)點(diǎn)E作為入口節(jié)點(diǎn)；第二步，為新加入節(jié)點(diǎn)創(chuàng)建鄰居集2.1假設(shè)A是新加入的節(jié)點(diǎn)，節(jié)點(diǎn)A向入口節(jié)點(diǎn)E發(fā)送加入請(qǐng)求；2.2入口節(jié)點(diǎn)E從其鄰居集中隨機(jī)選擇I個(gè)節(jié)點(diǎn)，將這些節(jié)點(diǎn)的IP發(fā)送給新節(jié)點(diǎn)A，I為正整數(shù)，I根據(jù)系統(tǒng)的擴(kuò)展性和維護(hù)開(kāi)銷(xiāo)進(jìn)行動(dòng)態(tài)調(diào)整；2.3新節(jié)點(diǎn)A將入口節(jié)點(diǎn)E發(fā)送的I個(gè)節(jié)點(diǎn)設(shè)置為初始鄰居集，并通過(guò)直接測(cè)量方式獲取本節(jié)點(diǎn)與鄰居節(jié)點(diǎn)之間的網(wǎng)絡(luò)距離；第三步，節(jié)點(diǎn)鄰居集更新每個(gè)節(jié)點(diǎn)定期更新鄰居集，具體包括隨機(jī)更新和最近鄰更新兩部分，隨機(jī)更新的周期為T(mén)R，最近鄰更新的周期為T(mén)N，TR和TN根據(jù)系統(tǒng)的擴(kuò)展性和維護(hù)開(kāi)銷(xiāo)動(dòng)態(tài)設(shè)置，將正更新的節(jié)點(diǎn)設(shè)為B，3.1隨機(jī)更新3.1.1節(jié)點(diǎn)B隨機(jī)選擇其鄰居集中的一個(gè)節(jié)點(diǎn)M，并向節(jié)點(diǎn)M發(fā)送請(qǐng)求消息；3.1.2節(jié)點(diǎn)M從其鄰居集中隨機(jī)選擇比例為P的鄰居節(jié)點(diǎn)構(gòu)成集合S，并將集合S返回給節(jié)點(diǎn)B，P取5％；3.1.3節(jié)點(diǎn)B通過(guò)直接測(cè)量方式獲取本節(jié)點(diǎn)與集合S中的各節(jié)點(diǎn)之間的網(wǎng)絡(luò)距離；3.1.4節(jié)點(diǎn)B將集合S中的節(jié)點(diǎn)添加到自己的鄰居集中；3.2最近鄰更新3.2.1節(jié)點(diǎn)B采用最近鄰節(jié)點(diǎn)搜索方法搜索自己的最近鄰節(jié)點(diǎn)，得到最近鄰節(jié)點(diǎn)BN；3.2.2節(jié)點(diǎn)B將節(jié)點(diǎn)BN添加到其鄰居集中；第四步，當(dāng)接收到搜索目標(biāo)節(jié)點(diǎn)T的K近鄰節(jié)點(diǎn)的請(qǐng)求時(shí)，系統(tǒng)的節(jié)點(diǎn)數(shù)目≥K≥1，進(jìn)行回退搜索4.1采用最近鄰節(jié)點(diǎn)搜索方法搜索目標(biāo)節(jié)點(diǎn)T的最近鄰節(jié)點(diǎn)NN；4.2目標(biāo)節(jié)點(diǎn)T的最近鄰節(jié)點(diǎn)NN向其上一跳步節(jié)點(diǎn)R發(fā)送最近鄰節(jié)點(diǎn)搜索請(qǐng)求和當(dāng)前K近鄰節(jié)點(diǎn)集合KNSet＝{NN}；4.3采用最近鄰節(jié)點(diǎn)搜索方法從節(jié)點(diǎn)R開(kāi)始，E＝R，在不包括當(dāng)前K近鄰節(jié)點(diǎn)集合KNSet的節(jié)點(diǎn)范圍內(nèi)搜索目標(biāo)節(jié)點(diǎn)T的最近鄰節(jié)點(diǎn)Y，當(dāng)前K近鄰節(jié)點(diǎn)集合更新為KNSet＝KNSet∪{Y}；4.4如果當(dāng)前K近鄰節(jié)點(diǎn)集合KNSet包含的節(jié)點(diǎn)數(shù)目等于K，那么，K近鄰節(jié)點(diǎn)搜索結(jié)束；否則，節(jié)點(diǎn)Y向其上一跳步節(jié)點(diǎn)R’發(fā)送最近鄰節(jié)點(diǎn)搜索請(qǐng)求和當(dāng)前K近鄰節(jié)點(diǎn)集合KNSet，R＝R’，轉(zhuǎn)到第4.3步，繼續(xù)回退搜索。
2.如權(quán)利要求1所述的一種面向大規(guī)模網(wǎng)絡(luò)環(huán)境的分布式K近鄰節(jié)點(diǎn)搜索方法，其特 征在于所述最近鄰節(jié)點(diǎn)搜索方法的流程是(1)從入口節(jié)點(diǎn)E開(kāi)始搜索目標(biāo)節(jié)點(diǎn)T的最遠(yuǎn)鄰節(jié)點(diǎn)(1. 1)節(jié)點(diǎn)E直接測(cè)量其與目標(biāo)節(jié)點(diǎn)T之間的網(wǎng)絡(luò)距離d ；(1. 2)在節(jié)點(diǎn)E的鄰居集中選擇符合如下條件的節(jié)點(diǎn)X 節(jié)點(diǎn)E與節(jié)點(diǎn)X之間的網(wǎng)絡(luò)距 離在[(1-0 )*d，(1+0 )*d]范圍內(nèi)，0為系統(tǒng)參數(shù)，0取10%，符合條件的節(jié)點(diǎn)構(gòu)成集合 FS ；(1. 3)直接測(cè)量集合FS中的各節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)T之間的網(wǎng)絡(luò)距離，確定與目標(biāo)節(jié)點(diǎn)T 距離最遠(yuǎn)的節(jié)點(diǎn)F，其與目標(biāo)節(jié)點(diǎn)T之間的網(wǎng)絡(luò)距離記為dF ；(1. 4)如果dF > d，節(jié)點(diǎn)E向節(jié)點(diǎn)F發(fā)送搜索最遠(yuǎn)鄰節(jié)點(diǎn)的請(qǐng)求信息，E = F，然后轉(zhuǎn)步 驟(1. 1)繼續(xù)搜索最遠(yuǎn)鄰節(jié)點(diǎn)；否則，當(dāng)前節(jié)點(diǎn)E即為最遠(yuǎn)鄰節(jié)點(diǎn)，記為Q ；(2)從最遠(yuǎn)鄰節(jié)點(diǎn)Q開(kāi)始搜索目標(biāo)節(jié)點(diǎn)T的最近鄰節(jié)點(diǎn)(2. 1)節(jié)點(diǎn)Q直接測(cè)量其與目標(biāo)節(jié)點(diǎn)T之間的網(wǎng)絡(luò)距離1 ；(2. 2)在節(jié)點(diǎn)Q的鄰居集中選擇符合如下條件的節(jié)點(diǎn)Y 節(jié)點(diǎn)Q與節(jié)點(diǎn)Y之間的網(wǎng)絡(luò)距 離在[(1_0)*1，(1+日)*1]范圍內(nèi)，符合條件的節(jié)點(diǎn)構(gòu)成集合NS1。(2. 3)在節(jié)點(diǎn)Q的鄰居集中隨機(jī)選擇m個(gè)節(jié)點(diǎn)構(gòu)成集合NS2，m為正整數(shù)，m根據(jù)系統(tǒng)的 擴(kuò)展性和維護(hù)開(kāi)銷(xiāo)進(jìn)行動(dòng)態(tài)調(diào)整；(2. 4) NS = NS1 U NS2 ；(2. 5)直接測(cè)量集合NS中的各節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)T之間的網(wǎng)絡(luò)距離，確定與目標(biāo)節(jié)點(diǎn)T 距離最近的節(jié)點(diǎn)N，其與目標(biāo)節(jié)點(diǎn)T之間的網(wǎng)絡(luò)距離記為1N ；(2. 6)如果1N < 1，節(jié)點(diǎn)Q向節(jié)點(diǎn)N發(fā)送搜索最近鄰節(jié)點(diǎn)的請(qǐng)求信息，節(jié)點(diǎn)N將節(jié)點(diǎn)Q 記錄為其上一跳步節(jié)點(diǎn)，為實(shí)現(xiàn)回退搜索提供信息，Q = N，然后轉(zhuǎn)步驟(2. 1)繼續(xù)搜索最近 鄰節(jié)點(diǎn)；否則，當(dāng)前節(jié)點(diǎn)Q即為最近鄰節(jié)點(diǎn)。
3.如權(quán)利要求1所述的一種面向大規(guī)模網(wǎng)絡(luò)環(huán)境的分布式K近鄰節(jié)點(diǎn)搜索方法，其特 征在于所述I的取值為5，m的取值為5。
4.如權(quán)利要求1所述的一種面向大規(guī)模網(wǎng)絡(luò)環(huán)境的分布式K近鄰節(jié)點(diǎn)搜索方法，其特 征在于所述TR取100s, TN = TR*10。
全文摘要
本發(fā)明公開(kāi)了一種面向大規(guī)模網(wǎng)絡(luò)環(huán)境的分布式K近鄰節(jié)點(diǎn)搜索方法，要解決的技術(shù)問(wèn)題是提出一種面向大規(guī)模網(wǎng)絡(luò)環(huán)境的分布式K近鄰節(jié)點(diǎn)搜索方法，低成本高精度實(shí)現(xiàn)節(jié)點(diǎn)鄰近性的測(cè)量。技術(shù)方案是采用直接測(cè)量方式為每個(gè)節(jié)點(diǎn)構(gòu)建鄰居集，并維護(hù)節(jié)點(diǎn)之間的網(wǎng)絡(luò)距離信息；采用隨機(jī)更新和最近鄰更新兩種方式更新節(jié)點(diǎn)的鄰居集；基于回退思想，從與目標(biāo)節(jié)點(diǎn)網(wǎng)絡(luò)距離最遠(yuǎn)的節(jié)點(diǎn)開(kāi)始搜索最近鄰節(jié)點(diǎn)。采用本發(fā)明可有效降低搜索迭代次數(shù)，提高搜索效率，且能保證從全局范圍搜索最近鄰節(jié)點(diǎn)，低成本高精度實(shí)現(xiàn)節(jié)點(diǎn)鄰近性測(cè)量。
文檔編號(hào)H04L12/28GK101827004SQ20101016897
公開(kāi)日2010年9月8日 申請(qǐng)日期2010年5月12日 優(yōu)先權(quán)日2010年5月12日
發(fā)明者孫偉東, 張一鳴, 彭宇行, 徐傳福, 李東升, 李小勇, 王勇獻(xiàn), 王意潔, 符永銓, 褚瑞, 車(chē)永剛, 陳振邦, 馬行空 申請(qǐng)人:中國(guó)人民解放軍國(guó)防科學(xué)技術(shù)大學(xué)