Interference-aware multipath routing for WSNs: overview and performance evaluation

In the last decade, Wireless Sensor Networks (WSN) have undergone remarkable development and their applications are foreseen to experience a significant growth in the near future. WSN are constrained networks with very limited resources, as a result, they were traditionally targeted to relatively low rate event-driven applications where a limited amount of data is transferred from a sensor to the sink. In these applications, the required data rate is less than tens of kilo-bits per second. However a class of WSN applications that require high data rate reporting like Wireless Multimedia Sensor Networks (WMSN) has emerged. Intensive traffic loads generated by such applications are prone to losses and network congestion. Due to the resource limitations and especially the low-power and low-rate radios used by sensor nodes, the available throughput is insufficient. Therefore, hardware and software solutions are necessary to provide sufficient bandwidth for supporting high data rate applications in WSNs.

With regard to such applications, routing protocols need to exploit the high density of WSN to raise the network capacity by involving more nodes using multiple paths. In fact, multipath routing is considered as a good alternative to single path routing since it allows bandwidth aggregation. However, the broadcast nature of radio propagation impedes achieving these goals in the context of high data rate applications. Simultaneous utilisation of adjacent paths with high rates results in intensive interpath interference, which increases the probability of packet collision at the nodes along the active paths. In the literature, this is known as the route coupling problem and it seriously affects the capacity of wireless networks. This problem is further exacerbated when the wireless network becomes large in size. This issue imposes a big challenge in designing efficient multipath routing protocols. A set of maximally zone-disjoint shortest paths that minimise both interpath and intrapath interference need to be discovered and used for load balancing to increase throughput.

In order to deal with the problem of interference in multipath routing, solutions that make use of special hardware support have been proposed [18,19,12]. When such specific hardware facilities are costly or simply not available, there were basically two main approaches in the literature to minimise interference. The first one consists in the use of an interference-aware metric [15,27] while the second one adopts iterative path discovery where only one path is built at once [17,25,20]. A subsequent path is built by avoiding nodes that are in the vicinity of already built ones.

In this paper, we focus on the iterative path discovery mechanism to build multiple paths that we argue more suitable to WSN. On the one hand, it does not require special hardware support. On the other hand, it can avoid complex metric estimation that is resource demanding either in the metric computation itself or in the amount of required periodic probe messages. The purpose of this work is not to propose yet another multipath protocol but to assess the benefit of the iterative approach to build paths against the traditional concurrent multipath routing. Rather than providing a detailed design and analysis of a specific multipath protocol, we study three generic protocols, one that corresponds to a traditional multipath routing in which only one request/reply session is performed. The other two evaluated protocols make use of the iterative path discovery strategy.

The paper is organised as follows. Section 2 overviews main approaches used to deal with interference in multipath routing. Then, in Section 3, three different multipath routing protocols are described. These protocols, combined or not to an interference-aware metric, have been the subject of extensive simulations. The main obtained results are presented in Section 4. Section 5 concludes the paper with some future directions.

Building an interference-free routing topology in a WSN is not a trivial task. There have been in the literature, several proposals dealing with the interference problem in the context of routing protocols especially multipath ones. Basically, interference aware multipath routing can be split into three main classes. The first class benefits from the support of special hardware, the second one is based on metrics that reflect the level of interference of a path and the third one implements an iterative paths discovery mechanism. In this section, we give an overview of the most important interference aware multipath routing protocols following the above classification as well as those that can fit into more than one of the mentioned three classes.

In this category of multipath routing, a special hardware is used to get rid of interference. Minimal interference between paths can be achieved using directional antennas where the transmission beam of a node can be set in a particular direction. In [22], a zone-disjoint shortest multipath routing algorithm is proposed where directional antennas are used to select maximally disjoint paths. However, the use of directional antennas in convergecast, the main communication pattern in WSN, may not provide the expected performances [24].

When multiple channels are available, interference can be minimised through an appropriate selection of orthogonal channels. As a result, the capacity of the network is improved as more links can operate simultaneously using non overlapping channels [23]. [16] made use of the multi-frequency characteristic of CC2420 radio and proposed IEMM-FA to minimise interference and energy consumption of multiple paths in WSN.

