Jiazi Yi

Thomas Clausen
email: thomas@thomasclausen.org

Collection Tree Extension of LOADng Protocol for Low-power and Lossy Networks

Keywords: sensor network, collection tree, routing protocol, LOADng

The Lightweight On-demand Ad hoc Distancevector 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. This paper proposes an extension to the LOADng, for efficient construction of a collection tree for data acquisition in sensor networks. 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 uni-directional 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.

I. INTRODUCTION

"The Internet of Things" (IoT) assumes objects in our environment to be part of the Internet, communicating with users and with each other -and that these objects have communication as a commodity, rather than as their reason for existence. Communication in "The Internet of Things" is a challenge, subject to resource constraints, fragile and lowcapacity links, 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, etc., and by their own impulse (either periodically or triggered by some event) transmit their data to a data concentrator (sink). These data are transmitted by way of a multi-hop 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 form 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 multi-hop sensor networks, where the protocol ensures that the resulting collection tree contains bi-directional paths between each sensor and the data concentrator. The protocol is defined as an extension to the LOADng routing protocol [START_REF] Clausen | The lln on-demand ad hoc distance-vector routing protocol -next generation[END_REF], 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.

A. Background and History

Since the late 90s, the Internet Engineering Task Force (IETF) 1 has embarked upon a path of developing routing protocols for networks with increasingly more fragile and lowcapacity links, with less pre-determined connectivity properties and with increasingly constrained router resources. In '97, by chartering the MANET (Mobile Ad hoc Networks) working group, then subsequently in 2006 and 2008 by chartering the 6LoWPAN (IPv6 over Low power WPAN) and ROLL (Routing Over Low power and Lossy networks) working groups.

1) MANET Protocol Developments: The MANET working group has developed of two protocol families: reactive protocols, including AODV (Ad hoc On-demand Distance Vector Routing [START_REF] Perkins | Ad hoc On-Demand Distance Vector (AODV) Routing[END_REF]), and proactive protocols, including OLSR (Optimized Link State Routing [START_REF] Clausen | Optimized Link State Routing Protocol (OLSR)[END_REF]). 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 [START_REF] Clausen | Comparative study of routing protocols for mobile ad-hoc networks[END_REF] . 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 developing successors to OLSR and AODV, denoted OLSRv2 and DYMO (Dynamic MANET Ondemand Routing). Whereas a relatively large and active community around OLSR thus standardized OLSRv2 [START_REF] Clausen | Mobile Ad Hoc Network (MANET) Neighborhood Discovery Protocol (NHDP)[END_REF] [6], the momentum behind DYMO withered in the MANET working group 2 .

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, ...). 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, meshunder, would, as part of an adaptation layer between 802.15.4 and IP, provide Layer 2.5 multi-hop routing, i.e., using link layer address for routing, and presenting an underlying meshrouted multi-hop topology as a single IP link. The latter, route-over, would expose the underlying multi-hop topology to the IP layer, whereupon IP routing would build multi-hop connectivity.

Several proposals for routing were presented in 6LowPAN, for each of these philosophies, including LOAD (6LoWPAN Ad Hoc On-Demand Distance Vector Routing [START_REF] Kim | 6LoWPAN Ad Hoc On-Demand Distance Vector Routing[END_REF]). LOAD was a derivative of AODV, but adapted for link layer addresses and mesh-under routing, and 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, created in 2008 for this purpose. ROLL produced a routing protocol denoted "Routing Protocol for Low-power lossy networks" (RPL) [START_REF] Winter | RPL: IPv6 Routing Protocol for Low power and Lossy Networks[END_REF] in 2011 based on the idea of collection tree protocol [START_REF] Gnawali | The Collection Tree Protocol (CTP)[END_REF].

3) Finally, Towards LOADng: RPL as a collection tree protocol has several well known issues with respect to supporting different kinds of traffic patterns, uni-direction link handling, as well as algorithmic and code complexity [START_REF] Clausen | Experiences with RPL: IPv6 Routing Protocol for Low power and Lossy Networks[END_REF]. On the other hand, while LOAD [START_REF] Kim | 6LoWPAN Ad Hoc On-Demand Distance Vector Routing[END_REF] development was suspended by the 6LoWPAN working group, pending the results from ROLL and experiences with RPL, AODV derivatives live on: IEEE 802.11s [START_REF] Hiertz | Principles of ieee 802.11s[END_REF] is based on AODV, and the ITU-T G3-PLC standard [START_REF] Itu-T G | Narrow-Band OFDM power line communication transceivers -Data link layer specification[END_REF], published in 2011, specifies the use of [START_REF] Kim | 6LoWPAN Ad Hoc On-Demand Distance Vector Routing[END_REF] 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 bi-directional data flows such as a request/reply of a meter reading, as well as algorithmic and code complexity reasons [START_REF] Clausen | Experiences with RPL: IPv6 Routing Protocol for Low power and Lossy Networks[END_REF].

The emergence of LLNs thus triggered a renewed interest in AODV-derived protocols for specific scenarios, resulting in work within the IETF [START_REF] Clausen | The lln on-demand ad hoc distance-vector routing protocol -next generation[END_REF] [START_REF] Clausen | Interoperability report for the lightweight on-demand ad hoc distance-vector routing protocol -next generation (loadng)[END_REF] for the purpose of stan-dardisation of a successor to LOAD -denoted LOADng (the Lightweight On-demand Ad hoc Distance-vector Routing Protocol -Next Generation). LOADng incorporates the experiences from deploying LOAD -including, but not only, in 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" [START_REF] Itu-T G | Narrow-band orthogonal frequency division multiplexing power line communication transceivers for G3-PLC networks: Amendment 1[END_REF].

B. Statement of Purpose

There are have been a lot of protocols proposed for data acquisition in sensor networks. In [START_REF] Lei | A reliable data collection protocol based on erasure-resilient code in asymmetric wireless sensor networks[END_REF], 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 [START_REF] Kui | Constructing a cds-based network backbone for data collection in wireless sensor networks[END_REF] , to balance energy consumption and prolong the router lifetime in the backbone. A Pareto based multi-optimization approach POCTP (Pareto Optimal Collection Tree Protocol) is discussed in [START_REF] Yi-Zhi | Pareto optimal collection tree protocol for industrial monitoring wsns[END_REF] to ensure QoS such as transmission throughput, delay, loss of packets. In [START_REF] Tang | A transmission time based routing protocol for clustered collection tree wireless sensor networks[END_REF], 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. Multi-channel is also used in [START_REF] Buengbon | Multi-channel collection tree protocol for wireless sensor networks[END_REF] to reduce interference. Those protocols, some of them only support one-way traffic from sensor routers to one concentrator like [START_REF] Lei | A reliable data collection protocol based on erasure-resilient code in asymmetric wireless sensor networks[END_REF], or hard to be extended for general sensor-to-sensor communications [16] [17]. Some of the protocols like [START_REF] Buengbon | Multi-channel collection tree protocol for wireless sensor networks[END_REF] requires specific support from lower layers, which are hard to be applied to normal sensor equipments.

The LOADng core specification aims at finding a route between any originator-destination pairs. This kind of pointto-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 multipointto-point exists. In such kind of scenarios, there is one or more concentrators that plays 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 LOADng, denoted LOADng Collection Tree Protocol (LOADng-CTP), for building a "collection tree" in environments, constrained in terms of computational power, memory, and in energy. An example of the design target for LOADng-CTP is the ESB (Embedded Sensor Board [START_REF]The ESB Embedded Sensor Board[END_REF]), with a TI MSP430 low-power microcontroller, an 1MHz CPU, 2kB RAM and 60kB 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, 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:

