用于高速列车移动网络的资源分配实时算法*

张永晖,蒋新华,林漳希

(1.福建工程学院 福建省汽车电子与电驱动技术重点实验室,福建 福州 350118;2.中南大学 信息科学与工程学院,湖南 长沙 410083;3.德克萨斯理工大学 商学院，TX 79409-2101,美国）

针对高速列车移动网络设计了基于容迟网络的多宿主列车移动网络方案，提出资源分配效用模型[1]，然而参考文献[2]中使用基于神经网络的遗传算法，迭代次数较多，不利于实时应用。

同时发现，初始化染色体如果随机产生，迭代需要平均158.7次；使用上一轮的优化数据作为下一轮输入，则将降低到23.8次；然而最差仍要迭代89次。由此得到启发，在上一轮历史数据的基础上计算效用的增减，效用增加则接受，效用减少则拒绝。实际上是以局部最优化来逼近全局最优化，从而减小计算量，满足实时应用。因为每次分配之后都要重新排序，计算量依然不小。

为此，使用服务等级来分配带宽，增加服务的子优先级，作为最优选择的一种近似来设计算法。这实际上是使带宽分配离散化，以减少重新计算的费用，避免资源分配调整过于频繁。

1 算法改良

对初始化和接纳控制的算法实施，如果先排序再满足队列中所有业务i的需求[2],算法时间复杂度为O(nlogn)，

由协议和端口号可得到服务种类j。令Bj,m(j=0～3，m=0～h)表示第j种业务的可用带宽等级,按效用值映射基本带宽子级m，仿真中取 h=9，则 m=0～9。然而 Bj,m与 Bj,m+1总是相差 diffj%(m=0～8)。j=4、5 时，定义为实时通信，没有带宽变化。设Bt为当前网络总带宽，BA为当前网络可用总带宽，定义当前带宽忙闲度：δbusy=INT((h+1)*BA/Bt)，则分给请求 i带宽 Bj,m，业务子级 m=h-δbusy。 网络越繁忙，δbusy越大，从而分配给的带宽子级越小。因此可自适应调节业务子级。 j=5、4 时，依次分派指定带宽；j=3，2，1，0 时，分配Bj,m的带宽。

效用函数队列调度简化算法描述如下：

上述算法对业务i进行分级计算后,划分到group(j,m)。在group(j,m)中不进行排序，而是按照队列或者链表串起来，因此，算法大大改进。虽然有嵌套循环，但实际执行次数不大于 Int(bandwidth(queue)/min(B(i)))，总的算法时间复杂度是O(n)。优于参考文献[2]提出的算法O(nlogn)。

利用效用函数分级的优点在于可以针对每一类业务甚至具体的业务实行不同的策略,以及可让预留信道的阈值精确适应话务量变化，例如对切换掉话率的处理。常规方法是假定掉话用户很难接受，通常优先级设置很高，并以之衡量系统服务质量。然而事实上不同类业务掉线的负效用不一样，同一类业务优先级不同的业务掉线的负效用也不一样，以效用函数不同的参数描述就能有针对性地灵活处理。

2 仿真和分析

使用NS2仿真，比较参考文献[2]的最优化算法、参考文献[3]的 NEMO优化算法（简称 N+）、参考文献[4]的SIP+SCTP+NEMO的方案(简称S+)以及与本文两种算法的性能。模型为两条100 km的正交十字型，采用WiFi小区沿途不完全覆盖,直径为 1 km(站点数 k=20、40、80、140、200)仿真。 速度 350 km/h(v)，并作规律性的停止，从上到下，从左到右。

设WiFi网络带宽为54 Mb/s，蜂窝网络带宽为3.84 Mb/s，假定有 500个 MSj，各类业务的到达时间服从泊松分布，用户的到达相互独立，移动站MSp1请求业务tp精确到 0.1 s。不同的业务组合确定如下:时长 (t0～t4都服从负指数分布,均值 1/μ 分别为3 000 s、100 s、200 s、100 s、200 s)，信令业务 5响应所有请求，因此定 34 kb/s；对于语音固定优先级，取带宽rv-min=12.0 kb/s;取参数Umin=1.5;Uv=4；a=0.1;b=55;c=7。设WiFi网络带宽为54 Mb/s，蜂窝网络带宽为 3.84 Mb/s，假定有 500个 MSj，各类业务的到达时间服从泊松分布，用户的到达相互独立，移动站MSp1请求业务tp精确到 0.1 s。

不同的业务组合确定如下:时长(t0～t4都服从负指数分布, 均值 1/μ 分别为 3 000 s、100 s、200 s、100 s、200 s)，信令业务5响应所有请求，因此定 34 kb/s；对于语音固定优先级，取带宽rv-min=12.0 kb/s;取参数Umin=1.5;Uv=4；a=0.1;b=55;c=7。此外多媒体流网络中传输350 kb/s，Bj4电子邮件类 30 kb/s，数据库类200 kb/s，交互式应用200 kb/s，每一级别正负5%。设资源预取设命中率为0.85，结果见图1～图3。在普通微机上执行实时性对比结果见表1。

可以看出，对于实时性而言，所提出的次优化算法是四种算法中最好的。而执行效率与参考文献[2]中最优化算法相差不大，而各方面均优于N+方案，除新呼叫阻塞率外，也优于S+方案。

表1 算法实时性比较

这是因为后两者没有针对容迟网络场景做优化，流量没有达到饱和，尤其是NEMO成群切换移出WiFi热区时，流量可能下降到0。NEMO方案根据信号和带宽来选择接入基站，之后又争用蜂窝窄带，导致流量改变较为剧烈。新呼叫阻塞率比S+差是因为次优化算法是以切换优先的策略，但两者相差0.05，还可以忍受。

本文提出的实时性资源分配次优算法，用于容迟网络的初始化过程和接纳控制过程，在不明显降低性能的前提下，达到了O(n)算法时间复杂度，能在极端环境下提供移动互联网的实时应用。算法针对路径可预知下的容迟网络环境,如配合GPS路径预测算法，可扩展到一般的容迟网络。

[1]张永晖,蒋新华,林漳希.基于中断和时延效用函数的多宿主分级DTN列车移动网络资源分配模型[J].铁道学报，2010,32(6):15-22.

[2]CHEN L W,TSENG Y C,WANG Y C et al.Exploiting spectral reuse in routing,resource allocation,and scheduling for IEEE 802.16 mesh networks[J].IEEE Transactions on Vehicular Technology.2009,58(1):301-313.

[3]任彦，苏伟，张思东.列车移动网络关键技术的研究[J].铁道学报，2006,28(1):121-124.

[4]Leu Fangyie.A novel network mobility handoff scheme using SIP and SCTP for multimedia applications[J].Journal of Network and Computer Applications.2009,32(5):1073-1091.