陳金濤， 梁 俊， 劉 波， 謝寶華

(空軍工程大學(xué)信息與導(dǎo)航學(xué)院， 西安， 710077)

衛(wèi)星通信[1]是實(shí)現(xiàn)真正全球化通信的關(guān)鍵支撐，是未來(lái)通信網(wǎng)絡(luò)體系架構(gòu)中必不可少的互連部分。包括Sat5G、ITU、3GPP等標(biāo)準(zhǔn)化組織已經(jīng)考慮將衛(wèi)星通信融合在5G環(huán)境中[2]。從而可以有效解決農(nóng)村和偏遠(yuǎn)地區(qū)的網(wǎng)絡(luò)接入、地面基礎(chǔ)設(shè)施損毀下網(wǎng)絡(luò)的臨時(shí)搭建[3]。融合衛(wèi)星的5G網(wǎng)絡(luò)將意味著更高的網(wǎng)絡(luò)可用性和可靠性，特別是，具有高吞吐量的衛(wèi)星鏈路可有效地卸載地面流量，以減輕網(wǎng)絡(luò)中的擁塞同時(shí)提高地面網(wǎng)絡(luò)的可伸縮性和安全性[4]。

總之，衛(wèi)星與地面5G網(wǎng)絡(luò)的融合將充分發(fā)揮各自優(yōu)勢(shì)，并提供一種新的網(wǎng)絡(luò)架構(gòu)以滿足未來(lái)無(wú)線網(wǎng)絡(luò)中的各種應(yīng)用。但是，由于集成網(wǎng)絡(luò)固有的異構(gòu)性，因此要管理具有大量物理設(shè)備的網(wǎng)絡(luò)同時(shí)實(shí)現(xiàn)網(wǎng)絡(luò)性能最佳是目前面臨的重大挑戰(zhàn)。正如軟件定義網(wǎng)絡(luò)SDN[5]所帶來(lái)的優(yōu)勢(shì)，SDN可以通過(guò)解耦控制平面和數(shù)據(jù)平面，利用全局視角調(diào)配網(wǎng)絡(luò)資源、制定有效的資源分配策略[6]，從而高效地管理整個(gè)集成網(wǎng)絡(luò)。此外，應(yīng)用SDN可以簡(jiǎn)化硬件操作，同時(shí)可以大大提高架構(gòu)的靈活性，系統(tǒng)升級(jí)成本也將降低。

在這種基于SDN的集成網(wǎng)絡(luò)中，控制平面起著承上啟下的核心作用，控制器位置的部署將影響集成網(wǎng)絡(luò)對(duì)網(wǎng)絡(luò)事件的響應(yīng)[7]，不同于傳統(tǒng)地面網(wǎng)絡(luò)，從地面節(jié)點(diǎn)到衛(wèi)星的大多數(shù)數(shù)據(jù)流量都必須通過(guò)衛(wèi)星網(wǎng)關(guān)，因此，本文所提的5G-衛(wèi)星集成網(wǎng)絡(luò)體系架構(gòu)中的主要挑戰(zhàn)之一是衛(wèi)星網(wǎng)關(guān)和控制器的聯(lián)合部署問(wèn)題，這是一個(gè)多目標(biāo)放置問(wèn)題(multi-target deployment)，顯著區(qū)別于單一控制器或網(wǎng)關(guān)部署問(wèn)題。文獻(xiàn)[8]首次證明了該問(wèn)題是一個(gè)NP-hard新問(wèn)題，并提出了一種基于模擬退火和聚類的混合算法，并與枚舉算法相比，該算法能夠以較短的運(yùn)行時(shí)間獲得較優(yōu)的解決方案。文獻(xiàn)[9]則提出了雙重模擬退火算法(SASA)和基于遺傳算法(GAJ)的2種聯(lián)合部署方法，其中SASA在運(yùn)行時(shí)間上折中考慮，GAJ在運(yùn)行時(shí)間和解的質(zhì)量上均有提高。本文提出了一種基于模擬退火與粒子群的混合算法(SA-PSO)，以進(jìn)一步降低算法復(fù)雜度同時(shí)實(shí)現(xiàn)更高的可靠性。

1 控制器與網(wǎng)關(guān)聯(lián)合部署問(wèn)題建模

1.1 模型建立

