基于選舉委員會(huì)的領(lǐng)導(dǎo)者選舉算法*

徐旭東, 李英玉

(1.中國(guó)科學(xué)院 國(guó)家空間科學(xué)中心,北京 100190； 2.中國(guó)科學(xué)院大學(xué),北京 100049)

0 引 言

隨著近年來(lái)小衛(wèi)星技術(shù)和星間通信技術(shù)的發(fā)展,以及“互聯(lián)網(wǎng)+”概念的興起,衛(wèi)星組網(wǎng)在未來(lái)將會(huì)成為趨勢(shì),由微小衛(wèi)星組成的天基互聯(lián)網(wǎng)在未來(lái)將可能實(shí)現(xiàn)。低軌衛(wèi)星具有較少的星地通信時(shí)延和較低的發(fā)射成本,通過(guò)星間鏈路將低軌衛(wèi)星組成衛(wèi)星網(wǎng)絡(luò),能夠提供全球覆蓋以及廣泛的數(shù)據(jù)通信服務(wù)能力,衛(wèi)星網(wǎng)絡(luò)將成為下一代互聯(lián)網(wǎng)(NGI)的重要組成部分。目前,國(guó)外的StarLink、OneWeb等低軌衛(wèi)星星座計(jì)劃,以及國(guó)內(nèi)的“天基互聯(lián)網(wǎng)”[1]、天基信息港[2]、天地一體化網(wǎng)絡(luò)[3]等用于衛(wèi)星通信研究,旨在提供面向全球的通信服務(wù)。

簡(jiǎn)單地說(shuō),天基互聯(lián)網(wǎng)就是通過(guò)星間鏈路進(jìn)行通信、多星協(xié)同共同完成任務(wù)的移動(dòng)分布式網(wǎng)絡(luò)。在分布式低軌衛(wèi)星網(wǎng)絡(luò)中,需要選舉某顆衛(wèi)星充當(dāng)領(lǐng)導(dǎo)者,來(lái)協(xié)調(diào)衛(wèi)星任務(wù)的分配。領(lǐng)導(dǎo)者不僅負(fù)責(zé)任務(wù)分配,還可以監(jiān)控其他衛(wèi)星節(jié)點(diǎn)的狀態(tài)。為了避免低軌衛(wèi)星網(wǎng)絡(luò)因領(lǐng)導(dǎo)者崩潰導(dǎo)致的系統(tǒng)不可用,需要可靠的選舉算法在領(lǐng)導(dǎo)者崩潰后,能快速地選出新的節(jié)點(diǎn)擔(dān)任領(lǐng)導(dǎo)者,維持分布式系統(tǒng)的可靠運(yùn)行。

Bully算法[4]是領(lǐng)導(dǎo)者選舉算法中經(jīng)典算法之一,能夠在分布式系統(tǒng)中選舉優(yōu)先級(jí)最高的節(jié)點(diǎn)擔(dān)任領(lǐng)導(dǎo)者,但其選舉過(guò)程將傳遞大量的消息,選舉時(shí)間較長(zhǎng),影響了系統(tǒng)的可用性。國(guó)內(nèi)外研究者針對(duì)Bully算法進(jìn)行了相關(guān)研究,各種算法相繼被提出。文獻(xiàn)[5]提出隨機(jī)向某個(gè)優(yōu)先級(jí)高的節(jié)點(diǎn)發(fā)送選舉消息的改進(jìn)算法,但由于引入了隨機(jī)性,系統(tǒng)通信開(kāi)銷(xiāo)起伏較大,影響算法的性能。文獻(xiàn)[6]通過(guò)循環(huán)選舉直接向優(yōu)先級(jí)最高的節(jié)點(diǎn)發(fā)送選舉消息,但該算法沒(méi)有容錯(cuò)機(jī)制。文獻(xiàn)[7]將最大堆(max-heap)概念引入到選舉算法中,節(jié)點(diǎn)不需要維持所有節(jié)點(diǎn)的優(yōu)先級(jí),降低了算法的空間復(fù)雜度,同時(shí),選舉領(lǐng)導(dǎo)者只需交換次消息,但算法過(guò)程相對(duì)復(fù)雜。

針對(duì)上述問(wèn)題,提出了基于選舉委員會(huì)的改進(jìn)Bully算法。選舉委員會(huì)確認(rèn)舊領(lǐng)導(dǎo)者下線后,由選舉委員會(huì)選舉出最高優(yōu)先級(jí)的節(jié)點(diǎn),降低了消息量和選舉時(shí)間,同時(shí)增加了系統(tǒng)的容錯(cuò)性,能更好地應(yīng)用于低軌衛(wèi)星網(wǎng)絡(luò)環(huán)境。

