Evaluating routing metric composition approaches for QoS differentiation in low power and lossy networks

Abstract

The use of Wireless Sensor Networks (WSN) in a wide variety of application domains has been intensively pursued lately while Future Internet designers consider WSN as a network architecture paradigm that provides abundant real-life real-time information which can be exploited to enhance the user experience. The wealth of applications running on WSNs imposes different Quality of Service requirements on the underlying network with respect to delay, reliability and loss. At the same time, WSNs present intricacies such as limited energy, node and network resources. To meet the application’s requirements while respecting the characteristics and limitations of the WSN, appropriate routing metrics have to be adopted by the routing protocol. These metrics can be primary (e.g. expected transmission count) to capture a specific effect (e.g. link reliability) and achieve a specific goal (e.g. low number of retransmissions to economize resources) or composite (e.g. combining latency with remaining energy) to satisfy different applications needs and WSNs requirements (e.g. low latency and energy consumption at the same time). In this paper, (a) we specify primary routing metrics and ways to combine them into composite routing metrics, (b) we prove (based on the routing algebra formalism) that these metrics can be utilized in such a way that the routing protocol converges to optimal paths in a loop-free manner and (c) we apply the proposed approach to the RPL protocol specified by the ROLL group of IETF for such low power and lossy link networks to quantify the achieved performance through extensive computer simulations.

1 Introduction

Wireless Sensor Networks (WSNs) have invaded both the residential and business environments and they are deployed either indoor or outdoor to serve a great variety of applications. In residential environments [1], they usually serve security or conditions control applications while applications related to household logistics (grocery and meal planning) or for health and well-being purposes emerge [2]. In business environments, apart from applications related to the building control and maintenance, WSNs contribute in the automation of the production lines and warehouse logistics with thousands of sensors existing in modern factory plants [3]. Finally, outdoor applications for border monitoring and control, terrorist attack defense and environmental monitoring are proliferating [4]. Additionally, approaches that allow different applications to run over the same WSN are under development [5]. While the main characteristics of all the WSN are still the low power of the involved nodes, the lossy nature of the wireless medium and the need for cooperative routing to ensure self-organisation and infrastructure-less operation, the requirements of each application with respect to quality of service (QoS) are different: for example, a temperature monitoring application for condition control purposes is both loss and delay tolerant, while for security applications this is not the case. Inside a manufacturing plant, applications related to warehouse accounting may be delay tolerant, but for applications related to the production line monitoring and control (associated with robots that plant screws on a car), the reliability of the communication is of higher importance than any other performance aspect.

During the last decade, the intricacies of the WSNs have triggered an enormous research effort spent on the design of routing protocols which are reviewed in [6]. To support effective communications, the design of a routing protocol must be based on the characteristics of its target network and applications. For example, the mobility of nodes in ad-hoc networks demands routing protocols that can converge rapidly and maintain connectivity in an efficient manner, the severe energy constraints of WSNs demand the design of energy-efficient routing protocols and heavy traffic load in mesh networks requires load-balancing routing schemes. The network performance is directly linked to the routing protocol in place and the metric it uses to decide the packet routes which prompted researchers to design different routing metrics to optimize specific performance aspects (see [7–9]). Among them we find metrics indicating the distance from the destination measured in hops (hop count) or in distance units (measured on physical or virtual coordinates), the link reliability and packet loss due to congestion measured as the expected transmissions number (named usually ETX) until the packet is successfully received by the next hop node, the remaining energy of a node or of the nodes in a path. Different ways to quantify them exist (as discussed in [10]) with fifteen ways to quantify ETX proposed in [11] and a similar number reported in [7] for energy. Nevertheless, for a single network to satisfy diverse requirements, the design of proper composite metrics combining primary routing metrics in an additive (see e.g. [12]), lexicographic (see e.g. [13]) or more complicated (see e.g. [14]) manner has been pursued.

Unfortunately, there is a lack of knowledge about the impact of the routing metric designs on the overall operation of routing protocols which should hold the features of convergence, optimality and loop freeness. Yang, Sobrinho and Gouda (in their works presented in [13, 15–19]) have established the routing algebra which defines the properties that a routing metric has to hold so that the respective routing protocol maintains these features. This routing algebra has been applied successfully to a variety of routing protocols and Yang et al. in [18, 19] have proved that not all metrics satisfy these properties. Furthermore, even if two primary metrics satisfy these properties, this does not necessarily imply that they can be combined in a composite metric which holds these properties.

The contribution of this paper is three-fold: first, we discuss (primary) routing metrics that lead to optimization of specific performance aspects relevant to Low power and Lossy Networks (LLN) and to their respective applications and propose formulas for their evaluation, which guarantee the convergence, optimality and loop freeness of the routing protocol. Second and more importantly, we investigate their combination and prove that they can be flexibly combined in lexicographic or additive manner still holding the necessary and sufficient properties for ensuring the routing protocol’s convergence to (loop-free) optimal paths. Based on our work, the prospective WSN designer/implementer can decide which primary routing metric to use depending on the application at hand and combine them flexibly in a composite routing metric, being sure that the routing protocol converges to optimal paths. Last but not least, to provide further insight, we apply the proposed approach to the RPL protocol, which has been standardized by the ROLL group of IETF [20] and allows the system user to decide on the way the different routing metrics can be evaluated. The achieved performance is quantified for different primary and composite routing metrics through extensive computer simulations using the JSIM open simulation platform. We have chosen to apply our findings on RPL (which is a distance –vector protocol) because it is expected to be a widespread routing protocol in few years and it leaves the freedom of selecting the routing metric to the system designer/implementer.

The rest of the paper is organized as follows: in Sect. 2, the principles and basic theorems of the adopted routing algebra are presented and the lexicographic and additive metric compositions are defined. In Sect. 3, we define formulas for the quantification of the primary routing metrics and for their combination into composite routing metrics and we prove that they hold the necessary properties for the routing protocol to converge to optimal paths in a loop-free manner. In Sect. 4, the operation and the applicability of our work to the RPL protocol is discussed. The simulation results are presented in Sect. 5 to reach conclusions in Sect. 6.

2 Background: routing algebra and composite metric definitions

Back in 2002, J. L. Sobrinho defined suitable algebraic structures and explored their properties to shed light into distributed network routing, focusing on the Internet routing protocols. He understood routing algebras as a generalization of shortest-path routing [15], designed a routing algebra to study the Dijkstra-based shortest path algorithm and inferred the relation between routing requirements (optimality and loop-freeness) and properties of the routing algebra. Later, (see [16]) he studied the routing algebra for the distributed Bellman-Ford algorithm and included routing consistency as the third routing requirement. The Sobrinho’s routing algebra examined the properties that a routing metric must hold in order to comply with the three aforementioned routing protocol requirements.

