基于SDN與NDN的衛(wèi)星網(wǎng)絡(luò)多約束路由算法

摘要：針對(duì)NDN衛(wèi)星網(wǎng)絡(luò)內(nèi)容傳輸時(shí)延高、丟包率高且請(qǐng)求命中率低的問題，提出了一種基于SDN與NDN的衛(wèi)星網(wǎng)絡(luò)多約束路由算法，并命名為SNMcRA。基于SDN的集中控制與全局視圖，通過建立多約束路由模型，將鏈路多約束信息與蟻群算法相結(jié)合以求解滿足時(shí)延、帶寬、丟包率多約束的代價(jià)最小路徑，由節(jié)點(diǎn)在包轉(zhuǎn)發(fā)的過程中動(dòng)態(tài)完成轉(zhuǎn)發(fā)表FIB和待定請(qǐng)求表PIT的構(gòu)建。實(shí)驗(yàn)結(jié)果表明，該算法與DSP算法相比時(shí)延降低了35%，帶寬利用率提升了29%，丟包率降低了17%，并且在請(qǐng)求命中率方面也具有顯著優(yōu)勢(shì)。

關(guān)鍵詞：SDN； NDN； 衛(wèi)星網(wǎng)絡(luò)； 路由算法

中圖分類號(hào)：TN927.2文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695（2022）08-036-2454-05

doi：10.19734/j.issn.1001-3695.2021.12.0692

Satellite network multi-constraint routing algorithm based on SDN and NDN

Liu Zhiguo1a，1b， Yao Qiaoyu1a，1b， Pan Chengsheng2

（1.a.School of Information Engineering， b.Key Laboratory of Communication amp; Network， Dalian University， Dalian Liaoning 116600， China; 2.School of Electronics amp; Information Engineering， Nanjing University of Information Science amp; Technology， Nanjing 211800， China）

Abstract：Aiming at the problems of high content transmission delay， high packet loss rate and low request hit rate in NDN satellite network， this paper proposed a multi-constraint routing algorithm for satellite network based on SDN and NDN and named SNMcRA （satellite networks multi-constraint routing algorithm）. Based on SDN’s centralized control and global view， by establi-shing a multi-constraint routing model， it combined the multi-constraint information of links with ant colony algorithm to solve the least-cost path that met the multi-constraints of delay， bandwidth and packet loss rate， and the nodes dynamically completed the construction of forwarding table FIB（forwarding information base） and pending request table PIT（pending interest table） in the process of packet forwarding. Experimental results show that compared with DSP algorithm， this algorithm reduces the time delay by 35%， improves the bandwidth utilization by 29%， reduces the packet loss rate by 17%， and has significant advantages in the request hit rate.

Key words：SDN; named data networking（NDN）; satellite network; routing algorithm

0引言

隨著空間技術(shù)的飛速發(fā)展，衛(wèi)星網(wǎng)絡(luò)已成為全球通信的重要組成部分［1］。路由協(xié)議作為衛(wèi)星網(wǎng)絡(luò)通信協(xié)議的核心，在提高衛(wèi)星網(wǎng)絡(luò)數(shù)據(jù)傳輸效率和可靠性方面意義重大［2］。同時(shí)，用戶對(duì)視頻、語音等多媒體內(nèi)容的需求飛速增長(zhǎng)［3，4］，而基于IP的衛(wèi)星網(wǎng)絡(luò)在內(nèi)容傳輸上存在固有缺陷，即“身份—位置”的綁定使網(wǎng)內(nèi)重復(fù)傳輸大量相同內(nèi)容，極大浪費(fèi)星上帶寬資源。因此，在衛(wèi)星網(wǎng)絡(luò)環(huán)境中，需要一種新型的網(wǎng)絡(luò)架構(gòu)來克服上述問題。

命名數(shù)據(jù)網(wǎng)絡(luò)（named data networking，NDN）作為以數(shù)據(jù)為中心的未來網(wǎng)絡(luò)架構(gòu)，將內(nèi)容與位置解耦，并支持網(wǎng)絡(luò)內(nèi)緩存，緩解了傳統(tǒng)TCP/IP網(wǎng)絡(luò)傳輸效率低的問題［5～7］。NDN采用接收者驅(qū)動(dòng)的通信模式，包含興趣包（interest packet）和數(shù)據(jù)包（data packet）兩種包結(jié)構(gòu)，并通過內(nèi)容緩存表（content store，CS）、待定請(qǐng)求表（PIT）和轉(zhuǎn)發(fā)信息表（FIB）進(jìn)行包的轉(zhuǎn)發(fā)［8～10］。

NDN現(xiàn)有的轉(zhuǎn)發(fā)方法在拓?fù)浣Y(jié)構(gòu)穩(wěn)定的場(chǎng)景下具有一定優(yōu)勢(shì)。Wang等人提出基于OSPF的命名數(shù)據(jù)網(wǎng)絡(luò)路由協(xié)議，通過洪泛來分發(fā)路由消息，實(shí)現(xiàn)內(nèi)容分發(fā)［11］。Zhang通過周期性廣播鏈路狀態(tài)信息創(chuàng)建網(wǎng)絡(luò)拓?fù)洳⑦M(jìn)行包的分發(fā)，利用逐跳轉(zhuǎn)發(fā)代替基于OSPF的周期性前綴公告泛洪［12］。但在衛(wèi)星網(wǎng)絡(luò)拓?fù)涓邉?dòng)態(tài)變化的環(huán)境下，已有的靜態(tài)映射和泛洪路由或基于鏈路狀態(tài)廣播的路由機(jī)制都難以適用，存在以下問題：a）興趣包的頻繁廣播或多播將導(dǎo)致多個(gè)數(shù)據(jù)源重復(fù)回應(yīng)請(qǐng)求，造成數(shù)據(jù)的冗余傳輸；b）衛(wèi)星鏈路頻繁中斷導(dǎo)致數(shù)據(jù)包可能無法按照興趣包的傳輸路徑反向回傳。

