# An Energy-Efficient Two-Stage Cooperative Routing Scheme in Wireless Multi-Hop Networks
## 2 System Model and Existing Schemes  
### System Model  
We consider a wireless network consisting of \(N\) nodes arbitrarily distributed in an area, where each node is equipped with a single omnidirectional antenna. These nodes can self-organize to form a multi-hop network. Define the whole network as a connected undirected graph \(G=(\mathcal{V},\mathcal{P})\), in which \(\mathcal{V}\) is the set of nodes and \(|\mathcal{V}|=N\) is the number of nodes. \(\mathcal{P}\) denotes the set of all the bi-directional wireless communication links between pairs of nodes. In case a node \(i\in\mathcal{V}\) transmits data \(X\) with the maximum power \(P_{\text{max}}\), and another node \(j\in\mathcal{V}\) can successfully decode \(X\) without the aid of any other nodes, we say a link \(\mathcal{P}_{i,j}\in\mathcal{P}\) exists. Assuming that \(X\) is encoded with an ideal forward error correction (FEC) code, then \(\mathcal{P}_{i,j}\in\mathcal{P}\) implies that if node \(i\) transmits with maximum power, the received signal-to-noise ratio (SNR) at node \(j\) is at least \(\gamma_{\text{min}}\) which is dictated by the FEC code-rate. Consider a pair of arbitrarily chosen source node \(V_{s}\in\mathcal{V}\) and destination node \(V_{d}\in\mathcal{V}\) as shown in Figure 1. The data of \(V_{s}\) is delivered to \(V_{d}\) via a route \(r=\{r_{1},r_{2},...,r_{K}\}\) where \(r_{1}=V_{s}\), \(r_{K}=V_{d}\), \(r_{2},\cdots,r_{K-1}\in\mathcal{V}\) are intermediate relay nodes such at \(\mathcal{P}_{k,k+1}\in\mathcal{P}\). Each hop is assigned with a _link cost_\(\mathcal{C}_{k,k+1}\). The shortest path is given by  
\[r^{\star}=\operatorname*{arg\,min}_{r\in\Omega(V_{s},V_{d})}\sum_{k=1}^{K} \mathcal{C}_{r_{k}r_{k+1}}, \tag{1}\]  
where \(\Omega\left(V_{s},V_{d}\right)\) is the set of all possible routes from \(V_{s}\) to \(V_{d}\). The difference of various routing schemes mainly lies in the different definition of link cost and different transmission model in each hop. Figure 1: A route from source to destination. With the non-cooperative point-to-point transmission model, the signal received by node \(j\) from node \(i\) can be expressed as  
\[y_{j}=h_{i,j}w_{i}X+z_{j}, \tag{2}\]  
where \(z_{j}\) is complex Gaussian noise with zero mean and variance \(\sigma^{2}\). \(X\) is the data symbol satisfying \(\mathbb{E}[|X|^{2}]=1\). \(w_{i}\) is the power control coefficient such that \(|\omega_{i}|^{2}=P_{i}\leq P_{\text{max}}\). \(h_{i,j}\) denotes the complex channel gain between node \(i\) and \(j\). We assume that the channel between any two nodes is Rayleigh block fading, and \(\mathbb{E}[|h_{i,j}|^{2}]\) is inversely proportional to \(d_{i,j}^{\text{a}}\)[24], where \(d_{i,j}\) denotes the distance between node \(i\) and \(j\), \(\alpha\) is the path loss exponent. The received SNR at node \(j\) is given by  
\[\gamma_{j}=\frac{|h_{i,j}w_{i}|^{2}}{\sigma^{2}}=\frac{P_{i}|h_{i,j}|^{2}}{ \sigma^{2}}. \tag{3}\]  
If node \(i\) can reach \(j\), i.e., \(\mathcal{P}_{i,j}\in\mathcal{P}\), then by definition there must be \(\frac{P_{i}|h_{i,j}|^{2}}{\sigma^{2}}\geq\gamma_{\text{min}}\). The _Neighbor Set_ of node \(i\), \(\mathcal{N}\left(i\right)\), consists of all reachable nodes of \(i\):  
\[\mathcal{N}\left(i\right)=\left\{j\in\mathcal{V}\left|\frac{P_{\text{max}}|h_{ i,j}|^{2}}{\sigma^{2}}\geq\gamma_{\text{min}}\right.\right\}. \tag{4}\]  
Similar to [4; 5], we assume that within the range of \(\mathcal{N}(i),\forall i\in\mathcal{V}\), channel state information (CSI) is available to node \(i\) and the signaling messages can be transmitted reliably with the negligible cost. Due to the broadcast nature of wireless communication, it is possible that when node \(i\) transmit \(X\) with power \(P_{i}\leq P_{\text{max}}\), multiple nodes in \(\mathcal{N}(i)\) can decode \(X\). Hence, some of the hops in Figure 1 may benefit from the cooperative transmission of multiple nodes. The concept of cooperative transmission has already been discussed in multi-hop routing schemes [25; 26] in the form of cooperative beamforming model.