Using location information, geographic routing allows the construction of physically separated paths that minimise interpath interference. Energy-Efficient and Collision-Aware Multipath Routing Protocol (EECA) [12] is a multipath routing protocol that uses the location information of all the sensor nodes to establish two paths in both sides of the direct line between the source-destination pair. Directional geographical routing (DGR) [6] is a geographical interference-aware routing protocol which constructs two non-interfering paths based on the angle deviation method.

Despite the efficiency of these solutions to construct non-interfering paths, they still require special hardware support to be used. Localisation algorithms may impose significant overhead in terms of communication and computational complexity. Multichannel approach, although quite suitable for mesh networks, is not suitable for WSN with high data rates. These latter require a channel scheduling strategy that may introduce significant overhead of about $200$μs on CC2420 chipcon [1]. Due to these issues, hardware-dependent routing may not be cost-effective in low-cost wireless sensor nodes especially in dense networks.

One approach to reduce interference is the design of routing protocols with new metrics that integrate the amount of interference that could be experienced by the built paths. One popular metric is ETX (Expected Transmission Count) [7]. ETX characterises the link loss ratio using the expected number of transmissions, including retransmissions, needed to successfully deliver a unicast packet across a link. Expected Transmission Time (ETT) [8] improves upon ETX by capturing the data rate used by each link. However, ETX and ETT do not explicitly consider the effects of intra-flow and inter-flow interference.

Based on ETX and ETT metrics, several metrics have been proposed in the literature such as interferer neighbours count (INX) [9]. The authors in [14] present an improved method for computing aggregate ETX for a path that increases end-to-end throughput and minimises delay. They propose EDGE, a greedy algorithm based on directed diffusion that reinforces routes with high link quality using this metric. DCHT [15] is a multipath extension of EDGE with application to video transport. However, DCHT only considers intrapath interference and does not take into account interpath one. Furthermore, ETX based metrics use probing packets to acquire delivery ratio which introduces overhead.

The correlation factor [27] of two (or more) paths is defined as the number of links connecting these paths to each other. Based on this metric, a DSR based decoupled multipath scheme is proposed in [28]. Node-disjoint paths are built so a small correlation factor is obtained while caring to get small length difference between them. To compute the correlation factor, each route reply (RREP) message carries not only the information of a newly discovered path, but also the neighbourhood information of this path.

Piggybacking neighbourhood information on control messages that serve route discovery is also adopted in [29]. Instead of RREP messages, route request (RREQ) messages are used to convey neighbourhood information. Based on these latter, the sink selects paths with the least common neighbours so nodes that are in the neighbourhood of a chosen path are prevented from being used in other paths. The main concern about this approach is that topology reporting through route discovery messages may cause high control overhead in large and dense networks especially in [27] where the source is in charge of path selection.

In order to build physically separated paths, in this category of multipath routing protocols, nodes that may interfere with a given path are eliminated. Using an iterative path discovery, one single path is built then surrounding nodes are prevented from taking part in subsequent route discovery phases. MR2 (Maximally Radio-disjoint multipath Routing) [17] makes use of this approach where neighbouring nodes are put in a passive mode where the radio can be switched off allowing energy saving. With respect to interference awareness, I2MR (Interference-minimised multipath routing) [25] follows the same principle with the availability of location information at both the source and the destination.

Interference-zone marking can be done up to two-hop neighbours of intermediate nodes of existing paths. This is done to consider the fact that the interference range can reach twice the communication range. This is the case of IAMR (Interference aware multipath routing) [26] where the shortest path as well as its one-hop neighbourhood is marked. Then, two paths surrounding the marked area are built. It is worth noting that two-hop neighbours marking may increase the hop count of built paths which may result in more losses and large buffer at the sink to reorder packets.

