Effective Clustering Algorithm of Wireless sensor network through clustered Mobile agents

Kamla Deep, S Niranjanr, Yashpal Singh

Journal of Computer Sciences and Applications

Effective Clustering Algorithm of Wireless sensor network through clustered Mobile agents

Kamla Deep1,, S Niranjanr1, Yashpal Singh2

1Department of Electronics Communication & Engineering, Mewar University, Rajasthan

2Computer Science & Engineering Department, GITM, Kablana, Jhajjar, Haryana

Abstract

In wireless sensor networks, the mobile agent technology is used in data transmission from one cluster to another cluster. The Optimization of mobile agent in the routing within the clustering algorithm for wireless sensor networks to further reduce the amount of data transfer. the main objectives of wireless sensor network design is to improve the energy efficiency & effective utilization of sensor nodes to prolong the lifespan of a wireless network .This paper presents an effective clustering algorithm, which is an extension to the LEACH routing algorithm., this algorithm fully utilizes the location information of network nodes in routing to reduce the routing cost. Through a clustering approach of intelligent mobile agents, it is possible to reduce the cost of time for each individual agent, here the problem of Multiple Clustering of Mobile Agents (MCCMA) where the decision is to cluster mobile agents such that a group of similar intelligent mobile agents will visit a group of similar sensor nodes are compare with location based clustering algorithm of wsn. both of Simulation results indicate that these algorithm & approach of mobile agent & wireless sensor network Nodes can have balance nodes' energy consumption and prolong the network's life span. It also has good extensibility & stability

Cite this article:

  • Kamla Deep, S Niranjanr, Yashpal Singh. Effective Clustering Algorithm of Wireless sensor network through clustered Mobile agents. Journal of Computer Sciences and Applications. Vol. 3, No. 6, 2015, pp 154-161. http://pubs.sciepub.com/jcsa/3/6/9
  • Deep, Kamla, S Niranjanr, and Yashpal Singh. "Effective Clustering Algorithm of Wireless sensor network through clustered Mobile agents." Journal of Computer Sciences and Applications 3.6 (2015): 154-161.
  • Deep, K. , Niranjanr, S. , & Singh, Y. (2015). Effective Clustering Algorithm of Wireless sensor network through clustered Mobile agents. Journal of Computer Sciences and Applications, 3(6), 154-161.
  • Deep, Kamla, S Niranjanr, and Yashpal Singh. "Effective Clustering Algorithm of Wireless sensor network through clustered Mobile agents." Journal of Computer Sciences and Applications 3, no. 6 (2015): 154-161.

Import into BibTeX Import into EndNote Import into RefMan Import into RefWorks

At a glance: Figures

1. Introduction

Wireless sensor networks (WSN) are wireless network composed of spatially distributed autonomous devices using sensors to co-operatively monitor physical or environmental conditions, such as temperature, sound, vibration, pressure, motion or pollutants, at different locations. Cluster-based wireless sensor network saves energy by reducing the number of the nodes communicating with the base station. Energy is the scarcest resource of WSN nodes, and it determines the lifetime of WSNs. It Compared with ad hoc network design, one of the most important design objectives of WSNs is to minimize node energy consumption and maximize the network lifetime [2]. cluster-based model has a remarkable improving in energy efficiency. On the other hand, to transmit the data from node to node or head will consume much more energy than processing the data. So how to reduce the communication degree will be node to cluster the most essential problem [2].

In Table 1 show the difference b/w wireless sensor networks with mobile agent technology & other technologies in a significant way.

Table 1. Differences between WSNs and other technologies

1.1. Introduction to Mobile Agent:

In Figure 1 it is show about mobile agent technology, it is process of server – client host communicate with help of mobile agents . A mobile agent to mean an autonomous software entity with the capability of roaming among nodes in a network-aware fashion. A mobile agent can move from host to host to find the needed resources. They are communicate through wireless communication .

1.2. Work Processing of Mobile Agents

The mobile agent to begin with when arrives at a node for the first time, stores its code at that node for future visit without carrying its code and sending the result to the sink node. Mobile agent also copies its processing code into the memory of each node in the first round. Once the whole task is completed, all those nodes discard the processing code. The agent performs the filtering function when it acquires the data.

