## 5 Analysis of Prominent Clustering Routing Protocols in WSNs
### Data-Transmission Based Clustering Routing Protocols  
#### 5.2.1 PEGASIS  
Power-Efficient Gathering in Sensor Information Systems (PEGASIS), proposed by [PERSON] _et al_. [26], is an improvement of LEACH. The main idea of PEGASIS is for each node to only communicate with their close neighbors and take turns being the leader for transmission to the sink. In PEGASIS, the locations of nodes are random, and each sensor node has the ability of data detection, wireless communication, data fusion and positioning. Energy load is distributed evenly among the sensor nodes in the network.  
In PEGASIS, the nodes are organized to form a chain, which can either be concentratedly assigned by the sink and broadcast to all nodes or accomplished by the nodes themselves using a greedy algorithm. If the chain is formed by the nodes themselves, they can first get the location data of all nodes and locally compute the chain using the same greedy algorithm. During the process of chain formation in PEGASIS, it is assumed that all nodes have global knowledge of the network and the greedy algorithm is employed. The chain construction is commenced from the furthest node from the sink and the closest neighbor to this node will be the next node on the chain. When a node on the chain dies, the chain will be reconstructed in the same manner to bypass the dead node.  
For gathering data from sensor nodes in each round, each node receives data from one neighbor, fuses the data with its own, and transmits to the other neighbor on the chain. By moving from node to node, the fused data eventually are sent to the sink by the leader at a random position on the chain. The leader is important for nodes to die at random locations, in respect that the idea of nodes dying at random places is to enhance the robustness of the network. Alternatively, in each round, a control token passing approach initiated by the leader is used to start the data transmission from the ends of the chain. The scheme of data transmission in PEGASIS is shown in Figure 8. In this figure, if node \(C_{2}\) is the leader, it will pass the token along the chain to node \(C_{0}\) at first. Then, node \(C_{0}\) will pass its data toward node \(C_{2}\). After node \(C_{2}\) receives data from node \(C_{1}\), it will pass the token to node \(C_{4}\), and node \(C_{4}\) will pass its data towards node \(C_{2}\) with data fusion taking place along the chain.  
According to above discussion, the following is the advantages of PEGASIS: (1) This protocol is able to outperform LEACH for different network sizes and topologies, because it reduces the overhead of dynamic cluster formation in LEACH, and decreases the number of data transmission volume through the chain of data aggregation; (2) The energy load is dispersed uniformly in the network.  
Figure 8: The Token Passing Scheme in PEGASIS.  
To ensure that the fixed sensor node is not select as the leader and thus to prevent the subsequent early death of this sensor node, all sensor nodes act as the leader in turn [70].  
However, there are some disadvantages in PEGASIS: (1) It is the necessity of having a complete view of the network topology at each node for chain construction and that all nodes must be able to transmit directly to the sink. Thus, this scheme is unsuitable for those networks with a time varying topology [71]; (2) It is assumed that each sensor node can be able to communicate with the sink directly, but nodes usually use multi-hop communications with the sink in practical cases. Furthermore, long-range communications directly from the node to the sink can breed too much energy consumption; (3) The communication manner suffers from excessive delays caused by the single chain for distant nodes and a high probability for any node to become a bottleneck; (4) It is a difficult task for all nodes to maintain a complete database about the location of all other nodes in the network, furthermore the network is not very scalable because all nodes must have global knowledge of the network and employ the greedy algorithm.