Project Description

Wireless Mesh Networks


Project Overview


BWN-Lab Personnel


Project Description


Publications


Testbed


BWN-Lab Research Projects

Classical WMN Research	Cognitive WMN Research
WMNs Network Architecture Characteristics Application Scenarios Physical Layer Medium Access Control Network Layer Transport Layer Application Layer Cross-Layer Approaches	Spectrum Sensing And Sharing Channel-Aware Cross-Layer Routing

Classical WMN Research

WMNs Network Architecture

WMNs consist of mesh routers and mesh client nodes. Other than the routing capability for gateway/repeater functions as in a conventional router, a mesh router contains additional routing functions to support mesh networking. To further improve the flexibility of mesh networking, a mesh router is usually equipped with multiple wireless interfaces built on either the same or different wireless access technologies. Compared with a conventional router, a mesh router can achieve the same coverage with much lower transmission power through multihop communications. Optionally, the medium access control protocol in a mesh router is enhanced with better scalability in a multi-hop mesh environment. Two types of mesh client nodes exist in WMNs, namely, Type I nodes with equivalent functions of a mesh router and Type II nodes with simpler functions than a mesh router.

The general case for WMNs is shown in the figure, because both Type I and II mesh client nodes are supported. Again, certain functions must be added into mesh routers to provide access for Type II mesh clients, and thus the hierarchical architecture is still needed. In addition, a Type I client node can establish direct mesh communications with mesh routers and other Type I clients nodes.

Back to Top

Characteristics

The characteristics of WMNs are as follows:

Multi-hop wireless network
Support for ad Hoc networking, and capability for selfforming, self-healing, and self-organization
Mobility dependence on the application domains and on the radios
Providing both backhaul access to external networks and peer-to-peer (P2P) communication within the internal network
Dependence of power-consumption constraints on applications
Compatible and interoperable with other wireless networks

Back to Top

Application Scenarios

Some of the applications of WMNs are as follows:

Broadband Home Networking: Mesh networking is needed to resolve the location of the access points problem in home networking.The access points must be replaced by wireless mesh routers with mesh connectivity established among them. Therefore, the communication between these nodes becomes much more flexible and more robust to network faults and link failures.
Building Automation: Access points are replaced by WMNs and thus the deployment cost will be significantly reduced. The deployment process is also much simpler due to the mesh connectivity among wireless routers.
Enterprise Networking:When WMNS are used, multiple backhaul access modems can be shared by all nodes in the entire network, and thus improve the robustness and resource utilization of enterprise networks. WMNs can grow easily as the size of enterprise expands.
Metropolitan Area Networks:Compared to cellular networks, wireless mesh MANs support much higher data rates, and the communication between nodes does not rely on a wired backbone. Compared to wired networks, e.g., cable or optical networks, wireless mesh MAN is an economic alternative to broadband networking, especially in underdeveloped regions. Wireless mesh MAN covers a potentially much larger area than home, enterprise, building, or community networks

Security Surveillance Systems:As security is turning out to be a very high concern, security surveillance systems become a necessity for enterprise buildings, shopping malls, grocery stores, etc. In order to deploy such systems at locations as needed, WMNs are a much more viable solution than wired networks to connect all devices.

Back to Top

Physical Layer

The key functions of physical layer techniques involve two aspects: efficient spectrum utilization and robustness to interference, fading, and shadowing. In order to increase capacity and mitigate the impairment by fading, delay-spread, and co-channel interference, antenna diversity and smart antenna techniques can be used in WMNs. Open Research Issues

It is still necessary to further improve the performance of physical layer techniques. Multiple-antenna systems have been researched for years. However, their complexity and cost are still too high to be widely accepted for WMNs.

To best utilize the advanced features provided by physical layer, higher layer protocols, especially MAC protocols, need to be re-designed. Otherwise, the advantages brought by such physical layer techniques will be significantly compromised.

Back to Top

Medium Access Control

MAC protocols for WMNs have the following differences compared to classical counterparts for wireless networks:

MAC for WMNs is concerned with more than one hop communication.
MAC is distributed and cooperative and works for multipoint-to-multipoint communication.
Network self-organization is needed for the MAC.
Mobility affects the performance of MAC.

For single-Channel MAC, there are three approaches: (i) improving existing MAC protocols, (ii) Cross-layer design with advanced physical layer techniques, and (iii) proposing innovative MAC protocols. A multi-channel MAC can be implemented on several different hardware platforms, which also impacts the design of the MAC. A multi-channel MAC may belong to one of the following categories: (i) multi-Channel single-transceiver MAC, (ii) multi-channel multi-transceiver MAC, and (iii) multi-radio MAC.