• Effectively build a route from all sensors to the root, and the route from the root to the sensors if required. • Uni-directional links being avoided in these routes.

• Low overhead, easy collection tree maintenance.

• Easy extension to LOADng, such that routers using only LOADng (without collection tree extension) can join the collection tree. The remainder of this paper is organized as follows: In section II, the LOADng-CTP specification is introduced, including related message format and main operations. The protocol is further analysed in section III, from the aspect of routing complexity, security and interoperability. The simulation study is performed in section IV, in which LOADng, LOADng-CTP and RPL are compared. Section V concludes this paper .

II. 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.

A. 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 [START_REF] Clausen | The lln on-demand ad hoc distance-vector routing protocol -next generation[END_REF], only the destination of the RREQ will reply by generating and unicasting a 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 contains 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:

• Modular design: The core specification defines the simple and light-weight 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. • Optimised Flooding: Reducing the overhead incurred by RREQ forwarding. Jitter is employed, to reduce the probability of losses due to collisions on lower layers [START_REF] Clausen | Jitter Considerations in MANETs[END_REF]. • Flexible Addressing: Address lengths from 1-16 octets are supported 3 . The only requirement is, that within a given routing domain, all addresses are of the same address length. • Metrics: Different metrics are supported, to make use of link information from different layers. • Destination-Replies: Intermediate LOADng Routersare 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 is reduced complexity of protocol operation and reduced message sizes -found to be without significant influence in the performance [START_REF] Clausen | LOADng: Towards AODV Version 2[END_REF].

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. • Reduced state: A LOADng Router is not required to maintain a precursor list, thus when forwarding of 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.

B. Message for LOADng-CTP

LOADng-CTP introduces two flags to RREQ messages, carried by a so-called RREQ flag:

• RREQ COLLECTION TREE TRIGGER: when set, a receiving router will be triggered to discover with which of its neighbours it has bi-directional links. • RREQ COLLECTION TREE BUILD: when set, a receiving router will build the route to the root. In addition, a HELLO message [START_REF] Clausen | Mobile Ad Hoc Network (MANET) Neighborhood Discovery Protocol (NHDP)[END_REF] is used, which includes all the 1-hop neighbours of the router generating the HELLO message. The HELLO message are broadcast, and never forwarded. It permits verification of bidirectionally of links before admitting them to the collection tree.

C. Router Parameters for LOADng-CTP

LOADng-CTP uses the following parameters for protocol functioning:

• NET TRAVERSAL TIME: the maximum time that a packet is expected to take when traversing from one end of the network to the other. • RREQ MAX JITTER: 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 [START_REF] Clausen | Jitter Considerations in MANETs[END_REF]. • HELLO MIN JITTER: is the minimum jitter for HELLO message transmission. HELLO MIN JITTER must be greater than 2× RREQ MAX JITTER. • HELLO MAX JITTER: is the maximum jitter for HELLO message transmission. • RREP REQUIRED: is the flag to define if an RREP message is required on receiving RREQ BUILD message, to build routes from the root to sensors.

D. LOADng-CTP Procedures

The collection tree is, then, build 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 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 RREQ BUILD) is scheduled to be generated in 2×NET TRAVERSAL TIME.

2) Bi-directional neighbour discovery: On receiving a RREQ TRIGGER, a router:

• 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. • If no earlier copy of that same RREQ TRIGGER has been previously received:

-The RREQ TRIGGER is retransmitted, subject to a jitter of RREQ MAX JITTER, to reduce the chance of collisions (except the root router). -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:

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

• The HELLO message is never forwarded, but discarded silently. Thus, each router will learn with which among its neighbour routers it has a bi-directional (SYM) or uni-directional (HEARD) link.

3) Collection tree building: 2×NET TRAVERSAL TIME after the RREQ TRIGGER, the root generates a RREQ BUILD.

On receiving a RREQ BUILD, a router:

• Verifies if the RREQ BUILD was received from a neighbour with which it has an bi-directional (SYM) link. If not, the RREQ BUILD is silently discarded. • 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 new routing entry is inserted into the routing table, with * next hop = previous hop of the RREQ BUILD; * destination = root -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 bi-directional links. The collection tree is built, enabling upward traffic. Figure 1 illustrates the RREQ BUILD processing. 4) Root-to-sensor Path Building: By exchanging of RREQ TRIGGER and RREQ BUILD messages, all the sensors in the network obtained a path using only bi-directional links to the root. This is sufficient for applications like environment monitoring, automatic meter reading, etc. 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 true. On receiving the RREQ BUILD message, all the sensor routers with RREP REQUIRED flag set must initiate an RREP message with content of:

• RREP originator = address of the sensor router;

• RREP destination = address of the root.

The RREP is thus unicast to the root, subjecting to jitter RREP JITTER. On receiving the RREP message, a routing tuple is created in the routing table with:

• next hop = previous hop of the RREP;

• 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, bi-directional 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 2a. The message exchange is shown in figure 2b. The pseudo-sequence 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. HE LLO [START_REF] Clausen | Optimized Link State Routing Protocol (OLSR)[END_REF] (br oad cas t)

RR EQ _B UIL D [START_REF] Clausen | Mobile Ad Hoc Network (MANET) Neighborhood Discovery Protocol (NHDP)[END_REF] (br oad cas t)

......

RR EQ _B UI LD [5 ] (b ro ad ca st) (discarded by root)

RR EP [START_REF] Clausen | The Optimized Link State Routing Protocol version 2[END_REF] (u nic as t)

X NET_TRAVERSAL_TIME Collection tree triggering

Bi-directional neighbour discovery

Collection tree building Root-to-sensor path building (optional)

sensor B

RR EQ _T RI G G ER [START_REF] Clausen | The lln on-demand ad hoc distance-vector routing protocol -next generation[END_REF] (b ro ad ca st )

HE LLO [START_REF] Perkins | Ad hoc On-Demand Distance Vector (AODV) Routing[END_REF] (br oad cas t)

HE LL O [4 ] (b ro ad ca st)

RR EQ _B UIL D [START_REF] Clausen | Mobile Ad Hoc Network (MANET) Neighborhood Discovery Protocol (NHDP)[END_REF] (br oad cas t)

RR EP [START_REF] Kim | 6LoWPAN Ad Hoc On-Demand Distance Vector Routing[END_REF] (u nic as t)

RR EP [START_REF] Kim | 6LoWPAN Ad Hoc On-Demand Distance Vector Routing[END_REF] (u nic as t)

E. Collection Tree Maintenance

Based on the operation introduced in section II-D, 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:

• Lost of control message during the collection tree building process; • Routing entries expire because of not updated timely;

• Participation of new sensors;

• Sensors quite 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:

• The data packet to be forwarded can not find a routing tuple to the desired destination in the routing table, OR • the link to the "next hop" indicated by the routing table is detected broken. To avoid that 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, the link between S-D is detected broken. Router A and B have already direct path to D, and C has also a routing tuple to D (by going through S). Figure 3a 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 router A, B, 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.

With smart route request, as shown in figure 3b, router A, B, 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.

III. LOADNG-CTP PROTOCOL ANALYSES

This section analyses the main features of the LOADng-CTP, including protocol complexity, security considerations,

A. Protocol Complexity

