Comparative Anlysis of Clustering Techniques for Various Models of Node Deployment Strategies

Alan J. George and Deepa V. Jose

Department of Computer Science, Christ University,  Bangalore, Karnataka-560029, India

 

Corresponding author Email: alan.george@mca.christuniversity.in

DOI : http://dx.doi.org/10.13005/ojcst/10.01.32

ABSTRACT:

Energy efficiency has always remained a pressing matter in the world of Wireless Sensor Networks. Irrespective of the number of routing protocols that exist for Wireless Sensor Networks, only a handful can be named as efficient. Yet above all these routing protocols stands the emblematic one, the LEACH protocol. This research work is aimed at bringing forth a new routing strategy based on the LEACH protocol, which aims at improving the energy efficiency in Wireless Sensor Networks and applying the given clustering technique, in randomly deployed and fixed sensor network simulation environment using MATLAB. In depth simulations have proven that the proposed clustering strategy gives better performance compared to LEACH based on the lifetime of the Nodes. A comparative analysis of the rate of energy consumed on various node deployment strategies has also been carried out.

KEYWORDS: Delay; Energy efficiency; Energy consumed; Node deployment; Random deployment; Sensor nodes; Wireless sensor networks

Copy the following to cite this article: George A. J, Jose D. V. Comparative Anlysis of Clustering Techniques for Various Models of Node Deployment Strategies. Orient.J. Comp. Sci. and Technol;10(1)

Copy the following to cite this URL: George A. J, Jose D. V. Comparative Anlysis of Clustering Techniques for Various Models of Node Deployment Strategies. Orient.J. Comp. Sci. and Technol;10(1). Available from: http://www.computerscijournal.org/?p=4897

Introduction

With the rise of technology, there has emerged a need for automating the jobs of humans. From finding out where the car is parked to a car that can drive by itself, we find ourselves in a situation where we are more and more dependent on technology. Wireless sensors are a kind of sensor that have their own computing ability and power source and work autonomously or with human intervention, to sense and detect the environmental changes and revert the sensed data back to its origin. A wireless sensor network (WSN) is a collection of autonomous sensor networks that can sense the environmental conditions including sound, temperature, seismic activity etc. and cooperate and communicate with the nearby sensors and collectively pass the data to the origin or the Base Station (BS). Their response is always a measurable response, to certain change in the physical conditions. The WSNs could be limited to a few meters or could be spread across a few kilometers.  

The Wireless Sensor Network seems to operate on a “Many Tiny Principle” which states that the Wireless Sensor Networks can consist of hundreds and thousands of tiny devices, or nodes, that come at a very low cost, and are capable of performing computing, sensing, receiving and transmission. There exist various clustering schemes, which are proved to be energy efficient. In general a cluster hold two types of nodes in one cluster i.e. Cluster Head (CH) and its member nodes. Cluster member sense data from the environment and periodically send the data to their respective CH’s. The CH’s in turn send the data to the Base Station (BS). Hence the CH’s act as point of fusion, where data is aggregated and then sent to the BS, further reducing energy consumption. Many of the existing clustering schemes consider a homogeneous WSN’s where all sensor nodes are designed with the same battery energy. There also exists another scheme where heterogeneity of the nodes are taken into picture, where the schemes used for homogeneous nodes may not work efficiently for the heterogeneous nodes [1].

In general there are 3 categories of sensor nodes, first one being Passive and Omni Directional Sensors where the sensor nodes will merely be sensing the environment, and not manipulating it. Direction from where the data is sensed is not important. The second being Passive and narrow beam Sensors which are passive sensors and are concerned about the direction when the environment is sensed. The third beingActive Sensors which includes active sensing of the environment. A sensor node has limited sensing capability, computing capacity and power, hence these devices are distributed around or over a specific area of interest and in turn collecting valuable data. The various advantages and disadvantages of wireless sensor networks [2], are as follows:

Advantages of wireless sensor networks

• Network setup can be performed without any fixed infrastructure.
• Ideal for all places that are not reachable by man, such as seas, mountains etc.
• Flexible if an Ad-Hoc situation is available, when additional workstation is required.
• Cost for its implementation is cheap.
• Not secure, as intruders can collect all data.
• Speed of data transmission is less than the speed of a wired network.
• The network can be easily affected by the surrounding.

