ENERGY BALANCING INTELLIGENT CLUSTRING PROTOCOL FOR WIRELESS SENSOR NETWORK

Navroop kaur Chattha

ENERGY BALANCING INTELLIGENT CLUSTRING PROTOCOL FOR WIRELESS SENSOR NETWORK

Navroop kaur Chattha
Dept. of Computer Science and Engineering, Yadavindra College of Engg Talwandi Sabo, Punjab, India

Corresponding Author: Navroop kaur Chattha, E-mail: navroop04@gmail.com

Related article at Pubmed, Scholar Google

Visit for more related articles at Journal of Global Research in Computer Sciences

Abstract

Recent advances in microelectronics have made feasible the deployment of sensor networks for a variety of monitoring and surveillance tasks. The severe energy constraints met in such networks make imperative the design of energy efficient protocols for communication. One method is to use Multiple-Input Multiple-Output (MIMO) links. The multiple antennas allow MIMO systems to perform pre coding (multi-layer beam forming), diversity coding (space-time coding), and spatial multiplexing. In this paper, we propose a Energy balancing intelligent clustering protocol based MIMO scheme which is an improvement of LEACH based MIMO scheme. Proposed scheme aims at balancing the energy consumption in every cluster, enables multihop transmissions among the clusters by incorporating cooperative MIMO scheme through the selection of cooperative sending and receiving nodes and prolonging the network lifetime. A fitness function is used to balance the energy consumption in every cluster according to the residual energy and positions of nodes. In every round the node called auxiliary cluster-head calculates the position of the cluster head using Bacterial Foraging Optimization Algorithm (BFOA).

Keywords

Cooperative MIMO, LEACH protocol, multihop communication, Bacterial Foraging optimization (BFO) algorithm, network lifetime, wireless sensor network, STBC.

INTRODUCTION

Recent advances in wireless technologies and microelectronics have made feasible, both from a technological as well as an economical point of view, the deployment of densely distributed sensor networks [1]. Although today’s sensor nodes have relatively small processing and storage capabilities, driven by the economy of scale, it is already observed that both are increasing at a rate similar to Moore’s law. In applications where sensors are powered by small batteries and replacing them is either too expensive or impossible, designing energy efficient protocols is essential to increase the lifetime of the sensor network. [13]. Due to limited energy and the difficulty in recharging a large number of sensor nodes energy efficiency and maximizing the network lifetime are the most important design goals of a sensor network. [2]

LEACH (low-energy adaptive clustering hierarchy) is a self-organizing, adaptive clustering protocol that uses randomization to distribute the energy load evenly among the sensors in the network. [3] In LEACH, all the nodes organize themselves into local clusters according to a certain procedure, with a number of nodes acting as the cluster-heads and other nodes acting as the members of the clusters. Because the cluster-head consumes more energy than the member node, LEACH includes randomized rotation of the cluster-head positions in order not to drain the energy of a particular sensor. In a cluster, the cluster-head performs local data fusion to “compress” the amount of data being collected from the members of the cluster and transmits the processed data to the base station in order to reduce energy consumption and enhance the lifetime of the whole sensor network. LEACH runs many rounds in the lifetime of the network and each round contains a cluster formation phase and a cluster steady phase.

Many improvements of LEACH have been studied in recent years [7], [8], [9]. The improvements can be arranged into two categories. One category focuses on changing the cluster-head selection procedure, and the other aims at avoiding direct communication between the cluster-head and the base station, and using multi-hop among the cluster-heads is a general choice for many studies in this line. In addition, most improvements consider the residual energy of the nodes. We proposed a method, which avoid direct communication and use residual energy for increasing lifetime of the sensor network.

In [4] [5] [6] one improvement is given by using MIMO (multiple input multiple output) systems can dramatically reduce the transmission energy consumption in wireless fading channels. Cooperative transmission and reception of data among sensors is known to diminish the per-node energy consumption, increasing the network lifetime, All sensor nodes are assumed to be stationary, heterogeneous and energy-constrained, where each node can transmit data to any other node and sink. The sink node is assumed to have no energy constraints and is equipped with one or more receiving antennas. The sensor nodes are geographically grouped into clusters consisting of a head node, cooperative sending and receiving nodes and non-cluster head nodes that sense the data from the sensing field. The cluster heads are reelected after each round of data transmission as in LEACH protocol. The multi hop cooperative MIMO transmission model is illustrated in Fig.1.

