基于預(yù)案匹配的衛(wèi)星互聯(lián)網(wǎng)資源動(dòng)態(tài)分配研究

王洪良，丁 暉，趙維晨，王 萌，馬樹森，張京平

（1.96946部隊(duì)，北京 100085；2.中國衛(wèi)通集團(tuán)股份有限公司，北京 100190；3. 凱睿星通信息科技（南京）股份有限公司，江蘇 南京 210012）

0 引言

隨著2021年4月23日，搭載4名宇航員的SpaceX公司的載人龍飛船由“獵鷹9號”火箭從佛羅里達(dá)肯尼迪航天發(fā)射中心發(fā)射升空，馬斯克的星鏈（Starlink）衛(wèi)星互聯(lián)網(wǎng)項(xiàng)目再次受到強(qiáng)烈關(guān)注，而星鏈項(xiàng)目早已在2020年底開放公測，短短幾個(gè)月時(shí)間參與的用戶數(shù)量就超過了1萬人[1]。SpaceX公司旨在通過星鏈項(xiàng)目打造一個(gè)由數(shù)千顆衛(wèi)星組成的互聯(lián)網(wǎng)絡(luò)，這種衛(wèi)星互聯(lián)網(wǎng)能夠向地球上任何地方的終端用戶提供高速互聯(lián)網(wǎng)服務(wù)。星鏈項(xiàng)目一系列成功運(yùn)營表明，全球衛(wèi)星互聯(lián)網(wǎng)的時(shí)代已經(jīng)開啟。衛(wèi)星互聯(lián)網(wǎng)的全球覆蓋、全天候、便攜、移動(dòng)、寬帶通信可以滿足地面用戶接入互聯(lián)網(wǎng)的需求[2]；同時(shí)，在互聯(lián)網(wǎng)的迅速發(fā)展下，衛(wèi)星互聯(lián)網(wǎng)的終端用戶會(huì)成幾何倍速增長，截止到2021年4月，全球互聯(lián)網(wǎng)用戶數(shù)量已經(jīng)達(dá)到約47億，占全球人口數(shù)量的60%，而且互聯(lián)網(wǎng)用戶數(shù)量還在快速增長[3]。基于以上兩個(gè)現(xiàn)狀，未來的衛(wèi)星互聯(lián)網(wǎng)就會(huì)遇到新的問題，即面對海量用戶，衛(wèi)星通信資源申請流程的繁瑣和資源分配的不穩(wěn)定性也成為影響衛(wèi)星互聯(lián)網(wǎng)通信速率的問題。

針對這個(gè)問題，需要研究基于預(yù)案匹配的衛(wèi)星互聯(lián)網(wǎng)絡(luò)資源動(dòng)態(tài)分配技術(shù)。目前提出的設(shè)計(jì)方案很多，主要的設(shè)計(jì)思想有兩點(diǎn)：一是如何簡化衛(wèi)星互聯(lián)網(wǎng)通信資源申請流程[4]？二是如何獲得衛(wèi)星互聯(lián)網(wǎng)通信資源分配的最優(yōu)化方式[5]？本文研究的重點(diǎn)在于首先實(shí)現(xiàn)基于預(yù)案匹配的衛(wèi)星互聯(lián)網(wǎng)通信資源申請流程，然后進(jìn)一步研究基于多參數(shù)遺傳算法的衛(wèi)星互聯(lián)網(wǎng)通信資源分配的最優(yōu)化算法。圖1為衛(wèi)星互聯(lián)網(wǎng)資源分配示意圖。

圖1 衛(wèi)星互聯(lián)網(wǎng)資源分配示意圖

1 基于預(yù)案匹配的衛(wèi)星互聯(lián)網(wǎng)絡(luò)資源申請流程

衛(wèi)星互聯(lián)網(wǎng)具有地面互聯(lián)網(wǎng)不具備的特點(diǎn)，比如高延遲性、移動(dòng)性、星間鏈路通斷、不同選星鏈路距離差異等，這些特點(diǎn)在海量用戶同時(shí)申請時(shí)，帶來的關(guān)鍵網(wǎng)關(guān)節(jié)點(diǎn)大量擁塞，極大降低了鏈路的利用率[6]。

