陳宇， 張勇，2， 陳實(shí)

(1. 中國科學(xué)院 國家空間科學(xué)中心，北京 100190； 2. 中國科學(xué)院大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，北京 101408)

衛(wèi)星通過模塊間的無線鏈路實(shí)現(xiàn)復(fù)雜的信息交互進(jìn)而完成相互間的協(xié)作，并最終構(gòu)成分布式衛(wèi)星集群系統(tǒng)，執(zhí)行多樣化的空間任務(wù)，已經(jīng)成為未來衛(wèi)星系統(tǒng)的重要發(fā)展趨勢之一[1]. 隨著衛(wèi)星集群編隊(duì)構(gòu)型以及空間通信等技術(shù)的日漸成熟[2-3]，未來衛(wèi)星集群系統(tǒng)的規(guī)模將越來越大，傳統(tǒng)的平面式管理結(jié)構(gòu)存在管理時(shí)延大、負(fù)載不均衡、可靠性低的缺點(diǎn). 相比之下，采用分簇算法將整個(gè)網(wǎng)絡(luò)轉(zhuǎn)化為層級化的網(wǎng)絡(luò)結(jié)構(gòu)具有非常多的優(yōu)勢：有效利用多信道技術(shù)提高網(wǎng)絡(luò)容量，優(yōu)化節(jié)點(diǎn)帶寬的利用；通過選取適當(dāng)?shù)墓?jié)點(diǎn)作為簇首，有效減少網(wǎng)絡(luò)中路由控制信息的開銷，優(yōu)化網(wǎng)絡(luò)管理；屏蔽局部拓?fù)浣Y(jié)構(gòu)變化的影響，提高整體網(wǎng)絡(luò)結(jié)構(gòu)的穩(wěn)定性；可隨新節(jié)點(diǎn)的加入和任務(wù)需要而不斷自我調(diào)整，具有良好的可拓展性.

現(xiàn)有的分簇算法大多是基于地面無線自組網(wǎng)提出的，并取得了完善的發(fā)展. 在此基礎(chǔ)上，研究人員對應(yīng)用于衛(wèi)星網(wǎng)絡(luò)的分簇算法進(jìn)行了許多研究[4-8]，然而其大多是基于衛(wèi)星星座提出的，網(wǎng)絡(luò)拓?fù)湎鄬潭? 在大規(guī)模衛(wèi)星集群中，集群內(nèi)衛(wèi)星分布在相對距離幾百米到幾千米的范圍內(nèi)，網(wǎng)絡(luò)結(jié)構(gòu)比較靈活，且各衛(wèi)星在一定范圍內(nèi)相互繞飛，網(wǎng)絡(luò)拓?fù)洳粩喟l(fā)生改變[1]. 因此，本文提出了一種新型的自適應(yīng)加權(quán)分簇算法，初始化由地面終端根據(jù)衛(wèi)星集群網(wǎng)絡(luò)的先驗(yàn)信息計(jì)算出加權(quán)權(quán)重劃分簇首和成員節(jié)點(diǎn)，星上只運(yùn)行簇的維護(hù)階段，另外對節(jié)點(diǎn)入簇和狀態(tài)改變的條件進(jìn)行優(yōu)化，以達(dá)到更好的負(fù)載均衡并且降低管理維護(hù)的開銷.

1 總體設(shè)計(jì)

分簇算法根據(jù)系統(tǒng)要求將衛(wèi)星集群劃分成多個(gè)集合，理想情況下希望以最少的簇頭覆蓋整個(gè)網(wǎng)絡(luò)[8]. 為了減少分簇算法帶來的額外控制開銷，提高網(wǎng)絡(luò)容量的實(shí)際利用率，分簇算法應(yīng)該盡量保證較低的算法復(fù)雜度. 此外，衛(wèi)星集群網(wǎng)絡(luò)中節(jié)點(diǎn)間的相對移動(dòng)會導(dǎo)致簇內(nèi)拓?fù)潢P(guān)系發(fā)生變化，嚴(yán)重情況下甚至?xí)鸫厥坠?jié)點(diǎn)更新以及網(wǎng)絡(luò)重新配置，嚴(yán)重降低網(wǎng)絡(luò)的性能. 因此，分簇算法應(yīng)盡量保持原有的網(wǎng)絡(luò)結(jié)構(gòu).

