融合斯塔克尔伯格模型的港口吞吐量预测方法

宋凌玉

(集美大学 诚毅学院，福建 厦门 361021)

港口吞吐量既是港口企业管理的目标之一，也是港口设施和经营管理水平的综合性反映[1-2].同时，根据吞吐量预测结果可以确定港口通过能力规模，从而使港口设施能较好地满足未来发展的要求[3].多港口的数据预测算法需先设定所有吞吐量都保持互相独立，再通过与“装箱问题”相似的求解算法完成数据预测[4-5].此算法虽然开销小，但忽略了吞吐量间同步互斥的约束关系[6].本文针对港口吞吐量中的多变量，提出了一种融合斯塔克尔伯格模型的港口吞吐量预测算法.此算法对港口吞吐量中的各项指标进行了分类处理并形成了多个数据子集，将相关数据子集移至相同的某一资源库内，能够有效防止出现港口数据的拥挤现象.实验结果表明，该算法预测能力高于同类算法.

1 港口吞吐量相关知识定义

采用三元组τi=(Ti,Ci,πi)的形式来表示周期多变量吞吐量(Task)i，其中，Ti代表吞吐量的周期，πi代表优先级，Ci代表最坏执行时间.每当一个周期发生时，τi先处于就绪状态，之后发生无释放抖动，每执行一次τi就代表一项吞吐量实例,通常将其用Ji进行表示.吞吐量的相对截止期限与其周期保持一致.

定义1 采用ui表示τi的CPU利用率，等于τi最坏执行时间和周期间的比值结果，将其用等式ui=Ci/Ti表达.周期吞吐量集合Γ={τ1,τ2,…,τn}的执行场所是m个港口共同构成的同构型港口处理器P={p1,p2,…,pm}.其中，p(τi)代表τi所处的港口,τ(pk)代表被分配在港口pk的所有吞吐量集合.此港口总共由q个港口吞吐量Φ={ρ1,ρ2,…,ρq}构成,其中，Θi∈Φ的含义是在τi访问的港口吞吐量中，τi需满足互斥访问条件∀ρs∈Θi.当ρs只是被分配在相同港口并进行吞吐量访问时，应该将其称作局部资源，反之则是属于全局资源.将Ф中局部的资源集合用ФL进行表示,并将全局资源集合用ΦG进行表示.如果τi∈Γ以及其它港口吞吐量不会对同一类型吞吐量进行访问时，则可将τi称作独立吞吐量,同时将Γ内的各项独立吞吐量共同构成的数据集合以Γ′来表示.

吞吐量的访问过程发生阻塞的情况出现在该请求访问期间全局资源被其它的港口锁定的条件下.按照MSRP协议的要求，吞吐量需保持预测状态以等待全局资源.当多个港口吞吐量同时等待某一相同的全局资源时,为防止出现饿死的现象，MSRP选择FIFO预测的方式得以解决.

引理1 假设τj对全局资源ρs进行一次访问所需的时间最长是ξj,s,则满足任意τi∈pk对ρs而进行访问请求的时间最长为

(1)

定义2 预测偏差(Sk)等于此港口吞吐量处于tLCM时间段中的最长预测等待时间跟tLCM的比值.tLCM等于此港口吞吐量周期最小公倍数.

为确保港口具备实时可调度的性质，需保留合理的处理器资源，以此保证该港口无论在何种状态下都可以达到实时吞吐量所需的截止时限标准.由此可见，可以通过减小预测偏差的方法来降低港口的整体资源耗费，从而有效地改善港口的利用率.

定理1 对于任意调度τi∈pk，由其产生的港口可调度性损失和τi对pk形成的预测偏差Sk(i)相等，即

(2)

2 港口吞吐量预测算法

该策略的实现过程为:首先把存在于Γ港口吞吐量冲突的各项数据分到一个数据集合，同时把相同数据子集都划分到同一类型中.当任意选择的吞吐量τ1和τ2对资源ρ1进行访问，同时τ2和τ3对资源ρ2进行访问，那么上述3项吞吐量属于相同的数据子集，结果见图1.

图1 数据预测策略

将Γ′中的数据预测到任何一个港口中都不会造成吞吐量的阻塞现象.可以采用下述递归算法来完成港口吞吐量预测：

(1)假定各港口吞吐量在初始状态下都保持相互独立状态(.indep←TRUE)，并且没有对其进行分组(.link←NONE).

(2)如果各港口吞吐量对应的.link都不是NONE,此时，算法结束；反之，从中选定某一没有进行过分组处理的吞吐量τi(τi.linkisNONE)，对该数据的分组状态进行修改至τi.link←i,之后再判断τi是否要跟其它吞吐量共同对港口吞吐量进行访问.