在本文中，考慮如圖1所示的5G-衛(wèi)星集成網(wǎng)絡(luò)體系結(jié)構(gòu)。該體系結(jié)構(gòu)由兩部分組成，即衛(wèi)星網(wǎng)絡(luò)和地面網(wǎng)絡(luò)。衛(wèi)星網(wǎng)絡(luò)主要由實(shí)現(xiàn)全球無(wú)縫覆蓋的對(duì)地靜止軌道(GEO)衛(wèi)星和地面衛(wèi)星網(wǎng)關(guān)組成，衛(wèi)星間通過(guò)星間鏈路相互通信。地面網(wǎng)絡(luò)主要由地面5G通信系統(tǒng)組成，包括gNB(gNodeB，5G NodeB)、5G核心網(wǎng)絡(luò)、SDN交換機(jī)組成。用戶終端設(shè)備產(chǎn)生的流量可以通過(guò)gNB(即gNodeB，5G NodeB)和RN連接到5G網(wǎng)絡(luò)。交換機(jī)和衛(wèi)星網(wǎng)關(guān)之間主要通過(guò)光纖建立連接，地面網(wǎng)絡(luò)主要通過(guò)衛(wèi)星網(wǎng)關(guān)與衛(wèi)星進(jìn)行通信，SDN控制器部署在地面網(wǎng)絡(luò)的物理節(jié)點(diǎn)上，為集成網(wǎng)絡(luò)提供集中控制和管理功能，為了簡(jiǎn)化分析，在該網(wǎng)絡(luò)模型中，不考慮衛(wèi)星網(wǎng)絡(luò)中衛(wèi)星間鏈路(ISL)的動(dòng)態(tài)性。

圖1 基于SDN的5G-衛(wèi)星集成網(wǎng)絡(luò)架構(gòu)示意圖

1.2 問(wèn)題描述

基于SDN的5G-衛(wèi)星集成網(wǎng)絡(luò)可以用無(wú)向圖G=(V,E)表示，其中，V=Vg∪Vs，Vg是地面交換機(jī)、衛(wèi)星網(wǎng)關(guān)等物理節(jié)點(diǎn)集，Vs是集成網(wǎng)絡(luò)中衛(wèi)星節(jié)點(diǎn)的集合，E是各類節(jié)點(diǎn)之間的物理鏈路集合，其鏈路的權(quán)重表示傳播延遲。

在基于SDN的5G-衛(wèi)星集成網(wǎng)絡(luò)架構(gòu)中，衛(wèi)星鏈路可有效地卸載地面流量[10]，因此，首先應(yīng)考慮的是地面交換機(jī)與衛(wèi)星的流量傳輸過(guò)程。在該過(guò)程中地面交換機(jī)與衛(wèi)星之間的時(shí)延是影響集成網(wǎng)絡(luò)性能的關(guān)鍵因素。因此，每個(gè)地面交換機(jī)都應(yīng)在最短的時(shí)間內(nèi)與衛(wèi)星通信。而時(shí)延主要以傳播時(shí)延為主，傳播延遲取決于交換機(jī)和衛(wèi)星之間的距離，由于對(duì)地靜止軌道(GEO)衛(wèi)星到地面的距離是固定的(35 786 km)，因此交換機(jī)與衛(wèi)星網(wǎng)關(guān)之間的延時(shí)特別重要。

(1)

式中：Lws為網(wǎng)關(guān)與衛(wèi)星通信傳播時(shí)延，為固定值。此外，通信的可靠性是集成網(wǎng)絡(luò)性能的必要保證，集成網(wǎng)絡(luò)中路徑類型主要包括地面通信和星地通信。在這里，令Pu，Pe，Pesw分別表示地面交換機(jī)節(jié)點(diǎn)u，地面鏈路e和衛(wèi)星鏈路esw的故障概率。因此從交換機(jī)u到控制器節(jié)點(diǎn)c的路徑的可靠性計(jì)算如下[8]：

(2)

式中：Vu→cu表示地面通信中從交換機(jī)u到控制器c的完整路徑上除該交換機(jī)節(jié)點(diǎn)的其他節(jié)點(diǎn)集合；Eu→c表示地面通信中從交換機(jī)u到控制器c的完整路徑上的鏈路集合。同理，則從衛(wèi)星節(jié)點(diǎn)s經(jīng)過(guò)衛(wèi)星網(wǎng)關(guān)w到控制器c的路徑可靠性計(jì)算如下：

(3)

