成衛(wèi)青 張 蕾

①(南京郵電大學(xué)計(jì)算機(jī)學(xué)院 南京 210023)

②(東南大學(xué)計(jì)算機(jī)網(wǎng)絡(luò)和信息集成教育部重點(diǎn)實(shí)驗(yàn)室 南京 211189)

1 引言

Gossip算法是一個(gè)依靠感染行為傳播信息的算法，具有簡(jiǎn)單、高效、健壯、可擴(kuò)展性和抗干擾能力強(qiáng)的特點(diǎn)，應(yīng)用場(chǎng)景十分廣泛。大型分布式系統(tǒng)常使用Gossip算法進(jìn)行信息擴(kuò)散，隨著對(duì)等網(wǎng)絡(luò)的發(fā)展，其應(yīng)用領(lǐng)域不斷擴(kuò)大。Gossip算法的應(yīng)用有數(shù)據(jù)庫(kù)復(fù)制[1]、聚合計(jì)算[2]、網(wǎng)絡(luò)拓?fù)錁?gòu)造[3,4]、數(shù)據(jù)挖掘[5]、故障檢測(cè)[6]、網(wǎng)絡(luò)監(jiān)控[7]等。

Gossip算法常用于聚合計(jì)算和達(dá)成共識(shí)。文獻(xiàn)[8]提出了一種新的基于Gossip算法的聚合計(jì)算方案，在O(log2n)輪通信中發(fā)送O(nlog2n)的消息。文獻(xiàn)[9]提出了一種局部平均信息交換算法來(lái)計(jì)算網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的初始測(cè)量值的全局一致性；在每一輪擴(kuò)散過(guò)程中，每個(gè)節(jié)點(diǎn)與所有相鄰節(jié)點(diǎn)交流，計(jì)算和交換局部平均值，使所有節(jié)點(diǎn)都能很快地以分布式方式逐漸達(dá)到全局一致。針對(duì)現(xiàn)有共識(shí)算法對(duì)拜占庭節(jié)點(diǎn)的容錯(cuò)能力低且對(duì)區(qū)塊鏈系統(tǒng)可擴(kuò)展性差的問(wèn)題，文獻(xiàn)[10]提出了基于Gossip的拜占庭共識(shí)算法，使系統(tǒng)可以容忍小于一半的節(jié)點(diǎn)為拜占庭節(jié)點(diǎn)。文獻(xiàn)[11]提出了一種在不可靠網(wǎng)絡(luò)中估計(jì)未知參數(shù)的異步廣播Gossip算法，該算法允許新的傳感器加入，舊的傳感器離開(kāi)，并能容忍鏈路故障。

Gossip算法可用于網(wǎng)絡(luò)拓?fù)錁?gòu)造。如文獻(xiàn)[4]提出了一個(gè)支持多個(gè)交互參與者和大量消費(fèi)者的自組織流媒體解決方案，該方案利用基于Gossip的覆蓋網(wǎng)的可伸縮性和健壯性來(lái)構(gòu)建延遲感知的流播樹(shù)，以便向多個(gè)用戶提供多個(gè)不同的流。Gossip算法可用于數(shù)據(jù)挖掘。例如文獻(xiàn)[5]針對(duì)淘寶等大型推薦系統(tǒng)中冷啟動(dòng)和稀疏評(píng)價(jià)嚴(yán)重降低推薦性能的問(wèn)題，提出了一種基于圓桌流言算法的稀疏信任挖掘方法。文獻(xiàn)[12]提出了基于Gossip的非結(jié)構(gòu)化P2P網(wǎng)絡(luò)分布式聚類算法，不依賴中央服務(wù)器來(lái)執(zhí)行數(shù)據(jù)聚類任務(wù)，也不需要同步操作。文獻(xiàn)[13]提出了一種能夠提高測(cè)量精度的基于Gossip算法的數(shù)據(jù)聚類算法。還有其他一些應(yīng)用，比如文獻(xiàn)[14]提出了一種新的基于Gossip的信令傳播方法，文獻(xiàn)[15]以無(wú)線傳感器網(wǎng)絡(luò)中的分布式定位問(wèn)題為研究背景，成功地將成對(duì)和廣播Gossip算法引入到原有定位算法框架之中。為了加速服務(wù)器群間的多批數(shù)據(jù)傳輸，文獻(xiàn)[16]提出了一種編碼排列流言算法，研究了最佳的塊劃分、批劃分和分批調(diào)度策略，以達(dá)到最小的廣播完成時(shí)間。

影響Gossip算法性能的因素有很多，主要因素有時(shí)間模型、網(wǎng)絡(luò)結(jié)構(gòu)、信息交互模式以及每個(gè)周期、每個(gè)節(jié)點(diǎn)選擇聯(lián)系的節(jié)點(diǎn)個(gè)數(shù)等。因此Gossip算法只要稍作改變就可以適應(yīng)很多應(yīng)用場(chǎng)景。傳統(tǒng)Gossip算法最大的缺點(diǎn)是冗余，冗余通信會(huì)造成對(duì)網(wǎng)路帶寬和計(jì)算機(jī)資源的過(guò)多占用，因此降低Gossip算法的冗余度非常重要。本文的目的是降低Gossip算法的冗余度并提高算法的收斂速度。本文的主要貢獻(xiàn)是：(1)提出一種二進(jìn)制指數(shù)退避的Gossip算法(Gossip with Binary Exponential Backoff，BEBG)，有效降低了算法的網(wǎng)絡(luò)負(fù)載，但BEBG存在邊緣節(jié)點(diǎn)問(wèn)題。(2)提出一個(gè)引入Pull的BEBG改進(jìn)算法PBEBG，以及一個(gè)增加向鄰居節(jié)點(diǎn)Push的BEBG改進(jìn)算法NBEBG，解決邊緣節(jié)點(diǎn)問(wèn)題并提高算法的收斂速度。

2 Gossip算法概述

