车载自组织网络中基于位置信息的快速广播方法

1.一种车载自组织网络中基于位置信息的快速广播方法，其特征在于，包括：
所述方法将广播分为十字路口广播和单一路段广播；
不管车辆位于十字路口或是单一路段，该方法都要求事先获知自身的绝对位置信息；
所述方法采用多辆车作为候选转发车辆来减少源点重发次数，同时由车辆根据自己所处的位置，即路口或路段，自适应的选择所应采取的广播机制；十字路口的广播包括：
(1)邻居信息表的建立；
车辆间通过定期交换信标信息来获取邻居车辆信息，信标信息主要包括车辆ID、当前所处位置、路段ID、移动方向、当前速度、加速度信息；当车辆接收到邻居车辆的信标信息后，它自动建立一张邻居信息表或在邻居信息表中增加新的邻居信息或者刷新邻居信息表中已有的该邻居信息；
(2)n当n表Ⅰ n车辆S为广播节点，S根据邻居信息表从计算出的候选转发车辆集合中找到距离路口最近的N+1辆车，然后产生MCAB-I数据包；当收到MCAB-I数据包后，列表中的车辆开始转播信息；为了减少网络冗余，本方法使用缓存机制来避免重复转发：车辆自动建立一张表存储接收过的数据包ID，当车辆接收到数据包后就检查当前列表，判断是否已接收过该数据包，若已经接收过，则丢弃该数据包；同时为了避免MCAB-I数据包中给定的所有候选车辆同时开始转播，发生碰撞，采取退避机制以保证每次只有一辆车来转发信息；方法规定V-1的退避计时器为1T，V-2的退避计时器为2T，依次类推，V-N的退避计时器为N T，其中T代表一个单位时间；广播过程如下：
1)当接收到发送者S发送的MCAB-I数据包后，V-1的退避计时器从1T开始递减，减为
0后成为转发节点，生成新的MCAB-I数据包向各个方向发送；
2)V-2退避计时器从2T开始递减，若在减到0之前未收到V-1转发的数据包，则认为V-1转发数据包没有成功，V-2作为新的转发节点，将MCAB-I数据包向各个方向发送，若在减到0之前收到V-1转发的数据包，则V-2丢弃该数据包，认为本次广播完成，同时V-L也会收到V-1转发的数据包，认为此次广播完成，向S发送ACK确认消息结束本次广播；
3)V-3，…，V-N的退避计时器依次从3T，…，N T开始递减，和上述步骤2)相同，若节点在退避计时器减到0之前未收到列表中前面车辆发送的数据包，则自己成为转发车辆，若收到前面车辆发送的数据包，则认为本次广播完成，同时列表中后面的车辆也会收到该数据包，确定广播完成，不再进行退避等待；V-L收到前面某个车辆转发的数据包后认为广播完成，向S发送ACK确认消息结束本次广播；
4)若(N+1)T之后，S依然没有收到V-L发送的ACK信息，则认为本次广播失败，重新选择下一跳候选转发车辆，进行新一轮的广播；
5)若S在行驶过程中，出现通信空洞问题，即在自己的通信范围内无任何车辆，则仍然定期发送信标信息寻找邻居车辆，直到通信范围内出现候选车辆再进行广播；
(3)n≥Nth时广播方法；
表Ⅱ n≥Nth时MCAB-I数据包格式
当n≥Nth时，广播车辆发送的MCAB-I数据包格式如表Ⅱ所示；其中P-ID(Packet ID)指发送数据包的ID，R-1，R-2，…，R-M为路口处的路段ID(M为路口处的路段数)，V-i-1，V-i-2，…，V-i-Ni(i＝1,2,…,M，Ni是为路段i选择的候选转发车辆的数目)指所选择的路段i的下一跳候选转发车辆的车辆ID，V-i-L(i＝1,2,…,M)为所选择的路段i候选转发车辆中的最后一辆车，用来向广播车辆发送ACK确认信息以确保数据广播成功，Message是所要发送的广播信息；
车辆S为广播节点，S根据邻居信息表从计算出的候选转发车辆集合中为路段i找到距离路口最近的Ni+1辆车，然后产生MCAB-I数据包；当路口处的车辆收到MCAB-I数据包后，根据相关信息进行转发操作；同n若两个或多个路段同时向广播车辆S发出ACK确认数据包，则可能会发生碰撞，这时需要采用退避机制；若(Ni+1)T之后，车辆S依然没有收到V-i-L发送的ACK信息，则认为路段i的转发失败，此时车辆S根据实时路况，再次选择路段i的Ni辆候选转发车辆并生成新的MCAB-I数据包，收到MCAB-I数据包的车辆就检查自己的ID号是否在数据包中，若存在则进入退避等待状态，准备进行转发操作，若不存在则丢弃该数据包；由于此次转发只针对那些没有转发成功的路段，所以广播车辆S在MCAB-I数据包中只需从未转发成功的路段中选取候选转发车辆即可，此时的MCAB-I数据包格式如表Ⅲ所示；
表Ⅲ 部分失败情况下MCAB-I数据包格式
单一路段广播：
(1)数据包格式与等待时间；
MCAB-R方法，即：单一路段的广播方法，是基于接收者的，由于接收车辆需要计算与广播车辆间的距离，所以广播车辆在广播数据包时，数据包中除了含有所要广播的消息外，还需要加入一些控制信息，如自身位置信息、控制参数；此时MCAB-R广播数据包格式如表Ⅳ所示，其中P-ID(Packet ID)指发送数据包的ID，Position指广播车辆的位置信息，R代表广播车辆的传输半径，maxWT是最大等待时间，它是一个控制参数，根据车辆密度自行进行调整，Message是所要发送的广播信息；
表Ⅳ MCAB-R广播数据包格式
MAC Header P-ID Position R maxWT Message
广播车辆广播完MCAB-R，数据包后由接收到该数据包的车辆自行决定是否需要转发，广播车辆不再干预转发车辆的选择，它只负责监听是否有转发成功确认ACK信息，maxWT时间后，若广播车辆仍未收到转发成功确认ACK信息，则再一次调整相关参数重发该广播消息；广播车辆通信范围内的车辆收到MCAB-R数据包后，首先根据数据包内的广播车辆位置信息及自身从GPS获得的位置信息计算出它们之间的距离d，然后通过式(1)计算出自己的等待时间WT：
WT＝k(1-d/R)×maxWT (1)
式中R表示无线传输半径，d表示接收车辆和发送车辆之间的距离，k是一个常数，根据实际情况进行调整，maxWT是最大等待时间；根据该式而知，在R和maxWT值固定的情况下，等待时间WT与车辆间的距离d是成反比的，所以距离广播车辆越远的车辆等待时间越短，最早开始转发，本方法中假设候选转发车辆由远及近的等待时间依次为WT1，WT2，WT3，…，maxWT，且WT1(2)广播过程；
本方法按照广播车辆通信范围内的所有车辆距离广播车辆的距离远近将这些车辆分为三类；第一类是与广播发送车辆S的距离在2R/3到R之间的车辆，第二类是与S的距离在R/3到2R/3之间的车辆，第三类是与S的距离在0到R/3之间的车辆，这些车辆根据自己所属的类别分别采取不同的转播机制；本发明用WT2R/3表示第二类车辆的等待时间，WTR/3表示第三类车辆的等待时间，定义WTR/3＝WT2R/3+maxBACKTIME，其中maxBACKTIME代表最大退避时间；
根据式(1)可知，距离广播车辆不同距离的车辆的等待时间是不同的，所以接收车辆自行组成若干候选转发车辆，根据等待时间的大小依次来转发信息，距离广播车辆最远的车辆等待时间最短，则被选定为第一个转发车辆，次远的车辆被选为第二个转发车辆，依此类推，最近的车辆被选为最后一个转发车辆；由于车辆间距离相对来说比较近，所以前一个车辆转发成功后处于等待状态的候选车辆都能听得到；当最先到达等待时间的车辆转发成功后，紧接着到达等待时间的车辆收到同样的广播信息后，就向源广播车辆发送ACK确认数据包并丢弃此信息，其他车辆收到此ACK数据包后便停止等待，本次转播完成；若最先到达等待时间的车辆转发失败，则后面到达等待时间的车辆就进行转发，直到源广播车辆收到ACK确认信息；为了避免重复转发，同样采取与十字路口广播相同的缓存机制；
广播过程如下：
1)广播车辆S首先广播MCAB-R数据包，S通信范围内的所有车辆收到该数据包后，首先根据相互的位置信息计算自己与S之间的距离，然后按照上述的分类方法确定自己的类别；
2)如果S通信范围内存在第一类的车，那么属于第一类的车辆则根据式(1)计算自己的等待时间WT，并设置计时器初值为WT，计时器开始递减计时；此类车辆进行转发的步骤如下：
(a)距离S最远的车辆等待时间最短，即WT最小，所以它的计时器最先减到0，由于它在计时器减到0之前未收到任何确认信息，便作为转发车辆进行广播信息的转发；
(b)距离S次远的车辆的计时器第二个减到0，若在计时器减到0之前收到了(a)中车辆转发的数据包，则认为转发成功并丢弃该数据包，且在计时器减为0时发送ACK确认信息，其它处于等待中的车辆收到此确认消息后停止等待，认为本次广播完成；若该车辆的计时器减到0时没有再次收到相同的广播信息，则认为前面车辆转发失败，立即作为转发车辆转发数据包；
(c)第三远的车辆的计时器第三个减到0，若在计时器减到0之前第二次收到相同的广播信息，但却没有收到任何ACK确认信息，说明前面车辆在发送ACK确认时出现了信息丢失，此车辆便发送ACK确认消息告知广播车辆及其它车辆，其它车辆收到后立即结束等待，认为本次广播完成；
(d)依次类推，当某一个车辆计时器减到0时未收到重复的广播信息则自己作为转发车辆开始转发，若第二次收到重复的广播信息但却没有收到ACK确认信息则向广播车辆发送ACK确认信息，若在计时器减到0之前收到重复的广播信息并收到别的车辆发送的ACK确认信息就结束等待，认为本次转播完成；
属于第一类的所有车辆都遵循上述转播机制来广播信息或者发送ACK信息，直到本次转播成功；
3)如果S通信范围内不存在第一类的车辆，则在WT2R/3时间后，属于第二类和第三类的车辆都没有收到与S发送的广播信息相同的转发数据包，则认为不存在第一类车；这时候如果存在第二类车，则这些车辆不再进行基于距离的等待转发，而是采用广播中的信道预约方法和退避方法进行争抢转发，从而有效地减少由于等待而引起的不必要的时间浪费；
第二类的车辆在转发之前要进行信道预约，第一个预约到信道的车辆转发数据包，第二个预约到信道的车辆根据是否收到前面车辆转发的数据包来判断是否转发成功；如果该车收到前面车辆转发的数据包则认为转发成功，立即发送ACK确认数据包通知其它车辆和广播车辆，其它车辆收到ACK后停止信道预约或停止计时，本次广播结束；如果该车没有收到前面车辆转发的数据包则认为转发失败，便立即转发广播信息，第二类其它车辆的操作同上，直到S收到ACK信息才结束本次广播；在该广播过程中，第二类的车辆根据预约到信道的顺序依次作为转发车辆；
4)如果WTR/3时间后，第三类车没有收到与S发送的广播信息相同的转发数据包而且也没有监听到信道忙碌，则认为第一类和第二类车均不存在，此时该类车便开始进行争抢转发广播信息，具体步骤和上述步骤3)相同；
5)在广播过程中，广播车辆S一旦收到ACK确认信息就认为本次广播完成，若maxWT之后，S仍未收到任何ACK确认消息或者其它车辆转发的相同广播信息，则认为本次广播失败，重新生成MCAB-R数据包，进行新一轮的广播；
6)若S在行驶过程中，出现了网络分隔问题，则采取携带转发策略，直到通信范围内出现候选车辆再进行广播。
2.根据权利要求1所述的一种车载自组织网络中基于位置信息的快速广播方法，其特征在于：所述十字路口广播的邻居信息表每个记录主要包括：邻居车辆ID(V-ID)、位置(Position)、所处路段ID(R-ID)、路口ID(I-ID)、相对速度(R-Speed)、车间距离(Distance)、时间戳(Timestamp)；邻居信息表中各个字段含义如下：
1)邻居车辆ID(V-ID)：邻居车辆的标识；
2)位置(Position)：邻居节点的位置信息，(x,y)是GPS坐标；
3)所处路段ID(R-ID)：车辆所处路段的标识；车辆通过GPS导航系统查询到自己所处路段的ID；
4)路口ID(I-ID)：车辆通过GPS导航系统知道自己是否处于路口附近，如果车辆处于路口附近，那么将所在路口的ID填入该字段，如不在路口附近，则该字段填入负值；
5)相对速度(R-Speed)：车辆通过信标信息知道邻居车辆的速度，然后计算出自己和邻居车辆的相对速度矢量；
6)车间距离(Distance)：车辆与邻居车辆之间的距离；
7)时间戳(Timestamp)：邻居信息表中创建或更新一条记录的时间；如果一条记录在一个BUP，即：信标信息更新的周期内没有被更新，则从邻居信息表中删除该记录；
当路口处的车辆较少时，每次选择一个转发车辆依次向各个方向的路段进行广播，转发比较慢，效率比较低，而且有的路口可能存在建筑物的遮挡，所以仅一辆车向各个方向进行转发有时候并不能覆盖全部路段；为了提高转发效率和保证覆盖范围，当路口处的车辆比较多时，本方法为每一个路段选择若干个候选转发车辆，这些候选转发车辆只负责向自身所处路段或行驶方向上进行转发，不负责其它方向的转发；这样每一个路段都有多个候选转发车辆，而且这些候选转发车辆互不重叠，因而路口附近向各个方向的转发操作并发执行；每个路段都有若干车辆作为候选转发车辆，每个路段并发的进行各自的转发操作，这样极大的减小了转发时间；在十字路口附近时，相对于n3.根据权利要求1所述的一种车载自组织网络中基于位置信息的快速广播方法，其特征在于，所述的单一路段广播包括：
问题分析与方法描述；
MCAB-I是由广播发送车辆根据位置信息来选择候选转发车辆的，它由发送车辆通过定期与邻居车辆交换信标信息而建立的邻居信息表来选择转发车辆，由于在路口处车辆的行驶速度一般比较慢，信标信息实时准确的进行传送，信标信息更新机制很简单因而本身复杂度很低；但是当广播车辆位于单一路段时，车辆的行驶速度往往很大，在高速行驶时，信标信息的传递往往正确率不高，而且信标信息的字节较多，往往难以获得满意的效果；
而且，车辆高速行驶时，车辆间的相对位置关系变化很快，由于MCAB-R方法是选择在广播车辆的传输范围内且距离广播车辆最远的车辆作为转发车辆，所以选择的转发车辆往往是位于广播车辆传输范围的边界的内侧，车辆B位于车辆A的传输范围的边界，B往往被选择作为转发车辆；由于A在选择转发车辆时是根据前一时刻B通过信标信息发送过来的B的位置信息作为依据的，当A选择好B作为转发车辆后通过MCAB-I数据包的形式告知B，但是经过A→B，B→A这样的一个来回，B的位置很可能已经不在A的传输范围内了；
所以MCAB针对单一路段的情况采用同十字路口不同的转发机制进行广播，当广播车辆位于单一路段时，MCAB-R选择广播车辆通信范围内距离其最远的若干节点来转发广播信息，且不同于MCAB-I的基于发送者的候选转发车辆选择方式，它采用基于接收者的候选转发车辆选择方式，由接收者自行判断是否需要进行转发操作；
该方法不需要车辆间交换信标信息，减少了网络开销和计算复杂度，同时也缩减了时延；MCAB-R是基于车辆间距离来选择候选转发车辆的，需要知道车辆的位置信息，同样地，车辆通过GPS导航系统来获取自身位置信息；广播车辆在进行广播时，将自身的位置信息加入到广播信息数据包中，邻居车辆接收到广播信息后，便计算出其距离广播车辆的距离；
由于车辆在道路上行驶有一定的随机性，所以该方法考虑实际情况，按照广播发送车辆通信范围内的所有车辆距离广播车辆的距离远近将这些车辆分为三类，以期进一步缩减时延。

