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.