1 Bully算法

Bully算法的目標(biāo)是在正常運(yùn)行的節(jié)點(diǎn)中選出優(yōu)先級(jí)最高的節(jié)點(diǎn),其算法思想比較簡(jiǎn)單：當(dāng)某個(gè)節(jié)點(diǎn)在選舉超時(shí)時(shí)間內(nèi)沒(méi)有收到領(lǐng)導(dǎo)者的心跳消息,認(rèn)為領(lǐng)導(dǎo)者崩潰,同時(shí)發(fā)起選舉,向所有優(yōu)先級(jí)高于自身的節(jié)點(diǎn)發(fā)送選舉消息；節(jié)點(diǎn)收到選舉消息后,回復(fù)Ok消息,運(yùn)行選舉算法；當(dāng)運(yùn)行選舉算法的節(jié)點(diǎn)在一段時(shí)間內(nèi)沒(méi)有收到任何Ok消息,該節(jié)點(diǎn)將成為新的領(lǐng)導(dǎo)者。

李巍[8]、李曉婷等人[9]和Shirali M等人[10]分別對(duì)Bully選舉算法的消息復(fù)雜度進(jìn)行分析。假設(shè)分布式系統(tǒng)中有n個(gè)節(jié)點(diǎn),節(jié)點(diǎn)i檢測(cè)到領(lǐng)導(dǎo)者n崩潰并發(fā)起選舉,N(i)表示選舉過(guò)程中產(chǎn)生的消息量。在選舉過(guò)程中,節(jié)點(diǎn)i發(fā)送n-i條選舉消息,接受n-i-1條Ok消息,最后領(lǐng)導(dǎo)者發(fā)送n-2條心跳消息,故N(i)可以表示為

N(i)=n-i+n-i+1+N(i-1)+n-2

(1)

由遞推公式可得

N(i)=(n-1)2+(n-2)

(2)

由式(2)可知,當(dāng)節(jié)點(diǎn)總數(shù)n固定時(shí),算法的消息復(fù)雜度為O(i2)。Bully算法的選舉過(guò)程具有一定的隨機(jī)性,當(dāng)發(fā)起選舉的節(jié)點(diǎn)i減小時(shí),消息量以平方級(jí)增長(zhǎng),總體來(lái)看,算法的通信代價(jià)較大。

2 改進(jìn)算法

2.1 算法假設(shè)

本文對(duì)Bully選舉算法進(jìn)行改進(jìn),提出了適用于衛(wèi)星網(wǎng)絡(luò)高動(dòng)態(tài)、大延時(shí)特性的改進(jìn)Bully選舉算法。該算法成立的前提還需要滿(mǎn)足如下的基本假設(shè)：

1)分布式系統(tǒng)是異步的且時(shí)鐘不同步。

2)衛(wèi)星節(jié)點(diǎn)間的星間通信是不可靠的,包括網(wǎng)絡(luò)延遲、數(shù)據(jù)包丟失等情況,可能導(dǎo)致選舉失敗。

3)不發(fā)生拜占庭將軍故障。

4)集群中的每個(gè)節(jié)點(diǎn)都有一個(gè)單調(diào)遞增的任期(term),在每個(gè)任期中選舉領(lǐng)導(dǎo)者。

2.2 算法描述

在改進(jìn)的選舉算法中,選舉新的領(lǐng)導(dǎo)者主要包括以下5種消息：

Heartbeat消息:領(lǐng)導(dǎo)者向所有節(jié)點(diǎn)發(fā)送心跳信息,通知節(jié)點(diǎn)領(lǐng)導(dǎo)者還在正常運(yùn)行。

Election消息:節(jié)點(diǎn)在檢測(cè)到領(lǐng)導(dǎo)者崩潰后,向選舉委員會(huì)成員發(fā)起選舉。

Ok消息:選舉委員會(huì)成員收到Election消息后,對(duì)源節(jié)點(diǎn)的回應(yīng),源節(jié)點(diǎn)收到Ok消息后,中止選舉算法。

Verify消息:選舉委員會(huì)成員收到Election消息后,向領(lǐng)導(dǎo)者發(fā)送Verify消息,用于驗(yàn)證領(lǐng)導(dǎo)者是否正常工作。

