低軌衛星物聯網場景下基于吸引子選擇算法的多星負載均衡算法

程一凡, 洪 濤,*, 丁曉進, 張更新

(1. 南京郵電大學通信與信息工程學院, 江蘇 南京 210003; 2. 南京郵電大學物聯網學院, 江蘇 南京 210003)

0 引 言

物聯網是一個基于互聯網、傳統電信網等信息承載體,讓所有能夠被獨立尋址的普通物理對象實現互聯互通的網絡,是對新一代信息產業變革和社會發展具有重要意義的一種新興的信息科技技術。根據相關研究院的市場調查報告顯示,到2020 年,全球安裝的物聯網設備已經在5年時間內增長了150多億臺。預計到 2025 年,物聯網的安裝設備將達到 700多億臺,并且未來十年復合增長率高達 17.21%。隨著目前無線網絡的發展,地面物聯網網絡已經取得了巨大進步。但是,由于空間環境和地理因素的限制,一些問題在地面物聯網上還不能得到有效的解決。在地理環境較為惡劣的地區,布設基站以及建立通信網絡并非易事:① 大面積的海洋、沙漠等區域無法建立基站;② 在人口稀少的邊遠地區建立基站的成本較高;③ 自然災害會對地面網絡造成嚴重的破壞。衛星物聯網作為地面物聯網系統的延伸及補充,有效地解決了地面網絡在部署時所面臨的環境受限問題。衛星物聯網具有如下優勢:① 物聯網終端布設不受環境限制;② 終端使用壽命長,不易受惡劣自然環境等外部因素影響;③ 動態性高,能夠向高速運動物體(飛機、船舶等)持續提供網絡連接等。選擇低地球軌道(low earth orbit,LEO)衛星作為衛星物聯網的主要使用衛星是因為其具有相對較低的傳播時延及傳播損耗,能夠滿足衛星物聯網終端設備低成本和高壽命的要求。

物聯網業務由于具有多種業務種類、節點數目較多、小數據通信且上行占優、終端較為固定等特點而與傳統話音業務不同。業務種類的差異也意味著接入網資源需求的差異,所以研究通用且有代表意義的物聯網業務模型估算方法,對未來接入網資源的規劃具有重要意義。因此,物聯網業務典型特征的建模分析己經成為了各個國家學者研究的熱點。文獻[8]中分析了地面物聯網業務的典型特征,研究了與互聯網相關流量模型明顯不同流量特征的物聯網業務模型,并針對物聯網業務的瞬時突發入網特性,驗證了Beta分布能夠更好地刻畫地面物聯網業務的同步通信過程。文獻[9]中研究了不同的地面物聯網業務,并發現不同的業務之間具有不同的自相似特性,不同的流量密度與時間尺度也會導致相同的業務具有不同的流量特性。文獻[10]根據不同的使用場合、業務特點等將M2M(machine to machine)業務進行區分,建立了一個具有M2M業務特征的簡化M2M業務模型。由于終端準靜態和在接入基站均勻分布的特點,地面物聯網研究多集中在業務模型中的業務到達時間。低軌衛星物聯網作為地面物聯網的補充,其節點分布具有顯著的與地理環境相關聯的特征,業務模型具有空間不均勻性。并且低軌衛星相對于地面處于高動態,低軌衛星波束覆蓋范圍內業務模型在空間和時間兩個維度具有時變性。因此,需要在空間和時間兩個維度上聯合研究低軌衛星物聯網業務,為星上接入資源的規劃奠定理論基礎。

