《电子技术应用》

协作资源分配的无人驾驶车载网链路调度算法

2018年电子技术应用第8期
盛雪丰1,姚宇峰2
(1.苏州信息职业技术学院 计算机科学与技术系,江苏 苏州215000;2.苏州大学 计算机学院,江苏 苏州215000)
摘要: 为了提高无人驾驶车辆自组织网络实时数据传输速率,提升无人驾驶车联网络的吞吐量,提出了一种协作资源分配的无人驾驶车载网链路调度算法。该算法首先构建了基于2-H的协作通信系统,采用价值函数来描述链路速率与所分配资源单元之间的关系,进一步提出无人驾驶车联网络的最大吞吐量方程。接着,为了对通信资源进行合理分配,基于多选择性背包问题,对链路速率进行了调度,并采用穷举搜索法求解无人驾驶车辆节点数量的最佳值。实验仿真结果表明,该算法相比基于分散感知和聚类的车辆网络以及基于信道传输模型优化的车辆网络,在链路速率上分别提升了8.7%和7.4%,网络总吞吐量分别提升了10.6%和12.8%,能够更好地满足无人驾驶车辆网络的数据传输速率要求。
中图分类号: TN297;TP393.0
文献标识码: A
DOI:10.16157/j.issn.0258-7998.174995
中文引用格式: 盛雪丰,姚宇峰. 协作资源分配的无人驾驶车载网链路调度算法[J].电子技术应用,2018,44(8):105-108,117.
英文引用格式: Sheng Xuefeng,Yao Yufeng. Coordinated resource allocation algorithm for unmanned vehicle link scheduling[J]. Application of Electronic Technique,2018,44(8):105-108,117.

Coordinated resource allocation algorithm for unmanned vehicle link scheduling

Sheng Xuefeng1,Yao Yufeng2
(1.Department of Computer Science and Technology,Suzhou Information Career Technical College,Suzhou 215000,China; 2.School of Computer Science,Soochow University,Suzhou 215000,China)
Abstract: To improve the real-time data transmission rate of unmanned vehicle ad hoc network and improve the throughput of unmanned vehicle network, a cooperative resource allocation algorithm for unmanned vehicle network link scheduling is proposed. Firstly, a 2-H cooperative communication system is constructed. The value function is used to describe the relationship between the link rate and the allocated resource unit. The maximum throughput equation of the unmanned vehicle is further proposed. Then, to allocate the communication resources reasonably, the link rate is dispatched based on multi-select knapsack problem, and the optimal value of the number of unmanned vehicle nodes is solved by exhaustive search method. Experimental results show that, compared with the vehicle network based on the distributed sensing and clustering and the optimization of the vehicle network based on the channel transmission model, the proposed algorithm improves the link speed by 8.7% and 7.4% respectively, and the total network throughput is improved respectively 10.6% and 12.8%. The proposed algorithm can better meet the requirements of data transmission rate of unmanned vehicle networks.

0 引言

    随着车辆用户对多媒体服务的需求不断增加,如何实现VANETs的高吞吐量和低延迟性成为了VANETs领域的研究热点[1-5]。然而VANETs的拓扑结构变化迅速,且高速移动性使得车辆与路边单元的之间的链路间歇性中断,这些问题给研究VANETs带来了巨大的挑战。何鹏等[6]提出一种基于分簇的多信道车载网MAC协议,根据专用短程通信标准中控制信道和服务信道的分配,考虑车辆间的无线通信干扰和不同应用的QoS需求, 采用基于竞争的CSMA/CA机制,相邻簇采用不同的服务信道,提升网络延迟及吞吐量性能。王力等[7]提出一种基于多智能体分群同步的城市路网交通控制,以路段的空间占有率为状态建立交通网络状态空间模型, 描述路网中车流的传递关系,提出路网多智能体分群一致算法,可使各路段的空间占有率达到均衡, 减轻局部拥堵, 减少车辆延误时间。廖丹等[8]提出一种车载自组织网络单接口多信道的切换方法,采用不同的报文发送模式,并且给出3种模式之间的动态判定和切换方法,避免了信道切换带来的开销,能够更好地利用信道。GORRIERI A[9]等提出一种基于分散感知和聚类的车辆ad hoc网络,提出一种新型的集群广播协议,通过集群拓扑进行分散感知,并且考虑到实际情况中的不同移动模型,对网络误码率和生命周期的性能进行分析,从而得到性能更佳的车辆网络聚类方案。KARADIMAS P等[10]提出一种车载无线网络信道传输模型,采用非广义平稳非相关散射无线信道,并根据信道的二阶统计特征时空变化,对车载无线网络的传播模型进行优化,提高车载网络的数据达到率及传输效率。

    为了满足VANET在提高多媒体服务时的高吞吐量需求,需要提高V2R和V2V链路的实时通信速率,在本文中针对V2R和V2V链路建立了协作中继通信场景,并对链路速率与所分配资源单元之间的关系进行了讨论,提出了吞吐量优化方程。

