Cross-Layer Bandwidth Management and Optimization in TDMA Based Wireless Mesh Networks using Network Coding
Key: Mog10-1
Author: Parag Mogre
Date: August 2010
Kind: @phdthesis
Keywords: Wireless Mesh Networks, IEEE 802.16, WiMAX, Network Coding, Routing, Scheduling, Stream-Oriented Network Coding
Abstract: Wireless Mesh Networks (WMNs) provide a novel network architecture to extend broadband network coverage with low costs. Additionally, we see an increased interest in supporting demanding multimedia applications in next-generation wireless mesh networks. Provision of Quality of Service (QoS) in wireless mesh networks requires end-to-end support for routing packets via a suitable multihop route to the destination. However, in wireless mesh networks, if the medium access control layer does not support mechanisms for QoS support at a per-link level, all efforts for providing end-to-end QoS are futile. Hence, we see a trend towards standards for wireless mesh networks which support QoS at the Medium Access Control (MAC) level on a per-link basis. The IEEE 802.16 standard's mesh mode of operation, the IEEE 802.11s Mesh Deterministic Access (MDA) mode of operation, and upcoming sensor network standards such as the Wireless HART standard, support MAC layer QoS mechanisms. A common feature of these standards is the use of Time Division Multiple Access/Time Division Duplex (TDMA/TDD) for supporting QoS, by enabling the explicit reservation of bandwidth for data transmissions on individual links in the wireless mesh network. This has enabled the setup of wireless mesh networks which are able to support hard QoS guarantees, and are thus viable for supporting the highly demanding multimedia traffic which can be expected in such networks in future. This, makes wireless mesh networks using such standards attractive for network operators who want to extend the reach of their current wired networks, as well as cellular wireless networks to support additional traffic, and at the same time not incur exorbitant additional costs for the infrastructure setup. However, the bandwidth in such wireless mesh networks still remains a scarce resource. Recently, network coding has been investigated as a novel mechanism to permit the saving of valuable bandwidth in such wireless mesh networks for individual transmissions, thereby increasing the traffic carrying capacity of the wireless mesh networks significantly. Beginning from mainly theoretical work, recently we have also seen an effort to investigate the practical gains which can be obtained via deployment of network coding in wireless mesh networks. However, to-date, the practical investigations for deployment of network coding have been limited to wireless mesh networks based on the IEEE 802.11 standard. There have been no significant investigations on the deployment of network coding, and its benefits, in TDMA/TDD based multihop wireless mesh networks. Given, however, the fact that the next generation of wireless mesh networks would be using bandwidth reservation schemes to support advanced multimedia services, it is vital that network coding be investigated in the light of such wireless mesh networks. This work bridges the above gap. In this thesis we first demonstrate that contemporary packet-by-packet approaches to network coding are highly inefficient in reservation based TDMA WMNs. We derive thus design principles for network coding solutions in such WMNs. Based on our design principles we then go on to propose a new paradigm for network coding, Stream Oriented Network Coding (SONC). SONC makes network coding decisions and performs network coding operations at the granularity of streams. The term stream is defined in the context of SONC in this thesis to refer to a aggregation of packets arriving at a relaying node from a given prior hop and going on to the same next hop. This enables SONC to amortize the reservation overhead via network coding operations on a range of packets. We present and analyze means to identify suitable opportunities for SONC and also mechanisms to deploy these. SONC uses distributed mechanisms and a cross-layer approach to achieve its goal. Thus nodes in the WMN can deploy SONC with just local knowledge. However, the effective benefits which can be obtained via deployment of SONC can be further improved with global (WMN-wide) knowledge. Hence in the second half of the thesis we present Centrally Optimized Routing Extensions (CORE) which, as the name suggests, extends the functionality provided by the default routing algorithms in the WMN to enable more opportunities to benefit from SONC. CORE too uses a cross-layer approach and works in close collaboration with SONC. CORE's design is such that the network operator can limit the computational effort to a predefined maximum value, thereby, ensuring that it can be run in near real-time. This enables our CORE to operate in realistic networks with changing traffic demands. To demonstrate the proof-of-concept of our solutions we have implemented these using the IEEE 802.16 standard's mesh mode of operation as a prototype for reservation based TDMA WMNs. Our results show that the WMN can benefit significantly in terms of bandwidth savings and additional traffic which it may support when CORE and SONC are deployed in the network.
View Full paper (PDF) | Download Full paper (PDF)
Official URL

The documents distributed by this server have been provided by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, not withstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.