Achieving high-rate multi-hop data delivery in vehicular networks

• US 8,169,897 B2
• Filed: 09/21/2009
• Issued: 05/01/2012
• Est. Priority Date: 09/19/2008
• Status: Active Grant

• Current Assignee: Telcordia Technologies Incorporated (Telefonaktiebolaget LM Ericsson)
• Original Assignee: Telcordia Technologies Incorporated (Telefonaktiebolaget LM Ericsson)
• Inventors: Guha, Ratul K., Chen, Wai, Chennikara-Varghese, Jasmine, Demers, Stephanie
• Primary Examiner(s): Pham, Chi
• Assistant Examiner(s): RIYAMI, ABDULLA A
• Application Number:
  US12/563,420
• Publication Number:
  US 20100074114A1
• Time in Patent Office: 953 Days
• Field of Search: 370/238, 370/328, 370/315, 370/252, 370/254, 370/400, 370/225, 370/226, 370/227, 370/228, 370/310, 370/316, 370/229, 370/230, 370/237, 455/456.1, 455/7, 455/8, 455/11.1, 455/12.1, 455/13.1, 455/73, 455/575, 701/115, 701/117, 701/118, 701/119, 701/210, 701/209, 701/300, 701/70, 701/202, 701/200, 701/201, 340/435, 340/438, 340/902, 340/903, 340/905
• US Class Current: 370/229
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/125 based on throughput or bandwidth
• CPC Class Codes: H04L 45/44 Distributed routing
• CPC Class Codes: H04L 67/12 specially adapted for proprietary or special-purpose networking environments, e.g. medical networks, sensor networks, networks in vehicles or remote metering networks

Abstract

A method for high rate data delivery in a multi-hop vehicular network comprises at each source vehicle, initiating a packet having a flow tag, assigning an identifier of the content and the current location to the flow tag, and forwarding the packet; at each destination vehicle, setting a flow request and broadcasting at the current intersection; further on movement, setting the flow request at the new intersection, and at each intersection, selecting a header vehicle at the intersection, computing backlog and congestion indicators and listening for broadcasts with a matrix and the flow requests at the header vehicle, determining if the matrix is present, updating the matrix in accordance with the backlog and congestion indicators if the matrix is present, initializing the matrix and estimating the delay on the outgoing road segments if the matrix is not present, forwarding the packet flow, and broadcasting the matrix from the header vehicle.

Claims

1. A method for high rate data delivery in a multi-hop vehicular network having a plurality of vehicles and a plurality of intersections, said method comprising steps of:

at each source vehicle;

initiating a packet having a flow tag;

assigning an identifier of a content and a current location to the flow tag; and

forwarding the packet;

at each destination vehicle;

setting a flow request and broadcasting at a current intersection, the flow request associated with a packet requesting a next hop in the network; and

on movement of the destination vehicle, setting the flow request at a new intersection;

at each intersection;

selecting a header vehicle at the intersection;

computing a backlog indicator and a congestion indicator and listening for broadcasts with a matrix and the flow requests at the header vehicle, the matrix including an estimated delay for one or more outgoing roadways from the intersection and one or more data flow rates, the backlog indicator associated with a data flow backlog and the congestion indicator associated with congestion of data flows;

determining if the matrix is present;

updating the matrix in accordance with the backlog and congestion indicators if the matrix is present;

initializing the matrix and estimating the estimated delay if the matrix is not present;

forwarding the packet; and

broadcasting the matrix from the header vehicle.

2. The method according to claim 1, wherein the step of forwarding at the source vehicle is done without knowledge of destination location or recipient information.

3. The method according to claim 1, wherein the step of selecting is performed based on random countdown and vehicle ID.

4. The method according to claim 1, wherein the step of broadcasting is performed when the header vehicle leaves the intersection and periodically thereafter.

5. The method according to claim 1, wherein the matrix includes the backlog indicator and a forwarding component.

6. A non-transitory computer readable medium having computer readable program for operating on a computer for high rate data delivery in a multi-hop vehicular network having a plurality of vehicles and a plurality of intersections, said program comprising instructions that cause the computer to perform the steps:

at each source vehicle;

initiating a packet having a flow tag;

assigning an identifier of a content and a current location to the flow tag; and

forwarding the packet;

at each destination vehicle;

setting a flow request and broadcasting at a current intersection, the flow request associated with a packet requesting a next hop in the network; and

on movement of the destination vehicle, setting the flow request at a new intersection;

at each intersection;

selecting a header vehicle at the intersection;

computing a backlog indicator and a congestion indicator and listening for broadcasts with a matrix and the flow requests at the header vehicle the matrix including an estimated data dissemination delay for one or more outgoing roadways from the intersection and one or more data flow rates for data flows outgoing from the intersection, the backlog indicator associated with a data flow backlog and the congestion indicator associated with congestion of data flows;

determining if the matrix is present;

updating the matrix in accordance with the backlog and congestion indicators if the matrix is present;

initializing the matrix and estimating the estimated delay if the matrix is not present;

forwarding the packet; and

broadcasting the matrix from the header vehicle.

7. The non-transitory computer readable medium according to claim 6, wherein the step of forwarding at the source vehicle is done without knowledge of destination location or recipient information.

8. The non-transitory computer readable medium according to claim 6, wherein the step of selecting is performed based on random countdown and vehicle ID.

9. The non-transitory computer readable medium according to claim 6, wherein the step of broadcasting is performed when the header vehicle leaves the intersection and periodically thereafter.

10. The non-transitory computer readable medium according to claim 6, wherein the matrix includes the backlog indicator and a forwarding component.