用于高速列车移动网络的资源分配实时算法-AET-电子技术应用

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

来源：电子技术应用2012年第12期

张永晖1,2, 蒋新华1, 林漳希3

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

摘要：误码率高、频繁中断的高速列车移动场景宜采用多宿主容迟网络。但其资源分配计算复杂，实时性较差。基于效用差分法设计初始化过程资源分配算法，以保证过程中每一步的效用单调不减，算法时间复杂度降至O(n)。

关键词： 高速移动网络资源分配算法效用函数容迟网络多宿主

中图分类号：TP393
文献标识码：A
文章编号： 0258-7998(2012)12-0098-03

Real-time resource allocation algorithm on high-speed train mobile network

Zhang Yonghui1,2, Jiang Xinhua1, Lin Zhangxi3

1.Key Lab For Automobile Electronics & Electric Drive of Fujian Province, Fujian University of Techrology, Fuzhou 350108, China； 2. School of Information Science & Engineering, Central-South University, Changsha 410083, China； 3. The Rawls College of Business Admin, Texas Tech University, TX 79409-2101, USA

Abstract：High-speed train mobile scenarios is fitted to adopted multi-homing delay tolerant mobile network, alleviating high error rate and frequent disruptions effectively. However, its resource allocation algorithms on it are of computational complexity and poor real-time. Give an Initialization resource allocation algorithm, and ensure every step utility of processes non-decreasing with utility differential, gains O(n) algorithm time complexity.

Key words :high-speed mobile internet access; resource allocation algorithm; utility; delay tolerant network; multi-homing

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

同时发现，初始化染色体如果随机产生，迭代需要平均158.7次；使用上一轮的优化数据作为下一轮输入，则将降低到23.8次；然而最差仍要迭代89次。由此得到启发，在上一轮历史数据的基础上计算效用的增减，效用增加则接受，效用减少则拒绝。实际上是以局部最优化来逼近全局最优化，从而减小计算量，满足实时应用。
1 算法改良
对初始化和接纳控制的算法实施，如果先排序再满足队列中所有业务i的需求[2],算法时间复杂度为O(nlogn)，因为每次分配之后都要重新排序，计算量依然不小。
为此，使用服务等级来分配带宽，增加服务的子优先级，作为最优选择的一种近似来设计算法。这实际上是使带宽分配离散化，以减少重新计算的费用，避免资源分配调整过于频繁。

效用函数队列调度简化算法描述如下：
Procedure_of_Enhanced_initialize ()
Begin
(1) 按用户i和请求业务j映射最小带宽等级minB(i,j)。按客户实际请求和服务提供商的收费标准升降子等级m。//O(n)
(2) If (Bremainder>0) and (count(3) For j=5 to 0 step -1 //从信令开始分配资源
(4) For m=9 to 0 step -1
(5) For Each e In group (j,m)
(6) If bandwidth (queue) ≥minB(i,j) Then
(7) llocation(bandwidth(queue),e,minB(i,j) //分配资源
(8) bandwidth(queue)=bandwidth(queue) -minB(i,j)
(9) Else
(10) 置标志skip(e)=1;累加器count+1 //将i剔出队列。
(11) End if
(12) Next e
(13) Next m
(14) Next j
(15) End If
End /*首次计算按最小带宽需求分配；类似的，如果带宽有剩余,对队列中所有skip(e)=0从高到底分配边际带宽：+diffj%；如果带宽无剩余，则终止。//算法中的效用可以是用户与服务提供商双方效用函数之和。*/
上述算法对业务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)，并作规律性的停止，从上到下，从左到右。

优化算法相差不大，而各方面均优于N+方案，除新呼叫阻塞率外，也优于S+方案。
这是因为后两者没有针对容迟网络场景做优化，流量没有达到饱和，尤其是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 schedulng 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.

原创声明：此内容为AET网站原创，未经授权禁止转载。

相关内容