# QoI-Aware DODAG Construction in RPL-Based Event Detection Wireless Sensor Networks

Authors: Hongliang Tian; Zhihong Qian; Xue Wang; Xiao Liang
Journal: Journal of Sensors
 (2017)

---

## Abstract

LLNs are gradually attracting people’s attention for the feature of low energy consumption. RPL is specifically designed for LLNs to construct a high energy efficiency network topology. In the noisy environment, the packet loss rate of RPL-based WSN increases during data transmission. The DODAG constructed by RPL-based WSN increases in depth when communication is affected by noise. In this situation the data transmission in the network will consume more energy. In event detection WSNs, the appropriate network topology enables root to use less sensor data to fuse enough information to determine whether or not an event has occurred. In this paper, we will improve RPL in two ways to optimize topology and reduce energy consumption.(1) The neighbor list and the information of DIO sender’s parent of a node are used to construct a better DODAG in the noisy environment. (2) SPRT and the quality of information of the data are used in the event detecting process for saving energy consumption. Simulation results show that, compared with the original RPL, QoI-aware RPL can reduce the energy consumption by collecting the same quality of information with less data transmission.


---

## Body

## 1. Introduction

Low Power and Lossy Networks (LLNs) are composed by nodes with constrained energy, memory, and processing capacity, so the interconnections of nodes in LLNs have the features of high packet loss rate, low data rates, and instability. Wireless Sensor Networks (WSNs) are a kind of LLN in which nodes collect data from sensors and send it to the base stations or sinks. WSNs play an important role in remote data collecting systems because the nodes in WSNs have an advantage of small size, low energy consumption, and easy networking in various fields. As research continues, WSNs are used in many fields, such as environment monitoring system and forest and grassland fire early warning and monitoring system. Recently, the development of Internet of Things makes its application more extensive; the scope of application extended to the location [1] and vehicle networking [2] and other related fields. Currently researches concentrate on energy consumption [3, 4], coverage [5, 6], and related issues. In many cases, the sensor nodes of these WSNs are battery powered. Once the energy of the battery is exhausted, the sensor node will die. Energy of sensor nodes is mostly used for data transmissions [7]. Therefore, improving routing protocol by energy-saving algorithm can increase the energy efficiency and extend the lifetime of the network.Routing Protocol for Low Power and Lossy Networks (RPL) [8] is proposed as an IPv6 routing protocol for LLNs by the ROLL [9] Working Group in the Internet Engineering Task Force (IETF). RPL is designed to adapt to TCP/IP and take into account the trade-off of energy efficiency and networking performance. The process of networking by using RPL is described in detail in Section 2. However, DODAG construction performance significantly degrades if RPL works under wireless interference [10, 11]. This study developed a modified DODAG discovery process that attempts to reduce the impact of packet loss under wireless interference.On the other hand, large amount of data in WSNs brings a huge challenge to the node energy consumption. Usually, because most of the data are forwarded to the root, the nodes consume more energy when they are located near the root [12]. However, the data generated by nodes are similar when they get close. Sometimes we need not to get all of the data which sensor nodes have collected.On the basis of existing works, we proposed a QoI-aware local DODAG discovery and construction method based on RPL. This method aims at reducing the energy consumption of RPL-based event detection wireless sensor networks. Firstly, by analyzing the influence of DIO message loss on DODAG structure in the noisy environment, the appropriate parent node is found and the DODAG discovery process is improved to optimize the network topology. Then the sensor data is fused and transmitted according to the quality of information. On the premise of ensuring enough quality of information, this method reduces the data transmission and therefore reduces the network energy consumption.


## 2. Background

### 2.1. Related Works

Recently, a general principle of quality of information (QoI) has emerged. In this framework, QoI is the measurement of its content. We can use routing protocols to aggregate and/or fusion data and fetch required results in WSNs for saving energy [13, 14].Unlike aggregation-based routing protocols, QoI-aware routing protocols measure the QoI of the message during data aggregation and forwarding. IDSQ and CADR [15–17] are routing protocols which are information-aware for saving energy, minimizing delay and overhead. In these schemes each node selects the neighboring node with the highest predicted gain of information as the next-hop along the path, and at the time when the fused data satisfies a given QoI threshold it is transmitted to the root. However, these schemes ignore other information besides the routing path. Therefore, it is not appropriate for event detection targeted WSNs in a flat plane. IQAR [18] adopts a tree based approach in WSNs but the root of the tree is the fusion center which cost more energy consumption. Event detection in sensor networks [19–22] is on designing energy efficient hypothesis testing models to detect the presence of the event. Most of these schemes do not consider routing and are based on a star network topology.


### 2.2. Overview of DODAG Construction in RPL

