## 3 Network Model and Problem Statement
### Problem Statement  
There are several requirements for a clustering algorithm. First, a clustering algorithm should be completely distributed because a centralized control manner is not practical in a large-scale sensor network. Second, the cluster heads should be well distributed throughout the monitoring area to make energy consumption be well-balanced among all sensor nodes. Third, the clustering algorithm itself should be energy efficient. Fourth, a clustering algorithm needs to handle the heterogeneous energy circumstance. In reality, it is hard to guarantee that the battery capacity of all nodes is the same. The amount of the energy consumed in gathering data differs among cluster heads, and it depends on the number of cluster members and their positions in the monitoring area. Energy consumption also differs among cluster members due to the different distances to a cluster-head. Furthermore, redeployment for prolonging network lifetime or denser observing will also be the cause that residual energy is not equal among all sensor nodes. In the current research done in the area of data gathering protocols in wireless sensor networks, we have noticed that most of the proposed clustering algorithms do not satisfy all these requirements. Here, we will make an analysis of three algorithms that may be regarded as representative of the existing research on clustering algorithm in WSNs in order to explain why the proposed clustering algorithms cannot meet all requirements. LEACH's clustering algorithm assumes that sensor nodes are homogenous and equal. However, in reality, it is hard to guarantee that. In addition, according to the scale of the sensor network, the optimum percentage of cluster heads has to be determined in advance. Therefore, LEACH cannot adapt to such changes in sensor networks as the addition, removal, and transfer of sensor nodes; however, the percentage of cluster heads considerably affects the efficiency of data gathering. Finally, a cluster head needs to broadcast its own advertisement to the whole sensor network in cluster formation phase of LEACH, thus causing another inefficient use of energy. HEED is a hybrid, energy-efficient, distributed clustering algorithm, but it needs multiple broadcasting for cluster formation and thus consumes more energy. EECS elects cluster heads they should be the nodes with more residual energy in a distributed manner through local radio communication with no iteration while achieving a good cluster head distribution. However, we argue that setting the residual energy as the primarily parameter for cluster heads election doesn't help balance the energy load for the proper nodes, especially in heavy energy heterogeneous circumstance. In most local clustering algorithms in wireless sensor networks, to prolong the sensor network lifetime, the probability of a sensor node's being selected as a cluster head primarily depends on its own residual energy. However, in some special cases, it doesn't help balance the energy load for the proper nodes. As a result, it may cause the problem that some nodes will be exhausted quickly. For instance, as shown in Figure 1, let us consider a sensor network composed by seven nodes. Nodes 4 and 3 locate in each other's cluster range and the amount of the residual energy of node 4 and node 3 is higher than that of the other nodes. Then, assume that each node's being selected as a cluster head only depends on the residual energy of this node. Obviously, the probability that node 3 is selected as a cluster head is the highest. Consequently, the probability that the other nodes with low residual energy are selected as a cluster head will increase, like node 5 or node 6. Because a cluster head consumes more energy than a plain node, the energy of nodes within the cluster range of node 4 will be exhausted quickly. In order to solve the problems mentioned above, we present a novel hierarchical clustering scheme EAP which can meet all the requirements listed previously. In the next section, we will describe the EAP algorithm in details.