式中：Vs→cs表示衛(wèi)星節(jié)點(diǎn)s通過(guò)衛(wèi)星網(wǎng)關(guān)w到達(dá)控制器c的完整鏈路上除衛(wèi)星節(jié)點(diǎn)外的其他節(jié)點(diǎn)集合；Es→c表示衛(wèi)星節(jié)點(diǎn)s通過(guò)衛(wèi)星網(wǎng)關(guān)w到達(dá)控制器c的完整鏈路上的鏈路集合。因此基于SDN的5G-衛(wèi)星集成網(wǎng)絡(luò)的平均可靠性可定義為：

(4)

1.3 控制器與網(wǎng)關(guān)聯(lián)合部署問(wèn)題

根據(jù)以上分析，集成網(wǎng)絡(luò)中控制器與網(wǎng)關(guān)的聯(lián)合部署問(wèn)題可以定義如下：給定集成網(wǎng)絡(luò)中需部署的地面交換機(jī)節(jié)點(diǎn)Vg，對(duì)地靜止軌道(GEO)衛(wèi)星節(jié)點(diǎn)Vs，k個(gè)衛(wèi)星網(wǎng)關(guān)以及m個(gè)控制器，目的是確定最佳控制器位置C={c1,c2,…,cm}?Vg與最佳衛(wèi)星網(wǎng)關(guān)位置W={g1,g2,…,gk}?Vg在滿足時(shí)延約束限制下，最大化基于SDN的5G-衛(wèi)星集成網(wǎng)絡(luò)中的平均可靠性，即：

(5)

(6)

式中：c∈C，w∈W，n和k分別表示Vg中的節(jié)點(diǎn)和W中的衛(wèi)星網(wǎng)關(guān)數(shù)；Lmax是最大等待時(shí)間約束，即地面網(wǎng)絡(luò)中可以接受的最大平均等待時(shí)間。

2 最大化可靠性部署算法

2.1 基于枚舉算法的最大化可靠性部署方法

為實(shí)現(xiàn)5G-衛(wèi)星集成網(wǎng)絡(luò)中控制器和衛(wèi)星網(wǎng)關(guān)聯(lián)合部署問(wèn)題，最直接的方法就是枚舉出所有部署的可能性，計(jì)算其目標(biāo)函數(shù)的值，并從中選出滿足時(shí)延約束且具有最大可靠性的放置方案。該方案簡(jiǎn)單直接，但求解速度極慢[11]，因此，在大規(guī)模網(wǎng)絡(luò)中枚舉算法(optimal enumeration algorithm，OEA)并不適用甚至無(wú)法求解。

2.2 基于模擬退火和粒子群的混合算法(SABPSO)

粒子群優(yōu)化算法[12]是一種全局優(yōu)化的智能算法，其尋優(yōu)是依靠粒子間的協(xié)作和共享，并記錄自身找到的最佳歷史位置以及種群所找到的最佳歷史位置，在優(yōu)化過(guò)程中目的性較強(qiáng)，粒子群算法收斂速度快，且易與其他優(yōu)化算法相結(jié)合，克服易陷入局部最優(yōu)的缺點(diǎn)。所以本文選用粒子群算法結(jié)合模擬退火算法算法對(duì)衛(wèi)星網(wǎng)關(guān)與控制器組合優(yōu)化問(wèn)題進(jìn)行求解。

定義有效的粒子編碼形式是SABPSO混合算法應(yīng)用的關(guān)鍵步驟。每一個(gè)粒子都應(yīng)對(duì)應(yīng)一種衛(wèi)星網(wǎng)關(guān)和控制器部署的解決方案。因此種群中粒子的長(zhǎng)度為k+m。其中k表示衛(wèi)星網(wǎng)關(guān)部署位置向量長(zhǎng)度，即W={g1,g2,…,gk}?Vg，m表示控制器部署位置向量長(zhǎng)度，即C={c1,c2,…,cm}?Vg。粒子的每一維值都在[1,n]的范圍內(nèi)，則每個(gè)粒子可以表示U=[W,C]。以n=12、k=2、m=3為例，即集成網(wǎng)絡(luò)中共有12個(gè)可部署網(wǎng)絡(luò)設(shè)備的節(jié)點(diǎn)，目標(biāo)是在12個(gè)節(jié)點(diǎn)的任何位置部署2個(gè)衛(wèi)星網(wǎng)關(guān)和3個(gè)控制器均實(shí)現(xiàn)在延時(shí)約束下的可靠性最大化。粒子編碼映射如圖2所示。每個(gè)粒子中的數(shù)代表衛(wèi)星網(wǎng)關(guān)和控制器的位置編號(hào)。例如，P1表示衛(wèi)星網(wǎng)關(guān)位于位置1和3，控制器位于3、6和9?？傊總€(gè)粒子均由2+3=5個(gè)整數(shù)編碼，在初始化過(guò)程中，隨機(jī)生成一組粒子，每個(gè)粒子由k+m個(gè)整數(shù)組成。

