Effective Clustering Algorithm of Wireless sensor network through clustered Mobile agents

Tables index

Veiw figure View Table

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.

Download as

Veiw figureFigures index

NEW
View larger figure in new window

Figure 1. Mobile Agent Technology

Download as

Veiw figureFigures index

Figure 2. Clustering of Mobile Agents

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].

Download as

Veiw figureFigures index

Figure 3. Example of Cluster Memberships

Where k1, k2……..k_mare the generalized Euclidean distance, the coefficients k = {k_i: 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 {A_ij} called router-agent incidence matrix is created which has i rows of routers and j columns of agents. An element a_ijof matrix {A_ij} is 1 if agent j require operation to be perform on router i, otherwise a_ij 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

Download as

Veiw figureFigures index

Figure 4. Path of routers

Table 2. Agents path table

Download as

Tables index

Veiw figure View Table

Table 3. Agent family and visited Routers table)

Download as

Tables index

Veiw figure View 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.

Table 4. Incidence matrix of router-agent

Download as

Tables index

Veiw figure View Table

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

Download as

Veiw figureFigures index

Figure 4. Structure of clustered of WSN with a mobile Agent

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.

Download as

Veiw figureFigures index

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

E_electhe power consumption of processing 1 bit of data

N_mem the number of members in a cluster

d⁴_toBs the distance between the cluster head and node Sink,

lE_elecN_mem is the power that N mem cluster members consume when each of them send out length of l data to the cluster head, lE_DA N_memis 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 & d⁴_{h1 to Bs} andd⁴_{h2 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

Download as

Veiw figureFigures index

Figure 7. Flowchart of selection of cluster head

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.

Download as

Veiw figureFigures index

Figure 8. FND vs. the distance between cluster heads

Table 5.

Download as

Tables index

Veiw figure View Table

Download as

Veiw figureFigures index

Figure 9. HNA vs. the distance between cluster heads

Table 6.

Download as

Tables index

Veiw figure View Table

Download as

Veiw figureFigures index

Figure 10. LND vs. the distance between cluster heads

Table 7.

Download as

Tables index

Veiw figure View Table