Unlike link-state routing protocols such as OSPF [START_REF] Moy | OSPF Version 2[END_REF] or OLSR [START_REF] Clausen | The Optimized Link State Routing Protocol version 2[END_REF], which require keeping a network topology locally and run the Dijkstra algorithm, LOADng and LOADng-CTP concerns only the basic additive operation when calculating link metrics. Therefore, the computational complexity is negligible. An 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.

The number of nodes at height h(0 ≤ h ≤ H -1) is n h = C h . The total number of nodes in the tree is

N = 1 + C + C 2 + ... + C (H-1) = 1 -C H 1 -C , (C > 1) (1)
In LOADng-CTP, the message required for collection tree building is the sum of RREQ TRIGGER, HELLO and RREQ BUILD: If root-to-sensor paths are required, every sensor also has to unicast an RREP message to the root.

RREQ = 3N (
The number of RREP messages forwarded by all the routers at height h is

RREP h = C h H-h-1 i=0 C i = C h 1 -C H-h 1 -C (3)
The total number of RREP can thus be given by

RREP All = H-1 h=1 RREP h = H-1 h=1 C h 1 -C - H-1 h=1 C H 1 -C (4)
Considering equation 1, the total number of RREP forwarding is

RREP All = 1 1 -C C -C H 1 -C - (H -1)C H 1 -C = N H -N + N -H 1 -C (5)
Considering H = log C N , the total number of RREP messages thus scales with O(N logN ).

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

RREQ = N 2 (6)
The RREP message is always needed in LOADng basic operation, which is the same with equation [START_REF] Clausen | Mobile Ad Hoc Network (MANET) Neighborhood Discovery Protocol (NHDP)[END_REF].

Based on equation ( 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 sensorto-root paths are needed, or O(N logN ), if root-to-sensor paths are also required.

B. 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 bi-direction 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 mis-configured 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 bi-directional neighbours correctlythus is not able to join the collection tree as expected.

In addition to message mis-ordering, LOADng-CTP is also prone to attacks like block-hole or spoofing attacks [START_REF] Wang | On vulnerability and protection of ad hoc on-demand distance vector protocol[END_REF], [START_REF] Ning | How to misuse AODV: a case study of insider attacks against mobile ad-hoc routing protocols[END_REF]. 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, e.g., because physical access is limited or lower layer protection is sufficient. Other networks require integrity protection with a lightweight cipher suite due to limited precessing power and memory of routers. In some cases, security requirements are tighter and confidentiality as well as strong cryptographic ciphers are required.

The IETF has standardized a security framework for protocols using the message and packet format defined in [START_REF] Clausen | Generalized Mobile Ad Hoc Network (MANET) Packet/Message Format[END_REF] 4 , which is used by LOADng-CTP. [START_REF] Herberg | Integrity Check Value and Timestamp TLV Definitions for Mobile Ad Hoc Networks (MANETs)[END_REF] specifies a syntactical representation of security-related information in TLVs for use with [START_REF] Clausen | Generalized Mobile Ad Hoc Network (MANET) Packet/Message Format[END_REF] 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 non-repudiation for LOADng, using the framework specified in [START_REF] Herberg | Integrity Check Value and Timestamp TLV Definitions for Mobile Ad Hoc Networks (MANETs)[END_REF].

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, [START_REF] Herberg | Integrity Check Value and Timestamp TLV Definitions for Mobile Ad Hoc Networks (MANETs)[END_REF] 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, i.e., 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".

C. Interoperability Considerations

As sensor networks and low power and lossy networks are generally decentralized system, devices would possibly work in a heterogeneous environment: there are 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 LOADngcore 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 bi-directional 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 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. 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 S probably provides a shorter path to the root. If the LOADngcore 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 II-E, the RREQ dissemination can be kept locally, thus without introducing much influence in the networks.

IV. SIMULATION AND PERFORMANCE ANALYSES

A. 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 is set according to [START_REF] Winter | RPL: IPv6 Routing Protocol for Low power and Lossy Networks[END_REF]. 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, i.e.,, the simulation field grows as the number of routers increases: 1100m×1100m for 63 nodes, 1580m×1580m for 125 nodes, 2230m×2230m for 250 nodes, 3160m×3160m 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 100s.

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), etc. Therefore, general behaviour of a protocol can be inferred from simulations using 802.11.

In the simulations, three types of routing protocols are compared:

• LOADng core specification [START_REF] Clausen | The lln on-demand ad hoc distance-vector routing protocol -next generation[END_REF], referred as LOADng in the following of the section. The routes are build reactively when there are data packets need to be send. • LOADng with collection tree extension, referred as LOADng-CTP. The collection tree is triggered and build before the sending of data packets. • RPL with trickle timer, referred as RPL. The parameters of trickle timer is set according to [START_REF] Winter | RPL: IPv6 Routing Protocol for Low power and Lossy Networks[END_REF].

B. 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 9 illustrates the average end-to-end delay. LOADng has longer delay mainly because the route discovery is performed reactively, i.e.,the data packets have to wait the finish of route discovery before being send out. LOADng-CTP and RPL have routes a-priori available, thus exhibit identical delays.

For the sensor networks, the routing overhead is also a crucial consideration. Figure 10 and Figure 11 shows 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, i.e.,, every router has a route to the root.

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 [START_REF] Clausen | Experiences with RPL: IPv6 Routing Protocol for Low power and Lossy Networks[END_REF]: a DIO packet 5 takes up to 40 octets in these scenarios, whereas a LOADng-CTP RREQ and RREP packet typically is 10 octets. The overhead of LOADng grows exponentially as the number of nodes increases, up to 5 Base header of 24 octets, plus other options and addresses. V. CONCLUSION This paper has presented a simple 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 bi-directional 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 be 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.

Figure 1 :

 1 Figure 1: LOADng-CTP RREQ BUILD message processing

  ad ca st ) RR EQ _T RI GG ER[START_REF] Clausen | The lln on-demand ad hoc distance-vector routing protocol -next generation[END_REF] (b ro ad ca st)HE LL O [2 ](b ro ad ca st)

Figure 2 :

 2 Figure 2: Message exchange of LOADng-CTP between root and sensors

  Route discovery with smart route request

Figure 3 :

 3 Figure 3: An example of route maintenance. Router D is the root. The link between S-D is detected broken. Sensor router A, B, C still have routing tuple to D.

2 )Figure 4 :

 24 Figure 4: An example of balanced tree. Every parent has 2 children (C = 2)

Figure 5 :

 5 Figure 5: Relationship with RFC5444, RFC6622 and LOADng-CTP

Figure 6 :

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

Figure 8 :

 8 Figure 7: Packet delivery ratio

Figure 9 :

 9 Figure 9: Average end-to-end delay

Figure 10 :Figure 11 :

 1011 Figure 10: Number of overhead packets transmitted by each router

http://www.ietf.org

http://tools.ietf.org/wg/manet/minutes?item=minutes81.html

i.e., IPv6, IPv4, 6LowPAN short addresses, Layer-2 MAC addresses etc. are all supported by LOADng

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

ACKNOWLEDGEMENTS

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


Ulrich Herberg
email: ulrich@herberg.name

Thomas Clausen
email: thomas@thomasclausen.org

Study of Multipoint-to-Point and Broadcast Tra c Performance in the "IPv6 Routing Protocol for Low Power and Lossy Networks"

