# RBCR: a Relay-Based Cooperative Routing Protocol for Cooperative Wireless Sensor Network

Ahmed Ben Nacef, Sidi-Mohammed Senouci, Yacine Ghamri-Doudane, André-Luc Beylot

► To cite this version:

Ahmed Ben Nacef, Sidi-Mohammed Senouci, Yacine Ghamri-Doudane, André-Luc Beylot. RBCR: a Relay-Based Cooperative Routing Protocol for Cooperative Wireless Sensor Network. IFIP Wireless Days (WD 2011), Oct 2011, Niagara Falls, Canada. pp.1-3, 10.1109/WD.2011.6098181. hal-00808020

HAL Id: hal-00808020

https://hal.science/hal-00808020

Submitted on 23 Aug 2022

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# RBCR: a Relay-Based Cooperative Routing Protocol for Cooperative Wireless Sensor Networks

Ahmed Ben Nacef*, Sidi-Mohamed Senouci, Yacine Ghamri-Doudane and André-Luc Beylot

*2, avenue Pierre Marzin 22307 Lannion Cedex, France

Université de Bourgogne, Laboratoire DRIVE, 49 Rue Mademoiselle Bourgeois, 58000 Nevers, France

§ENSIIE, 1 Square de la résistance, 91025 Evry CEDEX, France

¶ENSEEIHT, Laboratoire IRIT, 2 rue C. Camichel, BP 7122, 31071 Toulouse Cedex 7, France

** Université de Paris-Est, LIGM Lab, 75420 Champs sur Marne, France

Emails: ahmed.bennacef@orange-ftgroup.com, sidi-mohammed.Senouci@u-bourgogne.fr, ghamri@ensiie.fr, beylot@enseeiht.fr

**Abstract**—In wireless sensor networks several constraints decrease communications performances. The main objective of this paper is to present a multi-objective routing algorithm RBCR that computes routing path based on the energy consumption and channel qualities. Additionally, the channel qualities are evaluated based on the presence of relay nodes. Compared to AODV and AODV associated to a cooperative MAC protocol, RBCR provides better performances.

***Index Terms***—Cooperative relaying, multi-objective routing protocol

## I. INTRODUCTION

In wireless sensor networks, the unreliable channels and the restrictions in energy resources make the routing a complex task. In addition, classical routing protocols [1] are not able to cope with the routing constraint of WSNs. Furthermore, cooperative communication constitutes a potential alternative. It proposes to use the neighbors as helpers in case they have better channels than the source. In fact, due to the broadcast nature of the wireless channel, the neighbors can over-hear the packet of the source, preserve it, then retransmits it to the destination when required. This technique replaces the selfish competitive access to the medium, by a cooperative one. It proved its efficiency in saving energy and enhancing the use of the wireless channel. In this paper, we propose to combine cooperation and routing. The contribution of our routing protocol can be summarized as follows :

* In all the cooperative protocols relay nodes are selected anew for each packet, resulting in an important signaling burden. Our routing protocol RBCR, computes the routing path and includes the relay nodes in the routing path.

* Besides, RBCR (Relay Based Cooperative Routing) computes the routing paths based on the CSI and based on the consumed energy. For more efficient route computation, it optimizes separately the energy consumed by the intermediate nodes and the energy consumed by the relay nodes.

## II. RELATED WORK

The existing ad hoc routing protocols are not adapted to the routing requirements of WSNs. In fact, traditional routing protocols like AODV [1] define the best path as the path having the shortest number of hops from the source to the destination. Nevertheless, WSNs have several constraints and the optimal path is defined to be the path consuming less energy, having the best channels or both. Several research efforts were conducted during the last few years to conceive routing protocols coping with the WSN energy constraint. An energy aware routing protocols was proposed by the authors in [2]. The routing decision is taken by merging the information about the residual energy of the node and the environmental energy supply. The second major WSNs constraint is the wireless channel. WSN channels are unreliable. In order to increase the transmission range of the nodes, the protocol proposed in [3] considers that sensor nodes are able to transmit packets cooperatively and simultaneously. Simulation results show that this method strengthens the network connectivity.

