基于預(yù)計(jì)算的軟件定義衛(wèi)星網(wǎng)絡(luò)節(jié)能路由

劉之瑩，王興偉，徐雙，曾榮飛

（東北大學(xué)，遼寧沈陽 110169）

1 引言

作為下一代網(wǎng)絡(luò)不可或缺的一部分[1]，衛(wèi)星網(wǎng)絡(luò)具有快速部署、拓展性好、傳輸信息及時(shí)有效等優(yōu)點(diǎn)。但是，衛(wèi)星網(wǎng)絡(luò)的動(dòng)態(tài)性、封閉性、不靈活、部署成本高等特點(diǎn)導(dǎo)致地面流量分布不均勻，衛(wèi)星處于閑置狀態(tài)時(shí)仍然保持正常運(yùn)作，使得整網(wǎng)能源浪費(fèi)。能源成本持續(xù)上升以及全球溫室氣體大量排放使得節(jié)能成為本世紀(jì)的主要技術(shù)挑戰(zhàn)之一。多項(xiàng)研究報(bào)告表明[2]，互聯(lián)網(wǎng)的功耗已占到全球能源消耗的10%，而且占比還在不斷增加。針對這個(gè)現(xiàn)象，研究人員采取了許多舉措來降低信息和通信技術(shù)（Information and Communication Technology，ICT）行業(yè)的電力消耗。

在日蝕期間時(shí)，衛(wèi)星網(wǎng)絡(luò)由自身攜帶的蓄電池供電。而交換機(jī)節(jié)點(diǎn)（LEO）衛(wèi)星網(wǎng)絡(luò)的部署和維護(hù)成本極高，更換電池是不切實(shí)際的。因此，延長蓄電池的使用壽命對于衛(wèi)星網(wǎng)絡(luò)正常運(yùn)行至關(guān)重要。

軟件定義網(wǎng)絡(luò)（Software Defined Networking,SDN）是由斯坦福大學(xué)Nick McKeown教授提出的一種新型網(wǎng)絡(luò)架構(gòu)[1]。該架構(gòu)通過將控制平面與數(shù)據(jù)平面分離，實(shí)現(xiàn)了網(wǎng)絡(luò)靈活的集中式控制，促進(jìn)了核心網(wǎng)絡(luò)及其相關(guān)應(yīng)用的創(chuàng)新。SDN具有的功能與優(yōu)點(diǎn)可以改善衛(wèi)星之間的協(xié)作和異構(gòu)空間系統(tǒng)的兼容性。因此，本文將SDN技術(shù)引入到衛(wèi)星網(wǎng)絡(luò)中，提出了啟發(fā)式的軟件定義衛(wèi)星網(wǎng)絡(luò)預(yù)計(jì)算節(jié)能路由機(jī)制（Software Defined Satellite Network Precomputation-based Energy-Saving Routing Mechanis，SDSN-PBESRM）為網(wǎng)絡(luò)中任意節(jié)點(diǎn)對尋找最小能耗路徑，同時(shí)降低網(wǎng)絡(luò)能耗、減小平均路徑跳數(shù)。

本文的主要貢獻(xiàn)有三點(diǎn)：

（1） 將SDN思想引入到衛(wèi)星網(wǎng)絡(luò)中，解耦了衛(wèi)星網(wǎng)絡(luò)的控制平面和數(shù)據(jù)平面，構(gòu)建了一種軟件定義衛(wèi)星網(wǎng)絡(luò)雙層架構(gòu)；

（2） 在流量建模中，綜合考慮地面用戶數(shù)量與主機(jī)數(shù)量分布對區(qū)域間業(yè)務(wù)流的影響，提高了衛(wèi)星網(wǎng)絡(luò)節(jié)點(diǎn)間的流量需求預(yù)測結(jié)果的準(zhǔn)確性；

（3） 將星上載荷能耗分為操作系統(tǒng)能耗、輸入/輸出與流表查找能耗、處理器能耗及運(yùn)營與維護(hù)能耗四部分進(jìn)行計(jì)算，以構(gòu)建整網(wǎng)能耗模型。針對此網(wǎng)絡(luò)模型，以降低衛(wèi)星網(wǎng)絡(luò)能耗為目的設(shè)計(jì)了一種基于預(yù)計(jì)算的節(jié)能路由機(jī)制——網(wǎng)絡(luò)休眠機(jī)制，合理關(guān)閉空閑衛(wèi)星網(wǎng)絡(luò)節(jié)點(diǎn)。

2 相關(guān)研究工作

