基于动态复合优先级的海上节点网络选择算法

张治霖，毛忠阳*，刘传辉，徐建武，孙 林,魏靖怡

(1.海军航空大学 航空通信教研室，山东 烟台 264001;2.山东省信号与信息处理重点实验室，山东 烟台 264001；3.中国人民解放军91876部队，河北 秦皇岛 066206)

0 引言

网络选择作为异构网络资源分配的重要组成部分，直接决定了网络内节点的通信性能[1]。在海上利益凸显的时代背景下，海上异构无线网络(Marine Heterogeneous Wireless Networks,MHWNs)对节点业务传输的完成度和多样性提出了更高的要求，需要综合性更高、灵活性更高、适应性更强的新网络选择算法，实现各种业务类型的动态分配和高效传输[2]。这就要求网络选择算法必须同时兼顾多属性决策能力、业务优先级动态分配能力和复杂场景适应能力[3]。针对以上需求，相关领域的专家和学者提出了多种多样的解决方案。

VIKOR方法是解决复杂系统多属性决策问题的方法之一，比起TOPSIS方法[4]，VIKOR方法能够在众多冲突方案中选出最大化群体利益的方案，即折中方案。节点在海上异构网络中完成业务传输任务需要综合考虑信号强度、距离、带宽、丢包率等一系列参数，往往网络环境中没有非常完美的传输信道，需要在众多机动站点中选取最大化传输效率的节点，符合VIKOR方法的应用范围。VIKOR方法自1998年被提出后，诸多学者对其做了深入的研究。王坚强等人[5]针对多属性决策的准则权系数信息不完全确定或多为模糊数的问题，提出了模糊多准则VIKOR方法，拓展了VIKOR方法在模糊数领域的应用范围，但存在无法对方案进行排序的局限。索玮岚等人[6]提出了一种更为复杂的混合型E-VIKOR方法，主要面向具有数值、区间数和模糊数形式信息的混合型多属性决策问题，其做法是先分别处理数值、区间数和模糊数，再将归一化结果输入VIKOR方法计算排序，为VIKOR方法的改进提供了新思路。

节点产生业务传输业务时，每个业务对完成时间的需求不尽相同，通常的解决方法是选用业务优先级表示业务的执行紧迫性。围绕基于业务优先级的网络接入算法研究[7]，相关领域的专家学者提出了多种算法，最为传统的是最小空闲时间优先(Least Slack First,LSF)算法[8]、最早截止时间优先级 (Earliest Deadline First,EDF)算法[9-10]和随机公平队列(Stochastic Fairness Queueing，SFQ)算法[11]。LSF算法[12]遵循任务所剩的空闲时间越少，就越需要尽快执行规则，所以经常会造成乒乓效应，增大了系统开销；EDF算法[13]是根据任务的截止时间确定业务的优先级，虽然在一定程度上保证了业务完成率，但是对于高优先级业务的重视程度不够；SFQ算法遵循高度的公平性，其计算量相对较小，但精确度较差。Lun Zeng等人[14]采用改进的SFQ算法，针对网络信道状态和节点拓扑动态变化的问题，用优先级表示业务抢占信道的能力，用权重值影响信道接入，通过综合考虑优先级和权重值提升网络性能。陶洋、纪瑞娟等人[15]针对切换造成网络拥堵的问题，提出一种新的资源分配调度方法，根据业务的剩余价值密度和紧迫性系数动态调整优先级，但仿真环境过于平稳，缺少对恶劣环境适应性的研究。

在分析业务优先级排队方式的基础上，针对不同业务时效性不同和波动环境适应性不强的问题，引入环境权重、修改的剩余价值和执行紧迫性组成动态复合优先级，实时优化业务排队序列，所提算法能有效提高高优先级业务的完成率，从而降低网络在服务业务时的堵塞率。

1 基于业务优先级的网络选择算法

1.1 模型建立

海上作业船舶和飞机在海域上进行的业务多种多样，每个业务的时效性、紧迫性和优先级各不相同，仅用一种或几种网络已经远远不能满足当前网络发展的需要，因此在需求的牵引下，海上异构网络通过其覆盖面广、网络种类复杂等优点脱颖而出。在多重网络覆盖下的用户想要完成传输任务需要考虑带宽、距离以及包延迟等参数，这正是网络选择算法复杂度高的原因所在。

图1 MHWNs框架Fig.1 Architecture of MHWNs