Using an ETX-based cost metric, LIEMRO (Low Interference Energy Efficient Multipath Routing Protocol) [20] adopts the iterative approach to discover multiple paths. To avoid interference, LIEMRO makes use of flowing packets overhearing mechanism to eliminate paths with higher interference. This mechanism is also used in IMMR (Interference Minimised Multipath Routing) [4]. Multiple paths are used incrementally based on an already established spanning tree rooted at the sink. The first path consists in the tree path that follows the child-parent link. Subsequent paths are discovered based on a metric called Interference Level (IL) for which the estimation is based on the overhearing of data or explore packets that circulate in the vicinity.

Like IMMR, IM2PR (Interference-Minimised Multipath Routing Protocol) [21] makes use of a minimum cost recovery tree. The first path construction is initiated by sending an RREQ by the source following the tree structure. Subsequent RREQs to build additional paths are delayed in order to assess their interference degree with already built ones. A node is chosen to be in a path depending on the number of its neighbours that are in the other active paths. More recently, the iterative approach is adopted by [11,3]. In the former, hop count and correlation metrics are combined to build less interfering backup paths with respect to a primary path. In the latter, paths are built using location information and the banish state, equivalent to the passive mode in MR2 [17]. A metric called the number of common neighbours is introduced to reduce the number of banished nodes.

In the remainder of this paper, we mainly focus on the class of multipath protocols that adopt the iterative paths discovery. Their main advantage is that they do not require periodic messages in order to estimate complicated metrics that often become expensive to compute for a sensor node as it is the case of metric-based approaches [21]. This is not suitable to WSN characterised by their scarce energy and limited processing capabilities. In fact, most of these metrics are targeted to mesh networks where these limitations do not hold. Nevertheless, we consider in our performance evaluation the CATT (Contention Aware Transmission Time) metric that does not require costly probes to measure the number of interfering neighbours of a link l defined as [9]:

where $Lj$ is the packet size of link $j,Rj$ is the data rate of link j and N_l is the set of links (including l) whose transmission can interfere with transmissions on link l. When applied to multipath routing where both data transmission and packet size are the same in the different path flows, CATT simply counts the number of interfering nodes from other paths. This is the case of works in [21,11].

In what follows, we summarise the multipath routing protocols with and without interference awareness that will be the object of the performance evaluation conducted in Section 4. The first protocol consists in a traditional multipath routing, referred to as MP, in which only one request/reply session is performed and multiple paths are built at once. The second one consists in an iterative (incremental) approach, referred to as INC where only one path is built at once. The third protocol is a modified version of MR2 [17] referred to as M2R2 where nodes surrounding an already built path are put in a passive mode.

The three chosen multipath protocols are on-demand reactive routing protocols where the source willing to send data triggers route requests in order to find paths to the sink. The selected paths are sent to the source by the sink using route reply messages. When the source has data packets to send but does not have the route information to the sink, it transmits an RREQ packet that contains the source ID. When a node other than the sink receives an RREQ, it appends its ID to the list of traversed nodes before re-broadcasting the packet. This technique is called path accumulation in [10] and allows the selection of disjoint paths as well as route loops avoidance. RREPs also carry the whole path information between the source and the destination and are broadcast throughout the advertised path instead of being unicast in order to consider non symmetric links since the reverse path does not necessarily exist. Based on received RREPs, each intermediate node maintains a route table with one entry that indicates the path to the sink. The source maintains the same table but with multiple entries, one per discovered path. Each entry of the route table contains the following:

• • the path ID, that corresponds to the ID of the first traversed sensor in this path from the source to the sink;

• • the ID of the next hop toward the sink on this path;

• • an estimation of the associated quality metric for this path.

Finally, each sensor is assumed to maintain an up-to-date neighbours table built upon initialisation of the network and updated periodically to adapt to network dynamics. This table is refreshed by any received control or data packet. If a neighbour has not been refreshed for a timeout value, it is obsolete and erased from the table. In the remainder of this section, we describe the particular behaviour of each multipath routing protocol considered in our study.

In concurrent paths discovery, all paths are built using one RREQ flooding. The most important issue in this approach is whether a given RREQ is to be rebroadcast or dropped by an intermediate node. In fact, it appears that when dropping all duplicate packets (same source address and same sequence number), the probability to find node-disjoint paths is almost zero since generated paths are mostly overlapped. In [13], the authors propose to forward duplicate packets that traversed through a different incoming link than the link from which the first RREQ is received, and whose hop count is not larger than that of the first received RREQ. In [27], RREQ messages are cached at intermediate nodes. When a node receives a route query message, if received for the first time or the path included in this query message is node-disjoint with the paths included in previously cached path records, then the node will cache and broadcast it again.

