Routing with Minimum Frame Length Schedules in Wireless Mesh Networks

Author

Friderikos, Vasilis ; Papadaki, Katerina

Author_Institution

Centre for Telecommun. Res., King´´s Coll. London, London

fYear

2007

fDate

26-30 Nov. 2007

Firstpage

1

Lastpage

6

Abstract

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.

Keywords

integer programming; linear programming; radio networks; scheduling; telecommunication network routing; time division multiple access; NP-complete problem; STDMA; iterative pruning routing algorithm; minimum frame length schedules; mixed integer linear program; scheduling problem; shortest path rooted spanning trees; wireless mesh networks; Aggregates; Electronic mail; Interference; Iterative algorithms; Mesh networks; Power control; Routing; Scheduling algorithm; Signal to noise ratio; Wireless mesh networks;

fLanguage

English

Publisher

ieee

Conference_Titel

Globecom Workshops, 2007 IEEE

Conference_Location

Washington, DC

Print_ISBN

978-1-4244-2024-7

Type

conf

DOI

10.1109/GLOCOMW.2007.4437801

Filename

4437801