Routing in Self-organized Wireless Networks

Description

Motivation

In the context of Wireless Mesh Networks (WMNs), scalability requirements, heterogeneity, and (sometimes) uncontrolled deployment require the introduction of self-organization. The design of a routing protocol that really exploits the specific features of a Self-organized Wireless Mesh Network remains a challenge. The static and non-power constrained nature of potential backbone nodes allows offering some exploitable features towards this goal, such as multi-radio and multi-channel support, static backbone nodes, and increased CPU and storage capabilities. The expected additional benefit, with respect to those that do not or cannot exploit them, is an increase in overall throughput supported by the network. By contrast, the main design goal of routing protocols for mobile ad hoc networks (MANET) is end-to-end connectivity maintenance. In MANETs, transmitting a packet has a high cost due to node energy constraints. Therefore, at the routing level, research is mainly focused on designing low control overhead routing techniques to deal with frequent route breaks due to mobility or node failures. This is not exactly the case in WMNs.

Goal

We are interested in studying the fundamental behavior guiding the performance of WMNs (e.g., interference) in order to understand how a routing protocol should be designed, always bearing in mind the distinguishing features of WMNs. The ultimate goal is to design and implement practical routing protocols for WMNs in order to extend the reach of Internet network connections in real scenarios (e.g., hotels, community neighborhood, airports, stadiums) and to evaluate the feasibility of all-wireless networks.

Distributed Backpressure Routing

We are currently exploring the potential of backpressure when applied to routing in practical WMNs. In this direction, theoretical backpressure schemes must be adapted from centralized to distributed operation, from one queue per destination at each node to a single queue per node, from infinite to finite queue sizes, and from more or less static network setups to varying network setups (e.g., varying topologies and traffic loads). The Lyapunov drift-plus-penalty optimization framework allows trading off between 1) routing decisions for maintaining queue backlogs under control (and hence, the network stable) and 2) those that try to get close to the optimal value of an objective performance metric. Such framework offers a non-negative parameter (V) for weighting both components (see Figure). In this way, the degree of distribution of resource consumption throughout the network can be appropriately adjusted.

On the Impact of the V parameter on data packet distribution

On the Impact of the V parameter on data packet distribution

Specifically, we study practical backpressure routing strategies for Wireless-based Mesh Networks . It is practical in the sense that, unlike previous theoretical centralized algorithms, we present a distributed implementation of the algorithm with low queue complexity (i.e., one finite data queue at each node) to deal with any-to-any communications. Moreover, it has low overhead because it does not establish/manintain routes and decisions are taken on a per-packet basis. We are able to do that by also exploiting geographic information. To our knowledge, this is the first practical study based on Tassiulas/Neely’s Lyapunov optimization framework for WMNs. In fact, we propose a scalable and distributed routing policy that takes control actions based on Lyapunov’s drift-plus- penalty minimization combining local queue backlog and 1-hop geographic information.

Traffic conditions in a WMN can be highly dynamic. Hence routing policies based on a fixed-V parameter cannot met all traffic conditions in an uneven and dynamic WMN. To be able to adapt to traffic conditions, we propose to calculate a distributed and adaptive penalty weight (i.e., variable-V) at each node. In this way, dynamic and uneven traffic demands and wireless network variations can be met.

Evaluation methodology

Given the practical orientation of this task, our research is closely linked to research carried out in the group on Network Measurements. Experimental evaluation of the proposed solutions are carried out in the WMN extension of the EXTREME Testbed. In the context of EU project BeFEMTO and MICINN project SYMBIOSIS, we are also applying our distributed geographic+backpressure routing scheme in all-wireless networks of femtocells, which combine a cellular core and wireless mesh network of femtocells. Furthermore, we are also extending the features of NS-3.

Video Gallery

Geobackpressure routing demo
 

You might also be interested in the talks we gave during the Femtocells Winter School 2012 (Feb. 2012):

Publications

J. Nuñez-Martínez, J. Mangues. A Survey on Routing Protocols that really exploit Wireless Mesh Networks. Journal of Communications, Academy Publisher, Vol. 5, No. 3, pp. 211-231, March 2010.

J. Nuñez-Martínez, J. Mangues, M. Portolés-Comeras. Towards Distributed and Dynamic Backpressure Routing for Wireless Mesh Networks, in Proceedings of IEEE International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC) 11-14 September 2011, Toronto (Canada).

J. Nuñez-Martínez, J. Ferragut, J. Mangues. On Stateless Routing for an All-wireless Network of Femtocells. Implications in the 3GPP Architecture, in Proceedings of IEEE 73rd Vehicular Technology Conference (VTC2011-Spring), Workshop on Broadband Femtocell Technologies, 15-18 May, 2011, Budapest (Hungary).

J. Nuñez-Martínez, J. Mangues. Design, Implementation and Tracing of Dynamic Backpressure Routing for Ns-3, in Proceedings of 1th Wns3 held in conjunction with 4th International ICST Conference on Simulation Tools and Techniques (SimuTools), 21-25 March 2011, Barcelona (Spain).

J. Nuñez-Martínez, J. Mangues, M. Portolés-Comeras. Studying Practical Any-to-any Backpressure Routing in WiFi Mesh from a Lyapunov Optimization Perspective, in Proceedings of the 8th International Conference on Mobile Ad-hoc and Sensor Systems (IEEE MASS ) within the Fifth IEEE International Workshop on Enabling Technologies and Standards for Wireless Mesh Networking (MeshTech 2011), October 16-22, 2011, Valencia (Spain).

J. Nuñez-Martínez, J. Mangues. Distributed Lyapunov Drift-plus-penalty Routing for WiFi Mesh Networks with Adaptive Penalty Weight, in Proceedings of the Fifth IEEE International Workshop on Hot Topics in Mesh Networking (HotMesh 2012), co-located with the 13th International Symposium on a World of Wireless, Mobile and Multimedia Networks (IEEE WoWMoM), 25-28 June 2012, San Francisco, California (USA).

J. Ferragut, J. Mangues, J. Núñez, F. Zdarsky. Traffic and Mobility Management in Networks of Femtocells, in ACM/Springer Mobile Networks and Applications Journal, Special Issue on Cooperative and Networked Femtocells. DOI: 10.1007/s11036-012-0396-9, Copyright ACM/Springer 2012.

J. Núñez, J. Mangues. A Case for Evaluating Backpressure Routing using Ns-3 Emulation in a WiFi Mesh Testbed, in Proceedings of 7th ACM International Workshop on Wireless Network Testbeds, Experimental evaluation & Characterization (WinTECH), within the 18th Annual International Conference on Mobile Computing and Networking within MobiCom 2012, 22-26 August 2012, Istanbul (Turkey).

J.Núñez, J.Baranda, J. Mangues. Backpressure Routing for the Backhaul in Sparse Small Cell Deployments , in Proceedings of 32nd IEEE International Performance Computing and Communications Conference (IPCCC), 6-8 December 2013, San Diego, California (USA).

J.Núñez, J.Mangues, J.Baranda. Anycast Backpressure Routing: Scalable mobile backhaul for dense small cell deployments , IEEE Communications Letters, Vol. 17, pp. 2316 – 2319 , December 2013.