基于FM-Chord算法的天基分布式衛(wèi)星組網(wǎng)控制方法

程學(xué)斐，魯稼葦，李靜林

(北京郵電大學(xué) 網(wǎng)絡(luò)與交換技術(shù)國家重點(diǎn)實(shí)驗(yàn)室，北京 100876)

0 引言

天地一體化網(wǎng)絡(luò)是以地面網(wǎng)絡(luò)為基礎(chǔ)、空間網(wǎng)絡(luò)為延伸，覆蓋太空、空中、陸地和海洋等自然空間，為天基、空基、陸基和?；雀黝愑脩舻幕顒犹峁┬畔⒈Ｕ系幕A(chǔ)設(shè)施[1]，由文獻(xiàn)[2-6]可知，天基網(wǎng)絡(luò)可采用低軌/中軌衛(wèi)星混合高軌衛(wèi)星組網(wǎng)，由低軌/中軌衛(wèi)星提供地面站的接入，高軌衛(wèi)星提供業(yè)務(wù)載荷，且分布式星群網(wǎng)絡(luò)更有優(yōu)勢，因此在高軌衛(wèi)星部分，可采用P2P分布式網(wǎng)絡(luò)，并使用Chord[7]算法對其業(yè)務(wù)載荷的存儲和查詢提供支持。

目前分布式P2P網(wǎng)絡(luò)普遍使用Chord算法和Pastry算法[8]，分布式P2P網(wǎng)絡(luò)起源于有線網(wǎng)絡(luò)，因此將其運(yùn)用于無線網(wǎng)絡(luò)中時(shí)，存在一些問題[9]，如節(jié)點(diǎn)負(fù)載均衡、資源快速查詢以及路由快速收斂問題。文獻(xiàn)[10-11]分別提出了一種動態(tài)反饋機(jī)制和一種選擇后繼節(jié)點(diǎn)的啟發(fā)式算法，以改善P2P分布式網(wǎng)絡(luò)中負(fù)載均衡問題。文獻(xiàn)[12-13]分別提出了“鄰居表”這一概念，以及一種基于蟻群優(yōu)化算法和雙向路由查詢算法的Chord改進(jìn)算法，以提高查詢速率；文獻(xiàn)[14]在Chord算法基礎(chǔ)上提出了一種新的加入算法，以減少節(jié)點(diǎn)加入離開造成的維護(hù)開銷。

然而先前的研究忽略了Chord算法中finger表冗余而造成的高頻率維護(hù)問題。本文結(jié)合骨干衛(wèi)星總數(shù)目變動少、衛(wèi)星運(yùn)動具有一定周期性的特點(diǎn)，提出快速維護(hù)Chord算法(Fast-Maintain Chord，F(xiàn)M-Chord)。FM-Chord算法在對路由節(jié)點(diǎn)維護(hù)的過程中，結(jié)合所計(jì)算的冗余臨界點(diǎn)，對節(jié)點(diǎn)的路由表更新，從而減小路由信息維護(hù)的頻度，縮短路由信息維護(hù)的同步時(shí)間。

1 FM-Chord算法

1.1 算法改進(jìn)基本思想

在分布式P2P網(wǎng)絡(luò)中，每個節(jié)點(diǎn)保存一個長度為Ο(lbn)的不同跳數(shù)與后繼節(jié)點(diǎn)的映射表[15]。Chord算法通過一致性哈希將資源和主機(jī)映射到一維順時(shí)針Chord環(huán)上[16]，通過類似于二分查找的方式[17]，實(shí)現(xiàn)資源的定位和網(wǎng)絡(luò)拓?fù)涞木S護(hù)。

本文提出的FM-Chord算法相對于Chord算法存在以下2處應(yīng)加以改進(jìn)：

① 在路由信息映射表的維護(hù)過程中，記錄歷史路由信息，并在此基礎(chǔ)上對其鄰居進(jìn)行試探，判斷其前驅(qū)節(jié)點(diǎn)的哈希值與路由表項(xiàng)的跳數(shù)的映射關(guān)系，該方法可以避免路由維護(hù)對數(shù)級復(fù)雜度的重復(fù)定位，加快路由維護(hù)的過程。

② 通過計(jì)算路由信息的冗余臨界點(diǎn)，在路由維護(hù)過程中跳過不必要的路由維護(hù)過程，避免對整個路由表進(jìn)行維護(hù)，減輕路由維護(hù)的負(fù)擔(dān)。