基于預(yù)案匹配的衛(wèi)星互聯(lián)網(wǎng)絡(luò)資源申請流程，將衛(wèi)星互聯(lián)網(wǎng)關(guān)鍵節(jié)點(diǎn)的資源頻段通過預(yù)案的方式分成多段，網(wǎng)管系統(tǒng)可以通過用戶申請任務(wù)的信息計(jì)算出所需最優(yōu)帶寬，幫助衛(wèi)星通信系統(tǒng)節(jié)約了帶寬資源，提高了鏈路利用率，并且通過申請的時(shí)間和帶寬信息在可用的預(yù)案中進(jìn)行匹配，通過用戶填寫的任務(wù)信息和歷史任務(wù)的評分為用戶動(dòng)態(tài)匹配出最優(yōu)預(yù)案，幫助用戶節(jié)約選擇資源的時(shí)間，簡化了任務(wù)申請的流程，還可以避免資源碰撞，提高資源穩(wěn)定性，并且用戶可以對任務(wù)設(shè)置等級。當(dāng)空閑資源不足時(shí)，用戶可以手動(dòng)暫停或者回收等級較低的任務(wù)，這樣就可以預(yù)留出充足的帶寬資源，以保證當(dāng)前任務(wù)的執(zhí)行。用戶如果在任務(wù)執(zhí)行的時(shí)間內(nèi)不能完成任務(wù)，還可以提交延長任務(wù)時(shí)間的申請，審核單位通過申請后，即可繼續(xù)執(zhí)行任務(wù)，為任務(wù)的順利完成提供充足的保障，該方法還提供了任務(wù)撤回功能，用戶如果超前完成任務(wù)，可以使用該功能完成任務(wù)，提前回收資源，為后續(xù)任務(wù)的執(zhí)行提供支持。其流程如圖2所示。

圖2 基于預(yù)案匹配的衛(wèi)星互聯(lián)網(wǎng)絡(luò)資源申請流程圖

填寫申請使用資源的基本信息主要包括：任務(wù)名稱、任務(wù)類型、任務(wù)等級、開始時(shí)間、結(jié)束時(shí)間、所屬網(wǎng)系等。用戶填寫的開始時(shí)間不能早于當(dāng)前時(shí)間，用戶所填基本信息會(huì)作為最優(yōu)資源匹配的參數(shù)；選擇參與任務(wù)的單位以及參與設(shè)備相關(guān)信息，用戶所填的相關(guān)設(shè)備信息會(huì)作為最優(yōu)資源匹配的參數(shù)；選擇參與人員信息，用戶所填的人員信息會(huì)作為最優(yōu)資源匹配的參數(shù)；在地圖中圈出任務(wù)執(zhí)行區(qū)域，通過算法獲取任務(wù)執(zhí)行區(qū)域的經(jīng)緯度和面積。根據(jù)業(yè)務(wù)需求可以選擇填寫申請帶寬，用戶也可選擇關(guān)聯(lián)各個(gè)單位之間的鏈路關(guān)系，不選擇系統(tǒng)會(huì)根據(jù)任務(wù)信息自動(dòng)計(jì)算帶寬，TDMA通信體制任務(wù)帶寬為通聯(lián)關(guān)系總和加1 M，F(xiàn)DMA通信體制任務(wù)帶寬為通聯(lián)關(guān)系總和乘二再加1 M，并根據(jù)配置自動(dòng)進(jìn)行關(guān)聯(lián)，帶寬會(huì)作為查詢可用資源的參數(shù)，關(guān)聯(lián)關(guān)系則會(huì)作為資源匹配的參數(shù)。

網(wǎng)管對任務(wù)進(jìn)行審批，查看任務(wù)申請是否合理，申請合理即可通過任務(wù)審批，申請不合理即可駁回修改后重新提交。如果合理，利用搜索匹配出適合用戶使用的資源，通過任務(wù)執(zhí)行區(qū)域的經(jīng)緯度和面積，匹配出在任務(wù)執(zhí)行區(qū)間沒有被使用的預(yù)案，預(yù)案中綁定的有波束和波束轉(zhuǎn)發(fā)器資源，如果沒有合適的預(yù)案用戶可以手動(dòng)新增預(yù)案。

圖3 預(yù)案匹配過程示意圖