RPL is a distance vector routing protocol that builds a DODAG in addition to a set of features to bound the control traffic, support local (and slow) repair, and so on. The RPL architecture provides a flexible method by which each node performs DODAG discovery, construction, and maintenance. RPL provides a series of new ICMPv6 control messages for exchanging the information of DODAG to form network topology. In RPL, a node may use DODAG Information Solicitation (DIS) message to probe its neighborhood for nearby DODAGs. The DODAG Information Object (DIO) carries information that allows a node to discover a RPL Instance, learn its configuration parameters, select a DODAG parent set, and maintain the DODAG. The Destination Advertisement Object (DAO) message is used to propagate reverse route information to record the nodes visited along the upward path. A node’s Rank defines the node’s individual position relative to other nodes with respect to a DODAG root. Rank strictly increases in the down direction and strictly decreases in the up direction. The exact way Rank is computed depending on the DAG’s Objective Function (OF). The Rank may analogously track a simple topological distance, may be calculated as a function of link metrics, and may consider other properties such as constraints.The process of the DODAG construction begins from the DODAG root. First, the DODAG root broadcasts the DODAG information by transmitting a DIO message. Neighbors of the root receive and process the DIO message. The DIO message is processed and transmitted to other nodes one by one. A node which has not joined any DODAGs calculates the cost of the path to the DIO sender and then decides whether to join the DODAG or not. Once a neighbor joins the DODAG, it has a route towards the DODAG root, and the root becomes a DODAG parent of the node. Next, the node calculates its Rank in the DODAG and replies with a DAO message to its parent to inform its participation. A node which has not received any DIO messages and has not joined any DODAGs can request DODAG information by sending DIS messages periodically to its neighbors. All of the neighbors repeat this process until all of the nodes join the DODAG. Figure1 depicts a simplified flowchart of the DODAG construction process. The DODAG root sends a DIO message with DODAG information; nodeA receives the DIO message and joins the DODAG and replies with a DAO message which has its prefix information to the root. After that nodeA sends a DIO message which contains the DODAG information and nodeB which is in nodeA’s transmission scope receives the message, joins the DODAG, and replies with a DAO message to nodeA. NodeB has received a DIS request message from nodeC but replies nothing because it has not joined any DODAG. After nodeB joined the DODAG, nodeB sends DIO message to nodeC to invite it to join the DODAG. NodeC replies with a DAO message to nodeB after it has joined the DODAG. NodeB will integrate information after receiving the message and then send the DAO message to its preferred parent nodeA. After all, the DODAG root acquires all nodes’ prefix information by their DAO messages to form a downward route.Figure 1
Simplified flow diagram of the DODAG formation process.


### 2.3. QoI-Aware Event Detection Based on Sequential Detection

In the above methods, nodes forward messages without caring about QoI of these messages. In an event detection WSN we need not to collect all of sensor data to make a decision. To reduce the amount of forwarded data to save energy, literature [23] proposed Sequential Probability Ratio Test (SPRT) based on sequential detection. In SPRT, the amount of data which are required for making a decision is dependent on the data in the front of the data sequence which has been obtained thus far.V
{
v
0
,
v
1
,
…
,
v
n
} denotes the set of n nodes in the WSN and the DODAG root v0. In SPRT, they let Xa{x1,x2,…,xVa} be the collected data sequence from each node va∈Va. Using sequential detection, data collection can be terminated at the earliest subsequence Xτ{x1,x2,…,xτ}⊆Xa when the decision that an event has occurred can be made. That subsequence is the minimal cost of data acquisition. The decision can be made by the subsequence due to the sufficient information.For the independent sample of a node, the independent signalyi obtained by a node vi is(1)yi=ωiifH0,fri+ωiifH1,where ωi~N(0,σω0) is the random noise overlaid onto f(ri) that follows a normal distribution with mean zero and standard deviation σω; ri is the distance between vi and the occurring event. The function f is the expression of signal intensity and it decreases monotonically with the distance ri increases; H1 denotes the occurrence of an event in the event detection WSN; H0 denotes the absence of the event. For each signal yi sampled by a sensor node, vi can make a single-sample binary decision bi such that(2)bi=0ifyi<Ti,1otherwise,where Ti is the single-sample threshold for making single-sample binary decision by vi.The probability of false alarmp0i sampled by node vi is independent of its location, and the equation is given by [19] (3)p0i=Pbi=1∣H0=QTiσω,where Q(x) is the GaussianQ-function of a standard normal distribution. And the single-sample probability of event detection p1i (where p1i>p0i) at vi is dependent on the distance ri between vi and the occurring event, and the equation is given by(4)p1i=Pbi=1∣H1=QTi-friσω.Each node collects data at periodic intervals for event detection; however, it costs a lot for each sample data to be transmitted to the DODAG rootv0. Consequently, data sampled by vi to be transmitted to v0 only if vi makes a decision that the event has occurred and then activates itself for transmitting the data.The DODAG rootv0 makes a final decision whether the event occurs based on the data sequence that is received from the set of activated nodes Va. Let B={b1,b2,…,bVa} be a single-sample binary sequence that v0 receives from each va∈Va in a period of time. The event detection probability P(H1)=p, where 0<p<1 is known a priori, and in consequence P(H0)=1-p. Nodes periodically sense the environment and collect data around themselves independently. The collected data by sensors are independently and identically distributed (i.i.d.).Forv0 making the decision from the single-sample binary sequence, the Likelihood Ratio Test (LRT) [24] of the optimal convergence rule is(5)ΛB=Pb1,b2,…,bVa∣H1Pb1,b2,…,bVa∣H0≥H1≤H01-pp.Hence, based on the data sequencev0 can make the decision that the event occurs (H^=H1) if Λ(B)≥1-p/p.In a DODAG the cumulative log-likelihood ratioS0 at the DODAG root v0 is(6)S0=log⁡ΛB=log⁡∏i=1VaΛbi.If a set of nodes denoted withViu has an upward path to the root v0 across vi in the DODAG, the cumulative log-likelihood ratio Si at the node vi is(7)Si=log⁡ΛB=log⁡∏i=1ViuΛbi.A stopping rule according to the collected dataγi={0,1} should be made after the collected data sequence has enough information to make a decision. It is dependent on the event detection probability Pd and the false alarm probability Pf. The global decision whether the event occurs H^ should be made at v0, and the formula is given by Wald’s equation [23]:(8)γi=0ifA<Si<B,1otherwise,where A=log⁡1-Pd/1-Pf and B=log(Pd/Pf). The DODAG root v0 makes the decision H^:(9)H^=H0ifSi≤A,H1Si≥B.Hence, we can map the required QoI thresholdIT to B to get a minimal amount of required data when Pd and Pf are provided. Based on the sequential detection, the set of data generated by the activated nodes Vi and forwarded to the DODAG v0 satisfies(10)S0=log⁡ΛB=log⁡∏i=1ViΛbi≥B,in which qi=log⁡Λbi is the QoI contribution provided by each node vi.