However MIMO given is based upon LEACH and LEACH has some shortcomings when it faces such problems as cluster construction and energy management. LEACH doesn’t fully consider the distribution situation of nodes when it chooses the cluster-heads. The number of nodes in every cluster is not uniform. The nodes far from the cluster heads will consume much more energy when they are communicating with their cluster-heads. Some cluster-heads, which will communicate with the base station directly, are distributed in the network unevenly. They will drain their energy quickly if they are far from the base station or own large number of members. During the cluster-head election procedure, residual energy and positions of nodes are not fully taken into consideration. Because of these drawbacks of LEACH, MIMO also possesses some shortcoming.

In[4] MIMO scheme is given on the static environment , am going to give a method which is fully dynamic by using Bacterial Foraging optimization algorithm ,which is used to form or adjust the cluster and after adjusting a MIMO scheme is used for communication. In BFO a fitness function is used for balancing energy in the cluster.

BACTERIAL FORAGING OPTIMIZATION ALGORITHM (BFOA)

Bacterial Foraging Optimization Algorithm (BFOA) [7], [8] is a well-known computational methodology which is based on the study of the bacterial foraging behaviors. The complex but organized activities exhibited in bacterial foraging patterns could inspire a new solution for optimization problems. The underlying mechanism of the surviving of bacteria, especially E. coli in a complex environment has been reported by researchers in the area of biological sciences. Inspired from these phenomena, BFOA was developed as an optimization algorithm by K. M. Passino [10], [11], in which the self-adaptability of individuals in the group searching activities has attracted a great deal of interests. The classical bacterial foraging optimization (BFO) system consists of three principal mechanisms, namely, chemotaxis, reproduction, and elimination dispersal we briefly describe each of these processes as follows.

Chemotaxis

In the classical BFO, a unit walk with random direction represents a “tumble” and a unit walk with the same direction in the last step indicates a “run”. Suppose θ(i_j, k, l) represents the bacterium at jth chemotactic, kth reproductive, and lth elimination-dispersal step. C(i), namely, the run-length unit parameter, is the chemotactic step size during each run or tumble. Then, in each computational chemotactic step, the movement of the ith bacterium can be represented as

θi (j+1, k, l) = θi (j, k, l) + C(I ) (Δ(i)/)

Reproduction

The health status of each bacterium is calculated as the sum of the step fitness during its life, All bacteria are sorted in reverse order according to health status. In the reproduction step, only the first half of population survives, and a surviving bacterium splits into two identical ones, which are then placed in the same locations. Thus, the population of bacteria keeps constant.

Elimination and Dispersal

Bacteria may get stuck around the initial positions or local optima, it is possible for the diversity of BFO to change either gradually or suddenly to eliminate the accidents of being trapped into the local optima. In BFO, the dispersion event happens after a certain number of reproduction processes. Then, some bacteria are chosen, according to a preset probability Ped, to be killed and moved to another position within the environment.

Randomly initialize positions of bacteria in the domain;

FOR (Selection r = 1 : Ns)

FOR (chemotactic steps per bacterium j = 1: Nc)

Calculate

Calculate the nutrient function of bacterium i as Ji(j, r);

Tumble

For bacterium i, set Ji(j, r) as Jlast. Generate a random angle represented by an array Δ, where each element belongs to [0, 1] ; Move to a random direction (Δ /√Δ_×Δ) by a unit walk, the new position is calculated by equation (1); Start another chemotactic step.

Run

For bacterium i, calculate the step fitness as Ji(j, r). If Ji(j, r) < Jlast, take another unit walk of the same direction, set Ji(j, r) as Jlast; otherwise, start another chemotactic step; Continue the Run until Nr steps before start another chemotactic step;

END FOR (chemotactic steps)

Reproduction

Set Ji as the sum of the step fitness over the life time of bacterium i ;

Sort

Sort Ji in ascending values of fitness in the population ,the first half of population survives, and a surviving bacterium splits into two identical ones, which are then placed in the same locations;

Elimination and Dispersal (Select)

Some bacteria are chosen, according to a preset probability Ped, to be killed and moved to another position within the environment.

