Reliable Packet Delivery Protocol for Geocast Protocol in Disconnected Vehicular Ad Hoc Network

• US 20100060480A1
• Filed: 09/05/2008
• Published: 03/11/2010
• Est. Priority Date: 09/05/2008
• Status: Active Grant

• Current Assignee: GM Global Technology Operations LLC (General Motors Company)
• Original Assignee: GM Global Technology Operations Incorporated (Motors Liquidation Co. GUC Trust)
• Inventors: Mudalige, Upali Priyantha, Bai, Fan
• Granted Patent: US 8,059,012 B2
• Time in Patent Office: Days
• US Class Current: 340/901
• CPC Class Codes: H04L 45/46 Cluster building
• CPC Class Codes: H04W 4/12 Messaging; Mailboxes; Announcements
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• CPC Class Codes: H04W 40/20 based on geographic position or location
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

A method is provided for delivering data messages in an inter-vehicle ad hoc network. The inter-vehicle ad hoc network utilizes a multi-hop routing protocol for storing, carrying forward and distributing a data message to various vehicles traveling along the road. The method includes determining a first cluster consisting of a group of vehicles proximate to one another traversing along a road in a first direction. A determination is made as to which vehicles within the first cluster are trailer vehicles for re-broadcasting messages based on vehicle position within the first cluster. An event is detected in a travel path of the first cluster by one of the vehicles in the first cluster. The event is reported to other vehicles in the cluster. At least one vehicle in a second cluster moving in an opposite direction to the first cluster is detected. The data message is broadcast from the determined trailer vehicles to the second cluster.

Claims

1. A method of delivering data messages in a inter-vehicle ad hoc network, the inter-vehicle ad hoc network utilizing a multi-hop routing protocol for distributing a data message to various vehicles traveling along the road, the method comprising the steps of:

determining a first cluster consisting of a group of vehicles proximate to one another traversing along a road in a first direction;

determining which vehicles within the first cluster are trailer vehicles for re-broadcasting messages based on vehicle position within the first cluster;

detecting an event in a travel path of the first cluster by one of the vehicles in the first cluster;

reporting the event to other vehicles in the cluster;

detecting at least one vehicle in a second cluster moving in an opposite direction to the first cluster; and

broadcasting the data message from at least one determined trailer vehicle to the second cluster.

2. The method of claim 1 further comprises the steps of:

receiving the data message in the second cluster;

determining which vehicles in the second cluster are lead vehicles;

re-broadcasting the data message from the determined lead vehicles of the second cluster to a third cluster of vehicles traversing the direction of the first cluster.

3. The method of claim 1 wherein the trailer vehicles are host vehicles for retaining the data message in a buffer for future broadcast.

4. The method of claim 1 wherein each respective vehicle within a respective cluster periodically transmits a beacon message to neighboring vehicles for identifying its global position.

5. The method of claim 1 wherein vehicle kinematic information is also broadcast within the respective beacon message.

6. The method of claim 1 wherein the number of vehicles in the first cluster identified as the trailer vehicles is an optimal setting value derived from analytical modeling.

7. The method of claim 6 wherein a probability of successfully broadcasting the data message to the second cluster is represented by the formula:

P_s=(1−

(1−

p)^M)²

where M is the number of trailer vehicles in the cluster contaminated with the data message and are re-broadcasting the data message, p is the probability that a respective vehicle in the first cluster traversing along the road in the first direction can reliably relay a data message to a respective vehicle in the second cluster, and P_s is the probability of a successful transmission broadcast from M number of vehicles to the respective vehicle of an oncoming cluster.

8. The method of claim 7 wherein a probability of at least 90% is identified as a successful probability for broadcasting the data message in response to the number of trailer vehicles selected for broadcasting the data message.

9. The method of claim 8 wherein a probability of at least 95% is identified as a successful probability for broadcasting the data message in response to the number of trailer vehicles selected for broadcasting the data message.

10. The method of claim 1 wherein the data message is a slow vehicle ahead warning message.

11. The method of claim 1 wherein the data message is a post crash notification warning message.