Gossip算法是一種非常著名的信息傳播算法，其信息傳播過(guò)程和圖的著色類似。假設(shè)網(wǎng)絡(luò)中只有兩種顏色的節(jié)點(diǎn)，一種是已著色節(jié)點(diǎn)，一種是未著色節(jié)點(diǎn)，已著色節(jié)點(diǎn)是當(dāng)前網(wǎng)絡(luò)狀態(tài)下已經(jīng)收到信息的節(jié)點(diǎn)，未著色節(jié)點(diǎn)為網(wǎng)絡(luò)中沒(méi)有收到信息的節(jié)點(diǎn)。一個(gè)節(jié)點(diǎn)在網(wǎng)絡(luò)中只有兩種狀態(tài)，要么是已著色的，要么是未著色的。剛開(kāi)始，網(wǎng)絡(luò)中只有一個(gè)已著色節(jié)點(diǎn)，第1輪這個(gè)節(jié)點(diǎn)會(huì)隨機(jī)選擇一個(gè)節(jié)點(diǎn)發(fā)送信息。接下來(lái)的每一輪次，網(wǎng)絡(luò)中已著色的節(jié)點(diǎn)會(huì)隨機(jī)選擇另一節(jié)點(diǎn)發(fā)送信息。假設(shè)未著色節(jié)點(diǎn)為紅色，已著色節(jié)點(diǎn)為藍(lán)色。剛開(kāi)始網(wǎng)絡(luò)中只有一個(gè)藍(lán)色節(jié)點(diǎn)，隨著網(wǎng)絡(luò)狀態(tài)的變化，藍(lán)色節(jié)點(diǎn)會(huì)變得越來(lái)越多。當(dāng)藍(lán)色完全覆蓋了整個(gè)網(wǎng)絡(luò)，意味著信息已經(jīng)傳播到網(wǎng)絡(luò)中的所有節(jié)點(diǎn)。

2.1 時(shí)間模型

時(shí)間模型是Gossip算法的基礎(chǔ)，不同的時(shí)間模型有著不同的研究方式。目前常用的時(shí)間模型有兩種，即同步時(shí)間模型和異步時(shí)間模型。時(shí)間模型是對(duì)系統(tǒng)時(shí)間的簡(jiǎn)單假設(shè)，現(xiàn)實(shí)的時(shí)間模型更為復(fù)雜。

同步時(shí)間模型：將時(shí)間分為均勻的時(shí)隙，每個(gè)時(shí)隙，節(jié)點(diǎn)選擇與自己的鄰居節(jié)點(diǎn)進(jìn)行通信，鄰居節(jié)點(diǎn)選擇的過(guò)程是隨機(jī)且相互獨(dú)立的。同步模型下，節(jié)點(diǎn)與節(jié)點(diǎn)之間的信息交換均在同一時(shí)刻進(jìn)行，信息的發(fā)送與接收都在該時(shí)隙內(nèi)同步完成，因此整個(gè)分布式網(wǎng)絡(luò)中需要一個(gè)全局的時(shí)鐘來(lái)同步各個(gè)節(jié)點(diǎn)的時(shí)間。為了簡(jiǎn)化分析過(guò)程，本文設(shè)定的時(shí)間模型是同步的。

異步時(shí)間模型：網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)都有自己的時(shí)鐘，按照自己的節(jié)奏發(fā)送信息。節(jié)點(diǎn)根據(jù)自己時(shí)鐘來(lái)發(fā)起信息交換過(guò)程，節(jié)點(diǎn)之間的信息發(fā)送是互相獨(dú)立的。異步時(shí)間模型不需要全局時(shí)鐘的同步，這種異步的Gossip算法在分布式環(huán)境下更容易實(shí)現(xiàn)。

2.2 Gossip算法信息交換方式

假設(shè)A和B是大規(guī)模分布式系統(tǒng)中的兩個(gè)節(jié)點(diǎn)。Gossip算法中A節(jié)點(diǎn)和B節(jié)點(diǎn)信息交換的方式一般有3種：Push, Pull, Push&Pull。

Push：擁有更新信息的節(jié)點(diǎn)A發(fā)起信息交換，在網(wǎng)絡(luò)中隨機(jī)選擇一個(gè)節(jié)點(diǎn)B，A節(jié)點(diǎn)把自己的更新信息發(fā)送給B節(jié)點(diǎn)，B節(jié)點(diǎn)收到信息后更新本地信息。

Pull：未著色節(jié)點(diǎn)A在網(wǎng)絡(luò)中隨機(jī)選擇一個(gè)節(jié)點(diǎn)B，要求從B節(jié)點(diǎn)那里獲得更新信息。

Push&Pull：節(jié)點(diǎn)之間互相發(fā)送更新信息給對(duì)方。A節(jié)點(diǎn)在網(wǎng)絡(luò)中隨機(jī)選擇一個(gè)節(jié)點(diǎn)B，A節(jié)點(diǎn)將自己的更新信息發(fā)送給B節(jié)點(diǎn)，B節(jié)點(diǎn)接收到信息后更新本地信息，并將自己的更新信息發(fā)送給A節(jié)點(diǎn)，A節(jié)點(diǎn)收到B節(jié)點(diǎn)的信息后也要更新本地信息。

總的來(lái)說(shuō)，采用Push方式，信息傳播先快后慢，Pull方式相反，先慢后快。Push&Pull將兩種方式結(jié)合起來(lái)，這種方式速度是最快的，但也是最消耗網(wǎng)絡(luò)資源的。

2.3 相關(guān)研究

文獻(xiàn)[17]為Gossip算法提供一個(gè)簡(jiǎn)單而通用的框架，并使用該框架來(lái)描述Gossip算法在不同領(lǐng)域中的解決方案。該文獻(xiàn)將Gossip算法的過(guò)程抽象為3個(gè)步驟：節(jié)點(diǎn)的選擇、信息交換和數(shù)據(jù)處理。選擇節(jié)點(diǎn)的方式有很多種，一般情況下，每個(gè)周期節(jié)點(diǎn)隨機(jī)選擇另一個(gè)節(jié)點(diǎn)向其發(fā)送信息。但是，節(jié)點(diǎn)選擇向哪些節(jié)點(diǎn)發(fā)送信息，每個(gè)周期發(fā)送幾條信息，節(jié)點(diǎn)發(fā)送信息的概率都是可以隨著應(yīng)用場(chǎng)景的改變而改變的。