目前，已有的降低能耗方案大多是針對單顆衛(wèi)星而不是整個(gè)星座。Fu等人[3]考慮了單顆衛(wèi)星能量受限的情況，研究了地球軌道通信衛(wèi)星的最佳能量分配和準(zhǔn)入控制問題。Fu首先使用動(dòng)態(tài)規(guī)劃方法，將最優(yōu)策略導(dǎo)出并且以閾值為特征，用于優(yōu)化衛(wèi)星能量分配。隨后提出了有效獲取策略的方法：最優(yōu)方法、無限需求法和確定性等效法。這些方法不僅適用于衛(wèi)星網(wǎng)絡(luò)，也可以解決無線通信中的資源分配問題。Sridhar等人[4]對用于下行鏈路廣播數(shù)據(jù)傳輸?shù)男l(wèi)星架構(gòu)和蜂窩架構(gòu)使用排隊(duì)理論模型進(jìn)行比較分析，結(jié)果表明與蜂窩架構(gòu)相比衛(wèi)星架構(gòu)更加節(jié)能，但是會(huì)有更高的延遲和更低的吞吐量。Hussein等人[5]考慮剩余LEO衛(wèi)星網(wǎng)絡(luò)連通性的能量感知問題，提出了一種新的方法來關(guān)閉一些處于日蝕期的衛(wèi)星鏈路，同時(shí)保持剩余LEO衛(wèi)星網(wǎng)絡(luò)的網(wǎng)絡(luò)連接高于指定連接度。但是，由于該解決方案是基于拓?fù)涓兄?，沒有考慮路徑之間的流量分配，不能更好地區(qū)分不同負(fù)載的衛(wèi)星來達(dá)到有效節(jié)能的效果。

在衛(wèi)星通信中，考慮整個(gè)衛(wèi)星星座可以設(shè)計(jì)更好的方法來減少重疊衛(wèi)星的能耗。針對LEO星座中的節(jié)能優(yōu)化問題，Tang等人[6]闡述了衛(wèi)星網(wǎng)絡(luò)節(jié)能的重要性，考慮到了LEO衛(wèi)星的節(jié)能優(yōu)化，修改和擴(kuò)展了多功能流模型，利用多重覆蓋方案和流量分配設(shè)計(jì)了衛(wèi)星網(wǎng)絡(luò)啟發(fā)式算法，改進(jìn)了整個(gè)衛(wèi)星網(wǎng)絡(luò)的節(jié)能性質(zhì)。Wang等人[7]采用容量區(qū)域演進(jìn)圖來捕獲動(dòng)態(tài)網(wǎng)絡(luò)拓?fù)洌?gòu)建了吞吐量受限的最大生命周期路由問題，將其規(guī)約為耦合多個(gè)時(shí)間間隔（即時(shí)隙）的線性規(guī)劃問題。文章提出了兩種有效的路由算法，即最大生命路由和最短路徑漸進(jìn)路由以減少解決路由問題的執(zhí)行時(shí)間。兩種路由算法都可以獲得較長的網(wǎng)絡(luò)生命周期和均衡的流量分配，同時(shí)保證網(wǎng)絡(luò)吞吐量。

綜上所述，目前網(wǎng)絡(luò)級別降低能耗的方案研究較少。為此，本文以衛(wèi)星網(wǎng)絡(luò)整網(wǎng)節(jié)能為研究目標(biāo)，提出了基于預(yù)計(jì)算的軟件定義衛(wèi)星網(wǎng)絡(luò)節(jié)能路由算法，在更大程度上解決了整體衛(wèi)星網(wǎng)絡(luò)上為任意節(jié)點(diǎn)對尋找最小能耗路徑問題。

3 軟件定義衛(wèi)星網(wǎng)絡(luò)節(jié)能模型設(shè)計(jì)

3.1 系統(tǒng)模型

充分借鑒SDN數(shù)據(jù)平面與控制平面分離、網(wǎng)絡(luò)集中控制的思想，本文提出了一種基于軟件定義衛(wèi)星網(wǎng)絡(luò)的雙層架構(gòu)。該雙層架構(gòu)分為衛(wèi)星段、用戶段與地面段。在衛(wèi)星段中，利用星上控制器節(jié)點(diǎn)（GEO）層作為雙層衛(wèi)星網(wǎng)絡(luò)的控制平面，通過南向接口與交換機(jī)節(jié)點(diǎn)（LEO）通信，通過北向接口與地面控制器節(jié)點(diǎn)（NOCC）通信。用戶段為地面用戶終端，主要功能為接收衛(wèi)星信號，提供用戶所需位置和時(shí)間等信息，利用LEO衛(wèi)星覆蓋地面中心站實(shí)現(xiàn)衛(wèi)星段與用戶段之間的通信。在地面段中，利用NOCC作為整個(gè)架構(gòu)的控制中心，NOCC執(zhí)行休眠算法、路徑計(jì)算、快照切換，從而將計(jì)算的結(jié)果發(fā)送給GEO衛(wèi)星，由星上控制器管理星上交換機(jī)節(jié)點(diǎn)，軟件定義衛(wèi)星網(wǎng)絡(luò)雙層架構(gòu)如圖1所示。

圖1 軟件定義網(wǎng)絡(luò)雙層架構(gòu)

星間鏈路（Inter Satellite Links，ISL）是用于衛(wèi)星之間通信的鏈路，分為層間與層內(nèi)鏈路。每顆LEO衛(wèi)星有4條層內(nèi)ISL：同軌之間南北鏈路是持續(xù)的，軌間東西鏈路是動(dòng)態(tài)的。極軌道星座中存在兩個(gè)相鄰的軌道，這兩個(gè)軌道上的衛(wèi)星運(yùn)動(dòng)方向相反，他們形成的軌間鏈路稱為反向縫鏈路（Cross-seam Link），如圖2所示。