針對(duì)上述問題，Islam等人［13］針對(duì)NDN在頻繁中斷環(huán)境下數(shù)據(jù)包無法及時(shí)得到回復(fù)而重發(fā)的問題，將NDN與DTN相結(jié)合以解決NDN無法適應(yīng)頻繁中斷的問題。文獻(xiàn)［14］根據(jù)可預(yù)知的衛(wèi)星鏈路切換狀態(tài)，以時(shí)變圖的方式進(jìn)行建模，動(dòng)態(tài)計(jì)算時(shí)間相關(guān)的最快路徑實(shí)現(xiàn)包的傳輸，但其只考慮單個(gè)目標(biāo)優(yōu)化，而且聯(lián)絡(luò)拓?fù)鋾r(shí)變性大使得路由效率較低。Zhou等人［15］根據(jù)衛(wèi)星間連接計(jì)劃采用連接圖路由計(jì)算方法制定數(shù)據(jù)包轉(zhuǎn)發(fā)路徑，并采用最優(yōu)及次優(yōu)兩條路徑同時(shí)轉(zhuǎn)發(fā)，但其動(dòng)態(tài)性差且對(duì)衛(wèi)星節(jié)點(diǎn)要求較高。

針對(duì)上述算法的不足，本文提出了一種基于SDN與NDN的衛(wèi)星網(wǎng)絡(luò)多約束路由算法并命名為SNMcRA （satellite networks multi-constraint routing algorithm）。相較于傳統(tǒng)的洪泛路由和基于連接圖的單一目標(biāo)優(yōu)化的路由方法，此方法基于SDN集中控制并利用改進(jìn)的蟻群算法獲取滿足時(shí)延、帶寬和丟包率多約束的代價(jià)最小路徑，實(shí)現(xiàn)包的高效傳輸。

1基于SDN的衛(wèi)星網(wǎng)絡(luò)系統(tǒng)架構(gòu)

SDN（software defined network）架構(gòu)將網(wǎng)絡(luò)的控制層與轉(zhuǎn)發(fā)層分離，有效改善了網(wǎng)絡(luò)管理、控制以及數(shù)據(jù)處理［16，17］。本文設(shè)計(jì)了基于SDN的多層衛(wèi)星網(wǎng)絡(luò)架構(gòu)MsnSDN （multilayer satellite network based on SDN），如圖1所示。三顆GEO衛(wèi)星作為局部控制器，負(fù)責(zé)獲取LEO衛(wèi)星的實(shí)時(shí)狀態(tài)信息，并對(duì)網(wǎng)絡(luò)進(jìn)行路由計(jì)算與管理；轉(zhuǎn)發(fā)層由LEO衛(wèi)星節(jié)點(diǎn)組成，負(fù)責(zé)根據(jù)GEO衛(wèi)星下發(fā)的流表進(jìn)行數(shù)據(jù)傳輸；地面控制中心作為全局控制器負(fù)責(zé)集中控制和管理整個(gè)衛(wèi)星網(wǎng)絡(luò)。

根據(jù)衛(wèi)星網(wǎng)絡(luò)拓?fù)涞闹芷谛院涂深A(yù)測(cè)性，本文采用虛擬節(jié)點(diǎn)策略［18］“屏蔽”衛(wèi)星的高動(dòng)態(tài)性。根據(jù)地面站在地球表面劃分的區(qū)域位置，某區(qū)域上方的虛擬衛(wèi)星節(jié)點(diǎn)保持不變，實(shí)際的衛(wèi)星持續(xù)運(yùn)動(dòng)并根據(jù)區(qū)域位置不斷改變其邏輯地址，從而構(gòu)成一個(gè)覆蓋全球的虛擬固定拓?fù)渚W(wǎng)絡(luò)。

2基于SNMcRA的轉(zhuǎn)發(fā)機(jī)制

NDN中興趣包和數(shù)據(jù)包通過FIB表和PIT表進(jìn)行興趣查找和內(nèi)容返回，因此，要實(shí)現(xiàn)基于NDN的衛(wèi)星網(wǎng)絡(luò)高效路由首先需要進(jìn)行FIB表和PIT表的構(gòu)建。本文通過建立多約束路由模型，根據(jù)GEO衛(wèi)星控制器獲取全局網(wǎng)絡(luò)狀態(tài)信息，執(zhí)行SNMcRA算法求得滿足時(shí)延、帶寬和丟包率多約束的代價(jià)最小路徑，并在包轉(zhuǎn)發(fā)的過程中實(shí)現(xiàn)FIB和PIT的構(gòu)建。

2.1基于SNMcRA的FIB構(gòu)建流程

在衛(wèi)星網(wǎng)絡(luò)場(chǎng)景下，興趣包的廣播式轉(zhuǎn)發(fā)將導(dǎo)致多個(gè)數(shù)據(jù)源重復(fù)回應(yīng)請(qǐng)求，造成數(shù)據(jù)冗余傳輸，浪費(fèi)星上帶寬資源。因此，本文通過將興趣包轉(zhuǎn)發(fā)到GEO衛(wèi)星控制器獲取內(nèi)容源衛(wèi)星節(jié)點(diǎn)，并執(zhí)行多約束路由計(jì)算得到興趣包的最優(yōu)轉(zhuǎn)發(fā)路徑，由此更新/修改FIB表，如圖2所示。