Gossip算法可以容忍數(shù)據(jù)包丟失和鏈路崩潰，盡管流言傳播具有很高的容錯(cuò)性和可擴(kuò)展性，但它仍會(huì)受到網(wǎng)絡(luò)性能下降和網(wǎng)絡(luò)流量負(fù)載過(guò)大的影響。因此對(duì)于必須同時(shí)提供可靠性和及時(shí)性的應(yīng)用，尤其在易擁塞的網(wǎng)絡(luò)中它可能不是最優(yōu)的。文獻(xiàn)[18]通過(guò)確定哪些節(jié)點(diǎn)應(yīng)該接收流言消息來(lái)改進(jìn)流言傳播方案，提出采用分布式策略學(xué)習(xí)邏輯來(lái)高效地確定這些節(jié)點(diǎn)，文中提出了兩個(gè)啟發(fā)式方案：一個(gè)是基于QoS(Quality of Service)選擇，依據(jù)損失模式，從根節(jié)點(diǎn)開(kāi)始沿著路徑選擇鏈路質(zhì)量差的節(jié)點(diǎn)；另一個(gè)是基于拓?fù)洌鶕?jù)位置選擇組播樹(shù)內(nèi)更偏離根的節(jié)點(diǎn)。

為了提高算法的收斂速度，以及將信息傳播到網(wǎng)絡(luò)上所有的節(jié)點(diǎn)，文獻(xiàn)[19]提出了Corrected Gossip算法，將蒙特卡羅式流言和確定性修正相結(jié)合，構(gòu)造一個(gè)拉斯維加斯式的可靠廣播，在執(zhí)行Gossip算法有限周期后進(jìn)入修正階段，保證以低成本到達(dá)所有節(jié)點(diǎn)。該文獻(xiàn)將未被感染的節(jié)點(diǎn)稱為未著色的節(jié)點(diǎn)。文獻(xiàn)[20]在布爾網(wǎng)絡(luò)模型的基礎(chǔ)上提出了布爾流言網(wǎng)絡(luò)模型。在布爾網(wǎng)絡(luò)中，每個(gè)節(jié)點(diǎn)只有兩種狀態(tài)“開(kāi)” 和“關(guān)”，而在某個(gè)時(shí)刻每個(gè)節(jié)點(diǎn)只能處于其中一種狀態(tài)。節(jié)點(diǎn)之間相互作用，節(jié)點(diǎn)的狀態(tài)隨之發(fā)生改變。文獻(xiàn)中的網(wǎng)絡(luò)模型只考慮一對(duì)節(jié)點(diǎn)間的相互作用。布爾流言網(wǎng)絡(luò)模型是布爾網(wǎng)絡(luò)模型的一種特殊形式，可以應(yīng)用在基因調(diào)控、社會(huì)意見(jiàn)問(wèn)卷、病毒傳播等多個(gè)領(lǐng)域。文獻(xiàn)[21]研究了一種網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)目為奇數(shù)的Gossip模型，深入研究了同步奇Gossip算法模型和異步奇Gossip算法模型的時(shí)間下界，給出了n=2k-1 時(shí)的一個(gè)最優(yōu)同步算法。

為了解決C/S架構(gòu)信息系統(tǒng)采用的中心化數(shù)據(jù)同步模式導(dǎo)致的服務(wù)器性能下降，并影響信息系統(tǒng)整體性能的問(wèn)題，文獻(xiàn)[22]改進(jìn)了Gossip算法以解決其冗余通信量大且收斂速度慢的問(wèn)題，并提出了基于改進(jìn)Gossip算法的數(shù)據(jù)同步方法。該方法將Gossip算法與選舉算法中的環(huán)算法相結(jié)合，提高了數(shù)據(jù)同步效率，減少數(shù)據(jù)同步對(duì)系統(tǒng)整體性能的影響。文獻(xiàn)[23]研究和分析了兩種自然的基于流言傳播的發(fā)現(xiàn)過(guò)程，即基于Push和Pull的發(fā)現(xiàn)過(guò)程，對(duì)這兩個(gè)隨機(jī)過(guò)程在無(wú)向n節(jié)點(diǎn)圖及在有向n節(jié)點(diǎn)圖中的收斂時(shí)間進(jìn)行了較嚴(yán)密的分析。

3 基于二進(jìn)制指數(shù)退避的Gossip算法

以太網(wǎng)介質(zhì)訪問(wèn)控制協(xié)議CSMA/CD要求站點(diǎn)在發(fā)送數(shù)據(jù)之前要先監(jiān)聽(tīng)信道，監(jiān)聽(tīng)到信道空閑才發(fā)送數(shù)據(jù)，還需要邊發(fā)邊進(jìn)行沖突檢測(cè)，一旦檢測(cè)到?jīng)_突，就采用二進(jìn)制指數(shù)退避算法來(lái)決定站點(diǎn)再次嘗試發(fā)送數(shù)據(jù)前要退避的時(shí)間，經(jīng)過(guò)退避時(shí)間后再重復(fù)上述步驟。退避時(shí)間設(shè)定方法：從整數(shù)集合[0,20,21,···,(2k-1)]中隨機(jī)取出一個(gè)數(shù)r，其中k=min(沖突次數(shù),10)；退避時(shí)間=2τr，其中2τ是局域網(wǎng)端到端往返時(shí)延。使用隨機(jī)退避時(shí)間是為了降低沖突站點(diǎn)再次同時(shí)嘗試發(fā)送數(shù)據(jù)而又發(fā)生沖突的概率。