文中提出的大規(guī)模衛(wèi)星集群自適應(yīng)加權(quán)分簇算法以節(jié)點(diǎn)綜合權(quán)值作為簇首選舉及簇結(jié)構(gòu)維護(hù)的重要依據(jù)，權(quán)值計(jì)算主要考慮了連接度、載荷服務(wù)能力以及優(yōu)先級等因素，算法的基本工作步驟如圖1所示. 為了減少分簇帶來的額外開銷，權(quán)值計(jì)算和初始化階段由地面控制終端完成，星上只需要少量的通信和控制開銷即可實(shí)時(shí)分布式地執(zhí)行維護(hù)算法.

圖1 分簇算法工作步驟Fig.1 Working steps of clustering algorithm

2 權(quán)值計(jì)算

分簇算法的核心是簇首節(jié)點(diǎn)的選取，本文中簇首的選取采用組合加權(quán)方式選擇(節(jié)點(diǎn)權(quán)值越大，成為簇首節(jié)點(diǎn)的概率越高)，并考慮了衛(wèi)星節(jié)點(diǎn)的特殊性對加權(quán)參數(shù)進(jìn)行了選擇和優(yōu)化. 下面對本文中選取的加權(quán)參數(shù)進(jìn)行介紹.

平均連接度α：節(jié)點(diǎn)i在一個(gè)周期內(nèi)的平均連接度為

(1)

式中：T為衛(wèi)星網(wǎng)絡(luò)周期；θi表示節(jié)點(diǎn)i在周期中某一時(shí)刻的度(鄰居節(jié)點(diǎn)的數(shù)量). 本文中為了簡化仿真，將周期劃分為多個(gè)時(shí)間片，假定時(shí)間片內(nèi)網(wǎng)絡(luò)的拓?fù)洳话l(fā)生改變，因此時(shí)間片t內(nèi)網(wǎng)絡(luò)的拓?fù)潢P(guān)系可以用鄰接矩陣At來表示，則公式(1)轉(zhuǎn)化為公式(2).

(2)

式中：N為劃分的時(shí)間片的數(shù)量；θi(t)表示在第t個(gè)時(shí)間片內(nèi)節(jié)點(diǎn)i的度數(shù)；aij為1表示第t個(gè)時(shí)間片節(jié)點(diǎn)i和節(jié)點(diǎn)j相連，aij為0則表示第t個(gè)時(shí)間片節(jié)點(diǎn)i和節(jié)點(diǎn)j不相連.

載荷服務(wù)能力ρ表示了衛(wèi)星節(jié)點(diǎn)有效載荷的最大服務(wù)能力，例如：星上存儲、計(jì)算能力、傳輸帶寬與通信范圍等等. 載荷服務(wù)能力ρ為由衛(wèi)星節(jié)點(diǎn)本身能力決定的.

考慮到某些任務(wù)需求，一些節(jié)點(diǎn)可能會被給予更大的期望擔(dān)當(dāng)簇首節(jié)點(diǎn)，因此設(shè)定簇首優(yōu)先級φ∈[0,1]，即優(yōu)先級越高，節(jié)點(diǎn)擔(dān)當(dāng)簇首節(jié)點(diǎn)的概率越高，反之節(jié)點(diǎn)擔(dān)當(dāng)簇首節(jié)點(diǎn)的概率越低.

最后，對于網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)v，其權(quán)值wv計(jì)算公式為

wv=(w1α+w2ρ)φ

(3)

其中系數(shù)w1和w2為相應(yīng)參數(shù)的加權(quán)因子，滿足w1+w2=1，具體值由地面終端根據(jù)需要預(yù)先設(shè)定.

3 分簇算法

