Joint routing and scheduling via iterative link pruning in Wireless Mesh Networks

The focus of this paper is on routing in Wireless Mesh Networks (WMNs) that results in STDMA schedules with minimum frame length. In particular we focus on spanning tree construction and formulate the joint routing, power control and scheduling problem as a Mixed Integer Linear Program (MILP). Since this is an NP-complete problem, we propose an iterative pruning based routing scheme that utilizes scheduling information. Numerical investigations reveal that the iterative pruning algorithm outperforms previously proposed routing schemes that aim to minimize the transmitted power or interference produced without explicitly taking into account scheduling decisions.