Collection Tree Extension of Reactive Routing Protocol for Low-Power and Lossy Networks

Abstract

This paper proposes an extension to reactive routing protocol, for efficient construction of a collection tree for data acquisition in sensor networks. The Lightweight On-Demand Ad hoc Distance Vector Routing Protocol-Next Generation (LOADng) is a reactive distance vector protocol which is intended for use in mobile ad hoc networks and low-power and lossy networks to build paths between source-destination pairs. In 2013, ITU-T has ratified the recommendation G.9903 Amendment 1, which includes LOADng in a specific normative annex for routing protocol in smart grids. The extension uses the mechanisms from LOADng, imposes minimal overhead and complexity, and enables a deployment to efficiently support “sensor-to-root” traffic, avoiding complications of unidirectional links in the collection tree. The protocol complexity, security, and interoperability are examined in detail. The simulation results show that the extension can effectively improve the efficiency of data acquisition in the network.

1. Introduction

“The Internet of Things” (IoT) assumes objects in our environment be part of the Internet, communicating with users and with each other and that these objects have communication as a commodity. Communication in “The Internet of Things” is a challenge, subject to resource constraints, fragile and low-capacity links, and dynamic and arbitrary topologies. Routing is among the challenges, which requires efficient protocols, able to converge rapidly even in very large networks, while exchanging limited control traffic and requiring limited memory and processing power.

One of the important applications of IoT is for data acquisition in sensor networks: a set of spatially distributed sensors that are used to monitor physical or environmental conditions, and transmit their data to a data concentrator (periodically, or triggered by some events). These data are transmitted by way of a multihop network and where the intermediary hops (routers) in that network are the sensor devices themselves. The collection of all paths from each sensor to the data concentrator forms a collection tree. Traffic in such a collection tree is commonly described as being “sensor-to-root” traffic or “multipoint-to-point” traffic, indicating that all traffic flows from the sensors to the data concentrator.

This paper describes a protocol for constructing such a collection tree in multihop sensor networks, where the protocol ensures that the resulting collection tree contains bidirectional paths between each sensor and the data concentrator. The protocol is defined as an extension to a reactive protocol: the LOADng routing protocol [1], which provides point-to-point routes between any two devices in a sensor network. Deploying both in unison permits efficient construction of both point-to-point routes and collection trees, by way of the same, simple protocol mechanisms.

1.1. Background and History

