Interference-aware metrics impact on the performance of incremental multipath routing in WSNs

Abstract

Multipath routing has been considered in the literature to provide bandwidth aggregation for high data rate applications. Because of the phenomena of inter-path interference in wireless networks, the overall throughput is far from being the summation of the provided ones by the different paths individually. One promising solution to this problem is to make use of interference aware metrics to build multiple paths such that the inter-path interference is minimised. In this work, we are interested in assessing the impact of a set of interference aware metrics on the performance of incremental multipath routing in Wireless Sensor Networks (WSN). Incremental multipath routing builds one path per request/reply session and hence is more suitable to be combined to interference aware metrics. We review, implement and evaluate both active and passive monitoring metrics and show that for constrained networks such as WSNs, the latter are more adapted. Additionally, we show that within the passive monitoring metrics, the best one is not necessarily the most expensive to measure.

Keywords

Wireless sensor networks (WSN)iterference aware metrics multipath routing rrotocols

1. Introduction

Wireless Sensor Networks (WSN) are composed of low-cost sensor nodes characterised by their scarce resources in terms of energy, bandwidth, processing and storage means. As a consequence, WSN applications were restricted to those that generate low rate data. More recently, high data rate applications have emerged. They range from monitoring and surveillance to wild-life tracking and telemedicine services [1]. Due to the scarce resources of sensor nodes mainly and in particular to their low-rate radio modules, the available bandwidth is insufficient with respect to the requirements of high data rate applications. Multipath routing has been considered in the literature to provide bandwidth aggregation in the network. However, research results showed that the obtained bandwidth when multiple routes are used is far from being he summation of those provided individually by each path. This is due to the shared nature of the transmission medium where simultaneous use of adjacent routes especially for high rates results in significant inter-path interference. This is referred to as the route coupling problem in the literature and it affects seriously the capacity of wireless networks [2]. Efficient multipath routing protocols have to be carefully designed where both inter-path and intra-path interference have to be minimised in order to increase network throughput.

Solutions to the problem of interference based on special hardware support have been proposed by the research community. They mainly include the use of, if available, directional antennas [3,4] or multiple channels [5,6]. Location information can also help building physically separated paths with low interference as proposed in [7,8]. Even though these hardware-dependent solutions are efficient in producing non-interfering paths, they still require special hardware to be available. Moreover, localisation algorithms may incur significant overhead in terms of computational and communication complexity. As for multichannel approach, the required channel scheduling activities may introduce significant overhead that may exceed $200 μ s$ on CC2420 chipcon [9] for instance. Due to these issues, routing protocols that require special hardware support may not be cost-effective especially in dense wireless sensor networks.

One promising approach to reduce interference without any special hardware support is the design of routing protocols based on new metrics that consider the amount of interference that could be experienced by the routes to build. Interference aware routing metrics have received a keen interest in the literature of wireless mesh networks. ETX (Expected Transmission Count) [10], a popular one, characterises a link loss ratio by estimating the expected number of transmissions, including retransmissions, required to successfully deliver a unicast packet. Its computation is based on the delivery ratio of probes sent on the forward and the reverse directions of a link. In order to improve ETX metric, Expected Transmission Time (ETT) [11] considers the link data rate. Still, both ETX and ETT do not consider explicitly the effects of intra-path and inter-path interference. Based on ETX and ETT, other metrics have been proposed by the research community such as interference AWARE (iAWARE) and Interferer Neighbours Count (INX) [12]. Periodic probes exchange in ETX based metrics introduce significant overhead that limits the achievable throughput. As a result, passive monitoring metrics were developed such as Contention Aware Transmission Time (CATT) [13] and Metric for INterference and channel Diversity (MIND) [14].

Regarding multipath routing, Wu et al. [15] introduced the correlation factor metric to measure the relative degree of inter-path Independence. The correlation factor of two paths is defined as the number of links connecting two paths to each other. A DSR [16] based interference aware multipath routing is proposed using this metric. Node-disjoint paths with a small correlation factor are built while taking care of obtaining small length difference between them. DCHT (Delay-Constrained High Throughput) [17] is another multipath routing protocol based on EDGE [18] with application to video transport. In DCHT, paths construction is based on an improved method for estimating aggregate ETX for a route such that the end-to-end throughput is increased and the delay minimised.

Incremental multipath approach had also been proposed in the literature to deal with the problem of inter-path interference. An iterative path discovery is adopted where only one path is built at once [19,20]. Any other path is built by avoiding nodes surrounding already built ones in order to minimise their correlation. The iterative path discovery can be performed along with an interference aware metric. In [21], an ETX based metric is employed. Both proposals in [22] and [23] make use of a recovery tree combined to a path discovery using metrics that we consider as derived from CATT. This is also the case of the proposed protocol in [24] which however does not rely on a recovery tree.

In this paper, we assess the impact of using interference aware metrics on the performance of multipath routing protocols. We target the iterative path discovery mechanism to build multiple paths that we believe more relevant to WSN. On the one hand, it does not require neither special hardware support nor a pre-established recovery tree. On the other hand, it allows to achieve low overhead in terms of control messages required to build paths as will be shown in Section 5. In our previous work [25], we made a performance evaluation where only one interference metric is considered. In this paper we focus on the impact of five other metrics on the performance of multipath routing that adopts an incremental paths discovery. For the best of our knowledge, this is the first work that assesses the impact of interference aware metrics of the performances of multipath routing protocols. Most of the cited work compares either to a single path or to another multipath routing protocol that does not account for interference. For instance, in [17], DCHT is compared to EDGE [18] and Directed Diffusion [26]. In [24], the proposed protocol is compared to single path RPL [27] and LOADng [28]. Finally, IM2PR [22] is compared to EERP [29] and MSMRP [30] that are not interference aware.

The paper is organised as follows. The related work is reviewed in Section 2. Afterwards, in Section 3, we overview the interference aware metrics we chose to consider in our performance evaluation. Sections 4 describes two generic multipath routing protocols, object of our study. Simulation results are discussed in Section 5 before concluding the paper with some future directions.

2. Related work

