基于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表示同時加入或退出的節點?？啥xChord環不同節點狀態之間的距離為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.