移动自组织网络的分层领导者选举协议

### 移动自组织网络的分层领导者选举协议 #### 1. 引言 领导者选举在分布式系统中是一个基础问题，众多研究者都对此进行了探讨。在移动自组织网络（MANETs）中，领导者选举是一个较新的研究领域。之前已有一些针对MANETs的领导者选举算法被提出，不过这些算法大多是从普通节点中选举领导者。而本文提出的算法是从之前选定的领导者中选举一个超级领导者。 本文提出了一个用于MANETs的三层领导者选举协议（LEP）。该协议的最低层使用合并聚类算法（MCA）将MANET划分为平衡的簇；第二层采用骨干形成算法（BFA）构建簇领导者的虚拟环架构；最后，使用移动Chang Roberts领导者选举算法（Mobile CR）在第二层选举出的领导者中选出超级领导者。 #### 2. 背景 ##### 2.1 使用合并聚类算法进行聚类 无向图定义为 $G = (V, E)$，其中 $V$ 是有限非空节点集，$E$ 是边集。合并聚类算法（MCA）通过合并簇来在MANET中找到簇，它舍弃了最小生成树，从而降低了消息复杂度。此外，使用上下界参数进行聚类操作，使得形成的簇中节点数量平衡。该协议在ns2中进行了模拟，结果显示在不同密度和移动性条件下具有稳定性。 ##### 2.2 骨干形成算法 骨干形成算法在聚类后的MANET上构建骨干架构，将其构建为有向环架构，具有以下优势： - 利用了环拓扑的优点，为其他中间件协议提供更好的服务。 - 连接平衡聚类方案的簇头，满足聚类的两个基本需求：平衡簇和最小化路由延迟。 - 具有容错性。 该算法有两种操作模式：基于跳数的骨干形成方案和基于位置的骨干形成方案。在ns2模拟器上实现该算法，结果显示在不同MANET条件下具有稳定性。 #### 3. 提出的架构 提出了一个四层架构用于MANETs，具体如下： | 层次 | 功能 | 采用算法 | | ---- | ---- | ---- | | 最低层 | 路由层 | AODV路由协议，也可使用其他协议 | | 第二层 | 聚类层 | 合并聚类算法（MCA），形成平衡簇 | | 第三层 | 构建虚拟环 | 骨干形成算法（BFA），形成簇领导者的虚拟环 | | 第四层 | 领导者选举 | 移动Chang Roberts算法（Mobile CR） | 其架构流程如下： ```mermaid graph LR A[Ad hoc on Demand Distance Vector] --> B[Merging Clustering Algorithm] B --> C[Backbone Formation Algorithm] C --> D[Mobile Chang Roberts Algorithm] ``` #### 4. 移动Chang - Roberts算法 Chang Roberts算法是用于单向环网络的异步领导者选举算法。每个进程可以是红色（潜在领导者候选者）或黑色（已退出状态）。算法的非正式描述如下： 1. 初始时，所有发起进程为红色。 2. 每个发起者 $i$ 向其邻