For example to estimate temperature, if node 1, node2 and node3 are neighboring node, they must have similar temperature. We suppose that node1 estimate the temperature of thirty degree, node3 estimate the temperature of thirty two degree. node2 is located between node1 and node3. node2 must have the temperature either from thirty to thirty two or similar degree. But, if node2 estimates the temperature over forty or less than ten degree, Sensing data of nodes can be fault data. In this way agents can judge the data When the network connection is not available the mobile agent can save its status on secondary memory and later migrate to the home network when the connection is available. Software agents need not always travel across a network to communicate with information sources, or other agents. They work on message passing systems for agents [4].

In Figure 2 show that user program is communicate with other user program in network data is moving through mobile agents, it is like a clustering of mobile agent.

2. Related Work

Since sensor network works with limited energy, there has been an extensive research work toward energy efficiency of sensor. Liang Zhao [7] proposed a Medium-contention based Energy-efficient Distributed Clustering (MEDIC) scheme, through which sensors self organize themselves into energy-efficient clusters by bidding for cluster headship.. Low Energy Adaptive Clustering Hierarchy (LEACH) algorithm is applied to decompose the network into clusters, with one head for each. The main purpose of this technique is to collect the data by a mobile agent and to send them together to minimize the transmission [4].

The MA is a special kind of software that propagates over the network either periodically or on demand (when required by the applications). It performs data processing autonomously while migrating from node to node. Q. Wu et. al. [6]. The use of MAs in computer networks has certain advantages and disadvantages like code caching, safety and security, depending on the particular scenario. A lot of research has been done on power utilization in WSN various researchers have identified different clustering methods, routing algorithms, scheduling algorithms and load balancing algorithms. Energy consumption is also considered as a factor in the above cluster head selection. In the reality, when the nodes deployed in environment, the workload on data collection and transfer is varies from node to node. Because node energy consumption is directly proportional to the amount of data and distance squared of transferred data, a node sends data and the farther it is away from the cluster head, the more energy is consumed with the node [2].

It is assumed that sensor network is divided into clusters. In traditional client/server approach, data is transmitted directly to sink node which will reduce the life span of sensor network. To overcome this approach clustering approach is used, in which sensors are clustered using clustering algorithm. Sensor nodes send all sensed data to sink node whether all data is necessary or not. This approach requires a lot of bandwidth and increase network traffic. Mobile Agent is programs , which move sensor to sensor to gather information and transfer only specified information to sink node.

3. Clustering for Mobile Agents

Cluster analysis is concerned with the grouping of alternatives into homogeneous clusters (groups) based on certain features. Three well-known clustering strategies are hierarchical clustering

(Pandit, Srivastava, and Sharma 2001; Dias, Costa, and Climaco 1995), graph-theoretic methods (Matula 1977) and conceptual clustering (Michalski and Stepp 1982, 1983). Conventional clustering approaches involve two main factors: 1) distance (or dissimilarity) measurement, and 2) cluster centers.

By clustering mobile agents, cost of time for each agent to travel to its required routers, can be reduced [16]. Routers have certain capabilities and can process certain requests of each intelligent agent. We propose in our present work a new application to clustering. We discuss how clustering methods can be applied and used for MCCMA communication network problems. Intelligent agents are grouped into cluster in such a way that each cluster has similarity in responding to a group of routers [5].

In this way it helps to reduce demand imposed upon a network for a set of required task to be performed. . Suppose that an intelligent mobile agent must visit a certain number of routers in order to complete the task that it is assigned to. If required, additional agents can be assigned of identical capabilities. Such acquiring will increase cost .Hence each agent can be duplicated. In a simpler way, the procedure is to find cluster center Cr and then cluster all alternative objects into a group according some rules. First of all, we define similarity measurement d(X,C) as the generalized Euclidean distance between objects Xi and center Cr , r=1,2,3,4……..n [6].

Where k1, k2……..km are the generalized Euclidean distance, the coefficients k = {ki: i = 1, ... m} can be used to represent indirectly the important index of each attribute of the alternatives. An objective X belongs to cluster r if and only if d(X, Cr) < d(X, Ct) | t = 1, 2... R and t < r.