车载自组织网络中基于位置信息的快速广播方法\n技术领域\n[0001] 本发明涉及车载网络技术领域，特别涉及车载自组织网络中基于位置信息的快速广播方法。\n背景技术\n[0002] 进入21世纪以来，随着汽车数量的不断增加，汽车发挥着越来越重要的作用，随之而来的交通问题也引起了人们越来越多的关注。道路交通事故已经成为全球公共安全问[1]\n题，交通事故因其极强的“杀伤力”被称为“世界头号杀手” ，全球每年约有超过120万人死于交通事故，而中国拥有全世界1.9%的汽车，引发的交通死亡却占全球的15%，交通事故死亡率全球第一。相关研究表明，如果司机能够及时了解周围的交通和车辆情况，并在事故或碰撞发生前获得警告，就可降低至少40%的交通事故。因此，各国竞相大力建设智能交通系统（Intelligent Transportation System，ITS）以期解决道路交通安全问题，缓解交通压力。\n[0003] 在道路安全的紧急需求下，车载自组织网络（Vehicular Ad hoc Network，VANET）作为智能交通系统最具前景的重要研究领域之一应运而生。VANET是道路上车辆间（Vehicle to Vehicle，V2V）或车辆与基础设施之间（Vehicle to Infrastructure，V2I）通过各自配备的无线通信模块相互通信而组成的开放性移动ad hoc网络。VANET利用网络中移动的车辆作为节点来创建移动网络，将每一个参与的车辆变为一个无线路由器或节点，允许车辆在100～300m间相互连接，最终建立了一个大范围的网络。VANET在动态、随机、多跳的网络拓扑[2]中支持完全的移动和应用，是移动自组织网络（Mobile Ad hoc Network，MANET）在特殊情况下的一个分支，具有重要的研究意义。\n[0004] 为了满足驾乘人员对危险警告、协同驾驶、实时路况、娱乐新闻等交通信息的需求，以提高旅途的舒适性和安全性，安全可靠快速的广播协议成为VANET的一个重要研究领域。在VANET中，最简单的广播方法是洪泛广播，即每个收到广播信息的节点都进行广播，这种方式在车辆稀疏的情况下非常有效，但是在车辆密集的情况下，则会引起较高的网[3]\n络冗余，最终形成广播风暴 ；同时大量隐藏/暴露节点的存在也会影响广播信息的可靠分发；而且由于车辆快速移动、节点密度不断变化、网络拓扑频繁变化等因素，传统的广播协议并不适用于VANET。而且，到目前为止，还没有形成一种快速有效并适用于VANET的广播方法，因此，设计出一种有效的并适用于VANET的广播方法具有重大的研究意义和现实意义。\n[0005] UMB和AMB方法都可以解决了隐藏终端问题，减少了广播信息的重复转发，进而避免了广播风暴的发生。但是，它们都是仅选用一辆车作为转发节点，如果本次转发不成功，则广播节点就必须进行重发，大大增加了重发概率，造成平均时延加大；而且，频繁的握手信息的交换不但增加了网络开销也造成了时延的增加。而本发明能更好的解决上述问题。\n发明内容\n[0006] 本发明针对VANET中广播信息发送面临的延迟大、可靠性差等问题，提出了一种车载自组织网络中基于位置信息的快速广播方法MCAB（Multi-candidates-based Adaptive Broadcast Algorithm），该方法在降低时延的同时兼顾了可靠性。\n[0007] 本发明解决其技术问题所采用的技术方案是：本发明提出了一种车载自组织网络中基于位置信息的快速广播方法MCAB（Multi-candidates-based Adaptive Broadcast Algorithm），该方法采用多辆车作为候选转发车辆来减少源点重发次数，同时由车辆根据自己所处的位置（路口或路段）自适应的选择所应采取的广播机制，使得广播方法具有很大的灵活性，从而减小了时延并确保了可靠性。\n[0008] 方法流程：\n[0009] 本发明提出一种车载自组织网络中基于位置信息的快速广播方法，其包括如下：\n[0010] 本发明将广播分为十字路口广播和单一路段广播，不管车辆位于十字路口或是单一路段，都要求事先获知自身的绝对位置信息，所以本发明要求车辆均配备GPS导航系统。\n本发明假设车辆能够通过GPS导航系统获得位置信息、移动方向、当前速度、加速度、路段ID等信息。\n[0011] 假设无线传输半径为R，MCAB规定车辆在距离路口R/2时就认为接近路口，然后开始采用十字路口广播机制。通过车辆自适应的选择相应的广播机制，MCAB方法试图在时延、可靠性及网络开销等方面尽可能的达到一种平衡。\n[0012] 一、十字路口广播方法\n[0013] 在十字路口进行转发时，大部分广播方法都是通过在十字路口安装转发器来进行转发的，从而将十字路口广播方法转换为单一路段广播方法，这种方法虽然也达到了广播的效果，但是却需要大量转发器的安装，硬件设施成本较高。虽然MSB广播方法在十字路口时选用多辆车来依次转发，但是该方法规定所选定的所有车辆都要依次进行转播操作，在节点密度较大或网络环境较好的情况下造成了网络冗余，在节点密度稀疏的情况下，由于缺乏确认机制，容易造成信息的丢失，可靠性下降。\n[0014] 为了减少硬件设施成本，当车辆位于十字路口附近时，MCAB采用基于发送者的机制，发送者从车辆间定期交换的信标信息（beacon message）中获取邻居车辆的位置信息，建立邻居信息表，并从中选择距离路口最近的若干车辆作为下一跳转发车辆的候选者，该方法中由广播发送车辆来决定候选转发车辆的数目和ID，候选转发车辆根据收到的MCAB-I数据包规定的先后顺序进行相应的转发操作。\n[0015] 由于路口有多个不同的路段，而且路口附近的车辆密度也是不断变化的，所以该方法根据路口附近的车辆密度采用不同的转发机制。当车辆数目n小于阈值Nth时，由候选转发车辆分别向各个路段进行转发，当n大于等于Nth时，在每个路段选择若干候选转发车辆来进行转发，每个候选转发车辆只向一个路段进行转发。\n[0016] （1）邻居信息表的建立\n[0017] 车辆间通过定期交换信标消息来获取邻居车辆信息，信标信息主要包括车辆ID、当前所处位置、路段ID、移动方向、当前速度、加速度等信息。当车辆接收到邻居车辆的信标信息后，它自动建立一张邻居信息表或在邻居信息表中增加新的邻居信息或者刷新邻居信息表中已有的该邻居信息。邻居信息表的每个记录主要包括：邻居车辆ID（V-ID）、位置（Position）、所处路段ID（R-ID）、路口ID（I-ID）、相对速度(R-Speed)、车间距离（Distance）、时间戳（Timestamp）等。邻居信息表中各个字段含义如下：\n[0018] 1）邻居车辆ID（V-ID）：邻居车辆的标识。\n[0019] 2）位置（Position）：邻居节点的位置信息，(x,y)是GPS坐标。\n[0020] 3）所处路段ID（R-ID）：车辆所处路段的标识。车辆可以通过GPS导航系统查询到自己所处路段的ID。\n[0021] 4）路口ID（I-ID）：车辆可以通过GPS导航系统知道自己是否处于路口附近，如果车辆处于路口附近，那么将所在路口的ID填入该字段，如不在路口附近，则该字段填入负值。\n[0022] 5）相对速度(R-Speed)：车辆通过信标信息可以知道邻居车辆的速度，然后计算出自己和邻居车辆的相对速度矢量。\n[0023] 6）车间距离（Distance）：车辆与邻居车辆之间的距离。\n[0024] 7）时间戳（Timestamp）：邻居信息表中创建或更新一条记录的时间。如果一条记录在一个BUP（信标信息更新的周期）内没有被更新，则从邻居信息表中删除该记录。\n[0025] （2）n