## 2.1. Related Works

Recently, a general principle of quality of information (QoI) has emerged. In this framework, QoI is the measurement of its content. We can use routing protocols to aggregate and/or fusion data and fetch required results in WSNs for saving energy [13, 14].Unlike aggregation-based routing protocols, QoI-aware routing protocols measure the QoI of the message during data aggregation and forwarding. IDSQ and CADR [15–17] are routing protocols which are information-aware for saving energy, minimizing delay and overhead. In these schemes each node selects the neighboring node with the highest predicted gain of information as the next-hop along the path, and at the time when the fused data satisfies a given QoI threshold it is transmitted to the root. However, these schemes ignore other information besides the routing path. Therefore, it is not appropriate for event detection targeted WSNs in a flat plane. IQAR [18] adopts a tree based approach in WSNs but the root of the tree is the fusion center which cost more energy consumption. Event detection in sensor networks [19–22] is on designing energy efficient hypothesis testing models to detect the presence of the event. Most of these schemes do not consider routing and are based on a star network topology.


## 2.2. Overview of DODAG Construction in RPL

RPL is a distance vector routing protocol that builds a DODAG in addition to a set of features to bound the control traffic, support local (and slow) repair, and so on. The RPL architecture provides a flexible method by which each node performs DODAG discovery, construction, and maintenance. RPL provides a series of new ICMPv6 control messages for exchanging the information of DODAG to form network topology. In RPL, a node may use DODAG Information Solicitation (DIS) message to probe its neighborhood for nearby DODAGs. The DODAG Information Object (DIO) carries information that allows a node to discover a RPL Instance, learn its configuration parameters, select a DODAG parent set, and maintain the DODAG. The Destination Advertisement Object (DAO) message is used to propagate reverse route information to record the nodes visited along the upward path. A node’s Rank defines the node’s individual position relative to other nodes with respect to a DODAG root. Rank strictly increases in the down direction and strictly decreases in the up direction. The exact way Rank is computed depending on the DAG’s Objective Function (OF). The Rank may analogously track a simple topological distance, may be calculated as a function of link metrics, and may consider other properties such as constraints.The process of the DODAG construction begins from the DODAG root. First, the DODAG root broadcasts the DODAG information by transmitting a DIO message. Neighbors of the root receive and process the DIO message. The DIO message is processed and transmitted to other nodes one by one. A node which has not joined any DODAGs calculates the cost of the path to the DIO sender and then decides whether to join the DODAG or not. Once a neighbor joins the DODAG, it has a route towards the DODAG root, and the root becomes a DODAG parent of the node. Next, the node calculates its Rank in the DODAG and replies with a DAO message to its parent to inform its participation. A node which has not received any DIO messages and has not joined any DODAGs can request DODAG information by sending DIS messages periodically to its neighbors. All of the neighbors repeat this process until all of the nodes join the DODAG. Figure1 depicts a simplified flowchart of the DODAG construction process. The DODAG root sends a DIO message with DODAG information; nodeA receives the DIO message and joins the DODAG and replies with a DAO message which has its prefix information to the root. After that nodeA sends a DIO message which contains the DODAG information and nodeB which is in nodeA’s transmission scope receives the message, joins the DODAG, and replies with a DAO message to nodeA. NodeB has received a DIS request message from nodeC but replies nothing because it has not joined any DODAG. After nodeB joined the DODAG, nodeB sends DIO message to nodeC to invite it to join the DODAG. NodeC replies with a DAO message to nodeB after it has joined the DODAG. NodeB will integrate information after receiving the message and then send the DAO message to its preferred parent nodeA. After all, the DODAG root acquires all nodes’ prefix information by their DAO messages to form a downward route.Figure 1
Simplified flow diagram of the DODAG formation process.


## 2.3. QoI-Aware Event Detection Based on Sequential Detection

