Network coding for cooperative data exchange

Abstract

In this thesis we study cooperation between wireless devices with the goal of obtaining more efficiency in bandwidth usage, energy consumption or delay in wireless communication systems. We investigate different networking scenarios. However, all the scenarios have a common framework: we consider a set of messages and a set of clients where each client initially holds a subset of messages (or some side information about the messages) and is willing to cooperate with other clients by exchanging network coded packets to obtain its desired set of messages. The desired set of messages by each client can be any arbitrary subset of messages and possibly the entire set of messages. We refer to this family of problems as the coded cooperative data exchange (CDE) problems. Cooperation between wireless devices can be highly efficient as the short range links between devices are usually faster, cheaper and more reliable than cellular communication links. In the first scenario in this thesis, all clients are interested in the same set of messages and the network is fully connected. We find a polynomial time algorithm to obtain the optimal number of transmissions and maximize the fairness in the number of transmissions by the clients subject to optimality in the total number of transmissions. A more general scenario where clients are interested in arbitrary subsets of messages is also studied. This problem which we refer to as the cooperative index coding (CIC) is an NP-hard problem. We provide a heuristic algorithm to reduce the number of transmissions as well as an analytical approximation on the total number of transmissions required for fully connected networks. We further extend our heuristic to general wireless network topologies. Mobility of the clients is another topic of study in this thesis. Mobility changes the topology of the network over time. We use probabilistic methods to approximate the number of required transmissions in the cooperative data exchange problem by taking the dynamics of the network into account. We propose an energy efficient heuristic algorithm which is based on the idea of encouraging clients with higher connectivity degree to transmit at each time. Finally we propose a system for dissemination of delay tolerant information to a large group of wireless clients spread over a large area, such as a city. The system is highly bandwidth efficient at the service provider side as it broadcasts only a fraction of information to each sub-area (cell) and the clients exchange information while they move arbitrarily over the entire area and across the cells. Several fully distributed algorithms for scheduling transmissions with different objectives are provided and evaluated via extensive numerical experiments. This is also the first study using realistic synthetic human mobility traces in the context of network coded gossiping.