CGR: Centrality-based green routing for Low-power and Lossy Networks
Introduction
A Low-power and Lossy Network (L2N) is a network type inspired by the idea that even the smallest low-power devices should be able to run in a network. Energy is a resource extremely restricted in L2N due to small devices and their energy constraints [1]. Usually, the devices employed in these networks have no rechargeable batteries, and they are not reachable for replacement. In this context, green communications can enable longer network lifetime. By exploiting the devices features, and network topology, green-designed protocols can be an efficient way to save resources and keep alive the L2N. The design of green protocols for L2N has importance in several fields, ranging from urban and industrial low power networks to underwater networks [2], [3], [4].
A key challenge is to keep these networks alive as long as possible [2], [5]. But, some factors reduce L2N lifetime. For example, intermediate nodes usually forward data traffic of other nodes, thus eventually these relay nodes will have their energy resource quickly drained. When different source nodes send individual data flows to the sink collector, the number of transmissions will increase, and it may also promote transmission collisions or channel occupancy. Another factor, but not least, is the link conditions (quality) which can cause packet retransmissions due to bad reception and eventually packet drop by exhaustive transmission failures. Mitigating these problems can extend the L2N lifetime.
In this scenario, the routing protocols play a significant role in the resource usage. The L2N are composed of a large number of nodes with limited capabilities of computation (memory and processing), wireless communication, and energy. The protocol stack makes use of the computational resource to store and process routes, it needs to estimate the wireless link communication quality, and for all that to be done, the protocol’s execution needs energy. However, many applications need to transport a large amount of data (image, audio, video monitoring, so on). Thus, protocols have the responsibility to deliver data in an energy efficient way. Routing protocols are a fundamental part of the protocol stack. Therefore, efficient ways to deliver data are critical. These applications require high data delivery and long network lifetime. Thus, routing protocols for L2N that save resources and provide green efficient routes should be addressed.
In this work, we present the Centrality-based Green Routing for L2Ns (CGR) a green data collection routing protocol. CGR combines cost-efficient L2N features in order to be, simultaneously, energy aware and provide high throughput. First, CGR uses a centrality betweenness-based approach to choose intermediate nodes, which favors in-network data fusion techniques that can potentially save energy. Centrality metrics capture the topology importance of the nodes and therefore can be used to improve routing [6]. Second, CGR makes use of Expected Transmission Count (ETX) [7] or Four Bit [8] as the Link Quality Estimation (LQE) estimator. It assists CGR to find high throughput routes, reduce packets drop, and improve energy usage.
Data collection protocols suffer from the energy hole problem, where nodes next to the sink node tend to quickly drain their energy while sending and forwarding messages. To address that issue in CGR, we implement the Policy-Aware algorithm, specially designed to mitigate the energy hole problem. Policy-Aware keeps track of spots where energy is being drained (typically at central nodes) and then changes the route to balance the power consumption, by the cost of few controls packets.
We also present a survey of other approaches in the literature that considered specifically each piece of our object of study: LQE, centrality importance criterion, and related protocols.
In summary, the contributions of this paper include:
- •
The proposal of Centrality-based Green Routing for L2Ns (CGR), which is a distributed green algorithm to find the best routing intermediate nodes based on the Sink Betweenness centrality;
- •
The proposal of the Policy-Aware algorithm, which is a load balance algorithm that mitigates energy waste of the routing nodes in the network.
- •
Results show that CGR is a suitable algorithm in terms of delivery rate, energy consumption, and time to delivery for L2N.
CGR uses a LQE to optimize routes choice and improve throughput and energy usage, according to state-of-the-art protocols like RPL [9] and XCTP [10]. Traditional centrality routing protocols, such as CT [11] and CNS [12], use hop count to choose their routes, which can decrease the network throughput and increase energy spent. Also, the CGR architecture enables the use of the Policy-Aware algorithm to deal with the energy hole problem, while traditional centrality routing protocols do not manage this issue; indeed they increase the energy hole problem by routing only through central nodes.
Our work is organized as follows. In the next section, we present the related work divided into three parts (link quality estimators, centrality metrics, and routing protocols). Then, in Section 3, we introduce the underlines of the green routing problem, its hardness, a complexity analyses, and how we address the issues. Our proposed solution is detailed in Section 4. Section 5 brings the Policy-Aware Algorithm. Next, in Section 6, we present CGR results and compare it against state-of-the-art and traditional protocols. Finally, we conclude and present insights for future work in Section 7.
Section snippets
Related work
This section is organized into three parts. In the first one, we discuss the main techniques for LQE highlighting characteristics of each estimator and compare them. Next, we survey centrality metrics to rank nodes according to their topological position. Finally, in the third part, we classify CGR and the related state-of-the-art routing protocols and emphasize the differences among them.
Problem definition and its hardness
In this section, we first describe the network model as a connected weighted directional graph in Section 3.1. Then, we present the green routing tree-based problem. Next, we highlight its hardness by given an intuition of its the NP-Completeness in Section 3.2. Also, in Section 3.2.1, we describe how our proposed work treats the problem.
Centrality-based green routing
In this section, we describe the Centrality-based Green Routing for L2Ns, a routing protocol that considers both centrality and energy to improve the network performance and decrease energy consumption. First, we present the CGR architecture, its modules and relationship in Section 4.1. Next, in Section 4.2, we present the CGR Algorithm and implementation details. CGR complexity analysis regarding control packets to compute the centrality tree is presented in Section 4.3. Finally, we discuss
Policy-Aware
In this section, we introduce the Policy-Aware algorithm, an approach to deal with energy holes in the L2N. Energy hole problem is defined as excessive energy expenditure in parts of a network [40]. In L2N, energy hole can cause disconnected components. The Policy-Aware approach comes as an alternative to mitigate this problem by driving out existing flows of the central nodes to non-central nodes.
The Policy-Aware algorithm combines three features in its scheme. First, it uses a metric (a LQE)
Evaluation
We analyze CGR and compared it with two protocols: CT, SPT, and RPL. From the protocols presented in Table 3, RBC and the ones derived from it were not designed for L2N, therefore they can not be compared with CGR. InFRA and DAARP belong to a different class of protocols that approximate Steiner Tree that do not classify the nodes by centrality. CNS is a classical protocol and its results are lower than CT. Therefore, we compared CGR against CT and SPT. We also compare CGR with RPL, the
Conclusion
We present CGR a reliable, robust, and energy-efficient routing protocol for L2N based on the nodes’ centrality. CGR represents an alternative strategy for routing data in L2N that finds intermediate nodes based on the topological importance. CGR favors data aggregation by approximating the Minimum Steiner Tree. Our simulation results show that CGR presents smaller Steiner number and TPR than the protocols evaluated. Also, CGR and RPL show similar delivery rate close to 100% when some packet
Acknowledgment
We would like to thank the research agencies, CAPES, CNPq and FAPEMIG for funding this research.
Bruno P. Santos is a PhD candidate in Computer Science at the Universidade Federal de Minas Gerais (UFMG). He received his M.S. at the Universidade Federal de Minas Gerais in Belo Horizonte. His research interest is in Computer Networking.
References (44)
- et al.
A graph-theoretic perspective on centrality
Soc. Netw.
(2006) - et al.
Routing betweenness centrality
J. ACM
(2010) - et al.
Steiner minimal trees
SIAM J. Appl. Math.
(1968) - et al.
Avoiding energy holes in wireless sensor networks with nonuniform node distribution
Parallel Distrib. Syst. IEEE Trans.
(2008) - et al.
Survey on wireless sensor network devices
EFTA 2003. 2003 IEEE Conference on Emerging Technologies and Factory Automation. Proceedings
(2003) - et al.
On the design of green protocols for underwater sensor networks
IEEE Commun. Mag.
(2016) - S. Dwars, T. Phinney, P. Thubert, K. Pister, Industrial Routing Requirements in Low Power and Lossy Networks, 2009,...
- M. Dohler, T. Watteyne, T. Winter, D. Barthel, Routing requirements for urban low-power and lossy networks, 2009, (RFC...
- et al.
An efficient algorithm of constructing virtual backbone scheduling for maximizing the lifetime of dual-radio wireless sensor networks
Int. J. Distrib. Sen. Netw.
(2015) - et al.
A Novel Centrality Metric for Topology Control in Underwater Sensor Networks
Proceedings of the 19th ACM International Conference on Modeling, Analysis and Simulation of Wireless and Mobile Systems
(2016)
A High-throughput Path Metric for Multi-hop Wireless Routing
Proceedings of the 9th Annual International Conference on Mobile Computing and Networking, MobiCom ’03
Four-bit wireless link estimation
Proceedings of the Sixth ACM Workshop on Hot Topics in Networks (HotNets-VI)
eXtend collection tree protocol
2015 IEEE Wireless Communications and Networking Conference (WCNC)
Centrality-based routing for Wireless Sensor Networks
2010 IFIP Wireless Days
Modelling data-centric routing in wireless sensor networks
IEEE INFOCOM
Understanding the Causes of Packet Delivery Success and Failure in Dense Wireless Sensor Networks
Proceedings of the 4th International Conference on Embedded Networked Sensor Systems, SenSys ’06
Radio link quality estimation in wireless sensor networks: A Survey
ACM Trans. Sen. Netw.
Statistical model of lossy links in wireless sensor networks
IPSN 2005. Fourth International Symposium on Information Processing in Sensor Networks, 2005.
Measurement and characterization of link quality metrics in energy constrained wireless sensor networks
Global Telecommunications Conference, 2003. GLOBECOM ’03. IEEE
Bio-inspired link quality estimation for wireless mesh networks
2009 IEEE International Symposium on a World of Wireless, Mobile and Multimedia Networks Workshops
Link quality estimators for multi-hop mesh network
2014 Euro Med Telco Conference (EMTC)
Cited by (0)
Bruno P. Santos is a PhD candidate in Computer Science at the Universidade Federal de Minas Gerais (UFMG). He received his M.S. at the Universidade Federal de Minas Gerais in Belo Horizonte. His research interest is in Computer Networking.
Luiz F. M. Vieira is a Professor of Computer Science at the Universidade Federal de Minas Gerais (UFMG). He received his undergraduate and M.S. at the Universidade Federal de Minas Gerais in Belo Horizonte, and Ph. D. degree in Computer Science from the University of California Los Angeles (UCLA). His research interest is in Computer Networking.
Marcos A. M. Vieira is a Professor of Computer Science at the Universidade Federal de Minas Gerais (UFMG). He received his undergraduate and M.S. at the Universidade Federal de Minas Gerais in Belo Horizonte, and M.S. and Ph. D. degrees in Computer Science from the University of Southern California (USC). His research interest is in Computer Networking.