1 无人驾驶车载网络系统模型

    在车辆自组网络中,2跳(2-Hop,2-H)的协作中继车载网络不仅信令开销较小且链路控制更简单,因此在本文中采用的车辆网络模型为基于2-H的协作通信系统,如图1中场景1和场景2所示。在场景1和场景2中,都是结合V2V 和V2R两种通信类型,但场景1中一个源车辆节点只能转发数据给一个车辆节点(简称为1T1模型),场景2中一个源车辆节点可以转发数据给多个车辆节点(简称为1TM模型)。1T1模型和1TM模型满足以下要求:(1)都采用IEEE802.11p无线技术的3G LTE(3G Long-Term Evolution)规范[11-12];(2)每个源车辆节点都有与路边单元建立通信链路的能力,并且通过V2V与其他车辆进行通信。(3)V2V和V2R两种通信不会互相干扰。通过1T1模型和1TM模型,当车载网络中某一车辆节点远离路边单元无法与其直接通信时,其数据可通过靠近路边单元的源车辆节点进行转发,从而成功接收数据,并且在车载网络中每一个车辆节点都有机会充当源节点。

tx5-t1.gif

    如图2所示的基于2-H的协作通信系统,包含了1T1模型和1TM模型的情况,假设源节点有Ns个,普通节点有Np个,且在车载网络存活期间数据分组的传输不中断,则源节点i的数据速率vi为:

tx5-gs1-2.gif

其中,BW表示在V2V通信链路中总的无线电资源单元,BWi,j表示在节点i和节点j之间的V2V通信链路中所分配的无线电资源单元,1≤BWi,j≤BW。Hi,j表示在节点i和节点j之间的V2V通信链路中所占用的带宽,SINRi,j表示当i作为发射节点时j的信号与干扰加噪声比。

tx5-t2.gif

    对于普通节点j,其速率集合为Vi,j={vi,j|1≤BWi,j≤BW,1≤j≤Np},包括了BW×Np个元素,每一个元素表示对应于所分配资源单元的V2V链路速率,采用一个价值函数Cost(·)表示链路速率与所分配资源单元之间的关系:

    tx5-gs3.gif

    反过来在所分配资源单元为BWi,j时速率为vi,j,则用以下关系式表示:

    tx5-gs4.gif

    并以最大化所有节点的吞吐量为目标,可以将优化问题建模为:

     tx5-gs5.gif

    对于最大化吞吐量的优化问题,如何对V2V链路进行中继节点选择及资源分配,将在下一节中采用动态优化算法进行讨论。

2 链路调度算法

    为了优化资源分配进行链路调度,本节提出采用多选择性的背包问题来提升整体网络的吞吐量。根据多选择性的背包问题[10],本节通过3个步骤来进行V2V链路的资源分配:

    (1)对于普通节点,构造速率集合Vi,j

    tx5-gs6.gif

其中,vi,j表示在源节点i和普通节点j之间的V2V链路中当分配BWi,j资源单位时普通节点j的数据速率。考虑所有的速率作为一个组,BW作为资源单位总数量。对于普通节点j,最多只能从集合Vi,j选择一个速率,对于每个Vi,j的元素,都具有相应的价值BWi,j,为了最大化数据吞吐量,提出吞吐量优化方程:

     tx5-gs7.gif

    (2)通过基于多选择背包问题的调度算法来求解优化问题。算法的伪代码为:

tx5-dm1.gif

tx5-gs8-9.gif

    最佳的Np值可以通过穷举搜索法求得。

3 实验结果

    在实验中,对车载网络环境的模拟采用的是OPNET Modeler14.5通信仿真实验平台,该平台在主频4.0 GHz、内存4 GB的DELL计算机上运行。在仿真平台上同时采用交通和通信模拟器,并且交通模拟器实时发送车辆信息到通信模拟器。表1列出了车载网络的主要参数与配置。模拟的道路场景如图3所示,在一个半径为2 km的圆形区域内,3条道路进入交叉路口,两条道路离开交叉路口,道路的宽度均为18 m。假设在该网络空间中车辆的运动是无事故、连续且离散性的,根据经典的跟驰理论,在仿真实验中车辆的运动采用了车辆稳定跟驰行驶时的车头间距模型。

tx5-b1.gif