當(dāng)衛(wèi)星節(jié)點(diǎn)收到興趣包后，首先查找CS，若在CS中命中內(nèi)容，則包含內(nèi)容的數(shù)據(jù)包按原路返回，用戶請(qǐng)求得到滿足；否則，查找PIT，若有此內(nèi)容的PIT條目，則添加進(jìn)入接口信息到相應(yīng)條目；否則，繼續(xù)查找FIB，若找到此內(nèi)容轉(zhuǎn)發(fā)接口信息，則按照接口信息進(jìn)行轉(zhuǎn)發(fā)；否則，將興趣包轉(zhuǎn)發(fā)到GEO衛(wèi)星控制器，控制器根據(jù)解析出的內(nèi)容名獲取內(nèi)容源衛(wèi)星節(jié)點(diǎn)，并根據(jù)當(dāng)前全局網(wǎng)絡(luò)狀態(tài)信息執(zhí)行多約束路由計(jì)算興趣包的最優(yōu)轉(zhuǎn)發(fā)路徑，下發(fā)流表給相應(yīng)的LEO衛(wèi)星完成轉(zhuǎn)發(fā)；否則，將興趣包回溯或者丟棄。

2.2基于SNMcRA的PIT構(gòu)建流程

在網(wǎng)絡(luò)拓?fù)浞€(wěn)定的場(chǎng)景下，數(shù)據(jù)包按照興趣包傳輸路徑反向回傳。但衛(wèi)星網(wǎng)絡(luò)拓?fù)鋭?dòng)態(tài)變化，數(shù)據(jù)包在返回之前興趣包轉(zhuǎn)發(fā)路徑的反向路徑可能已經(jīng)不存在。因此，需要?jiǎng)討B(tài)構(gòu)建PIT表。由于NDN本地支持內(nèi)容級(jí)別的重路由，所以當(dāng)PIT表需要更新時(shí)，僅需通過GEO衛(wèi)星控制器執(zhí)行SNMcRA路由計(jì)算即可，如圖3所示。

當(dāng)衛(wèi)星節(jié)點(diǎn)收到數(shù)據(jù)包后，首先查看CS中是否有此數(shù)據(jù)包，若存在，則丟棄該數(shù)據(jù)包；否則，查找PIT。若PIT中記錄的興趣包傳輸鏈路存在，則按照PIT完成數(shù)據(jù)包的轉(zhuǎn)發(fā)與緩存；否則，向GEO衛(wèi)星控制器請(qǐng)求執(zhí)行多約束路由計(jì)算數(shù)據(jù)包最優(yōu)轉(zhuǎn)發(fā)路徑；若計(jì)算成功，則LEO衛(wèi)星節(jié)點(diǎn)按照流表轉(zhuǎn)發(fā)數(shù)據(jù)包，并按照相應(yīng)的緩存策略進(jìn)行緩存；否則，節(jié)點(diǎn)返回NACK。

3基于SNMcRA的路由計(jì)算

為保證興趣包和數(shù)據(jù)包的高效可靠傳輸，本章提出一種多約束路由計(jì)算方法。在建立衛(wèi)星網(wǎng)絡(luò)多約束模型的基礎(chǔ)上，結(jié)合鏈路多約束信息對(duì)基本蟻群算法的狀態(tài)轉(zhuǎn)移規(guī)則以及信息素更新方式進(jìn)行改進(jìn)，進(jìn)而基于改進(jìn)的蟻群算法計(jì)算出滿足時(shí)延、帶寬和丟包率多約束的代價(jià)最小路徑。

3.1多約束模型

將LEO衛(wèi)星系統(tǒng)建模為圖G=（V，E），V為衛(wèi)星節(jié)點(diǎn)集合，E為星間鏈路集合。（k，l）表示節(jié)點(diǎn)k和l之間的鏈路，p（s，d）表示從源節(jié)點(diǎn)s到目的節(jié)點(diǎn)d的一條路徑，k，l，s，d∈V。本文選擇最重要的多個(gè)路徑約束表示如下：

a）通信時(shí)延。

通信時(shí)延dealy（p（s，d））為路徑傳輸時(shí)延與節(jié)點(diǎn)排隊(duì)時(shí)延之和［19］。

dealy（p（s，d））=∑（k，l）∈p（s，d）dealytra（k，l）+∑v∈p（s，d）dealyque（v）（1）

其中：dealytra（k，l）為路徑的傳輸時(shí)延；dealyque（v）為路徑中節(jié)點(diǎn)排隊(duì)時(shí)延。

b）剩余可用帶寬。

剩余可用帶寬ban（k，l）為鏈路總帶寬與已用帶寬之差，屬于凹性參數(shù)。

ban（k，l）=B（k，l）－Bused（k，l）（2）

其中：B（k，l）表示鏈路總帶寬；Bused（k，l）表示鏈路已用帶寬。

c）丟包率。

丟包率loss（p（s，d））為傳輸數(shù)據(jù)包中丟失的數(shù)量占總數(shù)量的比值，屬于可乘性參數(shù)［20］。

loss（p（s，d））=1－∏（k，l）∈p（s，d）（1－loss（k，l））（3）

其中：loss（k，l）是單位時(shí)間內(nèi)路徑p（s，d）中鏈路（k，l）的丟包率。

本文定義最優(yōu)路徑的評(píng)判指標(biāo)為路徑代價(jià)cost（k，l），為通信時(shí)延、可用帶寬、丟包率的加權(quán)之和，計(jì)算公式如下：

cost（k，l）=ω1delay（k，l）Dmin+ω2banmaxban（k，l）+ω3loss（k，l）Lmin（4）

