6th International ICST Conference on Broadband Communications, Networks, and Systems

Research Article

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

Download663 downloads
  • @INPROCEEDINGS{10.4108/ICST.BROADNETS2009.7101,
        author={Abdullah-Al Mahmood and Ehab S. Elmallah},
        title={Joint Non-bifurcated Routing and Scheduling in Wireless Grid Mesh Networks},
        proceedings={6th International ICST Conference on Broadband Communications, Networks, and Systems},
        publisher={IEEE},
        proceedings_a={BROADNETS},
        year={2009},
        month={11},
        keywords={wireless mesh networks fixed broadband wireless access non-bifurcated routing dynamic programming},
        doi={10.4108/ICST.BROADNETS2009.7101}
    }
    
  • Abdullah-Al Mahmood
    Ehab S. Elmallah
    Year: 2009
    Joint Non-bifurcated Routing and Scheduling in Wireless Grid Mesh Networks
    BROADNETS
    IEEE
    DOI: 10.4108/ICST.BROADNETS2009.7101
Abdullah-Al Mahmood1,*, Ehab S. Elmallah1,*
  • 1: Department of Computing Science University of Alberta Edmonton, T6G 2E8, Canada
*Contact email: amahood@cs.ualberta.ca, ehab@cs.ualberta.ca

Abstract

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.