Recent trends in Wireless Sensor Networks (WSNs) have suggested converging to such being IPv6-based. To this e↵ect, the Internet Engineering Task Force has chartered a Working Group to develop a routing protocol specification, enabling IPv6-based multi-hop Wireless Sensor Networks. This routing protocol, denoted "IPv6 Routing Protocol for Low Power and Lossy Networks" (RPL), has been under development for approximately a year, and this paper takes a critical look at the state of advancement hereof: it provides a brief algorithmic description of the protocol, and discusses areas where -in the authors view -further e↵orts are required in order for the protocol to become a viable candidate for general use in WSNs. Among these areas is the lack of a proper broadcast mechanism. This paper suggests several such broadcast mechanisms, all aiming at (i) exploiting the existing routing state of RPL, while (ii) requiring no additional state maintenance, and studies the performance of RPL and of these suggested mechanisms.

Introduction

The general context for routing in Wireless Sensor Networks (WSNs) is small, cheap devices whose primary function is data acquisition, and for which communications capabilities are a "commodity to their primary function" -a necessary, but in preference unobtrusive, functionality, specifically targeted to the precise goal which the WSN is deployed to satisfy. As an example, a WSN deployed for environmental monitoring might contain a set of temperature sensors, sending "notifications" to a central controller when the temperature exceeds certain thresholds -and occasional "keepalive" messages otherwise, to let the controller know that the sensors are still operational. Tra c from the controller to the individual sensors may be limited to "setting the thresholds" -possibly rarely, such as at system deployment, or even never such as would be the case with factory set thresholds.

WSN Tra c Flows

The communications requirements for WSNs are in contrast to "traditional networks", wherein communications devices (network interfaces, switches, routers) have carrying data tra c as their sole raison d'être, and in which devices do not make any a-priori assumptions such as the characteristics of the tra c they will be carrying. WSNs assume an a-priori knowledge of the tra c patterns to optimize for -with sensor-to-controller tra c (multipoint-to-point) being predominant, controller-to-sensor tra c (point-to-multipoint) being rare and sensor-to-sensor tra c being somewhat esoteric 1 .

WSN Trade-o↵ 's

Low-power consumption, minute physical sizes, low price-points and ruggedness against the environment are among the industrial or commercial keywords, often associated with wireless sensors -and which entail challenging constraints (in terms of the computational power, permanent and temporary storage and in the characteristics (capacity) of the wireless interfaces) for designing routing algorithms. WSN routing protocols are therefore inherently compromises: trade-o↵s are made in adapting to the specific constraints under which they are to operate -the first of these is usually "generality". WSN routing protocols generally and narrowly consider only the tra c characteristics of their target environment as "valid", and discard all other tra c characteristics in the name of satisfying operational constraints; two of the most common such constraints brought forward are strict bounds on in-router state and on control tra c. A second trade-o↵ is often in route optimality: stretched (non-optimal) routing paths are an acceptable trade-o↵ for lower control tra c from a routing protocol, with the hypothesis that tra c flows will be such that the impact of such stretched paths will be negligible.

The perceived optimal routing protocol might thus be described as a routing protocol which requires zero in-router state and zero control tra c overhead, while providing non-stretched routing paths. Such a protocol is possible, although may not be desirable. Consider the example in figure 1(a). The network connectivity is as indicated by the dotted lines, with the source and destination indicated by Source (router C) and Destination (router I), respectively. A "perceived optimal routing protocol" would be, as illustrated in figure 1(b), simply flooding data tra c. Such entails no control tra c overhead and no in-router state, and a packet from C will arrive at I via a path of length 2 (i.e. a routing path stretch of 1). Data transmission between C and I via a path such as the one indicated in figure 1(c) appears intuitively better. While the routing path stretch is 3 (6 hops), at least routers D and E do not retransmit. An even worse situation is possible, as illustrated in figure 1(d): all routers still retransmitting and receiving as many copies of a packet as in flooding -but with a routing path stretch of 4.

1 Note that while this may be commonly assumed, this is not a universal distribution of tra c patterns in WSNsthere are scenarios in which sensor-router to sensor-router tra c is assumed a more common occurrence, such as [START_REF] Martocci | Building Automation Routing Requirements in Low-Power and Lossy Networks[END_REF].

A flooding operation, as in figure 1(b), would in this case entail 8 transmissions (i.e. (n 1) transmissions, with n being the number of routers in the network) -just as "bad"2 for battery consumption and media occupation as if the path length had been of 8, as in figure 1(d). On the other hand, the routing path in figure 1(d) did not appear "by magic": a (more or less optimal) routing protocol has provided this path, and in order to do so generated a certain amount of control tra c.

As a measure of success, "routing path stretch" is an inappropriate metric, when used alone. In deployments with heavy unicast tra c, it might be reasonable to trade o↵ more state and more control tra c in order to obtain shorter paths, whereas in scenarios where such unicast tra c is light, a longer path may be a reasonable trade-o↵ in order to reduce state and control tra c. If in a network unicast tra c is both light and rare, simple flooding, and so trading o↵ "route stretching" (or, more appropriately, "total number of transmissions on the wireless medium in order to successfully deliver the data packet at the destination") and state for simpler logic in the router and no control tra c, might be reasonable, as might flooding be reasonable if the majority of tra c is (very light) broadcast.

Paper Outline

The remainder of this paper is organized as follows: section 2 provides an overview of the activities of the Internet Engineering Task force (IETF) "Routing over Low Power and Lossy Networks" (ROLL) Working Group, chartered to develop routing protocols for IPv6-based sensor networks, as well as provides a description and critical discussion of the "IPv6 Routing Protocol for Low Power and Lossy Networks" (RPL) routing protocol, developed within that Working Group. RPL provides relatively well defined and well understood support for multipoint-to-point tra c -and is currently developing mechanisms for supporting point-to-multipoint tra c as well. Section 3 suggests a couple of di↵erent mechanisms for providing also support for broadcast tra c in a WSN, by way of using the data structures and topologies already maintained by RPL. Section 4 provides a performance study of the multipoint-to-point performance of RPL, as well as a comparative study of the suggested broadcast mechanisms. Section 5 concludes this paper.

State of the art: ROLL and RPL

ROLL is the abbreviation of an IETF Working Group named "Routing Over Low power and Lossy networks". This Working Group has as objective to develop a routing protocol for WSN-like networks, based on IP.

The uno cial goal, which this Working Group tries to attain, is to prevent fragmentation in the WSN market by providing an IP-based routing standard and solicit broad industrial support behind that standard. To this end, the Working Group is operating with a very tight schedule and an objective of completing the standardization e↵ort in fall 2010, satisfying only whatever requirements have been expressed within that time-frame.

The current proposal by the ROLL Working Group is denoted "Routing Protocol for Low Power and Lossy Networks" (RPL), a draft version hereof exists [START_REF] Winter | RPL: IPv6 Routing Protocol for Low power and Lossy Networks[END_REF]. The objective of this protocol is to target networks which "comprise up to thousands of routers", where the majority of the routers have very constrained resources, where the network to a large degree is "managed" by a (single or few) central "superrouters", and where handling mobility is not an explicit design criteria. Supported tra c patterns include multipoint-to-point, point-to-multipoint and point-to-point tra c. The emphasis among these tra c patterns is to optimize for multipoint-to-point tra c, to reasonably support point-to-multipoint tra c and to provide basic features for point-to-point tra c, in that order.

