徐旭東, 李英玉

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

0 引 言

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

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

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

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

1 Bully算法

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

李巍[8]、李曉婷等人[9]和Shirali M等人[10]分別對Bully選舉算法的消息復(fù)雜度進行分析。假設(shè)分布式系統(tǒng)中有n個節(jié)點,節(jié)點i檢測到領(lǐng)導(dǎo)者n崩潰并發(fā)起選舉,N(i)表示選舉過程中產(chǎn)生的消息量。在選舉過程中,節(jié)點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é)點總數(shù)n固定時,算法的消息復(fù)雜度為O(i2)。Bully算法的選舉過程具有一定的隨機性,當(dāng)發(fā)起選舉的節(jié)點i減小時,消息量以平方級增長,總體來看,算法的通信代價較大。

2 改進算法

2.1 算法假設(shè)

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

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

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

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

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

2.2 算法描述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖1 改進算法的選舉過程

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

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

Nl(r)=n+k-l

(3)

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

(4)

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

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

3.1 試驗設(shè)計

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

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

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

3.2 實驗結(jié)果與分析

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

圖2 仿真結(jié)果

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

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

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

綜上所述,改進算法能夠有效地降低消息量和選舉時間,同時,也能克服算法引入的隨機性帶來的性能上下波動。

4 結(jié)束語

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