郭子楨,梁俊,肖楠,陳威龍

(空軍工程大學信息與導航學院,710077,西安)

由于傳統(tǒng)衛(wèi)星網絡存在可拓展性差、設備難以更新升級、多種協(xié)議并存、無法為不同需求的用戶提供細粒度服務等問題[1],近年來軟件定義衛(wèi)星網絡(SDSN)開始走進研究人員的視野。SDSN采用控制與轉發(fā)分離的軟件定義網絡(SDN)架構,通過控制器管理整個網絡,提高了網絡的可擴展性和可編程性[2-3]。低軌道(LEO)衛(wèi)星星座作為衛(wèi)星網絡轉發(fā)平面的主要組成部分[4-5],如何高效地對其進行管理是SDSN的核心問題之一。不同于地面SDN網絡,LEO衛(wèi)星拓撲高速動態(tài)變化、業(yè)務時空分布不均勻,因此需要針對性的進行控制器的部署。

Wu等建立了SDSN開銷模型,以開銷為優(yōu)化目標,將最差時延作為衡量網絡可靠性的指標,卻忽略了鏈路失效、節(jié)點失效對網絡性能的影響[6]。Hu等提出SoftLEO策略,按軌道將衛(wèi)星分為6組,挑選6個運動方向相同、緯度相近且由軌道間鏈路相連的節(jié)點部署控制器[7],保證了網絡的時延性能,但對可能的節(jié)點失效及鏈路失效缺乏考慮。Xu等的部署方法與SoftLEO類似,不過為避免衛(wèi)星進入兩極地區(qū)時對控制器間通信的影響而動態(tài)地選擇赤道附近的衛(wèi)星節(jié)點部署控制器,且控制器的數(shù)量增加了一倍[8],同時也欠缺對可靠性的考慮。劉治國等以端到端時延為控制器部署評價指標,但部署模型以管理節(jié)點數(shù)表征控制器負載,對于業(yè)務分布極不均勻的衛(wèi)星網絡難以做到控制器間負載均衡[9]。楊力等通過負載門限判別控制器狀態(tài),進而實現(xiàn)負載的動態(tài)遷移,然而仿真實驗并未基于衛(wèi)星網絡拓撲[10]。Wu等主要關注已有衛(wèi)星網絡的擴展問題,未將網絡構建時的控制器部署問題作為研究重點[11]。Papa等以流建立時延為優(yōu)化目標,部署方案擁有較好的時延性能,但缺乏對除時延外其他網絡性能指標的考慮[12]。

現(xiàn)有SDSN控制器部署研究仍存在不足:一是忽略控制器處理時延僅考慮傳播時延。這相當于忽視控制器間處理能力差異,默認所有數(shù)據包的處理時間都相同。實際上,當控制器處理能力較小時,處理時延也對網絡性能有較大影響。二是缺乏對可靠性的考慮。SDN網絡的可靠性研究已較多而SDSN控制器可靠部署問題卻仍缺乏足夠的重視。

本文提出一種SDSN多控制器可靠部署算法,并利用改進的人工魚群算法進行求解。該算法將處理時延加入控制時延模型以優(yōu)化網絡時延,同時通過定義節(jié)點失效概率及鏈路失效概率衡量網絡可靠性。仿真對比說明,MCRDA算法能在保證較小的控制時延的前提下實現(xiàn)控制器間的負載均衡,并使網絡可靠性提高30%以上。

1 模型構建

本文主要面向SDN架構下LEO星座中控制器部署問題進行建模,以解決控制器部署位置的選取問題(選擇部分LEO節(jié)點作為控制器),并建立控制器到交換機間的控制關系[13]。SDSN網絡可描述為G=(V,E),構建模型所用參數(shù)及其說明見表1。表中xi,j、an均為二進制變量,用于表征交換機-控制器連接關系及控制器部署位置,其取值方法如下

(1)

(2)

表1 網絡參數(shù)匯總表