本文采用的海上异构无线网络架构如图1所示。海上异构网络的通信信道与陆地不同，遮挡物少使得传输收到反射波的影响变大。海上环境虽然比陆地环境空旷，但传输环境下由干扰造成的波动性仍然是不可忽视的影响因素，其中干扰包括自然因素和人为因素。因此如何在波动环境中仍能保持较为稳定的传输速率和业务完成率是目前亟待解决的问题之一。

1.2 算法描述

由于节点的随机移动和周围环境的变化波动，其所在接收范围内的机动站点和网络属性参数在不断改变。本文采用VIKOR法为移动节点提供合适的实时接入方案，选用环境权重、剩余价值和执行紧迫性作为业务改变优先级的标准，充分考虑业务的类型、初始价值和时效性。根据VIKOR法提供的最佳接入方案，将其选择的机动站点环境参数转变成环境权重，提供给优先级函数进行动态更新，根据优先级结果对请求接入业务进行排序和接入。

1.2.1 VIKOR法确立连接方案

机动站点周围的网络参数在每时每刻变化着，参数的大小和变化率都是随机的，VIKOR法能在众多网络参数中选择出效益最大的机动站点，能够有效地针对环境波动问题为移动节点提供更适合现阶段环境传输的连接方案。

(1)

(2)

然后根据公式求得Qj[5]：

(3)

其中，S*=minSj，S-=maxSj，R*=minRj,R-=maxRj,v一般取0.5。最后按照Q值降序排列，选取Q值最小的机动站点作为连接方案。

1.2.2 动态复合优先级

业务在等待接入队列中按照业务优先级进行升序排列，业务优先级越高，在带宽允许的情况下优先考虑接入。考虑到节点所处的波动环境对业务传输的影响，在文献[15]的剩余价值中加入环境参数权重，使得业务在队列排序中能尽量将适合现阶段环境传输的业务优先服务。定义ω(t)为动态复合优先级，其表达式为：

ω(t)=D(t)·φ(t)·Vij(t)，

(4)

式中，D(t)表示剩余价值，φ(t)表示执行紧迫性，Vij(t)表示环境权重。

业务的类型和等级造成了业务时效性的各不相同，其时效性变化规律也有一定差异。对于高优先级会话类业务，其时效性仅保留在产生业务后极短的时间内，而对于高优先级交互类和流媒体类业务，其时效性存在区域相对于同等级的会话类业务而言要宽一些。高优先级的会话类业务和低优先级的会话类业务虽然业务类型相同，但由于优先级的差异导致其时效性存在区域也略有差别。虽然会话类业务时效性区域比交互类业务时效性区域小，但需要动态复合优先级函数给予高优先级交互类业务的优先级能够利用请求接入的时间差超过低优先级会话类业务优先级的机会，否则会造成业务类型架空业务等级、高优先级交互类和流媒体类业务频繁被低优先级会话类业务插队的情况。基于上述考虑，在文献[15]的基础上对剩余价值和执行紧迫度函数进行了修改。

在文献[15]的基础上根据海上业务时效性强的特点，重新定义了剩余价值D(t)，强化了业务优先级与业务持续时间的对应关系，优化了时间间隔对应的价值差值，其表达式为：

(5)

式中，k表示业务参数，Tr表示相对剩余时间，相对剩余时间定义为业务截止时间与已服务时间的差值，V0表示初始价值。

在文献[15]基础上重新定义了执行紧迫度φ(t)，增强了业务类型、业务等级与紧迫性的相关性，平滑了紧迫度曲线，相比于原表达式能够使同一时间差下的紧迫度变化更加均匀，每一时刻变化下紧迫度的变化更加明显。其表达式为：

(6)

式中，q表示业务类型和业务等级的乘积，di表示绝对截止时间，t表示实时时间。

定义Vij(t)为根据VIKOR算法提供的接入方案通过归一化法计算得到的环境权重，其中i表示由VIKOR方法计算出的当前最适合连接的机动站点编号，j表示当前业务类型更侧重第j个网络环境参量。由于不同的业务类型对不同网络参数有着不同的需求，本文设定会话类业务关注包延迟参数，交互类业务关注丢包率参数，流媒体类业务关注带宽参数。设第i个机动站点t时刻的网络参数分别为{α1t,α2t,α3t,...,αnt}，定义归一化后业务关注的参数为其对应业务的环境权重，则会话类业务的环境权重为:

(7)

式中,i=1,2,…，n。交互类和流媒体类的环境权重以此类推。

1.3 算法流程

