基于行為特征的超級(jí)節(jié)點(diǎn)節(jié)流算法研究

電子科技大學(xué) 電子科學(xué)技術(shù)研究院，成都 611731

電子科技大學(xué) 電子科學(xué)技術(shù)研究院，成都 611731

1 引言

P2P網(wǎng)絡(luò)技術(shù)具有良好的可擴(kuò)展性和健壯性，當(dāng)前已被廣泛使用。由最初的有中心節(jié)點(diǎn)的集中式網(wǎng)絡(luò)結(jié)構(gòu)，到完全隨機(jī)的泛洪方式（全分布式非結(jié)構(gòu)化網(wǎng)絡(luò)），到分布式散列表（DHT）結(jié)構(gòu)。P2P網(wǎng)絡(luò)拓?fù)湓诓粩嘧兓桶l(fā)展。超級(jí)節(jié)點(diǎn)是一個(gè)子P2P網(wǎng)絡(luò)的中心，一般通過(guò)P2P子網(wǎng)中的節(jié)點(diǎn)選舉擔(dān)任。超級(jí)節(jié)點(diǎn)負(fù)責(zé)收集子網(wǎng)中其他節(jié)點(diǎn)的索引信息，以提高整個(gè)P2P網(wǎng)絡(luò)的搜索查詢效率。目前，超級(jí)節(jié)點(diǎn)普遍采用終身制，即超級(jí)節(jié)點(diǎn)一旦被選出，就會(huì)一直工作到節(jié)點(diǎn)失效[1]。超級(jí)節(jié)點(diǎn)網(wǎng)絡(luò)的流量包括控制流和數(shù)據(jù)流兩部分[2]。目前對(duì)數(shù)據(jù)流量的優(yōu)化主要依靠查詢算法和數(shù)據(jù)壓縮，對(duì)于網(wǎng)絡(luò)控制流量的優(yōu)化則主要依靠改進(jìn)超級(jí)節(jié)點(diǎn)選舉算法。

P2P網(wǎng)絡(luò)中節(jié)點(diǎn)具有動(dòng)態(tài)性和不穩(wěn)定性，可能發(fā)生斷開(kāi)、崩潰或擁堵等現(xiàn)象。由于超級(jí)節(jié)點(diǎn)比普通節(jié)點(diǎn)掌握更多的網(wǎng)絡(luò)資源，因此其突然失效會(huì)對(duì)網(wǎng)絡(luò)查詢效率產(chǎn)生很大影響。文獻(xiàn)[3]給出了chord網(wǎng)絡(luò)中查詢效率和節(jié)點(diǎn)失效率的關(guān)系公式。其中，p為chord網(wǎng)絡(luò)中平均節(jié)點(diǎn)失效率（即網(wǎng)絡(luò)中失效的節(jié)點(diǎn)占總節(jié)點(diǎn)數(shù)百分比），n為網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)，h(n)為網(wǎng)絡(luò)中平均查詢跳數(shù)。h(n)越大，則查詢效率越低。

公式（1）是一個(gè)遞歸公式，由公式可以看出，隨著網(wǎng)絡(luò)中參與查詢的節(jié)點(diǎn)失效率增加，查詢跳數(shù)非線性增大，導(dǎo)致較大的網(wǎng)絡(luò)延時(shí)。

當(dāng)超級(jí)節(jié)點(diǎn)失效時(shí)，重構(gòu)網(wǎng)絡(luò)造成的開(kāi)銷是相當(dāng)大的。子網(wǎng)先要通過(guò)泛洪或DHT的方式通知各子網(wǎng)節(jié)點(diǎn)進(jìn)行新一輪的選舉，在選出新繼任的超級(jí)節(jié)點(diǎn)后，新超級(jí)節(jié)點(diǎn)還要重新收集子網(wǎng)中的資源信息，以重建子網(wǎng)索引。