Disadvantages of wireless sensor networks

Applications of wireless sensor networks

Wireless Sensor Networks have a wide variety of applications. From household to office, to fields and mountains, these WSN’s can be stated as highly versatile. The ultimate goal of any WSN is to enable application in the real world. All these application differ drastically comparing other wireless scenarios. Some of the potential application domains are military, environment, healthcare and security. In military, sensor nodes can be used to locate or track enemy movements [3], [4], [5]. Figure (1) shows the various applications of Wireless Sensor Networks including problem specific applications and environment monitoring.

Figure 1: Applications of Wireless Sensor Network.   Click here to View figure

 

Related Work

Dongfeng Guo et al, in their paper talked about the improvement of LEACH protocol, and to make each nodes energy utilization more equalised, through which the total amount of data transferred and the network survival time can be further extended. Their improved method discusses about the two steps in LEACH protocol, which are selection of head cluster node that allows efficient selection of a cluster head, by increasing the probability, that nodes with higher energy become cluster heads, and the multi-hop path transmission which talks about the inter cluster routing strategy [6]. Comput et al. discussed about how an entire WSN can be made efficient using bio inspired cluster which is derived from honey bee. This paper discusses how establishing trust in the network gives various benefits such as solving the problem of access control, which cannot be solved using customary solutions [7]. An energy efficient method for node selection is proposed by Marques and  Ricardoin [8]. The authors discuss how the RPL protocol is the IETF proposed standard protocol for the IPv6 based multi hop WSN. The paper proposes an application driven extension to RPL which enables to increase the WSN lifetime by lessening the routing and forwarding functions of network mainly to nodes running the same network [8].

Rao[9] discusses and considers the implication of various deployment schemes for the connectivity and resilience of the WSN’s. This paper hovers over surveying four deployment models, namely, random, grid, group, and grid group. Another work by Pallavi Sahu et al. studies about the coverage of WSNs with their connectivity properties[10]. Reema Goyal et al. describes how the problem of coverage in WSNs is very important[11]. Sinha et al.[12], discusses about the periodic node deployment method and shows a statistical analysis on the same. The authors show that the method of mean and variance always converges to finite steady state values, thus ensuring the stability of the system. Wint Yi Poe et al.[13], covers all the major problems encountered in node deployment which is coverage, energy consumption and worst case delay. Here random and deterministic node deployment strategies are discussed for large scale wireless sensor networks for the 3 problem metrics mentioned above. The three methods discussed here are uniform random, square grid and a pattern based Tri-Hexagon Tilling (THT) node deployment. This paper proposes a novel strategy for calculating the relative frequency of exactly k-covered points, which use k-covered maps for both square grid and THT.

Problem Statement

Extending the lifetime of a WSN by increasing the energy efficiency has always been a matter of high priority for the researchers in this field. All methods that are used for node deployment are application oriented. Energy consumption for data transmission is highly influenced by the strategy used for node deployment. This research work focuses on the various strategies for node deployment, so as to perform a comparative analysis, of the energy consumed in varying situations of node deployment.

Proposed Work

An enhanced LEACH clustering protocol has been proposed. A comparative analysis of the performance of this clustering approach for random as well pre-defined deployment strategies based on the matrices residual energy of the network and delay, has been simulated.

Review of LEACH algorithm and its variants

The hierarchical category of wireless sensor networks has embedded in itself the concept of clustering. It is in this category that the LEACH algorithm actually lies. Clustering is a technique where the network allows for small groups called clusters to be formed, with each having a Cluster Head (CH), which requests for data from other nodes in its cluster. Each node passes data to its CH, which will later aggregate the data and pass it forward to the respective nodes. The entire process of clustering, and the selection of a CH is done using a probability factor, in the setup phase. The steady phase allows for data to be communicated to the Base Station (BS). During the setup phase, each node generates a random number between 0 and 1. The generated number is then compared to the threshold value, T(n). If its value falls below the threshold value, the node will be declared as the CH. The threshold value T(n) is defined as:

In Eq. (4.1), if n € G and 0 otherwise; where n represents the node, p is the desired cluster head percentage, r is the current round number, G is the set of all nodes that haven’t been cluster heads for the last 1/p rounds. The LEACH protocol ensures a balance of energy in the nodes, but the residual energy of the nodes is not taken into account while selecting the CH. In terms of large deployment, the single hop scheme where all nodes are allowed to transmit to the CH and the sink is also not encouraged. There exist several variants of the LEACH protocol. Table 1 shows the variations in the LEACH algorithm [14].

