Joint Non-bifurcated Routing and Scheduling in Wireless Grid Mesh Networks

In this paper we consider multi-hop wireless mesh networks intended to provide Internet connectivity to both end users and hotspots. In such networks mechanisms for provisioning QoS for delay sensitive flows arise as an important topic. In this context, we focus on the non-bifurcated (single path) routing of such flows as a means of allowing all packets in any flow to receive uniformly controlled treatment in each node along the path, thus simplifying routing and management of flows requiring QoS guarantee. In particular, we consider non-bifurcated routing in the class of wireless grid mesh networks (WGMNs). We formalize the problem of joint routing and scheduling of flows that can be best served by non-bifurcated routes as an optimization problem. We then discuss the advantages of solving the problem by a strategy that attempts to route and schedule pairs of flows at each step. Subsequently we propose a dynamic programming algorithm to compute such routes. We evaluate the performance of the proposed algorithm both analytically and by simulation. The experimental results show that the proposed algorithm performs better than two other commonly used competing strategies.