圖2 反向縫鏈路

用戶數(shù)據(jù)鏈路（User Data Link，UDL）用于衛(wèi)星與地面接收站之間的通信，又稱星地鏈路，包含上行鏈路與下行鏈路，上行鏈路為地面站發(fā)送消息給衛(wèi)星，下行鏈路為衛(wèi)星發(fā)送消息給地面站，如圖3所示。本文選擇最短距離覆蓋算法為地面計(jì)算接入衛(wèi)星。當(dāng)?shù)孛娈a(chǎn)生流量請求，將會(huì)發(fā)送到中心地面站，由地面站發(fā)起對衛(wèi)星的呼叫。根據(jù)信號平均功率的強(qiáng)度，首先在距離地面站最近的衛(wèi)星中尋找空閑信道，有則建立UDL進(jìn)行衛(wèi)星與地面站之間的通信，否則尋找其他覆蓋衛(wèi)星中距離最近的一個(gè)，進(jìn)行如上操作。當(dāng)所有覆蓋當(dāng)前地面站的衛(wèi)星均無空閑信道時(shí)，此地面站的請求則會(huì)處于等待狀態(tài)。隨著衛(wèi)星相對地面站的移動(dòng)，衛(wèi)星將會(huì)移動(dòng)到距離地面站較遠(yuǎn)的位置，此時(shí)會(huì)有新的衛(wèi)星為地面站提供接入服務(wù)，這稱為衛(wèi)星切換（Satellite Handover）。

圖3 用戶數(shù)據(jù)鏈路

3.2 流量模型

假設(shè)一個(gè)快照內(nèi)不發(fā)生衛(wèi)星接入切換，計(jì)算出單個(gè)衛(wèi)星節(jié)點(diǎn)i在一個(gè)快照內(nèi)的流量需求，計(jì)算式如下。

其中，zonek表示地面區(qū)域k的流量，coveri表示節(jié)點(diǎn)i覆蓋區(qū)域內(nèi)地面區(qū)域的集合。

兩個(gè)節(jié)點(diǎn)間的流量需求與節(jié)點(diǎn)流量相關(guān)，此外，地面主機(jī)數(shù)量與節(jié)點(diǎn)間的距離也會(huì)影響兩個(gè)節(jié)點(diǎn)的流量需求。主機(jī)數(shù)量計(jì)算如公式（2）所示：

其中，hj表示節(jié)點(diǎn)j覆蓋區(qū)域內(nèi)的主機(jī)數(shù)量，表示節(jié)點(diǎn)j的流量需求，表示p大洲上的所有區(qū)域用戶數(shù)量之和，Nh(p)表示p大洲上的主機(jī)個(gè)數(shù)。

兩衛(wèi)星節(jié)點(diǎn)間的流量需求如下：

其中，ts表示節(jié)點(diǎn)s的用戶流量需求，hd表示節(jié)點(diǎn)d覆蓋區(qū)域內(nèi)的主機(jī)數(shù)量，dis(s,d)表示節(jié)點(diǎn)s，d間的距離，α=0.5，β=1.5[8]。

3.3 能耗模型

本文將衛(wèi)星節(jié)點(diǎn)的能耗分為四部分，包括操作系統(tǒng)能耗、輸入/輸出與流表查找能耗、處理器能耗[9]及運(yùn)營與維護(hù)能耗。節(jié)點(diǎn)能耗計(jì)算式如（4）所示。

其中，PNi表示節(jié)點(diǎn)i的能耗，表示操作系統(tǒng)能耗，是一個(gè)與流量無關(guān)的常數(shù)，即在衛(wèi)星不處理流量時(shí)也會(huì)產(chǎn)生能耗；?iTi表示輸入/輸出與流表查找的能耗，?i為常量，Ti表示流經(jīng)節(jié)點(diǎn)i的流量；表示處理器的能耗，μi、αi為由處理器本身決定的常量；表示節(jié)點(diǎn)運(yùn)營與維護(hù)所消耗的能量，θi的取值如式（5）所示。

衛(wèi)星節(jié)點(diǎn)運(yùn)營與維護(hù)能耗是由于節(jié)點(diǎn)在日蝕期間不能接受光照造成的抵抗外界嚴(yán)寒和硬件維護(hù)而產(chǎn)生的。

定義1. 放電深度（Depth of Discharge，DOD）

表示電池放電量與電池額定容量的百分比，計(jì)算如式（6）所示。

其中，DODi表示節(jié)點(diǎn)i的放電深度，Pit表示電池放電量，Ci表示電池容量。

LEO層的每顆LEO衛(wèi)星有四條層內(nèi)ISL，ISL的能耗與鏈路上流經(jīng)的流量數(shù)目有關(guān)，計(jì)算式如（7）所示。

UDL鏈路中的上下行鏈路能耗也是星上負(fù)載能耗的一大部分，與星地鏈路上的流量有關(guān)，其計(jì)算式如（8）所示。

3.4 節(jié)能問題建模