為降低冗余，減少Gossip算法中節(jié)點(diǎn)在信息傳播過(guò)程中發(fā)送的信息量，本文借鑒二進(jìn)制指數(shù)退避算法的思想對(duì)經(jīng)典Gossip算法(classic Gossip Algorithm, GA)做改進(jìn)，提出二進(jìn)制指數(shù)退避的Gossip算法BEBG。該算法的思想是節(jié)點(diǎn)重復(fù)收到同一信息時(shí)降低傳播信息的概率，重復(fù)收到同一信息的次數(shù)越多，傳播該信息的概率越低。此外，針對(duì)BEBG存在邊緣節(jié)點(diǎn)的不足，從兩個(gè)方面對(duì)其進(jìn)行改進(jìn)，進(jìn)一步提出了PBEBG和NBEBG兩個(gè)算法。

3.1 二進(jìn)制指數(shù)退避的Gossip算法

BEBG與GA兩算法最大的不同在于，GA中，每一輪已著色節(jié)點(diǎn)向外傳播更新信息的概率恒為1，而B(niǎo)EBG中已著色節(jié)點(diǎn)向外傳播更新信息的概率是變化的。這個(gè)概率的大小與節(jié)點(diǎn)的網(wǎng)絡(luò)狀態(tài)有關(guān)，一條新的更新信息在網(wǎng)絡(luò)中流傳，節(jié)點(diǎn)重復(fù)收到這條信息的輪數(shù)越多，節(jié)點(diǎn)向外傳播這條信息的概率越低。這與現(xiàn)實(shí)中人們轉(zhuǎn)發(fā)新聞情形類似，對(duì)于廣為流傳的信息人們會(huì)失去傳播它的欲望。

BEBG中，節(jié)點(diǎn)向外傳播信息的概率p是一個(gè)變量，每個(gè)輪次一個(gè)節(jié)點(diǎn)的p值可能不一樣；未著色節(jié)點(diǎn)的p值設(shè)為0，剛收到信息的節(jié)點(diǎn)的p值設(shè)為1。根節(jié)點(diǎn)和第1次收到信息的節(jié)點(diǎn)向外傳播信息的概率為1，而未著色節(jié)點(diǎn)向外傳播信息的概率為0。

3.1.1 BEBG的信息發(fā)送過(guò)程

第1輪，只有根節(jié)點(diǎn)有新的更新信息，根節(jié)點(diǎn)隨機(jī)選擇一個(gè)其他節(jié)點(diǎn)以概率p=1向其傳播更新信息。第1輪結(jié)束時(shí)，網(wǎng)絡(luò)中一共有兩個(gè)已著色節(jié)點(diǎn)。第2輪，這兩個(gè)已著色節(jié)點(diǎn)各自先根據(jù)自己向外傳播信息的概率p決定是否向外發(fā)送更新信息，如果是，隨機(jī)選擇一個(gè)除自己以外的節(jié)點(diǎn)向其傳播更新信息。以此類推，若干輪后，網(wǎng)絡(luò)中所有節(jié)點(diǎn)可能都被著色了。節(jié)點(diǎn)發(fā)送信息的過(guò)程是嚴(yán)格全局時(shí)鐘同步的，每個(gè)周期節(jié)點(diǎn)只隨機(jī)選擇1個(gè)節(jié)點(diǎn)向其傳播1次更新信息。表1為BEBG的信息發(fā)送過(guò)程，節(jié)點(diǎn)向外傳播信息的概率p由節(jié)點(diǎn)接收更新信息的情況決定，初始化時(shí)，根節(jié)點(diǎn)的p值為1，其他節(jié)點(diǎn)的p值為0。

表1 BEBG算法的信息發(fā)送過(guò)程(算法1)

3.1.2 BEBG的信息接收過(guò)程

算法的接收過(guò)程比發(fā)送過(guò)程復(fù)雜，見(jiàn)表2。如果本輪中收到了更新信息，第1次收到信息的節(jié)點(diǎn)將自己的p值由0變?yōu)?，而其他收到信息的節(jié)點(diǎn)(已著色節(jié)點(diǎn))將自己的p值調(diào)為原來(lái)的1/2，即下一輪向外傳播信息的概率變?yōu)樵瓉?lái)的1/2。例如，如果節(jié)點(diǎn)A在第4輪中收到更新信息，并且它在第1和第3輪中也曾收到過(guò)相同的信息，即收到相同信息的輪次一共為3輪，則節(jié)點(diǎn)A在第5輪中向外傳播信息的概率p為1/4，節(jié)點(diǎn)A在第1-第5輪的p分別為0,1, 1, 1/2, 1/4。以此類推，如果某節(jié)點(diǎn)收到相同信息的輪次一共為4輪，那么在下一個(gè)輪次該節(jié)點(diǎn)的p為1/8。為了避免算法后期無(wú)節(jié)點(diǎn)發(fā)送信息導(dǎo)致出現(xiàn)邊緣節(jié)點(diǎn)(算法結(jié)束后還是未著色節(jié)點(diǎn))的情況，本文給已著色節(jié)點(diǎn)傳播信息的概率p設(shè)置了一個(gè)下限值：1/32。

每一輪中，節(jié)點(diǎn)傳播信息的概率只有兩種可能，不變或變?yōu)樵瓉?lái)的1/2。如表2，設(shè)置一個(gè)節(jié)點(diǎn)接收超時(shí)時(shí)間，超過(guò)一定時(shí)間節(jié)點(diǎn)未收到信息，表示本輪該節(jié)點(diǎn)的接收過(guò)程已經(jīng)結(jié)束，然后線程根據(jù)本輪是否收到信息、是否是第1次收到、p有無(wú)達(dá)到下限來(lái)將p減半或維持不變。

表2 BEBG算法的信息接收過(guò)程(算法2)

每一輪BEBG先執(zhí)行信息發(fā)送過(guò)程(算法1)再執(zhí)行信息接收過(guò)程(算法2)。在接收過(guò)程中，當(dāng)節(jié)點(diǎn)發(fā)現(xiàn)本輪重復(fù)收到之前輪次收到過(guò)的信息時(shí)，除非p已達(dá)到下限，否則p減半，這里改變的是節(jié)點(diǎn)下一輪傳播信息的概率。每一輪一個(gè)節(jié)點(diǎn)收到信息的次數(shù)是不確定的，可能零次、一次或多次，但是每輪至多只改變一次p的值。

