# CERP: Cooperative and Efficient Routing Protocol for Wireless Sensor Networks
## 4 Cooperative Efficient Routing Protocol Formulation
### Proposed Relay Selection Algorithm (PRSA)  
In this subsection, we will formulate the Algorithm of the selection of the optimal preferred relay that reduced the transmission power \(E_{c_{R}}^{b}\) and \(E_{c_{S}}^{b}\) (for \(S\) and \(R\), respectively) while maintaining the BEP expressions given by (3) and (7) in the range of a predefined threshold value noted \(P_{e_{th}}\) and satisfying the power constraint \(E_{c_{R}}^{b}+E_{c_{S}}^{b}<E_{d_{S}}^{b}\) where \(E_{c_{R}}^{b}\), \(E_{c_{S}}^{b}\) and \(E_{d_{S}}^{b}\) represent the required transmission power for each communication link, as schematized in Figure 3.  
Figure 3: Respective power transmission links.  
Essentially, we choose to keep the BEP below a certain threshold, denoted by \(P_{e_{th}}\), while minimizing the power sent by the transmitter. To do this, we use the cluster's remaining \(N-2\) sensor nodes as potential relays. We propose a method for determining the most efficient relay node by minimizing the sum of the transmission powers necessary for each communication link (\(E_{c_{R}}\), \(E_{c_{S}b}\), and \(E_{d_{S}b}\)) while fulfilling the power constraint (\(E_{c_{R}b}\), \(E_{c_{S}b}\), and \(E_{d_{S}b}\)) as schematized in Figure 3.  
The preferred relay is the one ensuring the minimum \(E_{c_{R}}^{b}+E_{c_{S}^{\prime}}^{b}\), under the constraint that \(P_{e}(E_{R_{i}b};E_{S,b})\) is in the range of \(P_{e_{th}}\). This can be formulated as follows:  
\[R_{pre}= \underset{i\in\mathcal{R}}{\arg\min}\,E_{c_{R_{i}}}^{b}+E_{c_{S}}^{b}<E_{ d_{S}}^{b}\] \[s.c.\,P_{e}(E_{R_{i}b};E_{S,b})\approx P_{e_{th}} \tag{9}\]  
where \(R_{pre}\) denotes the preferred relay, \(\mathcal{R}=\{R_{1},R_{2},\ldots R_{N_{r}}\}\) where \(N_{r}\) is the number of reliable nodes having source-node SNRs that exceed a predefined threshold \(\gamma_{th}\). This optimization problem is solved numerically using the exact algorithm.  
The main steps of the preferred relay selection algorithm are explained in the Algorithm 1. We highlight that cooperation is not always more energy-efficient than direct transmission. If \(E_{c_{R_{i}}}^{b}+E_{c_{S}}^{b}>E_{d_{S}}^{b}\), this means that the direct (in this case, the CH will be set as a preferred relay in the routing table of the sensor node) transmission ensures the minimum transmission power in the range of \(P_{e_{th}}\). Therefore, in the transmission strategy, cooperation only occurs when the constraint in (9) is verified. Otherwise, if \(E_{c_{R_{i}}}^{b}+E_{c_{S}}^{b}<E_{d_{S}}^{b}\), the transmission from \(S\) to \(CH\) is performed via the selected relay only and no direct transmission link is considered. In this case, the proposed transmission strategy will not only increase the system's energy saving but also promote communication reliability.  
```
Compute the value of \(E_{d_{S}}^{b}\) that maintains \(P_{e_{th}}\) according to Equation (3)  Find the set of reliable relays \(\mathcal{R}=\{R_{1},R_{2},\ldots R_{Nr}\}\) for each reliable relay \(R_{i}\in\mathcal{R}\)do  Compute the values of \(E_{c_{R_{i}}}^{b}\) and \(E_{c_{S}}^{b}\) that maintains \(P_{e_{th}}\) according to Equation (7) if\(E_{c_{R_{i}}}^{b}+E_{c_{S}}^{b}<E_{d_{S}}^{b}\)then  Cooperative Transmission via relay \(R_{i}\) else  Direct Transmission endif endfor
```  
**Algorithm 1** Preferred Relay Selection Algorithm