## 3 The Proposed Protocol for Energy Efficient Routing in WSNs
### Description of the Proposed Routing Model
The BS broadcasts the unique IDs of the newly selected cluster heads, and their cluster members and the nodes use this information to form and enter a cluster. Therefore, each node has the knowledge of the number of times that it can be a cluster head and the number of times that it cannot. The BS runs the Gaussian elimination algorithm and computes the appropriate number of rounds that the nodes can be cluster heads and sends this information to the nodes. 5. The lower level cluster heads do not transmit directly to the BS. They use the upper level cluster heads as intermediate repeaters of their data to the BS. 6. Each cluster head creates a TDMA schedule and broadcasts this schedule to the nodes in its cluster, in order to inform each node of the timeslot that it can transmit. Moreover, the radio component of each node is allowed to be turned off at all time periods, except during  
Figure 1: The network model adopted. its transmission time. Therefore, the energy dissipation of every individual sensor is considerably reduced. 7. Then, the data transmission starts. The nodes, based on the allocated transmission time, send the data concerning the sensed events to their cluster head. The transmission power of every node is adjusted to the minimum necessary to reach its next hop neighbor. In this way, both the interference with other transmissions and the energy dissipation are reduced. 8. Every lower level cluster head aggregates the data and then transmits the compressed data to the upper lever cluster heads until the data reaches the base station. A round of data transmission has been completed, and the protocol continues from step 4 for the next round. 9. In case that there is a change in the network topology, due to either a change in a node position or in the total dissipation of a node residual energy, the BS uses again the Gaussian elimination algorithm to determine the appropriate cluster head election
10. The execution of the protocol is terminated as soon as all the nodes in the network run out of energy. The flow chart of ECHERP is shown in Figure 2.  
Figure 2: Cluster formation and data sending in ECHERP. The Gaussian elimination algorithm as used in the proposed protocol is presented in Figure 3.  
The proposed protocol performs clustering only once, at the initial stage. Hence, the protocol can avoid the time and energy consumed for re-clustering. The energy spent by the nodes in the network is modeled as a linear system, and the BS uses the Gaussian elimination algorithm in order to compute the energy consumpted by a node if it becomes a cluster head at the very next round by taking into consideration all possible combinations. Therefore, a combination that minimizes the overall energy consumption and prolongs the network is selected. The process of Gaussian elimination is accomplished in two phases. During the first phase, by using the forward elimination technique, the rank of the system, which represents the energy spent, is reduced. This is accomplished through the use of elementary row operations. In the second phase, the back substitution technique is used in order to find the solution of the system above. The energy consumption of a cluster head is based on the data reception of the messages sent to it by the cluster nodes and the data transmission of the messages sent from the cluster head to the upper level cluster heads or to the base station. The energy consumption of a cluster node is based on the data transmission of the messages sent to the cluster head. Let us assume that a cluster consists of \(k\) nodes; matrix \(A\) represent the energy consumption of every node in the cluster and \(k\) the number of nodes in a cluster. \(a_{ij}\) Denotes the energy consumed by node \(i\) if node \(j\) is the cluster head. Additionally, \(b_{i}\) denotes the residual energy of node \(i\), while \(x_{i}\) expresses the times that node \(i\) can become a cluster head. In this way, matrices \(B\) and \(X\) are formed, so that \(A\cdot X=B\), as shown in Equation 3.  
\[