In WMNs, the end-to-end throughput falls greatly with increasing path length. In this project, a Fair End-to-end Bandwidth Allocation (FEBA) algorithm is devised to solve this problem. FEBA is implemented at the Medium Access Control (MAC) layer of single-radio, multiple channels IEEE 802.16 mesh nodes, operated in a distributed co-ordinated scheduling mode. FEBA negotiates bandwidth among neighbors to assign a fair share to each end-to-end trafÞc ßow through the following steps:

First, bandwidth is requested and granted in a round-robin fashion where heavily loaded links are provided with a proportionally higher amount of service than the lightly loaded links at each round.

Second, by keeping separate queues at each node for each traversing traffic flow, this tackles effectively the spatial bias problem found in other types of WMNs, like those based on IEEE 802.11 devices. Differentiated service is also provided by serving traffic flows proportionally to their priority.

FEBA is able to react promptly to short-term variations of the trafÞc load in the network, because it is implemented in a fully distributed manner, thus, it does not incur the overhead of signaling towards/from a centralized node.

With FEBA each node X maintains two virtual queues towards any of its neighbors, say Y : the requesting queue and the granting queue. The occupancy of the former, i.e., the requesting queue, is the total amount of backlogged bytes directed to Y . On the other hand, the total amount of data enqueued at node Y directed to node X is the occupancy of the granting queue. Both these queues are assigned weights so that the amount of service is proportional to number of trafÞc ßows under service, weighted based on their priorities. These weights decide how often the queue is served and through a modified round robin algorithm, which packets are to be transmitted are identified. FEBA is completely de-centralized, has an order of O(1) complexity, and its implementation is easy.

Publications

C. Cicconetti, I. F. Akyildiz and L. Lenzini, ``FEBA: A Bandwidth Allocation Algorithm for Service Differentiation in IEEE 802.16 Mesh Networks'', to appear in IEEE Transactions on Networking, 2008.

Back to Top

Network Layer

IP has been accepted as a network layer protocol for many wireless networks including WMNs. However, routing protocols for WMNs are different from those in wired networks and cellular networks. Since WMNs share common features with mobile ad hoc networks, the routing protocols developed for them can be applied to WMNs. Despite of the availability of several routing protocols for MANETS, the design of routing protocols for WMNs is still an active research area because the existing routing protocols treat the underlying MAC protocol as a transparent layer. However, the cross-layer interaction must be considered to improve the performance of the routing protocols in WMNs. The routing protocol for WMNs must capture the following features:

Performance Metrics.
Fault tolerance with link failures.
Load Balancing.
Scalability.

Open Research issues

Although many routing protocols exist, several challenging research issues need to be resolved. Scalability is the most critical question in WMNs. Hierarchical routing protocols can only partially solve this problem due to their complexity and difficulty of management. Thus, new scalable routing protocols need to be developed. Existing performance metrics incorporated into routing protocols need to be expanded. Moreover, how to integrate multiple performance metrics into a routing protocol so that the optimal overall performance is achieved is a challenging issue. Routing for multi-cast applications is another important research topic. Cross-layer design between routing and MAC protocols is another interesting research topic.

Back to Top

Transport Layer

In WMNs, due to multihop and ad hoc features, one of the critical problems causing TCP performance degradation is the network asymmetry which is defined as the situation in which the forward direction of a network is significantly different from the reverse direction in terms of bandwidth, loss rate, and latency. The packet loss rates and latencies may be the sources for asymmetry in WMNs because the TCP data and ACK packets may take two different paths with different packet loss rates and latencies. Even if TCP data and ACK packets may take the same path, their actual packet loss rates and latencies may be significantly different due to the unfairness in the link layer protocol and in the large variation of measured RTTs (Round Trip Times). Open Research issues

To improve TCP performance in WMNs, there is a need to design new schemes based on differentiation between packet losses due to congestion or due to errors. The critical issue of TCP over WMNs is the network asymmetry. To resolve this issue, cross-layer optimization is a challenging but an effective solution, since all problems of TCP performance degradation are actually related to protocols in the lower layers.

Back to Top

Application Layer

Applications determine the necessity to deploy WMNs. Thus, to discover and develop innovative applications is the key to success of WMNs. Application Layer Protocols consist of management protocols that maintain operation and monitor performance of WMNs.

