基于時延的LEO 衛(wèi)星網(wǎng)絡(luò)SDN 控制器動態(tài)放置方法

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

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

1 引言

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

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

表1 衛(wèi)星網(wǎng)絡(luò)多控制器放置方案對比分析

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

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

本文提出了一種基于時延的LEO 衛(wèi)星網(wǎng)絡(luò)SDN 控制器動態(tài)放置方法，能夠在滿足應(yīng)急衛(wèi)星組網(wǎng)覆蓋需求的同時降低網(wǎng)絡(luò)時延。首先，以衛(wèi)星對任務(wù)終端的覆蓋為基礎(chǔ)，設(shè)置衛(wèi)星節(jié)點覆蓋冗余度，并設(shè)計基于冗余覆蓋的應(yīng)急衛(wèi)星子網(wǎng)劃分機制，從而保障任務(wù)區(qū)域的有效覆蓋；其次，對網(wǎng)絡(luò)時延進行分析建模，在子網(wǎng)內(nèi)以時延為優(yōu)化目標(biāo)確定控制器放置方案；最后，將控制器放置問題轉(zhuǎn)化為設(shè)備放置問題，利用近似算法對模型進行求解，進一步降低網(wǎng)絡(luò)時延。

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

軟件定義天地一體化信息網(wǎng)絡(luò)基礎(chǔ)架構(gòu)如圖1所示，整個控制平面由地面管理控制中心、GEO 衛(wèi)星群主控制器和LEO 衛(wèi)星層從控制器構(gòu)成。

圖1 軟件定義天地一體化信息網(wǎng)絡(luò)基礎(chǔ)架構(gòu)

2.1 問題分析

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

為了滿足應(yīng)急任務(wù)動態(tài)組網(wǎng)的低網(wǎng)絡(luò)響應(yīng)時延的需求，LEO 衛(wèi)星網(wǎng)絡(luò)的控制放置方案需要考慮的2 個關(guān)鍵問題：1)如何根據(jù)應(yīng)急任務(wù)的覆蓋需求動態(tài)劃分衛(wèi)星子網(wǎng)以滿足衛(wèi)星子網(wǎng)的有效覆蓋；2)如何在衛(wèi)星子網(wǎng)內(nèi)選擇合適的衛(wèi)星節(jié)點作為控制器以降低網(wǎng)絡(luò)響應(yīng)時延。

2.2 研究思路

針對上述問題，本文提出基于時延的LEO 衛(wèi)星網(wǎng)絡(luò)SDN 控制器動態(tài)放置方法，其流程如圖2 所示。

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

圖3 衛(wèi)星對地覆蓋的幾何性質(zhì)

主要步驟如下。

1)基于覆蓋冗余度的衛(wèi)星子網(wǎng)劃分機制

根據(jù)衛(wèi)星對地覆蓋特性確定滿足當(dāng)前覆蓋需求的基礎(chǔ)衛(wèi)星子網(wǎng)S0后，當(dāng)衛(wèi)星節(jié)點動態(tài)變化時，為了滿足衛(wèi)星子網(wǎng)對應(yīng)急區(qū)域的有效覆蓋，選擇衛(wèi)星對終端的有效覆蓋時間窗口，以此來設(shè)計衛(wèi)星節(jié)點的覆蓋冗余值N，根據(jù)衛(wèi)星節(jié)點的覆蓋冗余值，確定需要滿足冗余覆蓋的衛(wèi)星子網(wǎng)Sr，在衛(wèi)星節(jié)點動態(tài)組網(wǎng)中能夠避免因網(wǎng)絡(luò)切換而產(chǎn)生的覆蓋漏洞。

2)建立基于網(wǎng)絡(luò)時延的優(yōu)化模型

在衛(wèi)星子網(wǎng)內(nèi)，基于分布式控制衛(wèi)星網(wǎng)絡(luò)的時延分析，以網(wǎng)絡(luò)時延作為控制器放置方案的目標(biāo)函數(shù)，選擇衛(wèi)星的可用度及星間鏈路的可靠性作為約束條件進行建模分析，能夠在設(shè)計控制器放置方案時優(yōu)化網(wǎng)絡(luò)時延，提高網(wǎng)絡(luò)控制的性能。

3)優(yōu)化模型近似算法求解

將上述控制器放置問題轉(zhuǎn)化為設(shè)備放置問題，設(shè)計基于近似算法的求解方法，優(yōu)化模型最優(yōu)化求解的時間復(fù)雜度，提高控制方案的穩(wěn)定性，從而進一步降低網(wǎng)絡(luò)時延。

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