Even if both described methods increase the flooding cost, RREQ caching and rebroadcast are required to allow the construction of node-disjoint routes. In MP, we adopt another RREQ caching and suppression strategy. On the reception of a new RREQ, an intermediate node records its sequence number, the corresponding path ID and the cost of this path from the source until this node in a path record. An RREQ is considered as a duplicate (as opposed to a new one) if both its sequence number and path ID have already been recorded. A duplicate RREQ is simply discarded if it carries a bigger path cost; otherwise it is rebroadcast and the corresponding path record is updated with the new cost. Our suppression strategy generates less RREQs than the one adopted in [13]. With respect to [27], more RREQs are broadcast but more node-disjoint paths can be discovered with less storage capabilities at intermediate nodes.

When the sink receives a route request, it sets a timer. Each time it receives an RREQ, it records the conveyed path nodes along with the corresponding cost. On timeout, the sink chooses the required number of disjoint paths with the least cost. Afterwards, an RREP per selected path is sent back to the source. On the reception of an RREP, an intermediate node that belongs to this RREP path sets its routing entry. Finally, when the RREP reaches the source, an entry is added to its routing table.

In the iterative paths discovery approach, the source sends its first RREQ to build one path and sends subsequent ones each time it receives an RREP with a new disjoint path until the required number of paths is achieved. Compared with the concurrent approach, this requires that the RREQ/RREP messages contain an additional field that records the sequence of the built path. Additionally, as opposed to MP, only one path record is maintained at intermediate nodes. However, all the path nodes are cached instead of only the path ID. When an intermediate node receives an RREQ for the first time, it caches the newly received path and sets a timer to allow the reception of other RREQs. During the timer period, only RREQs that convey a lower cost are considered and the path record is updated accordingly. On timeout, an RREQ is broadcast with the best path among those carried by the received RREQs during the timer period.

Every time the sink receives a request, it records it in its paths table and sets a timer for a given period. On timeout, the sink proceeds to the selection of one path with the best metric value. An RREP with the chosen path record is sent toward the source. RREPs are processed by intermediate nodes and the source as in the concurrent strategy with one difference it that the source can initiate another path discovery phase if the required number of paths is not reached.

M2R2 is a modified version of MR2 [17] where RREQs transmission is initiated by the source instead of the sink. Compared to INC, M2R2 operates in the same way except that nodes that are in the transmission range of the advertised path nodes have to switch to a passive mode. This is triggered by the reception of an RREP. This is another difference with MR2 where a dedicated message is used for this purpose. In fact, in M2R2, a node is able to know if it is a neighbour of a given path by checking the path field of the received RREP and its own neighbours table. Note that neighbours of the sink or the source cannot switch to passive mode to allow multiple paths discovery.

Passive nodes are prevented from taking part in the route discovery process. Any received control message (RREQ or RREP) is ignored. In order to save energy, passive nodes can simply be put in a sleep state where the radio is switched off or configured with a low duty cycle depending on the application requirements. Only one-hop neighbours are put in passive mode. Doing so for two-hop neighbours may result in longer paths that are prone to more losses. Moreover, the sink needs to maintain large reception buffers to reorder packets.

We implemented MP, INC and M2R2 using Castalia [5], an Omnet++ based simulator for WSNs. We implemented the hop count (HC) metric for the three protocols and the CATT metric only for INC and M2R2 protocols. As it is the case of most interference-aware metrics, CATT is designed to assess interference that results from other existing flows making it not suitable to the concurrent path discovery.