圖2 粒子編碼映射

每一個(gè)粒子都是k+m維的，設(shè)當(dāng)前粒子的位置為Uij=[gi1,gi2,…,gik,ci1,ci2,…,cim]，其中i∈1,2,…,N。當(dāng)前速度為vij=[vi1,vi2,…,vik,vi1,vi2,…,vim]。pbestij記錄局部最優(yōu)粒子。gbestij記錄全局最優(yōu)粒子。每次迭代，粒子按式(7)～(8)更新速度vij和位置Uij。

(7)

(8)

γ=γmax-(γmax-γmin)(t/tmax)

(9)

式中：γ為慣性因子(初始權(quán)重)，本文采用慣性因子隨迭代次數(shù)遞減的粒子群算法以提升算法性能[13]；l1和l2是加速系數(shù)，r1和r2是[0,1]之間的隨機(jī)數(shù)。

模擬退火算法[14]是一種基于概率選擇的優(yōu)化求解算法，Metropolis準(zhǔn)則是該算法的核心，模擬退火算法具有結(jié)構(gòu)簡(jiǎn)單、限制條件少、使用靈活等優(yōu)點(diǎn)?；诟怕蔬x擇，模擬退火算法在求解過(guò)程中對(duì)于較差的值也會(huì)根據(jù)溫度以一定的概率接受，這是算法在尋優(yōu)過(guò)程中跳出局部?jī)?yōu)解關(guān)鍵。首先，選擇一個(gè)隨機(jī)解并計(jì)算其適應(yīng)度函數(shù)值F(i)，在迭代過(guò)程中，以一定的規(guī)則生成該解的鄰域解并計(jì)算其適應(yīng)度函數(shù)值F′(i)，然后根據(jù)Metropolis準(zhǔn)則進(jìn)一步判斷是否接受擾動(dòng)所產(chǎn)生的新解代替全局最優(yōu)解，Metropolis準(zhǔn)則表達(dá)式如下:

(10)

式中：Δ=F′(i)-F(i)。由于接受概率是隨溫度的下降而降低的，因此，選擇起止溫度時(shí)不能過(guò)高或過(guò)低，在本文中我們?cè)O(shè)置初始溫度T0為1 000，終止溫度Tfinal為1。

盡管粒子群算法具有收斂速度快等許多優(yōu)點(diǎn)，但有時(shí)會(huì)陷入局部最優(yōu)。為避免陷入局部最優(yōu)，在本文中，引入了SA算法。SA算法具有較強(qiáng)的局部搜索能力，PSO算法具有較強(qiáng)的全局搜索能力。通過(guò)兩者的結(jié)合，充分利用了2種算法優(yōu)勢(shì)，提高了搜索效率，解決單個(gè)算法在優(yōu)化求解中存在的問(wèn)題。此外，為減少因每次迭代使用SA算法所帶來(lái)的計(jì)算復(fù)雜性，本文設(shè)置當(dāng)全局最優(yōu)解在t代中不發(fā)生變化的情況下才使用SA算法，這一定程度上簡(jiǎn)化了所設(shè)計(jì)算法的復(fù)雜性。所提算法如表1和表2所示。

表1 模擬退火與粒子群的混合算法(SABPSO)輸入:G=(V,E),Lmax,k(衛(wèi)星網(wǎng)關(guān)數(shù)量),m(控制器數(shù)量)輸出:Rmax(最大可靠性),W(k個(gè)網(wǎng)關(guān)最佳位置),C(m個(gè)控制器最佳位置)1:初始化參數(shù)2:pbest←0,gbest←03:for i=1:N do4:隨機(jī)生成粒子位置Uij5:v←0,通過(guò)式(5)計(jì)算適應(yīng)度值6:if F(i)>pbest do7:pbest←F(i)8:pb←p//記錄局部最優(yōu)解及粒子9:end if10:end for11:gbest←pbest12:gbesthistory←gbest13:gb←pb \記錄全局最優(yōu)解及粒子14:While t