本文提出的ADWCA分簇算法分為兩個(gè)階段：簇的初始化和維持階段. 其中，初始化階段由地面終端完成，主要任務(wù)是在初始時(shí)刻劃分所有節(jié)點(diǎn)狀態(tài)，指定適當(dāng)?shù)墓?jié)點(diǎn)擔(dān)當(dāng)簇首節(jié)點(diǎn). 簇的維護(hù)階段負(fù)責(zé)在集群網(wǎng)絡(luò)拓?fù)浒l(fā)生變化時(shí)，對簇結(jié)構(gòu)進(jìn)行維護(hù)，確保所有節(jié)點(diǎn)均在簇結(jié)構(gòu)中. 分簇過程中，將節(jié)點(diǎn)狀態(tài)分為4種：簇首(cluster head ,CH)、普通成員、未定狀態(tài)和游離狀態(tài). 初始時(shí)所有節(jié)點(diǎn)狀態(tài)均為未定. 下面對初始化和維護(hù)階段進(jìn)行詳細(xì)說明.

3.1 初始化階段

初始化階段工作主要由地面終端完成，地面終端根據(jù)集群信息和上述權(quán)值公式計(jì)算出各個(gè)節(jié)點(diǎn)的權(quán)重后，劃分節(jié)點(diǎn)狀態(tài)，過程如下所示.

1) 根據(jù)初始時(shí)刻鄰接矩陣判定節(jié)點(diǎn)是否存在鄰居節(jié)點(diǎn)，若不存在，則將該節(jié)點(diǎn)劃分為游離狀態(tài). 否則，進(jìn)入下一步，此時(shí)節(jié)點(diǎn)為未定狀態(tài).

2) 查找節(jié)點(diǎn)的k跳鄰居節(jié)點(diǎn)中是否存在簇首CH節(jié)點(diǎn)，若存在，則按公式(4)計(jì)算優(yōu)先級最大的CH加入，節(jié)點(diǎn)狀態(tài)劃分為普通成員. 若不存在CH，則進(jìn)入下一步.

(4)

式中：p(i,CHv)表示節(jié)點(diǎn)i加入簇首v的優(yōu)先級度量；wv表示簇首節(jié)點(diǎn)v的權(quán)重；s表示簇內(nèi)節(jié)點(diǎn)數(shù)量；h表示節(jié)點(diǎn)i距簇首節(jié)點(diǎn)v的跳數(shù).

3) 比較節(jié)點(diǎn)自身權(quán)值和k跳內(nèi)鄰居中所有未定節(jié)點(diǎn)權(quán)值，若節(jié)點(diǎn)自身權(quán)值為最大值，則將節(jié)點(diǎn)劃分為簇首節(jié)點(diǎn)，簇內(nèi)節(jié)點(diǎn)數(shù)量初始化為1，否則返回上一步.

初始化過程可能需經(jīng)過多次迭代，直到所有節(jié)點(diǎn)狀態(tài)均確定，算法流程圖如圖2所示.

圖2 初始化算法流程圖Fig.2 Initialization algorithm flow diagram

3.2 維護(hù)階段

初始化階段完成后，衛(wèi)星集群網(wǎng)絡(luò)立刻進(jìn)入簇維護(hù)階段，各節(jié)點(diǎn)通過一定的信息交互(大部分發(fā)生在簇內(nèi))完成自身的狀態(tài)變化，節(jié)點(diǎn)狀態(tài)改變主要分為以下4種.

① 簇首節(jié)點(diǎn)狀態(tài)變化：一般情況下，簇首節(jié)點(diǎn)狀態(tài)不會發(fā)生變化. 當(dāng)簇首節(jié)點(diǎn)不存在鄰居節(jié)點(diǎn)時(shí)，轉(zhuǎn)變?yōu)橛坞x狀態(tài). 另一方面，考慮到負(fù)載均衡，當(dāng)簇內(nèi)節(jié)點(diǎn)數(shù)量超過一定時(shí)限始終為一時(shí)，簇首節(jié)點(diǎn)退化為未定狀態(tài).

② 簇成員節(jié)點(diǎn)狀態(tài)變化：成員節(jié)點(diǎn)判斷自身與原簇首節(jié)點(diǎn)之間即將斷開連接或跳數(shù)大于k跳時(shí)，開始計(jì)時(shí)，超過一定時(shí)限向原簇首節(jié)點(diǎn)發(fā)送離簇申請，并檢索是否有鄰居節(jié)點(diǎn)，若沒有鄰居節(jié)點(diǎn)，則轉(zhuǎn)變?yōu)橛坞x狀態(tài)，否則轉(zhuǎn)變?yōu)槲炊顟B(tài). 本文中，設(shè)定成員節(jié)點(diǎn)大于或等于兩個(gè)時(shí)間片仍與簇首斷開連接時(shí)發(fā)生狀態(tài)改變.