The basic construct in RPL is the DODAG -a "Destination Oriented Directed Acyclic Graph", rooted in a "controller", in figure 2. In the converged state, each WSN router has identified a stable set of parents, on a path towards the "root" of the DODAG, as well as a preferred parent. Each router, which is part of a DODAG (i.e. has selected parents) will emit DODAG Information Object (DIO) messages, using link-local multicasting, indicating its respective Rank in the DODAG (i.e. their position -distance according to some metric(s), in the simplest form hop-count -with respect to the root). Upon having received a (number of such) DIO messages, a router will calculate its own rank such that it is greater than the rank of each of its parents, and will itself start emitting DIO messages. Thus, the DODAG formation starts at the root, and spreads gradually to cover the whole network. As a Distance Vector protocol, RPL [START_REF] Winter | RPL: IPv6 Routing Protocol for Low power and Lossy Networks[END_REF] contains rules restricting the ability for a router to change its rank. Specifically, a router is allowed to assume a smaller rank than previously advertised (i.e. to logically move closer to the root) if it discovers a parent advertising a lower rank (and it must then disregard all previous parents with higher ranks), while the ability for a router to assume a greater rank (i.e. to logically move farther from the root) in case all its former parents disappear, is restricted to avoid count-to-infinity problems. The root can trigger "global recalculation" of the DODAG by way of increasing a sequence number in the DIO messages.

RPL Data Tra c Flows

The DODAG so constructed is used for installing routes in the WSN routers: the "preferred parent" can serve as a default route towards the root, or the root can embed in its DIO messages the destination prefixes, also included by DIOs generated by WSN routers through the WSN, to which it can provide connectivity. Thus, RPL provides "upward routes" or "multipoint-to-point routes" from the sensors towards the controller.

"Downward routes" are installed by having the sensors issue Destination Advertisement Object (DAO) messages upwards in the DODAG towards the controller, describing which prefixes belong to, and can be reached via, that WSN router. Two distinct "modes of operation" for the downward mechanism are specified in RPL:

(i) In storing mode, each router is assumed to maintain routes to all WSN routers in its sub-DODAG, i.e. routers that are "deeper down" in the DODAG. DAOs propagate from the routers towards the controller, where each intermediate router adds its reverse routing stack to the DAO message (aggregating routes where possible).

(ii) In non-storing mode, only the controller stores routes to all WSN routers in the network. Each WSN router unicasts DAOs to the controller, which then calculates routes to all destinations by "piecing together" the information collected from DAO messages (which contain the destination prefix of the WSN router and addresses of the parents through which it is reachable). In non-storing mode, downward tra c is sent by way of source routing.

Sensor-to-sensor routes are as default supported by having the source sensor transmit via its default route to the root, which will add a source-route to the received data for reaching the destination sensor.

RPL Operational Requirements

The minimal set of in-router state, required in a WSN router running RPL is, (i) the identifier of the DODAG root, (ii) the address and rank of the preferred parent, (iii) the configuration parameters shared by the DODAG root (notably, destination prefixes and message emission timers) and (iv) the maximum rank that the WSN router has itself advertised. For redundancy, a WSN router running RPL can maintain information describing additional parents (up to and including all its parents), which may allow rapidly changing its preferred parent (and thus its "next hop") in case the former preferred parent becomes unreachable.

RPL message generation is timer-based, with the root able to configure suitable back-o↵ of message emission intervals using trickle timers [START_REF] Lewis | Trickle: A Self-Regulating Algorithm for Code Propagation and Maintenance in Wireless Sensor Networks[END_REF].

RPL Discussion

In its basic form, RPL is a fairly simple-to-understand and simple-to-implement distance-vector protocol. The DODAG formation mechanism, using DIO messages, is currently well understood, and despite the specification hereof in [START_REF] Winter | RPL: IPv6 Routing Protocol for Low power and Lossy Networks[END_REF] remaining somewhat ambiguous, the authors of this paper managed to develop and test an implementation "from scratch" within about a week.

The DODAG formation mechanism is not without potential issues, however. First, parents (and the preferred parent) are selected based on receipt of DIO messages, without verification of the ability for a WSN router to successfully communicate with the parent -i.e. without any bidirectionality check of links. In a wireless environment, unidirectional links are no rare occurrence, and can simply happen as illustrated in figure 3: the gray device, X, illustrates a source of environmental interference, preventing route b from successfully receive transmissions from a. This may, however, not prevent b from transmitting DIOs, received by a and which may contain information causing a to select b as both parent and preferred parent.

As b is a "useless" next-hop for a, due to the interference from X, this is a bad choice. RPL suggests using Neighbor Unreachability Detection (NUD) [START_REF] Narten | Neighbor Discovery for IP version 6 (IPv6)[END_REF] to detect and recover from this situation, when it occurs that a tries (and fails) to actually use b for forwarding tra c. NUD is based upon observing if a data packet is making forward progress towards the destination, either by way of indicators from upper-layer protocols (such as TCP), from lower-layer protocols (such as Link Layer ACKs) or -failing these two -by unicast probing. A couple of problems can be noted regarding this approach. First, absent all WSN routers consistently advertising their reachability through DAO messages, a protocol requiring bi-directional flows between the communicating devices, such as TCP, will be unable to operate. Even if such bi-directional flows are enabled, the source detecting, by way of an upper layer protocol, that no forward progress is possible, is of restricted use: the source can not know if it is its "preferred parent" (next hop) which is unreachable, or if it is a problem further along the path (even outside the WSN). Thus, any corrective action that the source might take (changing preferred parent, moving to a higher rank within the limits allowed, etc.) may be unable to alleviate the problem, and corrective actions may even be counter-productive (poison the sub-DODAG, for example).

Second, there is a change that the radio range of a unicast (as would be used for data delivery via the next hop towards the root) would di↵er from the radio range of DIOs, which are sent using link-local multicast 3 .

Third, upon having been notified by NUD that the "next hop" is unreachable, a WSN router must discard the preferred parent and select another preferred parent -hoping that this time, the preferred parent is actually reachable. Also, if NUD indicates "no forward progress" based on an upper-layer protocol, there is no guarantee that the problem stems from the preferred parent being unreachable. Indeed, it may be a problem father ahead, possibly outside the WSN, thus changing preferred parent will do nothing to alleviate the situation.

Fourth, the selection of parents and preferred parent is based on receipt of DIO messages only, and is based on the rank of the candidate parents. Absent other complementary mechanisms (which are currently not specified as part of [START_REF] Winter | RPL: IPv6 Routing Protocol for Low power and Lossy Networks[END_REF]), a WSN router may receive, transiently (e.g. due to a fortunate environmental reflection), a DIO from another router, much closer to the root -and as a consequence change its parent set and rank to this new more attractive parent. If no stable link exist, this may cause delivery failures.

The Destination Advertisement mechanism, for providing downward routes "from the root to the sensors", remains in a state of flux. While the basic properties of the Destination Advertisement mechanism, given a stable underlying DODAG, appear easy to understand, it does have several inconveniences: all sensor-to-sensor routes transit the root, possibly causing congestion in the wireless spectrum near the root, as well as draining energy from the intermediate routers on an unnecessarily long path. Several solutions are proposed to alleviate this, including allowing intermediate WSN routers, otherwise only forwarding DAO messages towards the root, to record routing state, and allowing these intermediate WSN routers to act as "shortcuts". Another proposed solution is to use proper sensor-to-sensor routing protocols, derived o↵ e.g. AODV [START_REF] Perkins | Ad hoc On-Demand Distance Vector (AODV) Routing[END_REF].

Finally, the current specification of RPL does not provide support for "broadcasting" of any form. Unicast tra c to and from the root can be enabled, as previously described, however is ine cient in case the root has data to deliver to all (or a su ciently large subset) of the WSN routers in the network.

Data Broadcasting in RPL