Network Management: Many functions are performed in a network management protocol. The statistics in the MIB (management information base) of mesh nodes, especially mesh routers, need to be reported to one or several servers in order to continuously monitor the network performance. Data processing algorithms in the performance monitoring software on the server analyze these statistical data and determine potential abnormality. The network topology of WMNs is not always fixed due to mobility in both mesh routers and clients. Thus, monitoring the network topology is a desired feature for WMNs. Knowing the location of a mesh router or client improves the performance of lower layer protocols.
Network Configuration: For each node of WMNs, a few parameters in different protocol layer need to be configured in order to optimize the network performance. Software tools in the application layer are needed to configure such parameters.
Authentication, Authorization, and Accounting: Authentication, authorization, and accounting (AAA) is usually performed through a centralized server. However, the centralized scheme like RADIUS is not scalable in WMNs; the dynamic and multi-hop ad hoc network topology significantly limits the efficiency of any centralized schemes.

Open Research issues

A few network management protocols have been proposed for wireless ad hoc networks. However, the efficiency of these schemes needs to be improved for a large scale mesh network. In addition, in order to accurately detect abnormal operation of WMNs, effective data processing algorithms are needed. Also, how to quickly determine network topology and the accurate location of a mesh node is still an open question. Developing an efficient AAA system also poses a challenging research problem for WMNs.

Back to Top

Cross-Layer Approaches

Layer 2.5 Forwarding Algorithm

The problem of joint channel assignment and routing in a multi-radio, multi-channel WMN is NP complete and several stage-wise algorithms that address each of them in turns have been proposed. In this project the more general problem of channel and rate selection is addressed by integrating it with a forwarding paradigm that allows scheduling of the flows at the desired and sustainable rates. A standard MAC layer can be used in this approach. Moreover, a detailed bi-dimensional Markov chain model is developed in this project for analytically measuring the performance of the algorithm.

The steps followed in this approach are as follows:

A pre-computed flow rate is determined for every link based on the given optimization objective.

Channels are assigned to radios in the attempt to make the pre-computed flow rates returned by the previous step schedulable, i.e., actually achievable considering the interference among transmissions over the same channel.

The pre-computed flow rates returned by the first step may be adjusted in order to obtain a set of schedulable flow rates given the computed channel assignment.

The solution to the joint channel assignment and routing problem provides a set of link flow rates that are schedulable given the computed channel assignment. Next, our Layer-2.5(L2.5) forwarding paradigm allows the routers to utilize each of its links in proportion to their flow rates. Routers build their own hop count vector based on the link costs, as well as, the minimum hop count to the each destination. The proposed approach is evaluated for the two cases of with and without rate-adaptation to quantify the performance improvement with other related approaches. The maximum total channel utilization returned by our approach is in the range of 2-4 times smaller than that of the other algorithms and shows an improvement even without adapting the transmission rates. This metric ensures that the collision domain is not saturated due to ongoing transmissions by the channel assignment process. The Markov chain formulation is also demonstrated to yield valuable insights to the choice of parameters for our scheme.

Physical-Link-Network Layer Optimization

In this project, we jointly consider the effect of the physical layer, the link layer and the network layer in devising a cross-layer multi-radio, multi-channel routing protocol, (XCHARM) for WMNs. Routes are chosen based on the availability of- 1) Channels that support high data rates, 2) Exhibit acceptable interference levels and 3) Resilience to multi-path fading.

The routing protocol, XCHARM, comprises of the following six functions: (i) channel selection stage, in which, the MR forwarding the route request (RREQ) and its potential next hops decide on a set of usable channels while accounting for external interference, (ii) channel and MR ranking, that establishes an order of preference in the channels and the candidate forwarding MRs, that are found to be suitable for transmission, (iii) time deferring process, that allows nodes with better channel characteristics to forward the RREQ earlier than the others, (iv) FEC assignment, that decides in part the end-to-end performance of the routes, (v) route selection by the destination, and finally (vi) route management to ensure the optimality of the route.

The basic functioning of the protocol is explained using the above figure:

Through the transmission of the RREQ, MRs obtain information about the quality of the channel on the link between them. Specifically, the channels exhibiting flat fading over frequency selective fading are preferred. In addition, a set of channels is negotiated between the sender and the candidate forwarder that not affected by external interference power, as well as, introduce tolerable interference in the neighborhood. Thus, MRs 1, 2, and 3 receive the RREQs from the sender and classify the channel states for each of these links they share with the sender.

