论文部分内容阅读
移动自组织网络是一种新型分布式系统,它不依赖基础设施,可用于人类无法或不便直接介入的特殊场景。近似一致性是经典一致性问题的弱化形式,它允许各参与节点在达成一致时存在可容忍范围内的误差。近似一致性可以作为自组织网络中的一个基础性问题,它涵盖了时钟同步、分布式数据融合、智能体协同、移动节点编队等现实应用。 现有的近似一致性求解方法往往依赖于全连接网络,或全网拓扑信息。然而移动自组织网络多跳连接的组网方式和移动特性,使得全网拓扑结构、所有节点当前状态等全局信息不易实时获得。针对移动自组织网络的内在特性,本文摒弃了集中式方法、复杂的计算逻辑以及很难实时获得的全局信息,使用了轻量级的分布式算法和较易获得的邻居信息。此外,针对自组织网络的开放性以及易受攻击性,本文提出的算法均可容忍少量的拜占庭失效。本文主要贡献和结论包括: (1)基于分布式线性迭代方法提出了一个新的拜占庭近似一致性算法LBAC(LinearByzantine Approximate Consensus)。算法LBAC允许节点使用一个连续的时间段来收集信息。该策略充分利用了移动性,增加了节点安全执行状态更新计算的机会。为了约束节点移动行为,保障算法最终的收敛性,本文提出了一个新的可保证收敛的充分必要条件:仅需要系统中的部分节点(“非全局性”)不断收集到足够数量的(“数量约束”)且满足特定性质的(“质量约束”)状态信息。此外,针对节点内部缓存,本文提供了两种不同的选择策略和两种不同的清理策略,并通过仿真实验对这四种策略不同组合下构造的三种具体算法进行了性能分析。 (2)时钟同步问题中的同步需求,可抽象为近似一致性问题。基于拜占庭近似一致性算法LBAC,本文为移动自组织网络设计了一个新的时钟同步算法BCSA(ByzantineClock Synchronization Algorithm)。算法BCSA允许节点通过与其它节点的不断交互,以迭代的方式对时钟值进行逐步调整。此外,算法BCSA通过时戳值转换方法,消除了时钟值会独立于同步算法而完成的周期性自增操作所带来的负面影响。为了分析同步算法BCSA在随机移动模型下的同步效果,本文通过矩阵和向量计算来建模同步过程,得到了影响同步精度的关键性因素,并通过仿真实验进行了验证。 (3)自组织网络的正常运行依赖于各参与节点的分工协作。为自组织网络构建信誉系统是一种通过量化方式来评估节点行为的策略。在信誉系统中,一个节点可通过不断积累、更新对目标节点服务质量的观测值,计算出一个量化指标“信誉等级”,从而根据信誉等级,对目标节点的未来行为进行评估。信誉等级更新问题隶属于分布式数据融合,也可抽象为近似一致性。信誉等级更新可通过获取“一手信息”和“二手信息”两种方式进行。为了屏蔽拜占庭节点发出的虚假二手信息,本文以拜占庭近似一致性算法LBAC为基础,提出了一个新的信誉等级更新算法RUA(Reputation UpdatingAlgorithm)。依据此算法,节点在收集到足够数量的二手信息后,首先剔除其中的“风险值”,然后执行融合计算。此外,在目标节点服务质量不变的前提下,本文提出了一个充要条件,使得其余正确节点的信誉等级最终可收敛到一个与目标节点服务质量相称的合理值。