Most of multipath protocols in the literature are on-demand reactive routing protocols. When a node (source) has to send data but does not have route information to the sink, it broadcasts a route request message (RREQ) toward the sink. Selected paths are sent by the sink back to the source using route reply messages (RREP). Interference aware multipath routing has generated a great deal of interest in the WSN research community. Minimum interference can be achieved through the use of an interference aware metric. The adopted metric depends on paths discovery mechanism which can be either concurrent or iterative (incremental). In concurrent multipath routing, multiple paths are built using one request/reply session while in the incremental approach, only one path is built at a time. Figure 1 summarises the interference aware multipath routing protocols detailed in what follows.

Fig. 1.

Summary of the overviewed interference aware multipath protocols.

2.1. Interference aware concurrent multipath routing

One of the first proposed metrics to characterise inter-path interference in multipath routing is the route coupling metric [34]. It describes the average number of nodes in a path that are blocked for receiving packets while a node on another path is transmitting. However, to obtain paths with minimum interference, the network connectivity graph has to be established which implies significant additional calculations especially in dense WSNs.

Wu et al. [15] introduced the correlation factor ( $CF$ ) metric to measure the relative degree of interdependence between two paths. The correlation factor of two node-disjoint paths is defined as the number of the links connecting the two paths. If there is no link between two node-disjoint paths, we say the two node-disjoint paths are unrelated. A link $(u, v)$ is said to be connecting two paths $P_{1}$ and $P_{2}$ if ( $u \in P_{1}$ and $v \in P_{2}$ ) or ( $u \in P_{2}$ and $v \in P_{1}$ ). The total correlation factor of a set of multiple paths is defined as the sum of the correlation factor of each pair of paths. A DSR [16] based interference aware multipath routing is proposed based on this metric. Node-disjoint paths with a small correlation factor are built while taking care of getting small length difference between them. To compute the correlation factor, each RREP message brings additionally neighbourhood information of the advertised route.

A similar strategy is adopted in [31] and [32]. In [31], for instance, RREQ (instead of RREP) messages are used to covey the neighbourhood information helping the sink to select routes with the least common neighbours. An issue of this piggybacking technique consists in the additional conveyed data that may produce large control overhead in dense networks. This is even more exacerbated in [15] where path selection is done by the source.

DCHT (Delay-Constrained High Throughput) [17] follows the basics of Directed Diffusion [26] with multipath extension. In order to maximise the throughput and improve the delay performance, it considers the path cost metric that consists in the product of the expected transmission count (ETX) and delay: $\begin{matrix} {Cost}_{p} = {ETX}_{p}^{α} \times {Delay}^{β} \end{matrix}$ α and β are non negative integers and ${ETX}_{p}$ is computed using: $\begin{matrix} {ETX}_{p} = \underset{i = 0}{\overset{N - 3}{Max}} (\sum_{j = i}^{i + 2} {ETX}_{j}) \end{matrix}$ where N is the number of hops in the path and ${ETX}_{j}$ is the ETX value of the jth hop. In [17], it is suggested to compute ETX based on SNR (Signal to Noise Ratio) read from each exploratory packet at intermediate nodes. The ETX of the two previous hops is considered to ensure intra-path interference. It is worth noting that the authors do not provide the method to obtain SNR measures. Their results show that DCHT applied to video streaming over WSNs obtains higher throughput than its single path counterpart (EDGE [18]). However, there was no comparison with another interference aware multipath routing protocol. One limitation of DCHT is that it considers more link quality and focuses on intra-path rather than inter-path interference in multipath routing.

2.2. Interference aware incremental multipath routing

Iterative paths discovery allows to obtain low interference between paths either by explicitly preventing nodes that may interfere with an existing path from being included in a new one or by leveraging an interference aware metric. In MR2 (Maximally Radio-disjoint Multipath Routing) [19], neighbouring nodes of an already-built path are set to passive mode where the radio can be switched off. This is twofold: energy is saved and interfering nodes are prevented from taking part in subsequent routes. Regarding interference awareness, I2MR (Interference-Minimised Multipath Routing) [20] adopts the same idea while being assisted by the availability of location information at the source and the destination nodes. In order to consider the possibility that interference range can attain twice the communication range [35], interference-zone marking can be done up to two-hop neighbours of intermediate nodes of an already built route. IAMR (Interference Aware Multipath Routing) [33] marks the shortest path nodes as well as its one-hop neighbours. Afterwards, it builds two paths surrounding the marked zone. Note that two-hop neighbours marking may increase routes hop count which may produce higher losses and more variable end-to-end delays which imply large buffer at the destination to reorder packets.

Based on ETX metric, LIEMRO (Low-Interference Energy-Efficient Multipath ROuting protocol) [21] makes use of the iterative approach to build multiple routes. A source node initiates the first path discovery by transmitting an RREQ message towards the sink node. Whenever a node receives an RREQ packet, it computes the transmission cost for every neighbouring node not included in any path from the source to the sink. Then, it broadcasts the newly estimated accumulated ETX cost if it is lower than the previous one. The active monitoring required by ETX based metrics impacts the overall achieved throughput as will be shown in Section 5. Moreover, the numerous updates in LIEMRO may consume significant computation resources that are limited in sensor nodes.

Flowing packets overhearing mechanism is also adopted by IMMR (Interference-Minimised Multipath Routing) [23]. IMMR is an interference aware extension of ZMTR [36], a multipath routing protocol targeted to ZigBee low-rate networks where multiple routes are incrementally built following the spanning tree rooted at the sink. A metric called Interference Level ( $IL$ ), measured based on the overhearing of packets (data and control) that circulate in the vicinity, is used to select the least interfering paths among discovered ones. Simulation results show that IMMR achieves better performances when compared to single and multipath routing without interference awareness.

Following a similar approach, authors of [22] build a minimum cost recovery tree and propose Interference-Minimised Multipath Routing Protocol (IM2PR). The recovery tree construction is based on a quality metric estimated using beacon messages exchange at the initialisation phase. The first path construction is triggered by an RREQ issued by the source. A node is chosen to be in this path based on a metric that counts for transmission cost (link quality) and the remaining energy. Subsequent paths are built by considering the interference level of the next node which is a measure of the number of neighbouring nodes that belong to other active paths. These neighbours are identified, once again, by leveraging the overhearing mechanism. Paths in IM2PR are built one by one even if the discovery of a new path may be done before the complete discovery of a previous path. Considering the fact that sensors have limited computation resources, the numerous required updates of the different measures to estimate links quality as well as paths interference level in IM2PR are resource consuming.

