车载网中多信道报文分割传输算法

胡玉睿， 张文军

(1. 重庆化工职业学院， 重庆 400020; 2. 上海交通大学 电子信息与电子工程学院， 上海 200240)



·计算机技术应用·

车载网中多信道报文分割传输算法

胡玉睿1， 张文军2

(1. 重庆化工职业学院， 重庆 400020; 2. 上海交通大学 电子信息与电子工程学院， 上海 200240)

为了保证通信质量，提出一种多信道报文分割传输算法。首先根据可用服务信道(SCH)数量对报文进行分割，然后利用各个SCH来传输报文。考虑到由于部分信道未被使用和部分车辆不可达所导致的报文丢失现象，采用随机线性网络编码来对报文进行编码，并根据信道可用概率和车辆可用概率提出算法来确定需要增加的报文数量。仿真实验结果表明，该算法的可靠性高、信道使用量低，有效地缓解了车辆密度较低所导致的连接性较弱的问题。

车载网； 多信道； 分割传输； 报文丢失； 网络编码； 可靠性

0 引 言

车载网络(Vehicular Ad-Hoc Networks, VANETs)是车辆间通信及车辆和路边基础设施通信的重要手段[1-2]。VANETs标准[3-4]支持6个服务信道(SCHs)和1个控制信道(CCH)。车辆在SCH间隔期间可以加入6个服务信道中的任意一个信道。另外，所有车辆必须在CCH间隔期间加入CCH信道，以便传输或接收安全信息。此外，来自所有车辆的信标信号利用该信道进行广播。VANETs可帮助车辆将各种信息发送给其他车辆或司机。如果通过一个信道传输多媒体数据等大量信息，很容易造成控制信道拥塞。一种避免拥塞的可行方法是通过多个信道传输多媒体信息[5]。然而，车辆密度较低时多信道连接性较差，增加了多信道数据传输的难度[6]，如果这一问题不解决，将导致通信失败。

使用多信道进行报文传输是VANETs的研究热点。文献[7]提出一种面向QoS保证的报文传输方案。车辆在其通信范围内形成一个簇，选择一个车辆作为簇头，其余车辆作为簇成员接受簇头车辆的控制。簇头车辆为其他成员车辆分配信道，使多个信道得到有效共享。然而该方案需要专门的簇建立和维护协议，控制开销较大。文献[8]提出基于有向天线的多信道使用算法，实现了空间重用率最大化，降低了报文延时。但是，为了利用多个信道的有向天线，多个车辆间需要就使用的信道和方向进行协调。文献[9]提出一种基于分簇的多信道混合型MAC协议，簇内通信采用非竞争的TDMA机制，簇间通信采用基于竞争的CSMA/CA机制，相邻簇采用不同的服务信道。然而该协议要求所有车辆广播数据，所以信道中的报文存在冗余。文献[10]针对VANETs中由于多信道传输需要进行信道切换导致控制信道起始处的同步冲突问题，文中利用车辆节点估算信道占用率并计算发送概率，对控制信道的传输机制进行规划，为安全消息和业务信道预约消息等设置不同优先级，然后进行自适应信道负载分散，提高了报文传输质量。但是该方法需要两个无线传输接收器来侦听控制信道中的报文，这在真实的VANETs应用场景中是不可行的。针对以上方法的不足，本文采用随机线性网络编码技术，提出了一种面向多信道的报文分割传输算法。该算法可在保证系统可靠性的前提下，将每个信道用于传输报文的带宽量降到最低，有效地缓解了车辆密度较低所导致的连接性较弱的问题。

1 算 法

首先分析面向多信道的报文分割传输算法所面临的挑战，然后考虑到车辆密度低、连接性低等因素所导致的报文丢失问题，通过新增网络编码报文来预测被丢失的报文，最后给出算法的伪码表示。

1.1 挑 战

分割传输算法若要取得成功，所有SCH中的所有分割报文均应被成功传输。下面通过一个简单实验来分析设计分割传输算法面临的挑战。设在某一测试场景中，车辆按照不同密度分布于10 km道路上，车辆中报文的传输范围设置为300 m。分割传输算法每次运行时，随机选择一个源车辆广播6个多媒体报文。广播后，所有车辆切换到6个服务信道中的某一个信道。成功接收到报文的车辆称为中继车辆，中继车辆需要转发信道中的报文。如果每个信道中的每个报文均被成功转发到另一车辆上，则这次运行视为成功。成功率定义为成功次数与总仿真次数之比。图1中的测试结果表明，当车辆密度较大时，分割传输算法的成功率较高。然而，当车辆密度较低时，成功率也较低。因此，开发出在车辆密度较低或者没有车辆的条件下仍可有效运行的算法，具有重要意义。