3.1. Clustering Algorithm Steps:

Step 1: Consider unclassified wireless sensor network area of (X*Y) meter having N number of routers and M number of agents.

Step 2: Sink node dispatch mobile agents with requirement of specific task to wsn. Mobile agent migrate from first to last sensor node to perform specified task.

Step 3: Route table of agents is created corresponding to their routers.

Step 4: A matrix {Aij} called router-agent incidence matrix is created which has i rows of routers and j columns of agents. An element aij of matrix {Aij} is 1 if agent j require operation to be perform on router i, otherwise aij is 0.

Step 5: Based on route table and incidence matrix of router-agent family, agents are divided into clusters. Agents perform operations on some specific routers are put into clusters.

Step 6: The few entries outside the diagonal blocks represent operations to be performed out-side the assigned group router cells. These elements are called exceptional elements.

We consider an example and divide into clusters

Table 3. Agent family and visited Routers table)

Here Table 3 is divide the agents into two clusters. That is, the primary cluster for handling 2,3,5 agents corresponding router are A,E,C and for 1,4,5 agents corresponding routers are B and D. Here in above example agent 5 used in both clusters so if we can afford the cost of more agents then we will acquire additional agents, the duplicated agents.

The router-agent cell formation is a strategy to group routers into cells and agents into families. Families of agents can then be completely processed in their corresponding group router cells [4].

In recent years, clustered routing protocol has gained increasing attention from researchers because of its potential of extending WSN lifetime. the first distributed and clustered routing protocol with low energy consumption designed and implemented [9], After that, some modified algorithms based on LEACH were proposed, such as LEACH-C, LEACH-E, and LEACH-F. This paper presents a new improved LEACH algorithm. The rest of the paper is organized as follows

4. Problem Formulation

The routing protocol design for WSNs is typical because WSNs different from traditional wireless ad hoc networks in many ways [8]

No global ID : The number of sensor nodes could be very large in a WSN and maintaining global IDs for them is too costly and unrealistic. Therefore, no global ID is maintained in a WSN, which is different from traditional IP- based routing protocols.

Many-to-one communications: Almost all applications require multiple sensor nodes to send data to a specific node.

Data redundancy: In different cases many sensors nodes may obtain large amount of the same or similar data. So there is a huge data redundancy in the network.

Limited resources: Sensor nodes are equipped with limited resources, such as power, computation capability and memory.

LEACH cluster head is selected using T(n) as shown in Figure 1. Where T(n)is calculated according to

In this formula, p is the percentage of cluster heads over all nodes in the network, i.e., the probability that a node is selected as a cluster head; r the number of rounds of selection; and M is the set of nodes that are not selected in round 1/p. As we can see here, the selection of cluster heads is totally randomly

Energy consumption is also considered as a factor in the above cluster head selection. In the reality, when the nodes deployed in environment, the workload on data collection and transfer is varies from node to node. Because node energy consumption is directly proportional to the amount of data and distance squared of transferred data, a node sends data and the farther it is away from the cluster head, the more energy is consumed with the node. Therefore, when a WSN has been in operation with LEACH protocol for a long time, it will experience unbalanced remaining energy among nodes [5].

For an energy unbalanced network, if the lifetime& prolong of cluster heads is less than the expected network lifetime, then blind & unexpected nodes will appear and the network life and routing efficiency will be compromised. Because cluster heads are randomly selected, it is possible the scenario illustrated in Figure 2 occurs, in which two or even more cluster heads are very close to each other.

Figure 5. Multiple cluster heads appear in a small region with LEACH protocol .

In Figure 5, there are five different region with different type of nodes where H1 and H2 are two cluster heads, nodes ■ and ▲ are their cluster members, respectively. H1 and H2 are very closely located. It is multiple cluster heads appear in a small region ,

According to data communication model, A cluster head(CH) consumes the energy is the sum of that consumed in receiving data and that in sending data, as described in Eq. (1):

(1)

l is the length of data,

εmp the power consumption of transferring l bit of data