Each sensor is equipped with a CC2420 radio that operates at 250 Kbps. To model interference, we adopt the additive interference model provided by Castalia along with a contention based CSMA MAC layer. Sensors are deployed in a randomised grid where the source and the sink are located respectively at the upper right and the lower left corners of the simulation area. To examine the effect of network topology on the different solutions, we consider both fixed zone area with variable number of nodes and fixed average density with variable zone dimensions. In all the performed simulations, there were no buffer overflow at the source. Each scenario is simulated several times using different simulation seeds until at least 20 successful simulations are obtained. A simulation is considered as successful if the required number of paths per source is actually built. Simulation parameters are summed up by Table 1.

Unless stated otherwise, we report on our simulation results performed with 400 nodes where the source transmits 64-byte data packets at a rate of 30 packets per second (pps) using two paths. The transmission rate is equally distributed on the paths. The obtained results and lessons learnt from 2-path experiments can be generalised to more paths as will be confirmed in Sections 4.4 and 4.5. When results are provided using box plots. Each box displays the distribution of a given metric. The central rectangle spans the first quartile to the third quartile (the interquartile range). A segment and a small black square inside each rectangle shows the median and the mean values respectively. The whiskers above and below the box show the minimum and maximum achieved values.

In our study, data reliability is assessed using the percentage of data packets successfully received by the sink. Figure 1a shows success ratio distribution for each protocol with three boxes that result from experiments using (left to right) high, intermediate and low network densities that correspond respectively to an average node degree of 20, 12 and 8. The mean degree is decreased by increasing the mean distance between nodes in the randomised grid and thus increasing the sensors area while preserving the total number of sensor nodes.

Independently of the route discovery mechanism, we observe that denser networks provide better performances. This can be explained by the fact that in a denser network, the built paths are shorter in terms of the number of traversed nodes. Figure 1b shows that the path length increases when the network density decreases since the sensor area becomes larger. When the number of traversed nodes increases, loss probability increases. We can also see, independently of the network density, that the iterative paths discovery (INC and M2R2) exhibits better performances than the concurrent approach (MP). For both implemented metrics, M2R2 provides the best success ratios. CATT allows better success ratio in average but can result in less performances when combined with INC. The minimum success ratio can drop as low as the one obtained in MP. This is due to the fact that CATT tends to build longer paths as can be confirmed by Figure 1b. CATT favours nodes with less potential interfering links in the vicinity at the expense of increasing path lengths.

Figure 2 brings the obtained path lengths averaged on all network densities. Path length can be used to evaluate average delay required for a packet to reach its destination. Delay is largely related to the number of traversed links. Regardless of the used metric, both INC and M2R2 produce longer paths compared to MP. In M2R2, excluding nodes surrounding already built paths makes subsequent paths even longer than those generated by INC. CATT produces longer paths than HC. MP builds the shortest paths because of its RREQs suppression strategy: the sink selects the paths based on a larger number of RREQs which increases the probability of selecting the shortest ones. Our simulation results show that the first chosen path in MP is in average shorter than those selected first in INC and M2R2.

Figure 3 shows the achieved throughput computed using the amount of useful data (payload) received by the sink. The shown results confirm the ones obtained in terms of success ratio. In average, MP achieves the smallest throughput, about 9 Kbps, whereas the four other protocols achieve higher values with more than 11 Kbps for M2R2-CATT for instance. Using our default settings, the maximum achievable throughput is 15.36 Kbps. In order to assess more precisely the behaviour of each protocol with respect to interference, Figure 4 plots the percentage of packets failed to be received due to interference with respect to the total number of transmitted packets by the source and intermediate nodes. We can note that MP generates more failures while M2R2 suffers from less interference compared to INC. With respect to the used metric, CATT produces less interference than HC.

Failures due to interference are mainly caused by paths that are close to each other. This can be evaluated using a metric such as the correlation factor [28] defined as the number of the links connecting the built paths. A link $(u,v)$ is said to be connecting two paths $P1$ and $P2$ if $u∈P1$ and $v∈P2$ or $u∈P2$ and $v∈P1$⁠. Figure 5 plots the correlation factor that we computed off-line based on the network connectivity graph and the built paths. The interference range is set to a slightly greater value than the transmission range. We see that the built paths in MP and INC are the most correlated compared to the three other protocols. Paths built by M2R2, however, are the less correlated and often present a near zero correlation factor.

