Integrated Scheduling for Wireless Mesh Networks

Lead Research Organisation: Cardiff University
Department Name: Computer Science

Abstract

Wireless mesh networks (WMN) represent a new networking technology involving wireless devices that are typically fixed at buildings and other infrastructure. These devices act as access points for wireless services such as the Internet. Importantly, the access points may directly connect to each other and forward data to a destination. This is typically an Internet gateway where communication is transferred from wireless to wires/cables. The relaying of data in a WMN causes problems for maintaining quality of service. It is important that data is scheduled sequentially for transfer between pairs of sending and receiving devices because processing within a device cannot occur in parallel. Consequently scheduling ensures that collisions between transmissions do not occur. It also allows data to be routed along paths so that objectives such as latency and delay of data are minimized while fairness between users is maximized. Our contribution will include eliciting the complexities of the underlying communication dynamics in mathematical terms. Collaboration with our project partner (BT plc) will ensure that all relevant engineering issues are incorporated. The research project specifically looks at the problem of creating schedules so that objectives are resolved. Two types of schedules are addressed: those for the user who wishes to transfer data to-and-from a particular access point and those needed to relay data to other access points in the WMN. These scheduling problems are computationally complex and require research based on mathematics and computer science. This will determine the existence of such schedules and their creation using advanced computational methods. The outcome of this research is of particular interest to our project partner who will examine the engineering implications of using the techniques developed in this project for future WMN deployments such as Wireless Cities initiatives.

Publications

10 25 50
publication icon
Allen S (2012) Optimising multi-rate link scheduling for wireless mesh networks in Computer Communications

 
Description Infrastructure Wireless Mesh Networks offer a flexible and cost-effective means to provide broadband access to premises, where instead of a direct wireless connection to a gateway to the Internet, traffic is forwarded over multiple hops between the access points of other users. To maximise the efficient use of the wireless spectrum, each access point needs to coordinate the transmissions from local clients (such as laptops, tablets, mobile devices) and the forwarded traffic from other nodes. The project has developed mathematical models of the problem of efficiently scheduling traffic within mesh networks, and developed algorithms capable of designing and coordinating schedules to optimise traffic performance. Although approximate in nature, the heuristic algorithms proposed are computationally quick yet give near optimal solutions, allowing them to be integrated into the design of network topology and routing. These outcomes have been validated on a range of benchmark problem instances, outperforming other published approaches.
Exploitation Route To synchronise transmissions between wireless devices in mesh network and multi-hop communication systems. Inclusion in future networking technology.



Support for integrated development between computation, operations research and communication systems.
Sectors Digital/Communication/Information Technologies (including Software)

URL http://www.cs.cf.ac.uk/ISforWMN/
 
Description A Step Towards an Intelligent Information Infrastructure (TI3)
Amount £534,918 (GBP)
Funding ID EP/L026074/1 
Organisation Engineering and Physical Sciences Research Council (EPSRC) 
Sector Public
Country United Kingdom
Start 12/2014 
End 02/2017
 
Title model for cycle time transmission 
Description we introduce a model for the optimisation of transmission schedules for infrastructure Wireless Mesh Networks in which data is forwarded through mesh routers from a single Internet Gateway node. The mesh routers receive and aggregate data from local mobile devices and each mesh router has an assigned data allowance to ensure fairness, set depending on its geographical position or the predicted usage patterns. We examined the use of fair and efficient link scheduling for Wireless Mesh Networks and provided an integer program for maximising the throughput allowance for each mesh router in a network given the topology. The model uses a slotted time approach to maximise the throughput within a given number of slots N, thus allowing the network to be split into sub networks for local access to the mesh routers, and back-haul transmissions to the gateway. 
Type Of Material Computer model/algorithm 
Provided To Others? No  
Impact Integration of operational research and study of wireless mesh networks. 
 
Description Gigamobile 
Organisation Queen's University Belfast
Country United Kingdom 
Sector Academic/University 
PI Contribution Development of a successful grant proposal for 5G technologies
Collaborator Contribution Protocols and analysis for cooperation
Impact Papers in preparation.
Start Year 2013