3.1.3 BEBG算法理論分析

本小節(jié)分析采用BEBG傳播信息，每一輪所有節(jié)點(diǎn)發(fā)送的總信息量以及信息傳播規(guī)律。設(shè)未著色節(jié)點(diǎn)為0類節(jié)點(diǎn)，C0(T)為在T輪次初始尚未著色的節(jié)點(diǎn)總數(shù)，它們向外傳播信息的概率p0= 0；一個(gè)節(jié)點(diǎn)若在T輪次之前累計(jì)在i個(gè)輪次中都接收到了信息，則為i類節(jié)點(diǎn)，Ci(T)表示在T輪次i類節(jié)點(diǎn)總數(shù)，i類節(jié)點(diǎn)向外傳播信息的概率Pi= 1/2i-1；其中i=1,2,3,4,5；一個(gè)節(jié)點(diǎn)若在T輪次之前累計(jì)在大于等于6個(gè)輪次中都接收到了信息，則為6類節(jié)點(diǎn)，C6(T)表示在T輪次6類節(jié)點(diǎn)總數(shù)，6類節(jié)點(diǎn)向外傳播信息的概率P6=1/32。C(T)為在T輪次初始已著色節(jié)點(diǎn)的總數(shù)，等于1到6類節(jié)點(diǎn)的總和。C(1)=1,C1(1)=1, C2(1)=C3(1)=C4(1)=C5(1)=C6(1)=0。

設(shè)當(dāng)前輪次為T，在T輪次向外傳播信息的節(jié)點(diǎn)數(shù)S(T)預(yù)期為

顯然，S(1)=1。

設(shè)網(wǎng)絡(luò)中共有N個(gè)節(jié)點(diǎn)，假設(shè)節(jié)點(diǎn)A是一個(gè)將向外發(fā)送信息的已著色節(jié)點(diǎn)，節(jié)點(diǎn)B是網(wǎng)絡(luò)中的任意一個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)B是否著色是未知的。節(jié)點(diǎn)A隨機(jī)選擇一個(gè)除自己之外的節(jié)點(diǎn)發(fā)送信息，所以網(wǎng)絡(luò)中任意節(jié)點(diǎn)B在當(dāng)前輪次收到節(jié)點(diǎn)A發(fā)送的信息的概率為1/(N-1)。

任意節(jié)點(diǎn)B在當(dāng)前輪次收不到節(jié)點(diǎn)A發(fā)送的信息的概率為

任意節(jié)點(diǎn)B在當(dāng)前輪次收不到來(lái)自任何將向外傳播信息的已著色節(jié)點(diǎn)的信息的概率Pf為

任意節(jié)點(diǎn)B在當(dāng)前輪次至少收到一條來(lái)自將向外傳播信息的已著色節(jié)點(diǎn)的信息的概率Ps為

又由于當(dāng)前網(wǎng)絡(luò)中未著色節(jié)點(diǎn)個(gè)數(shù)C0(T)即為N-C(T)，所以未著色節(jié)點(diǎn)在當(dāng)前輪次被著色(至少收到一條信息)的預(yù)期個(gè)數(shù)為

下一輪次的Ci(T+1)，其中i=1, 2, 3, 4, 5，由兩部分組成，當(dāng)前輪次i類節(jié)點(diǎn)的個(gè)數(shù)減去i類節(jié)點(diǎn)在本輪收到信息而轉(zhuǎn)變?yōu)閕+1類節(jié)點(diǎn)的個(gè)數(shù)，以及當(dāng)前i-1類節(jié)點(diǎn)在本輪收到信息而轉(zhuǎn)變?yōu)閕類節(jié)點(diǎn)的個(gè)數(shù)。即在本輪未收到信息的i類節(jié)點(diǎn)的個(gè)數(shù)，加上i-1類節(jié)點(diǎn)在本輪收到信息的個(gè)數(shù)。其計(jì)算公式為

S(T)是在T輪次向外傳播信息的節(jié)點(diǎn)數(shù)，也是在T輪次發(fā)送的總信息量，顯然BEBG能夠有效降低網(wǎng)絡(luò)負(fù)載，但是BEBG降低信息量是以增加周期為代價(jià)的。在算法的后期，大量節(jié)點(diǎn)對(duì)外傳播信息的概率為1/32，這可能導(dǎo)致有極個(gè)別未著色節(jié)點(diǎn)長(zhǎng)期收不到更新信息。很多周期后，某些未著色節(jié)點(diǎn)可能還是沒(méi)有收到信息，本文稱這些仿佛被隔絕了的，一直(或長(zhǎng)期)收不到信息的節(jié)點(diǎn)為邊緣節(jié)點(diǎn)。為了解決BEBG存在的邊緣節(jié)點(diǎn)問(wèn)題，3.2節(jié)和3.3節(jié)對(duì)BEBG進(jìn)行了改進(jìn)。

3.2 PBEBG算法

Gossip信息交換的方式有3種：Pull, Push,Push&Pull。BEBG實(shí)質(zhì)上是對(duì)Push模式的GA的改進(jìn)。在Pull模式的GA中，未著色節(jié)點(diǎn)會(huì)一直向其他節(jié)點(diǎn)發(fā)送更新請(qǐng)求消息，直到找到一個(gè)已著色節(jié)點(diǎn)，基于Pull的方法理論上不會(huì)出現(xiàn)邊緣節(jié)點(diǎn)。因此，本文將Pull與BEBG相結(jié)合來(lái)解決BEBG存在的邊緣節(jié)點(diǎn)問(wèn)題，此BEBG改進(jìn)算法稱為PBEBG(Binary Exponential Backoff Gossip with Pull)。如圖1所示，在算法的后期，邊緣節(jié)點(diǎn)隨機(jī)選擇一個(gè)節(jié)點(diǎn)向其發(fā)送請(qǐng)求消息，接收到請(qǐng)求消息的節(jié)點(diǎn)將更新信息(如果有)發(fā)送給該邊緣節(jié)點(diǎn)。圖1中灰色節(jié)點(diǎn)為已著色節(jié)點(diǎn)，白色節(jié)點(diǎn)為未著色節(jié)點(diǎn)。假設(shè)節(jié)點(diǎn)5隨機(jī)選擇向節(jié)點(diǎn)9發(fā)送更新請(qǐng)求消息，節(jié)點(diǎn)9收到后響應(yīng)請(qǐng)求，將更新信息發(fā)送給節(jié)點(diǎn)5。