在定義其他參數(shù)前對模型進行說明如下:控制器可能部署于網絡中任意節(jié)點上,且位置確定后不可更改;使用時間片劃分思想,處理拓撲動態(tài)變化的LEO衛(wèi)星網絡[14],并假設在時間片持續(xù)時間內網絡拓撲、業(yè)務、控制器與交換機連接關系保持不變;網絡重規(guī)劃僅在時間片切換時進行。

1.1 控制時延

為使網絡能滿足不同用戶的需求,控制器部署應當使網絡中控制器到交換機的響應時間(控制時延)[15]盡量短。衛(wèi)星網絡覆蓋范圍廣,為了減小控制時,要求控制器分布盡量均勻,如果過于集中,則必然造成部分節(jié)點控制時延過大。因此,本文定義了最遠距離以防止控制器的集中。

定義1最遠距離D。D代表交換機與最近控制器距離的最大值,該值較大說明部分節(jié)點距離控制器較遠,網絡中控制器分布比較集中;反之,則說明控制器分布較為均勻。D表達式如下

(3)

現(xiàn)有大部分衛(wèi)星網絡控制器部署研究及地面廣域網研究都忽略了控制器處理時延,本文在時延模型中加入了處理時延。

定義2控制時延T。Ti,j表示交換機sj與控制器ci進行一次控制信息交互所花費的時間,其計算公式如下

(4)

式中:右側第2項為往返路徑上的傳播時延;右側第1項為流請求在控制器中處理所需的處理時延;c為自由空間光速。處理時延只與流請求大小及控制器處理能力有關,不同交換機處理時延相互獨立。將控制器ci的控制時延Ti定義為ci到其控制的所有交換機的控制時延之和[16]

(5)

Ti值越小則控制器對所屬交換機的控制越高效。出于負載均衡的考慮,將整個網路的控制時延T定義為各個控制器控制時延按負載加權的和,qi為控制器ci的負載,計算式如下

(6)

(7)

由定義可知,負載大的控制器對網絡控制時延的影響更大。在控制器處理能力相同時,負載大的控制器往往有較大的控制時延,網絡中出現(xiàn)過載控制器將嚴重影響網絡的控制時延。因此,負載加權方法在保證網絡時延性能的同時也兼顧了控制器間的負載均衡性能。

1.2 控制鏈路可靠性

控制鏈路可靠性是規(guī)劃網絡時必須考慮的重要因素。由于衛(wèi)星網絡的柵格化,網絡中兩個節(jié)點間往往存在多條聯(lián)通路徑,因此能夠通過控制器選址及控制關系在保證網絡時延的情況下盡可能提高控制鏈路可靠性,使網絡更加可靠。本文主要基于概率分析控制鏈路的可靠性。

定義3直連鏈路失效概率re。直連鏈路失效概率由鏈路長度決定,長鏈路失效概率更大。re的計算式如下

re=(1-αu)de

(8)

式中:αu為單位長度失效概率;de為直連鏈路長度。由于軌道間鏈路和軌道內鏈路的差別,不同類型的鏈路應當具有不同的單位長度失效概率。衛(wèi)星節(jié)點在極點附近會關閉其軌道間鏈路而保留軌道內鏈路,頻繁的開閉使軌道間鏈路的單位長度鏈路失效概率應當比軌道內鏈路更高。

定義4節(jié)點失效概率rn。節(jié)點失效概率表示網絡中節(jié)點無法正常行使功能的概率。

定義5控制節(jié)點失效概率ξ。在選擇控制器時,為了保證網絡的可靠性,應當盡量將控制器部署在節(jié)點失效概率較小的節(jié)點上。ξ的計算式如下

(9)

定義6控制鏈路可靠系數(shù)R?？刂奇溌房煽肯禂?shù)由控制鏈路上的節(jié)點失效概率及直連鏈路失效概率共同決定,交換機sj與控制器ci間的控制鏈路可靠系數(shù)Ri,j計算方法如下

(10)

