The routing of data from source to sink is an integral part of any large-scale wireless sensing and Internet of Things (IoT) solution. Unplugged and/or mobile embedded devices used in such low-powered and lossy network (LLN) applications are always severely constrained in terms of available power. Therefore, energy-efficient routing of data becomes critical to any long-term sustainable solution.
Many large-scale wireless data acquisition and actuation related applications use low-powered embedded devices. These applications include precision agriculture, building management/industrial automation, vehicular ad-hoc networks (VANETs), and urban networks/energy and water grids to build smarter cities. In these wireless sensor networks, the embedded devices function under severe energy constraints, which results in computation, storage, and radio-transmission related constraints. They also communicate over a lossy channel.
- Understanding The Internet Of Things
- Understanding The Protocols Behind The Internet Of Things
- Looking Forwards And Backwards On The Internet Of Things
The low-powered embedded devices in such applications do not work in isolation and often are part of a larger wireless network, usually involving hundreds or thousands of similar other devices (or field nodes). These field nodes may enter or leave the network at arbitrary times. The wireless routing solution, then, should be highly energy-efficient, scalable, and autonomous.
Low-powered and lossy networks (LLNs) typically consist of sensors, actuators, and routers that communicate wirelessly with each other. Unlike sensors and actuators, though, routers generally do not suffer from (long-term) resource constraints. Routers that connect LLNs to the wider Internet infrastructure are known as LLN border routers (LBRs).
Traffic patterns and data flow within an LLN are highly directional. The patterns can be defined as multipoint-to-point traffic (MP2P), point-to-multipoint traffic (P2MP), or point-to-point traffic (P2P). In MP2P traffic, for example, sensed information from multiple sensing nodes is routed to an Internet application via an LBR. P2MP traffic is observed when a query request is made from the Internet (outside the LLN) and routed via the LBRs and LLN routers to multiple field nodes. P2P traffic occurs when control information needs to be sent to a specific actuator or alert information is received from a specific sensor.
The Internet Engineering Task Force (IETF) has created working groups (WGs) to better understand the energy-efficient routing protocol requirements for application scenarios like urban/city-wide networks (RFC 5548), building automation/management systems (RFC 5867), industrial automation systems (RFC 5673), and home automation (RFC 5826).
Urban Wireless Sensor Networks
Many projects related to urban sensing are looking to monitor and track many of our urban resources and environmental conditions. The MIT Senseable city lab has several projects running to understand the “real-time city” for monitoring the “removal-chain,” which is the opposite of the supply chain of products, in projects like Trash Talk and Real Time Rome.1 IBM has been implementing its Smart Cities technologies in more than 100 cities around the world.
Urban networked applications like these represent a special type of LLNs with their unique set of wireless routing requirements. The Real Time Rome project used aggregated people density data from mobile telecom operators and GPS location data of public buses communicated via cell tower connectivity.
Building a sustainable solution that will allow data collection, aggregation, and display, though, would require implementing a low-powered mesh network that can route data among devices that are wirelessly connected and powered using low-energy sources. The RFC documents describe the key functionality and routing requirements for urban LLNs:
• Deployment of nodes: In a typical urban network deployment, hundreds or thousands of nodes with pre-programmed functionalities are rolled out. Pre- or post-roll-out, the network initialization phase may include allocation of addresses, (hierarchical) roles in the network, synchronization, and determination of schedules. Post-roll-out, in the resulting topology there may be some node that can connect through multiple (redundant) paths, while some other nodes may depend on critical links to achieve connectivity. The routing protocol should account for these factors and support self-organization and self-configuration at the lowest possible energy cost.
• Association and disassociation of nodes: After the initialization phase, nodes may join or leave the network at arbitrary times. The routing protocol also should be able to handle situations where a malfunctioning node may affect or jeopardize the overall routing efficiency.
• Regular measurement reporting: Most field nodes are configured to report their readings on a regular basis (once per hour, per day, etc.). The data routing computation and selection may depend on the sensed data, the frequency of reporting, the amount of energy remaining in the nodes, the recharging pattern of the energy-scavenged nodes, or other factors.
• Queried measurement reporting: External applications can launch queries on the urban network. For instance, the level of pollution at a specific point or along a given road may need to be known. Round-trip times—i.e., from the launch of a query from a node to the delivery of the measured data to a node—are important. (The latency is not very stringent, but it should be smaller than the reporting intervals.)
• Alert reporting: Rarely, the sensing nodes may measure an event that is classified as an alarm, which is usually when the sensed data is crossing a threshold. Routes for reporting an alarm need to be unicast (toward an LBR) or multicast (toward multiple LBRs).
• Scalability: The routing protocol must be able to support a field deployment of a few hundred to tens of thousands of sensor nodes without deteriorating selected performance parameters below configurable thresholds.
• Parameter constrained routing: The protocol must be able to advertise node capabilities (CPU, memory size, available battery level) that it can use for routing decisions. The field nodes are required to dynamically compute, select, and install different paths toward the same destination, depending on the nature of the traffic.
• Support of autonomous and alien configuration: Given the large number of nodes, manually configuring each node is not feasible. The scale and the number of possible topologies require the network to self-organize and self-configure according to some prior defined rules and protocols, as well as allow externally triggered configurations.
• Support of highly directed information flows: Urban networks often route sensed data from the field nodes to Internet-based applications via the LBRs. As the nodes are spatially dispersed, and as the data gets closer to the LBR, the traffic concentration in the nodes nearest to the LBR increases, causing load imbalances in those nodes. The routing protocol must be able to accommodate traffic bursts by dynamically computing and selecting multiple paths toward the same destination.
• Support of multicast and anycast: The routing protocol must have an addressing scheme that can support routing to a single field device (unicast), routing to a set of nodes subscribed to the same group (multicast), and routing to multiple field nodes that all can be addressed by the same Internet protocol (IP) address (anycast).
• Network dynamicity: The field nodes may dynamically associate, disassociate, or disappear from the urban network. The field node dynamics should not impact the routing in the entire network, so the routing protocol should have an appropriate updating mechanism to be informed of changes in field node status. The protocol should use this information to perform the required routing level reorganization and reconfiguration to maintain overall routing efficiency.
• Latency: The routing protocol should support the ability to route based on different latency/delay requirements. Urban networks can tolerate delays as long as the information arrives in a proportionate time compared to the reporting time. (If the time is every few hours, latency can be a few seconds.)
IPv6-Enabled Wireless Routing Protocol For LLNs (RPL)
The entities and devices involved in building a routing-enabled IoT solution are unable to maintain state information due to memory and storage constraints. They also can’t maintain optimizations and overheads in transmitting control information due to energy and other routing-related constraints.
IoT solutions tend to grow considerably big in scale as well. Hence, the routing protocol needs to provide routing table scalability and packet loss response. Traditional routing protocols such as Open Shortest Path First (OSPF), Optimized Link State Routing (OLSR), and Ad-Hoc On Demand Vector (AODV) were unable to meet the performance requirements for an IoT solution with such characteristics.
The IETF Routing over LLN (RoLL) Working Group developed an IPv6 enabled routing protocol known as Routing Protocol for LLNs (RPL),2 which offers:
• Routing state propagation: RPL uses the Trickle algorithm for scalable state propagation. The Trickle algorithm allows nodes in a lossy shared medium like low-power and lossy net works to exchange information in a highly robust, energy efficient, simple, and scalable manner. Trickle dynamically adjusts transmission windows so new information spreads very quickly while only a few messages are transmitted when information does not change.
• Spatial diversity: Since nodes can dynamically appear and disassociate or disappear, RPL requires a router to maintain multiple potential parents toward a destination instead of a single one.
• Expressive link and node metrics: LLNs have significant link-cost variation across multiple dimensions (e.g., reliability, latency). RPL uses a flexible framework such as estimated number of transmissions (ETX) for incorporating such dynamic link metrics.
Fundamental Building Blocks Of RPL
At its core, RPL organizes its topology as a directed acyclic graph (DAG) that is partitioned into one or more destination oriented DAGs (DODAGs), with one DODAG per sink (see the figure). Each node in a DODAG, which is akin to a routing device in an IoT solution, has a node rank that defines the node’s position relative to other nodes with respect to a DODAG root.
The exact way RPL node rank is computed depends on the DAG’s objective function (OF). An OF defines how routing metrics, optimization objectives, and related functions are used to compute rank. In essence, the OF dictates the DODAG formation. The RPL topology is built using control messages that are transmitted as ICMPv6 messages. The three key RPL control messages are:
• DODAG information solicitation (DIS): The DIS solicits a DODAG information object (DIO) from an RPL node.
• DODAG information object (DIO): The DIO carries information that allows a node to discover a RPL Instance, learn its configuration parameters, select a DODAG parent set, and maintain the DODAG.
• Destination advertisement object (DAO): The DAO is used to propagate destination information upward along the DODAG.
To construct the DODAG topology, nodes may use a DIS message to solicit a DIO, or they may periodically send link-local multicast DIO messages. Nodes then listen for DIOs and use their information to join a new DODAG or to maintain an existing DODAG. Based on information in the DIOs, the node chooses parents that minimize the path cost to the DODAG root.
A successful implementation of the RPL could enable an IoT solution to meet its stated objective functions and goals. In the scope of RPL, a typical goal is to construct the DODAG according to a specific OF and to keep connectivity to a set of hosts. RPL is specifically optimized for MP2P and P2MP traffic patterns. Nodes are stateless, and the routing state information stored in each node is minimal. RPL also accounts for both link and node properties when choosing paths. And, link failures do not trigger a global network re-optimization.
For a large-scale IoT deployment (involving thousands of nodes and spread over a large geographical area), when the routing design and implementation minds the various features, functionalities, and attributes available in the RPL, the IoT solution could get a battery lifetime of years.3
The possibility of using IP-based networks could greatly reduce the energy and costs associated with wireless IoT communication, which would otherwise need expensive mobile-tower connectivity and GSM/EDGE-based communication. Such an RPL implementation could dramatically alter the rollout of IoT solutions for applications such as urban sensing networks.
1. “Connecting Low-Power and Lossy Networks to the Internet,” IETF Standards Update, JeongGil Ko and Andreas Terzis, Stephen Dawson-Haggerty and David E. Culler, Jonathan W. Hui, and Philip Levis, www.eecs.berkeley.edu/~stevedh/pubs/IEEECommMag11Ko.pdf
2. T. Winter (Ed.), P. Thubert (Ed.), and the ROLL Team. RPL: IPv6 Routing Protocol for Low power and Lossy Networks, Internet Engineering Task Force, RFC6550 (2012), http://tools.ietf.org/html/rfc6550
3. Tsiftes, Nicolas, Joakim Eriksson, and Adam Dunkels, “Low-power wireless IPv6 routing with ContikiRPL,” Proceedings of the 9th ACM/IEEE International Conference on Information Processing in Sensor Networks. ACM, 2010, www2.ee.kth.se/conferences/cpsweek2010/PDF/IPSN/p406-tsiftes.pdf
Ronak Sutaria is the principal researcher at Mindtree Research Labs, where he investigates IoT protocols, middleware, and platforms. His current focus is on data acquisition and data science solutions for smart city and dense urban sustainability initiatives. He has more than 12 years of experience in building large-scale Internet applications and online payment security-related technologies. He has bachelor of engineering and master of science degrees in computer science.