Eelec the power consumption of processing 1 bit of data

Nmem the number of members in a cluster

d4toBs the distance between the cluster head and node Sink,

lEelecNmem is the power that N mem cluster members consume when each of them send out length of l data to the cluster head, lEDA Nmem is the power that the cluster head consumes when it receives data of length l from its cluster members.

It follows from eq (1) that the amount of energy that cluster heads H1 and H2 consume during data transfer is

(2)
(3)

Where Nmem1 and N mem2 the number of members in clusters H1 and H2, respectively & d4h1 to Bs andd4h2 to Bs the distance between the two cluster heads and node Sink,

Therefore, The total energy consumed by the two clusters is

(4)

When H1 and H2 are very close, we can have

(5)

The total energy consumption when there are two cluster heads is approximately twice of that when there is only one cluster head. Now, it is clear that when multiple cluster heads are randomly selected within a small area, a big extra energy loss occurs in clustering algorithm. The amount of lost energy is approximately proportional to the number of cluster heads in the area. Of course, there is a precondition on this conclusion, that is, cluster heads are very closely located and the distance between them becomes negligible or very small.

5. Protocol Performance

The design objective of the routing protocols for wireless sensor networks varies with the network application and operational environment. LEACH protocol is suitable for the WSNs under the following assumptions [2]:

• Sensor nodes are static in nature

• The Sink node is fixed and far away from the wireless network. Thus we can ignore the energy consumed by the sink node. We assume that it always has sufficient energy to operate.

• All senor nodes are identical and charged with the same amount of initial energy. All communication channels are identical. The energy consumption of transferring data from node A to node B is the same as that of transferring the same amount of date from node B to node A.

• Every node can directly communicate with every other node, including the sink node. The Sink node is fixed and far away from the wireless network. Thus we can ignore the energy consumed by the sink node. We assume that it always has sufficient energy to operate.

• The coordination between nodes is done through wireless communication, which costs much. This is one of the major reasons that the LEACH protocol selects cluster heads randomly. WSNs are autonomous networks. Sensor nodes are independent with each other As we discussed before, this approach may cause the waste of energy because of unbalanced cluster head distribution. To solve this problem, we propose a new approach to selecting cluster heads. We assume that:

• After deployment, sensors are able to know their positions through GPS, or before deployment, their positions are accurately decided.

If we change the procedure of the calculation of T(n) during the cluster head generation such that cluster heads are produced progressively, then a node could decide if it is suitable to be a new cluster head based on the locations of existing cluster heads and its own location. More specifically, if any node is very close to any existing cluster head, then that node will give up the attempt to be a cluster head.

As shown in Figure 6, The network is divided into seven parts. R1, R2, R3, R4, R5, R6, R7 regions. Nodes in R1 start to compete for cluster heads at time 0, then nodes in R2 start with a delay, and then nodes in R3 start with a delay after nodes in R2 are finished, and so on. During the process, nodes need to send their location information to the base station

Nodes in region R1 will used for being a cluster head. When a node is selected as a cluster head, it will broadcast the information to nodes nearby. Nodes in region R2 will receive the message. Thus, when nodes in this region compete for being cluster head, the location information of the cluster head in region R1 will taken into consideration. If a node in R2 is close to the cluster head in R1, the node will be discarded. The cluster heads in all other regions will be generated in the same way. Some nodes quit the competition for cluster head, the total number of cluster heads can be reduced, which is not good for saving the network energy. The cluster heads generated with this progressive approach will not be close to each other.

Our algorithm to solving this problem is, when a node is excluded in the cluster head selection, a message is broadcast to other nodes and T(n) will be modified to increase the probability of others nodes being selected as cluster heads. The modified T(n) is:

(6)

In eq (6), k is the number of nodes that are excluded from the cluster head selection due to the location reason, with an initial value of 0. When k increases, then T(n) also increases ,which will ensure sufficient number of cluster heads will be generated by the progressive algorithm.

To facilitate the explanation of our improved algorithm, we introduce the following notations:

• BS: The base station or node Sink

• Si : The i-th sensor node

• Hj: The j-th cluster head

• ID(Si) : ID of the i-th sensor node

