Hierarchical routing

Motivation

The theoretical advantages that mobile ad hoc networks (MANETs) bring are well known. Among these advantages, it is worth highlighting the easy configuration and the ability to establish a communication path between any nodes of the network without using a central element. Moreover, an ad hoc network can work in isolated mode or being connected to a larger network infrastructure like the Internet. In this sense, new scenarios can be conceived as applications of MANETs, such as the popular concept of Smart Cities and the prevailing Internet of Things (IoT). They are also an essential element in the new 5G (5th Generation) networks.

Such network scenarios involve a set of independent wireless nodes that can communicate and move at the same time. Since no fixed infrastructure is required to allow such communications, nodes must cooperate in the task of routing packets to destination nodes. In order to communicate with nodes that are out of their transmission range, wireless nodes need to use intermediate nodes as routers. For this reason, MANETs are defined as multi-hop wireless networks. In this sense, routing protocols play an important role because they are in charge of discovering and maintaining routes for packets from the source node to the destination. In fact, routing in mobile environments is challenging due to the possible changes in network topology and the constraints existing on the resources (processing capacity, transmission bandwidth, battery power, etc.).

Moreover, applications and services are more and more bandwidth and resource demanding. For instance, video services are one of the most demanded (and demanding) services nowadays, whose bandwidth and delay requirements are very restrictive. Offering real-time video services in wireless ad hoc networks is not an easy task because of the difficulty of guaranteeing certain quality in a shared medium. Besides this fact, because of the dynamic topology of MANETs, routing protocols are more complex than traditional routing protocols used on the Internet. In any case, the main objective of these routing protocols is to achieve efficient routes between nodes so that the information will be available in destination nodes reliably and within boundary time.

Besides routing protocols, video transmission can be improved by means of cross-layer techniques that take into account node mobility and coverage. Moreover, the broadcast nature of wireless transmissions could be exploited to take advantage from spatial diversity in order to route or retransmit packets according to the propagation conditions and increase wireless throughput.

Therefore, despite the difficulty of providing hard Quality of Service (QoS) for real-time applications over MANETs, there are still many ways to improve video streaming quality, concerning routing, transport and application layers.

Overview

Hierarchical routing has been presented as a way of arranging wide ad hoc networks in clusters to improve network efficiency. Although the clustering mechanism may lead to an increase in control traffic and complexity, routing protocols can benefit from hierarchical structures so that routing flooding, especially in proactive protocols, can be confined within clusters and nodes can be arranged in virtual groups to optimize communications and reduce interferences [1]. Hence, the resulting network may scale well when the number of nodes grows.

Figure 1. Hierarchical routing scheme

In a hierarchical environment, quality of service can be achieved at two levels: intra-cluster and inter-cluster QoS solutions.

  • Intra-cluster solutions refer to the mechanisms used within the same cluster as if it was a whole network. In this sense, information about the delay metric of every node and bandwidth consumption can be added.

  • Inter-cluster solutions include approaches that involves more than one single cluster. For instance, one inter-cluster solution would imply that each cluster head obtains an estimation of the output channel losses towards other clusters. Then, a cluster will be able to include a new route to other cluster in order to balance the traffic load when these losses exceed a certain threshold.

On the other hand, mobility of nodes makes it difficult to create and maintain transmission routes in wireless ad hoc networks. Opportunistic strategies and ARQ mechanisms provide throughput gains in wireless communications and improve the QoS of video transmissions, providing the user with a higher QoE. To this end, a cross-layer technique that uses information drawn from MAC, routing and application layers is proposed in order to increase the overall packet delivery ratio and, in case of video transmissions, reduce frame losses so as to avoid playback interruptions. This altruistic routing is a scheme based on the fact that neighboring nodes of the destination node can help in recovering lost packets when a route breakage occurs.

Wireless networks have a particularity inherent to the wireless channel nature that is exploited by opportunistic [2] and cooperative routing protocols [3]. Neighbor nodes can overhear the packets that are being sent within their coverage area, even though these packets are not addressed to them, which is called Wireless Broadcast Advantage (WBA) [4]. This feature from the link layer can also aid the routing protocol in order to improve network performance and connectivity. Neighbor nodes can cache video packets that may be useful for the destination node in case it moves out of range and the established packet route changes. If this happens, neighbor nodes would be pleased to forward altruistically those packets that were lost during the hand-over.

Because the proof is in the pudding, the following video shows what happens when the destination of a video transmission moves out of range and the route from the video source changes. The difference of quality of the received streams can be subjectively confirmed. Moreover, the difference in PSNR (Peak Signal to Noise Ratio) is also worth highlighting.

Video 1. Comparation between OLSR and altruistic protocol in ad hoc networks

References

[1]  J. Y. Yu, and P. H. J. Chong, “A survey of clustering schemes for mobile ad hoc networks,” IEEE Communications Surveys & Tutorials, vol.7, no.1, pp. 32-48, 2005.
[2] C.-J. Hsu, H.-I. Liu, and W. K. G. Seah, “Opportunistic routing – A review and the challenges ahead,” Computer Networks, vol. 55, no. 15, pp. 3592-3603, Oct. 2011.
[3] X. Huang, H. Zhai, and Y. Fang, “Robust cooperative routing protocol in mobile wireless sensor networks,” IEEE Transactions on Wireless Communications, vol. 7, no. 12, pp. 5278-5285, Dec. 2008.
[4] J. E. Wieselthier, G. D. Nguyen, and A. Ephremides, “Algorithms for energy-efficient multicasting in ad hoc wireless networks,” Mobile Networks and Applications, vol. 6, no. 3, pp. 251-263, Jun. 2001.

Related publications

[5] P. Arce,  J. C. Guerri, A. Pajares, and O. Lázaro, “Performance evaluation of video streaming over ad-hoc networks using flat and hierarchical routing protocols,” Mobile Networks and Applications (Special Issue on Multimedia over Ad-Hoc and Sensor Networks), vol. 13, pp. 324-336, 2008.
[6] J. C. Guerri, P. Arce, P. Acelas, W. Castellanos, and F. Fraile, “Routing and Coding Enhancements to Improve QoS of Video Transmissions in Future Ad Hoc Networks,” Multimedia Services and Streaming for Mobile Devices: Challenges and Innovations, Ed. IGI Global, pp. 244-261, 2011.
[7] P. Arce, S. González, and J. C. Guerri, “Altruistic Networks: where every node matters,” Recent Advances in Ad Hoc Networks Research, Ed. Nova Science Publishers, pp. 41-68, 2014.
[8] P. Arce, I. de Fez, F. Fraile, S. González, P. Guzmán, and J. C. Guerri, “QoE en redes adhoc, descarga adaptativa de contenidos y vídeo 3D,” in Proc. of Jornadas de Ingeniería Telemática (JITEL), Palma de Mallorca (Spain), Oct. 2015, pp. 339-346.
[9] P. Arce and J. C. Guerri, “An altruistic cross-layer recovering mechanism for ad hoc wireless networks,” Wireless Communications and Mobile Computing, vol. 15, no. 3, pp. 1744-1758, 2015.
[10] W. Castellanos, P. Guzmán, P. Arce, and J. C. Guerri, “Mechanisms for improving the scalable video streaming in mobile ad hoc networks,” in Proc. of ACM Int. Symposium on Performance Evaluation of Wireless Ad Hoc, Sensor, and Ubiquitous Networks (PE-WASUN), Cancun (Mexico), Nov. 2015, pp. 33-40.