In the above methods, nodes forward messages without caring about QoI of these messages. In an event detection WSN we need not to collect all of sensor data to make a decision. To reduce the amount of forwarded data to save energy, literature [23] proposed Sequential Probability Ratio Test (SPRT) based on sequential detection. In SPRT, the amount of data which are required for making a decision is dependent on the data in the front of the data sequence which has been obtained thus far.V
{
v
0
,
v
1
,
…
,
v
n
} denotes the set of n nodes in the WSN and the DODAG root v0. In SPRT, they let Xa{x1,x2,…,xVa} be the collected data sequence from each node va∈Va. Using sequential detection, data collection can be terminated at the earliest subsequence Xτ{x1,x2,…,xτ}⊆Xa when the decision that an event has occurred can be made. That subsequence is the minimal cost of data acquisition. The decision can be made by the subsequence due to the sufficient information.For the independent sample of a node, the independent signalyi obtained by a node vi is(1)yi=ωiifH0,fri+ωiifH1,where ωi~N(0,σω0) is the random noise overlaid onto f(ri) that follows a normal distribution with mean zero and standard deviation σω; ri is the distance between vi and the occurring event. The function f is the expression of signal intensity and it decreases monotonically with the distance ri increases; H1 denotes the occurrence of an event in the event detection WSN; H0 denotes the absence of the event. For each signal yi sampled by a sensor node, vi can make a single-sample binary decision bi such that(2)bi=0ifyi<Ti,1otherwise,where Ti is the single-sample threshold for making single-sample binary decision by vi.The probability of false alarmp0i sampled by node vi is independent of its location, and the equation is given by [19] (3)p0i=Pbi=1∣H0=QTiσω,where Q(x) is the GaussianQ-function of a standard normal distribution. And the single-sample probability of event detection p1i (where p1i>p0i) at vi is dependent on the distance ri between vi and the occurring event, and the equation is given by(4)p1i=Pbi=1∣H1=QTi-friσω.Each node collects data at periodic intervals for event detection; however, it costs a lot for each sample data to be transmitted to the DODAG rootv0. Consequently, data sampled by vi to be transmitted to v0 only if vi makes a decision that the event has occurred and then activates itself for transmitting the data.The DODAG rootv0 makes a final decision whether the event occurs based on the data sequence that is received from the set of activated nodes Va. Let B={b1,b2,…,bVa} be a single-sample binary sequence that v0 receives from each va∈Va in a period of time. The event detection probability P(H1)=p, where 0<p<1 is known a priori, and in consequence P(H0)=1-p. Nodes periodically sense the environment and collect data around themselves independently. The collected data by sensors are independently and identically distributed (i.i.d.).Forv0 making the decision from the single-sample binary sequence, the Likelihood Ratio Test (LRT) [24] of the optimal convergence rule is(5)ΛB=Pb1,b2,…,bVa∣H1Pb1,b2,…,bVa∣H0≥H1≤H01-pp.Hence, based on the data sequencev0 can make the decision that the event occurs (H^=H1) if Λ(B)≥1-p/p.In a DODAG the cumulative log-likelihood ratioS0 at the DODAG root v0 is(6)S0=log⁡ΛB=log⁡∏i=1VaΛbi.If a set of nodes denoted withViu has an upward path to the root v0 across vi in the DODAG, the cumulative log-likelihood ratio Si at the node vi is(7)Si=log⁡ΛB=log⁡∏i=1ViuΛbi.A stopping rule according to the collected dataγi={0,1} should be made after the collected data sequence has enough information to make a decision. It is dependent on the event detection probability Pd and the false alarm probability Pf. The global decision whether the event occurs H^ should be made at v0, and the formula is given by Wald’s equation [23]:(8)γi=0ifA<Si<B,1otherwise,where A=log⁡1-Pd/1-Pf and B=log(Pd/Pf). The DODAG root v0 makes the decision H^:(9)H^=H0ifSi≤A,H1Si≥B.Hence, we can map the required QoI thresholdIT to B to get a minimal amount of required data when Pd and Pf are provided. Based on the sequential detection, the set of data generated by the activated nodes Vi and forwarded to the DODAG v0 satisfies(10)S0=log⁡ΛB=log⁡∏i=1ViΛbi≥B,in which qi=log⁡Λbi is the QoI contribution provided by each node vi.


## 3. The Implementation of Improved Global DODAG Discovery and Local QoI-Aware DODAG Construction

### 3.1. An Improved Global DODAG Discovery Process