P2P網(wǎng)絡(luò)的帶寬占用問(wèn)題一直是制約P2P技術(shù)推廣和應(yīng)用的一個(gè)關(guān)鍵問(wèn)題。目前，對(duì)超級(jí)節(jié)點(diǎn)網(wǎng)絡(luò)降低流量的研究較多集中于對(duì)超級(jí)節(jié)點(diǎn)的選擇標(biāo)準(zhǔn)上。文獻(xiàn)[4]提出以CPU動(dòng)態(tài)處理能力為考量標(biāo)準(zhǔn)，建立一套超級(jí)節(jié)點(diǎn)選取算法。文獻(xiàn)[5]為每個(gè)節(jié)點(diǎn)設(shè)置了能力值作為選舉超級(jí)節(jié)點(diǎn)的標(biāo)準(zhǔn)，并結(jié)合候補(bǔ)節(jié)點(diǎn)達(dá)到降低失效率的目的。文獻(xiàn)[6]為超級(jí)節(jié)點(diǎn)選舉設(shè)計(jì)了多個(gè)標(biāo)準(zhǔn)，普通節(jié)點(diǎn)根據(jù)需要加入到以不同標(biāo)準(zhǔn)選擇出的子網(wǎng)中，通過(guò)分類的方式減少查詢次數(shù)。文獻(xiàn)[7]提出了一種基于信譽(yù)感知的超級(jí)節(jié)點(diǎn)選擇算法，在選舉超級(jí)節(jié)點(diǎn)的時(shí)候不僅以節(jié)點(diǎn)性能做參考標(biāo)準(zhǔn)，還增加了安全屬性。文獻(xiàn)[8]提出了根據(jù)節(jié)點(diǎn)的ISP信息選擇查詢路由，從而減少查詢跳數(shù)達(dá)到節(jié)流的目的。文獻(xiàn)[9]通過(guò)監(jiān)測(cè)局域網(wǎng)內(nèi)的P2P流量，合并對(duì)外的網(wǎng)絡(luò)報(bào)文達(dá)到降低下載流量的目的。文獻(xiàn)[10]針對(duì)P2P流媒體流量提出了利用隨機(jī)網(wǎng)絡(luò)編碼實(shí)現(xiàn)全局網(wǎng)絡(luò)流量?jī)?yōu)化。但這些研究只關(guān)注了超級(jí)節(jié)點(diǎn)的選取對(duì)網(wǎng)絡(luò)查詢算法流量的優(yōu)化，卻忽略了超級(jí)節(jié)點(diǎn)產(chǎn)生和失效時(shí)重新收集資源對(duì)網(wǎng)絡(luò)帶寬產(chǎn)生的負(fù)擔(dān)。文獻(xiàn)[11]提出通過(guò)建立備選超級(jí)節(jié)點(diǎn)的方式減少單點(diǎn)失效問(wèn)題，與本文的思想比較相近，但對(duì)候補(bǔ)超級(jí)節(jié)點(diǎn)的選擇沒(méi)有給出依據(jù)，具有很大的隨機(jī)性。

為降低網(wǎng)絡(luò)單點(diǎn)失效而重新枚舉資源所產(chǎn)生控制流量的問(wèn)題，本文提出了一種超級(jí)節(jié)點(diǎn)禪讓算法。通過(guò)統(tǒng)計(jì)用戶行為特征，對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)失效問(wèn)題進(jìn)行預(yù)判，從而盡量避免不必要的流量開(kāi)銷，達(dá)到網(wǎng)絡(luò)節(jié)流的目的。并且通過(guò)與常用選舉算法配套做對(duì)比仿真實(shí)驗(yàn)，說(shuō)明算法取得了很好的降低通信流量的效果。

2 算法原理

圖1為一個(gè)混合型P2P網(wǎng)絡(luò)常見(jiàn)的拓?fù)浣Y(jié)構(gòu)。P2P網(wǎng)絡(luò)的每個(gè)節(jié)點(diǎn)是由人操作的，因此節(jié)點(diǎn)的存活狀態(tài)也會(huì)受人的生活狀態(tài)影響，存在一定的規(guī)律。比如上班族的工作主機(jī)通常早上9點(diǎn)左右開(kāi)機(jī)，下午5點(diǎn)左右關(guān)機(jī)；學(xué)生寢室晚上11點(diǎn)停電；一些服務(wù)器設(shè)定早上自動(dòng)開(kāi)啟，晚上自動(dòng)關(guān)閉等。這一類節(jié)點(diǎn)可以通過(guò)統(tǒng)計(jì)其生存周期，從而預(yù)先估計(jì)失效時(shí)間。對(duì)用戶行為進(jìn)行分析建模是近年來(lái)十分活躍的研究課題[12]，這種行為分析方式同樣可以引入節(jié)點(diǎn)節(jié)流算法研究中來(lái)。

圖1 混合型P2P網(wǎng)絡(luò)拓?fù)鋱D

基于這種規(guī)律，本文提出了一種超級(jí)節(jié)點(diǎn)禪讓算法（Super-Peers Abdication Algorithms，SPAA），通過(guò)一種新的方式達(dá)到控制節(jié)點(diǎn)失效開(kāi)銷的目的。SPAA算法作用于超級(jí)節(jié)點(diǎn)選舉產(chǎn)生之后，與各種選舉算法不沖突，可以疊加使用。使用SPAA算法能夠減少由于超級(jí)節(jié)點(diǎn)失效產(chǎn)生的控制流量，并且降低了超級(jí)節(jié)點(diǎn)失效率，從而間接也能降低查詢流量。

Fernandez等人認(rèn)為超級(jí)節(jié)點(diǎn)選舉與領(lǐng)導(dǎo)人選舉有相似的思想，可以借鑒其選舉機(jī)制[13]。但其實(shí)選舉超級(jí)節(jié)點(diǎn)與選領(lǐng)導(dǎo)人在實(shí)際應(yīng)用中有一個(gè)本質(zhì)不同。不同之處在于人類社會(huì)關(guān)系中上一屆領(lǐng)導(dǎo)的決策會(huì)受包括個(gè)人因素在內(nèi)的多種因素影響，因此用上級(jí)指派方式無(wú)法選出真正合適的人選，需要以選舉方式加以規(guī)范和制約。但在計(jì)算機(jī)的世界中不會(huì)存在這些不確定因素，對(duì)節(jié)點(diǎn)性能可以有標(biāo)準(zhǔn)統(tǒng)一的評(píng)價(jià)，超級(jí)節(jié)點(diǎn)也不會(huì)徇私舞弊，因此用指派方式能獲得更高的效率。