END FOR (Selection).

TABLE I: PSEUDO CODE FOR DBFA

PROPOSED ENERGY BALANCING INTELLIGENT PROTOCOL

This aims at balancing the energy consumption among the nodes in every cluster and reducing the energy dissipation of the cluster-heads. Like LEACH, this runs many rounds in the lifetime of the network. It includes four phases during the working process: a cluster formation phase, a cluster-head adjustment phase, cooperative nodes selection phase and a steady phase.

Cluster Formation Phase

Every node sends its position information to the base station. A certain number of nodes are elected to act as the auxiliary cluster-heads with a certain probability. According to the number of auxiliary cluster-heads, the network is divided into the same number of clusters evenly. If no node dies, the number of auxiliary cluster-heads is fixed, and also the number of members in every cluster is same means fixed. To construct the cluster network, the base station starts with the furthest node from it as the first auxiliary cluster head, which chooses the nearest fixed number of nodes as its member nodes. Then the base station chooses the furthest node from it as the second auxiliary cluster-head from the rest nodes, which chooses the nearest fixed number of nodes as its members. This process continues until all the auxiliary cluster heads and members are chosen out. The base station sends notifications to all the nodes in the network. According to this procedure, if no sensor node dies in the network, this cluster construction is stable. The network owns the same auxiliary cluster-heads and every auxiliary cluster-head owns the same members.

Cluster Adjustment Phase

The auxiliary cluster-heads are not the final cluster-heads, and BFOA algorithm is used for the adjustment. The algorithm is employed by every node. Auxiliary cluster heads then decide the final cluster-heads by BFOA after every member node sends its position and residual energy information to its auxiliary cluster-head. Each auxiliary cluster-head computes the position of the final cluster-head, and sends notifications to the final cluster-head and other members in the cluster. In this phase, the BFOA algorithm is used by the auxiliary cluster-head for the adjustment. We can use a fitness function which is based upon the relative distance of each node from the auxiliary cluster head and the residual energy of each node.

On the basis of this fitness function and at the end of all chemotaxis steps we can find suitable positions for each sensor node (by following BFO algorithm).At last the bacteriam or all sensor nodes in the cluster send their relative position and residual energy to the auxiliary cluster head, Then the auxiliary cluster head compute the final cluster head position. Now suppose before starting iteration, all the bacteria are present at their real position and after iteration all the bacterias are present at their suitable position.

Then the most suitable position is mapped into one of the real positions of the nodes in the cluster.

Auxiliary cluster head do this mapping according to: Dmin = min {||Pb-P1| |,| |Pb-P2||, ||Pb-P3||……..||Pb- Pn|| }

Hear Pb = real position,

Pn = suitable position

Then the real position of a certain node with dmin will be chosen to the position of final cluster head. , which means that the nearest node from the Pb will act as the final cluster-head.

Cooperative node Selection Phase

After the cluster formation, each cluster head will select J cooperative sending and receiving nodes for cooperative MIMO communication with each of its neighboring cluster head (j is fixed). Nodes with higher energy close to the cluster head will be elected as sending and receiving cooperative nodes for the cluster.The cluster head will broadcast a cooperative request (COOPERATE-REQ) message, which contains the ID of the cluster itself, the ID of the neighboring cluster head y, the ID of the transmitting and receiving cooperative nodes and the index of cooperative nodes in the cooperative node set of each cluster head to each cooperative node. The cooperative node on receiving the COOPERATE- REQ message, stores the cluster head ID and sends back a cooperat-acknowledgement (ACK) message to the cluster head. In this MIMO scheme cluster head itself act as a sender or receiver means cluster head also tke part in cooperatively sending and receiving. Is scheme is called firstly implemented on LEACH protocol,[14] but in that it suffers from lot of draw backs, But in the proposed scheme these draw backs are can be removed by considering a good energy balancing fitness function.

Data Transmission Phase

During this phase, the data sensed by sensor nodes are transmitted to the cluster head and forwarded to the sink using MIMO scheme according to the routing table.

Intra Cluster Transmission

In this phase, the non-cluster head nodes send their data frames to the cluster head during their allocated time slot.

Inter Cluster Transmission