Table 1: Variants of LEACH Algorithm

Algorithm	Method Adopted
I-LEACH	Uses an energy function to balance consumption of energy among CH
LEACH-B	Brings forth an additional round after the preliminary CH selection
LEACH-C	Base Station is used as a centralised controller for clustering process
LEACH-F	Has fixed number of clusters that can be formed
LEACH-M	Brings forth the mobility factor
LEACH-ME	An improvement of LEACH-M
LEACH-R	A significant reduction in low energy nodes being selected as CH
LEACH-SCH	Calculates a new threshold value
LS-LEACH	A secure and light weight form of LEACH
MG-LEACH	Enables redundant node removal
N-LEACH	Uneven load distribution among nodes is avoided
TB-LEACH	CH are selected by seeing the nodes with the shortest time interval

 

Proposed Clustering Strategy

Assumption: Information about all the nodes is initially known to the BS

Step 1: Each node maintains information which contains the IDs of all nodes, their distance to the BS and their energy levels within its transmission range.

Step 2: Initially, CHs are constructed according to LEACH algorithm.

Step 3: After a predefined time, re-clustering happens; where the competition radius for clustering is varied based on the energy level and their distance to the base station to have non uniform cluster sizes.

Step 4: Within a cluster the CHs will be rotated based on the residual energy set to a threshold value.

Step 5: If the CHs energy level goes beyond the threshold hold value, re-clustering is performed; go to Step 2.

Step 6: After CH selection and clustering is done, data is routed to the BS.

Simulation Results

Network model

The classical energy network model and simulation parameters adopted by LEACH are considered here for simulation. A simple first order radio model have been assumed for the simulation experiments where the radio dissipates E _elec=50nJ/bit to run the transmitter or the receiver circuitry, and є_amp=100pJ/bit/m² for the transmitter amplifier to achieve an acceptable E_b/N₀ .An r² energy loss has been assumed due to channel transmission. Thus, to transmit a k-bit message a distance d using the first order radio model, the radio expends:

As Eq. (5.2) implies receiving is not a low cost operation, therefore, the protocol should not only minimize the transmission distances, but also the number of receptions and transmissions should be minimized.  In our simulations, we have used a packet length k of 2000 bits. The radio channel has been assumed symmetric such that the energy required transmitting a message from node A to node B is the same, as the energy required transmitting a message from node B to node A for a given signal to noise ratio (SNR).

Simulation results

The simulation has been performed using MATLAB. Initially ten sensor nodes were randomly deployed in an area of 10×10m². The energy consumed for 500 rounds under different scenarios of random deployment as well as of predefined deployment is simulated. The results of the same are represented in Fig. 2 and Fig. 3. The simulation parameters are given in Table 2.

Table 2: Simulation Parameters

No. of Nodes	10
Area of Simulation	10×10m2
Range of Sensor	5 m
Initial Energy at sensor	50 Joules
Transmission Energy	0.5 Joules
Receiving Energy	0.2 Joules
No. of static sink	1
Deployment model	Random, Pre-defined

 

Table 3 shows a comparison between the LEACH algorithm and the proposed algorithm and shows a significant improvement brought by the proposed algorithm. The table shows how the residual energy is higher even after 500 rounds. In the LEACH algorithm, after 400 rounds, the residual energy falls down to 62 Joules which is a significant drop for any WSN node, while the delay increases to 58ms. On the contrary, the proposed clustering technique shows the residual energy remaining at 78 Joules while the delay increases to 44ms after 400 rounds. The drop in the residual energy in the proposed clustering technique has been steady as compared to the sudden drop of residual energy in the LEACH algorithm.

Figure (2) shows a significant improvement in average of energy of nodes in the network while using the pre-defined deployment as compared random deployment. Figure (3) shows the significant fall in delay time in pre-defined deployment, as compared to random deployment.

Table 3: Comparison between LEACH Algorithm and Proposed Algorithm

Rounds	LEACH		Proposed Clustering
	Residual Energy (J)	Delay (ms)	Residual Energy (J)	Delay (ms)