In this subsection we analyze the reason of network topology changes caused by DIO message loss in noisy environment, then we describe the topology repair method in detail, and at the end we analyze the cost of this method.The performance of DODAG construction goes bad in a noisy environment. The loss of a DIO message from its expected preferred parent brings the node a larger rank value and leads to larger transmission delay and energy consumption.As is shown in Figure2, letA,B, andC be neighbors within the respective communication radius, where nodeA is the node that has joined DODAG. There are two situations in the DODAG construction process: the noiseless environment and the noisy environment. In the situation of the noiseless environment, the Packet Loss Ratio (PDR) between nodes is 0; in the situation of the noisy environment, the PDR between nodes is not 0.Figure 2
A contrast of DODAG discovery processes in nonnoise environment and noisy environment.When the DODAGs start constructing, the node that does not join the DODAG sends broadcast DIS message to detect whether or not a node has joined the DODAG around it. The node that has joined the DODAG replies with a broadcast DIO message to inform the DODAG information after receiving the DIS request. The nodes surround the DIO sender and then join the DODAG after receiving the DIO message. If a node that has joined a DODAG does not receive any DIS request, it will send a DIO message after a period of time. The delay time is given by the Trickle algorithm [25].In the noiseless environment, the process of DODAG construction is shown in the upper part of Figure2. NodeA sends a DIO message; nodeB and nodeC receiveA’s DIO message. NodeB and nodeC add nodeA as their parent. The process of DODAG construction ends.In the noisy environment, the process of DODAG construction is shown in the lower part of Figure2. We suppose that when nodeA broadcasts DIO message, nodeB receives and nodeC does not receive the DIO message, nodeB joins the DODAG, and nodeC does not join. Then nodeB broadcasts the DIO message at some time after joining the DODAG so that the surrounding nodes join the DODAG. If nodeC receives the DIO message from nodeB, it will join the DODAG with nodeB as its parent. In this way, the network topology is different from the noiseless environment situation. It is because nodeC does not receive the DIO message sent by nodeA. In this network topology there is no direct link between nodeA and nodeC. Communication betweenA andC can only be forwarded through nodeB, which results in increased transmission latency and increased power consumption.The above-mentioned phenomena are caused by the loss of DIO messages. We propose a method to repair the network topology to solve this problem. The method uses the neighbor list and the information of DIO sender’s parent to determine whether the current DIO sender is an appropriate parent.According to RFC6550 [8], each node sends a DIS message after power on to detect whether there are any nodes that have joined the DODAG in the surrounding, so each node will receive DIS messages sent by the surrounding nodes. After receiving these DIS messages, nodes can establish the neighbor list according to the node ID in the DIS messages.On the other hand, we add the node ID information of the DIO sender’s parent in the DIO message. If the node ID of the DIO sender’s parent is in the neighbor list of the DIO receiver, the DIO sender and the DIO sender’s parent are both neighbors of the DIO receiver. Then the DIO receiver confirms whether the DIO sender’s parent node is available. If the DIO sender’s parent is available, the DIO receiver takes the DIO sender’s parent instead of the sender as its parent. Then the network topology is repaired in the case of DIO message loss.The specific repair process is as follows:(1)
A broadcast DIS receiver adds the DIS senders’ ID to its neighbor list.(2)
A DIO sender adds the node ID of its preferred parent to the DIO message before the DIO message broadcasted it to its neighbors. If the DIO sender is the root, its parent’s ID in the DIO message is null.(3)
A DIO receiver which has not joined any DODAGs checks the parent ID of the DIO sender in the DIO message. If the parent ID of the DIO sender is in the DIO receiver’s neighbor list, the DIO receiver should send a unicast DIS message directed to the DIO sender’s parent to ensure that it is available. If it is available, the DIO receiver should add the DIO sender’s parent as one of its parents rather than the aforementioned DIO sender. The parent ID which is null in the DIO message shows that the DIO sender is the root node. The DIO receiver should join the DODAG and accept the root as its preferred parent without judging.(4)
After selecting the appropriate parent, the DIO receiver sends a DAO message to the parent to inform its parent that it has joined the DODAG. Then the node adds the parent node ID to its DIO message and broadcasts it to the surrounding nodes to join the DODAG. All nodes perform this process until they all join DODAG, the network topology constructed.The energy consumed by the routing algorithm is composed of two parts: control message transmission energy consumption and data calculation energy consumption. The energy consumption by data transmission is far more than that by data calculation. The improved algorithm proposed in this paper only increases the task of searching neighbor list, and the length of the neighbor list is not large because of the limited communication radius, so the increase of the energy consumption is negligible. The main energy consumption increase by the improved routing algorithm comes from the DIS messages generated by the node to repair the network topology. The increase of energy consumption is related to the noise level of the network environment. The average increase in the number of DIS messages transmitted per node is between 0 and 1. This is the cost of repairing the network topology.


### 3.2. QoI-Aware Local DODAG Discovery and Construction

Based on the QoI-aware event detection model in Section2 we have come to the conclusion that we can make accurate enough decisions without collecting data from all of the nodes in the WSN. Our objective is to construct a QoI-aware local DODAG for detecting event by the activated nodes with the total QoI contribution at least IT. And handling the collected data in the network rather than at the root helps reduce the cost of forwarding all data to the root. Formally, we want to find a subset of nodes VT which are activated by single-sample binary decision bi=1 that constructs a local DODAG near the occurring event in the WSN. The sensor data are collected and processed by the root of local DODAG and transmitted to the root of global DODAG. The root of the local DODAG collects data and checks the total QoI contribution ∑vi∈VTqi to decide if it is sufficient for the final decision H^ to be made by the following formula: (11)H^=H1if∑vi∈VTqi≥log⁡PdPf,H0if∑vi∈VTqi≤log⁡1-Pd1-Pf.Once the sequence is sufficient to make a decision (γi=1), the root of the local DODAG stops collecting according to the stopping role and processes the current sequence for transmitting the result to the global root. However, if all of the data in the local DODAG are insufficient for making a decision (γi=0), the root of the local DODAG should transmit all the data to the global root. In this case, the decision can only be made by the global root.To address this requirement, we designed local DIS and DIO messages with the sensor nodes’ single QoI contributionqi that gathered by each sensor. The construction of local DODAG depends on these messages. The activated nodes exchange local DIS and DIO messages to elect local DODAG root which has the max value of qi. After the local DODAG discovery and construction, nodes in the local DODAG send its processed data to the root of the local DODAG to reduce the forwarding cost. The steps mainly include the following:(1)
Add a QoI contribution of sensor data and a timestamp in DIS and DIO messages to construct local DIS and local DIO messages. Add a queue of received data to check if the data is sufficient for making a decision, Add a local DODAG timer to adjust the local DODAG construction duration.(2)
Node broadcasts a local DIS with the QoI contributionqi when it is activated; then the node collects broadcast DIS messages from its neighbors in a time period τ.(3)
After a time intervalτ, node compares the QoI contribution of itself with all of received DIS. If the QoI of itself is larger than all of received DIS, node broadcasts a local DIO to its neighbors. The neighbors of the DIO sender join the local DODAG and treat it as their local root in the local DODAG. These DIO receivers then send their multicast DIO to the nodes which has lower QoI contribution to construct local DODAG.(4)
If the QoI contribution of itself is less than one of received DIS, node needs to wait until it received DIO messages. Then it assigns a DIO sender which has the largestqi as its preferred parent.(5)
If a node receives a DIS from a node which has not been sent to it (review its received queue) after node has joined a DODAG, the node sends a DIO with its QoI contribution. The receiver of the DIOs chooses a DIO sender which has the largest QoI contributionqi as its preferred parent. The local DODAG has been constructed so far.(6)
All the nodes in the local DODAG send their data to the local root. The local root checks whether it is sufficient to make a decision (γi=1). If γi=1, the local root sends the result to the global root. If γi=0, the local root compresses all the data and sends the compressed data to the global root.(7)
An activated node which has not joined any local DODAG sends its data directly to the global root after it has not received any DIO during the time intervalnτ. “n” indicates the contribution factor and is computed by the following formula:(12)n=ITqiifITqi>2,2ifITqi≤2.


