## 2 Related Works  
Many data collecting routing methods have been proposed. These methods can be classified into two categories, cluster-based and chain-based. In cluster-based methods [5; 6; 7; 8; 9; 10], the sensors are divided into several clusters. Each cluster elects a cluster header (CH) to serve as the local base station. Other sensors in this cluster forward their data to the CH directly. Next, each CH forwards the aggregated data to the sink. To balance the energy overhead of being the CH, each cluster elects a new sensor to be the cluster head for service. There are many clustering mechanisms proposed for data gathering. Sensors may be organized into constant size clusters [5], clustered according to the grids that they are deployed [6], based on the fuzzy logic or fuzzy c-mean mechanism [7; 21], or type-2 fuzzy logic and ACO [22]. In addition, clustering sensors according to the sensors' energy in heterogeneous wireless sensor network is also proposed [23]. The first proposed and well-known method is the LEACH approach [9]. The clustering-based methods use multiple hops propagation to shorten the transmitting distance from each sensor to the sink directly. It can also prevent all sensors from consuming a lot of energy on long-distance data transmission except the sensors being the CHs. Therefore, the sensors with plenty of energy are the candidates to be the cluster head [14]. The cluster-based methods can be improved further if the number of CHs can be reduced. All sensors can aggregate their data to one sensor and then transmits to sink. Sensors can be organized into the chain format to reduce the data propagation distance to the next hop. In the chain-based methods [11; 12], each sensor only has one or two neighbors. Sensors that located at both ends of the chain have one neighbor and the others have two neighbors. Each sensor combines its data with one neighbor's data and then forwards to the other neighbor. Eventually, a sensor named 'leader' aggregates all data and transferred to the sink. Similar as the cluster-based methods, sensors take turns to serve as the leader to share the long-distance transmission overhead. The well-known chain-based method is PEGASIS [11]. The chain-based protocols do efficiently reduce the energy consumption of sensors spent on long-distance data propagation, but the cost is the increasing propagation hops. The number of data propagation hops increases as the number of sensors grows. In a network with \(N\) sensors, the maximum number of propagation hops is \(N/2\) when the leader is located at the middle position of the chain. However, the maximum number of propagation hops is N-1 when the sensor located at the end of the chain is selected as the leader. A variation chaining mechanism named ring-based information collection architecture (RICA) is organizing the sensors as a circle [24]. Each sensor in the circle of the RICA method has two directions to propagate its data to leader and the maximum number of propagation hops can always be _N_/2 if the sensors are evenly divided between the left side and the right side of the leader. The key issue of the chain-based methods is the chaining mechanism. Building the Hamilton path or the Hamilton cycle has already known to be NP-complete problem. Heuristic chaining mechanisms are applied to link the deployed sensors [25; 26]. A worse chaining sequence may cause the sensors to exhaust their energy faster than the sensors in the cluster-based methods. Another variation of the chain-based methods is the tree-type methods [27; 28; 29; 30]. The tree-type methods use the minimum spanning trees (MSTP) [17] to create the shortest link between the sensors and their neighbors or try to propagate data to sink with a shortest distance path. The problem is the maximum number of propagation hops of the minimum spanning trees is topology dependent, and greedily using the shortest path causes the sensors exhaust their energy quickly.