Joint routing and scheduling in multi-Tx/Rx wireless mesh networks with random demands

Abstract

Multiple transmit or receive (MTR) capability is a promising approach that significantly improves the capacity of Wireless Mesh Networks (WMNs). A fundamental problem is deriving a minimal link schedule or superframe that satisfies traffic demands. Existing MTR link schedulers or works that jointly consider routing and scheduling in wireless networks assume traffic demands are known in advance and are fixed. However, in practice, traffic demands are likely to be uncertain. Consequently, any computed solution will lead to either idle slots or congestion. Moreover, uncertain demands may cause a network operator to compute and install a new routing and superframe frequently; this is likely to incur high signaling overheads, especially in large scale multi-hop WMNs. Henceforth, in this paper, we consider random traffic demands characterized by a polyhedral set. We model the problem as a semi-infinite Linear Program (LP). We then propose a novel heuristic algorithm, called Algo-PolyH, that jointly considers both routing and superframe generation to produce a robust solution that is valid for all random demands that belong to a given polyhedral set. This fact is confirmed in our evaluation of Algo-PolyH in networks with varying number of degrees, number of flows, number of nodes and number of paths.