其中：delay（k，l）為鏈路（k，l）的通信時(shí)延；Dmin為當(dāng)前衛(wèi)星網(wǎng)絡(luò)中的最小通信時(shí)延；banmax為當(dāng)前衛(wèi)星網(wǎng)絡(luò)鏈路中可用帶寬的最大值；ban（k，l）為鏈路（k，l）的剩余可用帶寬；loss（k，l）為鏈路（k，l）的丟包率；Lmin為當(dāng)前衛(wèi)星網(wǎng)絡(luò)中的最小丟包率；ωi（i=1，2，3）分別表示時(shí)延、可用帶寬、丟包率的相對(duì)權(quán)重，且∑ωi=1。

本文算法的目標(biāo)是為每個(gè)內(nèi)容請(qǐng)求找到一條路徑代價(jià)最小且滿足時(shí)延、帶寬、丟包率要求的路徑，因此建立多約束路由模型如下：

min cost（p（s，d））=min{∑（k，l）∈p（s，d）cost（k，l）}（5）

s.t.dealy（p（s，d））≤Dmax

min（k，l）∈p（s，d）ban（k，l）≥Bmin

loss（p（s，d））≤Lmax （6）

其中：Dmax、Bmin、Lmax分別表示傳輸業(yè)務(wù)對(duì)通信時(shí)延、可用帶寬、丟包率的約束閾值。

3.2基于改進(jìn)的蟻群算法的模型求解

蟻群算法模擬螞蟻覓食時(shí)在其經(jīng)過的路徑上釋放信息素，路徑越短，螞蟻在此路徑上來回次數(shù)越多，信息素濃度越大，選擇該路徑的螞蟻也越多，最后找到覓食最短路徑［21］。但基本的蟻群算法以尋找最短路徑為目標(biāo)，并且容易陷入局部最優(yōu)解。本文將多約束條件與蟻群算法相結(jié)合，在尋路過程中充分考慮鏈路多約束信息以高效求解滿足時(shí)延、帶寬、丟包率多約束的最優(yōu)路徑。

3.2.1基于先驗(yàn)知識(shí)與概率驅(qū)動(dòng)的狀態(tài)轉(zhuǎn)移規(guī)則

基本的螞蟻狀態(tài)轉(zhuǎn)移公式為

Pq（k，l）（t）=［τ（k，l）（t）］α［η（k，l）（t）］β∑s′∈precq［τ（k，s′）（t）］α［η（k，s′）（t）］βs′∈precq0s′precq （7）

其中：Pq（k，l）（t）為螞蟻q從衛(wèi)星k轉(zhuǎn)移到l的概率；precq為螞蟻q等待訪問節(jié)點(diǎn)集合；τ（k，l）（t）為t時(shí)刻鏈路（k，l）上的信息素濃度；α為信息素啟發(fā)因子，反映轉(zhuǎn)移規(guī)則受到信息素濃度的影響程度；η（k，l）（t）為t時(shí)刻節(jié)點(diǎn)k到l鏈路上的啟發(fā)度，一般η（k，l）（t）=1/d（k，l）（t），d（k，l）（t）表示t時(shí)刻節(jié)點(diǎn)k與l之間的距離；本文定義η（k，l）（t）=1/cost（k，l）（t），即路徑代價(jià)越小對(duì)螞蟻的啟發(fā)作用越大；β為啟發(fā)函數(shù)因子，反映啟發(fā)信息對(duì)轉(zhuǎn)移規(guī)則的影響程度。

基本的螞蟻狀態(tài)轉(zhuǎn)移規(guī)則僅按照概率來選擇下一跳節(jié)點(diǎn)，算法隨機(jī)性高，收斂速度慢。因此，本文采用先驗(yàn)知識(shí)選擇與概率驅(qū)動(dòng)方式來確定螞蟻的下一跳移動(dòng)方向，比基本蟻群算法更好地利用螞蟻正反饋機(jī)制。改進(jìn)后的螞蟻狀態(tài)轉(zhuǎn)移規(guī)則如式（8）所示。

l=arg maxl∈precq{［τ（k，l）（t）］α［η（k，l）（t）］β}p≤p0Pq（k，l）（t） pgt;p0（8）

p0=Nmax－NcNmax（9）

其中：p為［0，1］內(nèi)均勻分布的隨機(jī)數(shù)；p0為狀態(tài)轉(zhuǎn)移因子，如式（9）所示，Nmax為最大迭代次數(shù)，Nc為當(dāng)前迭代次數(shù)。當(dāng)p≤p0時(shí)，利用先驗(yàn)知識(shí)采用非隨機(jī)的搜索方式，即按照信息素與啟發(fā)式函數(shù)乘積最大的節(jié)點(diǎn)進(jìn)行狀態(tài)轉(zhuǎn)移；當(dāng)pgt;p0時(shí)，按照式（7）計(jì)算滿足約束條件的所有節(jié)點(diǎn)的隨機(jī)轉(zhuǎn)移概率Pq（k，l）（t），按照概率大的節(jié)點(diǎn)進(jìn)行狀態(tài)轉(zhuǎn)移。

在算法迭代初期，p0取值較大，使得節(jié)點(diǎn)以大概率選擇確定轉(zhuǎn)移，加快了局部最優(yōu)路徑搜索；迭代后期，p0取值較小，以增大隨機(jī)轉(zhuǎn)移概率，防止陷入局部最優(yōu)。因此，改進(jìn)的狀態(tài)轉(zhuǎn)移規(guī)則通過動(dòng)態(tài)調(diào)整狀態(tài)轉(zhuǎn)移因子，使螞蟻按照不同方式選擇下一跳節(jié)點(diǎn)，豐富了下一跳節(jié)點(diǎn)的可選擇性，并防止算法陷入局部最優(yōu)。