表2 SA算法輸入:T0,Tfinal,tmax,α,gb輸出:Rmax(最大可靠性),Uij(粒子位置)1:初始化參數(shù)2:While T≥Tfinal do3:生成一組新的粒子位置U'ij4:計(jì)算適應(yīng)度值5:Δ=F'(i)-F(i)6:if P≥r or Δ≤0 do7:更新的全局最優(yōu)解8:end if9:T=Tα10:end while

經(jīng)過(guò)多次實(shí)驗(yàn)，關(guān)于SABPSO算法的初始參數(shù)設(shè)置見(jiàn)表3所示。

表3 算法參數(shù)設(shè)置

為了評(píng)估本文提出的衛(wèi)星網(wǎng)關(guān)和控制器聯(lián)合部署算法，采用Topology Zoo[15]上的現(xiàn)實(shí)網(wǎng)絡(luò)拓?fù)溥M(jìn)行實(shí)驗(yàn)仿真，表4給出了詳細(xì)的拓?fù)湟约案黝惞收细怕试O(shè)置。本文仿真程序均在MATLAB(R2018a)上編譯運(yùn)行。另外，本文將枚舉算法、SASA算法、隨機(jī)算法作為對(duì)比算法，其中隨機(jī)算法選取隨機(jī)部署1 000次后的最佳部署方案。

表4 拓?fù)渑c故障概率設(shè)置

首先，我們將通過(guò)SABPSO、OEA、SASA、隨機(jī)放置等不同算法研究聯(lián)合部署問(wèn)題，并利用Agis拓?fù)溽槍?duì)網(wǎng)絡(luò)可靠性，運(yùn)行時(shí)間進(jìn)行仿真比較。

圖3～4顯示了在衛(wèi)星網(wǎng)關(guān)k=3、最大時(shí)延10 ms約束下，不同算法在相同網(wǎng)絡(luò)拓?fù)浜凸收细怕试O(shè)置見(jiàn)表4，網(wǎng)絡(luò)的平均可靠性和運(yùn)行時(shí)間隨SDN控制器數(shù)量m變化的比較。

圖3 Agis網(wǎng)絡(luò)中不同算法下網(wǎng)絡(luò)平均可靠性比較

由圖3可知，增加部署控制器可以直接提高集成網(wǎng)絡(luò)的平均可靠性，原因在于合理部署更多控制器可以極大改善網(wǎng)絡(luò)連接關(guān)系，使得交換機(jī)與控制器之間的跳數(shù)減少甚至為零。此外，由圖4可見(jiàn)，隨著控制器數(shù)量的增加，枚舉算法的運(yùn)行時(shí)間變得極長(zhǎng)，因此不適合解決大規(guī)模網(wǎng)絡(luò)中的部署，而其他算法則可以在較短時(shí)間內(nèi)實(shí)現(xiàn)較優(yōu)部署。從圖中可看出，本文的算法較文獻(xiàn)[9]中的SASA算法更接近最優(yōu)解，且運(yùn)行時(shí)間大大降低，更易于實(shí)現(xiàn)(運(yùn)行時(shí)間減少48%)。

圖4 Agis網(wǎng)絡(luò)中不同算法下運(yùn)行時(shí)間比較

此外，為了更好地證明本文所提算法的優(yōu)越性，本文在表4所列的不同拓?fù)浜凸收细怕氏逻M(jìn)行實(shí)驗(yàn)，得到了在不同網(wǎng)絡(luò)拓?fù)?，各算法所求網(wǎng)絡(luò)平均可靠性的比較結(jié)果，見(jiàn)圖5。

圖5 不同網(wǎng)絡(luò)拓?fù)湎戮W(wǎng)絡(luò)平均可靠性比較

由圖可知，在表4所列3種不同拓?fù)渲?，隨機(jī)放置算法性能最差，而本文算法的平均可靠性更接近網(wǎng)絡(luò)的最佳性能，較其他算法更有優(yōu)勢(shì)。

4 結(jié)語(yǔ)

本文針對(duì)基于SDN的5G-衛(wèi)星集成網(wǎng)絡(luò)中控制器和衛(wèi)星網(wǎng)關(guān)聯(lián)合部署問(wèn)題，提出了SABPSO算法，以實(shí)現(xiàn)在延遲約束條件下最大化集成網(wǎng)絡(luò)的可靠性，文中在3種不同拓?fù)浜凸收细怕试O(shè)置下進(jìn)行試驗(yàn)，實(shí)驗(yàn)結(jié)果表明，與枚舉算法、SASA算法、隨機(jī)放置算法相比，本文所提算法在運(yùn)行時(shí)間與性能上較其他算法更有優(yōu)勢(shì)。