超級(jí)節(jié)點(diǎn)的功能就是將大網(wǎng)絡(luò)劃分為小網(wǎng)絡(luò)，作為小網(wǎng)絡(luò)對(duì)外的代理，發(fā)現(xiàn)算法僅在超級(jí)節(jié)點(diǎn)之間轉(zhuǎn)發(fā)[14]。因此當(dāng)一個(gè)超級(jí)節(jié)點(diǎn)失效時(shí)，自然應(yīng)當(dāng)從其所在子網(wǎng)中選擇一個(gè)繼任者。SPAA算法的基本思想就是在失效時(shí)間到來(lái)之前，超級(jí)節(jié)點(diǎn)通過(guò)主動(dòng)退位的方式，將超級(jí)節(jié)點(diǎn)的地位和所掌握的資源通過(guò)指派的方式禪讓給子網(wǎng)中另一個(gè)更穩(wěn)定的節(jié)點(diǎn)。由于是主動(dòng)退位而不是忽然失效，超級(jí)節(jié)點(diǎn)有充裕的時(shí)間將自己所掌握的資源轉(zhuǎn)移，并通知子網(wǎng)其他節(jié)點(diǎn)，避免重新投票和重新收集資源的開(kāi)銷。

3 算法實(shí)現(xiàn)

3.1 流程

超級(jí)節(jié)點(diǎn)的首次產(chǎn)生依然采用選舉算法，如果超級(jí)節(jié)點(diǎn)由于預(yù)測(cè)算法失敗而忽然失效，SPAA算法會(huì)退化回重新選舉型算法。

根據(jù)SPAA算法原理，圖2給出使用SPAA算法節(jié)點(diǎn)登錄的流程圖，其中PSnew為更新的節(jié)點(diǎn)存活率時(shí)刻表，用于估計(jì)當(dāng)前節(jié)點(diǎn)在接下來(lái)的一段時(shí)間內(nèi)的存活率變化情況。K為網(wǎng)絡(luò)中對(duì)存活率設(shè)定的閾值，一旦超級(jí)節(jié)點(diǎn)的存活率低于閾值，就要啟動(dòng)禪讓流程。t為從注冊(cè)時(shí)刻之后節(jié)點(diǎn)低于閾值的時(shí)刻，作為禪讓流程中繼任節(jié)點(diǎn)的選擇依據(jù)。

圖2 節(jié)點(diǎn)登錄流程圖

算法說(shuō)明：

（1）普通節(jié)點(diǎn)登錄首先要進(jìn)行初始化，根據(jù)前次登錄情況更新上線概率PSnew。PSnew的計(jì)算方法將會(huì)在3.2節(jié)中具體給出。

（2）然后節(jié)點(diǎn)連接到P2P網(wǎng)絡(luò)，從超級(jí)節(jié)點(diǎn)獲取網(wǎng)絡(luò)的配置閾值K。閾值K的選擇需要根據(jù)具體應(yīng)用的穩(wěn)定性而定，本次仿真實(shí)驗(yàn)得到的一個(gè)經(jīng)驗(yàn)值為8 700左右。如果閾值選取過(guò)高，而會(huì)導(dǎo)致頻繁的超級(jí)節(jié)點(diǎn)更替，選取過(guò)低則容易導(dǎo)致預(yù)測(cè)失敗。

（3）普通節(jié)點(diǎn)計(jì)算本機(jī)存活率低于閾值的時(shí)刻t。根據(jù)普通用戶的作息規(guī)律，實(shí)驗(yàn)的統(tǒng)計(jì)周期為一天，t值即為當(dāng)天節(jié)點(diǎn)下線時(shí)間的估計(jì)值。

（4）節(jié)點(diǎn)將計(jì)算得到的t值注冊(cè)到子網(wǎng)的超級(jí)節(jié)點(diǎn)中，作為超級(jí)節(jié)點(diǎn)禪讓的選擇依據(jù)。同時(shí)進(jìn)行動(dòng)態(tài)身份認(rèn)證，雙方記錄身份密鑰作為禪讓時(shí)廣播繼任節(jié)點(diǎn)信息的身份依據(jù)（密鑰安全認(rèn)證問(wèn)題不作為本文研究重點(diǎn)，在此不做詳細(xì)分析）。

（5）之后普通節(jié)點(diǎn)進(jìn)行正常的P2P通信，并監(jiān)聽(tīng)超級(jí)節(jié)點(diǎn)更換消息。

開(kāi)銷比較：

與普通P2P網(wǎng)絡(luò)節(jié)點(diǎn)登錄相比，SPAA算法增加了K值獲取和t值注冊(cè)幾個(gè)環(huán)節(jié)，只有幾個(gè)字節(jié)的通信數(shù)據(jù)增加。這些數(shù)據(jù)也可以附加在正常P2P登錄通信中，基本沒(méi)有增加開(kāi)銷。并且節(jié)點(diǎn)注冊(cè)時(shí)間都相對(duì)分散，不會(huì)造成網(wǎng)絡(luò)的短期數(shù)據(jù)擁堵。