結(jié)合本文的系統(tǒng)架構(gòu)、流量模型、能耗模型，構(gòu)建網(wǎng)絡(luò)能耗模型如式（9）所示。

其中，

Ptotal表示LEO層網(wǎng)絡(luò)的總能耗，包括ISL星間鏈路的能耗、UDL用戶數(shù)據(jù)鏈路的能耗和衛(wèi)星節(jié)點(diǎn)的能耗，Nsat表示衛(wèi)星節(jié)點(diǎn)的個(gè)數(shù)。

以最小化LEO衛(wèi)星網(wǎng)絡(luò)總能耗為目標(biāo)構(gòu)建衛(wèi)星網(wǎng)絡(luò)能耗問題模型如下：

式（14）為流量守恒約束；式（15）表示流經(jīng)(i，j)鏈路上的全部流量，且鏈路的最大負(fù)載為；式（16）表示流經(jīng)節(jié)點(diǎn)i的所有UDL的總流量，且鏈路的最大負(fù)載為；式（17）表示只有當(dāng)節(jié)點(diǎn)i的所有鏈路都關(guān)閉時(shí)，該節(jié)點(diǎn)才能夠關(guān)閉；式（18）表示節(jié)點(diǎn)i的DOD小于上限K；式（19）表示當(dāng)且僅當(dāng)節(jié)點(diǎn)與其他節(jié)點(diǎn)間的所有鏈路均關(guān)閉時(shí)，該節(jié)點(diǎn)才能關(guān)閉[10]。

分析以上能耗模型，本文的最小化網(wǎng)絡(luò)總能耗問題屬于CMCF[11]問題，即多個(gè)商品必須在具有容量限制的圖中路由的問題。已知CMCF問題是NP hard的，因此本文提出啟發(fā)式算法來解決該問題。在骨干網(wǎng)中[12]，假設(shè)PN=1和PL<

4 基于預(yù)計(jì)算的節(jié)能路由算法

為解決軟件定義衛(wèi)星網(wǎng)絡(luò)中的節(jié)能問題，本文設(shè)計(jì)了啟發(fā)式的預(yù)計(jì)算節(jié)能路由機(jī)制。首先，將衛(wèi)星網(wǎng)絡(luò)動(dòng)態(tài)拓?fù)潆x散化為一系列網(wǎng)絡(luò)快照拓?fù)鋱D。然后，分析網(wǎng)絡(luò)與流量模型，設(shè)計(jì)了網(wǎng)絡(luò)休眠算法（Network Sleep Algorithm，NSA）來尋找網(wǎng)絡(luò)拓?fù)鋱D中滿足設(shè)計(jì)需求的網(wǎng)絡(luò)子集。最后，設(shè)計(jì)了基于預(yù)計(jì)算的節(jié)能路由算法（Precomputing Based Routing Algorithm，PBRA）為網(wǎng)絡(luò)子集中所有節(jié)點(diǎn)對計(jì)算最小能耗路徑。

4.1 動(dòng)態(tài)拓?fù)涮幚?/h3>

鑒于衛(wèi)星網(wǎng)絡(luò)拓?fù)鋭?dòng)態(tài)變化的特點(diǎn)，首先將網(wǎng)絡(luò)拓?fù)潆x散化為一系列靜態(tài)拓?fù)淇煺?，在每個(gè)快照內(nèi)進(jìn)行路由計(jì)算，以簡化衛(wèi)星網(wǎng)絡(luò)路由的復(fù)雜性。當(dāng)ISL建立或斷開時(shí)，網(wǎng)絡(luò)中產(chǎn)生一張新的拓?fù)淇煺誟13]，并進(jìn)行快照切換。本文將ISL變化作為切換點(diǎn)，將衛(wèi)星網(wǎng)絡(luò)每個(gè)周期內(nèi)的動(dòng)態(tài)拓?fù)浞稚⒒梢幌盗械撵o態(tài)拓?fù)?。網(wǎng)絡(luò)拓?fù)湫蛄谢?，網(wǎng)絡(luò)將由一系列快照（G1,G2,...,Gn）表示，其中Gi表示第i張快照內(nèi)的網(wǎng)絡(luò)拓?fù)鋱D。每張網(wǎng)絡(luò)拓?fù)鋱D由衛(wèi)星節(jié)點(diǎn)、ISL、UDL組成，表示為Gi(V、EISL、EUDL)。

4.2 網(wǎng)絡(luò)休眠算法

在得到網(wǎng)絡(luò)拓?fù)鋱DG(V、EISL、EUDL)后，為了達(dá)到網(wǎng)絡(luò)節(jié)能的目的，本節(jié)設(shè)計(jì)了網(wǎng)絡(luò)休眠算法，將部分衛(wèi)星節(jié)點(diǎn)以及鏈路休眠來得到網(wǎng)絡(luò)子集。