## 3.1. An Improved Global DODAG Discovery Process

In this subsection we analyze the reason of network topology changes caused by DIO message loss in noisy environment, then we describe the topology repair method in detail, and at the end we analyze the cost of this method.The performance of DODAG construction goes bad in a noisy environment. The loss of a DIO message from its expected preferred parent brings the node a larger rank value and leads to larger transmission delay and energy consumption.As is shown in Figure2, letA,B, andC be neighbors within the respective communication radius, where nodeA is the node that has joined DODAG. There are two situations in the DODAG construction process: the noiseless environment and the noisy environment. In the situation of the noiseless environment, the Packet Loss Ratio (PDR) between nodes is 0; in the situation of the noisy environment, the PDR between nodes is not 0.Figure 2
A contrast of DODAG discovery processes in nonnoise environment and noisy environment.When the DODAGs start constructing, the node that does not join the DODAG sends broadcast DIS message to detect whether or not a node has joined the DODAG around it. The node that has joined the DODAG replies with a broadcast DIO message to inform the DODAG information after receiving the DIS request. The nodes surround the DIO sender and then join the DODAG after receiving the DIO message. If a node that has joined a DODAG does not receive any DIS request, it will send a DIO message after a period of time. The delay time is given by the Trickle algorithm [25].In the noiseless environment, the process of DODAG construction is shown in the upper part of Figure2. NodeA sends a DIO message; nodeB and nodeC receiveA’s DIO message. NodeB and nodeC add nodeA as their parent. The process of DODAG construction ends.In the noisy environment, the process of DODAG construction is shown in the lower part of Figure2. We suppose that when nodeA broadcasts DIO message, nodeB receives and nodeC does not receive the DIO message, nodeB joins the DODAG, and nodeC does not join. Then nodeB broadcasts the DIO message at some time after joining the DODAG so that the surrounding nodes join the DODAG. If nodeC receives the DIO message from nodeB, it will join the DODAG with nodeB as its parent. In this way, the network topology is different from the noiseless environment situation. It is because nodeC does not receive the DIO message sent by nodeA. In this network topology there is no direct link between nodeA and nodeC. Communication betweenA andC can only be forwarded through nodeB, which results in increased transmission latency and increased power consumption.The above-mentioned phenomena are caused by the loss of DIO messages. We propose a method to repair the network topology to solve this problem. The method uses the neighbor list and the information of DIO sender’s parent to determine whether the current DIO sender is an appropriate parent.According to RFC6550 [8], each node sends a DIS message after power on to detect whether there are any nodes that have joined the DODAG in the surrounding, so each node will receive DIS messages sent by the surrounding nodes. After receiving these DIS messages, nodes can establish the neighbor list according to the node ID in the DIS messages.On the other hand, we add the node ID information of the DIO sender’s parent in the DIO message. If the node ID of the DIO sender’s parent is in the neighbor list of the DIO receiver, the DIO sender and the DIO sender’s parent are both neighbors of the DIO receiver. Then the DIO receiver confirms whether the DIO sender’s parent node is available. If the DIO sender’s parent is available, the DIO receiver takes the DIO sender’s parent instead of the sender as its parent. Then the network topology is repaired in the case of DIO message loss.The specific repair process is as follows:(1)
A broadcast DIS receiver adds the DIS senders’ ID to its neighbor list.(2)
A DIO sender adds the node ID of its preferred parent to the DIO message before the DIO message broadcasted it to its neighbors. If the DIO sender is the root, its parent’s ID in the DIO message is null.(3)
A DIO receiver which has not joined any DODAGs checks the parent ID of the DIO sender in the DIO message. If the parent ID of the DIO sender is in the DIO receiver’s neighbor list, the DIO receiver should send a unicast DIS message directed to the DIO sender’s parent to ensure that it is available. If it is available, the DIO receiver should add the DIO sender’s parent as one of its parents rather than the aforementioned DIO sender. The parent ID which is null in the DIO message shows that the DIO sender is the root node. The DIO receiver should join the DODAG and accept the root as its preferred parent without judging.(4)
After selecting the appropriate parent, the DIO receiver sends a DAO message to the parent to inform its parent that it has joined the DODAG. Then the node adds the parent node ID to its DIO message and broadcasts it to the surrounding nodes to join the DODAG. All nodes perform this process until they all join DODAG, the network topology constructed.The energy consumed by the routing algorithm is composed of two parts: control message transmission energy consumption and data calculation energy consumption. The energy consumption by data transmission is far more than that by data calculation. The improved algorithm proposed in this paper only increases the task of searching neighbor list, and the length of the neighbor list is not large because of the limited communication radius, so the increase of the energy consumption is negligible. The main energy consumption increase by the improved routing algorithm comes from the DIS messages generated by the node to repair the network topology. The increase of energy consumption is related to the noise level of the network environment. The average increase in the number of DIS messages transmitted per node is between 0 and 1. This is the cost of repairing the network topology.


## 3.2. QoI-Aware Local DODAG Discovery and Construction