This section suggests mechanisms for exploiting the DODAG as constructed by RPL in order to undertake better-than-classic-flooding WSN-wide broadcasting. The fundamental hypothesis for these mechanisms is that all broadcast operations are launched from the root of the DODAG. If a sensor needs to undertake a network-wide broadcast, the assumption is that this broadcast is sent to the root using unicast, from where the DODAG root will launch the broadcast operation -this is similar to the basic mechanism for sensor-to-sensor unicast in [START_REF] Winter | RPL: IPv6 Routing Protocol for Low power and Lossy Networks[END_REF], wherein tra c from the source sensor transits to the DODAG root, for relaying to the destination sensor.

Classic Flooding (CF)

A common baseline for broadcast operations is that of classic flooding: each router relays a broadcast packet upon its first receipt by that router; subsequent receipts of the same packet are suppressed and do not cause retransmissions. This has to its merit that no control tra c is required -however also entails (i) that each data packet must be uniquely identifiable (commonly ensured by embedding a unique sequence number in each broadcast packet, emitted by a given source), (ii) that each router must maintain information (state) for each already received and relayed data packet so as to enable suppression of duplicates, and (iii) each data packet is retransmitted by each router in the network -often with a large degree of redundant transmissions as consequence.

Redundant retransmissions cause increased battery drain, both when transmitting and receiving (and discarding) the redundant packets, and increase contention on the wireless media, increasing the probability of data loss due to collisions. CF is, for these reasons, not suggested as a mechanism for data broadcast in WSNs, but is described here as a baseline for data broadcasting in RPL.

MultiPoint Relay Flooding (MPRF)

A common improvement over Classic Flooding is for each router to select and designate a subset of its neighbors (MultiPoint Relays -MPRs [START_REF] Qayyum | Multipoint relaying: An e cient technique for flooding in mobile wireless networks[END_REF]) for relaying broadcast transmissions, thereby reducing the number of redundant retransmissions of each packet. This has been shown to o↵er dramatic reductions in the network load (fewer transmissions), as well as a dramatic reduction in data loss due to collisions [START_REF] Clausen | Investigating Broadcast Performance in Mobile Ad-hoc Networks[END_REF].

In order for MPRF to work, a router must select its MPRs such that a message relayed by these MPRs will be received by all routers two hops away, as illustrated in figure 4. To this end, each router must maintain, at a minimum, state describing both its neighbor routers, as well as its 2-hop neighbors ("neighbor routers of neighbors"). MPRF -as CF -requires identification of each broadcast packet, and maintenance of state allowing elimination of duplicate packets.

MPRF is a common approach in wireless ad hoc networks, where it is used e.g. for networkwide broadcast of routing protocol control tra c by [START_REF] Clausen | Optimized Link State Routing Protocol (OLSR)[END_REF], [START_REF] Clausen | SPF Multipoint Relay (MPR) Extension for Ad Hoc Networks[END_REF] and [START_REF] Clausen | The Optimized Link State Routing Protocol version 2 (OLSRv2)[END_REF] -as well as for network-wide data broadcast [START_REF] Macker | Simplified Multicast Forwarding[END_REF]. Comparing RPL-specific broadcast mechanisms with MPRF is therefore, to a certain extend, a comparison with "state of the art" of broadcasting in wireless multi-hop networks.

Parent Flooding (PF)

Admitting the RPL "philosophy" of data transmission to sensors originating at (or relaying via) "the DODAG root", RPL lends itself to a first and simple broadcast optimization: restricting a RPL router to retransmit only broadcast packets received from a "parent". Logically, the basic performance hereof should be similar to that of classic flooding: with the broadcast operation initiated from the DODAG root, each router will retransmit the packet upon receipt from a parent. PF does not require any additional control tra c over that which is caused by RPL. PF may apply identification of each broadcast packet, and maintenance of state allowing elimination of duplicate packets in order to avoid multiple retransmissions of the same packet received from di↵erent parents -similar to MPRF and CF.

Preferred Parent Flooding (PPF)

In order to not incur any additional in-router state requirements for detecting and suppressing retransmission of duplicate packets, preferred parent flooding utilizes the existing relationship between RPL routers, in order to ensure that no router will forward a broadcast packet more than once. Each RPL router is required to select exactly one Preferred Parent. Restricting retransmissions of broadcast packets to only those received from the router's preferred parent ensures that duplicates received from other routers (parents or otherwise) are ignored for retransmission.

Preferred Parent MPR Flooding (PPMPRF)

PPF is fundamentally a derivative of the MPRF optimization, attempting further to decrease the number of retransmissions necessary for a network wide broadcast. The idea is as follows: each router, selected as "Preferred Parent", must designate a subset of its "selectees" (children which have selected it as preferred parent) as "Preferred Children". These "Preferred Children" must be selected such that a message, relayed by these "Preferred Children", will reach all its "grand children" -i.e. the children of its "selectees". Whenever a router receives a data packet that is to be broadcast throughout the network, that router will only then forward the packet if (i) at least one parent of that router has selected it as preferred child and (ii) the packet has not been previously received (as determined by a duplicated detection mechanism). It is to be noted that it is not su cient to restrict forwarding to packets received from the preferred parent of a router, but that packets from any parent of that router have to be forwarded if the router has been selected as preferred child by at least one of its parents. The rationale is illustrated in figure 5. Assuming that the root of the network (router 0) has selected B as preferred child as indicated by the downward arrow, and B forwards a packet originating from the root. If forwarding was restricted to packets received from the preferred parent of a router, D would not forward the packet from B (since it is no preferred parent of D), and thus X would never receive the packet. Compared to "classic" MPR selection, the "Preferred Children selection" (i) concerns only coverage of "grand children" (i.e. "downward" in the DODAG as constructed by RPL) and (ii) is restricted by the preferred parent selection from RPL.

This restriction entails less liberties with respect to selecting relays for "best 2-hop coverage". It is quite possible that the child providing the "best" coverage of a router has not selected that router as Preferred Parent, and that therefore PPMPRF will result in more relays than MPRF. In RPL, the Preferred Parent selection is intended to optimize for "best upwards paths towards the DODAG root" (possibly according to some deployment specific optimization criteria), which may not coincide with what would be optimal for "best downwards coverage".

The PPMPRF mechanism also requires that each router knows (i) which children have selected it as Preferred Parent (i.e. its selectees), and (ii) which routers are Preferred Children of these selectees. This information can be made available through adding an option to DIO messages, emitted by all routers running RPL.

Optimized Preferred Parent MPR Flooding (PPMPRF-opt)

This mechanism represents a small optimization over PPMPRF, in that it provides all neighboring routers with the same rank with information, encouraging coordinated Preferred Parent selection so as to try to reduce the number of routers selected as Preferred Parent. Thus, a router will select as its Preferred Parent among its parents, the one which most of its adjacent routers also have in their parent set. Given a tie, the parent which a majority of the adjacent routers have already selected as Preferred Parent will be chosen. Thus, in addition to the information indicated for PPMPRF, PPMPRF-opt requires all parents to be advertised. Similarly, I, H, and G may select three di↵erent Preferred Parents. For PPMPRF, this means that all routers, other than 0, will be selected as MPRs and thus retransmit a broadcast.

Figure 6(b) depicts a coordinated Preferred Parent selection. Router D will advertise all its parents (C and B) in its control messages, as will E (parents C, B and A) and F (parents B and A). D has an equal choice between parents C and B, and F has the same choice between B and A. E will select B as Preferred Parent because this is the only parent that both of its adjacent routers can also select as Preferred Parent. Once D and F receive a control message from E, advertising that B is selected as Preferred Parent, they will also select B. Thus, only routers B, E and H will be selected as Preferred Parents and therefore retransmit a broadcast.

