STATEFUL SCHEDULING WITH NETWORK CODING FOR ROADSIDE-TO-VEHICLE COMMUNICATION

• US 20090279462A1
• Filed: 05/09/2008
• Published: 11/12/2009
• Est. Priority Date: 05/09/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Lu, Han Cheng, Wu, Feng, Luo, Chong, Chen, Chang Wen, Pu, Wei
• Granted Patent: US 8,687,530 B2
• Time in Patent Office: Days
• US Class Current: 370/310
• CPC Class Codes: H04B 7/15521 combining by calculations packets received from different stations before transmitting the combined packets as part of network coding network coding aspects for detection or prevention of errors in the information received H04L1/0076; network traffic management with optimizing of information sizing, e.g. header compression, by using assembly and disassembly of packets H04W28/065
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04W 28/06 Optimizing the usage of the radio link, e.g. header compression, information sizing , discarding information system modifying transmission characteristic according to link quality by modifying frame length H04L1/0007; dynamic adaptation of the packet size for flow control or congestion control H04L47/365

Abstract

Described is a technology by which a roadside-to-vehicle communication system may be implemented, including via a stateful scheduling with network coding scheme that enhances network capacity. Moving vehicles request and receive data from a roadside access points. Each of the access points operate a stateful scheduling algorithm that serves multiple vehicles by integrating network coding within a timeslot. In one aspect, the state of each vehicle'"'"'s previously received and retained data is obtained, and used to enhance network capacity by combining as many packets as possible for multiple recipients in network coding.

Claims

1. In a networking environment, a method comprising, determining state data corresponding to data already received at a recipient based upon a previous transmission, combining one set of data intended for the recipient and at least one other set of data intended for at least one other recipient based upon the state data into encoded data, and transmitting the encoded data to the recipient.

2. The method of claim 1 wherein determining the state data comprises communicating with the recipient from an access point.

3. The method of claim 2 further comprising, sending the previous transmission from another access point.

4. The method of claim 1 further comprising, receiving information from a server, the information intended for vehicular recipients.

5. The method of claim 1 wherein combining comprises XOR-ing at least two sets of data.

6. The method of claim 1 further comprising, sending a new packet to a first recipient, and changing state information associated with that new packet to indicate that the packet was sent.

7. The method of claim 1 further comprising, detecting a new potential recipient in range of an access point, and communicating with the new potential recipient to obtain state data of that new potential recipient.

8. The method of claim 1 further comprising, communicating with the recipient to determine whether the encoded data was received by the recipient.

9. The method of claim 1 further comprising, receiving a set of data at a recipient, determining whether the set of data was intended for the recipient, and if so, using the set of data, and if not, determining whether the set of data can be used in a decoding process in conjunction with another set of data previously received by the recipient, and if so, performing the decoding process.

10. In a networking environment, a system comprising, an access point, the access point communicating with mobile clients, including to determine which set or sets of data each mobile client has previously received and which set of data each mobile client is requesting, the access point configured to combine different sets of data requested by at least two requesting clients into a common set of data by which a requesting client is able to decode a requested set of data by using the set or sets of data that mobile client has previously received, and to transmit the common set of data to the mobile clients.

11. The system of claim 10 wherein the access point maintains a data structure for each client that indicates the set or sets of data needed by that client.

12. The system of claim 10 wherein the access point maintains a data structure for a plurality of clients that tracks the set or sets of data previously received by each client.

13. The system of claim 10 wherein the access point is couples an infrastructure network containing a server having vehicle-related information to a roadside network containing clients incorporated into vehicles.

14. The system of claim 10 wherein a mobile client receives a given set of data, determines that the set of data was intended for another mobile client, and uses the set of data in decoding process in conjunction with another set of data previously received.

15. The system of claim 10 wherein the access point sends point coordination function-type messages to mobile clients, including a message communication by which an access point determines reception state data corresponding to which set or sets of data a given mobile client has previously received.

16. The system of claim 10 wherein the access point communicates the set or sets of data to a particular mobile client via a unicast communication, and receives an acknowledgement only from the particular mobile client.

17. One or more computer-readable media having computer-executable instructions, which when executed perform steps, comprising:

communicating with a mobile client that is within range of an access point, including obtaining state information from that mobile client that indicates what set or sets of previously-received data that mobile client has retained; and

communicating a combined set of data to that mobile client and to at least one other mobile client, the combined set of data comprising data intended for the mobile client and the at least one other mobile client and being encoded such that the mobile client is capable of decoding the combined set of data into the data intended for the mobile client by using the set or sets of previously-received data that mobile client has retained.

18. The one or more computer-readable media of claim 17 having further computer-executable instructions comprising, maintaining a data structure for each client that indicates the set or sets of data needed by that client, and maintaining a data structure for a plurality of clients that tracks the set or sets of data previously received by each client.

19. The one or more computer-readable media of claim 17 having further computer-executable instructions comprising receiving information from a server, the information including traffic-related data intended for vehicular recipients.

20. The one or more computer-readable media of claim 17 having further computer-executable instructions comprising, tracking state information associated with data packets to determine whether each data packet was previously transmitted or is a new data packet that has not yet been transmitted, including changing the state information associated with a data packet in conjunction with transmitting that data packet.