Elsevier

Computer Networks

Volume 129, Part 1, 24 December 2017, Pages 117-128
Computer Networks

CGR: Centrality-based green routing for Low-power and Lossy Networks

https://doi.org/10.1016/j.comnet.2017.09.009Get rights and content

Abstract

High throughput and energy are two important constraints of the Low-power and Lossy Network (L2N). We propose Centrality-based Green Routing for L2Ns (CGR) as a routing protocol that considers both centrality and energy to improve network performance and decrease power consumption. CGR is a collection routing protocol that combines the best features of both protocols Collection Tree Protocol (CTP) and Centrality Tree (CT). CGR uses centrality betweenness-based to choose intermediate nodes that can perform data fusion and employ Link Quality Estimation (LQE) to find routes of high throughput and delivery rate. The suitable combination of these techniques leads the protocol to improve the literature results in delivery rate, energy consumption, and time to deliver data. There is a trade-off by routing through central nodes and their power consumption. Thus we also propose a Policy-Aware algorithm to balance energy consumption and to increase the network lifetime.

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)

  • S.P. Borgatti et al.

    A graph-theoretic perspective on centrality

    Soc. Netw.

    (2006)
  • S. Dolev et al.

    Routing betweenness centrality

    J. ACM

    (2010)
  • E.N. Gilbert et al.

    Steiner minimal trees

    SIAM J. Appl. Math.

    (1968)
  • X. Wu et al.

    Avoiding energy holes in wireless sensor networks with nonuniform node distribution

    Parallel Distrib. Syst. IEEE Trans.

    (2008)
  • M.A.M. Vieira et al.

    Survey on wireless sensor network devices

    EFTA 2003. 2003 IEEE Conference on Emerging Technologies and Factory Automation. Proceedings

    (2003)
  • R.W.L. Coutinho 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...
  • B.-H. Liu 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)
  • R.W. Coutinho 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)
  • D.S.J. De Couto et al.

    A High-throughput Path Metric for Multi-hop Wireless Routing

    Proceedings of the 9th Annual International Conference on Mobile Computing and Networking, MobiCom ’03

    (2003)
  • R. Fonseca et al.

    Four-bit wireless link estimation

    Proceedings of the Sixth ACM Workshop on Hot Topics in Networks (HotNets-VI)

    (2007)
  • P. Thubert, A. Brandt, J. Hui, R. Kelsey, P. Levis, K. Pister, R. Struik, J. Vasseur, R. Alexander, RPL: IPv6 routing...
  • B.P. Santos et al.

    eXtend collection tree protocol

    2015 IEEE Wireless Communications and Networking Conference (WCNC)

    (2015)
  • E.M.R. Oliveira et al.

    Centrality-based routing for Wireless Sensor Networks

    2010 IFIP Wireless Days

    (2010)
  • B. Krishnamachari et al.

    Modelling data-centric routing in wireless sensor networks

    IEEE INFOCOM

    (2002)
  • K. Srinivasan et al.

    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

    (2006)
  • N. Baccour et al.

    Radio link quality estimation in wireless sensor networks: A Survey

    ACM Trans. Sen. Netw.

    (2012)
  • A. Cerpa et al.

    Statistical model of lossy links in wireless sensor networks

    IPSN 2005. Fourth International Symposium on Information Processing in Sensor Networks, 2005.

    (2005)
  • D. LaI et al.

    Measurement and characterization of link quality metrics in energy constrained wireless sensor networks

    Global Telecommunications Conference, 2003. GLOBECOM ’03. IEEE

    (2003)
  • M. Caleffi et al.

    Bio-inspired link quality estimation for wireless mesh networks

    2009 IEEE International Symposium on a World of Wireless, Mobile and Multimedia Networks Workshops

    (2009)
  • A.S. Cacciapuoti et al.

    Link quality estimators for multi-hop mesh network

    2014 Euro Med Telco Conference (EMTC)

    (2014)
  • 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.

    View full text