基于3G的VANETs数据传输的技术研究

赵凯，李玮瑶

（1.平顶山学院 教务处，河南 平顶山　467000；2.平顶山学院 计算机科学与技术学院，河南 平顶山　467000）

基于3G的VANETs数据传输的技术研究

赵凯1，李玮瑶2

（1.平顶山学院 教务处，河南 平顶山467000；2.平顶山学院 计算机科学与技术学院，河南 平顶山467000）

在车载自组织VANETs中，为解决车辆间通信数据传输不流畅的问题。提出采用3G辅助VANETs的数据传输技术。在无法利用VANETs多跳通信传输数据时，启动3G传输，将此方案命名为3GDD，首先建立数据传输率和数据传输时延的效用函数，利用3G辅助VANETs数据传输实现最大化效用；其次，为了避开优化问题的复杂性，将原始的优化问题变换成整数线性规范问题ILP（integer linear programming problem）；最后通过解决ILP，在不同时刻分配3G预算，并选择最不可能通过VANETs传输的数据用于3G传输。实验结果表明，提出的3GDD与同类的方案相比具有良好的性能。

3G；效用函数；整数线性规划；数据传输率；VANETs

近期，车载自组织网（Vehicle Ad hoc Networks，VANETs）得到极大的关注。在VANETs中，装备传感设备［1-3］，每个车辆就成为强大的移动传感设备，并在其通信范围内其他车辆交互信息。许多应用和服务随VANETs技术不断发展而提出，如交通事故预警、道路安全［4-5］以及智能交通［6］。数据传输在VANETs中扮演着重要的作用，因为几乎所有应用都需要有效的数据传输。数据传输性能包括，数据传输率，传输时延以及吞吐量［7］。本文针对VANETs的数据采集［8］展开分析。在VANETs中，每个车辆产生数据包，并向服务中心CS（Central server）传递。考虑VANETs基础设施的路边接入点APs（Roadside access points）。通过AP接入Internet，服务中心也可接入Internet，保证每个车辆能向Aps传递数据包。

文中提出采用3G辅助VANETs数据传输，为VANETs内车辆提供3G数据通道。同时，存在3G流量的预算限制，并通过3G预算限制从而控制通过3G传输的数据包数量，其目的在于最大化数据传输率同时最小化传输时延。实现这个目标有两个问题：第一，通过3G传输时如何平衡数据传输率与数据传输时延。应当鼓励所有的数据包首选免费的多跳传输，仅当数据包在其TTL内未能成功传输的数据包再选择通过3G传输。通过这种方式，降低因使用3G所带来的费用成本。然而，使用3G传输增加数据传输时延。第二，很难决定从所有的数据包中选择哪些数据包、什么时候用3G传输。

1　系统模型

本节，首先分析网络模型，并定义3G辅助VANETs数据传输模型。

基于基础设施的VANETs主要由3部分组成：移动车辆集V，接入点AP集Φ以及服务中心CS（Central server）。AP间通过有线网络连接。系统中的每辆车均能产生数据包，且数据包的有效时限TTL（Time-to-live）被标识为T。假定所有的数据包具有相同的TTL。数据包的大小均相等。网络需传输的数据包集为P=｛p1，p2，…，pm｝。

系统中所有车辆均配备3G和短距离专用通信技术DSRC，因此，每个车辆能直接通过3G或多跳传输向AP点传输数据包。当两个节点在彼此的通信范围内，就用短距离通信（Short-range communication）。使用3G传输数据时，由于传递时延甚小，可忽略不计。如果采用多跳传输，必须要考虑其传输时延。考虑到3G流量（traffic）费用，假定3G流量预算，并标识为B。设定VANETs网络模型为联系图contact graph G（V，E），其中V表示网络中的节点集，边eij∈E表示两节点i、j间连接线。依据文献［8］的研究，两节点i、j间连接过程服从以连接率λ的泊松分布，连接时间服从指数分布。

此外，系统中的服务中心SC不仅从网络中收集数据，还分配3G预算。为此，SC需通过附加的3G通信从车辆获取当前网络信息。通过这些信息，决策每个数据包的传递概率或在每个时隙内（time slot）3G预算的分配（budget allocation）。假定这些信息远小于数据的尺寸，因此，可不考虑因收集这些信息所消耗3G流量。

2　3GDD的设计

文中提出3GDD方案，以解决数据传输问题。3GDD的主要思想如下：首先依据VANET的contact graph模型，估计的期望值。将原始的优化问题在简化成整数规划ILP（Integer linear programming）问题。通过解决ILP问题，在不同的时隙分配SG预算，然后3GDD选择那些不能通过VANET的多跳传输的数据包，并用3G进行传输。

2.1ILP

本小节首先分析在每个时隙如何估计通过VANET多跳传输数据包的期望值E［Zi］=zi，然后给出ILP的表达式。

为了估计zi，必须去简化网络模型。假定任何两节点i、j的连接率服从平均连接率λ的泊松分布。

