On Minimizing Data Forwarding Schedule in Multi Transmit/Receive Wireless Mesh Networks

Abstract

A key problem in wireless mesh networks is forwarding packets to/from one or more gateways with connectivity to the Internet. In this respect, a short link schedule, which determines the transmission time of links, is critical. To date, existing link schedulers do not consider routers that incorporate advances in multiple input multiple output communications, i.e., interference cancellation and spatial multiplexing. In particular, these routers are able to transmit or receive distinct packets on all their links concurrently as well as deliver multiple packets to a neighbor simultaneously. To this end, we consider the problem of deriving a time division multiple access schedule that forwards packets to their respective destination quickly. We first consider the personalized broadcast problem, which assumes a single gateway and present Algo-PB, a solution that produces a schedule that is within 34.5% of the lower bound, and is 45.5% shorter than those computed by the state-of-the-art algorithms. We then extend the problem to consider multiple gateways. This so-called forest construction problem is modeled as an integer linear program (ILP). We then outline Algo-FC, a novel heuristic that generates a balanced forest by repeatedly picking a node from the heaviest tree and migrating it to another tree if doing so reduces the overall load. Experiment results show that the resulting forest generated by Algo-FC is within 9.1% of the ILP solution.