PROBABILISTIC ROUTING FOR VEHICULAR AD HOC NETWORK

• US 20100080168A1
• Filed: 09/29/2008
• Published: 04/01/2010
• Est. Priority Date: 09/29/2008
• Status: Active Grant

• Current Assignee: Toyota Infotechnology Center Co., Ltd. (Toyota Motor Corporation)
• Original Assignee: Toyota Infotechnology Center Co., Ltd. (Toyota Motor Corporation)
• Inventors: Fukuyama, Junichiro
• Granted Patent: US 7,885,285 B2
• Time in Patent Office: Days
• US Class Current: 370/328
• CPC Class Codes: H04L 45/121 by minimising delays
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• CPC Class Codes: H04W 8/005 Discovery of network devices, e.g. terminals
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

A probabilistic method of determining a second vehicle in the VANET to which a packet is to be forwarded from a first vehicle is provided. The method includes determining the second vehicle to forward the packet from the first vehicle based on pre-calculated expected latency data corresponding to the second vehicle, and forwarding the packet from the first vehicle to the determined second vehicle. The expected latency data is indicative of the latency expected for communication of the packet from the first vehicle to the destination if the packet is forwarded from the first vehicle to the second vehicle, and is calculated in advance of the step of the determining the second vehicle to forward the packet. The second vehicle to forward the packet may also be determined based on pre-calculated communication probability data corresponding to the second vehicle in addition to the pre-calculated expected latency.

Claims

1. In a vehicular ad hoc network (VANET) in which a packet is to be wirelessly transmitted from a first vehicle to a destination, a method of determining a second vehicle among a plurality of vehicles in the VANET to which the packet is to be forwarded from the first vehicle, the method comprising the steps of:

at the first vehicle, determining the second vehicle to forward the packet from the first vehicle based on pre-calculated expected latency data corresponding to the next vehicle, the pre-calculated expected latency data indicative of an expected latency for communication of the packet from the first vehicle to the destination if the packet is forwarded from the first vehicle to the second vehicle, the pre-calculated expected latency data having been calculated in advance of said step of determining the second vehicle during a pre-compute phase prior to run-time; and

forwarding the packet from the source vehicle to the determined second vehicle.

2. The method of claim 1, wherein the step of determining the second vehicle to forward the packet comprises the step of:

applying a utility function to the pre-calculated expected latency data corresponding to a plurality of vehicles in the VANET located within a transmission range of a wireless communication device of the first vehicle to obtain a plurality of real numbers each corresponding to the plurality of vehicles; and

selecting at least one of the plurality of vehicles based on the real number as the second vehicle to forward the packet.

3. The method of claim 2, wherein the utility function ƒ

is f τ

(x, d) where x is a current location of the first vehicle or the plurality of vehicles, d is the location of the destination, τ

(x,d) is the latency of communication from the current location x to the destination d, and at least one of the plurality of vehicles with a smallest value of the latency τ

(x,d) is selected as the second vehicle.

4. The method of claim 2, wherein the second vehicle to forward the packet is determined based on pre-calculated communication probability data corresponding to the second vehicle in addition to the pre-calculated expected latency data, the communication probability data having been calculated in advance of said step of determining the second vehicle during the pre-compute phase prior to the run-time and being indicative of probability that there exists a communication path from the first vehicle to neighbors of the destination within a transmission range of a wireless communication device of the first vehicle, within a predetermined time and within a predetermined number of hops between the vehicles in the VANET, if the packet is forwarded from the first vehicle to the second vehicle.

5. The method of claim 4, wherein the utility function ƒ

is ƒ

=α

τ

(x,d)+(1−

α

)ρ

(x,d,T), where x is a current location of the first vehicle or the plurality of vehicles, d is the location of the destination, τ

(x,d) is the latency of communication from the current location x to the destination d, α

is a positive weight constant less than 1, T is a time limit, and ρ

is a pre-computed communication probability, and at least one of the plurality of vehicles with a smallest value of the real number of the utility function ƒ

is selected as the second vehicle.

6. The method of claim 4, wherein the utility function ƒ

is ƒ

=α

₁τ

(x,d)+α

₂ρ

(x,d,T)+α

₃Δ

(x,d), where x is a current location of the first vehicle or the plurality of vehicles, d is the location of the destination, τ

(x,d) is the latency of communication from the current location x to the destination d, α

₁, α

₂, α

₃ are positive weight constants, T is a time limit, ρ

is the pre-computed communication probability, Δ

(x, d) is the Euclidean distance from the current packet holder x to the destination d, and at least one of the plurality of vehicles with a smallest value of the real number of the utility function ƒ

is selected as the second vehicle.

7. The method of claim 4, wherein the expected latency

8. The method of claim 4, wherein the communication probability corresponding to the second vehicle is determined as a function of hop probabilities corresponding to a plurality of hypothetical positions in the VANET, the hop probabilities indicative of probabilities that the plurality of vehicles will move locations in the VANET.