吸引子選擇算法的出現始于生物系統的自適應反應,主要用來描述在外界環境變換的情況下大腸桿菌的動態自適應反應,目前已經廣泛應用在異構網絡的接入選擇問題中,通過用戶細胞吸引子選擇機制來做出分布式和具有魯棒性的異構網絡切換決策,以提升系統無線接入資源的利用率,保障業務服務質量(quality of service, QoS)。文獻[12]中將細胞吸引子選擇模型應用于網絡資源分配中,采用終端控制的方式,將每個終端節點看作一個細胞,基于吸引子的選擇模型設計了一種面向多終端的無線網絡選擇方法,解決了不同終端上的網絡接入問題。文獻[13]提出了一種基于吸引子選擇模型的自適應網絡選擇算法,用于解決單個網絡的數據過載問題,當用戶移動到新位置時,吸引子選擇能夠自適應地感知動態環境,并指示控制器在新位置上選擇哪些網絡。除此之外,吸引子選擇算法作為一種新型的生物啟發算法,已經應用于保障QoS的魯棒路由算法和可容忍的網絡覆蓋控制的研究中。這些研究成果表明,相比于傳統方法,吸引子選擇算法具有多方面的優勢。通過對吸引子選擇模型的研究分析,將網絡選擇問題的轉換為細胞吸引子選擇模型,并將網絡動態變化的條件與細胞活躍度聯系起來,為動態環境下的網絡選擇問題提供一個新的模型。文獻[18]在無線異構網絡場景下提出了一種基于吸引子選擇的魯棒性的異構網絡選擇算法,終端根據異構網絡間不同的網絡狀態和業務不同的QoS需求選擇接入的網絡以提升網絡傳輸性能。

本文針對低軌衛星物聯網場景下業務的不均勻性和時變特性,提出了一種基于吸引性選擇的物聯網業務負載均衡算法,以提高低軌衛星物聯網系統星上資源的利用效率,具體工作如下:① 提出了低軌衛星物聯網空時二維模型,使用網格劃分結合終端隨機位置生成算法確定物聯網終端的位置,使用Beta分布模擬海量同步接入請求。相比于傳統的地面物聯網業務模型,本文低軌衛星物聯網業務模型中充分挖掘物聯網業務的空間維度屬性,將物聯網業務模型拓展到空時二維模型;② 提出一種基于吸引子選擇算法的負載均衡策略,終端節點綜合考慮低軌衛星可用的前導碼數量、實時衛星通信仰角、衛星實時覆蓋節點數目以及衛星側實時接入成功率4個因素,通過多屬性決策的方式,計算網絡狀態變量,進而計算接入每顆可視衛星的概率,最終通過隨機數與累積概率比較的方式確定接入哪顆衛星。相比于吸引子選擇算法在地面異構網絡選擇中僅考慮基站側實時接入成功率和可用前導碼數目,本文提出的算法綜合考慮了低軌衛星物聯網系統中通信仰角等多個因素,并采用多屬性決策的方式權衡衛星側的設備滿意度,充分體現了低軌衛星物聯網的系統特征。

1 衛星物聯網空時二維業務模型

1.1 系統模型

圖1給出了衛星物聯網場景下典型終端接入場景。相比于地面物聯網基站,低軌衛星波束覆蓋范圍大,覆蓋范圍內地理環境復雜,而衛星物聯網業務與地面地理環境密切相關。并且低軌衛星相對于地面高速運動,導致低軌衛星波束覆蓋范圍內節點業務模型在空間和時間兩個維度呈現不均勻性和時變性。

圖1 多星覆蓋場景圖Fig.1 Multi-star coverage scene diagram

為了在空時兩個維度建模衛星物聯網業務模型,首先需要了解衛星物聯網終端類型以及不同類型終端分布的地理環境。衛星物聯網終端主要分為:移動載體終端(車載、船載、機載)、采集終端、固定終端、嵌入式終端、多模終端。其中移動載體類終端、多模終端主要應用在經濟物流和交通運輸中,預計主要部署在以下幾種區域:海洋中的重要航線,例如北大西洋航線,這是一條既運載石油、礦石等天然資源,同時運載大量集裝箱物資的運輸線,或者部署在陸地的重要交通要道,例如“一帶一路”通道,都需要大量物聯網終端實現貴重貨物、資產的跟蹤,保障大地域范圍的無縫通信。保守估計這部分終端在我國經濟物流領域有2 000萬臺的市場容量,若本系統占其中5%的市場份額,便有100萬的物聯網終端。采集終端主要應用在能源通道安全領域、防災減災以及圍界防入侵中,預計主要部署在以下幾種區域:能源通道,如在石油天然氣管道實現實時無縫監測;森林、沙漠、海洋等自然環境,實現火災預警、土壤荒漠化監測、水文監測等功能;陸地邊境線,安裝電子崗哨防止人步行穿越。以石油天然氣管道為例,目前我國的管線總長約7萬公里,按每50 km設置1個備份監測點計算,預計共需3 500個左右。以陸地、海洋資源監測為例,我國河流總長度4.2×10km,平均每10 km一個傳感器,預計共需4.2萬個;淡水湖泊3.6×10km,荒漠化土地2.64×10km,水土流失面積3.56×10km,森林總面積1.75×10km,平均每10 km一個傳感器,預計共需80萬個左右。