圖1 PBEBG算法中的“拉”

3.2.1 PBEBG的發(fā)送過(guò)程

PBEBG的發(fā)送過(guò)程比較復(fù)雜。初始化時(shí)，根節(jié)點(diǎn)的p值為1，其他節(jié)點(diǎn)的p值為0。發(fā)送信息之前節(jié)點(diǎn)要先確定是否在上一個(gè)輪次收到其他節(jié)點(diǎn)的更新請(qǐng)求。如果節(jié)點(diǎn)是已著色的且在上一個(gè)輪次收到了請(qǐng)求消息，那么本輪中節(jié)點(diǎn)將直接把自己的更新信息發(fā)送給請(qǐng)求節(jié)點(diǎn)，如果請(qǐng)求節(jié)點(diǎn)不止一個(gè)，節(jié)點(diǎn)將會(huì)從請(qǐng)求節(jié)點(diǎn)中選取一個(gè)節(jié)點(diǎn)向其發(fā)送更新信息。

如果節(jié)點(diǎn)沒(méi)有收到更新請(qǐng)求，那么信息發(fā)送過(guò)程與BEBG的相似，先根據(jù)節(jié)點(diǎn)向外傳播信息的概率p決定是否向外發(fā)送更新信息，如果是，則隨機(jī)選取一個(gè)除自己以外的節(jié)點(diǎn)向其發(fā)送更新信息。PBEBG的發(fā)送過(guò)程見(jiàn)表3。

PBEBG算法還引入了一個(gè)新的變量“Pull”。這里的“Pull”不是GA算法信息交換的一種方式，而是代表未著色節(jié)點(diǎn)向外發(fā)送更新請(qǐng)求的時(shí)機(jī)。設(shè)網(wǎng)絡(luò)中一共有N個(gè)節(jié)點(diǎn)，剛開(kāi)始網(wǎng)絡(luò)中有N-1個(gè)未著色節(jié)點(diǎn)，不可能第1輪就讓N-1個(gè)節(jié)點(diǎn)向外發(fā)送請(qǐng)求，這會(huì)導(dǎo)致第1輪時(shí)未著色節(jié)點(diǎn)發(fā)出N-1條請(qǐng)求消息，然而只有一條請(qǐng)求能得到根節(jié)點(diǎn)的回復(fù)，這會(huì)造成網(wǎng)絡(luò)資源的極大浪費(fèi)。因此，從哪一個(gè)輪次開(kāi)始發(fā)送更新請(qǐng)求就至關(guān)重要了。節(jié)點(diǎn)決定發(fā)送更新請(qǐng)求的前提是：(1)當(dāng)前節(jié)點(diǎn)未被著色；(2)當(dāng)前的輪次T大于等于“Pull”值(見(jiàn)表4)，表3中，request為真時(shí)發(fā)送更新請(qǐng)求，隨機(jī)選取一個(gè)除自己以外的節(jié)點(diǎn)向其發(fā)送更新請(qǐng)求。

表3 PBEBG算法的發(fā)送過(guò)程(算法3)

3.2.2 PBEBG的接收過(guò)程

PBEBG的接收過(guò)程比BEBG的接收過(guò)程多一個(gè)判斷，因?yàn)檫@時(shí)網(wǎng)絡(luò)中有兩種消息，一種是來(lái)自已著色節(jié)點(diǎn)的傳播感興趣信息的更新消息，一種是來(lái)自未著色節(jié)點(diǎn)的更新請(qǐng)求消息。

每1輪，1個(gè)節(jié)點(diǎn)v可能既接收到網(wǎng)絡(luò)中未著色節(jié)點(diǎn)發(fā)來(lái)的更新請(qǐng)求，也接收到已著色節(jié)點(diǎn)傳播的更新信息。節(jié)點(diǎn)v有可能收到多條更新請(qǐng)求消息，這時(shí)，線程只會(huì)存儲(chǔ)最后一條請(qǐng)求消息的來(lái)源，記為s，在下一輪如果節(jié)點(diǎn)v是已著色節(jié)點(diǎn)則會(huì)將更新消息發(fā)給節(jié)點(diǎn)s。如果節(jié)點(diǎn)v收到了多條包含相同信息的更新消息，這時(shí)的處理方法與BEBG算法的一樣，每1輪只改變1次p的值。PBEBG的接收過(guò)程見(jiàn)表4。

表4 PBEBG算法的接收過(guò)程(算法4)

PBEBG算法有效減少了網(wǎng)絡(luò)負(fù)載，并解決了邊緣節(jié)點(diǎn)問(wèn)題，但是該算法需要未著色節(jié)點(diǎn)在一定時(shí)間(輪次)后，向網(wǎng)絡(luò)中的其他節(jié)點(diǎn)發(fā)送更新請(qǐng)求消息。然而，除非有約定或每個(gè)節(jié)點(diǎn)定期地去詢問(wèn)，否則未著色節(jié)點(diǎn)不知道網(wǎng)絡(luò)中什么時(shí)候會(huì)有新的信息，也就無(wú)法估計(jì)當(dāng)前處于什么輪次了。另外，Pull參數(shù)的設(shè)置需要事先做約定。這些因素減少了該算法的適用場(chǎng)景。因此本文又提出了一種不需要Pull的BEBG改進(jìn)算法。

3.3 NBEBG算法