After a cluster head receives data frames from its cluster members, it performs data aggregation and broadcasts the data to J cooperative MIMO sending nodes. When each cooperative sending node receives the data packet, they including cluster head encode the data using space time block code (STBC) and transmit the data cooperatively. The advantage of using STBC technique is that they provide diversity gain in both transmits and receive operation in cooperative MIMO system. The diversity gain therefore provides reliable and energy efficient transmission. The receiving cooperative nodes use channel state information to decode the space time coded data. The cooperative node relays the decoded data to the neighboring cluster head node and forwards the data packet to the TCH (target cluster head).

Conclusion and Future Work

This method is better than MIMO using Leach because in LEACH in each round a new cluster head is chosen and then energy is consumed in every round for this process. But if we use BFO for clustering then only need to chose cluster head again when any Bactria die in any cluster because of low energy, so hear it consume less energy than LEACH and also cluster head itself takes part in communication like in cooperative sending and receiving operation so there is also a point exist for saving energy of whole cluster and cooperative nodes. So it gives better result than LEACH. The variation of BFOA parameters has little influence on the selection of final cluster-head in every cluster. So it has little influence on the working process of the wireless sensor network. For the large-scale wireless sensor network, there is large number of members in every cluster and the cluster-head will consume more energy during its work time. In the future research, we will pay more attention to the influence of the BFOA parameters on the large-scale wireless sensor network.

References

B. Warneke, M. Last, B. Liebowitz, and K. S.J. Pister. Smart Dust: Communicating with a Cubic-Millimeter Computer. IEEE Computer, 34(1):44–51, 2001.
Lifetime Maximisation of multihop WSN using cluster based cooperative MIMO scheme by J.Vidhya and P.Dananjayan .International Journal of computer theory and Engineering,vol 2, no 1 february ,2010
W. R. Heinzelman, A. P. Chandrakasan, and H. Balakrishnan, “Energyefficient communication protocol for wireless microsensor networks,” in Proceedings of the 33rd Hawaii International Conference on System Sciences. USA, vol. 2, pp. 1-10, January 2000.
J.Vidhya and P.Dananjayan: Lifetime Maximisation of multihop WSN using cluster based cooperative MIMO Scheme(international journal of computer Theory and Engineering, 2010)
G. N. Bravos and G. Efthymoglou, “MIMO-based and SISO multihop sensor network: Energy efficiencyevaluation”, Proceedings of IEEE International Conference on Wireless and Mobile Computing, Networking and Communications, 2007
S. K. Jayaweera, “Energy analysis of MIMO techniques in wireless sensor networks”, Proceedings of Annual Conference on Information Sciences and Systems, Princeton, NJ, 2004.
W. Y. Zhang, Z. Z. Liang, Z. G. Hou, and M. Tan, “A power efficient routing protocol for wireless sensor network,” 2007 IEEE/ACS International Conference on Computer Systems and Applications. Jordan, pp. 20-25, May 2007.
N. M. Abdul Latiff, C. C. Tsimenidis, and B. S. Sharif, “Energy-aware clustering for wireless sensor networks using particles swarm optimization,” 2007 IEEE 18th International Symposium on Personal, Indoor and Mobile Radio Communications. Greece, pp. 2713-2717, September 2007.
Y. Liang, H. B. Yu, and P. Zeng, “Optimization on routing protocol of wireless sensor network based on clustering using PSO,” Control and Decision. China, vol. 21, pp. 453-456, 461, April 2006.
K. M. Passino, “Distributed optimization and control using only a germ of intelligence,” in Proceedings of the 2000 IEEE International Symposium on Intelligent Control. Held jointly with the 8th IEEE Mediterranean Conference on Control and Automation. Greece, P5-P13, July 2000.
K. M. Passino, “Biomimicry of bacterial foraging for distributed optimization and control,” IEEE Control Syst Mag. USA, vol. 22, pp. 52- 67, June 2002.
D. Estrin, R. Govindan, J. Heidermann, and S. Kumar. Next Century Challenges: Scalable Coordination in Sensor Networks. In MobiCOM, 1999.
Energy Efficient STBC –Encoded Cooperative MIMO Routing Scheme for Cluster Based Wireless Sensor Networks by J.Vidhya and P.Dananjayan*,International Journal of Communication Networks and Information Security, Vol. 2, No. 3, December 2010.