衛星物聯網終端由于布置的地理環境的限制,不能頻繁地更換供電電池。而低軌衛星受限于體積大小和造價是一個資源受限系統。為了改善衛星網絡的覆蓋效果,未來衛星物聯網使用的星座將會朝著低軌巨型星座的方向發展,如SpaceX公司的“星鏈”計劃共達到了4.2萬顆衛星的規模,我國提出“虹云工程”,共由156顆小型衛星組成,運行在距地面約1 000 km的近地軌道上,預計2022年完成所有衛星的部署。這種密集建設低軌衛星星座的方式為地面物聯網終端提供了多星可視的接入條件,終端節點可以通過設計多星負載均衡算法提高終端隨機接入的性能以及星上資源的利用效率。

1.2 空時二維業務模型

文獻[24]中論述了衛星物聯網的業務模型特征:① 在空間維度上由于地理環境差異性導致終端分布密度不均;② 在時間維度上由于業務類型差異性導致業務到達時間不一致。針對上述特征,本節提出一種衛星物聯網空時二維業務模型方法。如圖2所示。

圖2 空時二維業務模型框圖Fig.2 Block diagram of space-time two-dimensional business model

所提衛星物聯網業務模型產生方法的步驟如下。

對地球表面區域進行網格劃分并進行業務分析,確定網格內終端部署密度。設(,)表示目標區域的終端部署密度,其中和通過相應的仿射變換對應于實際的地理緯度坐標和經度坐標。計算歸一化的二維節點概率密度函數,(,):

(1)

計算的邊緣累積概率分布函數:

(2)

采用一維逆變化采樣方法,可以利用上述分布函數生成一個軸上的隨機數:

(3)

將(,)中的第′行提取出來,記為(|′),并對其進行歸一化,記為|′(|′)。計算給定′條件下的累積條件概率分布函數|′(|′):

(4)

與步驟3同理,可以利用上述分布函數生成一個軸上的隨機數:

(5)

將步驟3和步驟5中生成的′和通過仿射變化轉換成實際的緯度坐標和經度坐標:

(6)

式中:和表示緯度和經度最小的參考坐標;和表示緯度和經度的劃分間隔。

計算每個時隙下產生的新業務數量,采用了時間受限的Beta分布,假設總數為的物聯網終端在=0到=之間的某一個時間節點被觸發,隨機接入的概率為(),則第個時隙中被觸發的終端數目可以由下式計算:

(7)

根據步驟7中計算的新業務數,每個時隙隨機選取相應數量的終端產生新業務。

2 基于吸引子選擇的多星負載均衡算法

2.1 吸引子選擇模型

文獻[25]中描述了大腸桿菌細胞通過切換不同的遺傳程序以自適應外部環境變化的行為,提出有噪聲干擾的吸引子選擇模型,并通過多次實驗,揭示了細胞根據動態環境變化從而改變基因表達以適應外部環境的生物行為。其利用了兩種熒光蛋白研究大腸桿菌細胞,分析了細胞體內部兩個相互抑制操縱子之間的“雙穩態切換”現象。如圖3所示,細胞生存環境的變化相當于給細胞輸入了兩種信號(實際是多種,此處以兩種為例),這兩種信號的輸入直接影響了細胞所需的營養成分的合成量,從而決定了細胞中兩種營養成分的濃度,最終細胞通過調整自己的基因表達控制此時刻自身的生命活動,而這種生命活動的改變會使細胞內部的營養成分趨近于一種動態的平衡。

