移动自组网中基于分簇的通用一致性协议

雷向东¹，郭坤坤¹，李梦甜¹，雷振阳²，卿优优¹

(1. 中南大学 信息科学与工程学院，湖南 长沙，410083;

2. 湖南农业大学 信息科学技术学院，湖南 长沙，410128)

摘要：提出解决移动自组网一致性问题的基于分簇的通用一致性协议(VCBC)。VCBC协议分为检测与分簇层和一致性实施层。检测与分簇层在对移动自组网分簇的同时，与附加的不可靠故障检测器一起向一致性实施层提供网络的当前状态。同时，分簇可以合并消息，减少网络中的消息数量，节省网络资源；一致性实施层利用检测与分簇层提供的层次化网络，采用一种通用的模型来解决移动自组网中一致性问题。通过NS2软件进行仿真实验，实验结果表明：VCBC协议在平均轮数(NR)、平均跳数(NH)和执行时间(ET)等3个方面均优于其他协议。

关键词：一致性协议；不可靠故障检测器；分簇；移动自组网

中图分类号：TP311        文献标志码：A         文章编号：1672-7207(2012)07-2629-07

A versatile clustering-based consensus protocol in mobile Ad Hoc networks

LEI Xiang-dong¹, GUO Kun-kun¹, LI Meng-tian¹, LEI Zhen-yang², QING You-you¹

(1. School of Information Science and Engineering, Central South University, Changsha 410083, China;

2. School of Information Science and Technology, Hunan Agricultural University, Changsha 410128, China)

Abstract: A versatile clustering-based consensus (VCBC) protocol to solve the consensus problem in mobile Ad Hoc networks was proposed. The VCBC protocol includes detect and cluster layer (DC layer) and reach consensus layer (RC layer). The DC layer clusters the network into two layers and uses failure detector (FD) to provide the network status to consensus layer, the clustering method can reduce the number of messages in order to save the cost. Meanwhile RC layer uses the information provided by DC layer through a versatile model to solve the consensus problem. The simulation result of the NS2 software shows that, the VCBC is better than other protocols with the parameters of number of rounds (NR), number of hops (NH) and execution time (ET).

Key words: consensus protocol; unreliable failure detector; clustering; mobile Ad Hoc network

一致性问题是许多分布式计算问题，例如原子提交、原子广播及文件复制等的基本问题。移动自组网(MANET)具有动态网络拓扑、分布式控制、无基础设施支持、有限链路带宽和资源等特点，对一致性问题的解决提出新的挑战。检测移动主机(MH)故障的不可靠故障检测器(FD)可用来解决一致性问题。基于FD的协议有多种^[1-4]，如Wu等^[1]提出基于FD的BHM协议。BHM协议利用移动支持站(MSS)代替移动主机(MH)执行一致性协议，并通过MSS将最后的结果广播。然而，MANET没有MSS的支持，不能应用BHM协议。因此，Wu等^[2-3]提出层次化一致性协议HCS和HCD，利用层次化的方法减少开销，提高稳定性和可扩展性。但HCS的簇头是静态且预先定义的，不能适应系统状态的变化。如果簇头节点崩溃，将会影响一致性协议的收敛速度。HCD协议要求网络中崩溃节点的数目不大于系统所有节点数目的一半。而对于完全自治的MANETs，这个要求难以满足。Seba等^[4]提出一种通用的解决一致性问题的多轮协议簇，由每一轮的协调者提出建议值给所有的MH，MH收到建议值后向决策者和一致性保管者发送回复消息。如果决策者收到超过预定数量的回复信息则做出决定，并通过可靠的分发机制，将决定值广播。MANET中消息是通过MH之间的转发而完成的，大量的请求与应答消息互传的代价过大。

本文作者基于层次化和FD的思想，提出MANET中基于分簇的通用一致性VCBC协议。VCBC协议采用分簇的形式，可合并网络中的请求与应答消息，减少网络的总体开销。协议分为2层：其中底层为检测与分簇层(DC)，上层为一致性实施层(RC)。VCBC协议的框架如图1所示。

图1  VCBC协议框架

Fig.1  Framework for VCBC protocol

