Coding-based cooperative caching in on-demand data broadcast environments

Data broadcasting has been commonly deployed in many emerging mobile applications such as intelligent transportation systems and location-based services, because it is a scalable approach to disseminating information from a mobile support station (MSS) to a large population of mobile hosts (MHs). To provide timely data access and better data availability, MHs can store data items broadcast by the MSS in their local caches and share cached data items cooperatively among neighboring peers via peer-to-peer (P2P) communication. However, if MHs are not neighbors, they cannot cooperate even if they have each other's requested data items in their own caches. Network coding is a technique, by which multiple MHs can decode out different requested data items from an encoded packet broadcast by the MSS in one broadcast time unit. In this work, we propose a network coding based solution to enable MHs which are not neighbors to cooperate indirectly. We formulate the Maximum Channel Efficiency Encoding (MCEE) problem by introducing network coding and cooperative caching techniques in on-demand data broadcast environments. We prove that MCEE is NP-hard by constructing a polynomial-time reduction from the Minimum Clique Cover (MCC) problem. Further, we propose two schemes (NCM and NCB) for on-demand data broadcasting using network coding. In each scheme, we propose two algorithms running at the MSS and MHs for making encoding decisions and decoding requested data items, respectively. We build the simulation model for performance evaluation and the simulation results demonstrate that the proposed schemes not only increase the bandwidth efficiency of the limited downlink communication channel, but also enhance the system performance by reducing the data access latency.