圖3為使用SPAA算法進(jìn)行超級(jí)節(jié)點(diǎn)禪讓的流程圖。當(dāng)超級(jí)節(jié)點(diǎn)自己的存活概率低于閾值時(shí)，啟動(dòng)禪讓流程。從登陸流程中可以看到，此時(shí)超級(jí)節(jié)點(diǎn)已經(jīng)建立了一份子網(wǎng)節(jié)點(diǎn)的信息列表，記錄了子節(jié)點(diǎn)的存活情況。

圖3 超級(jí)節(jié)點(diǎn)禪讓流程圖

算法說(shuō)明：

（1）原超級(jí)節(jié)點(diǎn)從子節(jié)點(diǎn)列表中查詢剩余在線時(shí)間t最長(zhǎng)的節(jié)點(diǎn)作為繼任超級(jí)節(jié)點(diǎn)。

（2）原超級(jí)節(jié)點(diǎn)對(duì)繼任超級(jí)節(jié)點(diǎn)進(jìn)行任命通知，并將現(xiàn)有在線子節(jié)點(diǎn)列表和身份密鑰信息移交給繼任超級(jí)節(jié)點(diǎn)。

（3）繼任超級(jí)節(jié)點(diǎn)根據(jù)子網(wǎng)節(jié)點(diǎn)列表和身份密鑰信息向所有子網(wǎng)節(jié)點(diǎn)通知超級(jí)節(jié)點(diǎn)已經(jīng)移交。

（4）子網(wǎng)節(jié)點(diǎn)更新超級(jí)節(jié)點(diǎn)信息，并重新與新任超級(jí)節(jié)點(diǎn)商定身份密鑰。

（5）原超級(jí)節(jié)點(diǎn)降級(jí)為普通子節(jié)點(diǎn)，等待失效。

開(kāi)銷比較：

與普通P2P網(wǎng)絡(luò)超級(jí)節(jié)點(diǎn)失效后進(jìn)行重新選舉相比，SPAA算法只增加了一次換屆信息廣播和密鑰更新，只需要建立n次連接（n為子網(wǎng)節(jié)點(diǎn)數(shù)）。同時(shí)省去了重新選舉的網(wǎng)絡(luò)開(kāi)銷，具體開(kāi)銷視選舉算法而定，至少為2n～3n。另外省去了為重新收集索引信息而分散連接子節(jié)點(diǎn)的開(kāi)銷，改為新舊超級(jí)節(jié)點(diǎn)間一次性數(shù)據(jù)拷貝，具體開(kāi)銷視子節(jié)點(diǎn)所含資源量而定。

3.2 節(jié)點(diǎn)存活率計(jì)算

節(jié)點(diǎn)存活率的計(jì)算可以以相對(duì)開(kāi)機(jī)的關(guān)機(jī)時(shí)間或絕對(duì)的關(guān)機(jī)時(shí)刻為時(shí)間單位，根據(jù)上一章中描述的場(chǎng)景，用時(shí)刻更能反映個(gè)人電腦的工作規(guī)律。節(jié)點(diǎn)的開(kāi)關(guān)機(jī)時(shí)刻數(shù)據(jù)可通過(guò)在各節(jié)點(diǎn)中加入服務(wù)程序或守護(hù)進(jìn)程，定時(shí)記錄在線時(shí)間。在系統(tǒng)再次啟動(dòng)時(shí)就能通過(guò)讀取開(kāi)機(jī)記錄，自行統(tǒng)計(jì)到主機(jī)的失效數(shù)據(jù)，并計(jì)算出下線概率。

根據(jù)統(tǒng)計(jì)學(xué)原理，節(jié)點(diǎn)在一次檢測(cè)到的關(guān)機(jī)時(shí)刻周圍關(guān)機(jī)的概率滿足正態(tài)分布：

其中μ為服從正態(tài)分布的均值，應(yīng)用中指檢測(cè)到的單次關(guān)機(jī)時(shí)刻。σ為標(biāo)準(zhǔn)差，反映數(shù)值分布的集中率，σ越小，分布越集中在μ附近，σ越大，分布越分散。