3.1 衛(wèi)星子網(wǎng)動態(tài)劃分建模

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

3.1.1 覆蓋冗余值N

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

根據(jù)衛(wèi)星對地覆蓋的幾何性質(zhì)，衛(wèi)星沿運行軌道方向在單位時間T 內(nèi)轉(zhuǎn)過的弧度為αs，終端節(jié)點單位時間內(nèi)轉(zhuǎn)過的弧度為βu，結(jié)合弧長計算式，當(dāng)αs=α 時，得到衛(wèi)星對地最大覆蓋時間窗口為

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

1)當(dāng)終端速度為0 時，此時N=1。

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

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

3.1.2 基于覆蓋冗余度的衛(wèi)星子網(wǎng)劃分方法

衛(wèi)星子網(wǎng)的劃分需要滿足網(wǎng)絡(luò)對任務(wù)區(qū)域的有效覆蓋，若僅根據(jù)當(dāng)前衛(wèi)星對地面的基礎(chǔ)覆蓋來確定衛(wèi)星子網(wǎng)，則當(dāng)終端與衛(wèi)星子網(wǎng)邊緣的衛(wèi)星相對速度過大時，衛(wèi)星網(wǎng)絡(luò)不能滿足對終端的覆蓋，這會導(dǎo)致覆蓋漏洞的問題。針對該問題，本節(jié)提出了基于冗余度的衛(wèi)星子網(wǎng)劃分機制，能夠滿足終端對衛(wèi)星下一時刻切換的需求。

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

圖4 基于冗余覆蓋的衛(wèi)星子網(wǎng)劃分

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

衛(wèi)星網(wǎng)絡(luò)中控制器放置的數(shù)量和選取的位置會影響網(wǎng)絡(luò)時延，同時也受存儲容量和星間鏈路的可關(guān)聯(lián)性約束，本節(jié)以網(wǎng)絡(luò)時延作為優(yōu)化目標(biāo)，以衛(wèi)星節(jié)點容量及星間鏈路的關(guān)聯(lián)關(guān)系作為約束條件，對衛(wèi)星網(wǎng)絡(luò)控制器放置問題進行建模分析，主要符號定義如表2 所示。

表2 參數(shù)符號及其定義

3.2.1 網(wǎng)絡(luò)時延分析

基于分布式控制的衛(wèi)星網(wǎng)絡(luò)時延包括網(wǎng)絡(luò)維護時間、數(shù)據(jù)流建立時間、控制同步時間和控制器切換時間，在這里主要考慮傳播時間和傳輸時間對網(wǎng)絡(luò)響應(yīng)時延產(chǎn)生的影響。具體過程如圖5 所示。

1)網(wǎng)絡(luò)維護時間

圖5 中a—c 為網(wǎng)絡(luò)維護過程。首先，控制器根據(jù)鏈路檢測協(xié)議，向其管理的交換機發(fā)送鏈路檢測數(shù)據(jù)分組，交換機向其鄰域節(jié)點一跳轉(zhuǎn)發(fā)數(shù)據(jù)分組，接收到該數(shù)據(jù)分組的交換機通過packet_in 方式將信息上傳到其連接的控制器。網(wǎng)絡(luò)維護過程產(chǎn)生的平均時延代價為

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

圖5 分布式控制系統(tǒng)時延分析

2)數(shù)據(jù)流建立時間

圖5 中d—e 為業(yè)務(wù)流的建立過程，以圖5 中交換機S1為例。每當(dāng)新的業(yè)務(wù)流到達(dá)交換機S1時，由于從S1流表中沒有匹配到相應(yīng)的數(shù)據(jù)流轉(zhuǎn)發(fā)規(guī)則，需要向控制器C2packet_in 業(yè)務(wù)信息，控制器C2再向交換機S1packet_out 并安裝該流的轉(zhuǎn)發(fā)規(guī)則。流建立過程的時延代價為

3)控制同步時間

圖5 中f—g 為控制器集群同步過程。從屬控制器向主控制器Cm發(fā)送本域的網(wǎng)絡(luò)信息，主控制器再向從屬控制器發(fā)送全局網(wǎng)絡(luò)信息?？刂破骷浩骄綍r延代價為

4)控制器切換時間

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

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

3.2.2 控制器放置方案優(yōu)化模型

根據(jù)上述分析可以得到，以最小化網(wǎng)絡(luò)時延確定子網(wǎng)控制器放置方案時可得到優(yōu)化目標(biāo)函數(shù)，即

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

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

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

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

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

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