More recently, the work in [24] also adopted the iterative approach and proposed NDM (Neighbour-Disjoint Multipath). Less interfering backup paths with respect to a primary path are built based on a combined metric that includes hop count and correlation factor. The primary path is first selected as the shortest one based on hop count. Then, a set of backup paths with nodes that are not adjacent to any node of the primary path, except the source or sink, are established. Unicast and broadcast RREP messages are transmitted by the sink and are sent one after another. Unicast RREP are processed as it would have been for a traditional AODV protocol. When a broadcast RREP is received, a node checks whether it is inside the primary path or a neighbour to any node of the primary path. Accordingly, it updates the correlation and hop count metrics. Only RREPs with a better correlation metric or a lower hop count in case of equal correlation parameter are broadcast.

At this stage, it is worth noting that all the above multipath routing protocols were evaluated and compared to a single path and/or multipath routing without interference awareness.

3. Interference aware routing metrics

In this section, we overview some of the interference aware routing metrics proposed in the literature. We suggest to integrate these selected metrics to an incremental multipath protocol that will be presented in the following Section. Building subsequent paths while others are in service allows to capture the potential interference level of the former with respect to the latter by the interference aware metrics. The considered metrics are chosen based on the following criteria. First, we consider a sensor network where each node is equipped with a radio that operates using only one channel. In addition to the multi-channel cost, its integration, usually results in non isotonic metrics [14,37] which require employing a virtual network with isotonicity verified in order to be able to use Bellman-Ford or Dijkstra’s algorithms. Therefore, if a metric includes a multi-channel component, this component will not be considered in our study. Second, a selected metric has to be of a reasonable complexity to be suitable to WSN. Finally, we selected metrics that are the most representative of those of the literature.

Overall, interference aware routing can be classified into two categories, namely active and passive monitoring metrics. As opposed to the latter, the former require periodic probing messages to assess the amount of the potential interference a link may experience.

3.1. Active monitoring metrics

In this section, ETX metric in addition to two other ETX-based metrics iAWARE and INX are described.

3.1.1. ETX [10]

ETX (Expected Transmission Count) measures the link loss ratio using the expected number of transmissions, counting retransmissions, needed to successfully receive a unicast packet through a link. The path metric is the summation of each link ETX in the path and the one with the minimum metric value is selected. A node u computes the ETX of the link to a node v using the delivery ratio of probes sent on the forward ( $p_{f}$ ) and reverse ( $p_{r}$ ) directions. These delivery ratios are, respectively, the fraction of successfully received probes from u announced by v and the fraction of successfully received probes from v, at the same period. The ETX of link $l (u, v)$ is given by: $\begin{matrix} {ETX}_{l} = \frac{1}{p_{f} \times p_{r}} \end{matrix}$

ETX is bidirectional and appropriately handles asymmetry by incorporating loss ratios in both direction. Measurements on a wireless test-bed show that ETX penalises routes with more hops which have lower throughput due to interferences between different hops of the same path [10]. Although ETX does very well in homogeneous environments, it does not perform well in environments with different data rates. This is due to the small size of probes compared to typical data packets in addition to the fact that it does not consider the data rate at which the packets are transmitted. Moreover, ETX does not capture the interference experienced by the links completely since the periodic probes are sent at a slow interval (usually 1 sec) which does not reflect how busy a link is [37].

3.1.2. iAWARE [37]

The interference AWARE (iAWARE) routing metric has two components. The first component is based on the physical interference model. It uses SNR (Signal to Noise Ratio) and SINR (Signal to Interference and Noise Ratio) to continuously reproduce neighbouring interference variations. In the physical model, a communication between nodes u and v on the link $l (u, v)$ is successful if the SINR at the receiver v is above a certain threshold. The second component exploits the channel diversity to find paths with least intra-flow interference. In this work, we only consider the first component since in our network model, we assumed that only one channel is available.

iAWARE is also based on the Expected Transmission Time (ETT) metric [11] which estimates the time a data packet requires to be transmitted successfully to each neighbour. It improves upon ETX by capturing the data rate used by each link, that is: $\begin{matrix} {ETT}_{l} = {ETX}_{l} \times \frac{S}{B} \end{matrix}$ where the number of expected transmissions is multiplied by the link bandwidth giving the time required to transmit the packet. S is the size of the used packet and B is the bandwidth (raw data rate) of the link.

Being based on the physical interference model. iAWARE employs a correlation between the ratio $SINR / SNR$ and ETT, thus, capturing the effects of variation in link loss-ratio, differences in transmission rate, as well as inter-path interference in a dynamic way. iAWARE metric of link l is given as follows: $\begin{matrix} {iAWARE}_{l} = \frac{{ETT}_{l}}{{IR}_{l}} = \frac{{ETT}_{l}}{min ({IR}_{l} (u), {IR}_{l} (v))} \end{matrix}$ where ${IR}_{l}$ is the interference ratio of link $l (u, v)$ . For a node u, ${IR}_{l} (u) \in] 0, 1]$ is this node interference ratio that can computed using: $\begin{matrix} {IR}_{l} (u) = \frac{{SINR}_{l} (u)}{{SNR}_{l} (u)} \end{matrix}$ ${SNR}_{l} (u)$ and ${SINR}_{l} (u)$ are given by: $\begin{array}{l} {SNR}_{l} (u) = \frac{P_{u} (v)}{N} \\ {SINR}_{l} (u) = \frac{P_{u} (v)}{N + \sum_{w \in η (u) - v} τ (w) P_{u} (w)} \end{array}$ where $P_{u} (v)$ denotes the signal strength of a packet from node u to node v. N is the background noise. $η (u)$ denotes the set of nodes from which u can hear a packet and $τ (w)$ is the normalised rate at which node w generates traffic averaged over a period of time. $τ (w)$ is 1 when node w sends out packets at the full data rate supported.

It is worth noting that when there is no interference ${IR}_{l} = 1$ which implies that iAWARE is simply ${ETT}_{l}$ . This latter captures the link loss ratio as well as its packet transmission rate. ${ETT}_{l}$ is weighted with ${IR}_{l}$ to capture the interference experienced by the link from its neighbours. A link with low ETT and high IR will have a low iAWARE value. The lower the iAWARE of a link, the better is the link. The cumulative path metric $iAWARE (p)$ of a path p is defined as $iAWARE (p) = \sum_{l \in P} {iAWARE}_{l}$ .