DC层作为协议的底层通过物理网络提供的信道交换消息，维护网络运行，向一致性实施层提供网络的信息。同时RC层通过下层提供的网络信息达成一致性。RC层与DC层在每个节点处都有1个模块，是分布式的。RC层是分布式运行的，而DC层则是1个分布式的信息库。DC层之下是物理网络，RC层之上是上层应用。DC层是协议的基础，是一个可替换不同类型FD的1个工具集，不同的FD可解决不同的一致性问题。一致性实施层是1种利用DC解决一致性问题的通用方案。如果将RC层决策者集合进行重新定义，VCBC协议可以作为分布式网络的层次化通用一致性协议。

1  一致性问题的可解性与DC层

在由n个MHs组成的MANETs中，任何2个MHs之间直接通过可靠信道收发消息，并进行协调。MH是对等分布式控制的，链路带宽和节点资源是有限的。MH可能崩溃，MH在崩溃之前是正确运行的。假设系统可能发生崩溃的节点个数为f(f＜n)，但至少有1个MH是正确的。所谓一致性问题是指一组参与的MHs或节点(本文对MH与节点不加区分)根据参与节点的初始值在某一个特定的问题上达成一致^[5-6]。

1.1  不可靠故障检测器FD

在分布式系统中，如果没有附加条件，即使只有1个节点崩溃，一致性问题也是不可解的^[7-8]。装配FD系统的一致性问题是可解的，不同类型FD的要求、适用范围是不一样的^[9-10]。FD分为8种，其中最重   要的2种是S类和?S类，其他的FD可以归约为这2种^[11-12]。在VCBC协议中，不同的FD只会影响协议的终止条件。

S类与?S类FD都满足强完整性，即最终所有崩溃的节点永久的被所有正确的节点怀疑^[13-14]。S类FD还要满足永久弱精确性，即一些正确的节点永远不被任何正确的节点怀疑。?S类FD要满足最终弱精确性，即经过一定的时间后，一些正确的节点永远不被任何正确的节点怀疑。S类故障检测器要求严格，不容易实现，应用范围小。使用S类FD 可以解决网络中MH崩溃数f满足0≤f＜n的一致性问题。?S类故障检测器要求低，容易实现^[15]，但使用?S类FD 要求网络中MHs崩溃数f满足0≤f＜n/2。

1.2  DC层

DC层是一个分布式的信息库，它检测系统的错误，解决网络的分簇以及分簇的维护，向上提供信息，它在每个MH处都有1个模块。对于节点i的查询， DC层的输出节点i信任的MHs集合Trust，网络中簇头节点的集合ClusterHead和当前MH的簇头ch。

DC层利用FD提供的可信MH集合Trust对网络进行分簇。在网络初始时，所有的MH都是簇头节点，每个MH只有在有MH从其信任列表中移除时，才发送其簇头集合给所有MH，如收到簇头集合的MH序列号小于发送方的序列号，就修改其簇头节点集合为新收到的集合，如果序列号相等，将2个集合作交运算机。

MH分布式运行会造成消息的混乱，对于发送的处理簇头维护的消息需要加上时间戳“sn”。当前簇头不可信时，簇头节点就发送“KQUIT”消息通知其所有簇成员，簇成员需要发送“QUIT”消息通知簇头。申请者一直重复上述过程，直到完成簇头切换过程。为防止重复向某一个节点发送请求，或者向速度较慢的节点发送请求，需要将在一定时间内没有收到回复的节点和收到拒绝的“ANSWER”消息的节点加入拒绝请求的Reject集合中。收到KQUIT消息后，簇头节点需要通知其簇成员。簇成员需要通知簇头退出，即发送“QUIT”消息。当簇头节点不可信时，启动切换簇头的模块，申请者通过“NEAR”消息请求距离最近的簇头节点充当其簇头，并发送“JOIN”消息。收到“JOIN”请求的簇头节点，将申请者加入本地簇成员列表，并回复同意的“ANSWER”消息。非簇头节点收到“JOIN”请求，发送拒绝的“ANSWER”消息。收到“QUIT”的簇头节点，就将请求退出的MH从簇成员列表中删除。簇头的切换过程会影响一致性实施层的消息流向，导致死锁等极端情况的发生，RC层需要处理这些问题。