本節(jié)提出一個(gè)基于鄰居節(jié)點(diǎn)的二進(jìn)制指數(shù)退避Gossip算法(Neighbor-based Binary Exponential Backoff Gossip, NBEBG)，該算法增加了一個(gè)定向“推送”。與BEBG算法不同的是，BEBG算法隨機(jī)選擇網(wǎng)絡(luò)中的節(jié)點(diǎn)向其傳播信息，而NBEBG算法則是先判斷本節(jié)點(diǎn)是否為第1次接收到更新信息，如果是，則將信息傳播給前1個(gè)鄰居節(jié)點(diǎn)，如果不是第1次，則將信息傳播給從網(wǎng)絡(luò)中隨機(jī)選擇的一個(gè)節(jié)點(diǎn)。算法運(yùn)行到最后，其實(shí)相當(dāng)于每一個(gè)著色節(jié)點(diǎn)都向前一個(gè)節(jié)點(diǎn)發(fā)送了一次更新信息，如果沒(méi)有丟包，理論上是不會(huì)存在邊緣節(jié)點(diǎn)的。

如圖2所示，給網(wǎng)絡(luò)中的節(jié)點(diǎn)編號(hào)，灰色節(jié)點(diǎn)為已著色節(jié)點(diǎn)，白色節(jié)點(diǎn)為未著色節(jié)點(diǎn)。滿足條件的已著色節(jié)點(diǎn)將更新信息發(fā)送給前一個(gè)節(jié)點(diǎn)，是否傳播信息與前一個(gè)節(jié)點(diǎn)是否著色無(wú)關(guān)。

圖2 NBEBG中向前1個(gè)鄰居節(jié)點(diǎn)推送信息

3.3.1 NBEBG的發(fā)送過(guò)程

NBEBG的發(fā)送過(guò)程比BEBG的多了一個(gè)判斷。每個(gè)已著色節(jié)點(diǎn)每輪至多只傳播一次信息，如果它向前一個(gè)鄰居節(jié)點(diǎn)發(fā)送更新信息則不會(huì)再向網(wǎng)絡(luò)中的其他節(jié)點(diǎn)發(fā)送更新信息。根據(jù)之前的經(jīng)驗(yàn)，從哪一個(gè)輪次開(kāi)始可能對(duì)總信息量產(chǎn)生影響，因此NBEBG算法引入了一個(gè)新的變量“Push”，代表已著色節(jié)點(diǎn)向鄰居節(jié)點(diǎn)發(fā)送信息的時(shí)機(jī)，也就是說(shuō)，已著色節(jié)點(diǎn)向前一個(gè)節(jié)點(diǎn)發(fā)送更新信息是在到達(dá)規(guī)定的輪次之后才會(huì)發(fā)送。算法會(huì)記錄已著色節(jié)點(diǎn)是否已經(jīng)向前一個(gè)節(jié)點(diǎn)發(fā)送過(guò)更新信息。只有當(dāng)前輪次已達(dá)到規(guī)定輪次，且還沒(méi)有向前一個(gè)節(jié)點(diǎn)發(fā)送過(guò)更新信息，已著色節(jié)點(diǎn)才會(huì)向前一個(gè)節(jié)點(diǎn)發(fā)送。NBEBG的信息發(fā)送的具體過(guò)程如表5所示。初始化時(shí)，根節(jié)點(diǎn)的p值為1，其他節(jié)點(diǎn)的p值為0，所有節(jié)點(diǎn)的hasPush標(biāo)志為false。

表5 NBEBG算法的信息發(fā)送過(guò)程(算法5)

3.3.2 NBEBG的接收過(guò)程

NBEBG算法接收過(guò)程與BEBG算法接收過(guò)程完全一樣，未做任何修改。

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

第3節(jié)提出了兩個(gè)BEBG改進(jìn)算法：引入Pull的PBEBG和向前一個(gè)鄰居節(jié)點(diǎn)Push的NBEBG。為了做對(duì)比實(shí)驗(yàn)，本文也將這兩種改進(jìn)方法引入經(jīng)典Gossip算法。將引入Pull的GA稱為PGA，將向前一個(gè)鄰居節(jié)點(diǎn)Push的GA稱為NGA。本文研究并實(shí)現(xiàn)了6種Gossip算法，如圖3所示。PGA與NGA是GA的變種，PBEBG和NBEBG是BEBG的變種。

圖3 6種算法名稱

本文實(shí)現(xiàn)的程序是基于JAVA的高并發(fā)程序，通過(guò)使用JAVA的一些同步機(jī)制來(lái)模擬大規(guī)模分布式網(wǎng)絡(luò)的環(huán)境，程序中實(shí)現(xiàn)了10000個(gè)高并發(fā)線程模擬10000個(gè)節(jié)點(diǎn)。實(shí)驗(yàn)結(jié)果表明，通過(guò)改變傳播信息的概率，能夠有效地降低Gossip算法的網(wǎng)絡(luò)開(kāi)銷。Gossip算法的性能一般由算法的收斂速度和網(wǎng)絡(luò)負(fù)載兩個(gè)方面來(lái)衡量。算法的收斂速度是指算法將信息傳播到網(wǎng)絡(luò)上所有節(jié)點(diǎn)所需的周期數(shù)。網(wǎng)絡(luò)負(fù)載又稱為信息量，在本文中指信息傳播時(shí)所發(fā)送的UDP數(shù)據(jù)包個(gè)數(shù)。本文中所有數(shù)據(jù)都是程序運(yùn)行30次取的平均值。

圖4為“Pull”取不同值時(shí)，PBEBG與PGA總信息量隨時(shí)間變化的示意圖，即累計(jì)發(fā)送的UDP數(shù)據(jù)包個(gè)數(shù)隨著輪次(周期)的變化圖。由圖可見(jiàn)，邊緣節(jié)點(diǎn)開(kāi)始向網(wǎng)絡(luò)中其他節(jié)點(diǎn)發(fā)送請(qǐng)求消息的起始輪次對(duì)算法的信息量是有影響的；“Pull”取值為12時(shí)，PGA的信息量最少，“Pull”為14時(shí)，PBEBG的信息量最少。網(wǎng)絡(luò)中有104個(gè)節(jié)點(diǎn)時(shí)，PBEBG比引入Pull的GA可減少約34%的網(wǎng)絡(luò)負(fù)載。