iAWARE gives more importance to ETT than interference which is additionally, only considered at the physical layer. That is, iAWARE does not capture the interference at the MAC layer. Moreover, the required measurements of the SNR, the signal strength and the background noise are not easy to obtain unless a cross-layer method is employed. This results also in considering all heard packets by the routing layer of a node even if they were not intended to this node.

3.1.3. INX [12]

Interferer Neighbours Count (INX) routing metric is improved on the basis of ETX. It takes into account interference through measuring the sum of the transmission rates of the links that can interfere with the transmission on link l as: $\begin{matrix} {INX}_{l} = {ETX}_{l} \times \sum_{j \in S_{l}} r_{j} \end{matrix}$ where $r_{j}$ is the data rate of link j; it is set to the same value for all links in the network. ${ETX}_{l}$ is the expected transmission time of link l. $S_{l}$ is the set of interfering links. For a given path p, $INX (p) = \sum_{l \in p} {INX}_{l} / N$ where N is the number of links in the WSN.

3.2. Passive monitoring metrics

All active monitoring metrics overviewed in the previous section are based on ETX. Therefore, probing packets are exchanged to acquire delivery ratio of each link in both directions. Since probe messages are usually shorter than data packets, a node may experience higher losses for actual packets [10]. Moreover, the number of broadcast probes in an n-node network is $O (n)$ which causes additional overhead especially in dense networks. Due to the restricted resources of WSN, passive monitoring is desirable to help acquiring measurements without introducing extra overhead disturbing the normal operation in the network. Providing sufficiently accurate interference metric without active monitoring is challenging.

3.2.1. CATT [13]

Contention aware transmission time (CATT) takes into account the effect of interferers on the transmission time of packets over the interfered link. It depicts the intra-path and inter-path interference as well as the traffic load in a uniform way by adding up the delays of the interfering neighbour links that are one and two hops away. CATT of link l is defined as: $\begin{matrix} {CATT}_{l} = \sum_{j \in N_{l}} \frac{L_{j}}{R_{j}} \end{matrix}$ where $L_{j}$ is the packet size of link j; it is set to the same value for all packets in the network. $R_{j}$ is the data rate of link j. $N_{l}$ is the set of links (including l) whose transmission can interfere with the transmission on link l. The CATT associated to a path p is $CATT (p) = \sum_{l \in p} {CATT}_{l}$

It is worth mentioning that ${CATT}^{LD}$ , an extension of CATT metric, was also proposed in [13]. ${CATT}^{LD}$ as opposed to CATT makes use of ETX, and thus is an active monitoring metric, to include loss-dependence as follows: $\begin{matrix} {CATT}_{l}^{LD} = {ETX}_{l} \times \sum_{j \in N_{l}} \frac{L_{j}}{R_{j}} \end{matrix}$

3.2.2. MIND [14]

MIND (Metric for INterference and channel Diversity) is an interference aware routing metric that relies on passive measurements to depict interference and traffic load. Like iAWARE, it is composed of two components. One that concerns inter-path interference and the other exploits channel diversity to limit intra-path interference. When considering one channel, MIND employs the interference ratio as done in iAWARE (Section 3.1.2) to capture the experienced interference based on the physical interference model. Additionally, as the Channel Busy Time (CBT) provides a more precise way of measuring traffic load [38], CBT is also considered. That is: $\begin{matrix} MIND (p) = \sum_{l \in p} ((1 - {IR}_{l}) * τ) * {CBT}_{l} \end{matrix}$ where ${IR}_{l}$ is the interference ratio of link l (Section 3.1.2) and τ is a configurable parameter used to provide a higher weight to interference. CBT is defined by: $\begin{matrix} CBT = \frac{TotalTime - IdleTime}{TotalTime} \end{matrix}$

4. Multipath routing protocols description

The aim of this paper is not to propose yet another multipath routing protocol, only to assess the advantage the incremental discovery approach can make when integrating interference aware metrics. Instead of giving a detailed description of a specific multipath protocol, we consider two generic protocols that will be the object of the performance evaluation conducted in Section 5. The first one corresponds to the concurrent multipath routing, we call MP, in which only one request/reply session is required to build multiple paths. The second one referred to as IM2R, consists in an interference aware iterative (incremental) paths discovery where only one path is built at once. Different interference metrics (considered as path cost) are integrated to this latter in order to assess their impact on its performance.

Both MP and IM2R are on-demand reactive routing protocols. The source transmits an RREQ packet with its ID. Each intermediate node that receives an RREQ, appends its own ID before re-broadcasting the packet. This allows avoiding loops as well as selecting disjoint paths since the list of nodes that belong to each traversed path is available. RREP messages also carry the whole path information between the source and the sink. They are broadcast throughout the advertised route instead of unicast to take into account non symmetric links. In fact, the reverse path does not necessarily exist. Based on a received RREP, each intermediate node maintains a route table that indicates the path to the sink. The source maintains a similar table with multiple entries, one per built path. Finally, each node in the network has to maintain an up-to-date neighbours table. In what follows, particular behaviour of the two considered multipath protocols are described.

4.1. Concurrent paths discovery (MP)

In this approach, all routes are built based on the flooding of one RREQ. An important point to consider is RREQ strategy suppression at intermediate nodes since dropping all duplicate RREQs may reduce drastically the probability to find multiple disjoint paths. Thus, RREQ caching and rebroadcast are required in multipath routing. When an intermediate node receives a new RREQ, it records its sequence number, the source ID and the cost of the corresponding path cost from the source to this node in a path record. An RREQ is considered as a duplicate if both its sequence number and source ID have already been recorded. Only duplicate RREQs that bring higher route cost are dropped.

Upon the reception of an RREQ by the sink, a timer is set and the advertised path nodes along with the corresponding cost are recorded. On timeout, the sink selects disjoint paths with the least cost and sends back to the source an RREP per chosen path. An intermediate node that belongs to the advertised path by a received RREP, updates its routing table accordingly. Finally, upon the reception of the RREP, the source adds an entry to its routing table for the advertised path.