## III. PROBLEM FORMULATION

In this section we present the models used by RBCR as well as the formulation of the shortest path problem while relays are used. More precisely, we present the used network and channel models and the problem formulation. Our models are based on two studies [4], [5]. We represent the WSN as a graph G(V,E). V is the set of vertices and E is the set of edges. The wireless links are characterized by two parameters: the CSI and the mean energy. Therefore, on the graph, an edge (i,j) is labeled by two costs: the energy $E_{V_i,V_j}$ and the CSI $CSI_{V_i,V_j}$. The channels are modeled by a Rayleigh fading distribution. Our sensors perform the Decode and Forward (DF) technique. They decode the received packet, and then re-encode it before forwarding it without verification. The signals of the packet received by the destination and over-heard by a relay can be represented by the following formula: $Y_{SD} = \sqrt{P_{SD}} \cdot h_{SD} \cdot X_s + n_{SD}$ and $Y_{SR} = \sqrt{P_{SR}} \cdot h_{SR} \cdot X_s + n_{SR}$

Where $P_{SD}$ (respectively $P_{SR}$) is the power of the signal received by the destination (respectively relay), $X_s$ is the signal transmitted by the sender and $h_{SD}$ (respectively $h_{SR}$)
is the Rayleigh distributed fading coefficient of the channels between the source and the destination (respectively relay) of one hop, and $n_{SD}$, $n_{SR}$ are the additive white Gaussian noise of the channels. The two channels, from S to R and from S to D can be modeled by an equivalent channel : $Y_D = W_{SD} \cdot Y_{SD} + W_{RD} \cdot Y_{RD}$

With $W_{SD} = \sqrt{P_{SD}} \cdot h_{SD}$ and $W_{RD} = \sqrt{P_{RD}} \cdot h_{RD}$ are the combining coefficient. More details about the computation of the equivalent channel are given in [6].

The main objective of this paper is to present a routing algorithm that computes routing path based on the energy consumption and channel qualities. For each hop, the relay node that proposes the best channel and consumes the least energy is selected and considered as a part of the route. In order to solve this dilemma, we represent it by the Minimum Cost Path problem With Relays [5]. Our routing problem can be modeled as follows:

$$E_i(p) = \text{Min} \sum_{p} Ei_{(V_i, V_j)} \quad V_i \text{ and } V_j \in p \quad (1)$$

$$E_r(p) = \text{Min} \sum_{p} Er_{(V_i, V_j)} \quad V_i \text{ and } V_j \in p \quad (2)$$

$$\text{CSI}(p) = \text{Max} (\text{Min } C_{\text{CSI}_{V_i, V_j}}) \quad V_i \text{ and } V_j \in p \quad (3)$$

Where p is a path joining a source and a destination and p is a member of $P_{s,d}$ the set of possible paths from S to D. $E_i(p)$ is the sum of energy consumed by the nodes of p to transport the packet from S to D. $E_r(p)$ is the sum of energy consumed by the eventual relay nodes. CSI(p) is the minimum CSI value of the links composing the path. Generally, these types of problems do not have a unique optimal solution. Several solutions exist. In our case, a solution S is considered as efficient if it does not exist a second solution S' that respects the following conditions with at least a strict inequality : $E_i(S) \le E_i(S')$, $E_r(S) \le E_r(S')$ and $\text{CSI}(S) \le \text{CSI}(S')$.

## IV. RELAY BASED COOPERATIVE ROUTING (RBCR)

In the current section we present our routing protocol. The optimal paths are found by solving the multi-objective optimization problem presented in section III. An optimal path is computed using a distributed algorithm and by propagating a label from the source towards the destination.