Such coordinated Preferred Parent selection may be a double-edged sword for RPL. While it is a potential benefit for broadcast tra c from the DODAG root, unicast tra c flows towards the DODAG root via Preferred Parents. Thus, coordinated selection of Preferred Parents implies that unicast tra c is concentrated through a subset of the routers in the network, possibly increasing congestion in these routers, increasing the battery drain in these routers etc.

RPL Performance Study

This section presents results of a simulation study of RPL with the Ns2 simulator. Several properties of the DIO mechanism, as well as unicast and broadcast data tra c have been analyzed.

Simulation Settings

RPL has been implemented in Java. The specific settings of the scenarios studied are detailed in table 1. For each datapoint, the values have been averaged over 10 runs.

DIO settings

The implementation reflects a basic version of the RPL protocol: only upward routes, and a single RPL instance with a single DODAG are considered. Since routers are not mobile in the simulation, the sequence number (and thus the DODAG iteration) will not change during the simulation. At the beginning of the simulation, only the root (which is the router with the ID of 0) starts transmitting DIOs. routers other than the root receiving a DIO start sending DIOs exactly two seconds after no more change in their Candidate Neighbor Set has been detected. Each DIO contains the DODAG Configuration message option. The simulations have been performed in two variations:

• with periodic DIO transmission: DIOs are sent periodically with an interval of two seconds minus a jitter of maximum 0.5 s (as defined in [START_REF] Clausen | Jitter Considerations in Mobile Ad Hoc Networks (MANETs)[END_REF])

• with a trickle timer: I_min is 2 s and DIOIntervalDoublings is 20. During the simulation, the trickle timer is never reset.

Results

This section describes the results of the Ns2 simulation. Figure 7 shows a RPL instance of a simulated network with 1000 routers. In this depicted setting, and in all simulated scenarios in the following, routers are not mobile and randomly distributed in the square simulation area. Figure 8 shows the maximum and average rank of routers in the DODAG, where the number represents the distance of a router to the root in terms of hops (i.e. the maximum rank represents the Figure 7: Example RPL instance with 1000 routers diameter of the network, the average rank represents the average over all routers). The maximum and average ranks grow logarithmically with the number of routers in the network.

Figure 9 depicts the average number of parents of each router in the DODAG. Keeping the density of the network constant with increasing number of routers, the average number of parents grows logarithmically.

Figure 10 displays the convergence time of the network, i.e. the time that is needed for all routers that are in the same connected component as the root to join the DODAG. Since each router starts sending DIOs two seconds after the last change to its Candidate Neighbor Set, the convergence time is roughly two seconds times the maximum rank of the DODAG. The convergence time grows logarithmically with the number of routers in the network.

Figure 11 depicts the total control tra c in the network in bytes. The RPL implementation with the trickle timer has significantly less overhead than the periodic timer. The control tra c grows linearly with the number of routers in the network.

Figure 12 depicts the collision ratio of the DIO messages. Since the RPL implementation using the trickle timer sends significantly fewer DIO messages, the probability of collision is lower.

Unicast Data tra c

In the following, unicast CBR (Constant Bit Rate) data streams of 1280 bytes/s have been sent from an arbitrary router to the root, in average five concurrent streams of 10s duration each.

Figure 13 depicts the delivery ratio of packets that have arrived at the root. It can be seen that it is constantly very high, only few packets are lost due to collisions on lower layers. Figure 14 illustrates the average path length in number of hops that a data tra c traverses before reaching the root. As expected, it grows logarithmically with the number of routers, and is very similar to the average rank as depicted in figure 8.

Figure 14: Unicast: path length Figure 15 shows the delay of the data transmission, i.e. the time interval from sending the packet at the source until it reaches the destination. Due to the longer path length, the delay increases with the number of routers in the network.

Broadcast Data tra c

In the following, the broadcast mechanisms presented in section 3 are analyzed in terms of MAC layer collisions, delivery ratio, overhead, delay, and path length. CF and PF (without duplicate detection) are not considered since their performance is expectedly much worse than any of the other mechanisms.

Figure 16 depicts the number of collisions of frames on the MAC layer, for the di↵erent broadcast mechanisms. MPRF and PPMPRF-opt yield the lowest number of collisions among the analyzed protocols, with PPMPRF causing about the same number of collisions as PF+DD (PF with duplicate packet detection). This is expected, as in MPRF, relays are explicitly selected so as to avoid redundant retransmission by topologically close routers, and the coordinated preferred parent selection in PPMPRF-opt also reduces the number of relays. PPMPRF without coordination entails more relays, as more routers in the network will be selected as preferred parents, which in turn select the relays (i.e. preferred children). In PPF, topologically close routers are likely to have chosen the same Preferred Parent and so will explicitly produce redundant retransmissions. Consider the example in figure 17, wherein a broadcast transmission is made by router 0 and relayed as indicated by the solid arrows. In PPF, as indicated in figure 17(a), each router will select its Preferred Parent and retransmit the packet once upon receipt from that preferred parent. Routers Figure 15: Unicast: delay A, B and C all receive the transmission directly from router 0. Routers D, E and F have all chosen one of A, B and C as Preferred Parent and will thus all retransmit when receiving the transmission from their chosen preferred parent -similar for I, H, G, even though these three do not have any routers further down the network. In contrast, in figure 17(b), MPRs have been selected. Router 0 has selected B as MPR (as B "covers" D, E, F) and router B has chosen router E as MPR (as it covers all of G, H, I). As there are no further routers "below" in the network, router E has chosen no MPRs downwards. Thus, only B and E retransmit the broadcast packet from 0 -i.e. for each "level" in this simple network, only a single transmission occurs, with no collisions at each level.

Figure 18 depicts the delivery ratio of broadcast packets. The delivery ratio of the MPRF and PPMPRF mechanisms are the highest of the compared broadcast mechanisms, with PPMPRFopt being not much below MPR. This can be interpreted as a tradeo↵ between redundancy and e ciency: in relatively scarce networks (such as the simulated scenario) a higher redundancy of relays, such as in PPMPRF, can lead to a higher delivery ratio, despite of the increased number of collisions. as observed in figure 16. In dense networks, however, the large number of collisions with more redundant delays can reverse that e↵ect and reduce the delivery ratio. A detailed analysis of the MPR relaying mechanism can be found in [START_REF] Qayyum | Multipoint relaying: An e cient technique for flooding in mobile wireless networks[END_REF].

PF+DD has a higher delivery ratio than PPF, due to the redundancy of transmissions -when a router receives the same broadcast packet from several of its parents, chances are higher that at least one of the packets will reach the router, while if the one transmission from the preferred parent in PPF is lost due to a collision, the router will not forward the other incoming packets from its (non-preferred) parents. The higher delivery ratio of PF+DD is at the expense of vastly higher media load, as depicted in figure 19: the cumulative number of bytes transmitted during the simulations are significantly higher for PF+DD and for PPMPRF without the optimization. PPF incurs a lower overhead than PF+DD with MPRF still outperforming PPF by a large, and constant, margin. PPMPRF-opt has a similar overhead as MPRF. Figure 20 depicts the average end-to-end delay for data tra c from the root to every WSN router in the network, and figure 21 depicts the average path length of successfully delivered data packets. The optimized MPR-based broadcast mechanisms incur the lowest delay of the protocols, while PPF causes a slightly lower delay than does PF+DD. The, on average, longer path lengths of MPRF are due to the data delivery ratio being higher -MPRF successfully "reaches" routers farther away from the root (as depicted in figure 22). It has been shown ( [START_REF] Qayyum | Multipoint relaying: An e cient technique for flooding in mobile wireless networks[END_REF]) that MPR leads to optimal path length. That means that every mechanism indicating a shorter path in the figure entails a lower reachability of routers further away from the broadcast source. Longer paths indicate suboptimal paths. It is worth observing that MPRF achieves the optimal path length with a lower delay still. This can in part be explained by the fact that MPRF ensures that data is flooded via shortest paths, and in part by the fact that with fewer retransmissions, less media and queue contention occurs.