ci所屬控制域的控制鏈路可靠系數(shù)Ri為控制域內所有控制鏈路可靠系數(shù)的平均值。同樣出于負載均衡的考慮,整個網絡的控制鏈路可靠系數(shù)R定義為各控制域控制鏈路可靠系數(shù)按負載加權的和,Ri和R計算式如下

(11)

(12)

控制鏈路可靠系數(shù)能夠反應網絡的可靠性,可靠系數(shù)大的網絡控制器與交換機之間的連接更不容易中斷,發(fā)生控制鏈路失效的概率更小。

定義7節(jié)點吸引度λj。λj表示節(jié)點vj對控制器的吸引力,控制器更傾向于部署在λj大的節(jié)點上。該值由節(jié)點失效概率及其所連接的直連鏈路共同決定,節(jié)點連接的直連鏈路越多、鏈路失效概率越小、節(jié)點失效概率越小,則節(jié)點吸引度越大、可靠性越好。λj的計算式如下

(13)

1.3 目標函數(shù)

為實現(xiàn)對時延、可靠性等評價指標的綜合優(yōu)化,將SDSN控制器部署目標函數(shù)概括如下

(14)

(15)

?i∈C,qi

(16)

(17)

式(14)第一項為控制器選址優(yōu)化目標,后一項為控制域劃分優(yōu)化目標。求解時由于兩項優(yōu)化目標難以同時最優(yōu),故對第一項優(yōu)化目標構造非劣解集而主要對后一項進行優(yōu)化。式(15)表示每個交換機僅受一個控制器控制;式(16)表示控制器負載不能超過處理能力;式(17)表示控制節(jié)點平均失效概率應小于所有節(jié)點平均失效概率。

2 求解算法

控制器部署問題已被證實為非確定性困難(NP-hard)問題[17],而智能啟發(fā)式算法是求解NP-hard問題的有效手段之一。由于人工魚群算法具有實現(xiàn)簡單、魯棒性強、對參數(shù)選擇不敏感、全局尋優(yōu)能力強、收斂速度快等優(yōu)點[19],本文利用人工魚群算法求解SDSN控制器部署問題。人工魚群算法所用參數(shù)見表2。人工魚群算法中共包括4種行為:覓食行為,魚群趨于向視野范圍內食物濃度高的區(qū)域移動;聚群行為,人工魚趨于聚集成群,在避免擁擠的情況下向鄰居伙伴的位置中心移動;追尾行為,當一條人工魚發(fā)現(xiàn)食物后,附近的人工魚會尾隨而來;隨機行為,人工魚隨機地在水中自由游動。人工魚群算法流程如圖1所示。

表2 人工魚群算法參數(shù)匯總表

圖1 人工魚群算法流程

經典人工魚群算法運算時步長固定,若步長過小,算法收斂速度慢,可能無法到達最優(yōu)解;若步長過大,算法可能在最優(yōu)解周圍振蕩而無法準確收斂[18]。因此,為了提升算法尋優(yōu)能力并加快收斂速度,本文采用指數(shù)函數(shù)型衰減的步長,步長更新方法如下

(18)

式中:ξmax為最大步長;ξmin為最小步長。在運算前期,步長較大使樣本能夠快速地接近最優(yōu)解;在運算后期,步長逐漸減小,使樣本能夠準確停留在最優(yōu)解位置[19]。

本文利用改進的人工魚群算法求解SDSN控制器部署問題的MCRDA算法,具體步驟如下。

輸入:SDSN網絡G,網絡流量,控制器處理能力p,控制器數(shù)量M,人工魚群算法參數(shù)

輸出:控制器部署位置集合A,控制域劃分X

1:采集d、rn、re等網絡參數(shù)

2:生成初始樣本

3:whileβ<βmaxdo

4:更新步長ξ

5: whilek

6: 計算各樣本目標函數(shù)值

7: 用改進的人工魚群算法更新樣本位置

8: endwhile

9: 構造非劣解集并排除無效解

10:endwhile

11:得到X、A

3 仿真與性能評估

3.1 仿真條件