4.2. Interference aware metric-based incremental multipath routing (IM2R)

In IM2R, the source sends a first RREQ to build one route and transmits subsequent ones each time it receives an RREP with a new disjoint path whenever the needed number of paths is not achieved. As opposed to the concurrent approach, this requires that RREQ and RREP messages contain an additional field that gives the rank of the built path. Additionally, only one path record with the list of its nodes is maintained at the intermediate nodes.

When an intermediate node, that does not belong to another path, receives an RREQ, it checks if it is the first time it receives such RREQ. If so, the newly received path is saved with its cost and a timer is set to allow the reception of other RREQs with paths having better cost. During the timer period, subsequent RREQs are considered by the intermediate node if they convey a lower cost and the path record is updated. On timeout, an RREQ is sent using broadcast. It conveys information on the best path among those advertised by the received RREQs during the timer period.

Upon the reception of an RREQ, the sink adds the conveyed path to its paths table and sets a timer for a given period to allow considering subsequent RREQs. On timeout, the sink selects one path with the best cost metric value. An RREP that contains the elected path record is sent back to the source. When an RREP is received by an intermediate node that belongs to the advertised path, an entry is set in the routing table using the information provided by this RREP. Otherwise, the RREP is ignored. Finally, upon the reception of the RREP, the source adds an entry to its routing table. If the number of required paths is not achieved then a new RREQ is sent by the source.

In addition to the traditional hop count (HC) metric, to be interference aware, metrics defined in Section 3, namely ETX, iAWARE, INX, CATT and MIND are implemented along with the incremental multipath routing. Moreover, we also considered the metric used in DCHT presented in Section 2.1 that we refer to as ETX3 since three consecutive nodes in a path are involved in its computation. All ETX based metrics require that each entry in the neighbours table is extended to maintain for each neighbour, the number of received probes from this neighbour and those received by the neighbour from this node. In turn, iAWARE and MIND require to record additionally, the receive power from each neighbour, an estimation of its neighbours’s transmission rate as well as the interference ration (IR) of its links.

5. Simulation results

Using Castalia [39], a wireless sensor network Omnet $+ +$ based simulator, we implemented both concurrent multipath variant (MP) as well as the interference aware incremental variant (IM2R). Metrics ETX, iAWARE, INX, ETX3, CATT and MIND were implemented along with IM2R as well as hop count (HC) metric in order to assess their impact on its performance. In active monitoring metrics, probes are sent every one second and ETX value is computed every 10 seconds.

Sensor nodes are equipped with a CC2420 radio operating at 250 kbps transmitting at a power of 0 dBm which results in a transmission range of about 46.42 meters when an ideal radio mode is assumed. Nodes are deployed in a randomised grid and spaced in average 21 meters from each other which results in a mean node degree of 12. The sink and the source are placed respectively at the lower left and the upper right corners of the sensors area.

To model interference, we adopted the Additive Interference model provided by Castalia. At the MAC layer, we made use of a contention based CSMA. Each sensor node has a 32-message MAC buffer and a 16-frame radio one. In our simulations, we varied the data packet rate from 20 to 50 packets per second with a data packet payload of 64 bytes giving a useful data rate ranging from 10.24 Kb/s to 25.6 Kb/s. The transmission rate is equally assigned on the built routes. In all the performed simulations, there was no buffer overflow at the source even with the highest data rate. At least 20 simulations using different seeds are performed for each scenario.

We limit our simulations to the case of two paths even if more paths can be discovered. This is sufficient to emphasise the performances of each metric with respect to each other. Obtained results can be generalised to more paths as well as for the case of multiple sources [25]. Simulations we performed using up to three sources showed that the relative performance of the different multipath protocols is still the same regardless the number of involved sources. In what follows, unless stated otherwise, we present our simulation results based on a 400-node sensor network where the source sends 25 data packets (64-byte) per second. Simulation parameters are summarised in Table 1 where default values are highlighted in bold.

Table 1
Simulation parameters

Number of sensors 225, 324, 400, 529, 625, 729

Transmission rate 20, 25, 30, 35, 40, 45, 50 pps

Data packet payload 64 bytes

Node average degree 12

Transmission power 0 dBm

Transmission range 46.42 m (average)

Collision model Additive interference

Active monitoring metrics ETX, iAWARE, INX

Passive monitoring metrics HC, ETX3, CATT, MIND

5.1. Routing overhead versus reliability

One important issue in routing protocols and in particular multipath ones is the amount of overheard caused by the different control messages required to build and maintain routes. These messages include mainly the RREQ and RREP messages in addition to the probe messages needed to maintain neighbourhood information. In our simulations, the number of control messages is normalised by dividing their number by the number of sensors. Figure 2(a) plots the boxes that summarise the normalised number of RREQs received by the sensors in the network during the path discovery phase for MP and IM2R combined with the different implemented metrics that occur at the x-axis. Each box plot displays the distribution of the number of RREQs obtained by each protocol variant. The central box spans the interquartile range with a segment giving the median. The mean value is represented with a black square inside each box. Minimum and maximum achieved values are represented by the whiskers above and below each box.

As opposed to the incremental paths discovery, we observe that there is an implosion in the number of the exchanged RREQs in MP (concurrent discovery). There is an average of more than 250 RREQs reception per node in MP while its maximum does not exceed 50 in IM2R whatever the used metric. The very big number of RREQs in MP is due to the RREQ suppression strategy used in which a minimum number of RREQs have to be rebroadcast to allow multiple disjoint paths discovery. This problem does not exist in IM2R whatever the used metric since paths are discovered sequentially.

Figure 2(b) depicts the normalised number of received RREPs. Even though, one RREP is sent by the sink for each chosen path in all the evaluated variants, we note that their overall number varies. Regardless the used metric, IM2R produces more RREPs than MP. This is still the case when the number of built paths is increased from 2 to 6 as shown by Fig. 3(a) that plots the amount of exchanged RREPs for MP (concurrent) and IM2R combined with HC (incremental) as a function of the number of built paths. The observed higher overhead in terms of RREPs in IM2R is due to the fact that paths built by the incremental multipath routing are likely to be longer as depicted in Fig. 3(b). This results in more RREPs to be exchanged along each path from the sink to the source. We note however that with respect to the concurrent paths discovery in MP, this overhead in the incremental approach, drops from 39% of additional RREPs for two built paths to 14% when the number of paths is rised to 6.