In routing algebra, a (wireless) network is defined as a strongly connected directed graph composed of a set of nodes and a set of edges representing (wireless) links between neighboring nodes. According to [19], a routing metric can be formally represented as an algebra on top of a quadruplet $(S, \oplus ,\omega , \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{ \prec } )$, where S is the set of paths, ω is a function that maps a path or a link to a weight, $\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{ \prec }$ is an order relation and $\oplus$ is the path concatenation operation. This quadruplet is named path weight structure and it is the mathematical representation of a routing metric. The relation $\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{ \prec }$ provides a total order of weights, where $\omega (\alpha ) \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{ \prec } \omega (b)$ means “a is lighter (better) than or equal to b” (correspondingly, $\omega (\alpha ) \prec \omega (b)$ means “a is lighter (better) than b”). By using different definitions for ω() and $\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{ \prec }$, a path weight structure can capture different path and node characteristics, such as delay, bandwidth, hop count, link reliability and energy consumption. The target of this routing algebra is to be used for routing packets along the lightest path between any pair of nodes by using the appropriate metrics (path weight structure). Each path will have a weight and these weights are ordered so that any set of paths between the source and the destination node can be compared, leading to the decision of traversing through the lightest/optimal path. In order to achieve this task, two primitive properties are introduced in this routing algebra: monotonicity and isotonicity.

According to the definitions found in [19]:

• The quadruplet $(S, \oplus ,\omega , \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{ \prec } )$ is monotonic if and only if $\omega (a) \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{ \prec} \omega (a \oplus b)$ and $\omega (a) \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{ \prec } \omega (c \oplus a)$ holds for any paths α, b and c in S. Strict monotonicity holds, if and only if $\omega (a) \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{ \prec } \omega (a \oplus b)$ and $\omega (a) \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{ \prec } \omega (c \oplus a)$. Moreover, the quadruplet is right-monotonic if and only if condition $\omega (a) \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{ \prec } \omega (a \oplus b)$ holds and left-monotonic if and only if only condition $\omega (a) \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{ \prec } \omega (c \oplus a)$ holds.

• The quadruplet $(S, \oplus ,\omega ,\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{ \prec} )$ is isotonic if and only if $\omega (a) \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{ \prec } \omega (b)$ implies both $\omega (a \oplus c) \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{ \prec } \omega (b \oplus c)$ and $\omega (c \oplus a) \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{ \prec } \omega (c \oplus b)$, for all paths α, b, c in S. Similarly, the quadruplet is strictly isotonic if $\omega (a) \prec \omega (b)$ implies both $\omega (a \oplus c) \prec \omega (b \oplus c)$ and $\omega (c \oplus a) \prec \omega (c \oplus b)$. Finally, $(S, \oplus ,\omega , \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{ \prec } )$ is left-isotonic and right-isotonic if and only if $\omega (a) \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{ \prec } \omega (b)$ implies only $\omega (c \oplus a) \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{ \prec } \omega (c \oplus b)$ or only $\omega (a \oplus c) \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{ \prec } \omega (b \oplus c)$, respectively (see Fig. 1).

  Fig. 1

  

  Example of a left-isotonicity and b right-isotonicity property

Briefly speaking, monotonicity means that the weight of a path does not “decrease” (i.e. gets better) when prefixed or suffixed by another path. If the metric is monotonic, then every network can be made free of loops, thereby ensuring convergence of the routing protocols for distance vector protocols like RPL.

On the other hand, the isotonicity property essentially means that a routing metric should ensure that the order of the weights of two paths is preserved if they are appended or prefixed by a common third path. If the algebra is isotonic, then the paths onto which routing protocols converge are optimal for distance vector protocols.

In [19], the relationship between the path weigh structure properties and the routing protocol type is investigated and the conclusion is that monotonicity and strict isotonicity of the employed routing metric guarantees the optimality, consistency and loop-freeness of any routing protocol type (e.g. distributed Bellman-Ford or Dijkstra, source or hop-by-hop routing). While intuitively this is expected to hold for all routing metrics, Yang et al. (in [18, 19]) have investigated specific routing metrics including hop count, Expected Transmission Count (ETX), Expected transmission time (ETT), Weighted Cumulative ETT (WCETT), Energy –related metrics (BAMER) and Metric of Interference and Channel-switching (MIC). They proved that they are not all proper for inclusion in every type of routing protocol. For example, WCETT is monotonic but neither left-isotonic nor right-isotonic. On the contrary, hop-count, ETX and ETT are isotonic and thus they can guarantee loop-freeness.

With respect to the combination of the routing metrics, Gouda et al. defined in [13] the lexicographic and additive routing metric compositions which have been used to decide the structure of the routing tree in this work.

The Lexical metric composition of two routing metrics is defined as follows: Consider two routing metrics r₁, r₂ represented by the quadruplets $\left( {S, \oplus ,\omega_{1} , \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{ \prec }_{1} } \right)$ and $(S, \oplus ,\omega_{2} , \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{ \prec }_{2} )$, respectively, each one mapping every path of S to a weight value set (say $M_{1}$ and $M_{2}$, respectively) where $\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{ \prec }_{1}$ is the order relation over the set of metric values $M_{1}$ and $\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{ \prec }_{2}$ is the order relation over the set of metric values $M_{2}$. Then, the relation $\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{ \prec }_{lex}$ is defined as the lexicographic composition over the ordered pair $\left\langle { \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{ \prec }_{1} , \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{ \prec }_{2} } \right\rangle$ if and only if for every link pair α, b in S, which are mapped to the weight pairs $(\omega_{1} (\alpha ),\omega_{2} (\alpha ))$ and $(\omega_{1} (b),\omega_{2} (b))$ in $M_{1} \times M_{2}$:

$$ (\omega_{1} (\alpha ),\omega_{2} (\alpha ))\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{ \prec}_{lex} (\omega_{1} (b),\omega_{2} (b)) \Leftrightarrow(\omega_{1} (\alpha ) \prec_{1} \omega_{1} (b)) \vee \left({\omega_{1} (\alpha ) = \omega_{1} (b) \wedge \omega_{2} (\alpha )\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{ \prec}_{2} \omega_{2} (b)} \right) $$

(1)

