基于時延的LEO 衛星網絡SDN 控制器動態放置方法

韓珍珍，趙國鋒，徐川，周文濤，周洋洋

（重慶郵電大學通信與信息工程學院，重慶 400065）

1 引言

衛星網絡能夠覆蓋海洋、高山、沙漠等地面網絡不能覆蓋的區域，在重大自然災害預防及應急救援工作中，能夠根據覆蓋需求動態組網，從而支撐應急服務。天地一體化信息網絡融合了衛星網絡與地面網絡的特點，能夠支撐多樣化的空間網絡需求，這也成為未來網絡發展的新趨勢[1-3]。SDN（software defined network）的引入進一步提高了天地一體化信息網絡的可擴展性及靈活性[4]。為了滿足應急任務低時延、高可靠的服務需求，需要部署多個SDN 控制器來實現衛星網絡的分布式控制，因此，控制器放置的數量和位置是設計控制器放置方案，提高衛星網絡靈活性需要考慮的關鍵問題。

針對上述問題，衛星網絡多控制器部署方案被相繼提出，基于控制器部署的空間地理位置可將其劃分為單層部署方案和多層部署方案兩類，具體特點如表1 所示。單層部署方案是指在單衛星軌道層或者地面部署控制器[6-9]，如基于地面站數目穩定且具有強大的計算能力和存儲能力，將控制器部署在地面中心站點上，能夠提高衛星網絡接入管理的靈活性[6]；基于GEO（geostationary earth orbit）衛星節點覆蓋范圍廣、數目穩定且對地靜止的特征，將GEO 衛星群作為控制器增強網絡的可擴展性和靈活性[7]；基于LEO（low earth orbit）層衛星低時延的特性，在低軌星座中選擇部分LEO 衛星節點作為控制器，以此來構建分布式控制架構，從而提高網絡控制的靈活性，且文獻[8]將LEO 軌道衛星節點交替設為控制節點和交換機來實現網絡控制的內嵌；文獻[9]基于地面用戶流量動態需求模型設計LEO 層動態控制器放置算法，并將控制器放置模型轉換為整型線性規劃模型，求解最優控制器配置方案，優化平均流建立時間。然而，受衛星節點軌道位置特性的影響，上述單層控制器部署方法無法綜合利用各個軌道層面的衛星的特性，整個網絡控制的靈活性受限，不能在兼顧衛星網絡廣覆蓋的同時滿足低時延的需求。

表1 衛星網絡多控制器放置方案對比分析

此外，研究者提出在多個衛星軌道層面和地面上設計主從控制模式的多層部署方案[10-13]，充分利用各層衛星節點的特點，提高網絡的可擴展性。例如，Li 等[10]提出在地面和GEO 層部署控制器構成網絡的控制平面；Xu 等[11]提出三層控制架構設計方案，控制平面由作為超級控制器的地面站、作為區域控制器的GEO 衛星群及作為從控制器的部分LEO 衛星構成，并在文獻[12]提出基于軌道平面劃分的從屬控制器動態選取方法。類似地，Wu 等[13]提出由GEO、MEO（medium earth orbit）和LEO不同軌道衛星節點控制器構成的多層控制方案，通過構建多目標優化模型確定最優的控制器放置方法。

然而，基于衛星星座在整個LEO 層放置控制器的方案雖然能夠充分利用LEO 層低時延的特點，但需要選擇大量的衛星節點作為控制器以滿足控制器對交換機的關聯覆蓋。當節點數目增加和動態性增強時，控制節點需要進行同步以維護全局網絡視圖。此時，節點間大量的信令交互會導致網絡時延增加，仍然無法很好地滿足應急任務動態組網的低時延需求。

本文提出了一種基于時延的LEO 衛星網絡SDN 控制器動態放置方法，能夠在滿足應急衛星組網覆蓋需求的同時降低網絡時延。首先，以衛星對任務終端的覆蓋為基礎，設置衛星節點覆蓋冗余度，并設計基于冗余覆蓋的應急衛星子網劃分機制，從而保障任務區域的有效覆蓋；其次，對網絡時延進行分析建模，在子網內以時延為優化目標確定控制器放置方案；最后，將控制器放置問題轉化為設備放置問題，利用近似算法對模型進行求解，進一步降低網絡時延。