存活率的計(jì)算遵循統(tǒng)計(jì)規(guī)律，統(tǒng)計(jì)結(jié)果是否精確取決于樣本的數(shù)量和質(zhì)量?jī)蓚€(gè)因素。樣本數(shù)量通過(guò)測(cè)量多個(gè)周期的節(jié)點(diǎn)上下線情況來(lái)確保，算法運(yùn)行周期越多越精確。樣本的質(zhì)量指的樣本方差或標(biāo)準(zhǔn)差，即計(jì)算每個(gè)周期中關(guān)機(jī)曲線的變化差異情況。在公式（2）中標(biāo)準(zhǔn)差σ就反映了節(jié)點(diǎn)使用者的作息規(guī)律性。通過(guò)比較一個(gè)節(jié)點(diǎn)多個(gè)周期的關(guān)機(jī)曲線的變化差異情況，可以計(jì)算出節(jié)點(diǎn)的方差和標(biāo)準(zhǔn)差。節(jié)點(diǎn)上下線時(shí)間越規(guī)律，則σ越小。如果σ過(guò)大說(shuō)明該節(jié)點(diǎn)用戶作息時(shí)間極不規(guī)律，不適合作為候補(bǔ)超級(jí)節(jié)點(diǎn)。σ過(guò)大會(huì)導(dǎo)致關(guān)機(jī)概率曲線變緩，影響閾值的選取，在小范圍內(nèi)變化則不影響算法的正確性。由于實(shí)驗(yàn)條件所限，無(wú)法對(duì)真實(shí)用戶樣本方差做大范圍全面統(tǒng)計(jì)，但根據(jù)簡(jiǎn)單的抽樣結(jié)果，有30%的普通用戶主機(jī)的作息規(guī)律能夠滿足統(tǒng)計(jì)質(zhì)量要求。限于篇幅限制和仿真方法的局限，本文沒(méi)有對(duì)樣本方差和標(biāo)準(zhǔn)差的計(jì)算仿真作深入討論，僅假設(shè)參與仿真的節(jié)點(diǎn)都有一致的規(guī)律性。為簡(jiǎn)化計(jì)算，可以將滿足規(guī)律性的節(jié)點(diǎn)的σ值設(shè)為1。

設(shè)已知μ時(shí)刻節(jié)點(diǎn)產(chǎn)生失效事件，某個(gè)時(shí)刻的關(guān)機(jī)率為萬(wàn)分之p，則公式（3）可以計(jì)算出此次失效事件發(fā)生后x時(shí)刻的失效率：

公式（3）為連續(xù)數(shù)值的表達(dá)式，而實(shí)際應(yīng)用中時(shí)刻和計(jì)算機(jī)的存儲(chǔ)數(shù)據(jù)都是離散數(shù)值，因此為便于計(jì)算，將公式轉(zhuǎn)為離散型表達(dá)式。 p(x，μ)的計(jì)算以時(shí)間刻度為單位，由經(jīng)驗(yàn)可知，當(dāng)將一天24 h分成72份，即以每20 min為單位檢測(cè)一次節(jié)點(diǎn)失效情況時(shí)，曲線在前后20 min內(nèi)的變化最陡峭，比較符合實(shí)際中人們的使用情況。則μ的取值范圍為（0，71）。當(dāng)|x-μ|大于4后，正態(tài)分布值小于萬(wàn)分之一，概率影響可以忽略不計(jì)。因此認(rèn)為μ時(shí)刻節(jié)點(diǎn)產(chǎn)生的失效事件，只會(huì)對(duì)(μ-4，μ+4)范圍內(nèi)時(shí)刻的概率產(chǎn)生影響，只需要重新計(jì)算前后4個(gè)點(diǎn)的概率值。

公式（4）將積分表達(dá)式 p(x，μ)轉(zhuǎn)換為近似的離散型求和表達(dá)式 pd(x，μ)：

在時(shí)間刻度單位選定后，μ和x都是有限的離散值，如按當(dāng)前取值范圍，pd(x，μ)有72×9個(gè)。使用時(shí)可以在每個(gè)節(jié)點(diǎn)以μ和x為坐標(biāo)保存一張二維表，在每次初始化啟動(dòng)時(shí)通過(guò)查表計(jì)算出 pdnew(x，μ)，不需要重復(fù)進(jìn)行公式計(jì)算。

設(shè)每個(gè)時(shí)刻節(jié)點(diǎn)的最終存活率為PS，初始情況下令每個(gè)時(shí)刻的值PS(x)=10 000。發(fā)生一次失效事件后導(dǎo)致該事件時(shí)刻周圍9個(gè)時(shí)刻的存活率發(fā)生變化。計(jì)算得新失效率為 pdnew(x，μ)，則新存活率曲線為：

其中λ為新計(jì)算的存活率占總存活率的權(quán)值。λ越大，新事件對(duì)總存活率的影響越大，反之則存活率曲線變化更平緩。

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

4.1節(jié)的實(shí)驗(yàn)通過(guò)實(shí)際統(tǒng)計(jì)主機(jī)的開(kāi)關(guān)機(jī)情況，為算法提供數(shù)據(jù)支持。4.2節(jié)通過(guò)將常用的選舉算法和搭載了SPAA算法的網(wǎng)絡(luò)的失效開(kāi)銷做對(duì)比仿真實(shí)驗(yàn)，說(shuō)明了算法的作用。

4.1 在線概率統(tǒng)計(jì)

首先驗(yàn)證測(cè)試節(jié)點(diǎn)存活率PSnew的計(jì)算準(zhǔn)確性。實(shí)驗(yàn)通過(guò)后臺(tái)服務(wù)，記錄了一臺(tái)主機(jī)兩周的離線情況，再根據(jù)第3章的算法得到主機(jī)的在線時(shí)間概率統(tǒng)分布計(jì)圖。圖4中橫坐標(biāo)為每天開(kāi)機(jī)時(shí)刻，以20 min為單位，縱坐標(biāo)表示每個(gè)時(shí)刻的存活概率，以萬(wàn)分之一為單位。

