基于选举委员会的领导者选举算法*

徐旭东, 李英玉

(1.中国科学院 国家空间科学中心,北京 100190； 2.中国科学院大学,北京 100049)

0 引 言

随着近年来小卫星技术和星间通信技术的发展,以及“互联网+”概念的兴起,卫星组网在未来将会成为趋势,由微小卫星组成的天基互联网在未来将可能实现。低轨卫星具有较少的星地通信时延和较低的发射成本,通过星间链路将低轨卫星组成卫星网络,能够提供全球覆盖以及广泛的数据通信服务能力,卫星网络将成为下一代互联网(NGI)的重要组成部分。目前,国外的StarLink、OneWeb等低轨卫星星座计划,以及国内的“天基互联网”[1]、天基信息港[2]、天地一体化网络[3]等用于卫星通信研究,旨在提供面向全球的通信服务。

简单地说,天基互联网就是通过星间链路进行通信、多星协同共同完成任务的移动分布式网络。在分布式低轨卫星网络中,需要选举某颗卫星充当领导者,来协调卫星任务的分配。领导者不仅负责任务分配,还可以监控其他卫星节点的状态。为了避免低轨卫星网络因领导者崩溃导致的系统不可用,需要可靠的选举算法在领导者崩溃后,能快速地选出新的节点担任领导者,维持分布式系统的可靠运行。

Bully算法[4]是领导者选举算法中经典算法之一,能够在分布式系统中选举优先级最高的节点担任领导者,但其选举过程将传递大量的消息,选举时间较长,影响了系统的可用性。国内外研究者针对Bully算法进行了相关研究,各种算法相继被提出。文献[5]提出随机向某个优先级高的节点发送选举消息的改进算法,但由于引入了随机性,系统通信开销起伏较大,影响算法的性能。文献[6]通过循环选举直接向优先级最高的节点发送选举消息,但该算法没有容错机制。文献[7]将最大堆(max-heap)概念引入到选举算法中,节点不需要维持所有节点的优先级,降低了算法的空间复杂度,同时,选举领导者只需交换次消息,但算法过程相对复杂。

针对上述问题,提出了基于选举委员会的改进Bully算法。选举委员会确认旧领导者下线后,由选举委员会选举出最高优先级的节点,降低了消息量和选举时间,同时增加了系统的容错性,能更好地应用于低轨卫星网络环境。

1 Bully算法

Bully算法的目标是在正常运行的节点中选出优先级最高的节点,其算法思想比较简单：当某个节点在选举超时时间内没有收到领导者的心跳消息,认为领导者崩溃,同时发起选举,向所有优先级高于自身的节点发送选举消息；节点收到选举消息后,回复Ok消息,运行选举算法；当运行选举算法的节点在一段时间内没有收到任何Ok消息,该节点将成为新的领导者。

李巍[8]、李晓婷等人[9]和Shirali M等人[10]分别对Bully选举算法的消息复杂度进行分析。假设分布式系统中有n个节点,节点i检测到领导者n崩溃并发起选举,N(i)表示选举过程中产生的消息量。在选举过程中,节点i发送n-i条选举消息,接受n-i-1条Ok消息,最后领导者发送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)可知,当节点总数n固定时,算法的消息复杂度为O(i2)。Bully算法的选举过程具有一定的随机性,当发起选举的节点i减小时,消息量以平方级增长,总体来看,算法的通信代价较大。

2 改进算法

2.1 算法假设

本文对Bully选举算法进行改进,提出了适用于卫星网络高动态、大延时特性的改进Bully选举算法。该算法成立的前提还需要满足如下的基本假设：

1)分布式系统是异步的且时钟不同步。

2)卫星节点间的星间通信是不可靠的,包括网络延迟、数据包丢失等情况,可能导致选举失败。

3)不发生拜占庭将军故障。

4)集群中的每个节点都有一个单调递增的任期(term),在每个任期中选举领导者。

2.2 算法描述

在改进的选举算法中,选举新的领导者主要包括以下5种消息：

Heartbeat消息:领导者向所有节点发送心跳信息,通知节点领导者还在正常运行。

Election消息:节点在检测到领导者崩溃后,向选举委员会成员发起选举。

Ok消息:选举委员会成员收到Election消息后,对源节点的回应,源节点收到Ok消息后,中止选举算法。

Verify消息:选举委员会成员收到Election消息后,向领导者发送Verify消息,用于验证领导者是否正常工作。

Alive消息:领导者对Verify消息的回复。如果选举委员会成员收到Alive消息,中止选举,否则,通过选举委员会选出新的领导者。

在改进算法的选举过程中,选举委员会由领导者,候选者1,…,候选者k组成。在初始化阶段,选举委员会由系统中优先级最高的若干个节点担任。节点P检测到领导者崩溃后,向选举委员会发送选举消息,选举委员会先验证领导者是否正常工作,如果领导者崩溃,在选举委员会中选出最高优先级的节点作为领导者,否则,中止选举算法。为了避免多个节点同时检测到领导者崩溃,改进的选举算法使用随机的选举超时机制,每个节点的选举超时时间设定为1～2 s上的随机值。在大多数情况下,某个节点会率先开始选举,并在其他节点开始选举前选举出新的领导者。

假设节点P率先检测到领导者崩溃,它发起的选举算法过程如下：

1)节点P检测到低轨卫星网络中领导者崩溃后,执行选举算法。根据节点P维护的配置信息,向选举委员会中优先级最高的候选者Q发送Election消息；

2)如果超过一定时间没有收到候选者Q的回应,候选者P向选举委员会中优先级次高的候选者R发送Election消息；

