Routing with Minimum Frame Length Schedules in Wireless Mesh Networks

In this article we focus on constructing routing paths in Wireless Mesh Networks (WMNs) that optimize STDMA scheduling. The optimal joint scheduling and routing problem is formulated as a Mixed Integer Linear Program (MILP). The chief difficulty is that this is an MV-complete problem, which naturally invites a study for suboptimal solutions. To this end, an iterative pruning routing algorithm is proposed that explicitly takes into account scheduling information in a STDMA WMN to construct shortest path rooted spanning trees. The pruning algorithm outperforms previously proposed routing schemes, which aim to minimize the transmitted power or interference produced without explicitly taking into account scheduling decisions.