改進(jìn)的Chord算法可以加快路由維護(hù)過程，故稱其為快速維護(hù)Chord(FM-Chord)算法。算法分為冗余臨界點(diǎn)計(jì)算算法和路由維護(hù)改進(jìn)算法。

1.2 冗余臨界點(diǎn)計(jì)算算法

冗余性是指Chord的Finger表中存在無用項(xiàng)，那些處在NodeN和其successor之間的項(xiàng)均無意義，因?yàn)檫@些項(xiàng)所代表的successor不存在。適當(dāng)?shù)娜哂嘈畔⒖梢蕴岣逤hord網(wǎng)絡(luò)的穩(wěn)定性，過大的冗余信息會降低空間存儲的效率，減低資源查找的效率[18]。Chord網(wǎng)絡(luò)冗余示意圖如圖1所示。

圖1 Chord網(wǎng)絡(luò)冗余示意

假設(shè)Chord環(huán)的大小為N=2m，節(jié)點(diǎn)數(shù)為n=2r，Chord算法默認(rèn)使用SHA-1進(jìn)行對節(jié)點(diǎn)和資源的一致性哈希，由于SHA-1算法的效果，節(jié)點(diǎn)與資源是均勻分布在Chord環(huán)上，節(jié)點(diǎn)之間的平均距離是2m/2r，只要路由的任意2跳數(shù)在同一等分范圍內(nèi)，它們的映射節(jié)點(diǎn)就會相同，則可得出任一節(jié)點(diǎn)N的Finger表中的前i項(xiàng)為冗余的條件為：

(1)

化簡得i<=m-r+1，即當(dāng)i<=m-r+1時(shí)有冗余。并且，資源數(shù)目往往遠(yuǎn)大于節(jié)點(diǎn)數(shù)目，即m>>r，故Chord會存在很多的冗余信息。優(yōu)化路由表信息的查找過程，可以解決該冗余問題。

資源查找：當(dāng)掃描某一衛(wèi)星節(jié)點(diǎn)N的路由表時(shí)，先掃描路由節(jié)點(diǎn)的第一項(xiàng)(即跳數(shù)為N+20)，查詢其映射節(jié)點(diǎn)，假設(shè)為K，那么在后續(xù)的掃描中，可以直接跳過后續(xù)的若干項(xiàng)，直接查詢跳數(shù)大于K的第一項(xiàng)，即直接跳轉(zhuǎn)到項(xiàng)數(shù)為next的項(xiàng)，進(jìn)行后續(xù)的查找，其中next求解為：

(2)

路由表更新：當(dāng)更新某一節(jié)點(diǎn)N的路由表時(shí)，先更新路由表的第一項(xiàng)，更新其節(jié)點(diǎn)為K，那么同理，可以一次性地將所有next項(xiàng)之前的映射節(jié)點(diǎn)置為K。

節(jié)點(diǎn)加入或退出：當(dāng)某一節(jié)點(diǎn)N加入或退出時(shí)，在向其路由表內(nèi)的映射節(jié)點(diǎn)推送節(jié)點(diǎn)加入更新時(shí)，只需對第一項(xiàng)和從next開始的后續(xù)項(xiàng)的映射節(jié)點(diǎn)發(fā)送更新消息。

1.3 路由維護(hù)改進(jìn)算法

路由表更新考慮2種情形：節(jié)點(diǎn)加入的影響和節(jié)點(diǎn)失聯(lián)或退出的影響。節(jié)點(diǎn)加入的主要影響是雖然過期路由表信息可達(dá)，但是不能反映真實(shí)拓?fù)浣Y(jié)構(gòu)；節(jié)點(diǎn)退出或失聯(lián)的主要影響是路由節(jié)點(diǎn)不可達(dá)。

路由表維護(hù)需要對路由表項(xiàng)的每一項(xiàng)轉(zhuǎn)發(fā)節(jié)點(diǎn)進(jìn)行stabilize試探，試探的結(jié)果有2種可能：節(jié)點(diǎn)成功響應(yīng)或節(jié)點(diǎn)失聯(lián)。