2 控制器放置問題分析及思路

軟件定義天地一體化信息網絡基礎架構如圖1所示，整個控制平面由地面管理控制中心、GEO 衛星群主控制器和LEO 衛星層從控制器構成。

圖1 軟件定義天地一體化信息網絡基礎架構

2.1 問題分析

面對需要快速組網的應急通信場景，如抗震救災等，系統能夠根據應急任務需求構建應急衛星子網，從控制器能夠及時根據本地衛星子網狀態變化進行動態調整，提高網絡控制的靈活性，并將本地衛星子網內的控制消息上傳給主控制器，由主控制器完成全局網絡視圖的動態更新，使整個星座系統呈現為邏輯上集中、地理上分散的分布式控制架構。然而，受地理及社會因素的影響，GEO 衛星數量及位置相對穩定，選為主控制器可增加網絡的穩定性。多層網絡SDN 控制器部署方案的靈活性主要取決于如何選擇合適的LEO 衛星作為從控制器，以保證網絡有效覆蓋和網絡響應時延。

為了滿足應急任務動態組網的低網絡響應時延的需求，LEO 衛星網絡的控制放置方案需要考慮的2 個關鍵問題：1)如何根據應急任務的覆蓋需求動態劃分衛星子網以滿足衛星子網的有效覆蓋；2)如何在衛星子網內選擇合適的衛星節點作為控制器以降低網絡響應時延。

2.2 研究思路

針對上述問題，本文提出基于時延的LEO 衛星網絡SDN 控制器動態放置方法，其流程如圖2 所示。

圖2 基于時延的SDN 控制器放置方法流程

圖3 衛星對地覆蓋的幾何性質

主要步驟如下。

1)基于覆蓋冗余度的衛星子網劃分機制

根據衛星對地覆蓋特性確定滿足當前覆蓋需求的基礎衛星子網S0后，當衛星節點動態變化時，為了滿足衛星子網對應急區域的有效覆蓋，選擇衛星對終端的有效覆蓋時間窗口，以此來設計衛星節點的覆蓋冗余值N，根據衛星節點的覆蓋冗余值，確定需要滿足冗余覆蓋的衛星子網Sr，在衛星節點動態組網中能夠避免因網絡切換而產生的覆蓋漏洞。

2)建立基于網絡時延的優化模型

在衛星子網內，基于分布式控制衛星網絡的時延分析，以網絡時延作為控制器放置方案的目標函數，選擇衛星的可用度及星間鏈路的可靠性作為約束條件進行建模分析，能夠在設計控制器放置方案時優化網絡時延，提高網絡控制的性能。

3)優化模型近似算法求解

將上述控制器放置問題轉化為設備放置問題，設計基于近似算法的求解方法，優化模型最優化求解的時間復雜度，提高控制方案的穩定性，從而進一步降低網絡時延。

3 控制器放置問題分析模型

3.1 衛星子網動態劃分建模

為了避免因終端速度移動過快衛星切換不及時而導致的覆蓋漏洞問題，本節提出基于覆蓋冗余度的動態子網劃分機制，其中覆蓋冗余值由衛星與終端的相對位置和相對速度確定；基于該冗余值來擴展衛星子網，以此滿足衛星網絡的冗余覆蓋。

3.1.1 覆蓋冗余值N

為了保障衛星對終端的有效覆蓋，定義覆蓋冗余值N表示在基礎的衛星對地最大時間窗口內終端需要切換的衛星數目。在建模過程中，假設衛星軌道和地球均為圓形，其中衛星對地覆蓋的幾何性質如圖3 所示，衛星對地高度為H，運行速度為vs，地球半徑為Re，衛星對地球的切線確定了衛星的最大覆蓋范圍[14-15]，此時的地心角一般設為α，終端是衛星對地覆蓋范圍內高度為h、速度為vu的節點，所對應的最大地心角為β。