3.2.2基于多約束鏈路代價(jià)的信息素更新規(guī)則

基本的信息素更新方式為

τ（k，l）（t+1）=（1－ρ）τ（k，l）（t）+Δτ（k，l）（t）（10）

Δτ（k，l）（t）=∑mq=1Δτq（k，l）（t）（11）

其中：ρ為信息素?fù)]發(fā)因子，且0lt;ρlt;1；Δτ（k，l）（t）為鏈路（k，l）上信息素量；Δτq（k，l）（t）為螞蟻q在鏈路（k，l）上留下的信息素增量，如式（12）所示。

Δτq（k，l）（t）=Q/Lq第q只螞蟻本次尋路經(jīng)過（k，l）0其他（12）

其中：Q為常數(shù)，表示信息素強(qiáng)度；Lq為螞蟻q在本次循環(huán)中所走的路徑長(zhǎng)度。

基本的信息素更新方式僅考慮單一的路徑長(zhǎng)度因素，不適用于求解多約束路由路徑，因此，本文將多約束條件與信息素更新方式相結(jié)合，使蟻群實(shí)時(shí)感知路徑的時(shí)延、帶寬和丟包率等參數(shù)，指導(dǎo)蟻群及時(shí)調(diào)整路徑搜索策略。改進(jìn)的信息素更新規(guī)則如式（13）所示。

τ（k，l）（t+1）=（1－ρ）τ（k，l）（t）+Δτ（k，l）（t）（13）

Δτ（k，l）（t）=ρ×［1/cost（k，l）（t）］（k，l）∈p（s，d）0（k，l）p（s，d）（14）

其中：cost（k，l）（t）為當(dāng)代最優(yōu)解螞蟻的路徑代價(jià)值，如式（4）所示。當(dāng)所選路徑代價(jià)越小時(shí)，該路徑上的信息素濃度增加越多，從而啟發(fā)更多的螞蟻選擇該條路徑。同時(shí)，為避免信息素濃度過高或過低導(dǎo)致算法過早陷入局部最優(yōu)或停滯搜索，本文將各條尋優(yōu)路徑上的信息素量限制在［τmin，τmax］，當(dāng)超出這個(gè)范圍時(shí)，信息素量被強(qiáng)制限定為τmin或τmax，如式（15）所示。

τ（k，l）（t+1）=τminτ（k，l）（t）≤τmin

（1－ρ）τ（k，l）（t）+Δτ（k，l）（t）τminlt;τ（k，l）（t）lt;τmax

τmaxτ（k，l）（t）≥τmax（15）

綜上，利用改進(jìn)的蟻群算法求解衛(wèi)星網(wǎng)絡(luò)多約束的最優(yōu)路徑的步驟描述如下：

a）初始化網(wǎng)絡(luò)中節(jié)點(diǎn)和鏈路的多約束條件參數(shù)以及蟻群算法中的基本參數(shù)。

b）根據(jù)多約束條件刪除網(wǎng)絡(luò)中不滿足條件的鏈路，得到一個(gè)新的網(wǎng)絡(luò)拓?fù)洌缓蠡谛碌木W(wǎng)絡(luò)拓?fù)銰（V，E）′開始搜索。

c）將源節(jié)點(diǎn)s設(shè)置為螞蟻的當(dāng)前節(jié)點(diǎn)，并加入禁忌表中，設(shè)置迭代次數(shù)Nc=Nc+1。

d）螞蟻根據(jù)狀態(tài)轉(zhuǎn)移規(guī)則（式（8））和多約束條件選擇下一跳節(jié)點(diǎn)，并將選擇的節(jié)點(diǎn)加入禁忌表中。

e）螞蟻判斷當(dāng)前節(jié)點(diǎn)是否為目的節(jié)點(diǎn)，若是，則宣布尋路成功，跳轉(zhuǎn)到步驟g）；否則，執(zhí)行步驟f）。

f）螞蟻判斷當(dāng)前節(jié)點(diǎn)的precq集合是否為空，若為空，則宣布尋路失敗；否則，執(zhí)行步驟d）。

g）目的節(jié)點(diǎn)d根據(jù)路徑代價(jià)cost（p（s，d））選擇一條最優(yōu)路徑，將螞蟻按原路返回，并按照式（13）更新信息素。

h）若Nc=Nmax，則算法循環(huán)結(jié)束，輸出最優(yōu)解；否則，返回步驟c）。

4仿真實(shí)驗(yàn)與結(jié)果分析

4.1仿真場(chǎng)景與參數(shù)設(shè)置

仿真過程中衛(wèi)星網(wǎng)絡(luò)通過三顆GEO衛(wèi)星作為控制器來實(shí)時(shí)控制整個(gè)網(wǎng)絡(luò)，LEO衛(wèi)星采用銥星星座模擬轉(zhuǎn)發(fā)層。仿真場(chǎng)景中，由GEO衛(wèi)星控制器收集LEO網(wǎng)絡(luò)中的節(jié)點(diǎn)鏈路信息，具體參數(shù)如表1所示。

在仿真中，考慮傳輸業(yè)務(wù)的通信時(shí)延、剩余帶寬和丟包率等約束條件，本文設(shè)置時(shí)延、帶寬、丟包率的閾值分別為Dmax=100 ms，Bmin=10～30 MB，Lmax=3%。根據(jù)本征向量法計(jì)算出代價(jià)函數(shù)中時(shí)延、可用帶寬、丟包率的權(quán)值為ωi=（0.55，0.25，0.2）T，并據(jù)此計(jì)算得一致性比率CR=0.04lt;0.1，即該權(quán)向量估計(jì)可被接受。