Based on the QoI-aware event detection model in Section2 we have come to the conclusion that we can make accurate enough decisions without collecting data from all of the nodes in the WSN. Our objective is to construct a QoI-aware local DODAG for detecting event by the activated nodes with the total QoI contribution at least IT. And handling the collected data in the network rather than at the root helps reduce the cost of forwarding all data to the root. Formally, we want to find a subset of nodes VT which are activated by single-sample binary decision bi=1 that constructs a local DODAG near the occurring event in the WSN. The sensor data are collected and processed by the root of local DODAG and transmitted to the root of global DODAG. The root of the local DODAG collects data and checks the total QoI contribution ∑vi∈VTqi to decide if it is sufficient for the final decision H^ to be made by the following formula: (11)H^=H1if∑vi∈VTqi≥log⁡PdPf,H0if∑vi∈VTqi≤log⁡1-Pd1-Pf.Once the sequence is sufficient to make a decision (γi=1), the root of the local DODAG stops collecting according to the stopping role and processes the current sequence for transmitting the result to the global root. However, if all of the data in the local DODAG are insufficient for making a decision (γi=0), the root of the local DODAG should transmit all the data to the global root. In this case, the decision can only be made by the global root.To address this requirement, we designed local DIS and DIO messages with the sensor nodes’ single QoI contributionqi that gathered by each sensor. The construction of local DODAG depends on these messages. The activated nodes exchange local DIS and DIO messages to elect local DODAG root which has the max value of qi. After the local DODAG discovery and construction, nodes in the local DODAG send its processed data to the root of the local DODAG to reduce the forwarding cost. The steps mainly include the following:(1)
Add a QoI contribution of sensor data and a timestamp in DIS and DIO messages to construct local DIS and local DIO messages. Add a queue of received data to check if the data is sufficient for making a decision, Add a local DODAG timer to adjust the local DODAG construction duration.(2)
Node broadcasts a local DIS with the QoI contributionqi when it is activated; then the node collects broadcast DIS messages from its neighbors in a time period τ.(3)
After a time intervalτ, node compares the QoI contribution of itself with all of received DIS. If the QoI of itself is larger than all of received DIS, node broadcasts a local DIO to its neighbors. The neighbors of the DIO sender join the local DODAG and treat it as their local root in the local DODAG. These DIO receivers then send their multicast DIO to the nodes which has lower QoI contribution to construct local DODAG.(4)
If the QoI contribution of itself is less than one of received DIS, node needs to wait until it received DIO messages. Then it assigns a DIO sender which has the largestqi as its preferred parent.(5)
If a node receives a DIS from a node which has not been sent to it (review its received queue) after node has joined a DODAG, the node sends a DIO with its QoI contribution. The receiver of the DIOs chooses a DIO sender which has the largest QoI contributionqi as its preferred parent. The local DODAG has been constructed so far.(6)
All the nodes in the local DODAG send their data to the local root. The local root checks whether it is sufficient to make a decision (γi=1). If γi=1, the local root sends the result to the global root. If γi=0, the local root compresses all the data and sends the compressed data to the global root.(7)
An activated node which has not joined any local DODAG sends its data directly to the global root after it has not received any DIO during the time intervalnτ. “n” indicates the contribution factor and is computed by the following formula:(12)n=ITqiifITqi>2,2ifITqi≤2.


## 4. Performance Evaluation

We have evaluated the performance of standard RPL and QoI-aware RPL in a500m∗500m simulation scenario. We allocated nodes in random positions in this scenario and the transmission ranges of the nodes are all the same. All the nodes communicate on the same channel. The global root was located near the bottom left hand corner of the scenario. Figure 3 gives a visual representation of the DODAG construction which includes 200 nodes. The numbers beside the nodes represent the DAGRANK value (and also hop count to the root) of node and the node ID. The root node is shown in red. We can see that the max DAGRANK is 13.Figure 3
An example of DODAG construction with 200 nodes (node ID and DAGRANK value are located beside the node).We set the event detection probability to 0.9 and the false alarm to 0.001. That is, if the cumulative probability of the event occurrence collected by sensors exceeds 0.9, we can make the decision that the event occurs; then we can transmit the fused data to the root without continuing to collect other data; if the cumulative probability that an event does not occur is less than 0.001, we can make the decision that the event does not occur; we do not need to transmit data. The false alarm probability of single sensor is set to 0.25 in the area of event (the three values are acceptable values in normal circumstances). For each individual combination of configuration in the simulation, we simulated 100 times and each time the nodes are placed randomly in the simulation scenario. In addition, we ensure that 95% of the nodes are in the constructed DODAG in each simulation. The DIO suppression intervalτ was set to 3 seconds.


### 4.1. DODAG Discovery and Construction with Interference

In the first set of simulations we focus on the influence of DODAG construction quality in a noise circumstance. We used the average hop count to the root to measure the influence at the time that the DODAG was formed. We evaluated the DODAG construction quality when PDR was set to 60%, 70%, 80%, 90%, or 100%. There were 100, 150, and 200 nodes whose transmission ranges were70m in three different simulation scenarios.Figure4 illustrates that various packet delivery ratio (PDR) affects the average hop count. The average hop count increased with the packet delivery ratio falling that brought more energy consumption for data transmission. This was caused by the loss of some DIO messages. The influence became larger if nodes have fewer neighbors on average due to fewer DIO messages each node had received. Compared with the standard RPL, QoI-aware RPL was less affected by the noise. With the PDR descended, the average hop count edged up by QoI-aware RPL. It was because both the DIS messages and the DIO messages were not be received at the same time. With the nodes increased, the effect of QoI-aware RPL descended due to the increased packets collisions.Figure 4
The average hop count with different PDR and node densities.


### 4.2. Varying Distance between Event Center and Global DODAG Root