A label in a given intermediate node is a pointer to the previous node in the reverse path to the source. The structure of such a label is given by Figure 1. It contains seven fields. The first field is used to identify the label in the current node. The second field is a pointer to the label that generated the current label. The Energy I and Energy R fields contain the mean of the consumed energy respectively by the intermediate nodes and the relay nodes. The CSI field describes the qualities of the links from the source to the current node. The PP ID, Relay ID and Previous ID fields define the identities of the previous nodes in the two-hop path. The Previous ID field contains the identity of the node preceding the current one in

the path. The Relay ID field identifies the relay between the current node and the previous one. Finally, the PP ID field contains the identity of the node preceding the previous one. In order to trigger a route search, the source broadcasts a Route

<figure><img src="image_2.png" /><figcaption>Fig. 1. The label's structure</figcaption></figure>

Request packet containing a label. It fills the Previous ID field by its address as well as the Previous Label ID field. Next, it puts on the Energy_I field the quantity of energy required to send the packet. Finally, it affects zero to all the other fields. The RReq packet is then relayed over the network from a node to its neighbors until reaching the destination. When a node $V_i$ receives a RReq it extracts the label. The following actions taken by $V_i$ depend on the value of the field Relay ID field. If its value is -1 (the previous node on the path is not a relay), so, the current node can be an intermediate node or a relay node. Otherwise, the current node can only be an intermediate node. At first, $V_i$ starts by considering itself as an intermediate node on the path. The coming label is compared to the existent ones to verify its optimality. Suppose that $L_c = (E_{I_c}, E_{R_c}, CSI_c)$ is the coming label and $L_i = (E_{I_i}, E_{R_i}, CSI_i)$ is a label of the routing entry. The subpath represented by $L_c$ is more efficient than the one represented by $L_i$ if one of the following optimality conditions (we call it C1) $CSI_c \ge CSI_i$ and $E_{I_c} \ge E_{I_i}$ and $E_{R_c} \ge E_{R_i}$ are true. In this case $L_c$ is added to the Routing entry and $L_i$ is deleted. Moreover, if one of the conditions of [4] is true, therefore both labels are equivalents and $L_c$ is added without deleting $L_i$. In both cases, a new label is created, the fields are updated using Algorithm 1 included in the RReq, and broadcast.

<caption>**Algorithm 1: Label Update No Relay**</caption>

E_{NewLabel} \leftarrow E_I + \text{transmission\_energy()}
E_{R_{NewLabel}} \leftarrow E_R
CSI_{NewLabel} \leftarrow \text{Min}(CSI_c, CSI_{LastHop})
\text{Previous ID}_{NewLabel} \leftarrow \text{my\_address}
PP ID_{NewLabel} \leftarrow \text{Previous ID}_{L_c}
Relay ID_{NewLabel} \leftarrow -1
\text{Previous LabelID} \leftarrow \text{Current Label ID}_{L_c}
\text{Current LabelID} \leftarrow \text{New\_Id()}

<caption>**Algorithm 2: Label Update With Relay**</caption>

E_{NewLabel} \leftarrow E_I
E_{R_{NewLabel}} \leftarrow E_R + \text{transmission\_energy()}
CSI_{NewLabel} \leftarrow \text{Min}(CSI_c, CSI_{LastCooperativeHop})
\text{Previous ID}_{NewLabel} \leftarrow \text{my\_address}
PP ID_{NewLabel} \leftarrow -1
Relay ID_{NewLabel} \leftarrow \text{Previous ID}_{L_c}
\text{Previous LabelID} \leftarrow \text{Current Label ID}_{L_c}
\text{Current LabelID} \leftarrow \text{New\_Id()}

When the Relay ID field of the received Label does not contain any address (field assigned to -1), the receiving node decides if the previous node can be a relay node. Therefore, it checks if it is a neighbor to the node in the PP ID field.
Provided that it is the case, the node verifies the optimality of this solution. It proceeds the same way to check the conditions of [4] and the C1 condition. Once the optimality of the solution is verified the node creates a new labels using the algorithm 2.