蟻群算法中參數(shù)的取值很大程度上影響算法性能。針對(duì)螞蟻數(shù)量參數(shù)，當(dāng)螞蟻數(shù)量過大（接近問題規(guī)模）時(shí)，雖然提高了搜索的穩(wěn)定性和全局性，但算法的收斂速度減慢。一般選擇最優(yōu)螞蟻數(shù)為節(jié)點(diǎn)數(shù)量的三分之二，故本文選定螞蟻數(shù)m=45。參考文獻(xiàn)［22］，考慮到信息素濃度初始值過低使得算法循環(huán)次數(shù)增大，因此設(shè)置τ0=20；為避免信息素濃度過低而導(dǎo)致算法提早停止搜索，因此設(shè)置τmin=10；當(dāng)信息素值在100以內(nèi)時(shí)，問題規(guī)模對(duì)于信息素值的選擇影響較小，因此本文選定τmax=100；為保證算法運(yùn)行性能最優(yōu)，因此設(shè)置最大迭代次數(shù)Nmax=50。α、β和ρ的取值由實(shí)驗(yàn)確定，分別測(cè)量當(dāng)固定其余參數(shù)時(shí)，α、β和ρ對(duì)算法收斂到最優(yōu)解的迭代次數(shù)的影響，實(shí)驗(yàn)結(jié)果如圖4、5所示。

由上述實(shí)驗(yàn)可知，隨著α取值的增大，算法迭代次數(shù)逐漸增大，所以，本文選取α=1，此時(shí)，當(dāng)β=2時(shí)算法收斂到最優(yōu)解的迭代次數(shù)最少，選取α=1，β=2。在確定α和β的值后，對(duì)ρ的取值實(shí)驗(yàn)結(jié)果如圖5所示。由圖5結(jié)果可知，當(dāng)ρ=0.5時(shí)，算法收斂到最優(yōu)解時(shí)的迭代次數(shù)最少，因此選取ρ=0.5。

4.2仿真結(jié)果分析

將本文SNMcRA算法與基本蟻群優(yōu)化（ant colony optimization，ACO）算法進(jìn)行算法收斂性能比較。

圖6為算法收斂性比較。隨著螞蟻數(shù)的增加，本文算法達(dá)到最優(yōu)解時(shí)的迭代次數(shù)均少于ACO算法。當(dāng)螞蟻數(shù)為45時(shí)，本文算法迭代6次左右就收斂到最優(yōu)解。這是由于本文算法改進(jìn)了基本蟻群優(yōu)化算法，根據(jù)先驗(yàn)知識(shí)與概率選擇相結(jié)合的方式選擇下一跳節(jié)點(diǎn)，加快了局部最優(yōu)解的搜索；同時(shí)，結(jié)合鏈路多約束信息優(yōu)化了信息素更新方式，并設(shè)置了信息素濃度的上下界，避免算法陷入局部最優(yōu)或停止搜索。所以，本文算法的收斂速度較快。

同時(shí)，本文還在相同場(chǎng)景下仿真了ACO和迪杰斯特拉最短路徑算法（dijkstra shortest path，DSP）以及基于SDN的最短路徑算法［23］（SDN-based shortest path algorithm，SDN-SPA），并針對(duì)網(wǎng)絡(luò)傳輸時(shí)延、鏈路帶寬利用率和丟包率等指標(biāo)進(jìn)行了詳細(xì)的分析與對(duì)比。

本文結(jié)合虛擬拓?fù)洳呗裕抡婺M了100個(gè)靜態(tài)網(wǎng)絡(luò)拓?fù)湎碌牟煌酚伤惴ǖ膫鬏敃r(shí)延，如圖7所示。可以看出，本文算法的傳輸時(shí)延始終小于另外四種算法。具體來說，ACO、DSP及SDN-SPA的平均傳輸時(shí)延分別為0.10 s、0.12 s及0.11 s，本文算法的平均傳輸時(shí)延為0.076 s，相比于其他算法最大降低了35%。當(dāng)網(wǎng)絡(luò)負(fù)載增大時(shí)，由于其他算法僅根據(jù)路徑距離進(jìn)行路徑選擇，容易導(dǎo)致鏈路擁塞，所以時(shí)延較大。而本文算法將時(shí)延作為優(yōu)化目標(biāo)，更傾向于選擇較低時(shí)延的鏈路，路徑時(shí)延性能較好。

圖8為帶寬利用率的對(duì)比仿真。當(dāng)業(yè)務(wù)請(qǐng)求數(shù)小于250時(shí)，四種算法的帶寬利用率相差不大。當(dāng)業(yè)務(wù)請(qǐng)求數(shù)超過250之后，SDN-SPA和DSP的帶寬利用率增大趨勢(shì)變小，這是由于SDN-SPA和DSP均為基于最短路徑算法，優(yōu)先將數(shù)據(jù)流路由到一條最短路徑。相比之下，ACO和本文SNMcRA綜合考慮了鏈路帶寬因素，在計(jì)算路徑時(shí)繞過了擁塞鏈路，將更多的鏈路作為路徑選擇，因此帶寬利用率性能較好。但傳統(tǒng)ACO易陷入局部最優(yōu)解使得其求解效果略差。本文算法結(jié)合鏈路信息對(duì)蟻群算法進(jìn)行了改進(jìn)，從而更快求得最優(yōu)解。當(dāng)業(yè)務(wù)請(qǐng)求數(shù)達(dá)到最大時(shí)，本文算法的帶寬利用率相比其他算法最大提高了29%。