(3)如果τi和其它某一吞吐量τj同时访问同一类型吞吐量，则将此二吞吐量的状态.indep同时设定成FALSE,把τj的分组状态设定成τi.link,再把τi和τj分组到相同的数据子集内；之后采用递归方法从τj开始重新执行这一步骤.

(4)分析τi和后续的吞吐量是否要对同一类型吞吐量进行访问操作，当需要对同一类型吞吐量进行访问时，便跳转至步骤(3)；反之，跳转到步骤(2).

当上述各项步骤都完成之后，各项.indep值结果都是TRUE的吞吐量便成为独立数据，并共同组成了独立数据子集Γ′，同时.link值相等的各港口吞吐量被分组至相同的数据子集内.由此生成相应的数据子集.本文提出了预测吞吐量方法，如下所示：

引理2 对于任意τi与τj∈τ(pk)在pk上形成的预测偏差是τi和τj各自具有的pk预测偏差相加所得的结果

Sk(i+j)=Sk(i)+Sk(j)

(3)

以矩阵Ux×q来表示x(1≤x≤n)个对港口吞吐量进行访问所需的最长时间.元素ui,s代表第i次τc对港口吞吐量ρs进行访问所需的最长时间，则根据引理1有ui,s=ξc,s.如果ui,s=0,则说明τc未对港口吞吐量ρs进行访问.

(4)

定理2 设Γ—={τa,τb,…,τc}(x=|Γ—|≤n)为算法1获得的数据子集，通过x×q(q是港口吞吐量的数量)阶矩阵Ux×q来表达Γ—对港口吞吐量进行访问所花费的时间.对于从Γ—中拆分得到的任意τi并将其分配至港口pr中,同时其它存在于Γ—中的所有数据被预测到港口pk中(r≠k)，那么Γ——中的剩余吞吐量所产生的港口pk预测偏差为

(5)

(6)

其中，Γ—i=Γ—-{τi};f(d)为矩阵Ux×q第d行对应的港口序号.

3 实验与结果分析

3.1 性能指标

本文采用吞吐量集合接受率来验证预测算法的性能，假定每次实验都会生成N=10 000个随机吞吐量集合，预测算法A最大可以对M个数据集合进行调度，此时算法A对应的吞吐量集合能达到的接受率等于M/N.如果得到的吞吐量集合接受率较大，则说明此算法的效率也相应更高.同时还对比了不同算法所具有的港口平均预测偏差,其定义为：

(7)

3.2 实验分析

港口吞吐量是一个体现港口规模及对港口城市社会影响力的综合性指标，而GDP则是一个较全面反映一个地区经济发展水平的综合性经济指标.因此，在一般情况下，港口吞吐量与国内生产总值之间的关系甚为密切.选取“2007—2017”年舟山GDP与舟山港口吞吐量的资料(见表1)进行分析，关系图见图2.从港口吞吐量与GDP关系分析可知，舟山港口吞吐量与GDP之间的关系很不密切，吞吐量增长速度比GDP的快得多.

表1 舟山历年港口吞吐量与舟山国内生产总值比较

图2 舟山GDP与舟山港口吞吐量之关系

图3显示了在临界区长度等于4以及每项吞吐量具有的临界区数量为2的条件下，港口利用率SU与集合接受率间的关系.从图3中可以看到，不同算法的吞吐量集合接受率与SU之间表现为单调递减的变化关系.当WFD和Syn-aware算法处于SU>0.6的条件下，吞吐量集合将具有不可调度的特征，FMPTSM算法则需满足SU>0.7的条件才会发生吞吐量集合的不可调度现象.对这两种算法进行比较可知，FMPTSM算法具有更大的吞吐量集合接受率.

图3 吞吐量集合接受率与港口利用率之间的关系

图4显示了不同算法性能与临界区长度之间的关系，从图中可以看到各港口吞吐量分别由2个临界区构成，此时SU=0.65.当临界区的长度增大后，需要等待的吞吐量预测时间也会随之增大，此时算法吞吐量集合接受率也会出现下降现象.如果无法将所有的数据子集都分配至相同的港口上时，可以利用FMPTSM算法并结合相关度分析结果对吞吐量进行拆分后再将其分配至相同的港口，所以吞吐量只对特定港口吞吐量进行预测等待，有效降低了预测偏差.

图4 临界区长度和吞吐量集合接受率的关系曲线

4 结语

本文提出了一种融合斯塔克尔伯格模型的港口吞吐量预测算法，通过结合港口吞吐量与数据预测策略，有效避免了在港口间发生阻塞现象，以此增加港口的利用率.同时，本文与其它算法进行对比，结果显示，采用此方法法对港口吞吐量的预测具有比Syn-aware与WFD更高的效率.