Compared to single path routing protocols, path discovery is more challenging in multipath routing protocols. In order to evaluate the efficiency of a multipath routing protocol, one has to consider the amount of required overhead incurred by the different control messages such as RREQ and RREP as well as the potential hello messages to maintain neighbourhood information. Figure 6a plots the normalised number of RREQs received by the different sensors in the path discovery phase. RREQs number is divided by the number of nodes in the network. We see that, as opposed to the iterative paths discovery, there is an implosion of the number of the exchanged RREQs in MP. Their average number rises to 300 processed RREQs per node in MP while it does not exceed 30 in other protocols. The huge number of exchanged RREQs in MP is inherent to the RREQ suppression strategy used in which a minimum of RREQs have to be forwarded; otherwise the probability to find disjoint paths is dramatically reduced. This problem does not exist in the iterative discovery approach since paths are discovered sequentially. The least number of RREQs is obtained in M2R2 where nodes are put in passive mode and hence do not receive or process any RREQ.

Figure 6b shows the normalised number of received RREPs. Recall that for each protocol, there is one RREP sent by the sink for each chosen path. However, we note that there is some differences in the number of the overall number of exchanged RREPs. The passive mode strategy allows M2R2 to generate the smallest number of RREPs. INC produces more RREPs than M2R2 and MP. With respect to MP, INC paths are longer (Figure 2) which produces more RREPs to be forwarded by intermediate nodes back to the source.

Energy efficiency should be one of the major design goals of any routing protocol in WSN. Figure 7 shows the amount of consumed energy. The amount of consumed energy using MP and INC is the same (about 34 J) during the entire simulation duration (500 s). In the Castalia energy model, when the radio is on, the consumed energy is the same whatever the number of sent and received messages by a given node. When the radio is put in a sleep mode, as done in M2R2 for nodes surrounding built paths, the consumed energy is reduced. When the network is dense, the number of nodes in passive mode increases. The number of nodes in the transmission range of those that compose a given path is larger. This explains why less energy is consumed in a denser network. As a result, M2R2 allows higher lifetime to the sensor network.

Figure 8a shows the evolution of the success ratio when the number of sensor nodes is varied. Once again, MP provides the least success ratio while M2R2 exhibits the best performances. The INC routing allows better results with respect to MP since its paths are less correlated as depicted by Figure 8b. The rational behind is that when RREQs are sent to build the second path, data packets are already flowing through the first one. Thus, RREQs are likely to be lost in the vicinity of this latter due to interference. As a result, INC routing takes advantage from the overhearing property of the wireless media. This is even more true when an interference aware metric such as CATT is used. In fact, CATT counts for data packets that already flows through active paths.

Moreover, we notice in Figure 8a that the performances of M2R2 using either HC or CATT are almost the same. This means that the interference-zone marking strategy of M2R2 is a good mean to avoid interference and that an interference-aware metric is not necessary required. As shown in Figure 8b, M2R2 builds the least correlated paths where the correlation factor is close to zero and almost constant when the network size increases. Finally, We observe that the success ratio decreases when the number of nodes increases. This is due to the fact that the source and the sink become more distant from each other since they are placed at opposite corners of the network area. As a result, built paths become longer which increases the number of transmission and thus the number of transmission failures.

Figure 9 plots the number of packets failed to be received due to interference with respect to the overall number of sent packets by the source and intermediate nodes. M2R2 presents the least number of failures that is almost the same whatever metric is used. CATT metrics however allows to reduce failures in INC. MP generates the highest failures where up to 11% of sent messages are lost due to interference. Finally, we can observe that this number decreases when the network size increases or equivalently the built paths are longer. This can be explained by the fact that when paths are longer, the number of packets to be sent as we approach the sink is smaller. Losses experienced at previous hops decreases the transmission rate at subsequent nodes in the path and at the same time decreases the number of transmission failures due to interference.