圖9為平均丟包率隨網(wǎng)絡(luò)負(fù)載的變化趨勢(shì)。隨著網(wǎng)絡(luò)負(fù)載的增大，四種路由算法的丟包率均逐漸增大；在網(wǎng)絡(luò)負(fù)載較輕時(shí)，四種路由算法的丟包率相差不大；隨著網(wǎng)絡(luò)負(fù)載的增大，與其他算法相比，本文SNMcRA的丟包率最低，并且最大降低了26%。這是由于ACO、DSP及SDN-SPA在搜索最短路徑時(shí)，不考慮鏈路丟包率條件，只選擇一條距離最短的路徑，而這些最短路徑上很容易產(chǎn)生網(wǎng)絡(luò)擁塞，丟包率增大；本文算法綜合考慮了鏈路的丟包率，在進(jìn)行路徑選擇時(shí)更傾向于選擇較低丟包率的非阻塞路徑，所以丟包率比較小。

圖10為本文MsnSDN架構(gòu)、SWIMNDN架構(gòu)、SDN衛(wèi)星網(wǎng)絡(luò)架構(gòu)在網(wǎng)絡(luò)環(huán)境穩(wěn)定的情況下的請(qǐng)求命中率的對(duì)比。在SDN衛(wèi)星網(wǎng)絡(luò)架構(gòu)下，由于轉(zhuǎn)發(fā)節(jié)點(diǎn)不具備緩存功能，并且請(qǐng)求內(nèi)容的提供者由源節(jié)點(diǎn)指定，所以該架構(gòu)下的請(qǐng)求在衛(wèi)星網(wǎng)絡(luò)中被命中的概率比較低；而在SWIMNDN架構(gòu)下，轉(zhuǎn)發(fā)節(jié)點(diǎn)引入緩存功能后充分利用網(wǎng)內(nèi)節(jié)點(diǎn)緩存，有效提高了衛(wèi)星網(wǎng)絡(luò)中請(qǐng)求的命中率。但本文MsnSDN架構(gòu)中控制器的全局視圖與集中控制，能夠更好地利用內(nèi)容緩存實(shí)現(xiàn)內(nèi)容查找與回傳，因此請(qǐng)求的命中率更高。

為了分析本文SNMcRA的時(shí)間復(fù)雜度，將算法運(yùn)行步驟進(jìn)行細(xì)分并逐步分析其時(shí)間復(fù)雜度，如表2所示。其中，n為L(zhǎng)EO衛(wèi)星節(jié)點(diǎn)數(shù)量，m為螞蟻數(shù)量。

由表2可得，當(dāng)算法運(yùn)行結(jié)束時(shí)螞蟻遍歷的循環(huán)數(shù)為Nc時(shí)，則整個(gè)算法運(yùn)行的時(shí)間復(fù)雜度為O（Ncn2m）。根據(jù)算法的理論與實(shí)際要求，SNMcRA算法在改進(jìn)了傳統(tǒng)蟻群算法的狀態(tài)轉(zhuǎn)移概率規(guī)則及信息素更新方式后，其時(shí)間復(fù)雜度是可以接受的。

5結(jié)束語

本文提出一種基于SDN與NDN的衛(wèi)星網(wǎng)絡(luò)多約束路由算法并命名為SNMcRA。通過建立多約束路由模型，將多約束信息與蟻群算法相結(jié)合，優(yōu)化了基本的蟻群算法中螞蟻狀態(tài)轉(zhuǎn)移規(guī)則以及信息素更新方式，提高了算法的收斂速度和尋優(yōu)能力，高效求解滿足時(shí)延、帶寬、丟包率多約束的代價(jià)最小路徑。仿真實(shí)驗(yàn)表明，本文算法具有更快的收斂速度。同時(shí)，與ACO和DSP相比，本文算法在傳輸時(shí)延、帶寬利用率、丟包率和請(qǐng)求命中率等方面均具有顯著優(yōu)勢(shì)。下一步工作將針對(duì)內(nèi)容請(qǐng)求聚合展開研究，更好地發(fā)揮NDN內(nèi)容分發(fā)的優(yōu)勢(shì)。

參考文獻(xiàn)：

［1］Feng Xuan， Tan Qiang， Liang Zongchuang. The development of sa-tellite mobile communication system［C］// Proc of the 6th Internatio-nal ICST Conference on Communications and Networking in China. Washington， DC： IEEE Computer Society， 2011： 1110-1114.

［2］Kodheli O， Andrenacci S， Maturo N， et al. Resource allocation approach for differential doppler reduction in NB-IoT over LEO satellite［C］// Proc of the 9th Advanced Satellite Multimedia Systems Confe-rence and the 15th Signal Processing for Space Communications Workshop. 2018： 1-8.

［3］Du Jun， Jiang Chunxiao， Wang Jian， et al. Resource allocation in space multi-access systems［J］. IEEE Trans on Aerospace and Electronic Systems， 2017， 53（2）： 598-618.

［4］Din I U， Hassan S， Khan M K， et al. Caching in information centric networking： strategies， challenges， and future research directions［J］. IEEE Communications Surveys amp; Tutorials， 2018， 20（2）： 1443-1474.

［5］劉迪， 黃傳河， 陳希， 等. 基于NDN的多層衛(wèi)星網(wǎng)絡(luò)分布式動(dòng)態(tài)路由方法［J］. 電子學(xué)報(bào)， 2017， 45（11）： 2769-2778. （Liu Di， Huang Chuanhe， Chen Xi， et al. Distributed dynamic routing method of multilayer satellite network based on NDN［J］. Acta Electronic Journal， 2017， 45（11）： 2769-2778.）