12. The method of claim 1 wherein the data message is a traffic congestion message.

13. The method of claim 1 wherein the data message is an accident message.

14. The method of claim 1 wherein the data message is a working zone warning message.

15. The method of claim 1 wherein the data message is a visibility enhancement data message for pedestrians/cyclists.

16. A vehicular multi-hop message dissemination system in a vehicle for providing redundant message packet delivery in an inter-vehicle ad hoc network, the system comprising:

an on-board broadcasting unit including a transmitter and receiver for communicating with other vehicles within the inter-vehicle ad hoc network;

a global positioning system for determining the vehicle'"'"'s position, the vehicle communication system adapted to exchange vehicle position data with other neighboring vehicles for determining whether the vehicle is part of a first cluster; and

a buffer for storing a received data message;

wherein the on-board broadcasting unit further includes a controller for determining whether the vehicle qualifies as a trailer vehicle within the first cluster, wherein when the controller determines the vehicle is a trailer vehicle and when a respective data message is received, then the respective data message is broadcast by the on-board broadcasting unit to at least one leading vehicle in a second cluster traversing along the road in an opposite direction of the first vehicle cluster.

17. The vehicular multi-hop message dissemination system of claim 16 wherein the on-board broadcasting unit further comprises a controller using a broadcast distribution protocol for controlling the broadcast of the data message from trailer vehicle.

18. The vehicular multi-hop message dissemination system of claim 17 wherein the determination of whether a respective vehicle within the first cluster is a respective trailer vehicle is based the position of the vehicle within the first cluster and a respective number of vehicles that are designated as trailer vehicles as determined by the controller.

19. The vehicular multi-hop message dissemination system of claim 18 wherein an optimum number of trailer vehicles used to successfully broadcast the vehicle message is based the following formula meeting a predetermined probability threshold:

P_s=(1−

(1−

p)^MT)²

where M is the number of trailer vehicles in the cluster contaminated with the data message and are re-broadcasting the data message, p is the probability that a respective vehicle in the first cluster traversing along the road in the first direction can reliably relay a data message to a respective vehicle in the second cluster, and P_s is the probability of a successful transmission broadcast from M_T number of vehicles to the respective vehicle of an oncoming cluster.

20. The vehicular multi-hop message dissemination system of claim 19 wherein a probability of at least 90% is identified as a successful probability for broadcasting the data message in response to the number of trailer vehicles selected for broadcasting the data message.

21. The vehicular multi-hop message dissemination system of claim 20 wherein a probability of at least 95% is identified as a successful probability for broadcasting the data message in response to the number of trailer vehicles selected for broadcasting the data message.

22. The vehicular multi-hop message dissemination system of claim 16 wherein the at least one leading vehicle in a second cluster traversing along the road in the opposite direction further comprises:

on-board broadcasting unit including a transmitter and receiver for communicating with other vehicles within the inter-vehicle ad hoc network; and

a global positioning system for determining the vehicle global position,

wherein the on-board broadcasting unit further includes a controller for exchanging vehicle position data with other neighboring vehicles within the second cluster for determining whether the vehicle is part of a second vehicle cluster, the controller further identifying whether the first vehicle is a leading vehicle within the second vehicle cluster for re-broadcasting the data message to a third cluster traversing along the road in a same direction as the first cluster.

23. The vehicular multi-hop message dissemination system of claim 22 wherein an optimum number of lead vehicles used to successfully broadcast the vehicle message is based the following formula meeting a predetermined probability threshold:

P_s=(1−

(1−

p)^ML)²

where M_L is the number of lead vehicles in the second cluster contaminated with the data message and are re-broadcasting the data message, p is the probability that a respective vehicle in the second cluster traversing along the road in the second direction can reliably relay a data message to a respective vehicle in a third cluster, and P_s is the probability of a successful transmission broadcast from M_L number of vehicles to the respective vehicle of an oncoming cluster.

24. The vehicular multi-hop message dissemination system of claim 23 wherein a probability of at least 90% is identified as a successful probability for broadcasting the data message in response to the number of lead vehicles selected for broadcasting the data message.