網(wǎng)管服務(wù)器根據(jù)任務(wù)填寫的信息以及預(yù)案的歷史評分對可用預(yù)案進(jìn)行排序，預(yù)案按照匹配度降序排序，同等匹配度按預(yù)案的歷史評分降序排序，其中預(yù)案的匹配度最大值為1，匹配度與任務(wù)和預(yù)案的網(wǎng)系、區(qū)域?qū)傩浴⒀b備、帶寬等因素相關(guān)，預(yù)案的歷史評分為，預(yù)案執(zhí)行過的歷史任務(wù)用戶針對此次任務(wù)執(zhí)行的預(yù)案滿意度評分（最高為100，最低為0）的平均值。這樣排序可以方便用戶更直觀的看到匹配度最高的預(yù)案，節(jié)省了用戶選擇合適預(yù)案的時(shí)間。

用戶也可以手動(dòng)選擇預(yù)案或者自動(dòng)使用綜合評分和匹配度最高的預(yù)案，任務(wù)執(zhí)行結(jié)束后，系統(tǒng)會(huì)自動(dòng)回收此預(yù)案，用戶可以對此段資源進(jìn)行評分，以便下次匹配的準(zhǔn)確性。當(dāng)存在緊急任務(wù)無空閑資源可用時(shí)，用戶可以選擇撤銷不緊要的未開始、進(jìn)行中的任務(wù)，任務(wù)撤銷后，占用資源被釋放，可提供給其他任務(wù)使用。或任務(wù)提前完成，用戶可以選擇撤銷該任務(wù)，提前釋放資源，為后續(xù)任務(wù)的執(zhí)行提供支持。任務(wù)如果在規(guī)定時(shí)間內(nèi)沒有完成，用戶可以申請延長任務(wù)，繼續(xù)使用該段資源或其他未被占用資源。

2 多參數(shù)遺傳算法

圖4 任務(wù)暫停和取消過程示意圖

上文提出了預(yù)案匹配的申請流程，發(fā)現(xiàn)雖然有比較清晰簡約的預(yù)案生成，但帶寬匹配還需要找出最優(yōu)方案，本文基于海量用戶的數(shù)據(jù)基數(shù)，同時(shí)每個(gè)鏈路多種狀態(tài)切換造成可用帶寬的不確定性，同時(shí)分配帶寬還要計(jì)算多個(gè)參數(shù)的影響因子，所以考慮使用多參數(shù)遺傳算法，基于“適者生存”機(jī)制是遺傳算法的一大特征，可以實(shí)現(xiàn)高度并行自適應(yīng)搜索算法。1967年，Rosenberg首次將遺傳進(jìn)化應(yīng)用到多個(gè)參數(shù)的選擇優(yōu)化問題，從此關(guān)于多參數(shù)問題的研究邁入新紀(jì)元，采用遺傳進(jìn)化的搜索思想后來也隨之成為大量學(xué)者研究的基礎(chǔ)[7]。

設(shè)一個(gè)衛(wèi)星互聯(lián)網(wǎng)中有L個(gè)可用鏈路，表示為L={1，2，L，L}，每個(gè)鏈路的已占用和正在申請用戶集為N={1，2，L，N}，用N1表示在鏈路l中的所有用戶，并且有衛(wèi)星互聯(lián)網(wǎng)的總帶寬設(shè)為Btot。

用戶申請頻段資源的基本信息主要包括10個(gè)參數(shù)，分別是任務(wù)名稱N、任務(wù)類型C、任務(wù)等級L、開始時(shí)間Ts、結(jié)束時(shí)間Te、申請帶寬B、所屬網(wǎng)系F、參與任務(wù)的單位信息D、人員信息P、設(shè)備信息E等任務(wù)基本信息，用戶填寫的開始時(shí)間Ts不能早于當(dāng)前系統(tǒng)時(shí)間T，用戶所填基本信息會(huì)作為初次計(jì)算此次申請所能分配的鏈路資源的輸入?yún)?shù)。