图1 成功率比较

造成这种现象的因素有两个：部分信道未被使用(UC)和部分车辆不可达(UV)。信道未被占用，表示部分信道中没有中继车辆存在。因为车辆随机选择服务信道，所以可能存在中继车辆只存在于部分信道中的情况，这是密度较低时成功率较低的主要原因。成功率较低的另外一个原因是车辆不可达。之所以出现车辆不可达情况，是因为中继车辆占据所有6个信道后，在中继车辆传输范围内没有其他车辆。因此，中继车辆无法利用信道传输报文。图2描述了信道和密度不同时关于所有车辆的连接丢失率。当车辆传输范围内没有其他车辆时，认为发生一次连接性丢失。当车辆位于一个信道时(1ch)，连接性丢失率较低。然而，当车辆分布于6个信道时(6chs)，连接性丢失率上升。从图2可以看出，即使在一个信道条件下车辆之间连接性较高(CCH间隔)，在多信道间隔期间(SCH间隔)，车辆与相邻其他车辆间的连接性开始丢失。因此，分割传输算法需要处理低连接性问题。

图2 连接丢失率比较

1.2 丢失报文的弥补

由于部分信道未被使用和部分车辆不可达导致部分信道内的报文未被传输，这些报文称为丢失报文。但是具体而言，信道中的车辆很难知道其他信道中哪些报文被丢失。因此，难以准确预测被丢失的报文。最坏情况下，大部分带宽将被浪费在无法弥补其他信道报文丢失问题的无用报文上。为此，本文采用网络编码来解决这一问题。因为网络编码可使报文共享其他报文的内容，当部分报文丢失时，可利用被成功接收的其他报文来恢复丢失信息。鉴于这一特点，可以增加每个信道中的报文数量，不用考虑其他信道丢失哪些报文就可恢复报文。具体而言，本文采用一种随机线性网络编码技术[11]。在该技术中，发送方从Galois域随机选择系数，进行报文和系数的线性组合。接收方接收到足够多的报文和已知系数后进行解码操作。下式给出了随机线性网络编码的基本操作，

(1)

1.3 新增网络编码报文

虽然通过随机线性网络编码生成额外报文可以恢复丢失报文，但是本文研究的一个核心问题是到底应该为原来的报文生成多少个额外报文。当不需要额外报文时，每个信道中发送的报文数量为Mbase。

(2)

式中：R为多媒体信息初始报文总数；N为信道数量。

考虑连接性丢失情况后，本文需要处理的报文数量多于Mbase个。为了确定需要增加的报文数量M，本文考虑两个因素：信道可用性概率和车辆可用性概率。其中，信道可用性概率表示车辆占用一定数量信道的概率。车辆可用性概率表示车辆位于其他车辆传输范围内的概率。

(3)

(4)

(5)

(6)

(7)

(8)

(9)

1.4 算法实现

设带有多媒体安全信息(报文)的车辆，是其他相邻车辆的数据源。源车辆在CCH间隔中以成功率ρ发送一定数量的编码报文。成功接收到广播报文的车辆成为中继车辆。中继车辆在SCH间隔内根据成功率ρ，决定新添多少个额外报文。为了确定将被广播的报文数量，中继车辆需要利用信道可用性概率Φ，车辆可用性概率Ψ，以及要求的成功率ρ，算法如下。

算法1：为给定的成功率ρ确定数量M。

R←初始报文总数

R←信道总数

Vt←相邻车辆总数

M←R/N

γ←N

γ←γ-1

endwhile

returnM

endprocedure

根据算法1，中继车辆增加每个信道中需要发送的报文数量，直到它达到成功率要求ρ为止。SCH间隔结束后，车辆进入CCH。然后，车辆开始通过收集其他车辆拥有的编码报文来恢复原始信息。为了缓和共享过程中的车辆冲突，采用文献[12]中的智能广播算法。在该算法下，距离源车辆最远的车辆具有最小的竞争窗口，且优先权更高。

2 性能评估

2.1 仿真设置