The channels of the links, as well as the links themselves are then ranked based on the maximum allowed transmission rate that can be supported. This ranking is used to introduce a forwarding delay, with the links with higher rates granted precedence. Let MR 1 have the best channel amongst the three candidate forwarders. It then has the highest rank and consequently, the least forwarding delay. It will send out the RREQ earlier than MRs 2 and 3.

Based on a target packet error rate, the FEC may be decided at the intermediate hops. The choice of FEC affects the end-to-end latency and is further optimized at the destination.

Finally, the destination sends back the route reply (RREP) confirming the route selection. External interference, changes in the fading environment or subsequent involvement in multiple routes may cause higher link delay and possibly violate the end-to-end QoS thresholds. These conditions are identified at the destination and route recovery is undertaken.

Publications

K. R. Chowdhury, M. D. Felice and L. Bononi, ``Fading and Interference Aware Cross-layer Multi-radio Multi-channel Routing Protocol for Wireless Mesh Networks'', submitted for journal review, July 2008.

S. Avallone, I. F. Akyildiz, I.F. and G. Ventre, ``A Channel and Rate Assignment Algorithm and a Layer 2.5 Forwarding Paradigm for Multi-Radio Wireless Mesh Networks'', to appear in IEEE Transactions on Networking, 2008.

Back to Top

Cognitive WMN Research

Spectrum Sensing and Sharing

In this research we explore ways in which mesh clusters, formed by the mesh router and the mesh clients served by it, share spectrum resource with the licensed users of that spectrum. The mesh nodes are equipped with tunable radios and may seek vacant spectrum in, say, TV channels that are used intermittently. These channels, in the 700 MHz range, are considered as the licensed band and the mesh nodes are secondary users that opportunistically use these frequencies. Our proposed COgnitive Mesh NETwork (COMNET) solution addresses the key challenges of identifying which portions of the spectrum are free for use, resolving contentions with the licensed users operating in those frequencies and load balancing over the entire available spectrum.

Broadly, COMNET can be described by the following main functionalities:

Spectrum Sensing: A new approach for spectrum sensing is devised that allows mesh nodes to monitor the primary channels while continuing operation in the ISM (secondary) band.
Interference Estimation: An analytical model is proposed that allows MRs to estimate the power in a given channel and location due to neighboring wireless LAN traffic, thus creating a virtual map in space and frequency domains.
Spectrum Sharing: These models are used to formulate the task of channel assignment within the mesh network as an optimization problem, which is solved in a decentralized manner.

COMNET is being improved further by considering generalised traffic models, realistic transmission spectral shapes, biased selection of the nodes used for signal estimation, amongst others.

Publications

K. R. Chowdhury and I. F. Akyildiz, ``Cognitive Wireless Mesh Networks with Dynamic Spectrum Access'', IEEE Journal on Selected Areas in Communications, Vol. 26, No. 1, pp. 168-181, January 2008.

Back to Top

Channel-Aware Cross-Layer Routing

Routing challenges for cognitive mesh networks are concerned with route selection and maintenance in a multichannel, multispectrum environment. Compared with classical mesh networks, new metrics such as primary user activity along the chosen route, the number of channels available at the intermediate hops, and the bandwidth of each of them also need to be considered. The decentralized nature of the mesh network makes channel coordination between nodes of the same route difficult. When mesh routers are of a hetergeneous nature with different spectrum access capabilities (say, two adjacent routers A and B can only tune their radios to 700 MHz and 5 GHz respectively apart from the ISM band) this becomes a critical concern.

In order to address the issues listed above, the research for cognitive mesh routing has been undertaken in the following directions:

Spectrum-Tree Based Routing: Based on primary user activity information and secondary user QoS requirements, a new cognitive route metric is devised. Also, the mesh network is partitioned into trees, each tree being on a different spectrum band. This addresses the issue of heterogenous mesh routers operating on different bands and simplifies route management in case of new primary user arrivals. By maintaining a list of tree nodes that overlap with the other spectral trees, the root can perform fast lookups and path re-assignments. The tree structure also provides a bounded performance on the routing functionality, once it is set up.

Publications

G. M. Zhu, I. F. Akyildiz and G. S. Kuo, ``STOD-RP: A Spectrum-Tree Based On-Demand Routing Protocol for Multi-Hop Cognitive Radio Networks'', to appear in Proc. of IEEE GLOBECOM, New Orleans, USA, November 2008.