當(dāng)成功響應(yīng)時(shí)，如果發(fā)送值小于接收點(diǎn)前驅(qū)值，則表示該接收節(jié)點(diǎn)是有效的路由節(jié)點(diǎn)，返回該路由節(jié)點(diǎn)；如果發(fā)送值大于等于接收點(diǎn)的前驅(qū)值，則表示有比該節(jié)點(diǎn)更合適的路由節(jié)點(diǎn)，則向前驅(qū)轉(zhuǎn)發(fā)發(fā)送值，以便讓前驅(qū)迭代查詢下去，最終返回合適的路由節(jié)點(diǎn)。

當(dāng)超時(shí)而沒有成功響應(yīng)時(shí)，表明接收節(jié)點(diǎn)失聯(lián)或退出后，沒有及時(shí)更新到發(fā)送點(diǎn)的路由表。這時(shí)，向該節(jié)點(diǎn)的后繼節(jié)點(diǎn)發(fā)送請求，查詢失聯(lián)節(jié)點(diǎn)的后繼節(jié)點(diǎn)。這會導(dǎo)致該節(jié)點(diǎn)的后繼節(jié)點(diǎn)對路由表中同一位置的路由項(xiàng)的更新，如此一直迭代下去，如果該節(jié)點(diǎn)是失聯(lián)節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)，則觸發(fā)節(jié)點(diǎn)失聯(lián)處理，直到找到失聯(lián)節(jié)點(diǎn)的后繼節(jié)點(diǎn)，將該失聯(lián)節(jié)點(diǎn)的后繼值更新到檢查的路由項(xiàng)。

算法前置定義：定義NodeX表示Chord節(jié)點(diǎn)，其中X表示該節(jié)點(diǎn)的哈希值；定義映射fingerT：t→Y，其中t表示跳數(shù)，Y表示跳數(shù)對應(yīng)的路由節(jié)點(diǎn)的哈希值，即fingerT(t)表示t的最近后繼節(jié)點(diǎn)的哈希值；定義映射precursor：NodeX→NodeY，precursor：NodeX→NodeY分別表示NodeX節(jié)點(diǎn)的前驅(qū)和后繼；定義路由維護(hù)請求Stabilize，其中t表示維護(hù)的跳數(shù)，d表示請求的目的節(jié)點(diǎn)，響應(yīng)StabilizeAck，其中y表示更新的映射節(jié)點(diǎn)；定義FindSucc，表示Chord算法的查詢，獲取t的最近后繼節(jié)點(diǎn)的哈希值。

算法考慮情境：假設(shè)存在路由更新源節(jié)點(diǎn)NodeX，其中x表示其哈希值，現(xiàn)需要對該節(jié)點(diǎn)的m項(xiàng)路由表信息進(jìn)行維護(hù)?？紤]第i項(xiàng)路由信息的維護(hù)，其跳數(shù)為X+2i，i∈[0，m-1]。

源節(jié)點(diǎn)NodeX處理過程：

FORiIN[0，2，…，m-1]：#針對每一項(xiàng)路由表 t=X+2i#t表示跳數(shù) Y=fingerT(t)#讀取本地路由表查詢映射節(jié)點(diǎn) IFYISNONE：#若初始路由映射節(jié)點(diǎn)不存在： fingerT(t)=FindSucc(t)#查詢t的后繼節(jié)點(diǎn)并更新路由表 ELSE：#若映射信息已存在： 異步發(fā)消息Stabilize#異步發(fā)送路由維護(hù)消息 IF收到響應(yīng)StabilizeAck：#如果收到路由維護(hù)響應(yīng)： fingerT(t)=y#更新第t項(xiàng)路由表 ELSEIF收到超時(shí)消息：#如果超時(shí)： fingerT(t)=FindSucc(Y)#查詢失聯(lián)節(jié)點(diǎn)后繼節(jié)點(diǎn)并#更新第t項(xiàng)路由映射

目標(biāo)節(jié)點(diǎn)NodeY處理過程：

收到Stabilize消息#接收到源節(jié)點(diǎn)的路由維護(hù)消息IFprecursor(NodeY)的哈希值#向該節(jié)點(diǎn)前驅(qū)轉(zhuǎn)發(fā)路由維護(hù)消息 IF收到響應(yīng)StabilizeAck：#如果收到路由維護(hù)響應(yīng)： 響應(yīng)轉(zhuǎn)發(fā)StabilizeAck#轉(zhuǎn)發(fā)響應(yīng)消息 ELSEIF收到超時(shí)消息：#如果超時(shí)：響應(yīng)StabilizeAck#直接響應(yīng)該節(jié)點(diǎn)哈希值

