基于FM-Chord算法的天基分布式卫星组网控制方法

程学斐，鲁稼苇，李静林

(北京邮电大学 网络与交换技术国家重点实验室，北京 100876)

0 引言

天地一体化网络是以地面网络为基础、空间网络为延伸，覆盖太空、空中、陆地和海洋等自然空间，为天基、空基、陆基和海基等各类用户的活动提供信息保障的基础设施[1]，由文献[2-6]可知，天基网络可采用低轨/中轨卫星混合高轨卫星组网，由低轨/中轨卫星提供地面站的接入，高轨卫星提供业务载荷，且分布式星群网络更有优势，因此在高轨卫星部分，可采用P2P分布式网络，并使用Chord[7]算法对其业务载荷的存储和查询提供支持。

目前分布式P2P网络普遍使用Chord算法和Pastry算法[8]，分布式P2P网络起源于有线网络，因此将其运用于无线网络中时，存在一些问题[9]，如节点负载均衡、资源快速查询以及路由快速收敛问题。文献[10-11]分别提出了一种动态反馈机制和一种选择后继节点的启发式算法，以改善P2P分布式网络中负载均衡问题。文献[12-13]分别提出了“邻居表”这一概念，以及一种基于蚁群优化算法和双向路由查询算法的Chord改进算法，以提高查询速率；文献[14]在Chord算法基础上提出了一种新的加入算法，以减少节点加入离开造成的维护开销。

然而先前的研究忽略了Chord算法中finger表冗余而造成的高频率维护问题。本文结合骨干卫星总数目变动少、卫星运动具有一定周期性的特点，提出快速维护Chord算法(Fast-Maintain Chord，FM-Chord)。FM-Chord算法在对路由节点维护的过程中，结合所计算的冗余临界点，对节点的路由表更新，从而减小路由信息维护的频度，缩短路由信息维护的同步时间。

1 FM-Chord算法

1.1 算法改进基本思想

在分布式P2P网络中，每个节点保存一个长度为Ο(lbn)的不同跳数与后继节点的映射表[15]。Chord算法通过一致性哈希将资源和主机映射到一维顺时针Chord环上[16]，通过类似于二分查找的方式[17]，实现资源的定位和网络拓扑的维护。

本文提出的FM-Chord算法相对于Chord算法存在以下2处应加以改进：

① 在路由信息映射表的维护过程中，记录历史路由信息，并在此基础上对其邻居进行试探，判断其前驱节点的哈希值与路由表项的跳数的映射关系，该方法可以避免路由维护对数级复杂度的重复定位，加快路由维护的过程。

② 通过计算路由信息的冗余临界点，在路由维护过程中跳过不必要的路由维护过程，避免对整个路由表进行维护，减轻路由维护的负担。

改进的Chord算法可以加快路由维护过程，故称其为快速维护Chord(FM-Chord)算法。算法分为冗余临界点计算算法和路由维护改进算法。

1.2 冗余临界点计算算法

冗余性是指Chord的Finger表中存在无用项，那些处在NodeN和其successor之间的项均无意义，因为这些项所代表的successor不存在。适当的冗余信息可以提高Chord网络的稳定性，过大的冗余信息会降低空间存储的效率，减低资源查找的效率[18]。Chord网络冗余示意图如图1所示。

图1 Chord网络冗余示意

假设Chord环的大小为N=2m，节点数为n=2r，Chord算法默认使用SHA-1进行对节点和资源的一致性哈希，由于SHA-1算法的效果，节点与资源是均匀分布在Chord环上，节点之间的平均距离是2m/2r，只要路由的任意2跳数在同一等分范围内，它们的映射节点就会相同，则可得出任一节点N的Finger表中的前i项为冗余的条件为：

(1)

化简得i<=m-r+1，即当i<=m-r+1时有冗余。并且，资源数目往往远大于节点数目，即m>>r，故Chord会存在很多的冗余信息。优化路由表信息的查找过程，可以解决该冗余问题。

资源查找：当扫描某一卫星节点N的路由表时，先扫描路由节点的第一项(即跳数为N+20)，查询其映射节点，假设为K，那么在后续的扫描中，可以直接跳过后续的若干项，直接查询跳数大于K的第一项，即直接跳转到项数为next的项，进行后续的查找，其中next求解为：

(2)

路由表更新：当更新某一节点N的路由表时，先更新路由表的第一项，更新其节点为K，那么同理，可以一次性地将所有next项之前的映射节点置为K。

节点加入或退出：当某一节点N加入或退出时，在向其路由表内的映射节点推送节点加入更新时，只需对第一项和从next开始的后续项的映射节点发送更新消息。

1.3 路由维护改进算法

路由表更新考虑2种情形：节点加入的影响和节点失联或退出的影响。节点加入的主要影响是虽然过期路由表信息可达，但是不能反映真实拓扑结构；节点退出或失联的主要影响是路由节点不可达。

路由表维护需要对路由表项的每一项转发节点进行stabilize试探，试探的结果有2种可能：节点成功响应或节点失联。