Alive消息:領(lǐng)導(dǎo)者對(duì)Verify消息的回復(fù)。如果選舉委員會(huì)成員收到Alive消息,中止選舉,否則,通過(guò)選舉委員會(huì)選出新的領(lǐng)導(dǎo)者。

在改進(jìn)算法的選舉過(guò)程中,選舉委員會(huì)由領(lǐng)導(dǎo)者,候選者1,…,候選者k組成。在初始化階段,選舉委員會(huì)由系統(tǒng)中優(yōu)先級(jí)最高的若干個(gè)節(jié)點(diǎn)擔(dān)任。節(jié)點(diǎn)P檢測(cè)到領(lǐng)導(dǎo)者崩潰后,向選舉委員會(huì)發(fā)送選舉消息,選舉委員會(huì)先驗(yàn)證領(lǐng)導(dǎo)者是否正常工作,如果領(lǐng)導(dǎo)者崩潰,在選舉委員會(huì)中選出最高優(yōu)先級(jí)的節(jié)點(diǎn)作為領(lǐng)導(dǎo)者,否則,中止選舉算法。為了避免多個(gè)節(jié)點(diǎn)同時(shí)檢測(cè)到領(lǐng)導(dǎo)者崩潰,改進(jìn)的選舉算法使用隨機(jī)的選舉超時(shí)機(jī)制,每個(gè)節(jié)點(diǎn)的選舉超時(shí)時(shí)間設(shè)定為1～2 s上的隨機(jī)值。在大多數(shù)情況下,某個(gè)節(jié)點(diǎn)會(huì)率先開(kāi)始選舉,并在其他節(jié)點(diǎn)開(kāi)始選舉前選舉出新的領(lǐng)導(dǎo)者。

假設(shè)節(jié)點(diǎn)P率先檢測(cè)到領(lǐng)導(dǎo)者崩潰,它發(fā)起的選舉算法過(guò)程如下：

1)節(jié)點(diǎn)P檢測(cè)到低軌衛(wèi)星網(wǎng)絡(luò)中領(lǐng)導(dǎo)者崩潰后,執(zhí)行選舉算法。根據(jù)節(jié)點(diǎn)P維護(hù)的配置信息,向選舉委員會(huì)中優(yōu)先級(jí)最高的候選者Q發(fā)送Election消息；

2)如果超過(guò)一定時(shí)間沒(méi)有收到候選者Q的回應(yīng),候選者P向選舉委員會(huì)中優(yōu)先級(jí)次高的候選者R發(fā)送Election消息；

3)如果收到Ok回應(yīng)消息,候選者P停止選舉算法。節(jié)點(diǎn)Q將向領(lǐng)導(dǎo)者和優(yōu)先級(jí)高于自身的候選者發(fā)送Verify消息,用于驗(yàn)證節(jié)點(diǎn)是否存活；

4)如果候選者Q沒(méi)有收到回應(yīng),則向所有節(jié)點(diǎn)發(fā)送Heartbeat消息,宣布當(dāng)選為新領(lǐng)導(dǎo)者；

5)如果候選者Q收到Alive回應(yīng)消息,Q將回應(yīng)消息中優(yōu)先級(jí)最高的節(jié)點(diǎn)選為領(lǐng)導(dǎo)者,并廣播Heartbeat消息。

6)如果所有候選者都沒(méi)有回應(yīng),節(jié)點(diǎn)P向所有優(yōu)先級(jí)高于自己的節(jié)點(diǎn)發(fā)送Election消息,并在所有回復(fù)消息中選出優(yōu)先級(jí)最高的節(jié)點(diǎn)擔(dān)任領(lǐng)導(dǎo)者。

以實(shí)例說(shuō)明改進(jìn)算法的整個(gè)選舉流程,如圖1所示。系統(tǒng)中有6個(gè)節(jié)點(diǎn),優(yōu)先級(jí)分別為1～6,選舉委員會(huì)成員為節(jié)點(diǎn)4,5,6。若節(jié)點(diǎn)2檢測(cè)到領(lǐng)導(dǎo)者崩潰,并向優(yōu)先級(jí)最高的候選者5發(fā)送Election消息。候選者5回復(fù)Ok消息,并向舊領(lǐng)導(dǎo)者發(fā)送Verify驗(yàn)證消息。最終,節(jié)點(diǎn)5當(dāng)選為領(lǐng)導(dǎo)者,向所有普通節(jié)點(diǎn)廣播Heartbeat消息。

圖1 改進(jìn)算法的選舉過(guò)程

