Building Wireless Network Coding Protocols

This work studies how to build wireless network protocols that achieve better reliability, lower delay and higher throughput than existing alternatives by using network coding and by exploiting the broadcast nature of the wireless channel. In the first part collection protocols, protocols used to gather information from a set of sources in a central location, are studied. Three scenaria where network coding helps data collection are discussed. First, network coding is used to reduce the overhead associated with end-to-end headers employed in traditional collection protocols. The main idea is to jointly code messages and identity of their sources using subspace codes. The benefits of the proposed protocol are assessed on a simulated testbed of wireless sensor nodes. Second, network coding is used to implement in-network function computation without requiring specialized operation of the routers. Finally, a complete protocol, SenseCode, is presented. This protocol uses network coding and overhearing as a lightweight alternative to multipath for improved reliability. The protocol performance is tested in a wide range of conditions using a simulated testbed of wireless nodes. The second part of the thesis shows how network coding can be used in broadcast protocols, protocols that are used to distribute information from a set of sources to all the network participants. First, flooding protocols for multi-hop networks are analyzed: the main objective is to improve reliability and reduce delay of this class of protocols. Existing codes and a novel scheme are tested using simulations and on a testbed made of mobile phones. Second, a complete system, MicroCast, that enables a group of mobile devices to receive high rate video content is presented. The system uses collaboratively the long range wireless links that connect each mobile device to the infrastructure and the short range local links that connect the devices among themselves. The system uses network coding and overhearing on the local links to improve the efficiency of utilization of the local radio resources.