9. The method of claim 8, wherein the communication probability ρ

(s,d,T) is determined by performing the steps of;

10. The method of claim 8, wherein the hop probabilities are obtained from field data obtained from actual measurements.

11. The method of claim 8, wherein the hop probabilities are obtained from traffic simulations.

12. The method of claim 11, wherein the hop probabilities are obtained by simulating probabilistic movements of vehicles in the VANET using intersection probabilities indicative of cars changing directions at intersections.

13. The method of claim 4, wherein the communication probability data or the expected latency data corresponding to a plurality of locations in the VANET are stored in a look-up table in the first vehicle.

14. A system for use in a vehicular ad hoc network (VANET) in which a packet is to be wirelessly transmitted from a first vehicle to a destination, the system including a processor and a computer readable storage medium storing computer instructions adapted to perform a method of determining a second vehicle among a plurality of vehicles in the VANET to which the packet is to be forwarded from the first vehicle, the method comprising the steps of:

at the first vehicle, determining the second vehicle to forward the packet from the first vehicle based on pre-calculated expected latency data corresponding to the second vehicle, the pre-calculated expected latency data indicative of an expected latency for communication of the packet from the first vehicle to the destination if the packet is forwarded from the first vehicle to the second vehicle, the pre-calculated expected latency data having been calculated in advance of said step of determining the second vehicle during a pre-compute phase prior to run-time; and

forwarding the packet from the first vehicle to the determined second vehicle.

15. The system of claim 14, wherein the step of determining the second vehicle to forward the packet comprises:

applying a utility function to the pre-calculated expected latency data corresponding to a plurality of vehicles in the VANET located within a transmission range of a wireless communication device of the first vehicle to obtain a plurality of real numbers each corresponding to the plurality of vehicles; and

selecting at least one of the plurality of vehicles based on the real number as the second vehicle to forward the packet.

16. The system of claim 15, wherein the utility function ƒ

is ƒ

=τ

(x,d) where x is a current location of the first vehicle or the plurality of vehicles, d is the location of the destination, τ

(x,d) is the latency of communication from the current location x to the destination d, and at least one of the plurality of vehicles with a smallest value of the latency τ

(x,d) is selected as the second vehicle.

17. The system of claim 15, wherein the second vehicle to forward the packet is determined based on pre-calculated communication probability data corresponding to the second vehicle in addition to the pre-calculated expected latency data, the communication probability data having been calculated in advance of said step of determining the second vehicle during the pre-compute phase prior to the run-time and being indicative of probability that there exists a communication path from the first vehicle to neighbors of the destination within a transmission range of a wireless communication device of the first vehicle, within a predetermined time and within a predetermined number of hops between vehicles in the VANET, if the packet is forwarded from the first vehicle to the second vehicle.

18. The system of claim 17, wherein the utility function ƒ

is ƒ

=α

τ

(x,d)+(1−

α

)ρ

(x,d,T), where x is a current location of the first vehicle or the plurality of vehicles, d is the location of the destination, τ

(x,d) is the latency of communication from the current location x to the destination d, α

is a positive weight constant less than 1, T is a time limit, and ρ

is a pre-computed communication probability, and at least one of the plurality of vehicles with a smallest value of the real number of the utility function ƒ

is selected as the second vehicle.

19. The system of claim 17, wherein the utility function ƒ

is ƒ

=α

₁τ

(x,d)+α

₂ρ

(x,d,T)+α

₃Δ

(x,d), where x is a current location of the first vehicle or the plurality of vehicles, d is the location of the destination, τ

(x,d) is the latency of communication from the current location x to the destination d, α

₁, α

₂, α

₃ are positive weight constants, T is a time limit, ρ

is the pre-computed communication probability, Δ

(x, d) is the Euclidean distance from the current packet holder x to the destination d, and at least one of the plurality of vehicles with a smallest value of the real number of the utility function ƒ

is selected as the second vehicle.

20. The system of claim 17, wherein the expected latency

21. The system of claim 17, wherein the communication probability corresponding to the second vehicle is determined as a function of hop probabilities for a plurality of hypothetical positions in the VANET, the hop probabilities indicative of probabilities that the plurality of vehicles will move locations in the VANET.

22. The system of claim 21, wherein the communication probability ρ

(s,d,T) is determined by performing the steps of;

23. The system of claim 21, wherein the hop probabilities are obtained from field data obtained from actual measurements.

24. The system of claim 21, wherein the hop probabilities are obtained from traffic simulations.

25. The system of claim 24, wherein the hop probabilities are obtained by simulating probabilistic movements of vehicles in the VANET using intersection probabilities indicative of cars changing directions at intersections.

26. The system of claim 17, wherein the computer readable medium stores the communication probability data or the expected latency data corresponding to a plurality of locations in the VANET in a look-up table.