Figure 10a plots the average ratio of RREQs received by the sensor nodes in INC and M2R2 with respect to MP during the path discovery phase as function of the network size. The ratio of processed RREQs in both INC and M2R2 decreases when the number of nodes in the network increases. At most, INC routing generates 9% of the amount of RREQs generated by MP. This ratio drops to 6.5% in M2R2. Similarly, Figure 10b plots the average ratio of received RREPs. M2R2, once again, produces the least RREPs overhead thanks to the passive mode. INC produces more RREPs than MP since INC paths are longer. As a summary, M2R2 incurs the least overhead compared to INC and MP in terms of both RREQs and RREPs.

Figure 11a plots the achieved success ratio when increasing packets payload. We observe that the ratio of successfully received packets by the sink decreases as the packets payload increases. This is due to the fact that larger packets are more likely to produce interference. This is confirmed by Figure 11b that plots the ratio of failed transmissions. Additionally, it confirms the correlation between the success ratio achieved and the amount of failures due to interference. M2R2 protocol allows more successful transmissions whatever the used metric while MP exhibits the poorest performances. We observe that INC-HC may behave better than INC-CATT when the size of transmitted packets increases. In fact, packets are transmitted on the first path when the second one discovery is in progress. The related RREQs experience more losses due to interference with first path data packets. These losses are more likely to appear in the vicinity of the first path, already in use. The same behaviour is also observed when the transmission rate increases as will be seen in the following section.

When the data transmission rate is varied, we obtain almost the same behaviour for the five evaluated protocols. As shown by Figure 12a, M2R2 achieves the highest success ratios and MP the lowest ones. As can be expected, the ratio of successfully received packets decreases when the data rate increases since the number of failures due to interference increases as depicted in Figure 12b. Moreover, INC-HC can achieve the same performances as INC-CATT when rising the data rate. A high transmission rate on the first path rises the number of failures due to interference during the discovery of the second path. RREQs related to less correlated paths are more likely to achieve the sink. In terms of achieved throughput as depicted in Figure 12c, M2R2 achieves the best performances while MP the worst ones. The throughput achieves its maximum when the transmission rate is set to 40 pps. Then, it decreases with the transmission rate. This means that rate adjusting through a transport level congestion control is critical to achieve optimal performances. In terms of achievable throughput, CATT obtains higher performances than the HC metric in both M2R2 and INC protocols.

Here, we are concerned with the potential performance enhancement of the simulated multipath protocols with two and three paths compared to a single path routing. Figure 13a shows the mean gain obtained in terms of success ratio when two paths are used. We observe that the improvement increases when the network size is bigger or equivalently when the path length between the source and the sink increases. The success ratio decreases with the network size and thus the improvement is more important since the number of traversed nodes is larger. Looking at the performances of each of the considered protocols, we see that almost, no improvement is achieved in MP when two paths are employed instead of one. With respect to single path routing, multipath protocols that consider interpath interference using either an interference metric such as INC-CATT or using a zone marking strategy such as the one employed in M2R2, achieve better performances. In INC-CATT, the additional success ratio ranges from 5% to 25% with two paths compared to one path. In M2R2, higher improvement can be obtained with up to 45% additional success ratio.

Figure 13b shows the improvement when three paths are used instead of only one path. We can make same observations while noting that, in most cases, we achieve higher improvement with three paths. Figure 14 plots the distribution of the achieved improvement in terms of success ratio for a 900-node network. For each protocol, the first and the second box summarise the improvement using respectively two and three paths over single path routing. We can see that interference-aware protocols (INC-CATT, M2R2-HC and M2R2-CATT) allow better success ratio using multiple paths over single path routing and this is for all the performed simulations. In half of them, INC-CATT allows about 25% and more than 30% improvement with two and three paths respectively. M2R2 achieves up to 70% improvement and more than 35% improvement in half of the experiments. The improvement in MP-HC and INC-HC is less obvious. In MP, near the half of experiments with two paths achieves lower success ratio than single path routing. Even with three paths, only a quarter of performed simulations allows more than 20% improvement and the maximum achieved improvement is about 25%. Compared to MP, INC-HC allows better performances since it may take advantage of overhearing. It achieves up to 45% improvement with three paths.