算法1按需動態(tài)控制器放置近似算法

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

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

計算基礎(chǔ)衛(wèi)星子網(wǎng)S0的邊界衛(wèi)星節(jié)點的N 值；

基于N 擴展S0獲得Sr，進而獲得子網(wǎng)內(nèi)衛(wèi)星節(jié)點集合V；

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

事件1

事件2

如果j ∈ C則xij=1；

返回(x,y)解集

4.2 按需動態(tài)控制器動態(tài)放置近似算法有效性說明

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

引理1目標(biāo)函數(shù)式(13)是規(guī)約設(shè)備放置問題。

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

1)非負(fù)性

cij為交換機的連接代價，pij’為二進制數(shù)，F(xiàn)ij為大于零的數(shù)值，為大于0 的數(shù)值，可得cij第一部分非負(fù)，第二部分有以下2 種情況。

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

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

因此，cij滿足非負(fù)性。

2)對稱性

由于dij=dij，F(xiàn)ij=Fji，，由式(21)可得cij=cji，因此cij具有對稱性。

3)三角不等式

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

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

情況2當(dāng)α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 三角不等關(guān)系

由以上分析可得，目標(biāo)函數(shù)的最優(yōu)化求解問題是規(guī)約設(shè)備放置問題。

證畢。

引理2目標(biāo)函數(shù)式(13)對應(yīng)的設(shè)備放置問題具有近似度為2 的近似算法。

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

其中，當(dāng)k ≥1 時，有

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

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

5 仿真實驗及結(jié)果分析

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

表3 主要實驗參數(shù)設(shè)置

5.1 控制器放置數(shù)量

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

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

圖7 不同子網(wǎng)占比下控制器放置的數(shù)量

5.2 網(wǎng)絡(luò)時延分析

網(wǎng)絡(luò)時延分析實驗主要驗證本文所提ODAA在不同的子網(wǎng)中能夠優(yōu)化網(wǎng)絡(luò)時延，保證交換機與控制器的關(guān)聯(lián)配置，從而保持平均流建立時間。

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

圖8 不同衛(wèi)星子網(wǎng)占比網(wǎng)絡(luò)時延的變化

5.3 算法有效性對比分析

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

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

OptSearch 算法能夠得到最低時延代價的優(yōu)化解，但是隨著網(wǎng)絡(luò)節(jié)點的增加，由于其算法執(zhí)行時間過長，從而導(dǎo)致適用性差，其中OptSearch算法的具體時間復(fù)雜度為O(2nn3)。為了在提高算法求解的精確度的同時降低計算時間復(fù)雜度，在進行控制器選擇時，本文所提算法根據(jù)星間鏈路的特性對解的有效性進行約束，設(shè)計逼近于最優(yōu)解的求解方法，獲得時間復(fù)雜度為O(n2)的啟發(fā)式求解算方法?；谝话銌l(fā)式求解方法的控制器放置求解算法ASPO，其算法的時間復(fù)雜度為O(mn)，雖然此算法能夠降低優(yōu)化算法的時間復(fù)雜度，但是無法保證解的準(zhǔn)確性。相較ASPO 算法，本文所提算法在不明顯增加計算復(fù)雜度的基礎(chǔ)上，獲得了逼近于最優(yōu)解的控制器放置方案，且在優(yōu)化算法計算時間的同時能夠保證解的穩(wěn)定性。

圖9 不同算法對比分析

6 結(jié)束語

本文提出了一種基于時延的LEO 衛(wèi)星網(wǎng)絡(luò)控制器動態(tài)放置方法。該方法能夠根據(jù)本地衛(wèi)星子網(wǎng)的動態(tài)變化靈活地調(diào)整網(wǎng)絡(luò)的大小，避免衛(wèi)星節(jié)點切換不及時而引起的網(wǎng)絡(luò)覆蓋漏洞問題，并在子網(wǎng)內(nèi)以網(wǎng)絡(luò)響應(yīng)時延作為優(yōu)化目標(biāo)函數(shù)，能夠優(yōu)化控制衛(wèi)星節(jié)點與交換衛(wèi)星節(jié)點之間的關(guān)聯(lián)關(guān)系，從而降低網(wǎng)絡(luò)的平均流建立時間及響應(yīng)時間。針對優(yōu)化目標(biāo)函數(shù)有效求解問題，將控制器放置問題轉(zhuǎn)換為設(shè)備放置問題，設(shè)計近似算法在降低計算時間復(fù)雜度的同時獲得更加逼近最優(yōu)的放置方案，從而進一步提高所提方案的穩(wěn)定性。