根據衛星對地覆蓋的幾何性質，衛星沿運行軌道方向在單位時間T 內轉過的弧度為αs，終端節點單位時間內轉過的弧度為βu，結合弧長計算式，當αs=α 時，得到衛星對地最大覆蓋時間窗口為

隨著衛星與終端的相對運動，當衛星與終端相對角度差值超過2α 時，終端將超出衛星的覆蓋范圍，當αs-βu=2α 時，衛星對終端覆蓋的時間窗口值Tmax為

1)當終端速度為0 時，此時N=1。

2)當終端與衛星相對運動方向相同時，N 值在0～1 之間，此時令N=1。

3)當終端與衛星相對運動方向相反時，N 值在1～2 之間，此時令N=2。

3.1.2 基于覆蓋冗余度的衛星子網劃分方法

衛星子網的劃分需要滿足網絡對任務區域的有效覆蓋，若僅根據當前衛星對地面的基礎覆蓋來確定衛星子網，則當終端與衛星子網邊緣的衛星相對速度過大時，衛星網絡不能滿足對終端的覆蓋，這會導致覆蓋漏洞的問題。針對該問題，本節提出了基于冗余度的衛星子網劃分機制，能夠滿足終端對衛星下一時刻切換的需求。

首先，根據任務終端的覆蓋需求及衛星對地覆蓋范圍，確定一個基礎的衛星子網S0；然后，計算子網邊界衛星節點關聯終端的N 值，取最大的N 值作為該衛星節點的擴展冗余度，圖4 中以N=1 為例進行說明；最后，選取LEO 衛星子網S0的邊界衛星節點（如圖4 中節點A 和節點B）間隔N-1 條軌道（如圖4 中Oaa和Oba），及垂直于與邊界衛星節點同軌道且間隔N-1 顆衛星的衛星節點到地心距離為半徑且以地心為圓心的弧線（如圖4 中Cas和Cbs），這些邊界衛星節點的外圍曲線圍成區域所包含的衛星節點構成基于冗余度擴展后的衛星子網Sr，滿足可能存在的終端切換的要求，從而滿足衛星子網覆蓋需求。

圖4 基于冗余覆蓋的衛星子網劃分

3.2 基于時延的控制器放置建模

衛星網絡中控制器放置的數量和選取的位置會影響網絡時延，同時也受存儲容量和星間鏈路的可關聯性約束，本節以網絡時延作為優化目標，以衛星節點容量及星間鏈路的關聯關系作為約束條件，對衛星網絡控制器放置問題進行建模分析，主要符號定義如表2 所示。

表2 參數符號及其定義

3.2.1 網絡時延分析

基于分布式控制的衛星網絡時延包括網絡維護時間、數據流建立時間、控制同步時間和控制器切換時間，在這里主要考慮傳播時間和傳輸時間對網絡響應時延產生的影響。具體過程如圖5 所示。

1)網絡維護時間

圖5 中a—c 為網絡維護過程。首先，控制器根據鏈路檢測協議，向其管理的交換機發送鏈路檢測數據分組，交換機向其鄰域節點一跳轉發數據分組，接收到該數據分組的交換機通過packet_in 方式將信息上傳到其連接的控制器。網絡維護過程產生的平均時延代價為

其中，等號右邊第一項表示控制器間進行信息交互產生的時間，第二項表示交換機進行信息交互產生的時間，每項都包括信息的傳播時間和傳輸處理時間，eij表示兩節點之間的邊。

圖5 分布式控制系統時延分析

2)數據流建立時間

圖5 中d—e 為業務流的建立過程，以圖5 中交換機S1為例。每當新的業務流到達交換機S1時，由于從S1流表中沒有匹配到相應的數據流轉發規則，需要向控制器C2packet_in 業務信息，控制器C2再向交換機S1packet_out 并安裝該流的轉發規則。流建立過程的時延代價為