为与实际运动更贴合，移动节点采用高斯-马尔科夫移动模型[16]进行描述，模拟海上作业飞机的连续随机运动，相较于传统随机模型有着运动曲线更平滑的优势。针对海上通信网络特征，节点通信信道采用海上通信信道[17]，考虑海面反射和大气吸收损耗，不考虑恶劣气候等其他偶然性影响因素。算法的具体流程如图2所示。

图2 算法流程Fig.2 Algorithm flow

节点开始运动时，算法同步运行。算法首先检查业务服务情况：将新产生的业务加入到请求接入排队序列，对过期的业务进行清除，已经结束的业务释放带宽。节点更新路径范围内机动站点周围的环境参数，算法根据输入参数更新所有序列中业务的动态优先级，根据机动站点的环境参数计算出环境权重。将所有参数输入到VIKOR法中，VIKOR提供适合现阶段环境传输的机动站点连接方案。对业务请求接入排队序列按照动态优先级进行排序，按照排队顺序依次检查剩余带宽情况，满足要求的业务开始服务，不满足要求的业务重新进入请求接入序列进行排序。若请求接入队列已满队，则新生成的业务与请求接入队列中动态优先级最小者进行比较，留下动态优先级较大的业务。

2 仿真结果与分析

2.1 参数设置

本文算法的仿真场景设置为海上临时机动站点环境，机动站点的位置如图3所示。机动站点在海平面以每小时15节的速度缓慢向x轴正方向移动，移动节点从原点出发，之后的时间内以150 m/s的速度做连续随机运动，仿真时间800 s。由于仿真使用的是机动站点和海上节点的相对距离，所以机动站点的移动速度相对海上节点来说可以近似为静止。机动站点的通信范围是视距范围，超出通信范围视为无信号。移动节点的出发起始点设置为坐标原点，以此为例进行蒙特卡洛仿真。

图3 机动站点位置图Fig.3 Mobile station location map

在本算法仿真中，移动节点最大带宽设置为150 kHz，等待队列和服务队列最大数量为10，等待队列和服务队列都满队的情况下，再产生业务接入请求时，定义为网络堵塞。业务生成间隔满足参数为3的泊松分布，机动站点的网络参数波动采用马尔科夫链形式进行模拟，状态转移概率为0.5，当前时间的参数只与前一时刻的参数相关，与其他时刻的参数值无关，机动站点网络参数波动范围如表1所示。

表1 仿真参数表

业务参数中带宽参数参考文献[6]，为方便数值计算，3种业务所需带宽同时缩小一个数量级，缩小后的数值不影响后续计算步骤的数值大小和意义。初始价值参数参考文献[7]，并在此基础上扩展到3种业务类型，按照高优先级价值高于低优先级、会话类高于交互类、交互类高于流媒体类的规则。业务参数设置如表2所示。

表2 业务参数表

业务等级的服务时间和等级数量比重如表3所示，根据统计学原理，3种业务等级服务时间的期望之和近似等于等级二所需的服务时间。业务状态分为等待、服务和过期3个状态，过期的业务指的是业务等待时间超过了其k倍的服务时长，根据不同等级业务的时效性将k按照业务等级一、二、三分别设定为0.8、1.2、1.5，过期业务不再进入到请求接入序列中排队，自动判断为传输业务失败。

表3 业务等级表

2.2 结果分析

为验证本文算法的性能，将其与基于距离、时间优先级算法[9]，以及改进的动态优先级控制算法[13]进行对比。基于距离是指基站连接选择方案按照距离大小进行选择，时间优先级指按照业务接入请求的发送时间进行排序，改进的动态优先级控制算法是指在文献[13]的基础上加入了基于距离选择连接基站的部分。

将完成的业务除以这段时间产生的所有业务得到业务完成率，用来衡量算法的业务执行情况。某次仿真结束后得到图4所示的完成率对比图，可以看到70 s之前两种算法的完成率是几乎相同的，这是由于服务序列未完全满队，算法之间的差异并不明显。在服务序列满队之后，按照动态优先级排序的队列业务完成率明显好于时间优先级的队列，这是因为高优先级业务的服务时间较少时，将高优先级的业务提前服务，能避免由于大带宽低优先级的业务长时间占用带宽致使高优先级业务无法接入最终失效的情况。经过50次蒙特卡罗仿真取平均，复合优先级算法和优先级控制算法相比有0.71%的提升，与时间优先级相比有3.85%的提升，这是因为复合优先级的剩余价值和执行紧迫性函数根据不同业务时效性的特点，增大了有效差异的时效性区域，避免了高优先级由于接入请求发送晚，而被低优先级先发送接入请求的业务一直插队的情况。

