Joint BATS Code and Periodic Scheduling in Multihop Wireless Networks

Abstract

Batched sparse (BATS) code is a promising technology for reliable data transmission in error-prone environments. A BATS code consists of an outer code and an inner code. It has been shown that a well-designed inner code is critical to the performance of BATS. Though great efforts have been made in the design of inner codes, the impact of scheduling (that determines when inner codes take place at nodes in the path) on inner codes is still unclear. In this paper, we study the joint design of inner code and scheduling in multihop wireless networks. We first introduce a new network utility from which to associate inner codes with scheduling, and formulate the coding constraint and the scheduling constraint using independent sets of a graph. With the utility, the joint design problem is then transformed to a network utility maximization problem under the constraints. We next exploit the property of the proposed optimization problem and reveal the relation between the expected batch transfer matrix rank and maximal independent sets. In the light of their relationship, we propose joint coding and scheduling rules and show that a periodic scheduling can be used to achieve provable performance guarantees. However, under most realistic coding settings, the proposed coding and scheduling problem is NP-hard. In order to meet the practical needs of the implementation, we develop greedy algorithms that attempt to iteratively improve the current best solution. Numerical results show that our algorithms enables us to approach the utilization of multi-hop wireless networks with a relatively low end-to-end delay.

Keywords

• Network coding
• batched sparse code
• network utility maximization
• scheduling