2.3 消息量復(fù)雜度分析

假設(shè)低軌衛(wèi)星網(wǎng)絡(luò)有n個(gè)節(jié)點(diǎn)參加選舉,其中選舉委員會(huì)共有k個(gè)成員,優(yōu)選級(jí)為r的節(jié)點(diǎn)在檢測(cè)到領(lǐng)導(dǎo)者崩潰時(shí)發(fā)起選舉,N(r)為選舉出新領(lǐng)導(dǎo)者時(shí)系統(tǒng)產(chǎn)生的消息數(shù)量,其中0k。此時(shí)節(jié)點(diǎn)r連續(xù)發(fā)送k-l個(gè)Election消息,候選者發(fā)送k-l條Verify消息,新選出的領(lǐng)導(dǎo)者發(fā)送了l-1+n-k條Heartbeat消息,選舉產(chǎn)生的消息量為

Nl(r)=n+k-l

(3)

故節(jié)點(diǎn)r選出新領(lǐng)導(dǎo)者產(chǎn)生的期望消息量為

(4)

由式(4)可知,改進(jìn)算法產(chǎn)生的消息量與節(jié)點(diǎn)數(shù)量n,發(fā)起選舉的節(jié)點(diǎn)r以及節(jié)點(diǎn)崩潰概率p呈線性關(guān)系,即算法的通信量復(fù)雜度為O(n)。

3 仿真試驗(yàn)與結(jié)果分析

3.1 試驗(yàn)設(shè)計(jì)

在分布式衛(wèi)星網(wǎng)絡(luò)仿真實(shí)驗(yàn)平臺(tái)上搭建具有60顆衛(wèi)星的低軌衛(wèi)星網(wǎng)絡(luò),節(jié)點(diǎn)均支持星上路由選擇,能夠根據(jù)用戶(hù)需求快速地進(jìn)行任務(wù)處理。在實(shí)驗(yàn)中,使用Python編程語(yǔ)言實(shí)現(xiàn)Bully算法和改進(jìn)算法的實(shí)現(xiàn),部署在分布式衛(wèi)星網(wǎng)絡(luò)仿真實(shí)驗(yàn)平臺(tái)上,并進(jìn)行算法性能的對(duì)比。仿真試驗(yàn)的運(yùn)行環(huán)境如下：計(jì)算機(jī)內(nèi)存為8 GB,CPU型號(hào)為Intel Core i5 2.50 GHz,操作系統(tǒng)為Ubuntu 16.04。

通過(guò)衛(wèi)星仿真軟件STK(Satellite Tool Kit)獲取衛(wèi)星網(wǎng)絡(luò)的星歷數(shù)據(jù),同時(shí)將星歷數(shù)據(jù)存儲(chǔ)在Redis數(shù)據(jù)庫(kù)中。該衛(wèi)星網(wǎng)絡(luò)由5條極地軌道和60顆低軌衛(wèi)星構(gòu)成,每個(gè)軌道平面上有12顆均勻分布的低軌衛(wèi)星。軌道半長(zhǎng)軸為6 878.14 km,偏心率為0,軌道傾角為97.4°。星歷的初始時(shí)刻是 8 Oct 2018 16︰00︰00.000 UTCG,仿真時(shí)間為1天。

在仿真實(shí)驗(yàn)中,使用進(jìn)程模擬低軌衛(wèi)星節(jié)點(diǎn),節(jié)點(diǎn)間通信采用UDP協(xié)議,設(shè)定隨機(jī)值的選舉超時(shí)時(shí)間。每次試驗(yàn)殺死領(lǐng)導(dǎo)者進(jìn)程,系統(tǒng)隨機(jī)的選擇節(jié)點(diǎn)發(fā)起選舉,記錄選舉算法選出新領(lǐng)導(dǎo)者產(chǎn)生的消息量和時(shí)間開(kāi)銷(xiāo)。為研究節(jié)點(diǎn)數(shù)目變化對(duì)算法的影響,針對(duì)分別具有10個(gè)和20個(gè)節(jié)點(diǎn)的集群進(jìn)行試驗(yàn)。為方便起見(jiàn),在初始化時(shí),集群的選舉委員會(huì)由最高優(yōu)先級(jí)的4個(gè)節(jié)點(diǎn)組成,包括領(lǐng)導(dǎo)者和3個(gè)候選者。由于設(shè)置了隨機(jī)的超時(shí)時(shí)間,發(fā)起選舉的節(jié)點(diǎn)具有一定的隨機(jī)性,本文針對(duì)不同情況重復(fù)60次試驗(yàn)。在本次試驗(yàn)中,設(shè)定的選舉超時(shí)時(shí)間為1～2 s上隨機(jī)值,領(lǐng)導(dǎo)者以T=0.2 s的頻率廣播心跳消息。