DC层负责对其他的节点进行监测并维护一个怀疑列表，这个列表是本地检测模块怀疑已经崩溃的节点的集合。在节点查询时以怀疑列表作为输出。同时，向RC层提供当前节点的簇头节点，并维持分簇的有效性。如果当前的簇头节点在怀疑列表中，应启动簇头切换过程以保证分簇信息的有效性。

2  VCBC协议

VCBC协议的RC层采用异步多轮式2阶段快速决定方式，在每一轮，协调者cc提出建议值，分发给所有的MH，收到的MH如果同意就回复“ACK”消息给cc，cc收到足够多的“ACK”消息后，就作出决定，并将决定通过广播机制广播。协议在建议分发与回复收集时采用层次化的方式，以节省资源。

2.1  数据说明

VCBC协议执行的过程中需要的数据和消息说明如下：r_i表示当前的轮数，IV_i是MH_i的提议值，stamp_i是当前的提议值在更新时的轮数，state表示MH已经作出决定与否，cc代表当前的协调者，由方法coordinate( )生成，对于给定的输入返回相同的值，MH节点i的族头为ch，*代表任意值，#代表不可能的值。

当前MH信任的MH集合为Trust，由FD生成。簇头节点集合为ClusterHead，由DC层提供。D是决策者集合，A是一致性保管者集合，good( )一个标志函数，用于检测协议是否可以作出决定。

PROP(r, IV)是在第r轮中，由协调者发送给簇头，并由簇头发送给簇成员的消息，IV是当前协调者的提议值。

ACK(r, IV, stamp)是在第r轮中，簇成员发往簇头的回复消息，IV是MH的提议值，stamp是建议值最后更新的轮数。

ACKC(r, IV, stamp，Agree)是在第r轮中，簇头发往D∪A的回复消息，stamp是簇头收集到的回复信息中最大的值；IV是具有最大stamp值的回复消息中的提议值，Agree是带有这个stamp的所有MH集合。

DECISION(est)是作出决定的MH广播的消息，IV是决定值。NEWROUND(r)唤醒一个在等待中的协调者，防止死锁。

2.2  协议描述

基于分簇的一致性协议有3个任务，任务1是协议的主体，任务2是维护簇并处理延迟的消息，任务3是处理那些相对提前的消息。3个任务相互独立运行，协调工作。

任务1的伪码如下：