圖4 主機(jī)在線時(shí)間概率統(tǒng)計(jì)圖

由圖4可知，該主機(jī)在每天17：00和24：00附近關(guān)機(jī)可能性較大，并且近期的關(guān)機(jī)時(shí)間集中在24：00點(diǎn)。

4.2 流量統(tǒng)計(jì)

由于本算法工作在超級(jí)節(jié)點(diǎn)后期，作用是降低由超級(jí)節(jié)點(diǎn)失效導(dǎo)致的控制流量開(kāi)銷，因此無(wú)法與各類選舉算法做直接比較，需要與選舉算法配合工作。若SPAA算法對(duì)超級(jí)節(jié)點(diǎn)的關(guān)機(jī)時(shí)間預(yù)測(cè)失敗，則整個(gè)網(wǎng)絡(luò)退化為重新選舉狀態(tài)。仿真通過(guò)5臺(tái)主機(jī)和虛擬機(jī)建立的一個(gè)chord網(wǎng)絡(luò)，用網(wǎng)絡(luò)抓包工具了記錄網(wǎng)絡(luò)中接入和斷開(kāi)的情況，并將超級(jí)節(jié)點(diǎn)設(shè)在虛擬機(jī)中。通過(guò)關(guān)閉虛擬機(jī)網(wǎng)絡(luò)模擬超級(jí)節(jié)點(diǎn)失效，并將多次抓包記錄導(dǎo)入到matlab程序中作為連接數(shù)基礎(chǔ)值。用matlab程序根據(jù)需要仿真的失效次數(shù)或節(jié)點(diǎn)數(shù)，隨機(jī)選擇一次數(shù)據(jù)作為某次節(jié)點(diǎn)失效連接次數(shù)的累積值，計(jì)算對(duì)應(yīng)使用禪讓方式的連接次數(shù)，然后繪制出坐標(biāo)圖。

選舉算法中通信復(fù)雜度和時(shí)間復(fù)雜度通常是互為矛盾的，為減少選舉時(shí)間通常要以增加連接數(shù)為代價(jià)。表1中給出幾種選舉算法做比較[15]，通信復(fù)雜度反映了選舉算法在流量上的占用量，時(shí)間復(fù)雜度則反映一次選舉所需要通信轉(zhuǎn)發(fā)的時(shí)間計(jì)數(shù)。其中n為網(wǎng)絡(luò)中節(jié)點(diǎn)個(gè)數(shù)，m為節(jié)點(diǎn)組成的聯(lián)通圖中無(wú)向邊的條數(shù)，d為無(wú)向圖的網(wǎng)絡(luò)直徑。通過(guò)比較可以看出各種算法在時(shí)間復(fù)雜度和通信復(fù)雜度上是一種此消彼長(zhǎng)的關(guān)系，使用單一的選舉算法無(wú)法同時(shí)在時(shí)間上和空間上對(duì)超級(jí)節(jié)點(diǎn)網(wǎng)絡(luò)進(jìn)行優(yōu)化。

表1 選舉算法性能比較

由選舉算法性能比較可知，就通信復(fù)雜度而言環(huán)選舉算法是開(kāi)銷最低的，因此用環(huán)選舉算法與SPAA搭配環(huán)選舉算法做對(duì)比實(shí)驗(yàn)更能表現(xiàn)SPAA算法的作用。一次環(huán)選舉算法超級(jí)節(jié)點(diǎn)節(jié)點(diǎn)失效的開(kāi)銷為2n～3n-1，加上重新收集節(jié)點(diǎn)索引開(kāi)銷為n，則總開(kāi)銷為3n～4n-1。SPAA算法開(kāi)始會(huì)預(yù)測(cè)失敗，經(jīng)過(guò)兩個(gè)周期的失效信息記錄后就能進(jìn)行失效概率的計(jì)算，但需要5～7次周期后節(jié)點(diǎn)的失效曲線才不會(huì)出現(xiàn)大幅波動(dòng)。預(yù)測(cè)失敗時(shí)算法退化為重新環(huán)選舉算法。預(yù)測(cè)成功則只需要向網(wǎng)絡(luò)廣播一次更換超級(jí)節(jié)點(diǎn)消息，所需開(kāi)銷為n。

實(shí)驗(yàn)時(shí)為提高速度，將節(jié)點(diǎn)影響周期單位縮小為標(biāo)準(zhǔn)的萬(wàn)分之一，即每1.2 s為一個(gè)時(shí)刻，約1.5 min為一周期。參數(shù)n為一次仿真中P2P子網(wǎng)的節(jié)點(diǎn)總數(shù)，參數(shù)t為一次仿真時(shí)超級(jí)節(jié)點(diǎn)的失效次數(shù)，參數(shù)y為統(tǒng)計(jì)在網(wǎng)絡(luò)中超級(jí)節(jié)點(diǎn)失效到新超級(jí)節(jié)點(diǎn)產(chǎn)生所需要的網(wǎng)絡(luò)連接總次數(shù)。