③ 游離節(jié)點(diǎn)狀態(tài)變化：游離節(jié)點(diǎn)發(fā)現(xiàn)自身與其它節(jié)點(diǎn)存在連接時(shí)，轉(zhuǎn)換為未定狀態(tài).

④ 未定節(jié)點(diǎn)狀態(tài)變化：未定狀態(tài)作為一種臨時(shí)態(tài)，節(jié)點(diǎn)在未定狀態(tài)不停留，需要立即轉(zhuǎn)變?yōu)槌蓡T狀態(tài)或簇首. 轉(zhuǎn)變規(guī)則如下：檢索其k跳鄰居內(nèi)是否存在CH，若存在則按照公式(4)計(jì)算并選擇優(yōu)先級最大的CH加入，節(jié)點(diǎn)狀態(tài)轉(zhuǎn)換為普通成員狀態(tài). 若其k跳鄰居內(nèi)不存在CH，且自身權(quán)值最大，則該節(jié)點(diǎn)成為簇首.

維護(hù)階段節(jié)點(diǎn)狀態(tài)轉(zhuǎn)換圖如圖3所示.

圖3 維護(hù)階段節(jié)點(diǎn)狀態(tài)轉(zhuǎn)換圖Fig.3 Node state transition diagram during maintenance phase

4 仿真與分析

衡量一個(gè)分簇算法的優(yōu)劣主要有以下幾個(gè)標(biāo)準(zhǔn)：簇首節(jié)點(diǎn)的數(shù)量、簇結(jié)構(gòu)的穩(wěn)定性和負(fù)載均衡度等. 本文采用MATLAB軟件對ADWCA算法在大規(guī)模集群衛(wèi)星網(wǎng)絡(luò)中的性能進(jìn)行了仿真，并與最小標(biāo)識分簇算法(lowest-ID algorithm,LID)和最大連接度優(yōu)先算法(highest-connectivity degree algorithm,HCC)進(jìn)行了比較. 仿真實(shí)驗(yàn)參數(shù)如表1所示. 為了降低單次實(shí)驗(yàn)的隨機(jī)性干擾，最終結(jié)果取20次仿真結(jié)果的均值.

表1 仿真參數(shù)Tab.1 Simulation parameter

在鏈路容量允許的情況下，簇首節(jié)點(diǎn)數(shù)目少的算法能夠有效提高鏈路的利用率. 但由于星上載荷能力的限制，單個(gè)衛(wèi)星節(jié)點(diǎn)不可能服務(wù)所有k跳內(nèi)鄰居衛(wèi)星節(jié)點(diǎn)，因此需要對簇成員的數(shù)量作出一定限制. 本文仿真中假定簇內(nèi)節(jié)點(diǎn)最大數(shù)量為10個(gè)，即生成的簇結(jié)構(gòu)內(nèi)簇首數(shù)量至少為20個(gè). 圖4反映了3種算法在仿真期間建立的簇結(jié)構(gòu)的簇首數(shù)量，從圖中可以看出，本文ADWCA算法所生成的簇首數(shù)量在整個(gè)仿真期間更少且更穩(wěn)定，明顯優(yōu)于LID和HCC算法.

圖4 簇首數(shù)量對比Fig.4 Comparison of the number of cluster heads