Table 2 summarises the obtained results using a representative topology with default settings when four paths are built. It gives the mean values for success ratio, path length and the percentage of failures due to interference. With single path routing, a success ratio of about 60.52% is achieved. Our results show that using two or three paths with MP, there is no improvement over single-path routing. Four paths are needed to achieve slightly higher performances (60.71%). Similar but slightly higher performances are obtained in INC-HC where three paths are required to outperform single path routing. When the interference-aware metric CATT is used by INC, the built paths are less correlated and the success ratio reaches 77.44%. Even with two paths, an additional success ratio of about 10% can be obtained. With three paths, this achieves about 17% of additional success. With only two paths, For both HC and CATT, M2R2 allows 12% additional success ratio than the single path routing protocol. When the number of built paths is risen to four, the improvement is more significant with more than 49% of additional success in M2R2-HC. We observed that the success ratio is higher using HC in M2R2 when the number of paths exceeds two. As already emphasised, the CATT metric is likely to build longer paths which increases the probability of losses. The mean path length in M2R2-CATT with four path is about 16 while it is about 15.25 in M2R2-HC.

In order to assess the ability of each protocol to handle multiple sources, simulations were performed with 2, 3 and 4 sources. We considered the worst case where all of them are located near each other in the upper right of the sensor field. Each source has to transmit data packets using at least two paths. We generated topologies with a mean degree of 12. 200 simulations are performed for each protocol and the number of successful ones as well as the corresponding percentage are reported in Table 3. As can be expected, M2R2 exhibits the least successful number of simulations that drops to 5% when the number of sources is raised to 4. This issue can be solved by allowing some passive nodes to take part in routing other sources data. Based on the nature of flows, a best trade-off has to be found between handling more flows in the network and their achievable performances. MP succeeds in handling more sources since there is no constraint in building paths except paths disjointness. Due to the iterative nature of INC, more RREQ/RREP losses are experienced which reduces the number of built paths for the considered sources.

Figure 15 presents the mean success ratio in the presence of respectively one, two and three sources. We can see that their relative performances are the same whatever the number of the sources is. M2R2 and MP exhibit respectively the highest and the lowest success ratios. When increasing the number of the sources, the success ratio decreases for all protocols. However, as shown by the plots, it fastly decreases in MP compared to INC and M2R2. With three sources, the achieved success ratio is about 34% of the one obtained when only one source is transmitting in MP while it is 40% and 57% in INC-CATT and M2R2-HC respectively.

Multipath routing holds a great potential to provide sufficient bandwidth to high data rate applications. To achieve this aim, a multipath routing protocol has to be carefully designed and the problem of interpath as well as intrapath interference have to be considered. In this paper, we focused on the performance evaluation of the iterative paths discovery approach as opposed to the traditional concurrent multipath routing. Five different variants of multipath protocols were simulated and evaluated using different performance metrics. We mainly showed that the iterative approach allows better performances when used jointly with an interference-aware metric such as CATT or when an interference-zone marking strategy is employed. This latter, used in M2R2, appears to exhibit the best performances in terms of success ratio, achieved throughput, control messages overhead as well as energy consumption at the expense of the number of flows that can be handled simultaneously.

The obtained performances can be further improved when the interference-aware multipath routing is jointly used with an appropriate transport protocol to control the source transmission rate. We plan to implement other interference-aware metrics than CATT for both the iterative paths discovery as well as the concurrent multipath routing. In the latter case, a metric such as route coupling [27] is more suitable and will be considered in our future work. Finally, we plan to make real test-bed performance evaluation using IoT-LAB [2] in order to consider more realistic application environment.

Publishers note: The publisher wishes to inform readers that the article “Interference-aware multipath routing for WSNs: Overview and performance evaluation” was originally published by the previous publisher of Applied Computing and Informatics and the pagination of this article has been subsequently changed. There has been no change to the content of the article. This change was necessary for the journal to transition from the previous publisher to the new one. The publisher sincerely apologises for any inconvenience caused. To access and cite this article, please use Maimour, M. (2020), “Interference-aware multipath routing for WSNs: Overview and performance evaluation”, Applied Computing and Informatics. Vol. 16 No. 1/2, pp. 59-80. The original publication date for this paper was 15/03/2018.