3)控制同步時間

圖5 中f—g 為控制器集群同步過程。從屬控制器向主控制器Cm發送本域的網絡信息，主控制器再向從屬控制器發送全局網絡信息。控制器集群平均同步時延代價為

4)控制器切換時間

圖5 中h—j 為交換機S2從控制器C1遷移到C2的過程。在切換過程中，控制器集群之間首先需要進行網絡信息同步，然后原控制器向遷移的交換機發送切換信息，該交換機向新關聯的控制器發送連接請求，目的控制器收到請求后回復確認信息。交換機遷移引起的平均時延代價為

其中，等號右邊第一項表示交換機與原控制器斷開時間，第二項表示交換機與新控制器連接時間。

3.2.2 控制器放置方案優化模型

根據上述分析可以得到，以最小化網絡時延確定子網控制器放置方案時可得到優化目標函數，即

其中，目標函數式(8)表示分布式衛星子網的網絡響應時延；約束式(9)表示開啟的控制器數目小于或等于網絡節點數目；約束式(10)表示每個交換機僅由一個控制器控制；約束式(11)可以保證控制器能夠承載關聯交換機的請求，其中Us表示衛星節點的最大容量；約束式(12)能夠限制控制鏈路關聯關系，其中pij是二進制數，i 與j 連接為1，否則為0，當i=j 時，該衛星節點是控制器。

4 基于近似算法的控制器放置模型求解

4.1 控制器放置問題近似求解算法

針對上述基于網絡時延的控制器放置模型，最優解的求解是NP-hard 問題[16-17]，當網絡節點較多時，算法求解復雜，難以在有效的時間內獲得最優解。針對該類問題，啟發式算法可以對模型進行快速求解，但是無法保證解的準確性和穩定性。需要近似算法對該問題進行有效求解，且對解的有效性進行約束[18]。在提出具體求解算法之前，先將目標函數轉換為有容量限制的設施選址問題[19]，具體如式(13)～式(17)所示。

其中，目標函數式(13)表示通過時延代價的優化確定控制器放置方案，其中xij表示控制器與交換機的匹配關系，yi表示節點i 為控制器；約束式(14)表示每個交換機與一個控制器相關聯；約束式(15)表示與控制器衛星關聯的交換機個數小于衛星星間鏈路的數量，其中ui表示星間鏈路的條數；約束式(16)表示只要有交換機關聯，那么控制器必須處于開啟狀態；約束式(17)表示xij和yi是二進制數。其中，有

針對上述設備放置問題的求解，本節提出按需動態控制器動態放置近似算法（ODAA,on demand dynamic approximate algorithm）。根據覆蓋需求確定衛星子網S0，根據邊緣衛星節點的擴展冗余度N 確定衛星子網Sr。在子網Sr內確定控制器放置方案，主要設計思想是根據目標函數式(13)建立控制器與交換機之間的關聯，隨著控制器數量的增加，重新判斷交換機和控制器的關聯關系，直至輸出最終結果。事件1 表示出現系統最小時延匹配時，將交換機j 關聯到控制器i 上，事件2 表示若增開新控制器存在更低的網絡時延，則開啟新控制器，完成交換機與控制器的關聯，降低系統時延，具體步驟如算法1 所示。

算法1按需動態控制器放置近似算法

輸入S0，{ fi,cij,ui}，{dij}

輸出可行整數解集(x,y)

計算基礎衛星子網S0的邊界衛星節點的N 值；

基于N 擴展S0獲得Sr，進而獲得子網內衛星節點集合V；

當U≠?時，針對j∈C 則αj=t，按照任意順序執行以下兩類事件；//t是時間變量；

事件1

事件2

如果j ∈ C則xij=1；

返回(x,y)解集

4.2 按需動態控制器動態放置近似算法有效性說明

本節通過引理1 證明目標函數式(13)是規約設備放置問題，因而具有可求解的近似算法；進而用引理2 證明本文所提的按需動態控制器放置算法是近似算法，該算法能夠在降低計算復雜度的同時保證解的有效性。