• Mem (Cj): Members of the j-th cluster

• Mem(Cj)i: The i-th members of the j-th cluster

• Loc(Si) :Location of the i-th sensor node

• Delay(Si): Time delay that the i-th sensor node start to compete for a cluster head Num(Giveup) Number of discarded cluster heads

Operation of concatenation

5.1. Distribution in Cluster Head Selection

After the deployment of sensor nodes,

1. Acquire all nodes’ location information (through GPS technology or known prior to its deployment) and report it to the base station.

2. The base station decides Delay (Si) for every node based on the geographic distribution of all sensor nodes.

3. Delay (Si) = 0 for those in the region to start first.

As illustrated in Fig. 7, nodes in R1 start to compete for cluster heads at time 0, then nodes in R2 start with a delay, and then nodes in R3 start with a delay after nodes in R2 are finished, and so on. During the process, nodes need to send their location information to the base station:

The base station needs to send the delay information to each node:

5.2. Selection of Cluster Heads

Set Num(Giveup) to 0. Start with the nodes in R1. If a cluster head is generated from R1, broadcast a Hello package and Num(Giveup).

When nodes in R1 are finished, consider nodes in R2.Now the cluster heads generated in R1 are as a reference points. The distance between a node in R2 and any cluster head in R1 is a factor in selecting the node as a cluster head, as well as the random value of T(n). If all conditions are satisfied, then broadcast the Hello message and Num(Giveup)

Otherwise, only broadcast Num(Giveup). When nodes in other region receives this message, they will increment Num(Giveup) by 1, and then modify T(n) to increase the probability of being selected as cluster head.[2]

Repeat the above process until all nodes in the network are considered.

6. Performance Analysis

6.1. Simulation Scenario and Parameters

In order to evaluate the performance of different algorithms, we use two scenarios to simulate the algorithms. In scenario 1, the region size is 200 meters by 200 meters, the number of nodes is 200, and the BS is located at (50, 175); In scenario 2, 400 sensor nodes are distributed in a 400 meters by 400 meters region and the BS is geographically located at (150, 350).

6.2. Simulation Results:
6.2.1. Performance Measurements

In a wireless sensor network, the computing capacity and stored energy of a node is very limited. In particular, the limited energy affects the lifespan of information quality of the network. For this reason, we evaluate the algorithms based on the efficiency of the network energy consumption. We use two performance indices:

Lifespan: The lifespan of a sensor network is the time span from the beginning of the network operation to the instant that the network can no longer provide readable information, measured in the number of rounds. It can be measured in three ways: FND (First Node Dies), HNA (Half of the Nodes Alive), and LND (Last Node Dies).

Data accuracy: The accuracy of data received by the BS. When more the data is received, the high the accuracy after data fusion. The data accuracy is measured by the total data sent by all nodes in the lifespan of the network.


6.2.2. Analysis of Simulation Results

We compare the performance of the original LEACH clustering protocol and our progressive clustering protocol. Figure 8, Figure 9, and Figure 10 show the change of FND, HNA and LND over the distance between cluster heads. As we can see, the lifespan of the network increases when the distance between cluster heads increases and reaches the cap when the distance is around 35 and 45. After that, when the distances increases further, the number of cluster heads goes down, and the energy consumption of the network goes up, which leads to the decline of the lifespan and data accuracy.

Figure 11. Comparison of the lifespan of the two protocols

It is clear from the simulation results shown in Figure 6 that the lifespan of the new progressive clustering protocol is longer than that of the original LEACH protocol. The data transferred with the new protocol is 1/3 more than that with the old protocol, and the lifespan of the network with the new protocol is almost doubled compared with that of the old protocol

7. CONCLUSION

The cluster head generation algorithm with the original LEACH clustering protocol can cause unbalanced distribution of cluster heads, which often leads to redundant cluster heads in a small region and thus cause the significant loss of energy. To solve this problem, we proposed a progressive algorithm for the cluster head selection. Simulation results show that our algorithm is much more efficient and can double the lifespan of a wireless sensor network. Such results are obtained under additional conditions, i.e., known location information and ability to adjust data transmission power based on distance. The algorithm can be easily implemented. We simulated the performance of our algorithm in two scenarios, one is a dense network – with 100 nodes distributed in a 200 meters by 200 meters area, the other one is a less dense network – with 200 nodes distributed in a 400 meters by 400 meters area