Lemma 1：给定接入点集Φ，节点与某接入点AP∈Φ的连接服从|Φ|λ的泊松分布，其中|Φ|表示网络中所有AP的个数。

假定m′i表示直到时隙ti内仍未传输的数据包的期望值，不包括通过在时隙ti内3G传输的数据包。依据Lemma 1，m′i与接点AP连接服从|Φ|λm′i的泊松分布。在时隙ti内传输的数据包期望值zi为|Φ|λm′iτ。显然m′1=m-n1，E［Z1］=Z1=m′1|Φ|λτ。为此，m′i可依据式（1）进行更新：

通过z1可以推导zi，i∈｛1，2，…，s｝。通过这种方式，能够获取U的期望值表达式，其是仅关于ni的函数。ni仅是整数，为此，需将3G辅助数据传输问题定义为整数规划问题：

Definition 3（ILP formulation of 3G-assisted data delivery problem）:依据Definition 2，简化的ILP可表述如下：

文中提出3G辅助数据传输问题的根本目的在于决定什么时候以及哪些数据包应当被3G传输，以致获取最大的数据传输率以及最小的数据传输时延。为此，将此问题归纳为整数规划问题，并通过分枝定界法（Branch and Bound）解决。

2.2启发式算法

为了处理Definition 3定义的ILP表达式，提出基于Tabu search算法［6］的启发式算法。启发式算法的核心思想：从一个可行的初始方法开始，寻找邻居或局部潜在方法，获取优化的方法提高整体的效用U。在描述该算法前，先定义邻居的概念。

Definition 4（neighbor）：两个整数a、b，如果|b-a|＜dmin，则整数a、b称为邻居。dmin为给定距离门限值。对于矢量v，u，如果u中的任何元素v与相对应的元素是邻居，则矢量v，u称为邻居矢量。

启发式算法的具体过程如图1所示。从初始方法开始并从局部候选方法搜索。最初，假定是最优的，其具有较高的效用。接下来，更优化的方法被开发。方法不断迭代，直到在最大的迭代数到达前，返回当前最佳的3G预测分配方案。为了提高性能以及避免已使用过的方法，采用清单tablist记录已遍历的方法。

图1　启发式算法Fig.1　Heuristic algorithms

2.33G传输数据包的选择

通过解决ILP，可以在每个时隙内指定3G预算。依据3G预算，可建立通过3G传输的数据包集。显然，选择那些在VANET中最不可能被传输的数据包是合理的。因此，数据包选择的一个关键问题在于在每个时隙前估计数据包传输的概率。本小节，介绍在时刻t如何估计每个数据包传输的概率。为了描述简单，假定数据包产生的时刻为0。

节点i、j一跳连接率为λi，连接时长服从指数分布，因此，数据包在时间x内能成功从节点i传输到j的概率pij（x）= λije-λijx，x＞0。对于从节点 i到 j的 r跳路由 Υ，定义一跳路径＜e1，…，er＞，其相应的连接概率为＜λ1…λr＞，在时间t的传递概率为：

假定φ表示节点i、j间所有可能路由集，那以数据包在时间t从节点i传递到j的传输概率为：

3　性能分析与仿真

1）仿真参数 在仿真过程使用真实的GPS数据。这些数据来自内蒙古自治区内的士公司的500辆移动数据。每天的平均连接率（average contact rate）约0.58。车辆通信范围R= 300米。产生的数据包数为500个。对于每个数据包，随机地选择源节点。AP数为50，TTL为2个小时。

采用Network Simulator 2.35作为仿真平台来验证3GDD的性能，并用Matlab（R2009b）绘制图，Network Simulator 2.35的具体的仿真参数如表1所示。

表1　仿真参数Tab.1 Simulation parameters

2）影响因素α首先，分析数据传输率的权值α对效用的影响。在仿真过程中，随机选择400的士，α的变化范围为0.4 至0.8，步长为0.2。

图2显示了效用随α的变化情况。从图可知，3GDD在α整个变化范围内具有高的效用Utility。而其他的方案在不同α情况，效用呈现不稳定性。

3）3G预算（3G预算）的影响 在这次仿真中，随机选择400的士，3G预算从100变化至200，步长25。α=0.6。仿真结果如图3，4，5所示。

图2　效用随α的变化情况Fig.2　The utility changes with α

图3　数据传输时延率随3G budget的影响Fig.3　Delay of data transmission rate with 3G budget

图4　数据传输时延随3G budget的影响Fig.4　Effect of time delay for data transmission with 3G budget

从图6可知，E_Random具有最高的数据传输率，这是因为E_Random总是用3G传输数据包，最大化地使用3G。而S_Random的数据传输率最低。3GDD的数据传输率与M_Average和M_Random相类似。这也表明在总的预算一定的情况下，平均分配或随机分布对数据传输率性能影响不大。图6显示了数据传输时延的性能曲线。从图6可知，E_Random的传输时延最高，这是因为其所有的数据包均采用3G传输时。而S_Random的数据传输时延最低。图6与图7进一步证实数据传输率和数据传输时延两性能的关系：通过3G传输可以提高数据传输率，但增加了数据传输时延。图7描述两个性能的综合效用Utility。从图7可知，提出3GDD在整个预算变化范围（100，200）内，具有最好的效用Utility。