本文使用ns-3仿真器来评估算法性能。实验场景设置为：车辆行驶在同向双车道10 km道路上。在每1 km处测量被中继传输的报文数量。在原点(0 km位置)生成报文，然后被车辆中继传输，直到报文到达终点(10 km位置)。多媒体信息为12 Mb。每个报文的有效负载是1 kb，传输速度是3 Mb/s。源车辆在一个CCH间隔发送12个报文。以3 Mb/s速度传输时，这12个报文占用CCH间隔70%以上的时间。将SCH数量N设置为6。车辆移动的平均速度为80.467 2 km/h(50英里/h)，标准差为8.046 72 km/h(5英里/h)。

2.2 实验结果

从3个角度分析算法的性能：可靠性、每个信道被占用的带宽和间隔的使用。因为需要把报文传输给很远距离之外且当时并不可用的路边单元，所以可靠性是我们的主要指标。为了衡量可靠性，测量成功到达每个测量点的报文数量，并将其称为报文到达率。选择基本的分割传输算法(BDD)和单信道算法(SC)作为比较对象。BDD算法根据信道数量分割报文，然后把分割后的报文发送给每个信道。该算法没有考虑采用网络编码和增加额外的报文。SC算法在SCH间隔期间只使用一个信道。本文算法称为改进后的分割传输算法(EDD)，在该算法下，车辆根据仿真开始时明确的ρ，计算每个信道需要传输的报文数量M。

报文到达率取决于接收车辆的信噪比(SNR)，以及发送车辆通信范围内的接收车辆数量。因为无线信道中的报文被随机丢失，所以如果车辆的信噪比类似，那么报文到达率是通信范围内车辆数量的函数。当通过广播方式传输报文时，车辆数量对报文丢失率具有重要影响。当部分信道中没有车辆接收到报文时，本文算法通过利用网络编码来有效提升报文到达率。图3给出了每个测量点的报文到达率。如果在SCH间隔传输报文时没有考虑已经下降了的车辆密度，那么数据传输的可靠性较低。三种算法中，BDD的报文到达率最低。SC算法优于BDD算法，但是车辆密度较低时可靠性较好，如图3(a)所示。SC算法的可靠性较差，是因为在选择的信道内缺乏接收报文的车辆。然而，在EDD算法中，虽然信道中部分报文未被中继传输，但是其他信道中仍有报文被成功中继传输。EDD算法利用网络编码策略成功传输这些报文，因此可靠性优于其他算法，如图3(b),(c)所示。当ρ增加时，EDD算法的可靠性也会增加，原因是在信道中增添了更多额外报文来缓解车辆密度较低时导致的连接性较弱的问题。

(a) 30辆/km

(b) 50辆/km

(c) 70辆/km

图3 不同车辆密度下的三种方案的报文到达率比较

图4(a)给出了信道传输一个报文的时间与SCH间隔持续时间的比值。从该图可以看到，对于EDD算法而言，当车辆密度增加时，需要传输的额外报文的数量下降，这表明EDD算法提高了信道的利用率。当车辆密度不变时，增加ρ，车辆需要传输更多的报文，系统的可靠性增加，但总的来说EDD算法占用的SCH间隔要低于SC算法。这主要是因为EDD算法通过随机线性网络编码可以改变待传输的报文数量，而SC算法每个信道的报文数量固定。此外，尽管BDD算法在SCH期间使用的资源最少，但BDD的可靠性最低(见图3)。因此，当路边单元和源车辆距离较远时，BDD算法便无法发挥作用。

图4(b)表明，传输数据时使用的CCH数量较低。为了验证这一点，将本文算法与只使用CCH间隔的算法(CO)和单信道算法(SC)做比较。在CO算法中，只在CCH间隔发送报文。SC算法和本文算法还利用了SCH间隔，所以CCH使用量低于CO算法。这表明，与CO算法相比，这些算法在CCH间隔可以为信标信息传输等安全应用提供更多带宽。另外还可以看到，SC算法的间隔使用量低于EDD算法。原因是EDD算法需要在CCH间隔共享报文，而不像SC算法那样将报文转发给距离最远的车辆。然而，EDD车辆可在SCH间隔采用多跳转发策略。对于SC算法，传输大量报文会占据被选择信道的大部分带宽，因此用于多跳转发的带宽很少。对EDD算法，报文数量低于SC算法，使车辆可以采用多跳转发策略。在图4(b)中，双跳EDD算法的CCH间隔使用量低于其他两种算法。

(a) 占用的带宽

(b) 使用的间隔

图4 不同方案的信道使用量比较

3 结 语