根據(jù)第3.1節(jié)中介紹的衛(wèi)星接入模型，地面站根據(jù)最短距離覆蓋的原則選擇衛(wèi)星建立UDL，并發(fā)送流量請求。根據(jù)第3.2節(jié)的流量模型，首先計(jì)算地面區(qū)域的流量請求，關(guān)閉沒有流量請求的地面區(qū)域與其接入衛(wèi)星之間的UDL。然后，根據(jù)式（1）計(jì)算衛(wèi)星節(jié)點(diǎn)流量，關(guān)閉流量請求為0的衛(wèi)星及其相鄰的ISL。為保證每次關(guān)閉節(jié)點(diǎn)及鏈路后剩余節(jié)點(diǎn)和鏈路可以完成網(wǎng)絡(luò)的數(shù)據(jù)轉(zhuǎn)發(fā)任務(wù)，在每一次快照切換時(shí)NOCC都會(huì)對節(jié)點(diǎn)進(jìn)行全覆蓋檢查，計(jì)算節(jié)點(diǎn)和鏈路上的流量，并進(jìn)行休眠處理。

在每次快照切換之后，首先運(yùn)行網(wǎng)絡(luò)休眠算法，得到網(wǎng)絡(luò)的子集G’(V’、E’ISL、E’UDL)，NOCC將要關(guān)閉的節(jié)點(diǎn)及鏈路信息發(fā)送給主GEO衛(wèi)星，主GEO衛(wèi)星根據(jù)各個(gè)GEO衛(wèi)星的覆蓋范圍，將要發(fā)送給所屬的LEO衛(wèi)星的流表發(fā)送到對應(yīng)GEO衛(wèi)星上，各個(gè)GEO衛(wèi)星發(fā)送給要關(guān)閉的LEO節(jié)點(diǎn)使其執(zhí)行關(guān)閉節(jié)點(diǎn)/UDL/ISL操作。在上一個(gè)快照中處于休眠狀態(tài)的節(jié)點(diǎn)若在本次快照切換之后沒有收到休眠指令，將會(huì)切換到開啟狀態(tài)，并根據(jù)網(wǎng)絡(luò)拓?fù)鋱D G(V、EISL、EUDL)建立與鄰居節(jié)點(diǎn)之間的ISL以及地面站之間的UDL。由于在衛(wèi)星網(wǎng)絡(luò)中喚醒一個(gè)節(jié)點(diǎn)/鏈路的能耗比衛(wèi)星不處理流量的能耗小很多，因此在本文不考慮喚醒網(wǎng)絡(luò)中休眠的節(jié)點(diǎn)以及鏈路的重新建立的能耗。

4.3 基于預(yù)計(jì)算衛(wèi)星網(wǎng)絡(luò)節(jié)能路由算法

在網(wǎng)絡(luò)休眠算法得到的網(wǎng)絡(luò)子圖G’(V’、E’ISL、E’UDL)中，首先為節(jié)點(diǎn)對尋找多條最短跳數(shù)路徑，然后計(jì)算每條路徑上的總能耗，選擇出能耗最小的一條路徑。在NOCC得到全網(wǎng)拓?fù)湫畔⒅螅谛l(wèi)星運(yùn)行前進(jìn)行路由預(yù)計(jì)算，并將預(yù)先得到的節(jié)點(diǎn)對間的最短ISL路徑長度設(shè)置為跳數(shù)，以此作為路徑選擇標(biāo)準(zhǔn)。由于極軌道LEO衛(wèi)星網(wǎng)絡(luò)類似曼哈頓網(wǎng)絡(luò)，因此兩節(jié)點(diǎn)間的最短路徑跳數(shù)即為以兩節(jié)點(diǎn)為對角線的矩形的長寬之和，如圖4所示。圖4中的S表示源節(jié)點(diǎn)，D表示目的節(jié)點(diǎn)，S，D之間有若干條最短跳數(shù)路徑，圖中給出一條示例路徑。

如果源節(jié)點(diǎn)與目的節(jié)點(diǎn)不能組成一個(gè)矩形，則包含兩種情況：

圖4 源/目的節(jié)點(diǎn)傳輸路徑

（1）兩個(gè)節(jié)點(diǎn)處于同一軌道上；

（2）兩個(gè)節(jié)點(diǎn)處于同一橫向圈中。

當(dāng)兩個(gè)節(jié)點(diǎn)的位置是以上兩種情況時(shí)，源節(jié)點(diǎn)與目的節(jié)點(diǎn)之間的最小跳數(shù)路徑就是兩個(gè)節(jié)點(diǎn)的直線距離，示例路徑如圖5所示。

根據(jù)上述分析，提出預(yù)計(jì)算算法，其偽代碼如算法1所示。

圖5 縱向/橫向源/目的節(jié)點(diǎn)傳輸路

算法1 預(yù)計(jì)算算法

BEGIN

2）設(shè)置集合S1記錄節(jié)點(diǎn)集合；

3）設(shè)置集合S2記錄已經(jīng)做過源節(jié)點(diǎn)的節(jié)點(diǎn)；

4）設(shè)置 記錄節(jié)點(diǎn)對之間多條最短路徑；

5）FOR源節(jié)點(diǎn)sS1；

6）將s放入集合S2中并從S1中刪除，并將其作為當(dāng)前節(jié)點(diǎn)；

7） FOR節(jié)點(diǎn)d S1；

8） IF 當(dāng)前節(jié)點(diǎn)與節(jié)點(diǎn)d位于同一軌道上；