Fig. 2.

Control messages.

Fig. 3.

Concurrent (MP) vs. incremental (IM2R) multipath routing.

Figure 4(a) brings the obtained path lengths for MP and IM2R with the seven considered metrics. Path length may give an indication on the average delay required for a packet to go from the source to a destination since delay is in part related to the path length. We can see that regardless of the used metric, IM2R produces longer paths compared to MP. This is due to the suppression strategy used to limit the number of exchanged RREQs in MP. Compared to IM2R, the sink selects the paths based on a larger number of RREQs, thus increasing the probability of selecting the shortest ones. Our simulation results show that the first selected route in MP is in average shorter than those selected first in IM2R. We can also see that interference aware metrics in IM2R produce longer paths than the hop count metric. In the former, subsequent paths are built so they are the least correlated to previous ones which results in longer paths. Nodes in the vicinity of already built paths are likely to be penalised by the interference aware metrics.

Reliability is one important aspect of any WSN application. Even if reliability is mainly a matter of the transport layer, the routing layer must still do its best. In our performance evaluation, data reliability is assessed using the percentage of data packet successfully received by the sink with respect to the total number of sent messages by the source node. Figures 4(b) and 4(c) show respectively the success ratio and the throughput achieved by MP and IM2R using the different implemented metrics. The throughput is computed using the amount of useful data (payload) received by the sink without considering the different headers of the transmitted packets. Overall, from Figs 4(b) and 4(c), two main observations can be made. First, while generating the least amount of routing overhead in terms of the number of RREQs and RREPs, passive monitoring metrics (except ETX3) and even HC allow better performances in IM2R when compared to MP. Second, we see that in terms of both success ratio and throughput, IM2R combined with active monitoring metrics exhibits poor performances when compared to MP. This is mainly due to the periodic probes used in active monitoring which consumes bandwidth. All active monitoring metrics are based on ETX that measures link quality rather than its experienced interference.

The poor performance of ETX3 when compared to other passive monitoring metrics can be explained by the fact that ETX3 deals with intra-path instead of inter-path interference. In fact, ETX3 builds the paths with the highest correlation factor. Figure 4(d) plots the correlation factor we computed off-line based on the network connectivity graph and the built paths by the different evaluated protocols. The interference range is set to a slightly higher value than the transmission range. We note that ETX3 obtains an average correlation factor that is greater than the one obtained in MP and HC i.e. IM2R without an interference aware metric. When compared to MP, active monitoring metrics achieve less performances in terms of throughput and success ratio while they build less interfering paths. Among all metrics, CATT allows to build the least correlated paths which confirms the highest performances obtained in terms of success ratio and throughput. Finally, Fig. 4(d) confirms that less correlated paths are likely to be longer (Fig. 4(a)) and hence justifying the amount of additional RREPs exchanged.

Fig. 4.

Performances in a 400-node network and a transmission rate of 25 packets per second.

5.2. Active monitoring metrics

To get more insight on the performance of active monitoring metrics when compared to each other, we performed simulations for different data transmission rates. Figure 5 plots the mean throughput achieved by IM2R using iAWARE, ETX and INX as a function of the transmission rate. We can see that ETX achieves higher throughput than iAWARE when the data transmission rate is increased and that INX outperforms both ETX and iAWARE metrics. This is mainly due to the fact that INX allows to build the least correlated paths as shown by Fig. 4(d). We can also note that iAWARE paths are less correlated than those produced with ETX. Nevertheless, the achieved throughput by iAWARE is not superior. The reason behind that is the additional overhead introduced by the technique of packet pairs [40] to estimate ETT values required by iAWARE. Furthermore, employing ETT may also lead to links quality to be overestimated [41]. Finally, iAWARE paths are more correlated than INX ones and hence iAWARE is less interference aware. This is due to the fact that iAWARE only considers interference at the physical level and does not capture interference at the MAC layer [13].

Fig. 5.

Mean throughput for active metrics as the data rate is varied.

Fig. 6.

Performances of passive metrics as the network size is varied.

5.3. Passive monitoring metrics

In what follows, we are interested in the performances of passive monitoring metrics. Figure 6(a) depicts the evolution of the success ratio for IM2R when passive monitoring metrics are employed as a function of the number of nodes ranging from 225 to 729. As can be expected, we can see that the success delivery ratio decreases with the network size. The sink and the source become more distant from each other since they are located at opposite corners. Thus, the number of transmission and failures increases since traversed routes are longer. Regardless the network size, as opposed to ETX3, we can see that MIND and CATT allow higher success ratio than the traditional HC metric. The same observations can be done following Fig. 6(b) that plots the achieved throughput by the different passive metrics.

Fig. 7.

Performances of passive metrics as the data rate is varied.

The main reason for the above observations is that paths produced by CATT and MIND are less correlated than those of HC, that is in turn less correlated when ETX3 is employed as a metric. This is confirmed by Fig. 6(c) that plots the average value of the correlation factor of the built paths as a function of the network size. IM2R routing using HC takes advantage from the overhearing property. When RREQs are broadcast to establish the following path, data packets are already flowing through the first path. Due to interference with this latter, second path RREQs are most likely to be lost in the vicinity of the first path. As a result, these RREQs have lower probability to reach the sink and hence the second path is more likely to be less interfering with the first one.

When the data transmission rate varies, we obtain almost the same behaviour for the different evaluated passive metrics. As shown by Fig. 7(a), that plots the throughput as a function of the transmission rate, CATT achieves the highest throughput. CATT is able to estimate the interference degree in the neighbourhood (up to two links away) of a path in a more accurate manner than the other metrics. MIND allows to build less interfering paths than HC since it considers how busy is the channel in the vicinity. The use of CBT instead of ETT allows MIND to build less interfering paths than iAWARE (Fig. 4(d)). ETX3 achieves the worst throughput since it considers more link quality and intra-path rather than inter-path interference. Once again, the mean correlation factor depicted in Fig. 7(b) for different loads confirms that the achieved throughput depends on the degree of correlation of built paths. In fact, CATT builds the least interfering paths while ETX3 paths are more correlated even when compared to the HC metric.

6. Conclusion

