## 4 Energy-Aware Routing Protocol
### Construction of Routing Tree  
After the network is clustered, inter-cluster organization depends on the network application. For example, cluster heads can communicate with each other to aggregate their information via multiple hops or communicate with the base station directly. For multi hop communication among cluster heads, the selected transmission range among cluster heads may vary to ensure a certain degree of connectivity and to control interference. For inter-cluster communication, the definition of connectivity depends on its multi hop organization and the relationship between the inter-clustertransmission range, R, the intra-cluster transmission range, r, and the density of nodes. In [8], authors demonstrate that the graph composed by cluster heads will be connected if \(R\geq 6r\). However, we argue that the theoretical value for connectivity may be not applicable for a real application, i.e. the unreasonable inter-cluster range for inter cluster communication is another inefficient use of energy. For example, we consider a typical setting of sensor network referenced in [8] [network size from (0,0) to (100,100), cluster range = 30 m, sink at (50,175)]. According to the above formulae for connectivity, the radio range for inter-cluster communication should be set as 180 m, which means all cluster heads can almost communicate with base station directly.  
In this paper, we set inter-cluster transmission range as 2.5r, where r is the intra-cluster range referenced as before. Because we assume the network is a dense network (\(>\) 1/100 m\({}^{2}\)), it can guarantee that most cluster heads are member nodes of the largest connected component of graph composed by all cluster heads. In the next section, we will discuss the relationship between the inter-cluster transmission range, R and the number of independent connected components of a graph by experiments. The theoretical analysis will be made in the later work.  
After clustering, cluster heads broadcast within a radius R the Weight message, which contains node ID and weight W. The cluster head compares its own weight and the weight contained in the Weight message received from its neighbor cluster head. If it has smaller weight, it selects the node that has the largest weight as its parents and sends the CHILD message to notify the parent node. Finally, after a specified time, a routing tree will be constructed, whose root node has the largest weight among all cluster heads in the same independent connected component. After routing tree construction, cluster heads broadcast a TDMA schedule to their active member nodes to be ready for data gathering. The pseudo code for cluster formation is shown in Figure 5.  
For example, as shown in Figure 6, node A\(\sim\)E are cluster heads with their weight in parenthesis. B will receive a WEIGHT message from A, C, D, E and select node A to be its parent. Similarly, node D and E choose B as their parent, while C chooses A as its parent. Node A receives a WEIGHT message from nodes B and C, but their weight is less than node A, so A will be the root node that communicates with the base station and routing tree is built.  
Figure 5: Routing Tree Construction.  
We define weight \(W\) of node \(i\) as:  
\[w_{i}=\frac{D\big{(}RSS_{i}\big{)}\times E_{a}}{D\big{(}RSS_{\max}\big{)}\times E _{residual}},\]  
where \(RSS_{i}\) denotes node i's received signal strength for the signal broadcasted by the base station, \(RSS_{max}\) is a constant which is determined by the location of the base station, and the function D is used to estimate the distance between node i and the base station. After the deployment of sensors, the base station broadcasts probing message to all sensors and sensors acquire the \(RSS\) according to the received signal strength. \(RSS\) remains constant during the network lifetime unless base station varies its location or sensor nodes are mobile. The node that is closer to the base station and locates in a subregion with full energy would be the root node of routing tree due to its higher weight.