In other words, when multiple routing metrics are combined into a composite lexicographic routing metric, this dictates that the primary routing metrics are prioritized and when a path offers a better weight with respect to the first metric then it will be preferred regardless of the path weights of the rest metrics. The second metric is taken into account only if more than one paths map to equal weights for the first metric. It is worth pointing out that any metric regardless of the order relation can be combined in lexicographic composite routing metrics because the comparison takes place between weights of the same metric, i.e. the order relations $\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{ \prec }_{1}$ and $\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{ \prec }_{2}$ are used to decide the order of the composite routing metric. For example, hop count and throughput are two metrics where an obvious optimization criterion is to select the path with the shortest hop count and the maximum available throughput. Assuming that the hop count metric maps the path to the (integer) number of included hops, then $\prec_{1}$ coincides with the “less than” order over the integers and the path with the minimum hop count is preferable (we call such metrics “minimizable”). For the throughput metric, assuming it maps paths of higher throughput to larger real numbers, then the $\prec_{2}$ order coincides with the “greater than” relation over the real numbers (we call such metrics “maximizable”). Even though the hop count is minimizable and throughput is maximizable, it is possible to combine them in a lexicographic composite routing metric and this would lead to selecting among the shortest paths, the one with the largest throughput.

Turning our attention to the monotonicity and isotonicity of the lexicographic composite routing metric, according to [13], to guarantee the monotonicity of the lexicographic composite routing metric, the two selected primary metrics have to be monotonic, while to guarantee the isotonicity the first of the combined primary metrics has to be strictly isotonic. (It is worth noticing that comparing the definitions of monotonicity and isotonicity presented in this section with [13], the property we have defined as monotonicity is related to “boundedness” in [13] and the isotonicity property is related to “monotonicity” in [13].)

The additive composition relation $\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{ \prec }_{add}$ over the set $M_{1} \times M_{2}$ is defined as follows:

$$ (\omega_{1} (\alpha ),\omega_{2} (\alpha )) \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{ \prec }_{add} (\omega_{1} (b),\omega_{2} (b)) \Leftrightarrow \omega_{1} (\alpha ) + \omega_{2} (\alpha ) \le \omega_{1} (b) + \omega_{2} (b) $$

(2)

In contrast to the lexicographic composition, in this case the two primary metrics should hold the same order relation ($\le$ or $\ge$) so that the produced composite additive routing metric makes sense. We will investigate the monotonicity and isotonicity properties of the additive composition approach later in Sect. 3.2.

3 Designing routing metrics for WSNs

Our aim is to design primary routing metrics which (a) capture WSN relevant node and network characteristics (b) are proved to be monotonic and strictly isotonic and (c) are suitable for building composite metrics to meet diverse application requirements still satisfying the monotonicity and strict isotonicity requirements so that the routing protocol converges to optimal paths in a loop-free manner. In the following sections, a routing metric is called additive over the path if the weight of a path is equal to the sum of weights of the links which produce the path when concatenated, i.e. $\omega (a \oplus c) = \omega (a) + \omega (c)$, for any paths a, c in S. Before proceeding with the discussion on the primary routing metrics, we state two properties of metrics that are additive over the path.

Theorem 1

Any metric $(S, \oplus ,\omega , \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{ \prec } )$ which (a) is additive over the path, (b) $\omega (a) > 0$ for any link α, and (c) $\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{ \prec }$ is the “less than or equal” order defined for real numbers, this metric is strictly monotonic, i.e. for any two paths α and b, $\omega (a) < \omega (a \oplus b)$ and $\omega (a) < \omega (b \oplus a)$.

Proof

Since $\omega (b) > 0$ for any path b, $\omega (a \oplus b) = \omega (a) + \omega (b) > \omega (a)$

Similarly $\omega (b \oplus \alpha ) = \omega (b) + \omega (\alpha ) > \omega (a)$ □

Theorem 2

Any metric $(S, \oplus ,\omega , \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{ \prec } )$ which (a) is additive over the path and (b) $\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{ \prec }$ is the “less than or equal” order defined for real numbers, this metric is strictly isotonic, i.e. for any links α, b and c, $\omega (a) < \omega (b) \Rightarrow \omega (a \oplus c) < \omega (b \oplus c)$ and $\omega (a) < \omega (b) \Rightarrow \omega (c \oplus a) < \omega (c \oplus b)$

Proof

From the specification of the “additive over the path” metric and its order relation, the following inequalities hold:

$$ \omega (a) < \omega (b) \Rightarrow \omega (a) + \omega (c) < \omega (b) + \omega (c) \Rightarrow \omega (a \oplus c) < \omega (b \oplus c) $$

and

$$ \omega (a) < \omega (b) \Rightarrow \omega (c) + \omega (a) < \omega (c) + \omega (b) \Rightarrow \omega (c \oplus a) < \omega (c \oplus b) $$

□

In other words, metrics that are minimizable and additive over the concatenated paths, are strictly isotonic; if their links further map to positive weights, they are also strictly monotonic.

It is worth mentioning that in [16], Sobinho states that monotonicity alone can guarantee convergence assuming that nodes prefer paths with minimum number of links among those with the same weight. This is also why in [19], the requirements for optimality, consistency and loop freeness for distance vector protocols do not include strict monotonicity. In the current paper, we remove the assumption about preference to paths with minimum links, since it mandates the implementation of a mechanism to do this which is not true for several protocols including RPL. As a consequence, the adopted routing metric has to be strictly monotonic to ensure loop freeness. We consider the situation that Sobrinho describes as a lexicographic combination of the hop count metric with any other.

3.1 Primary routing metrics

A routing metric that has been widely used to decide the cost of the routes in WSN is the hop count. It is a primary routing metric that is used to report the number of traversed nodes along the path and can be represented as $(S, \oplus ,\omega , \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{ \prec } )$, where ω maps a link to one, the weight of a path is equal to the sum of the weights of the links which produce the path when concatenated, i.e. $\omega (a \oplus c) = \omega (a) + \omega (c)$, for any paths a and c, and $\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{ \prec }$ is the “less than or equal” order defined for integers. Since the hop count satisfies all the conditions of theorems 1 and 2, it is both strictly monotonic and isotonic. By minimizing the number of traversed nodes, the overall number of transmissions is expected to be minimized leading to the consideration that also the overall energy consumption and the packet latency are reduced. However, this is true only under the assumption of equally loaded and equally lossy links, which in general does not hold.

To detect the link/path reliability, the Expected Transmission Count (ETX) has been proposed and defined as the number of transmissions a node expects to make towards a destination in order to successfully deliver a packet, according to [10]. The ETX is an “additive over the path” metric (see [18]) and on each link it expresses the number of link layer transmissions required for the successful delivery of a message to the next hop neighbour. Even if link layer losses are recovered by retransmission mechanisms, selecting lossy links results in high energy consumption and should be avoided. The successful delivery of a link layer frame is decided based on the reception of link layer acknowledgment. Based on ETX the lossy links are distinguished irrespective of the cause of loss, e.g. physical layer causes or contention at the MAC layer.

Assuming that node i transmits towards neighbor node j, realizing link α and that s packets were successfully delivered and f failures were observed (through the absence of link layer acknowledgement), the related metric can be quantified as

$$ \omega (\alpha ) = ETX^{i,\,j} = \frac{s + f}{s} > 0 $$