In this paper, we were interested in evaluating the impact of a set of interference aware metrics on the performance of incremental multipath routing in WSN. We first, considered traditional (concurrent) multipath routing where multiple paths are built using one request/reply session. We showed that the concurrent multipath routing introduce considerable amount of routing overhead when compared to the incremental approach. Moreover, even without interference awareness (using hop count as a metric), incremental multipath achieves higher performances in terms of both throughput and success ratio.

Naturally, incremental multipath is obviously more suitable to integrate and take benefit of interference aware metrics. We qualified these metrics either as active or passive monitoring metrics. The former require periodic probing messages to assess the amount of the potential interference a link may experience. We showed that even if active monitoring metrics are able to build less interfering paths, they still obtain poor performances in terms of throughput and success ratio. This is due to the bandwidth overhead introduced by the probe messages required to estimate ETX and/or ETT component in the corresponding metrics.

Passive monitoring metrics, except ETX3, allow to achieve better performances when compared to active ones. ETX3 considers more link quality and intra-path rather than inter-path interference. The best performance can be obtained using CATT followed by MIND. We also showed that thanks to packets overhearing, HC combined with an increment multipath is somehow interference aware and can obtain better performances when compared to traditional concurrent multipath. With respect to metric estimation complexity, we argue that CATT is once again the best candidate and is best suited for WSN in which nodes are characterised by their scarce resources.

As a future work, we expect to implement the passive metrics for experimentation on a real WSN test-bed. Moreover, we aim to achieve higher performance by leveraging channels diversity as part of the emerging IEEE 802.11.4 multichannel standards. To do so, an appropriate communication scheduling algorithm has to be designed in the context of high data rate applications.

References

L.M.

Borges,

F.J.

Velez and

A.S.

Lebres, Survey on the characterization and classification of wireless sensor network applications, IEEE Communications Surveys & Tutorials 16(4) (2014), 1860–1890. doi:10.1109/COMST.2014.2320073.

Gupta and

P.R.

Kumar, The capacity of wireless networks, IEEE Transactions on Information Theory 46(2) (2000), 388–404. doi:10.1109/18.825799.

Noguchi and

Kobayashi, Adaptive location-aware routing with directional antennas in mobile adhoc networks, in: International Conference on Computing, Networking and Communications (ICNC), IEEE, 2017, pp. 1006–1011.

Tarter,

Mottola and

G.P.

Picco, Directional antennas for convergecast in wireless sensor networks: Are they a good idea? in: International Conference on Mobile Ad Hoc and Sensor Systems (MASS), IEEE, 2016, pp. 172–182.

Liao,

Li,

Zhu,

Peng,

W.-F.

Cheng and

Dong, Path selection of reliable data delivery in wireless sensor networks, in: WASA, 2006, pp. 163–174.

Silva, A distributed algorithm to schedule TSCH links under the SINR interference model, in: VII Brazilian Symposium on Computing Systems Engineering (SBESC), IEEE, 2017, pp. 55–62. doi:10.1109/SBESC.2017.14.

Zijian,

Bulut and

B.K.

Szymanski, Energy efficient collision aware multipath routing for wireless sensor networks, in: Proceedings of the IEEE International Conference on Communications (ICC ’09), IEEE, Dresden, Germany, 2009, pp. 91–95, ISSN 1938-1883.

Bennis,

Fouchal,

Zytoune and

Aboutajdine, Carrier sense aware multipath geographic routing protocol, Wireless Communications and Mobile Computing 16(9) (2016), 1109–1123. doi:10.1002/wcm.2590.

2.4 GHz IEEE 802.15.4 / ZigBee-Ready RF Transceiver, http://www.ti.com/lit/ds/symlink/cc2420.pdf.

10.

D.S.J.

De Couto,

Aguayo,

Bicket and

Morris, A high-throughput path metric for multi-hop wireless routing, in: Proceedings of the 9th ACM International Conference on Mobile Computing and Networking (MobiCom ’03), San Diego, California, 2003.

11.

Draves,

Padhye and

Zill, Routing in multi-radio, multi-hop wireless mesh networks, in: MobiCom ’04: Proceedings of the 10th Annual International Conference on Mobile Computing and Networking, ACM, New York, NY, USA, 2004, pp. 114–128. ISBN 1-58113-868-7. doi:10.1145/1023720.1023732.

12.

Langar,

Bouabdallah and

Boutaba, Mobility-aware clustering algorithms with interference constraints in wireless mesh networks, Computer Networks 53(1) (2009), 25–44. doi:10.1016/j.comnet.2008.09.012.

13.

Genetzakis and

V.A.

Siris, A contention-aware routing metric for multi-rate multi-radio mesh networks, in: Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks (SECON ’08), IEEE, 2008, pp. 242–250.

14.

V.C.

Borges,

Pereira,

Curado and

Monteiro, Routing metric for interference and channel diversity in multi-radio wireless mesh networks, in: Ad-Hoc, Mobile and Wireless Networks, Springer, 2009, pp. 55–68. doi:10.1007/978-3-642-04383-3_5.

15.

Wu and

Harms, Performance study of a multipath routing method for wireless mobile ad hoc networks, in: Proceedings of the Ninth International Symposium in Modeling, Analysis and Simulation of Computer and Telecommunication Systems, MASCOTS ’01, IEEE Computer Society, Washington, DC, USA, 2001, pp. 99–107.

16.

D.B.

Johnson,

D.A.

Maltz and

Broch, DSR: The Dynamic Source Routing Protocol for Multi-Hop Wireless Ad Hoc Networks, Addison-Wesley, 2001, pp. 139–172, Chap. 5.

17.

Li,

Neelisetti,

Liu and

Lim, Delay-constrained high throughput protocol for multi-path transmission over wireless multimedia sensor networks, in: International Symposium on a World of Wireless, Mobile and Multimedia Networks (WOWMOM), 2008, pp. 1–8.

18.

Li,

Lim,

Kulkarni and

Liu, Edge: A routing algorithm for maximizing throughput and minimizing delay in wireless sensor networks, in: The 26th Military Communications Conference (MILCOM ’07), 2007.

19.

Maimour, Maximally radio-disjoint multipath routing for wireless multimedia sensor networks, in: Proceedings of the 4th ACM Workshop on Wireless Multimedia Networking and Performance Modeling Colocated with MSWIM ’08, Vancouver, Canada, 2008.