当成功响应时，如果发送值小于接收点前驱值，则表示该接收节点是有效的路由节点，返回该路由节点；如果发送值大于等于接收点的前驱值，则表示有比该节点更合适的路由节点，则向前驱转发发送值，以便让前驱迭代查询下去，最终返回合适的路由节点。

当超时而没有成功响应时，表明接收节点失联或退出后，没有及时更新到发送点的路由表。这时，向该节点的后继节点发送请求，查询失联节点的后继节点。这会导致该节点的后继节点对路由表中同一位置的路由项的更新，如此一直迭代下去，如果该节点是失联节点的前驱节点，则触发节点失联处理，直到找到失联节点的后继节点，将该失联节点的后继值更新到检查的路由项。

算法前置定义：定义NodeX表示Chord节点，其中X表示该节点的哈希值；定义映射fingerT：t→Y，其中t表示跳数，Y表示跳数对应的路由节点的哈希值，即fingerT(t)表示t的最近后继节点的哈希值；定义映射precursor：NodeX→NodeY，precursor：NodeX→NodeY分别表示NodeX节点的前驱和后继；定义路由维护请求Stabilize，其中t表示维护的跳数，d表示请求的目的节点，响应StabilizeAck，其中y表示更新的映射节点；定义FindSucc，表示Chord算法的查询，获取t的最近后继节点的哈希值。

算法考虑情境：假设存在路由更新源节点NodeX，其中x表示其哈希值，现需要对该节点的m项路由表信息进行维护。考虑第i项路由信息的维护，其跳数为X+2i，i∈[0，m-1]。

源节点NodeX处理过程：

FORiIN[0，2，…，m-1]：#针对每一项路由表 t=X+2i#t表示跳数 Y=fingerT(t)#读取本地路由表查询映射节点 IFYISNONE：#若初始路由映射节点不存在： fingerT(t)=FindSucc(t)#查询t的后继节点并更新路由表 ELSE：#若映射信息已存在： 异步发消息Stabilize#异步发送路由维护消息 IF收到响应StabilizeAck：#如果收到路由维护响应： fingerT(t)=y#更新第t项路由表 ELSEIF收到超时消息：#如果超时： fingerT(t)=FindSucc(Y)#查询失联节点后继节点并#更新第t项路由映射

目标节点NodeY处理过程：

收到Stabilize消息#接收到源节点的路由维护消息IFprecursor(NodeY)的哈希值#向该节点前驱转发路由维护消息 IF收到响应StabilizeAck：#如果收到路由维护响应： 响应转发StabilizeAck#转发响应消息 ELSEIF收到超时消息：#如果超时：响应StabilizeAck#直接响应该节点哈希值

2 算法性能分析

2.1 FM-Chord算法复杂度分析

FM-Chord算法利用了原有的历史路由信息，优化路由表维护过程。与传统Chord算法相比，其路由维护阶段某一项路由信息的维护复杂度由Ο(lbN)优化到了Ο(k)，其中k表示路由信息维护期间Chord环节点的变动数目(包括节点加入和退出)，可近似看成常数，其具体分析如下：

① 资源查找复杂度

Ο(lbN)。

(3)

② 单独某一节点路由表所有项维护复杂度

FM-Chord算法在维护路由表一致性时，通过对每一路由表项历史映射节点的查询，确认路由信息是否有效，以此更新路由表，维护路由表的一致性。在利用原有转发信息的基础上，对其前驱进行试探，查看它是否更适合作为转发节点，最坏的情况是Ο(k)，k表示同时加入或退出的节点。可定义Chord环不同节点状态之间的距离为k，即表明与当前状态相比节点加入或退出的数目。由于卫星节点同时退出或加入的可能性很小，姑且认为k为常数，所以其复杂度可表示为Ο(1)，而每个节点的路由表一共有m项，所以更新某一节点的路由表所需要的时间为：

Ο(m)。

(4)

③ 节点加入到路由表完全一致过程的复杂度

(5)

④ 节点主动退出到路由表完全一致过程的复杂度

(6)

⑤ 点失联到路由表完全一致过程复杂度

(7)

⑥ 空间复杂度

Ο(m×N)。

(8)

2.2 仿真结果分析

考虑到高轨同步卫星的分布式星群组网需求，分别对节点个数为2、4、8、16、32、64、96和128的卫星网络进行节点查询和路由维护一致性的模拟。

卫星网络资源定位和查询的平均跳数分析如图2所示。从分析结果看，FM-Chord算法对于资源的定位和查询有一定的改进，这是由于本改进算法主要针对卫星网络的节点路由维护频繁的背景下提出的，针对节点的加入和退出过程中，路由信息一致性维护来进行优化，以减少卫星间路由维护所造成的通信开销。

图2 资源查询平均跳数对比

路由维护的平均跳数对比分析如图3所示。在节点数相对较少时，FM-Chord算法比传统的Chord算法需要更多的跳数来维护路由一致性，这是由于FM-Chord算法需要针对历史的节点路由信息进行查询和相应的维护，然后在此基础上，再进一步进行节点的路由维护。但是在节点数相对较多的情况下，FM-Chord算法可以显著提高路由维护的效率。

图3 路由维护平均跳数对比

