Review Of Chain Based Hierarchical Protocols Computer Science Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Keywords - WSN; chain; routing protocols; network lifetime; energy efficiency.

Advanced research in wireless communications have developed the multifunctional, low cost, low power, sensor nodes which are small in size and these sensor nodes communicate in short distances. In recent years, Wireless sensor networks have achieved a great attention. A WSN consists of battery powered and resource constraint sensor nodes that are randomly deployed for sensing and collecting the data from the nearby surroundings and further reporting the information to the remote Base station. Wireless sensor nodes consist of sensing, processing and communicating components. Large number of wireless sensor nodes are deployed densely in WSN. An important feature of sensor network is that instead of sending raw data to the nodes, they transmit only partially processed and required data by using their processing capabilities. Wireless sensor networks are employed in some of the applications areas such as health, military, habitat monitoring and disaster supervising.

This paper is organized as follows: Section 2 discusses the architecture of wireless sensor network. In section 3, the design factors of WSN are discussed. In section 4 various applications of wireless sensor network are studied. Section 5 discusses the chain formation in WSN. In Section 6 chain based routing protocols are analyzed. The conclusion remarks follows in Section 7.


Wireless sensor nodes are scattered in a sensor field and they have the capability to collect the data and then route the data back to the sink by using multihop infrastructure less architecture as shown in Fig. 1. Then, further the sink communicates with the task manager node or user through Internet. Design of wireless sensor network depends on some factors such as transmission media, scalability, production cost, operating environment, fault tolerance, hardware constraints and the power consumption[1].

Fig.1: Sensor nodes scattered in a sensor field[1]


For designing good routing protocols for WSN, it is quite important to study the parameters which are relevant for the sensor applications[2].

There are various ways by which the properties of network routing protocol can be evaluated and they are:

I. Ease of Deployment

WSN contains thousands of sensor nodes that are required to be deployed in dangerous or remote environments for extracting the information which would have been otherwise impossible. Three different phases of deployment of wireless sensor nodes are:-

Phase-I: Pre deployment and deployment phase

Deployment of sensor nodes can be done in a mass or one by one. If the sensor nodes are to be placed one by one then it is usually done by human or robot. If the sensor nodes are to be deployed in a mass then it can be done by dropping from rocket or plane.

Phase-II: Post-deployment phase

If the sensor nodes have been deployed, then any changes in the position of sensor nodes, its reliability, energy will change the topology.

Phase-III: Redeployment phase

According to the requirement, redeployment of sensor nodes can be done[1].

II. System Lifetime

Since it is impossible to recharge the sensor node batteries therefore the WSNs must prolong for as long as possible. In order to enhance the network lifetime, protocols should be designed in such a way so that they are energy efficient[2].

III. Latency

Since the information obtained from the wireless sensor networks is time sensitive, therefore it is necessary to receive the information in a timely manner[2].

IV. Quality

Quality of WSN depends on the quality of the aggregated information set, therefore, the protocols should be designed in order to optimize a unique and application specific quality of WSN[2].


I. Industrial Applications

Industrial applications provides public safety, improves the preventive maintenance programs, helps to automate the data acquisition from the remote sensors, conservation, efficiency and control[3] as shown in Fig.2.

Fig.2: Industrial control applications[3]

II. Home Applications

Home applications provides easy management of heating and cooling systems in home, safety, conservation, control, can capture water and gas utility usage data, sensing applications in order to optimize the natural resources consumption and installation and upgradation of home control system[3] as shown in Fig.1.3.

Fig.3: Home control applications[3]

III. Military Applications

Various military applications are monitoring friendly resources, targeting, nuclear, biological and chemical attack[3].

IV. Medical Applications

Tracking as well as monitoring the patients and doctors, drug administration[3] as shown in Fig.4.

Fig.4: Use of Code Blue for emergency response: PDA displaying real time vital signs of multiple patients[3]


In WSN, chain is formed by connecting different wireless sensor nodes as shown in Fig.5. One of the important applications of WSN is data collection and an efficient way for collection of data is chaining. PEGASIS i.e. Power Efficient Gathering in Sensor Information Systems was the first protocol that was devised for the concept of chaining.

Fig.5: Chain formation in Wireless Sensor Network

Chain based routing is a significant routing scheme in which the sensor nodes are linked in advance into single or multiple chains. Each node in data dissemination phase communicates with closest neighbors and then takes the turns for transmitting the aggregated data to the base station. Even though the chain based routing schemes balances the node energy effectively and enhances the network lifetime but causes the redundant paths and transmission delays[4].


According to the current situation of wireless sensor network, many excellent and effective routing algorithms have been proposed. Some of them adopts cluster based system and the basic cluster based protocol is LEACH[5-7] and some of them adopts chain based system and the basic chain based protocol is PEGASIS[8-9].

Power Efficient Gathering in Sensor Information System (PEGASIS)

The concept PEGASIS algorithm is based on LEACH. The main idea in PEGASIS is formation of chain among all the sensor nodes so that each node can transmit to and receive from the closest neighbor. Aggregated data moves from one node to another node, then gets fused and finally cluster head transmits to the base station. Sensor nodes take turns while transmitting to the base station so that there is reduction in average energy spent by each node per round. PEGASIS uses greedy algorithm for the construction of chain.

Some of the advantages of PEGASIS algorithm are:-

Sensor nodes communicate only with the neighboring nodes.

Distance between the connected nodes has been reduced.

Some of the disadvantages of PEGASIS algorithm are:-

Time delay is created during data transmission.