图4 实时业务完成率对比Fig.4 Comparison of real time business completion rate

图5为仿真时间内两种算法不同业务等级完成数量的对比。

图5 业务等级完成数量对比Fig.5 Comparison of business level completed quantity

在密集业务传输需求的情况下，动态复合优先级算法的业务完成总量明显高于于其他两种算法，经过50次蒙特卡洛仿真取平均后得到，相对于时间优先级算法，本文算法在业务等级一完成量提升了约136.17%，业务等级二的完成量提升了约27.26%，业务等级三的完成量降低了23%，这是由于算法提高了高优先级的服务优先度，牺牲了一部分带宽需求较大的低优先级业务，使得队列快速服务低带宽需求的业务。与动态优先级控制算法相比，本文算法的业务等级一完成量提升了17.59%，业务等级二完成量提升了5.819%，业务等级三完成量提升了11.76%。动态复合优先级算法主动提高高优先级业务的服务时间，也变相提高了整个排队序列的通畅度，使得各个优先级的业务完成率都能有所提升。

图6为不同业务类型完成量对比，业务类型的完成与机动站点的网络参数还有业务类型的带宽有关，流媒体类业务由于所需带宽较大，造成业务完成量较低。通过50次蒙特卡洛仿真后取平均值，相对于时间优先级算法，本文算法在会话类业务完成量提升了约67%，交互类业务的完成量提升了约19.42%，流媒体类业务的完成量降低了21%。会话类业务作为3类业务中带宽需求最小的，当高优先级会话类业务请求时可以快速接入服务且对请求接入排队队列影响最小，所以会话类业务提升最为明显。同样，在牺牲大带宽需求且低优先级流媒体类业务的情况下，才能为高优先级低带宽需求的业务留出相应的服务位置。与动态优先级控制算法相比，由于高优先级业务完成率的提升，相应业务类型的完成率也有所提升，本文所提算法的会话类业务完成量提升了6.5%，交互类业务完成量提升了5.5%，流媒体类业务完成量提升了3%。

图6 业务类型完成数量对比Fig.6 Comparison of number of business types completed

环境参数波动是不可控的，算法的环境适应性体现在从大量多变的机动站点网络参数中提供合适的连接方案，并将连接方案的参数倾向性传递到业务请求接入队列中，因此选用实时的网络参数对波动环境适应性进行衡量。通过图7对比可以看出，VIKOR法在带宽、包延迟、包抖动和丢包率四种冲突参数下，提供的折中方案更倾向于较小的包延迟、包抖动和丢包率，这非常有利于会话类和交互类业务的传输，但这种方案的代价是带宽较小。VIKOR法为业务排序提供了环境权重，能有效促使业务按照适合环境传输的顺序进行排列。

(a) 实时带宽参数对比

图8为3种算法在仿真时间内堵塞率的对比，将请求接入队列中等候接入的业务数量除以满队列的业务数量定义为堵塞率，可以看出，本文算法的实时堵塞率始终处于较低值，其余两种算法均处于较高值。当算法的堵塞率处于满状态时，代表着下一时刻若再生成新的业务，就必定会有业务因网络堵塞而过期，造成业务完成率下降，所以低堵塞率意味着保证了节点服务队列的流畅度，能在一定程度上提升整个通信网络的性能。将图6～图8结合来看，在动态复合优先级提高业务完成率的基础上，结合VIKOR法选择较优参数的机动站点进行连接，业务服务处于良好的网络参数环境下，能使业务服务质量有较好的提升。

图8 实时堵塞率Fig.8 Real time blockage rate

3 结论

针对业务类型和业务等级的时效性特点不突出以及算法对于波动环境适应性不强的问题，本文提出了一种基于VIKOR法和动态优先级的多属性网络接入选择算法。首先用VIKOR法选出合适的网络接入方案，再把方案站点的网络环境参数权重传递给移动节点的业务连接请求队列，结合改进的剩余价值和执行紧迫度建立动态复合优先级模型，最后搭建仿真环境对其性能进行仿真。仿真结果表明，在海上波动环境移动节点基于业务优先级的网络选择场景下，基于动态复合优先级的算法与时间优先级算法和基于动态优先级控制算法相比，在同样保证业务优先级需求的基础上，能够有效提升业务完成率和队列流畅度，提高了整体通信网络的性能。