圖4 不同“Pull”值時(shí)，算法PGA和PBEBG隨時(shí)間變化的總信息量

圖5為“Push”取不同值時(shí)，NBEBG與NGA總信息量隨時(shí)間變化的示意圖。由圖可見(jiàn)，節(jié)點(diǎn)向前一個(gè)鄰居節(jié)點(diǎn)發(fā)送信息的具體輪次對(duì)算法的信息量是有影響的；“Push”取值為14時(shí)，NGA的信息量最少，“Push”為15時(shí)，NBEBG的信息量最少。網(wǎng)絡(luò)中有104個(gè)節(jié)點(diǎn)時(shí)，NBEBG比引入向鄰居節(jié)點(diǎn)Push的GA減少了約37%的網(wǎng)絡(luò)負(fù)載。

圖5 不同“Push”值時(shí)，算法NGA和NBEBG隨時(shí)間變化的總信息量

圖6是6種算法將信息傳遍整個(gè)網(wǎng)絡(luò)所需的周期數(shù)。實(shí)驗(yàn)表明，除了BEBG，其余Gossip算法基本都能在30個(gè)周期以內(nèi)將信息傳遍網(wǎng)絡(luò)，GA需要24個(gè)周期，但24周期時(shí)BEBG只能將信息傳到網(wǎng)絡(luò)中97.5%的節(jié)點(diǎn)，圖中的28是虛值，代表很大的值。而加入“Pull”方式或者加入“向鄰居Push”的4個(gè)算法，NGA-14(參數(shù)Push =14)，PGA-12(參數(shù)Pull=12)，NBEBG-15(參數(shù)Push =15)，PBEBG-14(參數(shù)Pull=14)，只需要19到21個(gè)周期就能將信息傳遍網(wǎng)絡(luò)，收斂速度相差不大，都有效解決了邊緣節(jié)點(diǎn)問(wèn)題。

圖6 6種算法將信息傳遍整個(gè)網(wǎng)絡(luò)所需周期對(duì)比

圖7為6種算法總信息量對(duì)比圖。GA(24個(gè)周期)，NGA-14，PGA-12這3種算法的總信息量依次遞減。而包含指數(shù)退避的算法中，BEBG(24個(gè)周期)，NBEBG-15，PBEBG-14這3種算法的總信息量依次遞增。BEBG(24個(gè)周期)總信息量最少，但并不能將信息傳遍整個(gè)網(wǎng)絡(luò)，存在邊緣節(jié)點(diǎn)問(wèn)題；網(wǎng)絡(luò)有104個(gè)節(jié)點(diǎn)時(shí)它比GA(24個(gè)周期)減少了約61%的網(wǎng)絡(luò)負(fù)載。

圖7 6種算法總信息量對(duì)比

實(shí)驗(yàn)結(jié)果顯示，PBEBG與NBEBG均改進(jìn)了BEBG存在邊緣節(jié)點(diǎn)的不足，同時(shí)具有BEBG的網(wǎng)絡(luò)負(fù)載低的優(yōu)點(diǎn)。PBEBG與NBEBG的收斂速度和產(chǎn)生的網(wǎng)絡(luò)負(fù)載相差無(wú)幾，兩算法應(yīng)用條件不同，各有各的優(yōu)勢(shì)，PBEBG不需要知道自己的前一個(gè)節(jié)點(diǎn)是誰(shuí)，而NBEBG不需要其他節(jié)點(diǎn)的響應(yīng)。實(shí)際應(yīng)用中，可以根據(jù)實(shí)際情況選擇具體算法，比如基于DHT(分布式哈希表)的對(duì)等網(wǎng)絡(luò)中的信息傳播可以使用NBEBG，因?yàn)槊總€(gè)節(jié)點(diǎn)知道自己的前繼，而對(duì)于信息更新周期比較長(zhǎng)，節(jié)點(diǎn)之間基本同步，一輪時(shí)長(zhǎng)可以估計(jì)的應(yīng)用場(chǎng)景可以使用PBEBG。

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

為減少Gossip算法的網(wǎng)絡(luò)負(fù)載，本文提出了一個(gè)將二進(jìn)制指數(shù)退避算法與經(jīng)典Gossip算法相結(jié)合的改進(jìn)算法BEBG，它使用指數(shù)退避的信息傳播策略，使一個(gè)節(jié)點(diǎn)收到同一更新信息的次數(shù)越多，繼續(xù)傳播更新信息的概率越低。仿真實(shí)驗(yàn)表明，該算法能夠有效地減少網(wǎng)絡(luò)負(fù)載，網(wǎng)絡(luò)包含104個(gè)節(jié)點(diǎn)時(shí)BEBG比經(jīng)典Gossip算法降低了約61%的網(wǎng)絡(luò)負(fù)載。為解決BEBG的邊緣節(jié)點(diǎn)問(wèn)題，對(duì)BEBG算法作改進(jìn)，提出了引入Pull的BEBG改進(jìn)算法PBEBG，在若干輪次后讓未收到更新信息的節(jié)點(diǎn)主動(dòng)詢問(wèn)其他節(jié)點(diǎn)，網(wǎng)絡(luò)包含104個(gè)節(jié)點(diǎn)時(shí)，PBEBG比引入Pull的經(jīng)典Gossip算法減少約34%的網(wǎng)絡(luò)負(fù)載。為解決邊緣節(jié)點(diǎn)問(wèn)題，對(duì)BEBG另作改進(jìn)，提出了一種向鄰居節(jié)點(diǎn)Push的BEBG改進(jìn)算法NBEBG，除了常規(guī)Push，還讓收到更新信息的節(jié)點(diǎn)向其前一個(gè)鄰居節(jié)點(diǎn)發(fā)送更新信息以達(dá)到加快收斂速度的目的，網(wǎng)絡(luò)包含104個(gè)節(jié)點(diǎn)時(shí)，NBEBG比引入向鄰居節(jié)點(diǎn)Push的經(jīng)典Gossip算法減少了約37%的網(wǎng)絡(luò)負(fù)載。