3)如果收到Ok回应消息,候选者P停止选举算法。节点Q将向领导者和优先级高于自身的候选者发送Verify消息,用于验证节点是否存活；

4)如果候选者Q没有收到回应,则向所有节点发送Heartbeat消息,宣布当选为新领导者；

5)如果候选者Q收到Alive回应消息,Q将回应消息中优先级最高的节点选为领导者,并广播Heartbeat消息。

6)如果所有候选者都没有回应,节点P向所有优先级高于自己的节点发送Election消息,并在所有回复消息中选出优先级最高的节点担任领导者。

以实例说明改进算法的整个选举流程,如图1所示。系统中有6个节点,优先级分别为1～6,选举委员会成员为节点4,5,6。若节点2检测到领导者崩溃,并向优先级最高的候选者5发送Election消息。候选者5回复Ok消息,并向旧领导者发送Verify验证消息。最终,节点5当选为领导者,向所有普通节点广播Heartbeat消息。

图1 改进算法的选举过程

2.3 消息量复杂度分析

假设低轨卫星网络有n个节点参加选举,其中选举委员会共有k个成员,优选级为r的节点在检测到领导者崩溃时发起选举,N(r)为选举出新领导者时系统产生的消息数量,其中0k。此时节点r连续发送k-l个Election消息,候选者发送k-l条Verify消息,新选出的领导者发送了l-1+n-k条Heartbeat消息,选举产生的消息量为

Nl(r)=n+k-l

(3)

故节点r选出新领导者产生的期望消息量为

(4)

由式(4)可知,改进算法产生的消息量与节点数量n,发起选举的节点r以及节点崩溃概率p呈线性关系,即算法的通信量复杂度为O(n)。

3 仿真试验与结果分析

3.1 试验设计

在分布式卫星网络仿真实验平台上搭建具有60颗卫星的低轨卫星网络,节点均支持星上路由选择,能够根据用户需求快速地进行任务处理。在实验中,使用Python编程语言实现Bully算法和改进算法的实现,部署在分布式卫星网络仿真实验平台上,并进行算法性能的对比。仿真试验的运行环境如下：计算机内存为8 GB,CPU型号为Intel Core i5 2.50 GHz,操作系统为Ubuntu 16.04。

通过卫星仿真软件STK(Satellite Tool Kit)获取卫星网络的星历数据,同时将星历数据存储在Redis数据库中。该卫星网络由5条极地轨道和60颗低轨卫星构成,每个轨道平面上有12颗均匀分布的低轨卫星。轨道半长轴为6 878.14 km,偏心率为0,轨道倾角为97.4°。星历的初始时刻是 8 Oct 2018 16︰00︰00.000 UTCG,仿真时间为1天。

在仿真实验中,使用进程模拟低轨卫星节点,节点间通信采用UDP协议,设定随机值的选举超时时间。每次试验杀死领导者进程,系统随机的选择节点发起选举,记录选举算法选出新领导者产生的消息量和时间开销。为研究节点数目变化对算法的影响,针对分别具有10个和20个节点的集群进行试验。为方便起见,在初始化时,集群的选举委员会由最高优先级的4个节点组成,包括领导者和3个候选者。由于设置了随机的超时时间,发起选举的节点具有一定的随机性,本文针对不同情况重复60次试验。在本次试验中,设定的选举超时时间为1～2 s上随机值,领导者以T=0.2 s的频率广播心跳消息。

3.2 实验结果与分析

低轨卫星网络采用虚拟节点策略[11]进行路由转发,能够屏蔽低轨卫星的高速运动,忽略卫星在短时间内的拓扑变化。使用卫星的星历数据,基于蚁群算法[12,13],计算卫星网络中通信节点间最短路径,仿真极轨道卫星星座中节点间的通信时延,得到如图2(a)所示的通信时延累积积分曲线。

图2 仿真结果

由于极轨道卫星星座存在两个缝隙,以及通信卫星之间可能处于不同半球,星间通信时延有较大的波动。其中,当两颗卫星在极地附近时,通信时延为5 ms,在不同半球时,最大通信时延为109 ms。任意两颗卫星间通信时延在5～110 ms内,星间通信时延的仿真结果将用于领导者选举的仿真试验。

在仿真试验中,选举过程产生的通信量结果如图 2(b)所示。可以看出,随着系统节点数目的增加,Bully算法消息量的增长幅度远大于改进算法；由于改进算法直接向选举委员会发送选举消息,其消息量比较平稳,而Bully算法向优先级高于自身的节点发送选举消息,导致消息量出现剧烈的波动；同时,改进算法的通信量明显小于Bully算法。

选举新领导者所需时间如图 2(c)所示。可以看出,随着系统节点数目的增加,两种算法的选举时间都在增加,但Bully算法的增长幅度较大；同时,在相同条件下,改进算法的选举时间较短,能更快地选举新的领导者。

综上所述,改进算法能够有效地降低消息量和选举时间,同时,也能克服算法引入的随机性带来的性能上下波动。

4 结束语

本文研究了Bully选举算法和分布式低轨卫星网络,为降低Bully选举算法产生的消息量和减少选举新领导者所需的时间开销,以适应低轨卫星网络高动态、大延迟的网络环境,提出了基于选举委员会的改进Bully算法。相比于Bully算法,改进的算法能有效降低消息量和减少选举新领导者所需的时间,随着集群节点数目的增加,消息量和时间开销没有明显的增加。本文采用随机的选举超时机制,降低了多个节点同时发起选举的概率,避免选举过程中出现消息拥塞的情况。仿真试验结果表明,改进的Bully算法具有良好的性能,能更好地应用于低轨卫星网络。