低轨卫星物联网场景下基于吸引子选择算法的多星负载均衡算法

程一凡, 洪 涛,*, 丁晓进, 张更新

(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 结 论

本文针对低轨卫星物联网场景,首先提出了一种空时二维模型物联网业务建模方法;其次基于细胞吸引子选择模型并结合卫星系统传播特征,提出一种适用于多星覆盖、业务源及接入规模变化的负载均衡算法,使得物联网终端进行自适应地卫星接入决策,提高了星上资源利用率,改善了终端随机接入性能。本文的工作只是在接入算法设计层面解决多星可视场景下多颗低轨卫星负载均衡问题,关于物联网终端位置随机产生方法、数据链路层协议、随机接入协议等问题有待进一步的研究。