3.2 實(shí)驗(yàn)結(jié)果與分析

低軌衛(wèi)星網(wǎng)絡(luò)采用虛擬節(jié)點(diǎn)策略[11]進(jìn)行路由轉(zhuǎn)發(fā),能夠屏蔽低軌衛(wèi)星的高速運(yùn)動(dòng),忽略衛(wèi)星在短時(shí)間內(nèi)的拓?fù)渥兓?。使用衛(wèi)星的星歷數(shù)據(jù),基于蟻群算法[12,13],計(jì)算衛(wèi)星網(wǎng)絡(luò)中通信節(jié)點(diǎn)間最短路徑,仿真極軌道衛(wèi)星星座中節(jié)點(diǎn)間的通信時(shí)延,得到如圖2(a)所示的通信時(shí)延累積積分曲線。

圖2 仿真結(jié)果

由于極軌道衛(wèi)星星座存在兩個(gè)縫隙,以及通信衛(wèi)星之間可能處于不同半球,星間通信時(shí)延有較大的波動(dòng)。其中,當(dāng)兩顆衛(wèi)星在極地附近時(shí),通信時(shí)延為5 ms,在不同半球時(shí),最大通信時(shí)延為109 ms。任意兩顆衛(wèi)星間通信時(shí)延在5～110 ms內(nèi),星間通信時(shí)延的仿真結(jié)果將用于領(lǐng)導(dǎo)者選舉的仿真試驗(yàn)。

在仿真試驗(yàn)中,選舉過(guò)程產(chǎn)生的通信量結(jié)果如圖 2(b)所示?？梢钥闯?隨著系統(tǒng)節(jié)點(diǎn)數(shù)目的增加,Bully算法消息量的增長(zhǎng)幅度遠(yuǎn)大于改進(jìn)算法；由于改進(jìn)算法直接向選舉委員會(huì)發(fā)送選舉消息,其消息量比較平穩(wěn),而B(niǎo)ully算法向優(yōu)先級(jí)高于自身的節(jié)點(diǎn)發(fā)送選舉消息,導(dǎo)致消息量出現(xiàn)劇烈的波動(dòng)；同時(shí),改進(jìn)算法的通信量明顯小于Bully算法。

選舉新領(lǐng)導(dǎo)者所需時(shí)間如圖 2(c)所示?？梢钥闯?隨著系統(tǒng)節(jié)點(diǎn)數(shù)目的增加,兩種算法的選舉時(shí)間都在增加,但Bully算法的增長(zhǎng)幅度較大；同時(shí),在相同條件下,改進(jìn)算法的選舉時(shí)間較短,能更快地選舉新的領(lǐng)導(dǎo)者。

綜上所述,改進(jìn)算法能夠有效地降低消息量和選舉時(shí)間,同時(shí),也能克服算法引入的隨機(jī)性帶來(lái)的性能上下波動(dòng)。

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

本文研究了Bully選舉算法和分布式低軌衛(wèi)星網(wǎng)絡(luò),為降低Bully選舉算法產(chǎn)生的消息量和減少選舉新領(lǐng)導(dǎo)者所需的時(shí)間開(kāi)銷(xiāo),以適應(yīng)低軌衛(wèi)星網(wǎng)絡(luò)高動(dòng)態(tài)、大延遲的網(wǎng)絡(luò)環(huán)境,提出了基于選舉委員會(huì)的改進(jìn)Bully算法。相比于Bully算法,改進(jìn)的算法能有效降低消息量和減少選舉新領(lǐng)導(dǎo)者所需的時(shí)間,隨著集群節(jié)點(diǎn)數(shù)目的增加,消息量和時(shí)間開(kāi)銷(xiāo)沒(méi)有明顯的增加。本文采用隨機(jī)的選舉超時(shí)機(jī)制,降低了多個(gè)節(jié)點(diǎn)同時(shí)發(fā)起選舉的概率,避免選舉過(guò)程中出現(xiàn)消息擁塞的情況。仿真試驗(yàn)結(jié)果表明,改進(jìn)的Bully算法具有良好的性能,能更好地應(yīng)用于低軌衛(wèi)星網(wǎng)絡(luò)。