Reliable packet delivery protocol for geocast protocol in disconnected vehicular ad hoc network

• US 8,059,012 B2
• Filed: 09/05/2008
• Issued: 11/15/2011
• Est. Priority Date: 09/05/2008
• Status: Expired due to Fees

• Current Assignee: GM Global Technology Operations LLC (General Motors Company)
• Original Assignee: GM Global Technology Operations LLC (General Motors Company)
• Inventors: Mudalige, Upali Priyantha, Bai, Fan
• Primary Examiner(s): Lee; Benjamin C
• Assistant Examiner(s): TANG, SIGMUND N
• Application Number:
  US12/204,850
• Publication Number:
  US 20100060480A1
• Time in Patent Office: 1,166 Days
• Field of Search: 340/539.1, 340/902, 340/995.13, 701/19, 370/270, 370/328, 370/230
• US Class Current: 340/902
• 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;

selecting at least one of the vehicles within the first cluster as a trailer vehicle, the trailer vehicle being a vehicle in a back of 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 a plurality of other vehicles in the cluster by the vehicle detecting the event;

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

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

receiving the data message in the second cluster; and

determining which vehicles in the second cluster are lead vehicles for re-broadcasting the received data message.

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

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 a number of vehicles in the first cluster identified as trailer vehicles equals an optimal setting value derived from analytical modeling.

7. The method of claim 6 wherein the optimal setting value is derived from the following formula based on a target probability:

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 target probability expected to achieve a successful transmission from M number of vehicles to the respective vehicle of an oncoming cluster.

8. The method of claim 7 wherein the target probability is at least 90%.

9. The method of claim 8 wherein the target probability is about 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, the trailer vehicle being a vehicle in a back of 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 derived from the following formula based on a target probability:

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 target probability.

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 derived from the following formula based on meeting a target probability:

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 target probability.

24. The vehicular multi-hop message dissemination system of claim 23 wherein the target probability is at least 90%.