圖3 細胞雙吸引子選擇模型Fig.3 Cell double attractor selection model

生物學中的吸引子指的是細胞的基因表達,如果目前的基因表達無法適應外部環境,在噪聲的影響下,細胞會自適應地切換合適的基因表達,從而適應外部不斷變化的環境。具體模型如下所示:

(8)

2.2 基于吸引子選擇的多星負載均衡算法

根據第21節所述的吸引子選擇模型,考慮將其引入到衛星物聯網中多衛星覆蓋的場景中,本文提出了一種吸引子選擇擴展模型,將原始的吸引子選擇模型擴展到衛星物聯網場景中的多個衛星選擇之中,該模型支持個衛星的選擇,其理論模型如下:

(9)

在本文提出的擴展吸引子選擇模型中,網絡活性因子表征參數是決策的核心參數之一,該參數用以表征衛星選擇決策解的綜合優化性能。為了保障物聯網終端實時做出最優決策,以及綜合考慮衛星系統的特殊性,因此本文以衛星側的實時接入成功率、衛星實時覆蓋節點數目、衛星側的可用前導碼數目以及衛星相對于終端的實時通信仰角作為考慮因素,構造一個新的參數稱為設備滿意度,用以表征衛星側的接入性能的優劣。時刻下物聯網終端收到衛星廣播傳輸的4個因素,通過多屬性決策的方式加權計算衛星的實時設備滿意度如下:

,=,,++,+,

(10)

式中:、、、代表了4個方面關鍵因素的權重系數,可以通過多屬性決策方式的離差最大化方法計算權值,表達式為

(11)

式中:表示規范化矩陣的元素值。在以上4個方面關鍵因素中,衛星實時覆蓋節點數目和可用前導碼數目對于衛星本身是已知的,衛星實時相對于終端節點的通信仰角可計算如下:

(12)

式中:表示衛星星下點所處的經度;和表示終端節點所處的經度和緯度。而衛星的實時接入成功率,,不是直接已知的,計算接入成功率,不僅需要獲得成功接入的節點數,還需要知道接入的總負載。為了獲取接入總負載,本文提出了一種負載估計的方法,使衛星能夠根據自身的隨機接入前導碼使用情況來預估接入的規模。終端在與衛星建立連接的過程中,首先需要從可用前導資源中隨機選擇一個前導序列并將其發送到目標衛星,假設衛星可用的前導序列為,第個隨機接入時隙內的上行接入請求數目為,,則從理論上分析某個前導碼序列未被任何終端節點選擇,處于空閑狀態的概率為

(13)

此外,由于衛星能夠監測隨機接入信道,從而獲知在第個隨機接入時隙內的空閑前導序列數目,,則也能夠獲知前導序列處于空閑狀態的概率:

(14)

通過聯立式(13)和式(14),可以求得第個隨機接入時隙內接入衛星的總負載數目為

(15)

然而,由于本文考慮的衛星物聯網中的突發流量具有短時間內激增的特性,會導致接入請求的數目急劇增加,當接入請求數目遠遠高于可用的前導序列數目時,即沒有任何可用前導序列處于空閑狀態,此時上述的基于空閑簽到序列空閑概率的估計方法已經不再適用。因此,本文提出了一種適用于無空閑前導序列的接入負載估計算法。從理論上分析,當前導序列僅被單個終端節點選擇的情況下,此次接入才能成功建立,因此在第個隨機接入時隙內向衛星發起隨機接入請求的終端,能夠完成成功接入的概率為

(16)

利用式(16)以及隨機接入過程的理論模型可以計算出在第個隨機接入時隙內成功接入衛星的負載數目:

(17)

通過聯立式(16)和式(17),可以得出無空閑前導序列情況下的接入總負載的估計值:

(18)

式中:lambertw(·)表示朗伯函數。

綜上所述,利用本節提出的方法估計出第個隨機接入時隙內成功接入衛星的總負載數目,進而可以計算出第個隨機接入時隙內衛星的接入成功概率,,:

(19)