以十種數(shù)據(jù)類型N、C、L、Ts、Te、B、F、D、P、E為對象，進(jìn)行染色體的編碼，并在L個(gè)可用鏈路中進(jìn)行收索查詢，L={1，2，L，L}，隨機(jī) 生成初始元數(shù)據(jù)種群Y={1，2，L，Y}。判斷進(jìn)化元數(shù)據(jù)文件Y={1，2，L，Y}的版本數(shù)是否達(dá)到客戶要求，如果達(dá)到要求，則輸出最后一代元數(shù)據(jù)文件種 群Ytot={1，2，L，Y}，其中Ytot的種群帶寬之和為Btot，用于分配帶寬，并結(jié)束算法流程，否則計(jì)算種群適應(yīng)度值，采用“十種數(shù)據(jù)類型競技”法選取父代的上一版本元數(shù)據(jù)文件（包括原始文件和需求文件）并以某種規(guī)則進(jìn)行交叉，產(chǎn)生子代元數(shù)據(jù)版本；交叉完成之后，父代原始文件以一定概率變異，加上需求迭代變化產(chǎn)生子代下一個(gè)版本的元數(shù)據(jù)文件（為保留種群多樣性，變異后的父代版本保留）。將交叉、變異后的子代版本與父代版本對比合并，觀察新需求是否在新版本中添加，重新計(jì)算用戶集為N={1，2，L，N}的種群個(gè)體適應(yīng)度值。判斷種群的元數(shù)據(jù)文件數(shù)據(jù)類型數(shù)量是否大于初始設(shè)定值Btot，超過設(shè)定值Btot則根據(jù)適應(yīng)度通過“十種數(shù)據(jù)錦標(biāo)賽”剔除多余解。進(jìn)化代數(shù)的版本數(shù)version+1，返回。圖5為多參數(shù)遺傳算法的流程圖。

圖5 多參數(shù)遺傳算法的流程圖

3 基于預(yù)案匹配的衛(wèi)星互聯(lián)網(wǎng)絡(luò)資源動(dòng)態(tài)分配技性能測試

本節(jié)采用基于預(yù)案匹配的衛(wèi)星互聯(lián)網(wǎng)絡(luò)資源動(dòng)態(tài)分配技術(shù)的衛(wèi)星網(wǎng)管服務(wù)器，在真實(shí)的運(yùn)營環(huán)境中進(jìn)行測試，如圖6所示。

圖6 基于預(yù)案匹配的中心網(wǎng)管測試環(huán)境

在1號終端的臺(tái)式機(jī)192.168.201.10上部署iperf 軟件的客戶端，在10.16.0.66上部署iperf服務(wù)端，在4 M、2 M和1 M的衛(wèi)星互聯(lián)網(wǎng)帶寬下，分別不使用預(yù)案匹配方案，標(biāo)準(zhǔn)的預(yù)案匹配方案和多參數(shù)遺傳算法的預(yù)案匹配方案分別測試平均發(fā)送速率，取6次樣本的平均值來進(jìn)行對比，數(shù)據(jù)如表1所示。

表1 預(yù)案匹配方案測試數(shù)據(jù)

由表1中看出，預(yù)案匹配方案對衛(wèi)星互聯(lián)網(wǎng)的傳輸速度由明顯提升。而用戶平均等待時(shí)間的對比結(jié)果如圖7所示。

由圖7可知，在相同帶寬的衛(wèi)星互聯(lián)網(wǎng)前提下，包含多參數(shù)遺傳算法的預(yù)案匹配方案可以較大的提升用戶申請效率。因此，在衛(wèi)星通信中，采用基于預(yù)案匹配的衛(wèi)星互聯(lián)網(wǎng)絡(luò)資源動(dòng)態(tài)分配技術(shù)可以大大提升帶寬分配效率，進(jìn)而可以提高系統(tǒng)的吞吐量。

圖7 多種分配方式的帶寬分配時(shí)間對比

4 結(jié)束語

基于低軌衛(wèi)星系統(tǒng)的寬帶衛(wèi)星互聯(lián)網(wǎng)是當(dāng)前互聯(lián)網(wǎng)發(fā)展的新方向，由于衛(wèi)星本身具有的移動(dòng)性和時(shí)變性以及地面-衛(wèi)星混合網(wǎng)絡(luò)的復(fù)雜性，面對海量用戶、衛(wèi)星通信資源申請流程的繁瑣和資源分配的不穩(wěn)定性也成為影響衛(wèi)星互聯(lián)網(wǎng)通信速率的問題。而基于預(yù)案匹配的衛(wèi)星互聯(lián)網(wǎng)絡(luò)資源動(dòng)態(tài)分配技術(shù)可以大大提升帶寬分配效率，進(jìn)而可以提高系統(tǒng)的吞吐量。