Since the late 90s, the Internet Engineering Task Force (IETF) (http://www.ietf.org) has embarked upon a path of developing routing protocols for networks with increasingly more fragile and low-capacity links, with less predetermined connectivity properties and with increasingly constrained router resources. In ′97, the MANET (Mobile Ad hoc Networks) working group was charted, then subsequently in 2006 and 2008, 6LoWPAN (IPv6 over Low Power WPAN) and ROLL (Routing over Low Power and Lossy Networks) working groups were charted.

(1) MANET Protocol Developments. The MANET working group has developed two protocol families: reactive protocols, including AODV (Ad hoc On-Demand Distance Vector Routing [2]), and proactive protocols, including OLSR (Optimized Link State Routing [3]). A distance vector protocol, AODV, operates in an on-demand fashion, acquiring and maintaining routes only while needed for carrying data, by way of a Route Request-Route Reply exchange. A link state protocol, OLSR, uses a periodic control messages exchanges, each router proactively maintaining a routing table with entries for all destinations in the network, which provides low delays but constant control overhead. A sizeable body of work exists, including studying the performance of these protocols in different scenarios and justifying their complementarity [4]. For the purpose of this paper, it suffices to observe that OLSR provides low delays and predictable, constant control overhead—at expense of requiring memory in each router for maintaining complete network topology. AODV limits the memory required for routing state to that for actively used routes—at the expense of delays for the Route Request-Route Reply exchange to take place and control overhead dependent on data flows.

After acquiring operational experiences, the MANET working group commenced by developing successors to OLSR and AODV, denoted by OLSRv2 and DYMO (Dynamic MANET On-Demand Routing). Whereas a relatively large and active community pushed OLSRv2 towards standardisation [5, 6], the momentum behind DYMO withered in the MANET working group http://tools.ietf.org/wg/manet/minutes?item=minutes81.html).

(2) 6LowPAN, ROLL, and Related Protocol Developments. The 6LowPAN (IPv6 over low power WPAN) working group was chartered for adapting IPv6 for operation over IEEE 802.15.4, accommodating characteristics of that MAC layer, and with a careful eye on resource constrained devices (memory, CPU, energy, and so forth). Part of the original charter for this working group was to develop protocols for routing in multihop topologies under such constrained conditions and over this particular MAC. Two initial philosophies to such routing were explored: mesh-under and route-over. The former, mesh-under, would, as part of an adaptation layer between 802.15.4 and IP, provide layer 2.5 multihop routing, that is, using link layer address for routing and presenting an underlying mesh-routed multihop topology as a single IP link. The latter, route-over, would expose the underlying multihop topology to the IP layer, whereupon IP routing would build multihop connectivity.

Several proposals for routing were presented in 6LowPAN, for each of these philosophies, including LOAD (6LoWPAN Ad hoc On-Demand Distance Vector Routing [7]). LOAD was a derivative of AODV but was adapted for link layer addresses and mesh-under routing, with some simplifications over AODV (e.g., removal of intermediate router replies and sequence numbers). However, 6LowPAN was addressing other issues regarding adapting IPv6 for IEEE 802.15.4, such as IP packet header compression, and solving the routing issues was suspended, delegated to a working group ROLL, and created in 2008 for this purpose. ROLL produced a routing protocol denoted by “routing protocol for low-power lossy networks” (RPL) [8] in 2011 based on the idea of collection tree protocol [9].

(3) Finally, towards LOADng. RPL as a collection tree protocol has several well-known issues with respect to supporting different kinds of traffic patterns, unidirection link handling, and algorithmic and code complexity [10]. On the other hand, while LOAD [7] development was suspended by the 6LoWPAN working group, AODV derivatives live on: IEEE 802.11s [11] is based on AODV, and the ITU-T G3-PLC standard [12], published in 2011, specifies the use of [7] at the MAC layer, for providing mesh-under routing for utility (electricity) metering networks. Justifications for using an AODV derivative in preference to RPL include that the former better supports bidirectional data flows such as a request/reply of a meter reading, as well as algorithmic and code complexity reasons [10].

The emergence of LLNs thus triggered a renewed interest in AODV-derived protocols for specific scenarios, resulting in work within the IETF [1, 13] for the purpose of standardisation of a successor to LOAD—denoted by LOADng (the Lightweight On-Demand Ad hoc Distance Vector Routing Protocol-Next Generation). LOADng incorporates the experiences from deploying LOAD—including, but not only, LLNs—and has been accepted as part of an update to the G3-PLC (Power Line Communication) ITU-T (International Telecommunication Union—Telecommunication Standardization Sector) standard for communication in the “smart grid” [14].

1.2. Statement of Purpose

There have been a lot of protocols proposed for data acquisition in sensor networks. In [15], the authors proposed collection tree protocol that uses ETX (expected transmission count) as the routing metric to construct one-way collection tree. A CDS-based network backbone for data collection is introduced in [16], to balance energy consumption and prolong the router lifetime in the backbone. A Pareto based multioptimization approach POCTP (Pareto Optimal Collection Tree Protocol) is discussed in [17] to ensure QoS such as transmission throughput, delay, and loss of packets. In [18], an average transmission time (ATT) metric is applied to routing protocol, under which real-time events are transferred along the routes with the shortest transmission time expectation. Multichannel is also used in [19] to reduce interference. Those protocols, some of them only support one-way traffic from sensor routers to one concentrator like [15], or hard to be extended for general sensor-to-sensor communications [16, 17]. Some of the protocols like [19] require specific support from lower layers, which are hard to be applied to normal sensor equipment.

The LOADng core specification aims at finding a route between any originator-destination pairs. This kind of point-to-point traffic pattern matches the basic traffic model of the Internet. However, in the world of smart grid, another important traffic pattern, called sensor-to-root, or multipoint-to-point exists. In such kind of scenarios, there are one or more concentrators that play as “root,” and all the other routers communicate with the root. If routes from all the other routers to the root are required, it is more efficient to build a “collection tree,” which is a directed graph that all edges are oriented toward and terminate at one root router.

This paper proposes an extension to a reactive routing protocol LOADng, denoted by LOADng Collection Tree Protocol (LOADng-CTP), for building a “collection tree” in environments, constrained in terms of computational power, memory, and energy. An example of the design target for LOADng-CTP is the ESB (Embedded Sensor Board [20]), with a TI MSP430 low-power microcontroller, an 1 MHz CPU, 2 kB RAM, and 60 kB flash ROM. The link layers typically used in LLNs impose strict limitations on packet sizes: in IEEE 802.15.4, the maximum physical layer packet size is 127 bytes and the resulting maximum frame size at the mac-layer is 102 bytes. If link-layer security is used, this may consume up to a further 21 bytes, which leaves just 81 bytes for upper layer protocols.

The LOADng-CTP presented in this paper is thus designed to meet the following requirements: (i)

effectively building a route from all sensors to the root and the route from the root to the sensors if required;

(ii)

unidirectional links being avoided in these routes;

(iii)

low overhead, easy collection tree maintenance;

(iv)

easy extension to LOADng, such that routers using only LOADng (without collection tree extension) can join the collection tree.

Although the specification in this paper is designated for LOADng, its basic mechanism can be applied to general reactive protocol, like AODV also.

The remainder of this paper is organized as follows. In Section 2, the LOADng-CTP specification is introduced, including related message format and main operations. The protocol is further analysed in Section 3, from the aspect of routing complexity, security, and interoperability. The simulation study is performed in Section 4, in which LOADng, LOADng-CTP, and RPL are compared. Section 5 concludes this paper.

2. LOADng-CTP Protocol Specification

LOADng Collection Tree Protocol (LOADng-CTP) is based on the operation and packet format of LOADng. Therefore, the current LOADng implementation can be easily extended to the collection tree protocol. In the following, the basic operation of LOADng is introduced briefly, followed by the single message and protocol processing required for collection tree building and maintenance.

2.1. LOADng Basic Operation

LOADng contains two main operations: Route Discovery and Route Maintenance.

(1) Route Discovery. During Route Discovery, RREQ (Route Request) messages are flooded through the network. In LOADng [1], only the destination of the RREQ will reply by generating and unicasting an RREP (Route Reply) to the originator of the RREQ. All RREQ and RREP messages, generated by a LOADng router, carry a monotonically increasing sequence number, permitting both duplicate detection, and detecting which of two messages contain the most “fresh” information.

(2) Route Maintenance. Route Maintenance is performed when an actively used route fails. Route failure is detected by way of a data packet not being deliverable to the next hop towards the intended destination. In LOADng, the RERR is unicasted to the source of data packet. On receiving the RERR at the source of data packet, a new Route Discovery can be performed, in order to discover a new route to the intended destination.

Compared to AODV, LOADng has the following characteristics. (i)

Modular design: the core specification defines the simple and lightweight core functions of the protocol. LOADng is extensible, by way of a flexible packet format permitting addition of arbitrary attributes and information via new message types and/or TLV (type-length-value) blocks. The LOADng protocol core is detailed in this section, with subsequent sections illustrating the use of the flexible architecture of LOADng for developing (interoperable and backwards compatible) protocol extensions.

(ii)

Optimised flooding: It can reduce the overhead incurred by RREQ forwarding. Jitter is employed, to reduce the probability of losses due to collisions on lower layers [21].

(iii)

Flexible addressing: address lengths from 1 to 16 octets are supported (i.e., IPv6, IPv4, 6LowPAN short addresses, Layer-2 MAC addresses, and so forth are all supported by LOADng). The only requirement is that, within a given routing domain, all addresses are of the same address length.

(iv)

Metrics: different metrics are supported, to make use of link information from different layers.

(v)

Destination replies: intermediate LOADng routers are explicitly prohibited from responding to RREQs, even if they may have active routes to the sought destination. All messages (RREQ or RREPs) generated by a given LOADng router share a single unique, monotonically increasing sequence number. This also eliminates Gratuitous RREPs while ensuring loop freedom. The rationale for this simplification reduced complexity of protocol operation and reduced message sizes—found to be without significant influence in the performance [22]. Allowing only the destination to reply to an RREQ also simplifies the task of securing the protocol, because the destination can thus sign the RREP message, and the originator could verify that it is the “real” destination that replies.

(vi)

Reduced state: a LOADng router is not required to maintain a precursor list; thus when forwarding a data packet to the recorded next hop on the path to the destination fails, an RERR is sent only to the originator of that data packet. The rationale for this simplification is an assumption that few overlapping routes are in use concurrently, and delay is not a critical issue in a given network.

2.2. Message for LOADng-CTP

LOADng-CTP introduces two flags to RREQ messages, carried by a so-called RREQ flag. (i)

RREQ COLLECTION_TREE_TRIGGER: when set, a receiving router will be triggered to discover with which of its neighbours it has bidirectional links.

(ii)

RREQ COLLECTION_TREE_BUILD: when set, a receiving router will build the route to the root.

In addition, a HELLO message [5] is used, which includes all the 1-hop neighbours of the router generating the HELLO message. The HELLO messages are broadcast and never forwarded. Bidirectional neighbours are identified by the exchange of HELLO messages.

2.3. Router Parameters for LOADng-CTP

LOADng-CTP uses the following parameters for protocol functioning. (i)

NET_TRAVERSAL_TIME: it is the maximum time that a packet is expected to take when traversing from one end of the network to the other.

(ii)

RREQ_MAX_JITTER: it is the maximum jitter for RREQ message transmission. Jitter is a randomly modifying timing mechanism to control traffic transmission in wireless networks to reduce the probability of transmission collisions [21].

(iii)

HELLO_MIN_JITTER: it is the minimum jitter for HELLO message transmission. HELLO_MIN_JITTER must be greater than 2 $\times$ RREQ_MAX_JITTER.

(iv)

HELLO_MAX_JITTER: it is the maximum jitter for HELLO message transmission.

(v)

RREP_REQUIRED: it is the flag to define if an RREP message is required on receiving RREQ_BUILD message, to build routes from the root to sensors.

2.4. LOADng-CTP Procedures

The collection tree is, then, built by way of the following procedure—initiated by the router wishing to be the root of the collection tree.

(1) Collection Tree Triggering (by the Root). The root generates an RREQ with COLLECTION_TREE_TRIGGER set (henceforth, denoted by RREQ_TRIGGER). Both the originator and destination of the RREQ_TRIGGER are set to the address of the root.

When an RREQ_TRIGGER is generated, an RREQ with COLLECTION_TREE_BUILD flag set (henceforth, denoted by RREQ_BUILD) is scheduled to be generated in 2 $\times$ NET_TRAVERSAL_TIME.

(2) Bidirectional Neighbour Discovery. On receiving a RREQ_TRIGGER, a router does the following. (i)

It records the address of the sending router (i.e., the neighbour, from which it received the RREQ_TRIGGER) in its neighbour set, with the status HEARD.

(ii)

If no earlier copy of that same RREQ_TRIGGER has been previously received,

(a)

the RREQ_TRIGGER is retransmitted, subject to a jitter of RREQ_MAX_JITTER, to reduce the chance of collisions (except the root router);

(b)

it schedules generation of a HELLO message, subject to a jitter of between HELLO_MIN_JITTER and HELLO_MAX_JITTER. When the scheduled HELLO message is generated, it lists the addresses of all the 1-hop neighbours, from which it has received a RREQ_TRIGGER.

On receiving a HELLO message, a router does the following. (i)

If it finds its own address listed in the HELLO message, it records the address of the sending router (i.e., the neighbour, from which it received the HELLO) in its neighbour set, with the status SYM (bidirectional).

(ii)

The HELLO message is never forwarded but discarded silently.

Thus, each router will learn with which among its neighbour routers it has a bidirectional (SYM) or unidirectional (HEARD) link.

(3) Collection Tree Building. For 2 $\times$ NET_TRAVERSAL_TIME after the RREQ_TRIGGER, the root generates a RREQ_BUILD.

On receiving a RREQ_BUILD, a router does the following. (i)

It verifies if the RREQ_BUILD was received from a neighbour with which it has a bidirectional (SYM) link. If not, the RREQ_BUILD is silently discarded.

(ii)

Otherwise, if no earlier copy of that same RREQ_BUILD has been previously received, or the RREQ_BUILD indicates a short path to the root,

(a)

a new routing entry is inserted into the routing table, with

(1)

next_hop = previous hop of the RREQ_BUILD,

(2)

destination = root;

(b)

the RREQ_BUILD is retransmitted, again subject to a jitter of RREQ_JITTER.

Thus, each router will record a route to the root, and this route will contain only bidirectional links. The collection tree is built, enabling upward traffic. Figure 1 illustrates the RREQ_BUILD processing.

Figure 1

LOADng-CTP RREQ_BUILD message processing.

(4) Root-to-Sensor Path Building. By exchanging RREQ_TRIGGER and RREQ_BUILD messages, all the sensors in the network obtained a path using only bidirectional links to the root. This is sufficient for applications like environment monitoring, automatic meter reading, and so forth. However, in some applications, such as firmware update or remote control, the root needs to send messages to sensors in the network. The paths from root to sensors are thus desired.

The sensors that require root-to-sensor traffic must have their RREP_REQUIRED flag set to be true. On receiving the RREQ_BUILD message, all the sensor routers with RREP_REQUIRED flag set must initiate an RREP message with content of (i)

RREP_originator = address of the sensor router;

(ii)

RREP_destination = address of the root.

The RREP is thus unicast to the root, subject to jitter RREP_JITTER. On receiving the RREP message, a routing tuple is created in the routing table with (i)

next_hop = previous hop of the RREP;

(ii)

destination = address of the RREP originator (RREP_originator).

Figure 2 depicts an example of root-sensor message exchange sequences by illustrating the four steps of LOADng-CTP protocol (collection tree triggering, bidirectional neighbour discovery, collection tree build, and root-to-sensor path building). In the example, the root router builds a collections tree connecting sensor routers A and B, with the topology shown in Figure 2(a). The message exchange is shown in Figure 2(b). The pseudosequence number in the brackets is used just for distinguishing different messages in this figure. In a real protocol implementation, sequence numbers are generated independently at each router.

Figure 2

Message exchange of LOADng-CTP between root and sensors.

2.5. Collection Tree Maintenance

Based on the operation introduced in Section 2.4, a collection tree is built to enable data traffic transmission between the root router and all the other sensors. However, route failure could still happen, due to the “lossy” nature of sensor networks or topology changes, such as (i)

loss of control message during the collection tree building process;

(ii)

routing entries expire because of not updated timely;

(iii)

participation of new sensors;

(iv)

Sensors quit the network because of movement or battery drain.

LOADng-CTP supports per-path maintenance when a path failure is detected, without rebuilding the whole collection tree. A new route discovery is initiated according to usual procedures of route discovery if (i)

the data packet to be forwarded cannot find a routing tuple to the desired destination in the routing table, or

(ii)

the link to the “next hop” indicated by the routing table is detected broken.

To avoid RREQ being broadcast through the whole network and take benefits from that “most of other neighbour routers might have an available route to the root,” a Smart Route Request scheme can be employed: if an intermediate router, receiving the RREQ, does not have an available route to the destination, the RREQ is forwarded as normal. If the intermediate router has a route to the root, that intermediate router will unicast the RREQ to the destination according to the routing table.

Figure 3 gives an example of path maintenance in collection tree. Router D is the root, and the link between S–D is detected broken. Routers A and B have already direct path to D, and C has also a routing tuple to D (by going through S). Figure 3(a) depicts the route discovery initiated by S according to LOADng basic operation. Because only the destination is allowed to reply to the RREQ message, sensor routers A, B, and C have to rebroadcast the RREQ message, even they have already routing tuples to D. This renders a network-wide flooding: for a network with n routers, n RREQ message retransmissions are required.

Figure 3

An example of route maintenance. Router D is the root. The link between S–D is detected broken. Sensor routers A, B, and C still have routing tuple to D.

With smart route request, as shown in Figure 3(b), routers A, B, and C will unicast the RREQ to root D according to their routing tables, and D can choose the best path to send RREP message. By doing so, the RREQ dissemination is limited locally (4 retransmission in this example), and the routing overhead can be greatly reduced.

When a link on an active route to a destination is detected as broken (by way of inability to forward a data packet towards that destination), an RERR (route error) message is unicast to the source of the undeliverable data packet. Both this intermediate router and the source router need to initiate a new route discovery procedure.

3. LOADng-CTP Protocol Analyses

This section analyzes the main features of the LOADng-CTP, including protocol complexity, security considerations, and its interoperability with LOADng protocol.

3.1. Protocol Complexity

Unlike link-state routing protocols such as OSPF [23] or OLSR [6], which require keeping a network topology locally and run the Dijkstra algorithm, LOADng and LOADng-CTP concern only the basic additive operation when calculating link metrics. Therefore, the computational complexity is negligible. A very important concern of routing protocol for sensor networks is its routing overhead: the message required to maintain the routing table.

For simplicity, a balanced tree model is considered: there is a single root in the tree, with total height of H. The height of root is $0$ , and the leaf nodes are with height $H - 1$ . Every node in the tree (except the leaf nodes) has C children ( $C > 1$ ). Figure 4 gives an example of balanced tree with $C = 2$ .

Figure 4

An example of balanced tree. Every parent has 2 children ( $C = 2$ ).

The number of nodes at height $h (0 \leq h \leq H - 1)$ is $n_{h} = C^{h}$ . The total number of nodes in the tree is

\begin{matrix} N = 1 + C + C^{2} + \dots + C^{(H - 1)} = \frac{1 - C^{H}}{1 - C} (C > 1) . \end{matrix}

(1)

In LOADng-CTP, the message required for collection tree building is the sum of RREQ_TRIGGER, HELLO, and RREQ_BUILD:

\begin{matrix} RREQ = 3 N . \end{matrix}

(2)

If root-to-sensor paths are required, every sensor also has to unicast an RREP message to the root.

The number of RREP messages forwarded by all the routers at height h is

\begin{matrix} RRE P_{h} = C^{h} \sum_{i = 0}^{H - h - 1} C^{i} = C^{h} \frac{1 - C^{H - h}}{1 - C} . \end{matrix}

(3)

The total number of RREP can thus be given by

\begin{matrix} RRE P_{All} = \sum_{h = 1}^{H - 1} ‍ RRE P_{h} = \sum_{h = 1}^{H - 1} ‍ \frac{C^{h}}{1 - C} - \sum_{h = 1}^{H - 1} ‍ \frac{C^{H}}{1 - C} . \end{matrix}

(4)

Considering (1), the total number of RREP forwarding is

\begin{array}{l} RRE P_{All} = \frac{1}{1 - C} \frac{C - C^{H}}{1 - C} - \frac{(H - 1) C^{H}}{1 - C} \\ = N H - N + \frac{N - H}{1 - C} . \end{array}

(5)

Considering $H = ⌊ lo g_{C} N ⌋$ , the total number of RREP messages thus scales with $O (N \log N)$ .

For the basic LOADng protocol, by which only point-to-point route build is supported, the number of RREQ messages forwarding required to build path from all the sensors to the root is

\begin{matrix} RREQ = N^{2} . \end{matrix}

(6)

The RREP message is always needed in LOADng basic operation, which is the same as (5).

Based on (2), (5), and (6), it can be concluded that LOADng-CTP reduced routing overhead from $O (N^{2})$ to $O (N)$ compared to basic LOADng mechanism if only sensor-to-root paths are needed, or $O (N \log N)$ , if root-to-sensor paths are also required.

3.2. Security Considerations

(1) Protocol Vulnerability. The collection tree building process relies on strictly ordered message sequences: RREQ_TRIGGER message for triggering the building process, then HELLO message for bidirectional neighbour check, and RREQ_BUILD message for collection tree build in the end. The message emission is controlled by router parameters like NET_TRAVERSAL_TIME, RREQ_JITTER, and HELLO_JITTER.

The receiving order can be expected if those parameters are set correctly; however, in real implementations, there might exist misconfigured routers, or even compromised routers that emit messages out of order. For example, if a router sends a HELLO message before it receives all the RREQ_TRIGGER messages from its neighbours, or an RREQ_BUILD message is received before the HELLO message exchange finished, the router cannot identify its bidirectional neighbours correctly—thus it is not able to join the collection tree as expected.

In addition to message misordering, LOADng-CTP is also prone to attacks like block-hole or spoofing attacks [24, 25]. Malicious control traffic can have severe impact on the network stability.

(2) Security Framework. One of the main objectives when specifying LOADng was to provide a modular architecture with a core module that is easily extensible. The rationale for this decision was that rarely “one-size-fits-all” in the area of constrained networks. This is particularly true for security extensions: some networks may not require any level of Layer 3 security, for example, because physical access is limited or lower layer protection is sufficient. Other networks require integrity protection with a lightweight cipher suite due to limited processing power and memory of routers. In some cases, security requirements are tighter and confidentiality as well as strong cryptographic ciphers is required.

The IETF has standardized a security framework for protocols using the message and packet format defined in [26], which is used by LOADng-CTP. (Note that this framework is currently being revised in a succeeding document that will obsolete RFC6622 once approved: http://tools.ietf.org/html/draft-ietf-manet-rfc6622-bis). Reference [27] specifies a syntactical representation of security-related information in TLVs for use with [26] addresses, messages, and packets. That specification does not represent a stand-alone protocol but is intended for use by MANET routing protocols, or security extensions thereof, such as LOADng-CTP.

Figure 5 depicts the architecture of a module for LOADng-CTP that provides integrity and nonrepudiation for LOADng, using the framework specified in [27].

Figure 5

Relationship with RFC5444, RFC6622, and LOADng-CTP.

Incoming RFC5444 packets are first parsed by the RFC5444 parser that demultiplexes messages and sends them to the protocol “owning” the message type. As each RFC5444 packet may contain multiple messages that are used by different protocols on a router, the message type is used to demultiplex and send the message to the appropriate protocol instance. A message intended for LOADng-CTP will then be forwarded to the security extension module that verifies the signature contained in a signature TLV inside the message. As the TLV contains additional information, such as the hash function (e.g., SHA-256, Secure Hash Algorithm) and the cryptographic function (e.g., AES, Advanced Encryption Standard), the module can choose the correct key and verify the integrity protection. If the message signature is correct, the message is handed over to the LOADng-CTP module; otherwise it is rejected. Similarly, outgoing messages from LOADng-CTP are handed over to the security module, which in turn adds the TLV containing the digital signature of the message. Then the message is handed over to the RFC5444 module that multiplexes it into a packet.

During the message signature generation as well as verification process, [27] takes special consideration for mutable fields, such as hop count and hop limit. In addition to hop count and limit, the route metric contained in a metric TLV is also updated along the path of a message and can therefore not be protected by a digital signature. LOADng-CTP lists these mutable fields explicitly. While this is a security problem that needs to be addressed in addition to a pure message signature (and is not discussed in this paper), based on the message format of LOADng-CTP messages, at least the calculation of signature is easy. This is because the message size does not change as no field is added or removed during the forwarding process of a message through the network (and therefore no other fields, such as message size or TLV block size, need to be recalculated). The metric can simply be replaced by a sequence of zeros before calculating the signature and is then restored afterwards.

In addition to message integrity, packets may also be digitally signed. As packets are used hop-by-hop, that is, are never forwarded, this is useful to authenticate the previous hop along the path of a message. Otherwise, a router not having any credentials may, for example, simply forward a correctly signed RREP message from one adjacent router to another and increase the hop count. As the hop count is excluded from the signature calculation, the message integrity would still be valid. Packet signatures mitigate this problem at the expense of increased overhead on the channel. Note also that it is difficult to detect simple forwarding of a frame without modifying the content, also known as “wormhole attack.”

3.3. Interoperability Considerations

As sensor networks and low-power and lossy networks are generally decentralized system, devices would possibly work in a heterogeneous environment: there might be old devices with basic functions, and newly jointed devices with extensions in the same routing domain. This requires interoperability between routers using LOADng-CTP and LOADng routers without collection tree extension (denoted by LOADng-core router).

A LOADng-core router will forward RREQ_TRIGGER and RREQ_BUILD message as normal RREQ messages, so it will not affect the collection tree building process of other routers in the network. But because LOADng-core routers cannot generate HELLO messages themselves and are not able to be verified as bidirectional neighbour, therefore, LOADng routers will not join the collection tree during the collection tree building process described in this section. However, these routers can participate in the collection tree by initiating a new RREQ message to the root and thus join the collection tree as “leaf nodes” (i.e., nodes without children), as shown in Figure 6.

Figure 6

An example of interoperability between LOADng-CTP (white nodes) and LOADng-core routers (grey nodes).

During the collection tree building process, LOADng-core routers will not be able to function as parents of other routers. As depicted in Figure 6, router C will choose B as parent, even if S probably provides a shorter path to the root. If the LOADng-core router is on the only path to the root,for example, router E has to go through S to reach the root, a new RREQ will be initiated to the root.

The existence of LOADng-core routers will possibly increase the routing overhead in the network by initiating more route discoveries. But with the smart RREQ introduced in Section 2.5, the RREQ dissemination can be kept locally, thus without introducing much influence in the networks.

4. Simulation and Performance Analyses

4.1. Simulation Settings

In order to understand the performance impact of the collection tree extension to LOADng, this section presents a set of ns2 simulations, comparing LOADng, LOADng-CTP, and RPL, with the parameters of the trickle timer in RPL being set according to [8]. Simulations were made with varying numbers of routers from 63 to 500 and placed statically randomly in a square field. The networks have consistent density of nodes; that is, the simulation field grows as the number of routers increases: 1100 m × 1100 m for 63 nodes, 1580 m × 1580 m for 125 nodes, 2230 m × 2230 m for 250 nodes, and 3160 m × 3160 m for 500 nodes. This simulates smart grid in suburban areas. As the size of the network grows, the scalability of the protocol can be tested.

The network is subject to sensor-to-root traffic, like periodic meter reading: all routers generate traffic, for which the destination always is a single, fixed router in the network. Each data source transmits a 512-byte data packet every 5 seconds, in bursts lasting for 80 seconds each, for a total simulation time of 100 s.

For the purpose of this study, router mobility was not considered. Simulations were conducted using the TwoRayGround propagation model and the IEEE 802.11 MAC. Although there are various low-layer technologies more commonly (and, perhaps, more viably) used for LLNs (power line communication, 802.15.4, low-power wifi, Bluetooth low energy, etc.), 802.11 provides basic distributed mechanisms for channel access, such as DCF (distributed coordination function), CSMA/CA (carrier sense multiple access with collision avoidance). Therefore, general behaviour of a protocol can be inferred from simulations using 802.11.

In the simulations, three types of routing protocols are compared. (i)

LOADng core specification [1], referred to as LOADng in the following section. The routes are built reactively when there are data packets need to be sent.

(ii)

LOADng with collection tree extension, referred to as LOADng-CTP. The collection tree is triggered and built before the sending of data packets.

(iii)

RPL with trickle timer, referred to as RPL. The parameters of trickle timer are set according to [8].

4.2. Simulation Results

Figure 7 depicts the delivery ratio of three protocols. Both LOADng-CTP and RPL obtain delivery ratios close to 100%, regardless of number of nodes. LOADng, initiating route discovery for every router (network-wide broadcast), incurs a high number of collisions on the MAC layer (shown in Figure 8), and thus a lower data delivery ratio, especially in larger scenarios.

Figure 7

Packet delivery ratio.

Figure 8

Number of MAC layer collisions.

Figure 9 illustrates the average end-to-end delay. LOADng has longer delay mainly because the route discovery is performed reactively; that is, the data packets have to wait the finish of route discovery before being sent out. LOADng-CTP and RPL have routes a priori available, thus exhibiting identical delays.

Figure 9

Average end-to-end delay.

For the sensor networks, the routing overhead is also a crucial consideration. Figures 10 and 11 show the number of overhead packets per router and average overhead of network (bytes/second), respectively, which the networks are needed to converge to a stable state; that is, every router has a route to the root.

Figure 10

Number of overhead packets transmitted by each router.

Figure 11

Overhead bytes per second in the whole network.

The overhead packets of LOADng-CTP and RPL grow linearly with RPL sending twice as many packets as LOADng-CTP and RPL sending 10 times more bytes/s as compared to LOADng-CTP, due to the RPL control packets (mainly, the DIOs) being bigger [10]: a DIO packet takes up to 40 octets in these scenarios, whereas a LOADng-CTP RREQ and RREP packet typically are 10 octets (base header of 24 octets, plus other options and addresses). The overhead of LOADng grows exponentially as the number of nodes increases, up to 700,000 packets for scenarios of 500 nodes (not drawn in the figure). The point-to-point based basic LOADng mechanism is not optimized for sensor-to-root traffic.

5. Conclusion

This paper has presented an extension, LOADng-CTP, to the reactive LOADng routing protocol, permitting efficient and on-demand construction of collection trees for supporting sensor-to-root traffic types. LOADng-CTP permits finding paths between a root router and all the other sensor routers in the network using bidirectional links. The protocol supports per-path route maintenance without rebuilding the whole collection tree. Another key aspect of LOADng-CTP is that any router can at any time determine that it needs to act as a root for sensor-to-root traffic and spawn a collection tree construction; this, without requiring that said router is specifically provisioned for this purpose (no extra state, processing power, required).

The main features of LOADng-CTP are analysed. The routing overhead is reduced to $O (N)$ for collection tree building, compared to $O (N^{2})$ of LOADng core specification (N is the number of routers in the network). An extensible security framework is proposed to protect the integrity of routing message exchange. The interoperability between collection tree extension and LOADng core specification is considered. The LOADng routers without collection tree extension can also join the collection tree by initiating a route discovery.

The performance of this extension has been studied; revealing delays and data delivery rations, comparable with RPL, are obtained while at the same time yielding considerably lower control traffic overheads. Compared to basic LOADng, the performance of the LOADng-CTP extension yields better performance: lower overhead, higher data delivery ratios, and lower delays.

Footnotes

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

Acknowledgments

The authors would like to gratefully acknowledge Ulrich Herberg, Axel Colin de Verdiere, Yuichi Igarashi, Christos Verikoukis (assigned editor), and anonymous reviewers of the paper for valuable comments, reviews, and technical discussions.

References

Clausen

de Verdiere

A. C.

Niktash

Igarashi

Satoh

Herberg

The lln on-demand ad hoc distance-vector routing protocol—next generation

The Internet Engineering Task Force, October 2013, internet Draft, work in progress, draft-clausen-lln-loadng

Perkins

Belding-Royer

Das

Ad hoc On-Demand Distance Vector (AODV) Routing

Experimental RFC, 3561, July 2003

Clausen

Jacquet

Optimized Link State Routing Protocol (OLSR)

Experimental RFC, 3626, October 2003

Clausen

L. V. T.

Jacquet

Comparative study of routing protocols for mobile ad-hoc networks

Proceedings of the IFIP MedHocNet

September 2002

Sardinia, Italy

Clausen

Dearlove

Dean

Mobile Ad Hoc Network (MANET) Neighborhood Discovery Protocol (NHDP)

RFC, 6130, IETF, April 2010

Clausen

Dearlove

Jacquet

Herberg

The Optimized Link State Routing Protocol version 2

Internet Draft, draft-ietf-manetolsrv2- 19, work in progress, March 2013

Kim

Park

S. D.

Montenegro

Yoo

Kushalnagar

6LoWPAN Ad Hoc On-Demand Distance Vector Routing

Internet Draft, work in progress, draft-daniel-6lowpan-load-adhocrouting- 03, June 2007

Winter

Thubert

Brandt

Hui

Kelsey

Levis

Pister

Struik

Vasseur

RPL: IPv6 Routing Protocol for Low power and Lossy Networks

IETF RFC6550, March 2011

Gnawali

Fonseca

Jamieson

Moss

Levis

The Collection Tree Protocol (CTP)

TinyOS, Tech. Rep., 2009, http://sing.stanford.edu/pubs/sing-09-01.pdf

10.

Clausen

de Verdiere

A. C.

Herberg

Igarashi

Experiences with RPL: IPv6 Routing Protocol for Low power and Lossy Networks

The Internet Engineering Task Force, internet Draft, work in progress, draft-clausen-lln-rpl-experiences, February 2013

11.

Hiertz

G. R.

Max

Rui

Denteneer

Berlemann

Principles of IEEE 802.11s

Proceedings of the 16th International Conference on Computer Communications and Networks (ICCCN '07)

August 2007

Honolulu, Hawaii, USA

1002 1007

2-s2.0-40949119126

10.1109/ICCCN.2007.4317949

12.

ITU-T G. 9956: Narrow-Band OFDM power line communication transceivers—Data link layer specification

November 2011

13.

Clausen

Camacho

de Verdiere

A. C.

Igarashi

Satoh

Morii

Interoperability report for the lightweight on-demand ad hoc distance-vector routing protocol—next generation (loadng)

The Internet Engineering Task Force, internet Draft, work in progress, draft-lavenu-lln-loadng-interoperability-report, December 2012

14.

ITU

ITU-T G. 9903: Narrow-band orthogonal frequency division multiplexing power line communication transceivers for G3-PLC networks: Amendment 1

May 2013

15.

Lei

J. J.

Park

Kwon

G. I.

A reliable data collection protocol based on erasure-resilient code in asymmetric wireless sensor networks

International Journal of Distributed Sensor Networks 2013 2013 8

730819

10.1155/2013/730819

16.

Kui

Sheng

Liang

Constructing a cds-based network backbone for data collection in wireless sensor networks

International Journal of Distributed Sensor Networks 2013 2013 12

258081

10.1155/2013/258081

17.

Y.-Z.

Quan

D.-P.

Han

H.-G.

Pareto Optimal Collection Tree Protocol for industrial monitoring WSNs

Proceedings of the IEEE GLOBECOM Workshops (GC Wkshps '11)

December 2011

Houston, Tex, USA

508 512

2-s2.0-84858428644

10.1109/GLOCOMW.2011.6162501

18.

Tang

Fan

A transmission time based routing protocol for clustered collection tree wireless sensor networks

Proceedings of the International Conference on Computational and Information Sciences (ICCIS '10)

December 2010

Chengdu, China

21 24

2-s2.0-79952424427

10.1109/ICCIS.2010.13

19.

Buengbon

Tanwongvarl

Chantaraskul

Multi-channel collection tree protocol for wireless sensor networks

Proceedings of the 10th International Conference on Electrical Engineering/ Electronics, Computer, Telecommunications and Information Technology (ECTI-CON '13)

2013

1 5

20.

The ESB Embedded Sensor Board

2013, http://contiki.sourceforge.net/docs/2.6/a01781.html

21.

Clausen

Dearlove

Adamson

Jitter Considerations in MANETs

IETF Inf. RFC, 5148, February 2008

22.

Clausen

de Verdiere

A. C.

LOADng: Towards AODV Version 2

in VTC Fall. IEEE, pp. 1–5, 2012

23.

Moy

OSPF Version 2

RFC, 2328, IETF, April 1998

24.

Wang

Bhargava

B. K.

On vulnerability and protection of ad hoc on-demand distance vector protocol

Proceedings of the 10th International Conference on Telecommunications (ICT '03)

2003

375 382

25.

Ning

Sun

How to misuse AODV: a case study of insider attacks against mobile ad-hoc routing protocols

Ad Hoc Networks 2005 3 6 795 819

2-s2.0-24144437206

10.1016/j.adhoc.2004.04.001

26.

Clausen

Dearlove

Dean

Adjih

Generalized Mobile Ad Hoc Network (MANET) Packet/Message Format

RFC, 5444, IETF, Feburary 2009

27.

Herberg

Clausen

Integrity Check Value and Timestamp TLV Definitions for Mobile Ad Hoc Networks (MANETs)

RFC, 6622, IETF, May 2012