Our future work includes:

1. In order to evaluate the network performance more precisely, we should consider more extreme cases.

2. Our new approach differs from the existing approaches, such as LEACH-C/E/F and DCHS, in that they all consider energy consumption as a factor in protocol improvement. We will explore the possibility of combining the strengths of these different approaches.

3. There is an assumption on the selection of new cluster head and key management scheme, which is the locations of nodes in a network are known. In reality this assumption may not be true. We will improve our protocol to deal with such situations.

References

[1]  L. Sun, J. Li, Y. Chen and H. Zhu, “Wireless Sensor Networks,” Tsinghua University Publishers, May 2005.
In article      
 
[2]  Lin SHEN and Xiangquan SHI” A Location Based Clustering Algorithm for Wireless Sensor Networks, Vol. 13, No. 3, September 2008,208-213, International Journal Of Intelligent Control And Systems.
In article      
 
[3]  Abdelhakim Hamzi1, Mouloud Koudil1, Jean-Paul Jamont2, Michel Occello “ Multi-Agent Architecture for the Design of WSN Applications” Wireless Sensor Network, 2013, 5, 14-25.
In article      View Article
 
[4]  Yashpal Singh, ,Kamal Deep, and S Niranjan “Multiple Criteria Clustering of Mobile Agents inWSN” International Journal of Wireless & Mobile Networks (IJWMN) Vol. 4, No. 3, June 2012.
In article      
 
[5]  www.google.co.in/cluster of mobile.
In article      
 
[6]  Malakooti, B., V. Raman, “Clustering and Selection of Multiple Criteria Alternatives using Unsupervise and Supervised Neural Networks", Journal of Intelligent Manufacturing, Vol. 11, 2000, 435-453.
In article      View Article
 
[7]  Liang Zhao, Qilian Liang, “Medium-contention based energy-efficient distributed clustering (MEDIC) for wireless sensor networks”, International Journal of Distributed Sensor Networks, 3, 2007, 347-369.
In article      View Article
 
[8]  V. Handziski and A. Kopk, “A common wireless sensor network architecture,” Technical Report TKN-03-012.
In article      
 
[9]  Telecommunications Networks Group, July 2003, 10-17. F. Ren, H. Huang and C. Lin, “Wireless sensor networks,” Journal of Software, 2003, 14(7):1282 -1291.
In article      
 
[10]  M. Yu, A. Malvankar, and W. Su, “An Environment Monitoring System Architecture Based on Sensor Networks,” Int. J of Intelligent Control and Systems, 10(3):201-209, 2006.
In article      
 
[11]  C. Zhang, M. C. Zhou, and M. Yu, “Ad hoc network routing and security: a review,” International Journal of Communication Systems, 20:909-925, 2007.
In article      View Article
 
[12]  L. Cui, H. Ju and T. Li, “Advances in wireless sensor networks,” Journal of Computer Research and Advances, 2005, 42(1): 163-174.
In article      
 
[13]  J. Li and H. Gao, “Research advances in wireless sensor networks,” Journal of Computer Research and Advances, 2008, 45(1): 1-15.
In article      
 
[14]  B. Shen, S. Zhang and Y. Zhong, “Clustering protocols of wireless sensor networks,” Journal of Software, 2006, 17(7):1588-1600.
In article      View Article
 
[15]  Z. Yan and B. Zheng, “Wireless sensor networks,” Journal of Computer Engineering and Application, 2005, Vol. 15.
In article      
 
[16]  Chan, H.M. Milner, D.A., “Direct Clustering Algorithm for Group Formation in Cellular Manufacturing,” Journal of Manufacturing Systems, 65-75, 1982.
In article      View Article
 
  • CiteULikeCiteULike
  • MendeleyMendeley
  • StumbleUponStumbleUpon
  • Add to DeliciousDelicious
  • FacebookFacebook
  • TwitterTwitter
  • LinkedInLinkedIn