圖5反映了在擁有相同節(jié)點(diǎn)的P2P網(wǎng)絡(luò)中，在兩種算法下超級(jí)節(jié)點(diǎn)失效次數(shù)與網(wǎng)絡(luò)開(kāi)銷的關(guān)系。其中O形線條代表在未加入SPAA算法前節(jié)點(diǎn)環(huán)選舉失效次數(shù)和網(wǎng)絡(luò)失效開(kāi)銷的關(guān)系，+號(hào)線代表加入SPAA算法后二者的增長(zhǎng)關(guān)系。

圖5 超級(jí)節(jié)點(diǎn)失效次數(shù)與網(wǎng)絡(luò)失效開(kāi)銷關(guān)系圖

由圖5可見(jiàn)，隨著網(wǎng)絡(luò)超級(jí)節(jié)點(diǎn)失效次數(shù)增大，采用SPAA算法的網(wǎng)絡(luò)所花費(fèi)的開(kāi)銷約等于重新選舉開(kāi)銷的1/3，與理論推導(dǎo)結(jié)論相符。

圖6反映了在相同超級(jí)節(jié)點(diǎn)失效次數(shù)下，兩種算法下網(wǎng)絡(luò)節(jié)點(diǎn)規(guī)模與網(wǎng)絡(luò)開(kāi)銷的關(guān)系。其中O形線段表示了在未加入SPAA算法前網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)量增加與網(wǎng)絡(luò)失效開(kāi)銷的比例關(guān)系，+號(hào)線段代表加入SPAA算法后二者的比例關(guān)系。

圖6 網(wǎng)絡(luò)節(jié)點(diǎn)規(guī)模網(wǎng)絡(luò)失效開(kāi)銷關(guān)系圖

由圖6可見(jiàn)，隨著網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)增加，采用禪讓機(jī)制的網(wǎng)絡(luò)所花費(fèi)的開(kāi)銷約等于重新選舉開(kāi)銷的1/3，與理論推導(dǎo)結(jié)論相符。

5 結(jié)束語(yǔ)

本文針對(duì)P2P應(yīng)用中超級(jí)節(jié)點(diǎn)失效時(shí)帶來(lái)網(wǎng)絡(luò)波動(dòng)問(wèn)題，提出了一種基于用戶行為統(tǒng)計(jì)規(guī)律的超級(jí)節(jié)點(diǎn)禪讓機(jī)制。在該機(jī)制中，首先通過(guò)統(tǒng)計(jì)節(jié)點(diǎn)的歷史失效情況，計(jì)算出在線概率分布曲線。再選取在線可能性最長(zhǎng)的節(jié)點(diǎn)作為超級(jí)節(jié)點(diǎn)。當(dāng)超級(jí)節(jié)點(diǎn)在線概率低于閾值時(shí)，通過(guò)禪讓機(jī)制選取網(wǎng)絡(luò)中在線率最長(zhǎng)的節(jié)點(diǎn)作為新超級(jí)節(jié)點(diǎn)。從而避免再次選舉帶來(lái)的網(wǎng)絡(luò)開(kāi)銷。仿真實(shí)驗(yàn)和結(jié)果表明，在節(jié)點(diǎn)作息時(shí)間規(guī)則的情況下，采用禪讓機(jī)制能夠有效減小由超級(jí)節(jié)點(diǎn)失效帶來(lái)的網(wǎng)絡(luò)開(kāi)銷。

由于研究精力和實(shí)驗(yàn)條件有限，本文提出的方法存在一些不足。SPAA算法較適用于由個(gè)人用戶組成的P2P網(wǎng)絡(luò)（如電驢的kad網(wǎng)絡(luò)），目前的方法是統(tǒng)計(jì)節(jié)點(diǎn)開(kāi)機(jī)、關(guān)機(jī)的規(guī)律，對(duì)用戶的作息規(guī)律有很大依賴，應(yīng)用上存在一定的局限性。節(jié)點(diǎn)間由于減少了控制流量通信，可能導(dǎo)致較大的信息不同步。這些問(wèn)題有待進(jìn)一步研究。

[1]譚義紅，羅立，林亞平，等.超級(jí)節(jié)點(diǎn)網(wǎng)絡(luò)的構(gòu)建與搜索機(jī)制研究[J].小型微型計(jì)算機(jī)系統(tǒng)，2008，29（11）：1-4.

[2]張國(guó)強(qiáng)，唐明董，程蘇琦，等.P2P流量?jī)?yōu)化[J].中國(guó)科學(xué)：信息科學(xué)，2012，42（1）：1-5.

[3]Luis G E，Keith W R，Guillaume U K，et al.Hierarchical peer-to-peerlook-up services[C]//Proc ofIEEE Infocom，2003：1-3.

[4]陳水平，吳開(kāi)貴.P2P網(wǎng)絡(luò)基于CPU動(dòng)態(tài)處理能力的超級(jí)節(jié)點(diǎn)選取[J].計(jì)算機(jī)工程與應(yīng)用，2011，47（19）：1-2.

