On the Role of Network Coding in Uncoordinated Multihop Content Distribution over Ad Hoc Networks

We consider the problem of multihop communication in ad hoc networks. This work was originally motivated by vehicular networks, and has application in numerous fields. The key constraint in such systems is the infeasibility of coordination. Because no single node has global knowledge of the network topology, centralized scheduling of transmissions and routing of packets is prohibitively expensive. We propose instead a simple distributed protocol, based on independent channel access and random network coding. This scheme does not require link level feedback, and nodes need not even track the identities of their current neighbors. Our main result shows that when using this scheme, the end-to-end throughput is identical to the throughput in a one hop network utilizing the same protocol. Thus, in an application requiring uncoordinated communication, network coding enables a multihop network to perform as efficiently as a single hop network. In the context of vehicular networks, in a region of congested traffic a constant throughput can be provided to vehicles arbitrarily far from the base station. In essence, every vehicle can be thought of as a digital repeater, despite the packet losses due to collisions and fading.