(3)

ETX is a minimizable routing metric in the sense that a path with lower ETX value is preferred over any path with higher ETX since higher ETX values indicate higher number of retransmissions. For the routing module of any node to maintain the ETX-related information, the routing layer has to communicate with the link layer, mandating the realization of a cross-layer interface. The ETX metric defined above satisfies all the prerequisites of theorems 1 and 2 and thus ETX is strictly isotonic and monotonic.

Apart from ETX, an important number of metrics that capture link quality/reliability has been proposed as e.g. ETT [11]. Furthermore, significant research work (e.g. [21, 22]) has been devoted to the design of interference-aware routing metrics. As soon as a metric holds the prerequisites of theorems 1 and 2, they are suitable either for adoption as individual routing metrics or for composition of metrics (as will be proved later on). Namely, ETT holds all the prerequisites of these theorems 1 and 2 while MIC (Metric of Interference and Channel-switching) as explained in [18] can also fulfill them if virtual nodes are introduced.

In energy-aware routing, the routing decisions depend on considerations of the available energy of the nodes. These considerations can be significantly more complicated than simply finding the route with the lowest energy consumption. In fact, the shortest path seems to introduce the lowest energy consumption, which is not necessarily true, if we take into account the retransmissions that may be needed. Even if we consider the energy cost of retransmission (through ETX), then few paths can be more loaded than others and nodes closer to the sink are more subject to premature energy depletion, since they have to relay more packets, which can eventually lead to network disconnection. As discussed in [7], while the researchers agree on the target of energy-aware routing which is the elongation of the network lifetime, different views on the definition of the network lifetime and the metrics to achieve it have been presented. Depending on the adopted approach, a wireless network is considered alive (a) when all nodes are alive or (b) when the energy-depleted nodes are less than a percentage (e.g. 5 %) or (c) when the network remains connected or (d) when all the monitored area is sensed or some other condition holds. Several metrics have been proposed (as e.g. in [23]), depending on the performance aspect that is to be optimized. Hence, adopting option (a), the metric that has to be considered should indicate the lowest energy level in the path and this should be maximized (max–min criterion). In other words, if any direct link α is scored by the metric $\omega (\alpha )$ which reflects the remaining energy of the end node i of the direct link, expressed as the ratio between the maximum (initial) energy $V_{\hbox{max} }$ and the current energy value $V_{now}$, i.e.

$$ \omega (\alpha ) = RE^{i} = \frac{{V^{i}_{\hbox{max} } }}{{V^{i}_{now} }} \ge 1 $$

(4)

then the energy metric $(S, \oplus ,\omega , \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{ \prec } )$ can be defined as $\omega (\alpha \oplus b) = \hbox{max} \{ \omega (\alpha ),\omega (b)\} \ge 1$, and $\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{ \prec }$ the “less than or equal” relation over real numbers. This way, the path traversing nodes with higher remaining energy will be preferred irrespective of the total number of nodes in the path (and, thus, irrespective of the overall energy consumption). This metric is concave and it is monotonic and isotonic but not strictly (it is easy to verify that the metric is not strictly monotonic). It is not strictly isotonic because, assuming $\omega (\alpha ) < \omega (b)$ it may happen that $\omega (\alpha ) < \omega (b) \le \omega (c)$ in which case $\omega (\alpha \oplus c) = \hbox{max} \{ \omega (\alpha ),\omega (c)\} = \omega (c) = \hbox{max} \{ \omega (b),\omega (c)\} = \omega (b \oplus c)$.

We opt for evaluating the energy-related metric of the concatenated path $\omega (\alpha \oplus b)$ as the summation of the metric values of the links forming the path, i.e. $\omega (\alpha \oplus b) = \omega (\alpha ) + \omega (b) > 1$. The advantages of this choice are two:

• 1. It sufficiently captures energy-related attributes of a path and enables energy-aware path comparison. To make it more clear, (a) if two paths α₁ and α₂ of the same length (say of k hops) are compared based on this metric, then the path (say α₁) that traverses nodes with higher energy on average will be selected, since (assuming path $\alpha_{1} = b_{1} \oplus b_{2} \oplus \ldots \oplus b_{k}$ and $\alpha_{2} = c_{1} \oplus c_{2} \oplus \ldots \oplus c_{k}$)

$$ \omega (\alpha_{1} ) < \omega (a_{2} ) \Leftrightarrow \sum\limits_{1}^{k} {\omega (b_{i} ) < \sum\limits_{1}^{k} {\omega (c_{i} ) \,\Leftrightarrow \,\frac{{\sum\nolimits_{1}^{k} {\omega (b_{i} )} }}{k}} } = \frac{{\sum\nolimits_{1}^{k} {\omega (c_{i} )} }}{k} $$

and (b) if two paths traversing nodes with the same energy-metric value, then the path with the lowest involved number of nodes will be preferred, which leads to overall network energy consumption savings since

$$ \omega (\alpha _{1} ) < \omega (a_{2} ) \Leftrightarrow k\cdot\omega (b_{i} ) < n\cdot\omega (c_{i} )\overset {\omega (b_{i} ) = \omega (c_{i} )} \longleftrightarrow k < n $$

For this reason, as will be also shown using computer simulations, the proposed RE metric succeeds in relieving the energy-weaker nodes in the network which are usually the nodes close to the sink.

• 2. This metric holds all the assumptions of theorems 1 and 2 and thus it is strictly isotonic and monotonic, which will prove to be significant properties for creating composite routing metrics.

To detect and minimize losses at layer 3 caused by misbehaving nodes, we propose the use of a trust-related primary routing metric. In WSNs, apart from layer-2 losses which are recovered through retransmissions, layer 3 losses may occur since a very common routing attack ([24, 25]) in WSNs is the black hole/grey hole attack during which a node refuses forwarding all/part of the traffic acting either selfishly (to economise energy) or maliciously, even though it acknowledges the reception of the traffic at layer 2. The impact on the network performance is aggravated if it additionally advertises “good” routes to the root, where “good” is expressed according to the adopted routing metric. To account for this cause of loss (which we consider as routing layer losses), we consider a trust-related metric which is evaluated as follows: each node after transmitting a packet to a neighbor, it enters the promiscuous mode and waits to listen whether the selected neighbor has actually forwarded its packet, as proposed in [25–28], thus building trust knowledge. Assuming that sf packets were successfully forwarded and ff packets failed to be forwarded (realized through the absence of overheard packet being forwarded), the estimated probability for a packet to successfully be forwarded on this link is:

$$ P_{succ} = \frac{sf}{sf + ff} $$

And the probability for a packet to successfully travel along this path α consisting of m links (without being dropped) is:

$$ P_{succ(a)} = \prod\limits_{i = 1}^{m} {\frac{{sf_{i} }}{{sf_{i} + ff_{i} }}} , $$

(5)

where i ranges over the m links that form the path α. Equivalently, the “best” path is the one that corresponds to the lowest value of the ratio $1/P_{succ(a)}$. Since the logarithmic function is monotonically increasing, to compare any two paths based on $1/P_{succ(a)}$, the $\log (1/P_{succ(a)} )$ can be equivalently compared, i.e. the trust on a path increases as the $\log (\frac{1}{{P_{succ(a)} }}) = \log (\prod\nolimits_{1}^{m} {\frac{{sf_{i} + ff_{i} }}{{sf_{i} }}} )$ decreases (throughout the paper the logarithm to base 10 is considered).

We define the packet forwarding indication (PFI) metric $(S, \oplus ,\omega , \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{ \prec } )$ for any link α as,

$$ \omega (\alpha ) = \log \left(\frac{1}{{P_{succ(a)} }} \right) = \log \left(\frac{sf + ff}{sf} \right) \ge 0 $$

(6)

and $\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{ \prec }$ the “less than or equal” relation over the (positive) real numbers.

For any path produced by the concatenation of paths α and b,

$$ \omega (\alpha \oplus b) = \log \left( {\frac{1}{{P_{succ(a \oplus b)} }}} \right) = \log \left( {\frac{1}{{P_{succ(a)} }} \cdot \frac{1}{{P_{succ(b)} }}} \right) = \log \left( {\frac{1}{{P_{succ(a)} }}} \right) + \log \left( {\frac{1}{{P_{succ(b)} }}} \right) = \omega (\alpha ) + \omega (b) \ge 0 $$

$$ {\text{i}} . {\text{e}} .\quad \omega (\alpha \oplus b) = \omega (\alpha ) + \omega (b) $$

The PFI metric is monotonic (although not strictly) and strictly isotonic (according to theorem 2).

The approach adopted for PFI can also be applied to other primary routing metrics that are multiplicative over the path. In other words, a derived routing $d(\omega (\alpha )) = \log (\omega (\alpha ))$where $\omega (\alpha ) \ge 1$ can be defined; this metric enables the comparison of two paths based on metric ω(α) and is suitable for inclusion in additive composite routing metrics.

3.2 Designing composite routing metrics

The combination of multiple primary routing metrics into a composite one can lead to the optimization of more than one performance aspect. However, the monotonicity and isotonicity properties still have to be proved for the composite routing metric so that the routing protocol guarantees loop-freeness, convergence and optimality.

Let us denote by ω the function that maps a path or a link to a weight for the additive routing metric which is defined based on ω₁ and ω₂, where ω₁ and ω₂ are the corresponding functions of any two of the primary metrics discussed in the previous section. We generalize the definition of the additive composite routing metric defined in (2) and define that the weight of a path can be expressed as

$$ \omega (\alpha ) = a_{1} \cdot \omega_{1} (\alpha ) + a_{2} \cdot \omega_{2} (\alpha ) $$

(7)

where $(a_{1} ,a_{2} )$ is a pair of positive real numbers which represent the relative weights of the two metrics and enable the shift of emphasis between the two primary routing metrics, as it will be shown using computer simulations.

Theorem 3

If ω ₁ and ω ₂ are the path-to-weight mapping functions for two strictly monotonic primary routing metrics for which the “less than or equal” order relation over real numbers is applied, then the additive composite routing metric $(S, \oplus ,\omega ,\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{ \prec } )$, with ω defined as in ( 7 ) and $\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{ \prec }$ defined as the same “less than or equal” relation, is also strictly monotonic, i.e. for any paths α and b

$$ \omega (a) < \omega (a \oplus b)\quad {\text{and}}\quad \omega (a) < \omega (b \oplus a) $$

Proof

Since $a_{1} > 0$, and ω₁ is strictly monotonic then

$$ \,\omega_{1} (\alpha ) < \omega_{1} (\alpha \oplus b) \Rightarrow a_{1} \cdot \omega_{1} (\alpha ) < a_{1} \cdot \omega_{1} (\alpha \oplus b) $$

(8)

Since $\,a_{2} > 0$, and ω₂ is strictly monotonic then

$$ \omega_{2} (\alpha ) < \omega_{2} (\alpha \oplus b) \Rightarrow a_{2} \cdot \omega_{2} (\alpha ) < a_{2} \cdot \omega_{2} (\alpha \oplus b) $$

(9)

Summing up the two inequalities (8) and (9), we have

$$ \begin{gathered} a_{1} \cdot \omega_{1} (\alpha ) + a_{2} \cdot \omega_{2} (\alpha ) < a_{1} \cdot \omega_{1} (\alpha \oplus b) + a_{2} \cdot \omega_{2} (\alpha \oplus b) \Rightarrow \hfill \\ \omega (\alpha ) < \omega (\alpha \oplus b) \hfill \\ \end{gathered} $$

Similarly the left monotonicity is proved. □

It is obvious that the strict monotonicity property of the additive routing metric holds for any combination of primary routing metrics that are strictly monotonic.

Theorem 4

If $(S, \oplus ,\omega_{1} , \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{ \prec } )$ and $(S, \oplus ,\omega_{2} , \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{ \prec } )$ are two strictly isotonic and additive over the path primary routing metrics (i.e. $\omega_{1} (a \oplus c) = \omega_{1} (a) + \omega_{1} (c)$, and $\omega_{2} (a \oplus c) = \omega_{2} (a) + \omega_{2} (c)$) then the additive composite routing metric $(S, \oplus ,\omega , < )$ is also strictly isotonic, i.e. for any paths α, b and c.

$$ \omega (a) < \omega (b) \Rightarrow \omega (a \oplus c) < \omega (b \oplus c)\quad {\text{and}}\quad \omega (a) < \omega (b) \Rightarrow \omega (c \oplus a) < \omega (c \oplus b) $$

Proof

From the definition of the additive composite routing metric, we have:

$$ \begin{gathered} \omega (a) < \omega (b) \Rightarrow \hfill \\ a_{1} \omega_{1} (\alpha ) + a_{2} \omega_{2} (\alpha ) < a_{1} \omega_{1} (b) + a_{2} \omega_{2} (b) \Rightarrow \hfill \\ a_{1} \omega_{1} (\alpha ) + a_{2} \omega_{2} (\alpha ) + a_{1} \omega_{1} (c) + a_{2} \omega_{2} (c) < a_{1} \omega_{1} (b) + a_{2} \omega_{2} (b) + a_{1} \omega_{1} (c) + a_{2} \omega_{2} (c) \Leftrightarrow \hfill \\ \left. \begin{gathered} a_{1} (\omega_{1} (\alpha ) + \omega_{1} (c)) + a_{2} (\omega_{2} (\alpha ) + \omega_{2} (c)) < a_{1} (\omega_{1} (b) + \omega_{1} (c)) + a_{2} (\omega_{2} (b) + \omega_{2} (c)) \hfill \\ {\text{since}}\quad \left\{ \begin{gathered} \omega_{1} (a \oplus c) = \omega_{1} (a) + \omega_{1} (c) \hfill \\ \omega_{1} (b \oplus c) = \omega_{1} (b) + \omega_{1} (c) \hfill \\ \omega_{2} (a \oplus c) = \omega_{2} (a) + \omega_{2} (c) \hfill \\ \omega_{2} (b \oplus c) = \omega_{2} (b) + \omega_{2} (c) \hfill \\ \end{gathered} \right. \hfill \\ \end{gathered} \right\} \hfill \\ \end{gathered} $$

From the definition of the additive composite routing metric, this leads to

$$\omega(a \oplus c) <\omega(b \oplus c) $$

Similarly the left isotonicity is proved. □

So, the additive composite routing metric holds both the strict monotonicity and strict isotonicity properties for any combination of primary routing metrics as long as they are strictly monotonic, strictly isotonic and additive over the path.

3.3 Use of primary and composite routing metrics

The discussed primary routing metrics are summarized in Table 1, where the effect to be captured and the target performance metric to be optimized are also indicated. They are all additive over the path, all of them are strictly isotonic and all (except PFI) are strictly monotonic; PFI is monotonic but not strictly. Thus,

Table 1 The proposed primary routing metrics and their characteristics

• All the proposed primary routing metrics can be used in any routing protocol type (like the ones presented in [19]) apart from PFI which has to be combined with a strictly monotonic metrics to ensure loop freeness.

• Any lexicographic combination of the proposed primary routing metrics can be used in any routing protocol type given that all the primary routing metric presented in the previous section are monotonic and strictly isotonic, and any combination of them in lexicographic manner produces a monotonic and strictly isotonic composite metric, as discussed in Sect. 3.2.

• Any additive combination of the proposed primary routing metrics can be used in any routing protocol type given the primary routing metrics properties and the theorems proved in Sect. 3.2.

Prospective implementers should take into account that:

• When combining primary metrics in lexicographic manner, the second metric will be inspected only if two paths are equivalent with respect to the first metric. If the first metric is not associated with integers (or a limited number of discrete values), then it is very likely that the second metric will never (or very seldom) be considered. A viable solution could be to define a threshold for the tolerated difference between two paths with respect to the first metric, so that the second metric is also considered.

• When combining primary metrics in additive manner using relation (7), the parameters α₁, α₂ allow for fine-tuning of the solution, as will be shown in the simulation results section.

• While we have considered only minimizable primary routing metrics (i.e. the path with the lowest weight is the best), maximizable routing metrics have also been proposed in the literature. These can be used a) either as individual primary metric (as soon as they are monotonic and isotonic) or b)can be combined in lexicographic composite metrics with maximizable and minimizable routing metrics or c) can be combined with maximizable metrics in additive composite metrics. In other words, they cannot be combined with minimizable metrics in additive manner since the sum of a maximizable and a minimizable routing metrics makes no sense and the metrics cancel one another.

• Any other primary routing metric holding the properties required for theorems 1 and 2 can be included in Table 1 and be combined with the metrics listed in it. The selected metrics represent just an indicative set capturing different effects.

4 Applicability to RPL

The Routing Over Low power and Lossy networks (ROLL) group has standardized the so-called IPv6 Routing Protocol for LLNs (RPL) [20] which provides a mechanism whereby traffic from devices inside the Low power and Lossy Network (LLN) is routed towards a central control point inside the LLN. RPL constructs Directed Acyclic Graphs (DAG) and defines the rules based on which every node selects a neighbor as its preferred parent in the DAG, thus forming a tree. To cover the diverse requirements imposed by different applications, ROLL has specified in [10] a set of link and node routing metrics and constraints (which can be static or dynamic) suitable to Low Power and Lossy link Networks to be used in RPL. This document does not provide details on the quantification of each routing metric, leaving it to the implementer to decide how to express each metric and how to combine them if needed. Recently, Zahariadis et al. [29] proposed an IETF draft that provides guidelines for routing metrics composition.

For the construction of the tree, each node calculates a rank value and advertises it in the so-called Destination Information Object (DIO) messages. The rank of a node is a scalar representation of the “location” of that node within a destination-oriented DAG (DODAG). In particular, the rank of the nodes must monotonically decrease from the leaves towards the DAG destination (root), i.e. the rank of every child is greater than the rank of its preferred parent. Each node selects as parent the neighbor that advertises the minimum rank value to guarantee loop free operation and convergence. The rank has properties of its own that are not necessarily those of all metrics. It is the Objective Function (OF) that defines how routing metrics are used to compute the Rank, and as such must demonstrate certain properties [30], [31].

5 Simulation results

Having proved that the proposed formulas for quantifying the primary routing metric and their combinations in additive or lexicographic composite routing metric lead to loop-free routing protocols which converge to optimal paths, our aim in this section is to shed light on the performance achieved based on different composite routing metrics.

The JSIM [32] open simulation platform has been used to model RPL. The features of our RPL model have been presented in [33] and the relevant code is publicly available at [34]. (Apart from tools to measure performance in terms of packet latency and packet loss, we also developed a graphical user interface which shows the constructed paths in real-time, thus allowing us to observe all dynamic path alterations.) The topology tested consists of 100 nodes placed on a 10 × 10 grid, and assigned a node identifier which is the concatenation of the column index and the row index which range from 0 to 9. For example, node 26 is located in the 3rd column, in the 7th row of the grid. Seven nodes (namely nodes 80, 61, 93, 65, 97, 58 and 79) were generating data messages towards the same destination (root node) periodically every 2 s, unless otherwise stated. Node 2 was selected as root node. The sessions were activated with a random offset and each session generated 1,600 data packets. Every node has eight one-hop neighbours apart from edge nodes (which have a lower number of one-hop neighbours). During our investigation, the routing metrics tested included Hop Count, ETX, PFI and RE either as single routing metrics or in combination with each other.

5.1 Combining HC with PFI

To create shortest paths avoiding misbehaving nodes (acting selfishly or maliciously), the hop count can be combined with PFI. To evaluate the performance benefits brought by the combination, we have run scenarios for different composite routing metrics combining HC and PFI for different penetrations of misbehaving nodes randomly distributed in the grid. The tested routing metrics include:

• the lexicographic combination of HC and PFI (marked as lex(HC, PFI) and lex(PFI, HC) in the figures)

• the additive combination of HC and PFI (marked as Add(HC, PFI)) for different (α₁, α₂) pair values and