接下來采用Sigmoid型效用函數將設備滿意度映射到網絡活性因子,保證兩者的一致性,即衛星對于終端的實時設備滿意度越高,則該衛星的實時網絡活性就越大。時刻下衛星的瞬時網絡活性因子由下式計算:

(20)

在吸引子選擇算法的驅動下,系統能夠搜索到合適的吸引子選擇方案使系統活性達到最大,并使系統狀態暫時趨于平穩,此時的噪聲對系統整體狀態的變化可以忽略不計。那么在平衡狀態下,式(9)轉換為

(21)

根據上述平衡狀態下的非線性微分方程,可以求得

(22)

由于第一個解是負數解,因此舍棄。可以求得可行的實時網絡狀態變量解為

(23)

式中：=arg max{,,=1,2,…,}。

進而計算物聯網終端在時刻下接入衛星的概率為

(24)

式中:表示時刻下可視衛星的個數。

終端生成服從均勻分布的隨機數～U(0,1),∈[0,]。

每個終端將自己生成的隨機數與中的元素依次比較,直到找到中第一個小于等于的元素(1,)。

取出(1,)所在的列標號即為該終端發起隨機接入的衛星編號,可表示如下:

=argmin{(1,),=1,2,…,|(1,)≤}

(25)

基于吸引子選擇算法的負載均衡算法的基本框圖和流程圖如圖4和圖5所示,其中隨機接入流程采用面向連接隨機接入協議,如圖6所示,算法偽代碼如算法1所示。

圖4 基于吸引子選擇算法的負載均衡算法框圖Fig.4 Block diagram of load balancing algorithm based on attractor selection algorithm

圖5 基于吸引子選擇算法的負載均衡算法的算法流程圖Fig.5 Flow chart of load balancing algorithm based on attractor selection algorithm

圖6 面向連接的隨機接入協議流程Fig.6 Flow diagram of connection-oriented random access protocol

算法 1 基于吸引子選擇算法的負載均衡算法初始化:1: At,i:第t個隨機接入時隙內衛星i的網絡活性因子;2: mt,i:第t個隨機接入時隙內衛星i的網絡狀態變量;3: mt,k:第t個隨機接入時隙內最優衛星k的網絡狀態變量;4: ps,t,i:第t個隨機接入時隙內衛星i的接入成功率;5: pt,i:第t個隨機接入時隙內選擇衛星i發起隨機接入的概率;6: Nt:第t個隨機接入時隙內可視衛星的數目;算法 決策過程7: if 終端未選擇任何衛星發起隨機接入 then8: for i=1:Nt do9: 根據式(20)計算At,i;10: end for11: 終端選擇網絡活性最大的衛星k=arg max{At,k,k=1,2,…,K};12: else13: for ω=1:Nt do14: 衛星根據式(15)、式(18)和式(19)計算實時接入成功率;15: 終端根據式(12)計算衛星實時通信仰角;16: 終端根據式(10)進行多屬性決策計算設備滿意度;17: 終端根據式(20)計算At,i;18: 終端根據式(21)計算mt,i;19: 終端根據式(22)計算pt,i;20: end for21: 記St=[pt,1,pt,1+pt,2,…,∑Nti=1pt,i,…,1],終端生成服從U(0,1)的隨機數;22: 終端根據公式(23)計算發起隨機接入的衛星編號;23: end if

3 數值仿真與分析

本文針對衛星物聯網場景下事件驅動型業務產生的突發流量進行仿真,分別采用文獻[30]中提出的基于最高優先級的決策接入算法和本文提出的負載均衡算法進行決策接入。本仿真采用的星座類型為OneWeb星座,對地球表面以緯度間隔2°、經度間隔2.5°為標準進行網格劃分。衛星物聯網終端的部署密度等級預計如圖7所示,圖中將終端部署密度由高到低劃分為紅、橙、黃、綠、藍、紫6個等級,等級的高低與世界主要運輸交通線的繁忙程度、土地的荒漠化程度以及重要自然資源(煤、石油)的分布密度成正相關。本仿真取南緯10°-北緯14°、西經15°-東經20°作為代表性區域進行研究,如圖8所示,這片區域被12顆衛星的波束覆蓋。終端節點的總數設置為5 000～10 000個,在100個時隙內產生服從Beta分布的突發流量。考慮到衛星物聯網的接入終端是海量的,將衛星的前導碼個數設置為15個,相比于終端節點數目可以看出,在每個時隙能夠成功接入的節點數不超過總數的10%。節點碰撞后采用的退避方式為二進制指數型退避,原因是這種退避方式中節點隨著重傳次數的增加,其退避時間也會增大,避免了沖突的加劇。具體仿真參數如表1所示。