PPF with Jitter

In the results presented in section 4.2.2, data tra c has been promptly forwarded by each WSN router, without explicit delay. As has been shown in [?, 6], adding a random jitter before retransmitting a broadcast packet can significantly reduce the number of collisions and, therefore, increase the delivery ratio for broadcast packets. In the following, the e↵ect of adding jitter to PPF is investigated.

Figure 23 depicts the collision ratio of frames when using no jitter, and a random jitter uniformly distributed between 0 and 500 ms respectively. With jitter, the collision ratio is much lower than it is without. This is due to the fewer concurrent retransmissions by adjacent WSN routers. Comparing to figure 16, PPF with jitter yields a collision ratio comparable to, or lower than, MPRF without jitter.

As a consequence of the lower collision ratio, the delivery ratio of PPF with jitter is higher than it is without, as depicted in figure 24. Comparing to figure 18, the delivery ratio of PPF still remains consistently below that of MPRF, even when PFF is used with jitter. The drawback of using jitter is a higher end-to-end delay of packets, as depicted in figure 25. With jitter, the delay is considerably higher than it is without.

Conclusion

This paper has presented a critical review of the "IPv6 Routing Protocol for Low Power and Lossy Networks" (RPL) -the currently proposed routing protocol for IPv6-based Wireless Sensor Networks (WSNs), as developed within the Internet Engineering Task Force (IETF). A distance vector protocol constructing routing paths from sensors to a central "controller", RPLs basic mechanism is one of "Directed Acyclic Graph" (DAG) formation, with that DAG being the central topology upon which routing is performed. The review reveals areas where, in the authors' opinion, further work is required -in particular with respect to tracking of uni-directional links, to point-to-multipoint routes (controller-to-sensor routes) and data broadcasting in a WSN. Moreover, the performance of "upward" tra c (sensor-to-controller) in an RPL-based sensor network is evaluated using Ns2 simulations, showing that RPL scales well with the size of the network. The control tra c overhead of the protocol is relatively low, and delivery ratio of data tra c is high and stable -even for large networks of several hundred routers.

The paper then presents a comparative study and an Ns2-based performance evaluation of broadcast mechanisms for RPL, utilizing the DAGs already constructed by RPL. These broadcast mechanisms, denoted "Parent Flooding" (PF), "Preferred Parent Flooding" (PPF) and "Preferred Parent MPR Flooding" (PPMPRF) adhere to the "root-oriented" concept of RPL, in that all broadcast operations are to be initiated by the root of the DAG. PF, PPF and PPMPRF are studied and compared by way of network simulations -and as a point of comparison, MPR Flooding (MPRF), is also subjected to the same network scenarios in the simulator.

The results show that the MPR based broadcast mechanisms lead to a much lower bandwidth consumption and a higher delivery ratio than PF and PPF, with the expense of additional control tra c information that is required. If such information is not provided, PPF leads to a better performance than PF. In order to further reduce collisions in the network, using a jitter (i.e. a delay when forwarding a message on a router) is evaluated: the jitter decreases the collisions, and thus increases the delivery ratio, but also increases the end-to-end delay.

Figure 1 :

 1 Figure 1: "Route Stretching" vs "number of transmissions"

Figure 2 :

 2 Figure 2: RPL Basic Construct: DODAGs

Figure 3 :

 3 Figure 3: Unidirectional link due to radio interference

Figure 4 :

 4 Figure 4: (a) Classic flooding and (b) MPR Flooding

Figure 5 :

 5 Figure 5: PPMPRF: Example showing the need to forward packets not only received by the preferred parent, but by any parent if the router is selected as preferred child by at least one of its parents. Upward arrows depict preferred parent selection, downward arrows preferred child selection.

Figure 6 :

 6 Figure 6: Uncoordinated PP selection (a) and coordinated PP selection (b) in the same network. Solid arrows indicate the selection of a Parent as Preferred Parent; dotted lines the connectivity of the network.

Figure 6 (

 6 Figure6(a) depicts an example of Preferred Parent selection, as may happen in basic RPL: a router selects its Preferred Parent amongst all its parents with the lowest rank in an uncoordinated way. Worst case (in terms of redundant transmissions and therefore possible collisions when broadcasting), routers D, E and F all select di↵erent Preferred Parents (C, B, and A respectively). Similarly, I, H, and G may select three di↵erent Preferred Parents. For PPMPRF, this means that all routers, other than 0, will be selected as MPRs and thus retransmit a broadcast.Figure6(b) depicts a coordinated Preferred Parent selection. Router D will advertise all its parents (C and B) in its control messages, as will E (parents C, B and A) and F (parents B and A). D has an equal choice between parents C and B, and F has the same choice between B and A. E will select B as Preferred Parent because this is the only parent that both of its adjacent routers can also select as Preferred Parent. Once D and F receive a control message from E, advertising that B is selected as Preferred Parent, they will also select B. Thus, only routers B, E and H will be selected as Preferred Parents and therefore retransmit a broadcast.Such coordinated Preferred Parent selection may be a double-edged sword for RPL. While it is a potential benefit for broadcast tra c from the DODAG root, unicast tra c flows towards the DODAG root via Preferred Parents. Thus, coordinated selection of Preferred Parents implies that unicast tra c is concentrated through a subset of the routers in the network, possibly increasing congestion in these routers, increasing the battery drain in these routers etc.

Figure 8 :

 8 Figure 8: Maximum and average rank of routers in the DODAG

Figure 9 :Figure 10

 910 Figure 9: Average number of parents per router in a DODAG

Figure 11 :

 11 Figure 11: Control tra c: overhead in bytes

Figure 13 :

 13 Figure 13: Unicast: delivery ratio

  Figure 16: Broadcast: total number of MAC layer collisions

Figure 17 :Figure 19 :

 1719 Figure 17: PPF (a) and MPRF (b) in the same network. Solid arrows indicate transmission of a packet; dotted lines the connectivity of the network.

Figure 20 :

 20 Figure 20: Broadcast: average delay

Figure 22 :Figure 24 :

 2224 Figure 21: Broadcast: average path length

Figure 25 :

 25 Figure 25: Average delay of PPF with jitter

Table 1

 1

		: Ns2 parameters
	Parameter	Value
	Ns2 version	2.34
	Mobility scenarios	No mobility, random distribution of routers
	Grid size	variable
	Router density	50 / km 2
	Communication range	250m
	Radio propagation model Two-ray ground
	Simulation time	100 secs
	Interface type	802.11b
	Frequency	2.4 GHz

Actually, even worse: in order to prevent "looping" packets, state would have to be maintained in each sensor router, ensuring that each such packet would be retransmitted no more than once.

Such is the case for some implementations of IEEE 802.11b. IEEE 802.11b is, of course, not suggested as a viable radio interface for WSNs, but serves to illustrate that such asymmetric designs exist.