(1)實驗平臺介紹。仿真實驗均利用STK 11.01進行衛(wèi)星網絡拓撲信息的采集,利用Matlab 2016b進行算法仿真以及實驗結果處理。

(2)拓撲選擇。由于Iridium為最經典的LEO衛(wèi)星星座且具有星間鏈路,諸多衛(wèi)星網絡相關研究均將其作為實驗拓撲,故以Iridium星座作為本文實驗拓撲,具體參數(shù)如表3所示。

表3 仿真實驗拓撲參數(shù)

(3)業(yè)務模型。本文所用衛(wèi)星網絡業(yè)務流量模型將地球表面劃分為288個區(qū)域,在每個區(qū)域內以106為單位計算該區(qū)域的用戶數(shù)(該用戶數(shù)為區(qū)域內用戶總數(shù)而不是正在使用網絡的用戶數(shù))及流量,每個區(qū)域的流量由距其最近的衛(wèi)星節(jié)點轉發(fā)[21]。每組用戶的流量情況受當?shù)貢r間的影響,10時至22時流量達到最大值1 Mb/s,0時至6時最小,具體如下

(19)

需要注意的是,在SDN架構下,不是所有數(shù)據包都需要控制器處理,只有無法匹配流表的數(shù)據包需要調用控制器處理資源,設這部分數(shù)據的比例為10%[12]。由此模型,交換機流請求速率的值即為所有由該交換機負責轉發(fā)的地區(qū)業(yè)務流量之和乘以10%。

(4)仿真參數(shù)。在LEO星座每個周期內設置6個時間片,將部署方案各時間片內仿真性能的平均值作為方案最終性能,控制器處理能力取60 Mb/s。在0～0.1范圍內,差異化地確定各個節(jié)點的失效概率,且不同節(jié)點的失效概率相互獨立。人工魚群算法中種群數(shù)量為400,迭代次數(shù)為200,試探次數(shù)為50,視野為37,步長范圍為5～55,擁擠度因子為0.618。

3.2 仿真結果分析

為了展示MCRDA算法的性能及優(yōu)勢,本文共設計了3組實驗。在仿真實驗中,除了控制時延與網絡可靠性,負載均衡也是反映網絡性能的一個重要指標。本文定義控制器負載標準差為負載均衡系數(shù)δ,并以此表征網絡負載均衡性能,計算方法如下

(20)

(21)

圖2 控制器節(jié)點平均失效概率與控制數(shù)的關系

(1)實驗1:控制器節(jié)點平均失效概率。由圖2可知,MCRDA算法選擇的控制器節(jié)點平均失效概率隨控制器數(shù)量的增加有增大的趨勢,不過仍小于所有網絡節(jié)點的平均失效概率。這是由于控制器數(shù)量較少時,在選擇控制器節(jié)點時有較大余裕?？刂破鲾?shù)量較多時,由于控制時延的約束,一些失效概率較大的節(jié)點不可避免地被作為控制器使用,使得控制器節(jié)點平均失效概率略微上漲。最極端的情況就是網絡中所有節(jié)點均部署控制器,此時控制器節(jié)點平均失效概率達到最大,等于所有網絡節(jié)點的平均失效概率。

(2)實驗2:考慮可靠性對控制時延的影響。由于控制時延和網絡可靠性難以同時達到最優(yōu),在優(yōu)化目標中加入可靠性指標,將不可避免地帶來控制時延的下降。由圖3～5可知,相較于僅對控制時延進行優(yōu)化的部署方案(下稱delay方案),本文算法能夠犧牲較小的控制時延和負載均衡率,換取網絡可靠性的較大提升,其中控制時延性能下降不足7.4%,網絡控制鏈路可靠性提升了近50%。這是由于衛(wèi)星網絡的柵格性,使得網絡中兩個節(jié)點間存在多條可能的路徑,因此在部署控制器時,通過合理調整控制器的位置能夠在控制鏈路長度相差不大的情況下取得更高的可靠性指數(shù)。

圖3 兩種算法控制時延的對比

圖4 兩種算法負載均衡率的對比

圖5 兩種算法控制鏈路可靠性的對比