20.

J.-Y.

Teo,

Ha and

C.-K.

Tham, Interference-minimized multipath routing with congestion control in wireless sensor network for high-rate streaming, IEEE Trans. Mobile Comput. 7(9) (2008), 1124–1137. doi:10.1109/TMC.2008.24.

21.

Radi,

Dezfouli,

K.A.

Bakar,

S.A.

Razak and

M.A.

Nematbakhsh, Interference-aware multipath routing protocol for QoS improvement in event-driven wireless sensor networks, Tsinghua Sci. Tech 16(5) (2011), 475–490. doi:10.1016/S1007-0214(11)70067-0.

22.

Radi,

Dezfouli,

K.A.

Bakar,

S.A.

Razak and

Hwee-Pink, IM2PR: Interference-minimized multipath routing protocol for wireless sensor networks, Wireless Networks 20(7) (2014), 1807–1823. doi:10.1007/s11276-014-0710-5.

23.

Bidai and

Maimour, Interference-aware multipath routing protocol for video transmission over ZigBee wireless sensor networks, in: The 4th International Conference on Multimedia Computing and Systems, IEEE, Marrakesh, Morocco, 2014.

24.

Hossain,

C.J.

Sreenan and

R.D.P.

Alberola, Neighbour-disjoint multipath for low-power and lossy networks, ACM Transactions on Sensor Networks (TOSN) 12(3) (2016), 23. doi:10.1145/2914792.

25.

Maimour, Interference-aware multipath routing for WSNs: Overview and performance evaluation, Applied Computing and Informatics (2018), To appear, ISSN 2210-8327, https://www-sciencedirect-com.web.bisu.edu.cn/science/article/pii/S2210832717303009.

26.

Intanagonwiwat,

Govindan,

Estrin,

Heidemann and

Silva, Directed diffusion for wireless sensor networking, IEEE/ACM Transactions on Networking (TON) 11(1) (2003), 2–16, ISSN 1063-6692.

27.

Winter

et al., RPL: IPv6 routing protocol for low-power and lossy networks, RFC, 6550, RFC Editor, 2012, ISSN 2070-1721, http://www.rfc-editor.org/rfc/rfc6550.txt.

28.

Clausen,

A.C.

de Verdiere,

Yi,

Niktash,

Igarashi,

Satoh,

Herberg,

Lavenu,

Lys,

Perkins et al., The lightweight on-demand ad hoc distance-vector routing protocol-next generation (LOADng), draft-clausen-lln-loadng-09 (work in progress), 2013.

29.

Boulfekhar and

Benmohammed, A novel energy efficient and lifetime maximization routing protocol in wireless sensor networks, Wireless personal communications 72(2) (2013), 1333–1349. doi:10.1007/s11277-013-1081-4.

30.

Gao,

Yang,

Zhang and

H.-C.

Chao, Multi-path routing protocol with unavailable areas identification in wireless sensor networks, Wireless Personal Communications 60(3) (2011), 443–462. doi:10.1007/s11277-011-0301-z.

31.

Zeghilet,

Baziz,

Maimour,

Kechar and

Badache, The effects of interference on video quality over wireless s ensor networks, in: 2013 International Workshop on Communications and Sensor Networks, Vol. 21, Ontario, Canada, 2013, pp. 436–441.

32.

Ghrab,

Jemili,

Belghith and

Mosbah, Correlation-free MultiPath routing for multimedia traffic in wireless sensor networks, in: Ad-Hoc, Mobile, and Wireless Networks. ADHOC-NOW 2017,

Puliafito,

Bruneo,

Distefano and

Longo, eds, Lecture Notes in Computer Science, Vol. 10517, Springer, 2017.

33.

Wang and

Zhang, Interference aware multipath routing protocol for wireless sensor networks, in: GLOBECOM Workshops (GC Wkshps), 2010, IEEE, 2010, pp. 1696–1700. doi:10.1109/GLOCOMW.2010.5700229.

34.

M.R.

Pearlman,

Z.J.

Haas,

Sholander and

S.S.

Tabrizi, On the impact of alternate path routing for load balancing in mobile ad hoc networks, in: Mobile and Ad Hoc Networking and Computing, 2000. MobiHOC. 2000 First Annual Workshop on, IEEE, 2000, pp. 3–10.

35.

Zhou,

He,

Krishnamurthy and

J.A.

Stankovic, Impact of radio irregularity on wireless sensor networks, in: Proceedings of the 2nd International Conference on Mobile Systems, Applications, and Services, ACM, 2004, pp. 125–138.

36.

Bidai,

Haffaf and

Maimour, Node disjoint multi-path routing for ZigBee cluster-tree wireless sensor networks, in: International Conference on Multimedia Computing and Systems (ICMCS), 2011, pp. 1–6.

37.

A.P.

Subramanian,

M.M.

Buddhikot and

Miller, Interference aware routing in multi-radio wireless mesh networks, in: Wireless Mesh Networks, 2006. WiMesh 2006. 2nd IEEE Workshop on, IEEE, 2006, pp. 55–63.

38.

Wu and

T.-C.

Chiueh, Passive and accurate traffic load estimation for infrastructure-mode wireless lan, in: Proceedings of the 10th ACM Symposium on Modeling, Analysis, and Simulation of Wireless and Mobile Systems, ACM, 2007, pp. 109–116.

39.

Castalia Network Simulator , 2011, last accessed 2016-10-10, castalia.forge.nicta.com.au/.

40.

Keshav, A Control-Theoretic Approach to Flow Control, Vol. 21, ACM, 1991.

41.

V.C.M.

Borges,

Curado and

Monteiro, The impact of interference-aware routing metrics on video streaming in wireless mesh networks, Ad Hoc Networks 9(4) (2011), 652–661, Multimedia Ad Hoc and Sensor Networks, ISSN 1570-8705.

Number of sensors	225, 324, 400, 529, 625, 729
Transmission rate	20, 25, 30, 35, 40, 45, 50 pps
Data packet payload	64 bytes
Node average degree	12
Transmission power	0 dBm
Transmission range	46.42 m (average)
Collision model	Additive interference
Active monitoring metrics	ETX, iAWARE, INX
Passive monitoring metrics	HC, ETX3, CATT, MIND