［6］Kim S Y， Lee J W. Content allocation in information centric network［C］// Proc of International Conference on information Networking. 2016： 135-140.

［7］胡曉艷， 龔儉. 命名數(shù)據(jù)網(wǎng)絡(luò)NDN的域間多路徑路由機(jī)制［J］. 通信學(xué)報(bào)， 2015， 36（10）： 211-223. （Hu Xiaoyan， Gong Jian. Inter-domain multi-path routing mechanism of named data network NDN［J］. Journal of Communications， 2015， 36（10）： 211-223.）

［8］Zhang Lixia， Afanasyev A， Burke J， et al. Named data networking［J］. ACM Sigcomm Computer Communication Review， 2014， 44（3）： 66-73.

［9］Yi Cheng， Afanasyev A， Wang Lan， et al. Adaptive forwarding in named data networking［J］. ACM SIGCOMM Computer Communication Review， 2012， 42（3）： 62-67.

［10］Yuan Haowei， Crowley P. Scalable pending interest table design： from principles to practice ［C］// Proc of IEEE Conference on Computer Communications. Piscataway， NJ： IEEE Press， 2014： 2049-2057.

［11］Guo Xian， Yang Shengya， Cao Laicheng， et al. A novel routing based on OLSR for NDN-MANET［C］// Advances in Intelligent Systems and Computing. Berlin： Springer， 2020： 698-714.

［12］Hoque A K M， Amin S O， Alyyan A. NLSR： named-data link state routing protocol［C］// Proc of ACM SIGCOMM Workshop on Information-Centric Networking. 2013： 15-20.

［13］Islam H M A， Lukyanenko A， Tarkoma S， et al. Towards disruption tolerant ICN［C］// Proc of IEEE Symposium on Computers and Communication. Piscataway， NJ： IEEE Press. 2015： 212-219.

［14］Liu Di， Huang Chuanhe， Chen Xi， et al. Supporting producer mobi-lity via named data networking in space terrestrial integrated networks［J］. Lecture Notes in Computer Science， 2017， 10251： 829-841.

［15］Zhou Yongqi， Li Wenfeng， Zhao Kanglian. Information centric networking for future deep space networks ［C］// Proc of International Conference on Wireless and Satellite Systems. Berlin： Springer，2019： 437-448.

［16］Xia Wenfeng， Wen Yonggang， Heng F C， et al. A survey on software defined networking［J］. IEEE Communications Surveys and Tutorials， 2015， 17（1）： 27-51.

［17］Bu Chao， Wang Xingwei， Huang Min， et al. SDNFV-based dynamic network function deployment： model and mechanism［J］. IEEE Communications Letters， 2018， 22（1）： 93-96.

［18］齊小剛， 馬久龍， 劉立芳. 基于拓?fù)淇刂频男l(wèi)星網(wǎng)絡(luò)路由優(yōu)化［J］. 通信學(xué)報(bào)， 2018， 39（2）： 11-20. （Qi Xiaogang， Ma Jiulong， Liu Lifang. Routing optimization of satellite network based on topology control［J］. Journal of Communication， 2018， 39（2）： 11-20.）

［19］Liu Ziluan， Li Jiangsheng， Wang Yanru， et al. HGL： a hybrid glo-bal-local load balancing routing scheme for the Internet of Things through satellite networks［J］. International Journal of Distributed Sensor Networks， 2017， 13（3）： 69-72.

［20］魏德賓， 劉健， 潘成勝， 等. 衛(wèi)星網(wǎng)絡(luò)中基于多QoS約束的蟻群優(yōu)化路由算法［J］. 計(jì)算機(jī)工程， 2019， 45（7）： 114-120. （Wei Debin， Liu Jian， Pan Chengsheng， et al. Ant colony optimization routing algorithm based on multiple QoS constraints in satellite networks［J］. Computer Engineering， 2019， 45（7）： 114-120.）

［21］Li Sicong， Cai Saihua， Li Li， et al. CAAS： a novel collective action-based ant system algorithm for solving TSP problem［J］. Soft Computing， 2020， 24（12）： 9257-9278.

［22］陳穎杰， 高茂庭. 基于信息素初始分配和動(dòng)態(tài)更新的蟻群算法［J］. 計(jì)算機(jī)工程與應(yīng)用， 2022， 58（2）： 95-101. （Chen Yingjie， Gao Maoting. Ant colony algorithm based on pheromone initial distribution and dynamic update［J］. Computer Engineering and Applications， 2022， 58（2）： 95-101.）

［23］Guo Andong， Zhao Chenglin， Xu Fangmin， et al. LEO satellite routing algorithm in software defined space terrestrial integrated network［C］// Proc of the 17th International Symposium on Communications and Information Technologies. 2017： 1-6.

收稿日期：2021-12-21；修回日期：2022-02-17基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目（61931004）

作者簡(jiǎn)介：劉治國(guó)（1974-），男（通信作者），遼寧沈陽人，教授，碩導(dǎo)，博士，主要研究方向?yàn)榫W(wǎng)絡(luò)體系結(jié)構(gòu)、協(xié)議技術(shù)、網(wǎng)絡(luò)管理（liuzhiguo_dldx@163.com）；姚巧雨（1997-），女，河北邢臺(tái)人，碩士研究生，主要研究方向?yàn)槊麛?shù)據(jù)網(wǎng)絡(luò)、軟件定義衛(wèi)星網(wǎng)絡(luò)通信研究；潘成勝（1962-），男，江蘇宜興人，教授，博導(dǎo)，博士，主要研究方向?yàn)樾l(wèi)星網(wǎng)絡(luò)通信研究.