引理1目標函數式(13)是規約設備放置問題。

證明在目標函數式(13)中，fi表示開啟控制器所產生的時間代價，主要包括控制器與控制器之間的節點同步時間；cij表示交換機關聯的時間代價，主要包括兩部分，分別為交換機與控制器之間的時間及交換機與交換機之間的時間。根據有容量限制設備放置問題的基本屬性可得，cij需要滿足非負性、對稱性及三角不等式[19]。

1)非負性

cij為交換機的連接代價，pij’為二進制數，Fij為大于零的數值，為大于0 的數值，可得cij第一部分非負，第二部分有以下2 種情況。

情況1當pij’=0 時，(1-2 pij’)Ih值非負，此時，cij第二部分非負。

情況2當pij’=1 時，當前i 與j 節點的配置關系不發生改變，Ih=0，(1-2 pij’)Ih=0，從而可得cij第二部分非負。

因此，cij滿足非負性。

2)對稱性

由于dij=dij，Fij=Fji，，由式(21)可得cij=cji，因此cij具有對稱性。

3)三角不等式

三角不等關系如圖6 所示。從以下2 種情況證明對于?1 ≤j ＜i ≤k,必然滿足性質αi≤rj,i+di+dj。

情況1當αj=αi時，顯然滿足αi≤rj,i+di+dj。

情況2當αj＜ αi時，因為j 在t 時刻沒有連接到另一控制器 i(j)，所以t=αi-ε≤ci(j)j，αi=t-ε≤ci(j)i≤ci(j)j+di+dj=rj,i+di+dj。

圖6 三角不等關系

由以上分析可得，目標函數的最優化求解問題是規約設備放置問題。

證畢。

引理2目標函數式(13)對應的設備放置問題具有近似度為2 的近似算法。

證明根據文獻[20]將上述控制器放置問題歸納成線性代價的設備選址問題（LCFLP,linear cost facility location problem），在軟容量設施選址問題（SCFLP,soft capacitated facility location problem）中，控制器設施i 的開啟代價為

其中，當k ≥1 時，有

所以SCFLP 是相應LCFLP(a,b,c)的(2,1)-規約。則該問題可以等效轉換為相應的無容量限制設施選址問題UFLP(b,c+a)（un-capacitated facility location problem），且滿足

結合文獻[19]中的推論2 可得，UFLP(b,c+a)運行上述算法可以得到LCFLP(a,b,c)(1,2)-近似算法。再根據文獻[20]中定理3 得到，上述SCFLP 求解算法ODAA 是近似度為2 的近似算法。

5 仿真實驗及結果分析

針對衛星網絡的特點，本文主要利用STK（satellite tool kit）對LEO 低軌星座系統的衛星節點及星間鏈路進行建模，并聯合Matlab 完成控制器放置方法的仿真驗證。在Iridium 星座系統中，網絡任務由地面移動終端產生，任務流的大小及基本分布情況主要參考文獻[13]，在GMT 2019-04-10 8:00 am 到2019-04-11 7:00 am 時段內，通過需要放置的控制器的數量、網絡響應時間及平均流建立時間驗證本文所提方案的可行性及有效性，并根據文獻[21-22]設置如表3 所示的仿真實驗參數。

表3 主要實驗參數設置

5.1 控制器放置數量

控制器放置數量實驗主要驗證本文所提子網劃分機制能夠有效減少控制器放置的數量。其中衛星子網占比γ 指滿足地面網絡冗余覆蓋需求的總衛星子網Sr與整個星座對地覆蓋的比值。

