## 4 The Optimal Relay Nodes Placement with Respect to Minimum Overall Power Usage  
### Problem Formulation  
Each sensor node has a limited communication ability; therefore, without pre-installed relay nodes, data acquired by sensor nodes may not be able to be piggybacked to the base station. In this section, we try to give the optimal scheme for relay nodes' placement with respect to minimum overall power usage. Without losing the rigorous nature of mathematics, we resort to the Lagrange dual problem and KKT conditions in order to figure out the closed-form solution. Before we step forward into the problem formulation, please allow us to introduce some notations used here. Since the networking issues among all layers are similar to each other, without any loss of generality, we take one layer of the mine for example. Since most coal mines are composed of tunnels, the topological structure of sensor networks of coal mines is somewhat linear. The optimization problem we formulated in this section is aimed to minimize the energy consumption of sensor and relay nodes along a linear structure. Assume that the distance between two sensor nodes is \(L\) meters. The communication range of each sensor node is \(R\) meters, and \(R<L\). For the successful communication between these two sensor nodes, a certain amount of relay sensor nodes should be placed between them. As shown in Figure 2, there are \(n\) relay nodes placed successively at \(x_{1},x_{2},\ldots,x_{n}\), and each of these sensor nodes has a communication range of \(R\) meters. The positions of the two sensor nodes are denoted as \(x_{0}\) and \(x_{n+1}\). We assume that the relay nodes are only reliable for receiving and forwarding data in the following discussion. The power usage of each node is composed of transmitting, receiving, processing and sensing data. Since the last two parts are relatively smaller compared to the first two factors and are independent of the optimization problem we discuss below, therefore, we omit the last two factors in the formulation of our optimization problem. The power usage of a node when transmitting data can be modeled as:  
\[p_{T}^{i}(t)=(\Phi_{1}+\Phi_{2}d_{i}^{k})r_{T}^{i}(t), \tag{1}\]  
Figure 2: A sketch map for sensor nodes and relay nodes. where \(p_{{}_{T}}^{i}(t)\) is the transmitting power used by node \(i\) at time instance \(t\), \(d_{i}\) is the transmitting distance, \(k\) is often chosen between two and four and \(r_{{}_{T}}^{i}(t)\) is the transmitting data rate of node \(i\) at time instance \(t\). The symbols \(\Phi_{1}\) and \(\Phi_{2}\) are power-related constants. The receiving power used by node \(i\) can be modeled as:  
\[p_{{}_{R}}^{i}(t)=\rho r_{{}_{R}}^{i}(t) \tag{2}\]  
where \(p_{{}_{R}}^{i}(t)\) is the power used for receiving data at time instance \(t\), \(r_{{}_{R}}^{i}(t)\) is the receiving data rate and \(\rho\) is the power-related constant. As shown in Figure 2, there are two sensor nodes and \(n\) relay nodes. By the definition of \(x_{i}\) given in the previous section, we have the following equation,  
\[\sum\limits_{i=1}^{n+1}(x_{i}-x_{i-1})=\sum\limits_{i=0}^{n}d_{i}=L \tag{3}\]  
where \(d_{i-1}=x_{i}-x_{i-1}\) is the distance between two successive sensor nodes. Then, we formulate the following optimization problem, OPT-1:  
min \[\int_{{}_{T}}[\sum\limits_{i=0}^{n}p_{{}_{T}}^{i}(t)+\sum\limits_{ i=1}^{n+1}p_{{}_{R}}^{i}(t)]dt\] s.t. \[(1)\text{--}(3)\] \[(0\leq d_{i}\leq R,i=0,\ldots,n)\]  
In this optimization problem, our objective is to minimize the energy used for transmitting data among sensor nodes and the corresponding relay nodes. The optimization variables are the number of relaying nodes n, which is an integer value, and the distance between two nodes \(d_{i}\). The optimization constants are the power-related constants, _i.e._, \(\Phi_{1}\), \(\Phi_{2}\) and \(\rho\), the transmitting data rate of the first sensor node, \(r_{{}_{T}}^{0}(t)\). Since all nodes should communicate properly, we have \(0\leq d_{i}\leq R\).