9） 計(jì)算當(dāng)前節(jié)點(diǎn)與節(jié)點(diǎn)d在該軌道上順時(shí)針/逆時(shí)針方向的兩條路徑的跳數(shù)；

10）記錄跳數(shù)小的路徑；

11）ELSEIF 當(dāng)前節(jié)點(diǎn)與節(jié)點(diǎn)d位于同一橫向圈上 ；

12）記錄當(dāng)前節(jié)點(diǎn)與節(jié)點(diǎn)d在橫向圈上的直線連線的路徑；

13）ELSE；

14）查找當(dāng)前節(jié)點(diǎn)的鄰居節(jié)點(diǎn)，并將所有的鄰居節(jié)點(diǎn)作為后繼節(jié)點(diǎn)；

15）將當(dāng)前節(jié)點(diǎn)、后繼節(jié)點(diǎn)記錄為路徑的一部分；

16）將后繼節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)，重復(fù)步驟5～16直到找到節(jié)點(diǎn)d；

17）記錄s，d之間的所有路徑；

18）END IF；

20）END FOR；

21）END FOR；

22）RETURN。

END

在完成預(yù)計(jì)算，得到網(wǎng)絡(luò)中任意節(jié)點(diǎn)對之間的多條最短路徑集合Setall后，計(jì)算源/目的節(jié)點(diǎn)對之間所有路徑上的能量消耗，選出每個(gè)節(jié)點(diǎn)對間能耗最小的一條路徑。路徑能耗計(jì)算中鏈路的權(quán)重為：

其中，weightij表示鏈路（i，j）權(quán)重，PNi為節(jié)點(diǎn)i的能耗，表示節(jié)點(diǎn)i與節(jié)點(diǎn)j之間ISL鏈路上的能耗。

綜上所述，本文所提出的基于預(yù)計(jì)算的節(jié)能路由算法偽代碼如算法2所示。

算法2 基于預(yù)計(jì)算的節(jié)能路由算法

輸入：流量模型、節(jié)點(diǎn)多路徑集；

BEGIN

1）根據(jù)流量模型通過公式(1)計(jì)算節(jié)點(diǎn)流量；

2）通過公式(3)計(jì)算源/目的節(jié)點(diǎn)的流量需求；

4）FOR 中的路徑；

5） FOR 每個(gè)節(jié)點(diǎn)對 ；

6）根據(jù)式(20)計(jì)算鏈路權(quán)重；

7）計(jì)算節(jié)點(diǎn)對 的所有路徑的能耗；

9）END FOR；

10）END FOR；

11）RETURN。

END

該算法的時(shí)間復(fù)雜度為O(N2)，優(yōu)于GreenSR-B算法的時(shí)間復(fù)雜度 O(N3)。

5 實(shí)驗(yàn)與性能評價(jià)

本文利用STK模擬衛(wèi)星的運(yùn)動(dòng)，并導(dǎo)出衛(wèi)星軌跡數(shù)據(jù)、衛(wèi)星日蝕數(shù)據(jù)和星間可見性數(shù)據(jù)，作為輸入在MyEclipse中對本文提出的節(jié)能機(jī)制進(jìn)行了仿真實(shí)現(xiàn)。選用GreenSR-B算法[12]與基于快照的節(jié)能路由算法[14]（Energy Snapshot Routing Algorithm，ESRA）作為基準(zhǔn)算法評估本文所提算法性能。該算法將鏈路的能耗作為鏈路成本，以計(jì)算最小化充電/放電周期數(shù)的路由。

5.1 拓?fù)浣Y(jié)構(gòu)

本文設(shè)計(jì)的衛(wèi)星網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)包含GEO層和LEO層衛(wèi)星網(wǎng)絡(luò)。GEO層有3顆衛(wèi)星，且邏輯位置不會(huì)改變。LEO層網(wǎng)絡(luò)結(jié)構(gòu)包含66顆衛(wèi)星，由于衛(wèi)星相對于地面的高速運(yùn)轉(zhuǎn)，LEO層衛(wèi)星的邏輯位置一直在變化，衛(wèi)星在太空中的運(yùn)動(dòng)狀態(tài)用衛(wèi)星軌道參數(shù)來刻畫，該參數(shù)可以描述在太空中運(yùn)行的坐標(biāo)、形狀和方向的各種參數(shù)。LEO層衛(wèi)星星座包含66顆低軌道衛(wèi)星，衛(wèi)星高度約為780km，均勻分布在6個(gè)近極點(diǎn)軌道上，軌道傾角為86°，軌道偏心率為0。同向旋轉(zhuǎn)軌道面相隔31.6°，反向旋轉(zhuǎn)軌道面相隔22°，每個(gè)軌道平面上有11顆衛(wèi)星。LEO衛(wèi)星網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)3D和2D視圖分別如圖6和7所示。

5.2 評價(jià)指標(biāo)

圖6 3D視圖

圖7 2D視圖

（1） 關(guān)閉量