When the destination receives a RReq, it verifies the effi-
ciency of the label. At the destination, the labels are added
to the routing entry only if they verify the C1 conditions. It
means, only if the currently used label represent a dominated
solution. Thereafter, the destination sends a Route Update
(RUpd) packet to inform the intermediate nodes about the new
path. When an intermediate node receives a Route Reply or
Route Update, It searches for the label whose Id correspond
to the one received in the RRep or RUpd. It extracts from
this label the address of the next node and the Id of the
next label. It creates a new Route Reply (respectively Route
Update) packet then sends it to the corresponding node. When
the packet reaches the source node then the path is established.

V. SIMULATION RESULTS

In this section we evaluate RBCR performances using sim-
ulations. Our protocol is implemented on the Opnet simulator
with the Zigbee module. RBCR performances are compared
to those of: (i) AODV with a classical MAC layer (i.e.
without cooperation) and (ii) AODV with COSMIC [16]. We
run simulations with each of these protocols using different
network configurations. All configurations contain a source, a
destination and a number of intermediate nodes. We start by
a network containing 10 nodes and we increase the network
size by ten nodes at each step until reaching 70 nodes.
The node are uniformly distributed in a square with a side
length of 500m. The CSI of the channels is represented by
the Signal-To-Noise-Ratio (SNR). The channels are Rayleigh
faded with quasi-static fading: each packet is faded randomly
and independently. Furthermore, we consider that the channels
of the network are fully symmetric. The power consumption
of the node is 17.4mA for transmission, 19.7mA for reception
and 10<sup>-3</sup>mA in Idle mode. For each data value we present in
the results, we also give its 90% confidence interval.

**Delivery Ratio:** Figure .2 depicts the delivery ratio. It defines the ratio of the successfully delivered packets to the destination. AODV has the lowest delivery ratio since it does not consider link qualities. Combined with COSMIC, the performances of AODV are obviously improved. Indeed, COSMIC enhances the use of the links of the route and saves more packets. This helps in partially solving the channel-quality issue in AODV since COSMIC tries to enhance the performance of each link. However, this does not overcome the fact that AODV does not necessarily chooses the best paths in term of channel qualities. Alternatively, RBCR does by including the CSI as a parameter in route computations. By doing so, RBCR demonstrates the best delivery ratio. Since the path links used by RBCR are better and the number of lost packets is reduced.

<figure><img src="image_3.png" /><figcaption>Fig. 2. Delivery Ratio Vs Number of nodes</figcaption></figure>

VI. CONCLUSION

In this work we proposed a routing protocol, RBCR that
copes with WSN constraints. Route computation considers
the existence of relay nodes, able to enhance the channel
use, in addition to the consideration of energy consumption.
Simulation results are promising and show that RBCR is able
to enhance the delivery ratio.

REFERENCES

[1] C. Perkins, E. Belding-Royer, and S. Das, "Ad hoc on-demand distance vector (aodv) routing," United States, 2003.

[2] K. Zeng, K. Ren, W. Lou, and P. J. Moran, "Energy aware efficient geographic routing in lossy wireless sensor networks with environmental energy supply," *Wirel. Netw.*, vol. 15, pp. 39–51, January 2009.

[3] J. Yu, H. Roh, W. Lee, S. Pack, and D.-Z. Du, "Cooperative bridges: Topology control in cooperative wireless ad hoc networks," in *INFOCOM, 2010 Proceedings IEEE*, march 2010, pp. 1–9.

[4] X. Gandibleux, F. Beugnies, and S. Randriamasy, "Martins' algorithm revisited for multi-objective shortest path problems with a maxmin cost function," *4OR*, vol. 4, pp. 47–59, 2006.

[5] G. Laporte and M. M. Pascoal, "Minimum cost path problems with relays," *Computers and Operations Research*, vol. 38, no. 1, pp. 165–173, 2011, project Management and Scheduling.

[6] M. Dohler and Y. Li, *Cooperative Communications: Hardware, Channel and PHY*. Wiley & Sons, February 2010.