[5]相有桓，熊焰，苗付友.移動(dòng)P2P網(wǎng)絡(luò)中超級(jí)節(jié)點(diǎn)的選擇[J].計(jì)算機(jī)工程，2010，36（10）：1-5.

[6]楊壽保，許通，胡云.用戶需求適應(yīng)的P2P超級(jí)節(jié)點(diǎn)選取機(jī)制[J].電子科技大學(xué)學(xué)報(bào)，2009，38（3）：1-4.

[7]劉玉枚，楊壽保，陳萬(wàn)明，等.P2P系統(tǒng)中基于信譽(yù)感知的超級(jí)節(jié)點(diǎn)選擇算法研究[J].中國(guó)科學(xué)院研究生院學(xué)報(bào)，2008，25（2）：1-6.

[8]余兆.基于ISP主動(dòng)參與的P2P下載流量?jī)?yōu)化研究[D].武漢：湖北工業(yè)大學(xué)，2011：3-7.

[9]梁卓明，黃偉強(qiáng)，鄭凱.P2P流量本地優(yōu)化綜合機(jī)制[J].計(jì)算機(jī)系統(tǒng)應(yīng)用，2012，21（1）：1-5.

[10]Tomozei D C，Massoulie L.Flow control for cost-efficient peer-to-peer streaming[C]//Proc of IEEE Infocom，2010：1-6.

[11]柴勇，劉一松，曹陽(yáng).基于分層P2P系統(tǒng)的失效恢復(fù)機(jī)制的改進(jìn)[J].微計(jì)算機(jī)信息，2006，30（22）：1-5.

[12]李瑾，周竹榮.基于用戶行為和社區(qū)發(fā)現(xiàn)的P2P資源檢索方法[J].計(jì)算機(jī)工程與應(yīng)用，2012，48（21）：1-2.

[13]Fernandez A，Jimenez E，Raynal M.Eventual leader election with weak assumptions on initial knowledge，communication reliability，and synchrony[C]//Proceedings of Dependable Systems and Networks，2006：165-179.

[14]廖小偉，王敏，王曉國(guó).一種基于超級(jí)節(jié)點(diǎn)的半分布式P2P系統(tǒng)改進(jìn)策略[J].計(jì)算機(jī)應(yīng)用與軟件，2007，11（24）：1-2.

[15]杜麗娟，余鎮(zhèn)危.分布式超級(jí)節(jié)點(diǎn)選舉算法[J].計(jì)算機(jī)工程與應(yīng)用，2011，47（14）：1-5.

基于行為特征的超級(jí)節(jié)點(diǎn)節(jié)流算法研究

何 欽，劉 丹，周 明

HE Qin,LIU Dan,ZHOU Ming

Research Institute of Electronic Science and Technology,University of Electronic Science and Technology of China,Chengdu 611731,China

In a super-peers-based P2P network,if super-peers fail or leave,it may bring many problems,such as resource losing, network topology changing and increasing bandwidth occupancy for re-election.To solve these problem,this paper brings up a super-peers abdicate algorithm based on user’s behavior characteristic.According to statistic characteristic of the node failure, the SPAA algorithm can forecast the node leave time and appoint next super-peer.Simulation and analysis show that the SPAA algorithm can effectively reduce the net churn by super-peer failure and reduce network traffic.

super-peer;node failure;abdicate algorithm;reduce network traff

針對(duì)P2P網(wǎng)絡(luò)中超級(jí)節(jié)點(diǎn)失效時(shí)帶來(lái)的資源流失、網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)變化和重新選舉網(wǎng)絡(luò)開(kāi)銷增加等問(wèn)題，提出了一種基于用戶行為特征統(tǒng)計(jì)的超級(jí)節(jié)點(diǎn)禪讓算法。根據(jù)節(jié)點(diǎn)的失效統(tǒng)計(jì)特征預(yù)估失效時(shí)間，預(yù)先指定繼任超級(jí)節(jié)點(diǎn)。仿真實(shí)驗(yàn)對(duì)比結(jié)果表明，該算法可以有效降低超級(jí)節(jié)點(diǎn)失效時(shí)帶來(lái)的網(wǎng)絡(luò)波動(dòng)，降低網(wǎng)絡(luò)流量消耗。

超級(jí)節(jié)點(diǎn)；節(jié)點(diǎn)失效；退位算法；降低網(wǎng)絡(luò)流量

A

TP393.0

10.3778/j.issn.1002-8331.1211-0245

HE Qin,LIU Dan,ZHOU Ming.Research on algorithm for low bandwidth super-peers network based on user’s behavior characteristic.Computer Engineering and Applications,2013,49（11）：61-65.

寧波市科技局工業(yè)、農(nóng)業(yè)與民生領(lǐng)域重大科技攻關(guān)項(xiàng)目（No.2011C51007）。

何欽（1987—），男，碩士研究生，主要研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)安全及開(kāi)發(fā)；劉丹（1969—），男，博士，副教授，主要研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)安全和物聯(lián)網(wǎng)開(kāi)發(fā)；周明（1976—），男，研究員。E-mail：hunterheqin@163.com

2012-11-21

2013-01-23

1002-8331（2013）11-0061-05