本節(jié)將從UDL關(guān)閉比例、節(jié)點(diǎn)關(guān)閉數(shù)量、ISL關(guān)閉數(shù)量三個(gè)方面進(jìn)行性能分析。UDL關(guān)閉比例是指UDL關(guān)閉的數(shù)量與UDL總數(shù)的比值，如式（21）所示UDL建立比例是指UDL建立的數(shù)量與UDL總數(shù)的比值，如式（22）所示。

其中，UDLClosePercent為UDL關(guān)閉比例，U D L N u m b e rClose為U D L關(guān)閉的數(shù)量，UDLNumberTotal為UDL的總數(shù)，UDLConnPercent為UDL建立比例，UDLNumberConn為UDL建立的數(shù)量。

節(jié)點(diǎn)關(guān)閉數(shù)量（SatCloseNumber）是指每個(gè)快照中關(guān)閉的衛(wèi)星節(jié)點(diǎn)個(gè)數(shù)。ISL關(guān)閉數(shù)量（ISLCloseNumber）是指每個(gè)快照中可以關(guān)閉的ISL的數(shù)量。

（2） 休眠時(shí)間

休眠時(shí)間（SatDormancyTime）是指在一定時(shí)間內(nèi)衛(wèi)星節(jié)點(diǎn)的休眠時(shí)間。假設(shè)衛(wèi)星只在快照切換時(shí)刻進(jìn)行流表更新，因此節(jié)點(diǎn)的狀態(tài)在一個(gè)快照內(nèi)不會(huì)變化，即在一個(gè)快照內(nèi)每顆衛(wèi)星均維持開啟/休眠狀態(tài)。為了觀察每個(gè)衛(wèi)星的休眠時(shí)間，選擇衛(wèi)星運(yùn)行的一段時(shí)間，計(jì)算每顆衛(wèi)星的累計(jì)休眠時(shí)間。

（3） 網(wǎng)絡(luò)能耗

網(wǎng)絡(luò)能耗[15]是指一個(gè)快照內(nèi)所有組件的能耗，包括節(jié)點(diǎn)的能耗、ISL能耗、UDL能耗，計(jì)算式如（23）所示。

（4） 平均路徑跳數(shù)

平均路徑跳數(shù)[16]是一個(gè)快照內(nèi)所有節(jié)點(diǎn)對之間的路徑跳數(shù)的平均值，計(jì)算式如（24）所示。

其中，countavg表示網(wǎng)絡(luò)中所有節(jié)點(diǎn)對之間的平均路徑跳數(shù)，countsd表示源節(jié)點(diǎn)s目的節(jié)點(diǎn)d之間的路徑跳數(shù)，表示網(wǎng)絡(luò)中所有節(jié)點(diǎn)對之間的路徑跳數(shù)，PathTotal表示網(wǎng)絡(luò)中路徑的總跳數(shù)。

5.3 節(jié)能路由算法性能評價(jià)

（1） 關(guān)閉量

圖8中給出了UDL建立與關(guān)閉的比例，UDL建立的比例比UDL關(guān)閉的比例大。這是因?yàn)榈孛鎱^(qū)域的流量決定星上流量，根據(jù)第4.2節(jié)網(wǎng)絡(luò)休眠算法，將沒有流量需求的地面網(wǎng)關(guān)與衛(wèi)星之間的UDL關(guān)閉，星上拓?fù)潆S時(shí)間的變化而一直變化，地面區(qū)域的流量需求與衛(wèi)星拓?fù)涞淖兓療o關(guān)，因此UDL的關(guān)閉比例是不會(huì)隨時(shí)間變化而變化的。

圖8 UDL關(guān)閉比例

圖9 節(jié)點(diǎn)關(guān)閉數(shù)量

為了觀察節(jié)點(diǎn)關(guān)閉數(shù)量的變化，選取24個(gè)快照采用網(wǎng)絡(luò)休眠算法計(jì)算衛(wèi)星節(jié)點(diǎn)的關(guān)閉數(shù)量。圖9給出了節(jié)點(diǎn)關(guān)閉數(shù)量在不同網(wǎng)絡(luò)快照內(nèi)的分布情況。從圖中可以看出每個(gè)網(wǎng)絡(luò)快照中衛(wèi)星節(jié)點(diǎn)的關(guān)閉數(shù)量分布各不相同，差距很大，這是節(jié)點(diǎn)移動(dòng)造成衛(wèi)星接入的地面區(qū)域不同。當(dāng)流量不為0的地面區(qū)域接入同一顆衛(wèi)星時(shí)，可以關(guān)閉的衛(wèi)星節(jié)點(diǎn)就會(huì)增多。當(dāng)流量不為0的地面區(qū)域接入不同的衛(wèi)星時(shí)，就需要多顆衛(wèi)星為地面提供服務(wù)，可以關(guān)閉的節(jié)點(diǎn)就會(huì)減少。

圖10 ISL關(guān)閉數(shù)量

