## 4 Energy-Aware Routing Protocol
### Clustering Algorithm  
In EAP protocol, each node needs to maintain a neighborhood table to store the information about its neighbors, as shown in table 2. The ID indicates the unique identification of the neighbor nodes. Without losing the generality, we use an integer value to label a node's identification like TinyOS [14]. At the beginning of each round, each node broadcasts the E_Msg within radio range r and all nodes are cluster head candidates. Here we use r to denote the cluster range. All nodes within the cluster range of one node can be seen as the neighbors of this node. Each node receives the E_Msg from all neighbors in its cluster range and updates the neighborhood table. Using Ea denotes the average residual energy of the cluster range of node V\({}_{\mathrm{i}}\), and V\({}_{\mathrm{j}}\) represents a neighbor node in cluster range of V\({}_{\mathrm{i}}\), where m is the number of nodes within the cluster range. We define:  
\[E_{a}=\frac{\sum\limits_{j=1}^{m}\mathrm{V}_{j}.E_{residual}}{m} \tag{1}\]  
After exchanging E_Msg, each node computes the broadcasting delay time t for competing cluster head according to the following equation:  
\[t=k*T*\frac{E_{a}}{E_{residual}} \tag{2}\] \begin{table}
\begin{tabular}{l l} \hline
**State or Message** & **Description a** \\ \hline Candidate & The node is a candidate node \\ Head & The node is selected as cluster head \\ Plain & The node is a member node \\ Compete_Msg & Composed by the ID of sender \\ Join_Msg & Composed by the ID of sender and the ID of head \\ Weight_Msg & Composed by the ID of sender, weight, E\({}_{\mathrm{a}}\), E\({}_{\mathrm{residual}}\) \\ Schedule _Msg_ & Head assign slot time for its member nodes \\ \hline \end{tabular}
\end{table} 
Table 1: Descriptions of States and Messages. \begin{table}
\begin{tabular}{c c c} \hline
**ID** & **State** & **Residual Energy (J)a** \\ \hline
3 & Candidate & 1.32J \\
7 & Candidate & 0.16J \\
6 & Candidate & 0.09J \\
5 & Candidate & 0.32J \\ \hline \end{tabular}
\end{table} 
Table 2: Node 4’s Neighborhood Table. where k is a real value uniformly distributed between 0 and 1 and T is the time duration for cluster heads election. In order to solve the heterogeneous energy problem, EAP uses \(E_{a}\div E_{residual}\) as the primarily clustering parameter for competing cluster heads. Observing equation 2, t is the time that each node broadcasts the Compete_Msg for competing cluster head, which is mainly determined by \(E_{a}\div E_{residual}\). As shown in Figure 1, we introduce this clustering parameter for cluster head election. It is easy to find the probability that node 1 becomes a cluster head will increase. This means that the lifetime of the nodes with low residual energy within the cluster range of node 1 will increase. Compared with the previous works [5; 8; 11], which only depend on the residual energy of nodes, EAP can better handle the heterogeneous energy circumstance. In EAP, if a node S\({}_{i}\) has not received any Compete_Msg from its neighbor nodes in the time (0, t), as shown in Figure 2, this node will broadcast the Compete_Msg to all its neighbor nodes. Otherwise, it will give up competition. After S\({}_{i}\) broadcasts Compete_Msg, it will wait 2*\(\Delta t\), where \(\Delta t\) denotes the time interval which can guarantee that all neighbor nodes can receive the Compete_Msg, to make sure whether there exists another Compete_Msg broadcasted by other nodes in its cluster range. If S\({}_{i}\) has not received any Compete_Msg from its neighbors over \(\Delta t\), it will set its state as Head, or else it will compare its weight with the weights of other broadcasting neighbors. If S\({}_{i}\)'s weight is the largest one, it will set its state as Head and other broadcasting neighbors give up competition, or else S\({}_{i}\) sets its state as Plain. Obviously, the CF procedure allows only one cluster head in a cluster range. If there are multiple Compete_Msg overheard, the one with the largest weight will serve as the only cluster head.