不同子網占比下控制器放置的數量如圖7 所示。由圖7 可得，隨著衛星子網占比的不斷提高，衛星子網覆蓋區域不斷擴大，需要放置的控制器數量隨之增加。當γ=0.1 時，衛星節點數量較少，子網中控制器衛星節點與交換機的配比約為1:5，即一個控制節點衛星關聯5 個交換機的衛星。當網絡達到全覆蓋時，需要放置的控制器的數量平均是12 顆，放置控制器的衛星和作為交換機的衛星的配比略大于1:4，基本滿足衛星網絡星間鏈路的特點。由此可見，為了滿足控制器對交換機的覆蓋需求，衛星子網越大，需要放置的控制器數量就越多。因此基于覆蓋需求的子網劃分機制相較基于全網的控制器放置方案能夠根據網絡的覆蓋需求放置控制器，在滿足網絡覆蓋需求的同時能夠優化需要放置的控制器的數量。

圖7 不同子網占比下控制器放置的數量

5.2 網絡時延分析

網絡時延分析實驗主要驗證本文所提ODAA在不同的子網中能夠優化網絡時延，保證交換機與控制器的關聯配置，從而保持平均流建立時間。

當衛星子網占比不同時，采用ODAA 放置控制器平均網絡時延及平均流建立時間變化趨勢如圖8所示。由圖8 可得，隨著子網占比的增加，網絡時延近似成比例增加，但平均流建立時間維持在20～25 ms。因為隨著衛星子網范圍的擴大，需要放置更多的控制器來滿足對交換機的關聯，由式(8)可得網絡時延也隨之增加，受星間鏈路特性的約束，一個放置控制器的衛星節點最多與4 個作為交換機的衛星直接關聯，交換機與控制器平均間隔一跳的距離；由式(5)可得平均流建立時間相對穩定。隨著時間的推移，控制器放置方案能夠動態更新，網絡時延和流建立時間能夠保持相對穩定。因此，本文所提基于子網劃分機制的控制器放置算法能夠優化網絡時延和平均流建立時間，提高網絡的靈活性。

圖8 不同衛星子網占比網絡時延的變化

5.3 算法有效性對比分析

為了驗證所提近似算法的有效性，基于整個網絡系統，將所提算法ODAA 與文獻[13]中動態控制器放置求解加速粒子群算法ASPO（accelerated particle swarm optimization）及最優搜索算法OptSearch（optimal search）進行對比分析。

如圖9 所示，本文所提算法ODAA 在控制器放置數量、平均網絡響應時延及平均流建立時間上相較ASPO 算法所得結果更趨向于最優搜索算法，且與ASPO 算法相比ODAA 能夠降低約10%的平均網絡時延及23%的平均流建立時間，有效改善網絡控制的時延性能。

OptSearch 算法能夠得到最低時延代價的優化解，但是隨著網絡節點的增加，由于其算法執行時間過長，從而導致適用性差，其中OptSearch算法的具體時間復雜度為O(2nn3)。為了在提高算法求解的精確度的同時降低計算時間復雜度，在進行控制器選擇時，本文所提算法根據星間鏈路的特性對解的有效性進行約束，設計逼近于最優解的求解方法，獲得時間復雜度為O(n2)的啟發式求解算方法。基于一般啟發式求解方法的控制器放置求解算法ASPO，其算法的時間復雜度為O(mn)，雖然此算法能夠降低優化算法的時間復雜度，但是無法保證解的準確性。相較ASPO 算法，本文所提算法在不明顯增加計算復雜度的基礎上，獲得了逼近于最優解的控制器放置方案，且在優化算法計算時間的同時能夠保證解的穩定性。

圖9 不同算法對比分析

6 結束語

本文提出了一種基于時延的LEO 衛星網絡控制器動態放置方法。該方法能夠根據本地衛星子網的動態變化靈活地調整網絡的大小，避免衛星節點切換不及時而引起的網絡覆蓋漏洞問題，并在子網內以網絡響應時延作為優化目標函數，能夠優化控制衛星節點與交換衛星節點之間的關聯關系，從而降低網絡的平均流建立時間及響應時間。針對優化目標函數有效求解問題，將控制器放置問題轉換為設備放置問題，設計近似算法在降低計算時間復雜度的同時獲得更加逼近最優的放置方案，從而進一步提高所提方案的穩定性。