100	94	15	98	8
200	83	23	94	15
300	64	32	86	24
400	62	58	78	44
500	53	72	74	48

 

Figure 2: Average Energy Vs Number of Rounds   Click here to View figure

 

Figure 3: Delay Time Vs Number of Rounds   Click here to View figure

 

Conclusion and Future Scope

According to the simulation results it is observed that the proposed clustering approach gives significant improvement in energy enhancement of the networks lifetime. As WSNs are used in a variety of applications, the node deployment requirements also differ. Here a comparison of the basic node deployment strategies, random node deployment and pre-defined node deployment is also carried out based on the residual energy of the network and the delay metrics. In the random deployment the overheads in clustering are more. In different scenarios, the random deployment shows lesser energy consumption and delay at different rounds. But in the case of fixed deployment uniform performance degradation can be observed. There are various other node deployment strategies to be explored. The area of deployment and the optimal sensor nodes has to be calculated. A real time application of the same will be the future focus.

References

1. D. Kumar, “Performance analysis of energy efficient clustering protocols for maximising lifetime of wireless sensor networks,” IET Wirel. Sens. Syst., vol September, pp. 9–16,  2013.
2. D. Bhattacharyya, T. Kim, and S. Pal, “A Comparative Study of Wireless Sensor Networks and Their Routing Protocols,” Sensors, vol. 10, no. 12, pp. 10506–10523, 2010.
   CrossRef
3. R. L. Cueva, S. Member, and R. G. Orquera, “Towards a New Volcano Monitoring System Using Wireless Sensor Networks,” pp. 1–5, 2012.
4. D. S. N. Kheirabadi, D. N. M. Kulkarni, and D. A. D. Shaligram, “Wireless Sensor Network Based Traffic Monitoring ; Overview And Threats To Its Security,” J. Glob. Res. Comput. Sci., vol. 2, no. 8, p. 6, 2011.
5. P. Rawat, K. D. Singh, H. Chaouchi, and J. M. Bonnin, “Wireless sensor networks: A survey on recent developments and potential synergies,” J. Supercomput., vol. 68, no. 1, pp. 1–48, 2014.
   CrossRef
6. D. Guo, L. Xu, “LEACH Clustering Routing Protocol for WSN.”, Preceedings of th International Conference on  Information Engineering and Applications,vol. 219,pp. 153-160, 2013.
   CrossRef
7. N. Comput, R. Ranjan, S. Abdur, and R. Sardar, “A bio inspired and trust based approach for clustering in WSN,”, Natural Computing, vol.15, no. 3, 2015.
8. B. Marques and M. Ricardo, “Energy-efficient node selection in application-driven WSN,” Wirel. Networks, pp. 1–30, 2016.
9. G. Sanjiv Rao, “A Beneficial Analysis Of Node Deployment Schemes For Wireless Sensor Networks,” Int. J. Adv. Smart Sens. Netw. Syst., vol. 2, no. 2, pp. 33–43, 2012.
   CrossRef
10. H. Zhang and C. Liu, “A Review on Node Deployment of Wireless Sensor Network,” IJCSI Int. J. Comput. Sci. Issues, vol. 9, no. 6, pp. 378–383, 2012.
11. R. Goyal, “A Survey on Deployment Methods in Wireless Sensor Networks,” Int. J. Adv. Res. Comput. Sci. Softw. Eng. Res., vol. 3, no. 7, pp. 540–543, 2013.
12. A. Sinha, S. Das, and A. V Vasilakos, “On Periodic Node Deployment in Wireless Sensor Networks : A Statistical Analysis.”,Journal of Network and Systems Management, 2011.
13. W. Y. Poe and J. B. Schmitt, “Node deployment in large wireless sensor networks: coverage, energy consumption, and worst-case delay,” Asian Internet Eng. Conf., pp. 77-84, 2009.
    CrossRef
14. Dr. Deepa V. Jose, Dr G.Sadashivappa,”An Augmented LEACH Strategy to Enhance Energy Efficiency in Wireless Sensor Networks”, IEEE Sponsored International Conference on Knowledge Collaboration in Engineering, ISBN: 978-1-4799-8619-4, p. 16, 27th -28th  March,2015.

---

This work is licensed under a Creative Commons Attribution 4.0 International License.