协议是一个异步的多轮协议，每一轮分为2个阶段。在第一阶段，如果节点i是当前轮的协调者，就发送“PROP(r_i, IV_i)”消息到簇头集合ClusterHead(第(4)行)；否则，就发送“NEWROUND(r_i)”消息给协调者(第(5)行)。给协调者发送“NEWROUND”消息的目的是为了防止本轮协调者永久等待消息，从而发生死锁。簇头节点将一直等待直到从协调者收到消息或者协调者不可信或者i不再是簇头节点(第(7)行)。簇头节点如果收到协调者的消息，就将消息转发给所有簇成员，否则发送“PROP(r_i, #)”消息给所有簇成员(第(8)~(9)行)。发送“PROP(r_i, #)”的目的是保持系统中消息的一致，减少消息的类型。节点等待接收簇头发送的“PROP”消息或者簇头不可信(第(10)行)。如果节点收到簇头的“PROP(r_i,*)”消息并且*≠#，则修改自己的值及时间戳(第(11)行)。第一阶段结束。第二阶段开始时，首先发送回复消息“ACK”给簇头节点。所有簇头节点等待接收其所有的簇成员回复消息“ACK”，或者簇成员不可信(第(14)行)。收到所有回复后，簇头节点构造自己的回复消息“ACKC(r_i, IV, stamp)”，其中是r_i轮数，stamp是收到的MH中最大的stamp，IV是带有stamp时间戳的提议值(第(15)行)。簇头节点将ACKC消息发送给D∪A中所有MHs。属于D∪A的MH将一直等待收到所有可信簇头节点的“ACKC”消息(第(19)行)。如果MH不是决策者(决策者属于D)，则仅修改stamp。如果MH是决策者，则利用good(Agree₁∪Agree₂∪…∪Agree_n) 判断是否可以作出决策。如果作出决策，使用DECISION(IV)广播决定值(第(22)行)。对于收到DECISION(IV)的MH，继续广播该决定(第(23)~(24)行)。

任务2处理延迟的回复消息，并处理簇头切换过程。所谓延迟的回复消息是指簇头在已发送“ACKC”消息后，又收到其簇成员的“ACK”消息，这是由于簇头节点错误的将1个速度较慢的节点当成1个崩溃的节点导致的。如果忽略这些消息，D∪A集合的某些MH可能会被永远地阻塞。为防止出现这种极端的情况，簇头节点将再构造1个“ACKC”消息，并发送给第r_j轮的集合D∪A。

在运行过程中，一部分簇头节点由于崩溃或FD的错误怀疑而不能再作为簇头，就会发生簇头的切换，新簇头没有收到这些MHs的回复消息，就会阻塞。为此MHs需要补发回复消息，如果MH已经进行第二阶段，不管它有没有收到簇头分发的消息，都要进行回复。

任务3处理处于阻塞的MH收到新的消息，需要跳过某些轮的情况。如果MHs是簇头节点并且收到的不是新一轮消息，它需要通知其簇成员进入新的一轮。如果MH属于第r-1轮的集合D∪A并且r-1＞r_i，要跳入r-1轮。如果MH不属于第r-1轮的集合D∪A，MH跳入到r轮，MH在跳过一些轮前需要补偿跳过轮的回复消息。

2.3  通用性

VCBC协议的通用性体现在2个方面：与消息交换模式相关的通用性和与MH崩溃数目相关的通用性。与消息交换模式相关的通用性通过决策者集合D和一致性保管者集合A来调节，与MH崩溃数目相关的通用性通过底层FD来调节。

2.3.1  与消息交换模式相关的通用性

集合D与A的定义决定消息交换的模式是全分布式或者是全集中式的。D与协议的终止性直接相关，A与协议的一致性直接相关，因此，D与A不能随意定义。

决策者集合D是在指某一轮中那些必须检查协调者的提议能否通过的MH集合。对于第r轮，D是通过方法Decider(r)来定义的。因此，Decider(r)是确定的，对于给定的输入返回的结果是确定的，而且Decider(r)包含第r轮的协调者。

一致保管者集合A是指那些保证协议一致性的MH集合。如果所有MH都是正确的，A可以任意指定，但MH是异步执行的，可能崩溃，FD也是不可靠的，所以A必须明确定义。由于异步性，可能存在不同的MH在不同的轮作出决定。假设第一个作出决定IV的MH所在的轮数为r，A就必须保证在r轮后面作出决定的MH的值为IV。A通过一个确定的函数agreeKeeper(r)来决定。如果一个MH在第r轮作出决定值IV，则属于A的MH需要修改它的IV值，使得在下一轮的提议值必须是这个值，为保证这一点，第r+1轮决策者必须属于A。

考虑一种极端的情况，D和A为所有MH的集合，即所有的MH都等到上一轮的回复消息到达，判断是否可以作出决定后，再进入下一轮，这样可以作出决定的MH多，但消息交换模式就变成全分布式。考虑另一个极端，D＝{Decider(r)}；A={Decider(r+1)}，即每次可作出决定的只有本轮的协调者，这样消息交换模式就是全集中式的。由上面的讨论可以得出：D与A的定义可以调节作出决定的MH数目与消息的交换模式。

2.3.2  与MH崩溃数目相关的通用性

不同的FD可以解决不同类型的一致性问题。如果网络同时崩溃的MH数目不超过总数的一半，可以使用?S类解决。如果不能保证崩溃的MH数目，就必须使用S类，否则一致性问题是不可解的。因此，可以通过网络可崩溃的MH数目来选用不同的FD。

不同类型的FD终止条件good()是不一样的。如果FD属于S类，终止条件是收到的回复MH集合中包含一个永远不会被任何MH怀疑的MH；如果FD属于?S类，终止条件是收到的回复中至少包含(f+1)个MH，即必须包含一个正确的MH。

HCS协议通过预先定义的至少(f+1)个MH作为代理，在每一轮，某一个代理MH作为协调者提出提议值，收到的代理MH转发提议值；收到提议值的MH发送回复消息给代理，代理合并消息后，发送回复消息给协调者，协调者作为决策者通过收到的回复作出决定。如果令代理MH包含至少(f+1)个MH，D＝{协调者}，A＝{代理MH}；系统配?P类FD；good()包含(f+1)个MH的回复；那么通用一致性协议就和HCS协议等价。因此，HCS协议是VCBC协议的一个特例。

3  性能分析

一致性协议的性能主要从时间开销与消息开销2个方面进行评价，性能指标有平均轮数(NR)，平均跳数(NH)和执行时间(ET)。平均轮数影响多轮协议的性能，每增加一轮网络达成一致性的执行时间和交换消息数量都会显著增加。在MANET中，由于无线通信的距离有限，一般2个MHs之间的消息传递需要通过其他MH的中继与转发才能实现。

性能测试采用NS2网络模拟器^[16]，与VCP^[8]协议进行性能比较。模拟器的参数设置如表1所示。

表1  模拟器参数设置

Table 1  Setting of simulation

由于VCP与VCBC协议都是通用一致性协议，因此，对于底层FD和节点可崩溃数目的要求是一致的，FD采用?S类。除FD外，对协议影响最大的的因素是D与A的定义。对每个协议的性能采用|D∪A|=2 (D＝{cc}，A＝{nc}, nc为下一轮的仲裁者)和|D∪A|=n。|D∪A|=2时协议的平均轮数(NR)如图2所示。

图2  |D∪A|=2时协议的平均轮数(NR)

Fig.2  Performance comparison: number of rounds(NR) when |D∪A|=2

图2中在|D∪A|=2时，VCP协议的平均轮数要比VCBC协议少一点。这是因为VCBC协议采用分簇的方法，会将网络中的崩溃累积，从而增加一致性达成的时间。当|D∪A|=n时，2个协议达成一致性基本上只需要1轮就可以。

协议的平均跳数(NH)如图3所示。从图3可见：VCBC协议在运行时的平均跳数比VCP协议要少，并且随着网络规模的扩大，跳数就会减少的更快。在节点个数小于25时，2个协议的跳数基本相同，这是因为当网络规模较小时，节省的消息会因为相当的控制消息而没有节省太多的网络计算资源。

协议的执行时间(ET)如图4所示。图 4中VCP协议的执行时间总体上要比VCBC协议要长，这是因为VCP协议中有太多的消息需要转发，而节点的处理能力有限，会造成一定的阻塞，从而延长每一轮的时间，也使得ET增大。而|D∪A|=2时协议ET要比|D∪A|=n时的大，因为所有的节点都必须等待cc和nc 2个节点的回复消息才能进入下一轮，使得网络依赖于单个节点，降低系统性能。

图3  协议的平均跳数(NH)

Fig.3  Performance comparison: number of hops (NH)

图4  协议的执行时间(ET)

Fig.4  Performance comparison: execution time (ET)

从上述分析可知，VCBC协议能够显著地节约消息成本，并且网络规模越大，节约的成本越多，因为n越大，簇头节点的簇成员越多，合并在一直的回复消息就越多，节约的成本就更多。另外，簇头节点占节点总数的比值对性能有较大的影响。如果簇头节点较少，合并的回复消息就比较多，但是这样簇成员到簇头的消息成本就会大一些。相反，如果簇头节点较多，合并的回复消息就会减少，簇成员到簇头节点的消息成本也会减少。

4  结论

(1) 提出用于MANET的基于分簇的通用一致性VCBC协议，VCBC协议分为DC层和RC层。DC层基于不可靠故障检测器对网络进行分簇，RC层采用异步多轮式2阶段快速决定方式。

(2) VCBC协议分簇可以合并消息，减少网络中的消息数量，节省网络资源。在VCBC协议每一轮，协调者提出提议值，并发送给所有的簇头节点，簇头节点将提议值分发给簇成员，簇成员如果同意作出决定，就发送回复消息给簇头，簇头合并回复消息，并发送总的回复消息给所有决策者和一致性保管者，决策者根据收到的回复作出决定，并通过可靠的分发机制将决定值广播。

(3) VCBC协议是通用的，通过定义消息交换模式和可崩溃的节点数目可以导出一系列的等价协议簇。

(4) 通过NS2软件进行仿真实验，实验结果表明VCBC协议在NR，NH和ET 3个方面都优于其他   协议。

参考文献：

[1] WU Wei-gang, Cao J, Raynal M. The eventual clusterer oracle and its application to consensus in MANETs[C]//HUAI Jin-peng. Proceedings of the 26th IEEE International Symposium on Reliable Distributed Systems (SRDS’07). Los Alamitos, California: IEEE Computer Society Press, 2007: 23-32.

[2] WU Wei-gang, Cao J, Raynal M. Eventual cluster: A modular approach to designing hierarchical consensus protocols in MANETs[J]. IEEE Transactions on Paralllel and distributed Systems, 2009, 20(6): 753-765.

[3] ZHOU Jing-li, YANG Guang, DONG Li-jun, et al. Implementation and performance evaluation of an adaptable failure detector for distributed system[C]//WANG Yu-ping. Proceedings of 2007 International Conference on Computational Intelligence and Security. Los Alamitos, California: IEEE Computer Society Press, 2007: 266-270.

[4] Seba H, Badache N, Bouabdallah A. Solving the consensus problem in a dynamic group: An approach suitable for a mobile environment[C]//Corradi A. Proceedings of the Seventh International Symposium on Computers and Communications (ISCC’02). Los Alamitos, California: IEEE Computer Society Press, 2002: 327-332.

[5] WU W G, Cao J, Raynal M. Using asynchrony and zero degradation to speed up indulgent consensus protocols[J]. Journal of Parallel and Distributed Computing, 2008, 86(7): 984-996.

[6] WU W G, Cao J, Raynal M. A hierarchical consensus protocol for mobile Ad Hoc networks[C]//Cantarella J D. Proceedings of the 14th Euromicro International Conference on Parallel, Distributed, and Network-Based Processing (PDP’06). Los Alamitos, California: IEEE Computer Society Press, 2006: 15-17.

[7] Hurfin M, Mostefaoui A, Raynal M. A versatile family of consensus protocols based on chandra-toueg’s unreliable failure detectors[J]. IEEE Transactions on Computers, 2002, 51(4): 395-408.

[8] WU W G, Cao J, YANG J, et al. Design and performance evaluation of efficient consensus protocols for mobile ad hoc networks[J]. IEEE Transactions on Computers, 2007, 56(8): 1055-1070.

[9] Harri J, Filali F, Bonnet C. Mobility models for vehicular Ad Hoc networks: a survey and taxonomy[J]. IEEE Communications Surveys & Tutorials, 2009, 11(4): 19-41.

[10] Larrea M, Fernandez A, Arevalo S. On the implementation of unreliable failure detectors in partially synchronous systems[J]. IEEE Transactions on Computers, 2004, 53(7): 815-828.

[11] Park T, Shin K G. Optimal tradeoffs for location-based routing in large-Scale Ad Hoc networks[J]. IEEE/ACM Transactions on Networking, 2005, 13(2): 398-410.

[12] Bauso D, Giarre L, Presenti R. Challenging aspects in consensus protocols for networks[C]//Proceedings of the 3rd International Symposium on Communications, Control and Signal Proceeding (ISCCSP’08). Los Alamitos, California: IEEE Computer Society Press, 2008: 660-665.

[13] Nedos A, Singh K, Cunningham R, et al. Probabilistic discovery of semantically diverse content in MANETs[J]. IEEE Transactions on Mobile Computing, 2009, 8(4): 544-557.

[14] Vollset E, Ezhilchelvan P D. Design and performance-study of crash-tolerant protocols for broadcasting and reaching consensus in MANETs[C]//Singhal M. Proceedings of the 24th IEEE Symposium on Reliable Distributed Systems (SRDS ’05). Los Alamitos, California: IEEE Computer Society Press, 2005: 166-175.

[15] ZHAO Qing, Tong L. Energy efficiency of large-scale wireless networks: proactive versus reactive networking[J]. IEEE Journal on Selected Areas in Communications, 2005, 23(5): 1100-1112.

[16] Hogie L, Bouvry P, Guinand F. An overview of MANETs simulation[J]. Electronic Notes in Theoretical Computer Science, 2006, 150(1): 81-101.

(编辑 邓履翔)

收稿日期：2011-03-20；修回日期：2011-05-19

基金项目：国家自然科学基金资助项目(61073037)

通信作者：雷向东(1964-)，男，湖南常宁人，副教授，博士，从事移动网络计算方面的研究；电话：13786153879；E-mail: leixiangdong@csu.edu.cn