• hop count (HC), for comparison reasons.

The misbehaving nodes perform “grey hole attacks”, i.e. drop randomly half of the received traffic and are randomly distributed in the network in the 50 different repetitions of each scenario.

The results regarding the packet loss are depicted in Fig. 2a. In this figure the curve obtained for HC is not included because it prevented the comparison of the rest routing metrics since it was almost linear reaching the value of 70 % packet loss for 30 % misbehaving nodes in the network. So, if the hop count is the only routing criterion, then, even with low penetration of misbehaving nodes and even if these nodes drop 50 % of the received traffic (and not all the received traffic as would happen in the case of black-hole attack), the packet loss raises very rapidly. This is alleviated for all tested composite routing functions combining PFI with hop count which offer better performance in terms of packet loss than HC when used on its own proving that the composite routing functions enable the detection of misbehaving nodes and the selection of paths that are more reliable. The improvement in loss depends on the adopted composite routing metric and on the penetration of misbehaving nodes. Looking at the composite routing metrics, the lexicographic combination of the hop count and PFI offers better performance than HC but worse than any additive combination of HC and PFI. This is due to the fact that in Lex(HC, PFI) case, the PFI metric is inspected only when alternative paths of equal length with better PFI values exist. For the additive combinations the performance significantly depends on the metric weight pair (α₁, α₂) especially when the penetration of misbehaving nodes increases. When the HC weight (α₁) is higher, the performance comes closer to that of the Lex(HC, PFI) while for lower α₁ values the emphasis is shifted to PFI and the performance comes closer to that of the Lex(PFI, HC) which is the best (with respect to loss) among the tested cases, since strict priority of PFI is assigned in this case.

Fig. 2

Performance comparison in terms of a packet loss and b latency for routing metrics combining Hop Count and PFI versus the penetration of misbehaving nodes

The average latency results are included in Fig. 2b and show that for zero misbehaving nodes in the network, all the tested routing metrics lead to equal average latency. Comparing the latency observed for the HC with any composite routing metric, the prevalent observations are: first, that the HC leads to the lowest latency and second, that the metric that leads to the best performance with respect to packet loss, leads to higher average latency. This is due to the fact that, to avoid the misbehaving nodes, longer paths are usually followed in the case of composite HC, PFI metrics. When the penetration of misbehaving nodes is low, then paths of equal length are very likely to exist and for this reason, for up to 10 % misbehaving node the latency differences are negligible (lower than 0.2 ms). The situation slightly changes when the number of misbehaving nodes increases, causing higher latency especially in the case of 30 % misbehaving nodes. It is worth pointing out that the average latency is calculated over the latency of packet that managed to reach the destination. The increase in latency for the different penetration depicted in the figure is on average less than two hop time (in our model, each hop introduces 1.5 ms of delay in simulation time), which is rather negligible compared to the packet loss improvements. It is worth stressing that the Lex(HC, PFI) results in latency performance very close to the one observed for the HC, while still offering a loss improvement of 23 % for 30 % malicious nodes in the network. While for any tested penetration of misbehaving nodes, the lower average latency is observed for the HC metric, it should be taken into account that in this case, even one misbehaving node on a data path, leads to 50 % packet loss for the session being routed over this path.

While the hop count information is built prior to any data packet exchange, the PFI value of the links is initially set to 0 (i.e. all nodes are a priori considered benevolent) and the PFI value of links involving a misbehaving node will become greater than 0 (based on Eq. (6)) only after a number of routing co-operations (for data forwarding) are attempted. As a result, the number of failed co-operations indicates how fast the misbehaving nodes are detected and avoided: the faster they are detected and avoided, the lowest the failed cooperation are and the better overall network performance is achieved, since lower loss leads to better throughput utilization and signifies that no power is consumed for transmissions in vain. The results shown in Fig. 3a prove that the number of failed cooperation depends on the “sensitivity” of the routing metric to PFI: the lowest number was observed for the Lex(PFI, HC) and the additive composite routing metric with metric weight pairs 0.2 and 0.8 for hop count and PFI respectively. This is also reflected in the average number of data message transmissions in the network for the successful delivery to the destination of one data packet, which we call “packet transmission cost” and is depicted in Fig. 3b. The worse situation was measured for the hop count metric while 20 % saving in transmission was achieved for the case of 20 % misbehaving nodes in the network through the use of any of the considered routing metrics. In other words, for each data packet generated by a source node, adopting a composite routing metric, the packet will reach its destination with 20 % less transmissions in the network for every packet that was successfully transferred to the root, compared to the case where the hop count is only considered for routing decisions.

Fig. 3

Performance comparison for routing metrics combining Hop Count and PFI in terms of a failed cooperation for data forwarding and b packet transmission count as a function of misbehaving node penetration

To this end, the combination of HC and PFI significantly increases the network efficiency in delivering data messages at the cost of slightly increased delay for the packets that would (otherwise) have been lost.

5.2 Combining HC with RE

In this section we investigate the combination of hop count with remaining energy (RE) considering that HC serves as a tool for reducing latency (a possible application requirement) and RE aims to satisfy a network requirement (for prolonged lifetime). When the Hop Count is the only routing metric used, the paths to the root are static, since no dynamic routing metric is taken into account, while they change dynamically when RE is also considered during routing decision making.

To investigate this effect, we have established seven data sessions within the same tree. When only the hop count metric is used, five of them pass through node 11 (one hop neighbour of the sink node) and one from node 12 (also one hop neighbour of the sink node). The results regarding the power consumption for these two nodes, expressed in percentage of initial energy consumed every ms are depicted in Fig. 4a. It is evident that when routing is decided based only on hop count, node 11 (which undertakes the forwarding of five data sessions) has higher energy consumption rate than node 12 (which participates in one data session). Combining HC with RE either in a lexicographic or in an additive manner, the energy consumption of both nodes drops since the forwarding load is distributed among all one hop neighbours of the destination-sink node and the energy consumption of the monitored nodes converges. The neighbors of node 11 and 12 will very quickly realize that node’s 11 remaining energy has dropped and will select another node offering a path to the root. This is proven by our simulation results, which show that the energy consumption of node 11 for any composite HC, RE metric is lower than the one observed when the HC is taken only into account for deciding the route. A lower difference is observed for node 12 since this forwards data from just one flow and the improvement potential is lower. Comparing the different composite routing metrics, the perfect load balancing is achieved when the additive routing metric places emphasis on the remaining energy. Any composite routing metrics brings an improvement ranging between 14 16 % for node 11 and between 6 and 8 % for node 12. Comparing the different composite routing metrics and with regards to the additive composite metric, as the weight of hop count decreases, an additional energy saving of 2 % is achieved. Comparing the additive case with the lexicographic, the energy consumption of the lexicographic is almost the same with the one observed for hop count weight below 0.25. It is worth stressing that in the HC case, the energy consumption of node 11 is not five times higher than that of node 12 since every node is not only transmitting/forwarding data messages but also control messages and in our runs we have set the control message interval equal to 4 s, which is comparable to the data message interval.

