How to shuffle and scatter pieces of a puzzle over a metropolitan area

Abstract

We propose a new architecture for broadcasting an enormous amount of information over a large population of users in a typical urban area via multiple base stations for delay tolerant applications. The core idea is that each base station partially broadcasts the information instead of transmitting the whole information. In particular, the large target file is broken into M smaller chunks and is provided to N base stations. Each base station i independently generates M i < M linear combinations of the chunks using random linear network coding (RLNC) techniques and broadcasts it to the users in its coverage area. Users then code and exchange packets in their possession via their short range communication links (e.g. bluetooth). Thanks to the random nature of human mobility patterns, it is expected that after a while, the placement of the users would be mixed enough so that users can obtain sufficient number of chunks to decode the entire file. The proposed architecture provides a fundamentally bandwidth efficient scheme for delay tolerant broadcast applications and has the potential to be implemented in practice. In particular, the proposed approach is completely opportunistic i.e. it does not require any routing algorithm. We evaluate the performance of the proposed architecture via extensive simulations using a well known human mobility patterns simulator.