## 4 Description of the Proposed Topology Construction
### Selection of Leader Nodes  
Given a chain structure, leader scheduling determines which nodes play the role of leaders in operational rounds. The goal is to prolong network lifetime, _i.e._, to maximise the number of operational rounds. The following discusses the general issues about selecting leader node(s) with respect to power consumption. Suppose any node in a chain can be elected as a leader, and the leader is responsible to send the aggregated data to the BS. The maximum number of operational rounds that can be achieved before any node exhausts its power is analysed first. Without loss of generality, it can be assumed that nodes  
Figure 8: Link exchange. Crossed links are replaced by new links. in the chain are numbered sequentially as \(1,2,\ldots,n\). Let \(e_{i}\) be the energy consumed by the node \(i\) in transmitting a data message to the BS. Let \(\rho_{i,j}=kE_{elec}+k\epsilon_{amp}\left(d(i,j)\right)^{\alpha}\) be the energy consumed by the node \(i\), and \(e_{r}=kE_{elec}\) be the energy consumed by the node \(j\) when the node \(i\) transmits a \(k\)-bit message to the node \(j\). When a node \(i\) is selected to be the leader, every node numbered \(j<i\) (if any) expends \(\rho_{j,j+1}\) energy in sending data to the node \(j+1\), at which energy \(e_{r}\) is consumed to receive the data. Likewise, every node numbered \(k>i\) (if any) expends \(\rho_{k,k-1}\) to send data to the node \(k-1\), where energy \(e_{r}\) is expended in receiving the data. The leader transmits the collected data to the BS, consuming energy \(e_{i}\). Suppose that, every node \(i\) is scheduled to be the leader \(x_{i}\) times. Table 1 shows the energy expense of every sensor node in this case. The optimal leader scheduling problem is to find positive integer values of \(x_{i}\)'s to maximise \(\sum_{i}x_{i}\) subject to the following constraints:  
\[E_{1}\geq(e_{1}+e_{r})x_{1}+\rho_{1,2}x_{2}+\rho_{1,2}x_{3}+ \ldots+\rho_{1,2}x_{n}\] \[\vdots\] \[E_{i}\geq(\rho_{i,i-1}+e_{r})x_{1}+\ldots+(\rho_{i,i-1}+e_{r})x_{ i-1}+(e_{i}+2e_{r})x_{i}+(\rho_{i,i+1}+e_{r})x_{i+1}+\ldots+(\rho_{i,i+1}+e_{r})x_{n}\] \[\vdots\] \[E_{n}\geq\rho_{n,n-1}x_{1}+\rho_{n,n-1}x_{2}+\ldots+(e_{n}+e_{r}) x_{n}\]  
where \(E_{i}\) denotes the amount of energy that node \(i\) initially has. These constraints can be formulated as  
\[A\left( \begin{array}{c}x_{1}\\ x_{2}\\ x_{3}\\ \vdots\\ x_{n}\end{array} \right)\leq\left( \begin{array}{c}E_{1}\\ E_{2}\\ E_{3}\\ \vdots\\ E_{n}\end{array} \right)\] \begin{table}
\begin{tabular}{l l l l} \hline \hline
**Node ID** & **Energy spent to send message to the BS** & **Energy spent to neighbours** & **Energy spent to message** \\ \hline
1 & \(e_{1}x_{1}\) & \(\rho_{1,2}\sum_{j=2}^{n}x_{j}\) & \(e_{r}x_{1}\) \\ \hline \(i\in\{2,3,\ldots,n-1\}\) & \(e_{i}x_{i}\) & \(\rho_{i,i-1}\sum_{j=1}^{i-1}x_{j}+\) & \(e_{r}\left(\sum_{j=1}^{i-1}x_{j}+2x_{i}+\sum_{j=i+1}^{n}x_{j}\right)\) \\  & & \(\rho_{i,i+1}\sum_{j=i+1}^{n}x_{j}\) & \\ \hline \(N\) & \(e_{n}x_{n}\) & \(\rho_{n,n-1}\sum_{j=1}^{n-1}x_{j}\) & \(e_{r}x_{n}\) \\ \hline \hline \multicolumn{3}{l}{\(x_{i}\) : the number of times node \(i\) is selected to be the leader; \(e_{i}\) : the amount of energy consumed in transmitting message from node \(i\) to BS; \(\rho_{i,j}\): the energy consumed by \(i\) in transmitting a message to \(j\); \(e_{r}\) : the energy consumed by any node in receiving a message.} \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Energy consumption by different nodes while acting as a leader. where  
\[A=\left( \begin{array}{cccc}e_{1}+e_{r}&\rho_{1,2}&\cdots&\rho_{1,2}\\ \rho_{2,1}+e_{r}&e_{2}+2e_{r}&\cdots&\rho_{2,3}+e_{r}\\ \rho_{3,2}+e_{r}&\rho_{3,2}+e_{r}&\cdots&\rho_{3,4}+e_{r}\\ \vdots&\vdots&\cdots&\vdots\\ \rho_{n,n-1}&\rho_{n,n-1}&\cdots&e_{n}+e_{r}\\ \end{array} \right)\]  
Thus, the problem becomes a linear programming problem. Round robin leader scheduling equalises the values of \(x_{i}\)'s, which is generally far from optimal. The authors of PEGASIS also proposed an improvement on round robin scheduling [40].