(3)實驗3:MCRDA算法與其他部署方案對比。k-means算法將節(jié)點按照距離劃域,并在域中心處部署控制器[22];RD算法隨機選擇控制器部署位置,并按最短距離原則為控制器分配交換機;NSGA-Ⅱ算法綜合考慮網絡端到端時延與負載均衡,靜態(tài)的規(guī)劃衛(wèi)星網絡[9]。MCRDA算法與其他部署方案性能對比見圖6～8。

圖6 4種算法控制時延的對比

圖7 4種算法負載均衡率的對比

圖8 4種算法控制鏈路可靠性的對比

由圖6～8可見,隨著控制器部署數(shù)量的增加,4種算法的控制時延和負載均衡率均呈現(xiàn)下降趨勢,可靠性呈上漲趨勢。這是由于,隨著控制器數(shù)量的增加,網絡控制鏈路長度的減小以及總處理能力的增大。NSGA-Ⅱ算法將端到端時延作為優(yōu)化目標,導致網絡中控制器到交換機的最大時延較大,因而控制鏈路較長,控制時延與網絡可靠性不理想。NSGA-Ⅱ算法雖然加入了對負載均衡的考慮,但卻忽略了每個衛(wèi)星節(jié)點流請求數(shù)量的差異而追求控制器連接的衛(wèi)星節(jié)點數(shù)量的均衡,故其負載均衡性能雖優(yōu)于另外兩種算法卻仍與MCRDA算法有一定差距。k-均值算法、RD算法分析時延時忽略了處理時延,也未考慮控制器負載差異對網絡性能的影響,故而負載均衡性能較差。不過由于兩種算法優(yōu)先挑選距離短的鏈路作為控制鏈路,所以控制鏈路可靠性要優(yōu)于NSGA-Ⅱ算法。由于全面的考慮了時延與可靠性,并且在建立模型時加入了對負載均衡的約束,MCRDA算法在控制時延、負載均衡率、可靠性方面均優(yōu)于對比算法,控制時延提升23%以上,負載均衡率提升25%以上,網絡的控制鏈路可靠性提升約30%。

本實驗還進行了MCRDA算法與現(xiàn)有衛(wèi)星網絡控制器SoftLEO、SCSS部署方案的性能對比,如圖9所示。

圖9 MCRDA與其他衛(wèi)星網絡控制器部署方案對比

由圖9可知,在不同控制器部署數(shù)量情況下,MCRDA算法各項性能均優(yōu)于對比方案,尤其是負載均衡性能提升可達53.2%。這是因為,SoftLEO方案與SCSS方案均按照軌道劃分控制域,衛(wèi)星網絡業(yè)務空間、時間分布的不均勻特性不可避免地導致控制器間的負載差距大。同時,這種部署方式使得控制鏈路上只包含軌道內鏈路,不含失效概率較大的軌道間鏈路,因此這兩種方案的控制鏈路可靠性均較為優(yōu)秀,不過仍略低與本文算法。值得一提的是,SCSS部署方案要求網絡中所有衛(wèi)星節(jié)點均安裝控制器模塊(同一時刻只有部分節(jié)點開啟該模塊作為控制器使用),同時動態(tài)調整控制器的開閉狀態(tài)以適應網絡業(yè)務和拓撲的變化,這就使得該算法的設備制造、發(fā)射成本巨大,經濟效益較差。

4 結 論

本文結合衛(wèi)星網絡特點,同時考慮到鏈路失效與節(jié)點失效,提出了一種SDSN多控制器可靠部署算法,將處理時延加入時延模型以提高網絡性能,并利用可變步長的人工魚群算法求解。仿真結果表明,與現(xiàn)有控制器部署方案相比,MCRDA算法能夠在保持良好時延性能的同時,將網絡可靠性提升30%以上,負載均衡性能提升25%以上。不過本文仍有以下不足:計算鏈路失效概率時未考慮流量擁塞,缺乏對控制器間通信的研究分析。這些不足將在未來研究中加以改進。