多信道报文分割传输算法，可实现多媒体紧急信息的快速稳定传输。为了避免VANETs的控制信道过载，多媒体内容被分割到可用的服务信道中，因此每个服务信道中的流量负载降到最低水平。然而，如果车辆密度很低，那么连接性丢失问题将会比较严重。为此，在信道生存概念中引入网络编码技术，在增加可靠性的同时，降低服务信道的带宽使用量。最后的仿真实验也验证了多信道报文分割传输算法的有效性。在下一步工作中，我们将针对VANETs中现有的报文转发方案在可靠性、安全和隐私保护等方面的不足，研究一种面向隐私保护的报文转发方案。

[1] 罗 娟, 肖 仪, 卢 真, 等. 基于网络编码的多播车载网路由算法研究[J]. 计算机研究与发展, 2015, 48(9): 1616-1622.

[2] 张 宇, 陈 晶, 杜瑞颖, 等. 适于车载网安全通信的高效签密方案[J]. 电子学报, 2015, 43(3): 512-517.

[3] Ros F J, Ruiz P M, Stojmenovic I. Acknowledgment-based broadcast protocol for reliable and efficient data dissemination in vehicular ad hoc networks [J]. IEEE Transactions on Mobile Computing, 2012, 11(1): 33-46.

[4] Wang Q, Leng S, Fu H,etal. An IEEE 802.11 p-based multichannel MAC scheme with channel coordination for vehicular ad hoc networks [J]. IEEE Transactions on Intelligent Transportation Systems, 2012, 13(2): 449-458.

[5] Wasef A, Shen X. EMAP: Expedite message authentication protocol for vehicular ad hoc networks [J]. IEEE Transactions on Mobile Computing, 2013, 12(1): 78-89.

[6] Dua A, Kumar N, Bawa S. A systematic review on routing protocols for vehicular ad hoc networks [J]. Vehicular Communications, 2014, 1(1): 33-52.

[7] Su H, Zhang X. Clustering-based multichannel MAC protocols for QoS provisionings over vehicular ad hoc networks [J]. IEEE Transactions on Vehicular Technology, 2014, 56(6): 3309-3323.

[8] Xie X, Huang B, Yang S,etal. Adaptive multi-channel MAC protocol for dense VANET with directional antennas[C]// 6th IEEE Consumer Communications and Networking Conference(CCNC). Las Vegas, NV, United States: IEEE Press, 2009: 1-5.

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

[10] 张 伟, 刘南杰, 赵海涛. VANET 多信道传输中控制信道冲突缓解算法研究[J]. 计算机研究与发展, 2015, 25(6): 73-83.

[11] Swapna B T, Eryilmaz A, Shroff N B. Throughput-delay analysis of random linear network coding for wireless broadcasting [J]. IEEE Transactions on Information Theory, 2013, 59(10): 6328-6341.

[12] Amoroso A, Marfia G, Roccetti M. Going realistic and optimal: A distributed multi-hop broadcast algorithm for vehicular safety [J]. Computer Networks, 2011, 55(10): 2504-2519.

Research on Packets Split Transmission Algorithm for Multi-channel in Vehicular Ad-hoc Networks

HUYu-rui1,ZHANGWen-jun2

(1. Chongqing Chemical Industry Vocational College, Chongqing 400020, China; 2. School of Electronic Information and Electrical Engineering, Shanghai Jiaotong University, Shanghai 200240, China)

In order to guarantee the communication quality, a packets split transmission algorithm for multi channel is proposed. First, the packets are split by the number of the available service channels (SCH), and then the split packets are transmitted by using the SCH. Considering the packet loss due to the unoccupied channel and the unreached vehicle, the random linear network coding is used to encode the packets, and the algorithm can be used to determine the number of packets to be added according to the available probability of the channel and the available probability of the vehicle. The simulation results show that the proposed algorithm has the higher reliability and the lower channel usage, and can effectively alleviate the weak connectivity problems when the vehicle density is low.

vehicular ad-hoc networks; multi-channel; split transmission; packet loss; network coding; reliability

2015-10-29

国家自然科学基金重点项目(61420106008/F0102)

胡玉睿(1979-)，女，陕西宝鸡人，硕士，讲师,研究方向为车载网、智能信息处理。

张文军(1963-)，男，山东人，教授，博士生导师，研究方向：车载网、智能信息处理。

E-mail:1715847023@qq.com

TP 393

A

1006-7167(2016)08-0111-05