2 算法性能分析

2.1 FM-Chord算法復(fù)雜度分析

FM-Chord算法利用了原有的歷史路由信息，優(yōu)化路由表維護(hù)過程。與傳統(tǒng)Chord算法相比，其路由維護(hù)階段某一項(xiàng)路由信息的維護(hù)復(fù)雜度由Ο(lbN)優(yōu)化到了Ο(k)，其中k表示路由信息維護(hù)期間Chord環(huán)節(jié)點(diǎn)的變動數(shù)目(包括節(jié)點(diǎn)加入和退出)，可近似看成常數(shù)，其具體分析如下：

① 資源查找復(fù)雜度

Ο(lbN)。

(3)

② 單獨(dú)某一節(jié)點(diǎn)路由表所有項(xiàng)維護(hù)復(fù)雜度

FM-Chord算法在維護(hù)路由表一致性時(shí)，通過對每一路由表項(xiàng)歷史映射節(jié)點(diǎn)的查詢，確認(rèn)路由信息是否有效，以此更新路由表，維護(hù)路由表的一致性。在利用原有轉(zhuǎn)發(fā)信息的基礎(chǔ)上，對其前驅(qū)進(jìn)行試探，查看它是否更適合作為轉(zhuǎn)發(fā)節(jié)點(diǎn)，最壞的情況是Ο(k)，k表示同時(shí)加入或退出的節(jié)點(diǎn)?？啥xChord環(huán)不同節(jié)點(diǎn)狀態(tài)之間的距離為k，即表明與當(dāng)前狀態(tài)相比節(jié)點(diǎn)加入或退出的數(shù)目。由于衛(wèi)星節(jié)點(diǎn)同時(shí)退出或加入的可能性很小，姑且認(rèn)為k為常數(shù)，所以其復(fù)雜度可表示為Ο(1)，而每個節(jié)點(diǎn)的路由表一共有m項(xiàng)，所以更新某一節(jié)點(diǎn)的路由表所需要的時(shí)間為：

Ο(m)。

(4)

③ 節(jié)點(diǎn)加入到路由表完全一致過程的復(fù)雜度

(5)

④ 節(jié)點(diǎn)主動退出到路由表完全一致過程的復(fù)雜度

(6)

⑤ 點(diǎn)失聯(lián)到路由表完全一致過程復(fù)雜度

(7)

⑥ 空間復(fù)雜度

Ο(m×N)。

(8)

2.2 仿真結(jié)果分析

考慮到高軌同步衛(wèi)星的分布式星群組網(wǎng)需求，分別對節(jié)點(diǎn)個數(shù)為2、4、8、16、32、64、96和128的衛(wèi)星網(wǎng)絡(luò)進(jìn)行節(jié)點(diǎn)查詢和路由維護(hù)一致性的模擬。

衛(wèi)星網(wǎng)絡(luò)資源定位和查詢的平均跳數(shù)分析如圖2所示。從分析結(jié)果看，F(xiàn)M-Chord算法對于資源的定位和查詢有一定的改進(jìn)，這是由于本改進(jìn)算法主要針對衛(wèi)星網(wǎng)絡(luò)的節(jié)點(diǎn)路由維護(hù)頻繁的背景下提出的，針對節(jié)點(diǎn)的加入和退出過程中，路由信息一致性維護(hù)來進(jìn)行優(yōu)化，以減少衛(wèi)星間路由維護(hù)所造成的通信開銷。

圖2 資源查詢平均跳數(shù)對比

路由維護(hù)的平均跳數(shù)對比分析如圖3所示。在節(jié)點(diǎn)數(shù)相對較少時(shí)，F(xiàn)M-Chord算法比傳統(tǒng)的Chord算法需要更多的跳數(shù)來維護(hù)路由一致性，這是由于FM-Chord算法需要針對歷史的節(jié)點(diǎn)路由信息進(jìn)行查詢和相應(yīng)的維護(hù)，然后在此基礎(chǔ)上，再進(jìn)一步進(jìn)行節(jié)點(diǎn)的路由維護(hù)。但是在節(jié)點(diǎn)數(shù)相對較多的情況下，F(xiàn)M-Chord算法可以顯著提高路由維護(hù)的效率。

圖3 路由維護(hù)平均跳數(shù)對比

