## 3 The Proposed Protocol for Energy Efficient Routing in WSNs
### Description of the Proposed Routing Model  
In ECHERP, the BS is assumed to have unlimited energy residues and communication power. It is also assumed that the BS is located at a fixed position, either inside or away from the sensor field. The longer the distance between the BS and the center of the sensor field, the higher the energy expenditure for every node transmitting to the BS. All the network nodes, which are assumed to be located within the sensor field, are dynamically grouped into clusters. One of the nodes within every cluster is elected to be the cluster head of this cluster. Therefore, the number of cluster heads is equal to the number of clusters. The cluster heads, which are located close enough to the network base station, are referred to as the first level cluster heads. These cluster heads are capable of direct transmission to the base station with reasonable energy expenditure. The cluster heads that are located at more distant positions from the base station are considered as second-, third-, _etc._ level cluster heads. These cluster heads transmit data to the upper level cluster heads. Moreover, in order to achieve balanced energy consumption and extend the network's lifetime, the election of the cluster heads is performed in turns. The main characteristic of ECHERP is the head selection process. In this protocol, in order to elect a cluster head, the routing information and the energy spent in the network are formulated as a linear system, the solution of which is computed using the Gaussian elimination algorithm. Therefore, cluster heads are elected as the nodes that minimize the total energy consumption in the cluster. In most of the protocols proposed so far, the node with the highest residual energy in a cluster is elected as the cluster head. This selection may lead to inefficiencies, as can be seen by the following example. Let us assume that node \(x\) in Figure 1 has higher residual energy than the other nodes belonging to the same cluster. Then, this node is elected as the new cluster head. However, this forces the rest of the nodes to send data in the opposite direction to the base station, resulting in higher energy consumption. Obviously, this is not an energy efficient process, and it can be avoided by selecting cluster heads in a more energy efficient manner. This is pursued by the proposed protocol. The steps in order to setup clusters and then to elect cluster heads are the following:  
1. The BS creates a Time Division Multiple Access (TDMA) schedule and requests the nodes to advertise themselves, a process similar to that of other protocols. 2. Each node broadcasts a message to advertise its energy level and location to its neighbors. Based on this exchanged information, each node sets up a neighbor information table that records the energy level and the positions of its neighbors and sends this table along with its corresponding information to its neighbors. This step is repeated until the information of all the nodes in the network is sent to the BS, allowing the BS to have a global knowledge of the network. At this step, all the nodes are cluster head candidates, and each node has a unique ID that is also included in the exchanged table. 3. As soon as the node advertisement is completed, the BS runs the Gaussian elimination algorithm and computes the number of rounds at which every node can be a cluster head, trying to maximize the network lifetime. In the first step of the cluster head selection, the BS chooses the nodes closest to itself to be the high level cluster heads. Moreover, some of the nodes from which the BS has not received any direct advertisement message are considered to be low level cluster heads. The overall number of nodes, which are assigned to be cluster heads, is 5% of the total number of the nodes in the network, as this can be helpful in achieving good performance in a homogeneous network with various parameter settings [11]. Other percentages can also be used. 4.