tx5-t3.gif

    图4显示了在车辆节点数量变化条件下的车辆节点平均数据速率。从图中可以看出,随着车辆节点数量的增多,平均数据速率逐渐降低。由于路边单元的数量固定,并且路边的发射功率不变,数据传输速率不变,而随着车辆节点数量的增加,源节点和普通节点同时增多,V2R和V2V链路的平均速率都会逐渐下降。本文采用基于协作资源分配的车载网络链路调度算法,通过对资源单元分配的优化以及普通节点数量的最佳选择,提升网络总的数据速率。文献[9]提出的分散感知和聚类的广播协议通过优化拓扑结构来提升网络通信质量,但聚类的方法使得V2V链路的平均传输速率降低。文献[10]提出了车载无线网络信道传输模型,但该模型提出的非相关散射的数据传输方案在提高V2R和V2V链路的平均数据速率上并没有起到作用。从实验结果来看,本文算法的平均数据速率相比另外两种算法提高了5%以上。

tx5-t4.gif

    图5显示了在车辆节点数量变化条件下的网络吞吐量情况,从图中可以看出,随着车辆节点数量的增多,网络总的吞吐量逐渐增大。其中,本文算法为了最大化数据吞吐量,通过吞吐量优化方程对不同数据速率的资源单位进行配置,再基于多选择背包问题的调度算法对普通节点数量的选择进行优化,因此对提高网络总的吞吐量具有明显的增益作用。文献[9]的算法通过集群拓扑结构提高了网络数据的流通量,但平均的数据传输速率低于本文算法,因此网络总吞吐量约为本文算法的89.4%,而文献[10]的算法提升了信道传输的误码率性能,但对提升网络总吞吐量的增益来说较小。

tx5-t5.gif

4 结论

    为了提高无人驾驶车辆自组织网络的数据速率和吞吐量,本文基于对网络V2R和V2V通信链路的模拟中继通信场景的构建,提出了2-H的协作通信系统。在该系统的基础上,以最大化所有节点的吞吐量为目标,对系统V2V链路进行了中继节点选择及资源分配的分析,提出了吞吐量优化方程。为了进一步求解出优化方程中的节点速率和最佳普通节点数量,根据求解多选择性背包问题的思路,采用了调度算法和穷举搜索法得到最佳值。通过采用OPNET Modeler14.5通信平台进行仿真实验所得出的结果可以看出,在提高链路数据速率和网络总吞吐量上,基于协作资源分配的车载网络链路调度算法发挥出了较好的效果。

参考文献

[1] 张扶桑,金蓓弘,汪兆洋,等.基于轨迹挖掘的公交车自组织网络路由机制[J].计算机学报,2015,38(3):648-662.

[2] FRANCOLIN C C,RAO A V,DUARTE C,et al.Optimal control of a surface vehicle to improve underwater vehicle network connectivity[J].Journal of Aerospace Computing Information & Communication,2012,9(1):1-13.

[3] 周毅喆,罗守山.基于免疫理论的车联网的城市路网实时容量研究[J].北京邮电大学学报,2015(1):71-75.

[4] 冯慧芳,孟玉如.基于移动模型的车载自组织网络连通特征[J].计算机应用,2015,35(7):1829-1832.

[5] RICHARDSON P C,ELKATEEB A,SIEH L.An adaptive real-time intravehicle network protocol for intelligent vehicle systems[J].IEEE Transactions on Vehicular Technology,2004,53(5):1594-1606.

[6] 何鹏,阎保平,李志,等.CM-MAC:一种基于分簇的多信道车载网MAC协议[J].计算机研究与发展,2014,51(3):502-510.

[7] 王力,李岱,何忠贺.基于多智能体分群同步的城市路网交通控制[J].控制理论与应用,2014,31(11):1448 -1456.

[8] 廖丹,孙罡,杨晓玲,等.车载自组织网络单接口多信道的切换方法[J].电子科技大学学报,2015(2):227-232.

[9] GORRIERI A,MARTAL?魹 M,BUSANELLI S,et al.Clustering and sensing with decentralized detection in vehicular ad hoc networks[J].Ad Hoc Networks,2015,36(P2):450-464.

[10] KARADIMAS P,MATOLAK D.Generic stochastic modeling of vehicle-to-vehicle wireless channels[J].Vehicular Communications,2014,1(4):153-167.

[11] ABBAS T,TUFVESSON F.Line-of-sight obstruction analysis for vehicle-to-vehicle network simulations in a two-lane highway scenario[J].International Journal of Antennas & Propagation,2013,58(4):455-461.

[12] 贺然,张钢,刘春凤,等.车载网络中基于移动轨迹预测的快速邻居发现算法[J].计算机应用研究,2015(9):2737-2741.



作者信息:

盛雪丰1,姚宇峰2

(1.苏州信息职业技术学院 计算机科学与技术系,江苏 苏州215000;2.苏州大学 计算机学院,江苏 苏州215000)

继续阅读>>