Fig. 4

Performance comparison in terms of a power consumption expressed in percentage of initial energy consumed every ms and b latency combining HC and RE in composite routing metrics

For the Lex(HC, RE) the selected path will always be the shortest while for any other combination it is possible that a neighbor with slightly longer path to the root than the shortest can be selected to avoid energy depletion. To assess this effect, we have measured the average latency observed for all the data packets transmitted in the network. The results, shown in Fig. 4b, reveal interesting features: first, the latency difference between any composite routing metric and the HC is less than 4 % (less than 0.8 ms). Second, the lexicographic routing metric and the additive routing metrics when high (>0.5) weight is assigned to the hop count metric lead to similar latency to the case where only the HC is used. In real life, the Lex(HC, RE) metric may lead to even lower delay than the one observed for HC because the forwarding load distribution (achieved by Lex(HC, RE)) alleviates link congestion effects.

To sum up, when the hop count and the remaining energy are combined either in a lexicographic or in additive composite routing metrics significant energy savings (up to 16 % for nodes participating in forwarding data from multiple data sessions) can be reached without severely compromising performance in terms of packet loss or latency.

5.3 Combining PFI, ETX and RE

The combination of three routing metrics is at the focus of another simulation scenario set. The three primary metrics chosen were ETX, PFI and RE. The use of PFI is expected to lead to paths free of misbehaving nodes (to the extent possible), the use of ETX leads to lossy link avoidance and the RE is used towards elongating the network lifetime.

In the simulation scenarios presented in this section, 10 % of the network nodes are misbehaving (grey hole) nodes that drop 50 % of the received traffic and another 10 % of them provide “lossy links” i.e. no link layer acknowledgment is generated for 80 % of the link frames. The lossy links and grey-hole nodes were uniformly distributed in the network. Different runs using lexicographic and additive composite routing metrics were tested.

To assess the efficiency in detecting the misbehaving nodes and the lossy links, we measured the number of grey hole attacks, i.e. the packets that were dropped by the misbehaving nodes and the link layer losses (i.e. unacknowledged messages) which are however, recovered through retransmissions. The results are included in Fig. 5a and show that the lower link layer losses are measured for the case where the routing is decided based on ETX only. The same amount of link layer losses is measured for the case of Lex(ETX, PFI, RE) since the routing is decided primarily based on ETX. However, in the lexicographic case the number of losses due to misbehaving nodes is significantly lower since PFI is also taken into account. In the case of the additive combinations, the balance between the link-layer losses and losses due to node misbehaviors depends on the metric weights value: as the weight of the PFI metric increases, the losses due to misbehaviors decrease.

Fig. 5

Comparison of network performance for metrics combining PFI, ETX and RE in terms of a losses due to node misbehaviors and link-layer losses (unacknowledged frames) and b network lifetime expressed as simulation time during which more than 95 % of the network nodes are alive

Figure 5b shows the network lifetime considering that the network is alive as soon as more that 95 % of the network nodes remain alive. Between the lexicographic combination and the additive that consider RE, the additive case leads to longer network lifetime. Although the difference in lifetime is not large, it should be taken into account that in the additive case, the network has significantly higher data delivery ratio (apart from longer lifetime) due to the flexible combination of ETX, PFI and RE metric. The slightly lower network lifetime for Add(ETX, PFI, RE) with zero weight assigned to the RE compared to ETX is justified by the transmission of packets which would have been dropped in the ETX case.

6 Discussion and guidelines

In the previous section, we presented and analysed the results from extensive simulation testing for indicative primary and composite routing metrics and quantified the performance difference between different composite routing and primary metrics. Based on these results, we provide here guidelines and examples of routing metrics that seem to better suit specific applications. In general, we can state that:

• 1. The additive composite routing metric leads to better overall performance compared to the respective lexicographic approaches in most of the cases, especially when the weighting factors are “well-balanced”, i.e. almost equally shared.

• 2. A “triple-metric” approach shows very good behavior under extreme and adverse conditions. The third metric can be RE with a weighting factor that does not exceed 0.3 value to achieve network lifetime elongation in parallel to other performance aspect optimisation.

• 3. The lexicographic approach can be proved a useful option when optimization is clearly related to a single type of misbehaviour; the lexicographic approach can be seen equal to an additive approach, strongly biased towards the first routing metric of the lexicographic.

Let us now examine example application domains and suggest routing metrics.

In energy control applications in public and private buildings, the need for extended network lifetime and for tackling scalability issues drives the use of a routing metric combining hop count and Remaining energy. Given that strict prioritization does not seem absolutely necessary, an additive combination of HC and RE is suggested where the RE metric weighting factor will not exceed 0.4.

In case the WSN supports a logistic application where sensors are used for product monitoring, the minimization of data packets loss by means of the link reliability seems to be the prime concern. This can be achieved by the introduction of ETX metric, followed by RE that takes into consideration issues related to transmission energy reduction.

In the case of WSNs supporting traffic control applications in a smart city environment e.g. for traffic light control and traffic management, the requirements are quite different from the previous case. More specifically, these applications require a high level of security along with a minimization of latency. To enhance security, the use of PFI is necessary while to reduce latency either hop count or latency routing metric can be used. The use of these two metrics in an additive manner leads to excellent performance and is preferred over their lexicographic combination since both security and low latency are equally important for this application.

Security in public areas as well as disaster management is a critical application area, where the fundamental criterion is the trust-awareness of the deployed nodes, followed by link reliability maximization. The lexicographic approach is preferred in this case because a performance metric (security) is considered of strictly higher priority to others. Hence, PFI followed by ETX and RE are recommended.

7 Conclusions

In this paper we have focused on Low power Lossy link Networks and we have proposed formulas for quantifying primary routing metrics which capture effects relevant to the considered network type and of interest to the applications they serve and we investigated their combinations. We proved that the proposed primary or composite routing metric hold all the necessary and sufficient properties for the routing protocol to converge to optimal loop-free paths. We also defined the properties that a primary routing metric has to hold so that it can be combined with other metrics to produce composite routing metrics still holding the necessary properties for the protocol to converge to optimal loop-free paths. We have additionally provided guidelines on their use for prospective system designers and implementers. The computer simulations for an LLN executing the RPL protocol and adopting the proposed routing metrics have shown that combining primary routing metrics in composite ones allows for improving more than one performance aspect. In our future work, we plan to generalize our finding in multiplicative and concave primary routing metrics and to define a transformation that leads to a derived primary metric holding the desired properties.