圖7 衛星物聯網終端的部署情況Fig.7 Deployment of satellite internet of things terminals

圖8 仿真研究區域Fig.8 Simulation study area

表1 仿真參數

圖9是采用基于最高優先級的接入策略的衛星業務量曲線圖,可以看出衛星編號為1、4、5、9、12的衛星始終沒有承擔任何的業務,系統資源利用率較低。圖10是采用基于吸引子選擇算法的負載均衡策略的衛星業務量曲線圖。可以看出，相比于原始策略,12顆衛星分別承擔了一定的業務,提高了系統資源利用率。圖11是兩種策略下部分衛星的業務峰均比柱狀圖,可以直觀地看出,所提方法在一定程度上改善了業務峰均比。綜合圖9～圖11可以看出,采用本文提出的算法進行決策接入能夠使原本空閑的衛星分擔其他繁忙衛星的業務,提高了資源利用率;并且改善了部分衛星的高峰均比,使單星業務曲線更加平滑,有益于衛星長期使用。

圖9 采用基于最高優先級的接入策略進行決策接入的衛星業務量曲線Fig.9 Satellite traffic curve using access strategy based on the highest priority for decision access

圖10 采用所提算法進行決策接入的衛星業務量曲線Fig.10 Satellite traffic curve for decision access using the proposed algorithm

圖11 采用兩種策略進行決策接入的衛星業務峰均比柱狀圖Fig.11 Peak-to-average ratio histogram of satellite service using two strategies for decision access

圖12是兩種策略下的平均接入時延隨接入規模的變化曲線圖。可以看出，隨著接入規模的提升,所提方法的平均接入時延基本沒有顯著變化,而現有文獻中的方法的平均接入時延急劇增加,從數值上來看,前者明顯低于后者,在高負載情況下,前者最小約為后者的1/10。圖13是兩種策略下的系統吞吐量隨接入規模的變化曲線圖。可以看出，隨著接入規模的提升,采用本文提出的算法,平均吞吐量呈現先上升后下降的趨勢,而采用基于最高優先級的接入策略,平均吞吐量逐漸降低,從數值上來看,前者明顯高于后者,在高負載情況,吞吐量最大提升了約90%。圖14是兩種策略下的平均重傳次數隨接入規模的變化曲線圖,可以看出隨著接入規模的提升,采用本文提出的算法,平均重傳次數基本沒有顯著變化,而現有文獻中的方法的平均重傳次數急劇增加,從數值上來看,前者明顯低于后者,在高負載情況下,前者最小約為后者的1/9。

圖12 采用兩種策略進行決策接入的平均時延隨接入規模的變化曲線Fig.12 Changing curve of average delay with access scale using two strategies for decision access

圖13 采用兩種策略進行決策接入的平均吞吐量隨接入規模的變化曲線Fig.13 Changing curve of average throughput with access scale using two strategies for decision access

圖14 采用兩種策略進行決策接入的平均重傳次數隨 接入規模的變化曲線Fig.14 Changing curve of average retransmission times with access scale using two strategies for decision access

4 結 論

本文針對低軌衛星物聯網場景,首先提出了一種空時二維模型物聯網業務建模方法;其次基于細胞吸引子選擇模型并結合衛星系統傳播特征,提出一種適用于多星覆蓋、業務源及接入規模變化的負載均衡算法,使得物聯網終端進行自適應地衛星接入決策,提高了星上資源利用率,改善了終端隨機接入性能。本文的工作只是在接入算法設計層面解決多星可視場景下多顆低軌衛星負載均衡問題,關于物聯網終端位置隨機產生方法、數據鏈路層協議、隨機接入協議等問題有待進一步的研究。