與節(jié)點(diǎn)關(guān)閉數(shù)量一樣，為了觀察ISL關(guān)閉數(shù)量在不同快照內(nèi)的變化，選擇24個(gè)快照進(jìn)行數(shù)據(jù)分析。圖10給出了ISL關(guān)閉數(shù)量隨時(shí)間變化的分布情況。從圖10中可以看出，不同快照內(nèi)的ISL關(guān)閉數(shù)量有所差異，這是因?yàn)椴煌l(wèi)星節(jié)點(diǎn)的關(guān)閉數(shù)量不同，導(dǎo)致衛(wèi)星之間的ISL有所不同，其次本文采用的是極軌道星座，有反向縫鏈路，當(dāng)休眠的節(jié)點(diǎn)位于首/尾軌道上時(shí)，節(jié)點(diǎn)與其鄰居節(jié)點(diǎn)之間的ISL有3條；當(dāng)休眠的節(jié)點(diǎn)位于其他軌道上時(shí)，節(jié)點(diǎn)與其鄰居節(jié)點(diǎn)之間的ISL有4條；當(dāng)節(jié)點(diǎn)位于極地地區(qū)時(shí)，軌間鏈路斷開，軌內(nèi)鏈路仍處于建立狀態(tài)，因此節(jié)點(diǎn)的位置不同，緯度不同，會(huì)導(dǎo)致ISL關(guān)閉的數(shù)量有差異。

（2） 休眠時(shí)間

圖11給出了一段時(shí)間內(nèi)每個(gè)節(jié)點(diǎn)的休眠時(shí)間。從圖11中可以看出，各個(gè)節(jié)點(diǎn)的休眠時(shí)間不同，這是因?yàn)榈孛鎱^(qū)域流量不同的原因，本文的衛(wèi)星星座從南向北運(yùn)行，覆蓋某些精度范圍的衛(wèi)星會(huì)在一定時(shí)間內(nèi)不變導(dǎo)致衛(wèi)星的開啟或休眠狀態(tài)在一定時(shí)間內(nèi)是不變的，因此各個(gè)衛(wèi)星得到的累積結(jié)果相差較大。

（3） 網(wǎng)絡(luò)能耗

圖11 各個(gè)節(jié)點(diǎn)的休眠時(shí)間

圖12 為三種路由算法的網(wǎng)絡(luò)能耗隨快照序列變化情況。從中可以明顯看出，三種算法的能耗從一開始相當(dāng)，隨時(shí)間變化，GREEN算法的能耗逐漸高于其他兩個(gè)算法算法，這是由于GREEN算法在計(jì)算鏈路時(shí)選擇鏈路能耗作為權(quán)重，但是鏈路連接的節(jié)點(diǎn)能耗比其他路徑的高從而導(dǎo)致網(wǎng)絡(luò)能耗增高。PBR算法的能耗小于GREEN大于ESR，這是因?yàn)殡m然PBR計(jì)算出最短路徑，但是不一定是能耗最小的路徑，但是可以從圖中看到，PBR的能耗是逼近ESR的，因此PBR的誤差也是在可接受范圍內(nèi)。

（4） 平均路徑跳數(shù)

圖12 網(wǎng)絡(luò)能耗

圖13 為三種路由算法的平均路徑跳數(shù)分布。從圖13中可以看出，不同快照內(nèi)的平均路徑條數(shù)均不同，這是因?yàn)镮SL的建立與斷開導(dǎo)致節(jié)點(diǎn)對之間的路徑變化。在每個(gè)快照中，ESR算法的平均路徑跳數(shù)最大，因?yàn)镋SR算法的計(jì)算路徑的鏈路權(quán)重是節(jié)點(diǎn)能耗與鏈路能耗的加和，選擇能耗最短路徑，其中的有些路徑并不是跳數(shù)最短的路徑。GREEN的路徑長度其次，因?yàn)镚REEN路由算法計(jì)算路徑的鏈路權(quán)重是鏈路能耗，當(dāng)遇到流量集中的一些鏈路時(shí)，會(huì)選擇繞過這些鏈路，從而造成跳數(shù)增加。PBR的平均路徑跳數(shù)最小，因?yàn)镻BR算法是基于最短跳數(shù)的節(jié)能路由算法，它的平均路徑跳數(shù)最短，帶寬利用率也是最高的。

6 結(jié)束語

圖13 平均路徑跳數(shù)

針對衛(wèi)星網(wǎng)絡(luò)中的節(jié)能問題，本文將SDN的思想與衛(wèi)星網(wǎng)絡(luò)體系相結(jié)合，設(shè)計(jì)了一種基于預(yù)計(jì)算的節(jié)能路由機(jī)制。該節(jié)能路由機(jī)制綜合考慮到了路徑能耗與路徑跳數(shù)因素對路由計(jì)算的影響，使得該機(jī)制與基于快照的節(jié)能機(jī)制相比，達(dá)到減少5.51%的平均路徑跳數(shù)的效果。同時(shí)，帶寬利用率增高，使得該機(jī)制與傳統(tǒng)GreenSR-B機(jī)制相比，降低了0.13%的網(wǎng)絡(luò)能耗。但是，本文沒有考慮到拓?fù)浜凸?jié)點(diǎn)/鏈路故障這種特殊情況對系統(tǒng)的影響。因此，考慮網(wǎng)絡(luò)拓?fù)浜凸?jié)點(diǎn)/鏈路故障等不可預(yù)測的變化會(huì)是下一步工作的重點(diǎn)。