簇結(jié)構(gòu)的穩(wěn)定性采用節(jié)點(diǎn)狀態(tài)變化次數(shù)來度量，即每個(gè)時(shí)間片內(nèi)所有節(jié)點(diǎn)發(fā)生狀態(tài)變化的總次數(shù). 變化次數(shù)越少，說明簇的穩(wěn)定性越高，控制開銷就越低. 圖5反映了仿真期間3種算法在各個(gè)時(shí)間片發(fā)生狀態(tài)變化的總次數(shù). LID和HCC算法發(fā)生狀態(tài)變化的次數(shù)在取多次仿真結(jié)果的均值后是非常接近的，大概在每個(gè)時(shí)間片90次左右. 這是因?yàn)榉抡嬷胁捎玫氖请S機(jī)生成的拓?fù)洌襆ID和HCC算法節(jié)點(diǎn)發(fā)生狀態(tài)改變的條件幾乎一致，另外考慮到簇首節(jié)點(diǎn)的狀態(tài)不輕易發(fā)生變化，仿真結(jié)果是滿足預(yù)期的. 而ADWCA算法的節(jié)點(diǎn)狀態(tài)改變次數(shù)則只有45次左右，下降了一半的數(shù)量，極大地提高了簇結(jié)構(gòu)的穩(wěn)定性.

圖5 節(jié)點(diǎn)狀態(tài)變化次數(shù)對比Fig.5 Comparison of the number of node status changes

簇首的負(fù)載大小取決于其所支持的節(jié)點(diǎn)的多少. 簇結(jié)構(gòu)的維護(hù)和基于分簇的路由均需要消耗簇首一定的資源，因此不希望出現(xiàn)有的簇首過載，有的簇首卻很輕閑的狀況. 本文采用文獻(xiàn)[9]提出的負(fù)載均衡度(load balance factor,LBF)的概念作為量化指標(biāo),具體計(jì)算如公式(5)所示.

(5)

式中：xi為簇首節(jié)點(diǎn)i的成員節(jié)點(diǎn)數(shù)；u為簇首的平均鄰居節(jié)點(diǎn)數(shù)量，u=(N-nc)/nc，N為網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)，nc為簇首節(jié)點(diǎn)的數(shù)量. 該值越大，表示負(fù)載均衡度越好.

圖6反映了整個(gè)仿真期間3種算法負(fù)載均衡度的比較，從圖6中可以看出，LID算法只以節(jié)點(diǎn)ID作為簇首的選舉標(biāo)準(zhǔn)，沒有考慮其他因素，負(fù)載均衡度在整個(gè)仿真期間最低. HCC算法以節(jié)點(diǎn)度數(shù)作為選舉標(biāo)準(zhǔn)，負(fù)載均衡度較LID有所改善. 本文提出的ADWCA算法負(fù)載均衡度較前兩種算法有了非常明顯的提高，這是因?yàn)锳DWCA分簇算法在節(jié)點(diǎn)入簇上做出了改進(jìn)，綜合考慮了節(jié)點(diǎn)距簇首的跳數(shù)、簇首權(quán)重以及簇內(nèi)節(jié)點(diǎn)數(shù)量，當(dāng)簇內(nèi)節(jié)點(diǎn)數(shù)過多時(shí)，其新加入節(jié)點(diǎn)的概率就會減小. 通過這種方式平均各個(gè)簇內(nèi)節(jié)點(diǎn)的數(shù)量，達(dá)到有效的負(fù)載均衡.

圖6 負(fù)載均衡度對比Fig.6 Comparison of the load balance

5 結(jié)束語

大規(guī)模衛(wèi)星集群網(wǎng)絡(luò)相比于傳統(tǒng)衛(wèi)星星座動(dòng)態(tài)性更強(qiáng)，同時(shí)面臨著日益復(fù)雜的任務(wù)需求，采用分簇算法對集群網(wǎng)絡(luò)進(jìn)行分層式管理具有重要的意義. 本文提出了一種自適應(yīng)分布式的分簇算法，由地面終端根據(jù)先驗(yàn)信息進(jìn)行初始化分簇，星上通過實(shí)時(shí)的信息交互完成簇結(jié)構(gòu)的維護(hù)，同時(shí)改進(jìn)了節(jié)點(diǎn)入簇和狀態(tài)改變的條件. 仿真結(jié)果表明，該算法生成的簇結(jié)構(gòu)簇首數(shù)量更少，具有良好的穩(wěn)定性同時(shí)能夠達(dá)到有效的負(fù)載均衡. 但本算法也具有一些不足，例如沒有考慮到衛(wèi)星之間可能存在單向鏈路的情況，需要在下一步研究工作中繼續(xù)完善.