模拟实验表明，FM-Chord算法虽然在资源查询上没有显著的优化结果，但是在路由一致性维护上，在节点数相对较多时具有一定的优化和提高，加快了路由的维护过程。在卫星网络环境下，Chord网络的节点运动具有规律性，卫星节点通过不断加入Chord网络来形成稳定的天基组网结构，在节点加入过程中，需要针对路由信息进行一致性的维护，同时针对卫星网络的通信不稳定性，节点可能会在一定时间内失联，此过程也需要Chord网络的路由维护来实现其一致性。该算法可以提高此过程的维护效率，减少卫星通信开销。另一方面，该改进算法保留了一致性哈希算法的特点，将需要存储的信息均衡分散到各个骨干接点，降低了单个骨干接点的接入压力和存储开销。

3 结束语

在天地一体化混合组网方案的前提下，通过FM-Chord算法对由高轨分布式星群组成的核心网进行组网方案的设计。将业务载荷数据分布式存储在多个卫星上，并对接入骨干卫星的接入卫星提供相应的查询和更新功能。在传统Chord算法的基础上，结合卫星总数变化小，卫星移动具有周期性的特点，对算法进行改造，提供了良好的分布式存储和查询服务，采用历史数据作为路由信息的更新起点，在一定程度上提高了路由维护的效率，加快了路由信息的收敛过程。同时，针对Chord算法的冗余率大的问题，本文通过计算冗余信息的位置，在路由维护过程中，跳过冗余部分的路由维护，进一步提高了算法查询和维护效率，降低了卫星组网的存储成本和时间成本，并通过仿真模拟，给出了相应的资源定位和路由维护的对比分析，提出了一个相对合理的高轨卫星分布式组网方案。

[1] 李贺武，吴茜，徐恪，等.天地一体化网络研究进展与趋势[J].科技导报，2016(14)：95-106.

[2] ANDREWS J.Constellation ofDistributed Nanosats for Real Time Earth Observation[C]∥8th IAA Symposium on Small Satellites for Earth Observation，Berlin：IAA，2011：4-8.

[3] 潘成胜.空间信息网络的若干关键技术[J].中国计算机学会通信，2013，9(4)：46-51.

[4] 董云峰，王兴龙.卫星集群概念研究[J].航天器工程，2012，21(4)：83-88.

[5] 洪佳楠，李少华，薛开平，等.天地一体化网络中基于预认证与群组管理的安全切换方案[J].网络与信息安全学报，2016，2(7)：33-41.

[6] ASOREY-CACHEDA R，GONZALEZ-CASTANO F J，CAVIGLIONE L，et al.P2P in Satellite Networks：a Tutorial on Related Problems and Some Possible Solutions [C]∥ International Symposium on Wireless Communication Systems，IEEE，2005：733-736.

[7] STOICA I，MORRIS R，LIBEN-NOWELL D，et al.Chord：a Scalable Peer-to-Peer Lookup Protocol for Internet Applications [J].IEEE/ACM Transactions on Networking，2003，11(1)：17-32.

[8] KARRELS D R，PETERSON G L，MULLINS B E.RC-Chord：Resource Clustering in a Large-scale Hierarchical Peer-to-Peer System[J].IEEE Military Communications Conference，2009：1-7.

[9] WOUNGANG I，TSENG F H，LIN Y H，et al.MR-Chord：Improved Chord Lookup Performance in Structured Mobile P2P Networks [J].IEEE Systems Journal，2015，9(3)：743-751.

[10] 胡丽聪，徐雅静，徐惠民.基于动态反馈的一致性哈希负载均衡算法[J].微电子学与计算机，2012(1)：177-180.

[11] DING Z M，QIAN Q.A Chord-based Load Balancing Algorithm for P2P Network[C]∥ Information and Network Security，ICINS 2014-2014 International Conference on IET，2014：91-96.

[12] 成培，胡峰松，粟智.基于Chord的结构化P2P路由改进算法[J].计算机工程与设计，2009(1)：63-65.

[13] ZHAO L，SHEN H，LI Y，et al.AB-Chord：An Improved Chord Based on Ant Colony Optimization and Bi-Directional Lookup Routing [C]∥ Sixth International Symposium on Parallel Architectures，Algorithms and Programming，IEEE，2014：172-177.

[14] 任小金，古志民，高志伟，等.RR-Chord：一个基于Chord的低开销快速查询P2P系统[J].北京理工大学学报，2008(2)：134-138.

[15] BINZENHOFER A，STAEHLE D，HENJES R.On the Stability of Chord-based P2P Systems [C]∥ On the stability of Chord-based P2P Systems，2004.

[16] 张亮，邹福泰，马范援.Chord协议的最优路由表结构[J].上海交通大学学报，2005(8)：1276-1279.

[17] BENTER M，DIVBAND M，KNIESBURGES S，et al.Ca-Re-Chord：A Churn Resistant Self-Stabilizing ChordOverlay Network[C]∥ Conference on Networked Systems，IEEE Computer Society，2013：27-34.

[18] 熊继平.对等网络中路由机制及关键技术研究[D].北京：中国科学技术大学，2006.