In the second set of simulations we focus on how the distance between the event center and the root affected the energy consumption. We measured the energy consumption by total transmitted packet count in the simulations for simplification. We put 200 nodes in this simulation and their locations were also random except the root. The root node was also located at the bottom left hand corner of the scenario. The PDR of the nodes were 100%. An exponential sensing model [26] is applied to function f(ri) in (1). The event which occurred in a 100 m ∗ 100 m area and the distance of the event center was set to 150 m, 250 m, 350 m, and 450 m far from the root node in each simulation. The single-sample false alarm probability Pf was set to 0.25.Figure5 illustrates the total transmitted packet count in the simulations by standard RPL and QoI-aware RPL. With the distance between the event center and the root increased, the amount of total transmitted packets significantly raised by standard RPL because there is no data aggregation and/or fusion process in the network. The detected data were all forwarded directly to the root node. The farther the distance from the root to the event center, the more the number of times which the nodes’ packets will be forwarded. On the other hand, due to the fact that data were aggregated to the local DODAG root which has the maximal value of QoI contribution pi by QoI-aware RPL, nodes in the path from the local DODAG root to the global DODAG root only need to forward one aggregated packet to the root. Thus, the total transmitted packets increased unobviously.Figure 5
Performance with increasing distance between the event center and the root.


### 4.3. Varying the Area of Event

In the third set of simulations we expanded the area of event from100m∗100m to 250m∗250m which centered at {250,250}. We also used the total transmitted packets to measure the cost of event detection by standard RPL and QoI-aware RPL.As is shown in Figure6, with the network density increased, the amount of average neighbors (node degree) was raised. The number of activated nodes increased simultaneously. Both phenomena lead to raised energy consumption by both standard RPL and QoI-aware RPL. The excessive energy consumption incurred by standard RPL highlighted the sensor data which flowed through more intermediate nodes.Figure 6
Performance with increasing area of event.


## 4.1. DODAG Discovery and Construction with Interference

In the first set of simulations we focus on the influence of DODAG construction quality in a noise circumstance. We used the average hop count to the root to measure the influence at the time that the DODAG was formed. We evaluated the DODAG construction quality when PDR was set to 60%, 70%, 80%, 90%, or 100%. There were 100, 150, and 200 nodes whose transmission ranges were70m in three different simulation scenarios.Figure4 illustrates that various packet delivery ratio (PDR) affects the average hop count. The average hop count increased with the packet delivery ratio falling that brought more energy consumption for data transmission. This was caused by the loss of some DIO messages. The influence became larger if nodes have fewer neighbors on average due to fewer DIO messages each node had received. Compared with the standard RPL, QoI-aware RPL was less affected by the noise. With the PDR descended, the average hop count edged up by QoI-aware RPL. It was because both the DIS messages and the DIO messages were not be received at the same time. With the nodes increased, the effect of QoI-aware RPL descended due to the increased packets collisions.Figure 4
The average hop count with different PDR and node densities.


## 4.2. Varying Distance between Event Center and Global DODAG Root

In the second set of simulations we focus on how the distance between the event center and the root affected the energy consumption. We measured the energy consumption by total transmitted packet count in the simulations for simplification. We put 200 nodes in this simulation and their locations were also random except the root. The root node was also located at the bottom left hand corner of the scenario. The PDR of the nodes were 100%. An exponential sensing model [26] is applied to function f(ri) in (1). The event which occurred in a 100 m ∗ 100 m area and the distance of the event center was set to 150 m, 250 m, 350 m, and 450 m far from the root node in each simulation. The single-sample false alarm probability Pf was set to 0.25.Figure5 illustrates the total transmitted packet count in the simulations by standard RPL and QoI-aware RPL. With the distance between the event center and the root increased, the amount of total transmitted packets significantly raised by standard RPL because there is no data aggregation and/or fusion process in the network. The detected data were all forwarded directly to the root node. The farther the distance from the root to the event center, the more the number of times which the nodes’ packets will be forwarded. On the other hand, due to the fact that data were aggregated to the local DODAG root which has the maximal value of QoI contribution pi by QoI-aware RPL, nodes in the path from the local DODAG root to the global DODAG root only need to forward one aggregated packet to the root. Thus, the total transmitted packets increased unobviously.Figure 5
Performance with increasing distance between the event center and the root.


## 4.3. Varying the Area of Event

In the third set of simulations we expanded the area of event from100m∗100m to 250m∗250m which centered at {250,250}. We also used the total transmitted packets to measure the cost of event detection by standard RPL and QoI-aware RPL.As is shown in Figure6, with the network density increased, the amount of average neighbors (node degree) was raised. The number of activated nodes increased simultaneously. Both phenomena lead to raised energy consumption by both standard RPL and QoI-aware RPL. The excessive energy consumption incurred by standard RPL highlighted the sensor data which flowed through more intermediate nodes.Figure 6
Performance with increasing area of event.


## 5. Conclusion

In this paper a QoI-Aware DODAG construction mechanism for Low Power and Lossy Networks was proposed to improve the recent standard RPL protocol for event detection. The influence of noise on DODAG structure of RPL-based WSNs is discussed, and the quality and information are used to measure the data collected by the sensor. We shorten the deeper DODAG links due to the DIO message loss by the neighbor list and the DIO sender’s parent information and construct a least cost path for data fusion and transmission by measuring the quality of information that the sensor collected. This method constructs an effective DODAG to reduce the cost of data transmission by increasing less than 1 control message overhead in the networking process. Simulation results show that, on the premise of ensuring the quality of information, data transmission energy consumption reduced by 70%.



---

*Source: 1603713-2017-03-09.xml*