图5　效用Utility随3G budget的影响Fig.5　Effect of Utility with the 3G budget utility

图6　数据传输率随节点数目的影响Fig.6　Data transmission rate with the number of nodes affected

图7　数据传输时延随节点数目的影响Fig.7　Effect of data transmission delay with the number of nodes

为了评估车辆数目对系统性能的影响，改变网络车辆数目，使其从100至300变化，步长为50，3G的预测为150，α=0.6。仿真结果如图6～图8所示。

图8　效用Utility随节点数目的影响Fig.8　Effect of Utility with the node number effect

从图6可知，随着车辆数目的增加，数据传输率呈上升趋势。这是因为车辆数目增加，提高了车辆相遇的概率，车辆间的连接率上升。仿真结果与图5类似，E_Random具有最高的数据传输率，而S_Random的数据传输率最低。图7显示的结果与图6相似，进一步表明不论在什么环境下，采用3G传输增加了数据传输时延。不出所料，3GDD的效用在整个变化范围内Utility最好，如图8所示。当车辆数目为450时，S_Random的Utility高于3GDD不超过0.013%。

4　结　论

数据有效传递对VANETs的应用起到重要作用。然而，VANETs有很多数据未能得到有效的传输。为此，提出3GDD方案，在VANETs中采用3G辅助数据的传输，从而提高VANETs的数据传输性能。3GDD通过解决ILP问题，先分配每个时隙的3G预算，再从选择那些难以通过VANETs多跳传输的数据，将这些数据用3G传输。在每个时隙开始，启动数据包的选择，同时依据网络的实时状态选择数据包。通过真实的车辆数据仿真表明，与其他方案相比，3GDD方案具有良好整体Utility。

［1］Li M，Liu Y.Rendered path:Range-free localization in anisotropic sensor networks with holes［J］.IEEE/ACM Trans.Netw.，2010，18（1）:320-332.

［2］Wu K，Tan H，Ngan H，et al.Chip error pattern analysis in IEEE 802.15.4［J］.IEEE Trans.Mobile Comput.，2012，11 （4）:543-552.

［3］Miao F，Jiang L，Li Y，et al.Biometrics based novel key distribution solution for body sensor networks［J］.Conf.Eng. Med.Biol.Soc.，2009:2458-2461.

［4］Farnoud F，Valaee S.Reliable broadcast of safety messages in vehicular ad hoc networks［J］.IEEE INFOCOM，2009:226-234.

［5］Taleb T，Benslimane A，Ben Letaief K.Toward an effective riskconscious and collaborative vehicular collision avoidance system［J］.IEEE Trans.Veh.Technol.，2010，59（3）:1474-1486.

［6］Liu N，Liu M，Cao J，et al.When transportation meets communication:V2P over VANETs［J］.30th IEEE Int.Conf. Distrib.Comput.Syst.，2010:567-576.

［7］Bai F，Stancil D，Krishnan H.Toward understanding characteristics of dedicated short range communications（DSRC）from a perspective of vehicular network engineers［J］.Mobile Comput.Netw.，2010:329-340.

［8］Zhu Y，Bao Y，Li B.On maximizing delay-constrained coverage of urban vehicular networks［J］.IEEE J.Sel.Areas Commun.，2012，30（4）:804-817.

Research on data delivery in VANETs 3G-assisted

ZHAO Kai1，LI Wei-yao2
（1.Teaching Affairs Division，Pingdingshan University，Pingdingshan 467000，China；2.College of Computer Science and Technology，Pingdingshan University，Pingdingshan 467000，China）

Data delivery is significant impact on application of a vehicular ad hoc network（VANET）.In this paper，we explore the problem of 3G-assisted data delivery in a VANET with a budget constraint of 3G traffic.A packet can either be delivered via multi-hop transmissions in the VANET or via 3G.We propose an approach called 3GDD for 3G-assisted data delivery in a VANET.Firstly，we construct a utility function to explore the tradeoff between delivery ratio and delivery delay，which provides a unified framework to reflect the two factors.We formulate the 3G-assisted data delivery as an optimization problem in which the objective is to maximize the overall utility under the 3G budget constraint.Secondly，to circumvent the high complexity of this optimization problem，we further transition the original optimization problem as an integer linear programming problem（ILP）.Finally，solving this ILP，we derive the 3G allocation over different time stages.Given the 3G budget at each time stage，those packets that are most unlikely delivered via the VANET are selected for 3G transmissions. Evaluation results show that our approach outperforms other schemes.

3G；utility function；integer linear programming；data delivery delay；VANETs

TN915.11

A

1674－6236（2016）05-0130-04

2015-03-26稿件编号：201503362

赵 凯（1982—），男，河南平顶山人，硕士，讲师。研究方向：向量机、工作流引擎。