Problem of long chain is always high.

Technique of selecting the cluster is not appropriate for load balancing[10].

PEGASIS Double Cluster Head (PDCH)

Energy efficiency is one of the important parameter of WSN. The main idea of PDCH is load balancing and to extend the network lifetime and is based on PEGASIS. In PEGASIS, there is only one cluster head in each chain but in PDCH, there are two cluster heads in each chain. It uses hierarchical structure for avoiding the long chain existing in PEGASIS[10-11].

The two cluster heads used in PDCH are referred to as bottom level cluster head and super level cluster head. The procedure of PDCH is described as follows:-


In hierarchy structure of PDCH, base station is at the center of circle and distance from every node to BS decides the level to which it belongs. Each node will receive the signal from base station and then according to the signal strength will detect the distance to the base station. Number of nodes, density distribution of nodes, location of base station, affects the number of levels in the hierarchy of PDCH and level has its own ID. First level ID is 0 and it belongs to BS, second level ID is 1 and it belongs to nodes closest to BS and so on.

Fig.6: Hierarchy

Process of building chain

Fig.7: Process of building chain

If the nodes have more than one branch chain, then they have more chances to be selected as the cluster head as compared to other sensor nodes in different levels.

Double cluster head algorithm

There are two cluster heads in one chain i.e. main cluster head and another is secondary cluster head. The function of main cluster head is data receiving and fusion and then finally transmits the data to secondary cluster head. The function of secondary cluster head is to transmit the local level and lower level data to upper level cluster head from main cluster head.

Fig.8: Double cluster head method

PDCH outperforms PEGASIS by eliminating overhead during cluster formation, minimizes the distance and limits the number of transmissions and receptions among all sensor nodes by using only one transmission to base station in each round.

C. Energy-Aware PEGASIS-Based Hierarchical Routing Protocol (EAPHRN)

EAPHRN is one of the hierarchical routing protocol for stationary WSNs. This protocols enhances the lifetime as well as the throughput of WSN. It eliminates the long chain problem of PEGASIS by using new chain leader election technique. The main idea of this protocol is to make WSN optimal in terms of power consumption and to determine a low cost chain which will cover all the nodes in a network.

Fig.9: Long chain problem in PEGASIS

In PEGASIS greedy algorithm is used and this protocol makes an enhancement by using new algorithm that does not uses the concept of connecting to the immediate next neighbor node. EAPHRN connects to a random node which is not located far than Distance Threshold. This protocol algorithm is categorized into two phases i.e. chain setup phase and the other is leader election method.

Fig.10: EAPHRN

Chain Setup Phase

Distance Threshold is computed before the chain is constructed. Each node computes LDT i.e. Local Distance Threshold. LDT is the average of distance between the wireless sensor node and closest n nodes.

LDT is equated as the following:-


After computing LDT, DT is computed and sends it to all the sensor nodes in WSN for forming the chain.

DT is equated as the following:-


where, m indicates the number of nodes in WSN.

Leader Election Method

When the chain formation is over, election of chain leader is done which is actually the closest sensor node to Base Station. Then each node senses and forwards the aggregated data to the next node in chain. In turn the node fuses its own data and then forwards to next node and so on.

Energy consumption ration equation is as the following:-

Ratio= (EnCons/ EnResidual) * 100%

where, EnCons refers to the amount of energy which is consumed if the sensor node is selected as a leader.

EnResidual refers to the amount if residual energy is in the sensor's node battery[12].

D. Chain Based Hierarchical Routing Protocol (CHIRON)

CHIRON is an energy efficient routing protocol which alleviates the deficiencies such as redundant transmission and data propagation delay. It is based on Beam Star concept that splits the sensing field into smaller areas which creates multiple shorter chains. The operation of CHIRON is categorized into three main phases:-

Group Construction Phase

This phase divides the sensing field into number of smaller areas that creates multiple shorter chains in order to reduce redundant transmission path and data propagation delay.

Chain Formation Phase

The nodes in each group Gx,y are linked to form a chain cx,y.

Leader Node Election Phase

A leader node is selected in each group chain for collecting and then forwarding the whole data to the base station.

Data Collection and Transmission Phase

After the completion of three phases, the data is collected and transmitted. The procedure of transmission in CHIRON is same as compared to PEGASIS[4].

E. Chain Routing Protocol based on Coordinate Clustering (CRBCC)

In WSN, energy efficiency is an utmost priority to enhance the network lifetime. A two layer hierarchical routing protocol i.e. CRBCC ensures short delay and minimum energy consumption. Firstly, this protocol forms clusters along y coordinates and then by Stimulated Annealing, it selects chain leader along x coordinates. At last, it makes chain routing between the chain leaders by SA method. The procedure of CRBCC is categorized into various phases i.e. Route computation in cluster, Route computation between clusters, Route formation in cluster, Route formation between clusters and Data Gathering Phase[13].


PEGASIS is a routing protocol which is based on greedy algorithm but there is a problem of long chain in PEGASIS. PDCH extends the network lifetime and maintains load balancing by utilizing two cluster heads. EAPHRN is an hierarchical routing protocol that attempts to increase both the lifetime and throughput of stationary WSN. EAPHRN is based on PEGASIS and eliminates the problem of long chain existing in PEGASIS. CHIRON is suitable for large wireless sensor networks and utilizes the Beam Star concept. CHIRON has the benefits of both chaining and clustering where the geographical area is divided into zones. CRBCC is also an hierarchical routing protocol which is not only energy efficient but also works in timely manner to meet the real time requirements.