模擬實(shí)驗(yàn)表明，F(xiàn)M-Chord算法雖然在資源查詢上沒有顯著的優(yōu)化結(jié)果，但是在路由一致性維護(hù)上，在節(jié)點(diǎn)數(shù)相對較多時(shí)具有一定的優(yōu)化和提高，加快了路由的維護(hù)過程。在衛(wèi)星網(wǎng)絡(luò)環(huán)境下，Chord網(wǎng)絡(luò)的節(jié)點(diǎn)運(yùn)動具有規(guī)律性，衛(wèi)星節(jié)點(diǎn)通過不斷加入Chord網(wǎng)絡(luò)來形成穩(wěn)定的天基組網(wǎng)結(jié)構(gòu)，在節(jié)點(diǎn)加入過程中，需要針對路由信息進(jìn)行一致性的維護(hù)，同時(shí)針對衛(wèi)星網(wǎng)絡(luò)的通信不穩(wěn)定性，節(jié)點(diǎn)可能會在一定時(shí)間內(nèi)失聯(lián)，此過程也需要Chord網(wǎng)絡(luò)的路由維護(hù)來實(shí)現(xiàn)其一致性。該算法可以提高此過程的維護(hù)效率，減少衛(wèi)星通信開銷。另一方面，該改進(jìn)算法保留了一致性哈希算法的特點(diǎn)，將需要存儲的信息均衡分散到各個骨干接點(diǎn)，降低了單個骨干接點(diǎn)的接入壓力和存儲開銷。

3 結(jié)束語

在天地一體化混合組網(wǎng)方案的前提下，通過FM-Chord算法對由高軌分布式星群組成的核心網(wǎng)進(jìn)行組網(wǎng)方案的設(shè)計(jì)。將業(yè)務(wù)載荷數(shù)據(jù)分布式存儲在多個衛(wèi)星上，并對接入骨干衛(wèi)星的接入衛(wèi)星提供相應(yīng)的查詢和更新功能。在傳統(tǒng)Chord算法的基礎(chǔ)上，結(jié)合衛(wèi)星總數(shù)變化小，衛(wèi)星移動具有周期性的特點(diǎn)，對算法進(jìn)行改造，提供了良好的分布式存儲和查詢服務(wù)，采用歷史數(shù)據(jù)作為路由信息的更新起點(diǎn)，在一定程度上提高了路由維護(hù)的效率，加快了路由信息的收斂過程。同時(shí)，針對Chord算法的冗余率大的問題，本文通過計(jì)算冗余信息的位置，在路由維護(hù)過程中，跳過冗余部分的路由維護(hù)，進(jìn)一步提高了算法查詢和維護(hù)效率，降低了衛(wèi)星組網(wǎng)的存儲成本和時(shí)間成本，并通過仿真模擬，給出了相應(yīng)的資源定位和路由維護(hù)的對比分析，提出了一個相對合理的高軌衛(wèi)星分布式組網(wǎng)方案。

[1] 李賀武，吳茜，徐恪，等.天地一體化網(wǎng)絡(luò)研究進(jìn)展與趨勢[J].科技導(dǎo)報(bào)，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] 潘成勝.空間信息網(wǎng)絡(luò)的若干關(guān)鍵技術(shù)[J].中國計(jì)算機(jī)學(xué)會通信，2013，9(4)：46-51.

[4] 董云峰，王興龍.衛(wèi)星集群概念研究[J].航天器工程，2012，21(4)：83-88.

[5] 洪佳楠，李少華，薛開平，等.天地一體化網(wǎng)絡(luò)中基于預(yù)認(rèn)證與群組管理的安全切換方案[J].網(wǎng)絡(luò)與信息安全學(xué)報(bào)，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] 胡麗聰，徐雅靜，徐惠民.基于動態(tài)反饋的一致性哈希負(fù)載均衡算法[J].微電子學(xué)與計(jì)算機(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的結(jié)構(gòu)化P2P路由改進(jìn)算法[J].計(jì)算機(jī)工程與設(shè)計(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系統(tǒng)[J].北京理工大學(xué)學(xué)報(bào)，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協(xié)議的最優(yōu)路由表結(jié)構(gòu)[J].上海交通大學(xué)學(xué)報(bào)，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] 熊繼平.對等網(wǎng)絡(luò)中路由機(jī)制及關(guān)鍵技術(shù)研究[D].北京：中國科學(xué)技術(shù)大學(xué)，2006.