Cluster Based Routing For Wireless Sensor Network

Energy Efficient Cluster Based Routing Protocol for Wireless Sensor Networks Rab Nawaz Department of Computer Science COMSATS Institute of Information Technology, Abbottabad. [email protected] Abstract Wireless sensor network are sophisticated systems that are used to collect data from an inaccessible environment. They consist of base station and hundred to thousand of tiny nodes called sensor nodes. Nodes in the sensor network are constrained by energy. The sensor networks where base station is very distant from the sensor field, the energy efficiency in the working of sensor networks plays an important role in the lifetime of the sensor networks. To prolong the life of the sensor network energy efficient techniques for routing is an important issue. In this paper we proposed a new algorithm for cluster head selection in each cluster for each round of communication. The clusters are fixed through out the network life time. Our proposed work is based on LEACH and LEACH-C. The protocol works efficiently to increase the overall network lifetime and outperforms LEACH in terms of minimizing the overall energy consumption. Keywords – Clustering methods, energy efficiency, routing protocol, wireless sensor networks.

1. Introduction. Wireless sensor networks are a paradigm for gathering data from inaccessible environment. The nodes in the network are interconnected by wireless communication channels. Each sensor node has capability to collect data from its surrounding area, carry out simple computations, and communicate with rest of the nodes in the network or with base stations (sink) [1]. In these networks the nodes are the energy constrained, once they deployed in any area, it is almost impossible to replace or recharge the node battery. Wireless sensor network has a tremendous growth over the last few years, in addition to the military applications, environmental applications, and more industrial applications for the sensor networks are found, resulting in an increase in functionality and decrease in implementation cost. These networks are emerging as an important new concept in the information technology for distributed monitoring of environments, which are physically remote, hostile or inaccessible. Advancement in miniaturization allow sensor to have increasing on

board processing power which allow for distributed computing application for in place processing of gathered data before transmission. These networks have capability of collecting audio, seismic and other type of data and collaborate to perform a high level task in the network. As for as wireless environment in concerned, basically it consumes significant amount of energy, sensor node should consume as little energy consumption as possible for receiving and transmitting data. Currently, researchers put their efforts in sensor networks focusing on the issues involved in the development of energy efficient protocol, low cost, secure and fault tolerance networks. Wireless Sensor Networks Routing Protocols can be classified into three categories, named direct communication, flat (multi hope) and clustering protocol. In direct communication, sensor nodes send their data directly to the base station. The main drawback of the direct communication protocol is that if the diameter of the network is very large, then the nodes away from the base station will drain their energy very quickly. And another problem is that if the number of nodes increases, collision becomes a significant factor which defeats the purpose of data transmission. In the multihope strategy, once a node has data to send, it may find rout consisting of several hop to base station. Comparing the first two strategies, the clustering protocol have several advantages, the most important is of scalability. Secondly, it could be energy efficient in finding an available route to a destination. In cluster based routing protocols, each cluster has a cluster head (CH), all the nodes in the cluster send their sensed data to cluster head, and then cluster head after aggregation send data to base station[7]. In this paper we consider a network model used in [7] – [8], having properties,  All the nodes after deploying are static as for as location is concerned and having same energy level.  All the nodes having a power control capability to very the transmitted power.  Base station is rigidly fixed.  Each node is allocated a timeslot for sensing and sending data to CH. In this paper, cluster based working is involved. Once the clusters are formed during the network operations, the

cluster will never be changed during the whole network life time. This is a static clustering concept. Static clustering eliminates the overhead of dynamic clustering for each round of communication. In this paper we propose a new hybrid technique for cluster head selection by merging the concept of LEACH and LEACH-C [7]. Basically this protocol is an enhanced version of LEACH protocol in terms of energy efficiency. Same concept of data fusion is performed as in LEACH-C [7] is used. Data fusion is a mechanism for combining one or more packets from different sensors to produce a single packet [3]. LEACH uses randomization to rotate the cluster head and achieve major improvements compared to the direct approach before the first node dies [8]. The main difference between the proposed and LEACH protocol is,  The proposed protocol utilized a new idea of cluster head selection.  It utilizes multihope communication instead of direct communication. Especially for the case in which the network diameter is very large. So the direct communication fails in such scenarios. So introduces multi hope communication between cluster head to cluster head to rout the packet to base station. The rest of the paper is organized as follows. Section II describes the previous work. Section III describes the problem statement and section IV states the Proposed Algorithm. And finally in section V conclusion and future work will be initiated. In this technique a totally new concept of cluster head selection is carried out which is more energy efficient and more reliable.

2. Related work. Many cluster based protocol have been proposed. Cluster base protocol also called hierarchical protocols to make routing efficiently. In the cluster based protocol the nodes in the sensor fields are grouped into clusters, and each cluster has a cluster head (CH). All the nodes in the cluster send their data to the cluster head and cluster head then communicate with the base station. Decision of cluster head selection for each round can be centralized or distributed selection. If the protocol is based on centralized selection[3,9,10], then it means that after each round , base station will decide next round cluster heads on the basis of remaining energy level. Whereas in the case of distributed selection nodes organized themselves to form clusters. Many cluster based protocol have been proposed, to make routing efficiently. LEACH (Low Energy Adoptive clustering Hierarchy [1] is a clustering protocol based on distributed cluster head selections, where sensor nodes elect themselves as cluster head nodes with some probility based on remaining energy of sensor nodes for each round. LEACH-C [3] is based on LEACH and uses centralized approach for cluster head selection. It uses

direct communication mechanism between cluster head and base stations. PEGASIS [2] is a chain based power efficient protocol based on LEACH. PLR (prolonging network lifetime via intra cluster routing) [10] is another centralized cluster based protocol and is based on LEACH-C. It provides three hop routing algorithm within clusters. HYENAS [9], also uses centralized and distributed algorithm to form cluster in the network. It uses remaining energy, location and movement of nodes. A new hierarchical energy aware routing protocol for sensor network [5], combines features such as data aggregation [7], energy aware routing, clustering into a single protocol. These entire features extended the overall network lifetime. Dynamic clustering is utilized to allow the sensor to change their cluster association dynamically. Data aggregation is utilized to allow different data packets to be combining together in order to conserve energy and finally hierarchical routing is used to bridge larger distances. Energy aware routing in cluster based sensor networks [9], presents a novel approach for energy aware and context aware routing for sensor network. The work described in [6], states the requirements and similarities of MANETS and sensor networks on the basis of routing protocols. And this comparison reveals the important features that need to be considered while designing new energy efficient protocol for wireless sensor networks. In conventional cluster based networks the infrastructure is fixed [7]. The new research is focusing on ways to implement clustering technique in an ad-hoc fashion [10]. Early work by Baker et al. developed a linked cluster architecture, where nodes are assigned to be ordinary nodes, cluster head nodes, or gateways between different clusters [10]. The cluster head act as a central control authority, whereas gateway acts as a backbone network, transporting data between different users. Currently, lot of work has been done on “Power Aware” routing in wireless sensor networks [11]. In these types of protocols, optimal paths are chosen on the basis of remaining energy at each node along the path i.e. the path that is selected for routing a packet to base station has only those nodes which has more energy to rest of the nodes and having a very short distance.

3. Problem Statement. All the above mentioned protocols doest not provide any keen attention to the number of clusters in the network. Basically my proposed work is based on [3], LEACH-C and LEACH as well. Developing a new hybrid cluster based protocol which uses both the important feature of LEACH-C and LEACH with location and energy aware routing mechanism. In LEACH the cluster head selection mechanism is carried out by the clusters nodes themselves. They select cluster head without the involvement of the base station. The sensor nodes elect themselves as cluster head node

with some probability based on remaining energy of the sensor nodes for each round of communication. Basically the work described in [3], the cluster head selection mechanism is base station controlled. Basically the LEACH-C cluster head selection technique is nearly adopted. In [3] the base station select one Temporary cluster head in each cluster randomly. The responsibly of the TCH to select only one node that is utmost energy level to rest of the nodes. This is only for the first round. After the successful completion of the first round, when next round begin, the node in each cluster that has minimum energy to rest of the nodes, send out a round start packet by showing its identity as a TCS, and send energy level to it. Through this way it selects the utmost energy level node as a cluster Head for that particular round of communication. Here the problem is that due to passage of time, the round increases, the energy level of each node will be dropped down directly with the round increments. So the node that is selected after the first round has minimum energy, and that node is responsible for cluster head selection. So the problem is that especially in last round of communication this node in each cluster has also very low energy, so when it has no enough energy to complete the task of cluster head selection for any particular round of communication, the overall working of that cluster will be disturbed because of failure in terms of energy of TCH. Most of the protocols [7], have not given attention to the issue of providing the location information to base station. The proposed Algorithm also provide location information of each node to other nodes in the network i.e. each cluster head send its location to another cluster head in other cluster and same information is shared among all the cluster heads of the network. Through this way each cluster knows the location information of its neighbor cluster head. Through this way the cluster head to cluster head communication is implemented. The complete solution of this problem is presented in the next section. The communication between cluster head and base station is direct [3]. In [3] it is assumed that all the nodes in the network are directly reachable to BS, it is not a valid assumption beacuase there is no issue of energy and transmission range with the BS. This protocol may not work efficiently especially when the network diameter is bit large. The nodes at the border will drain their energy very quickly as compared to the nodes that are near enough to the base station. The direct communication is suitable, when the network diameter is very small or the area and distance between sensor field and base station is very small. So when the networks diameter is very large and direct communication fails so our proposed protocol works efficiently in the scenario. So multihope communication is adopted to route a packet from the cluster head to base station. Only the first cluster’s cluster head communicate directly to base station but rest of the cluster uses cluster head to cluster head communication to rout a packet to base station.

The proposed work defines a new algorithm for cluster head selection and number of clusters in the network, and the communication between CHs and sink is multihope communication for energy efficiency especially for scalable networks.

4. Proposed Algorithm Architecture. The proposed protocol is self organizing and static clustering methodology is adopted to reduce the overhead of dynamic clustering. The working of protocol is divided into two major phases, the setup phase and data communication phase. 1. Setup Phase. In setup phase some important factor to be considered first are, cluster formation, cluster head selection mechanism and setting up TDMA schedule to each cluster before network operation. The cluster formation is performed by message passing technique used in [3], in which the base station broadcast different messages to sensor field with different transmission power. The base station broadcast n-1 different messages with different transmission power, where n is desired number of clusters. By broadcasting the n=1 message all the sensor nodes which hear this message (are in the radio range of this message) set their cluster ID to n and inform the Base Station that they are member of the cluster n via transmitting a join Request message (Join-REQ) back to the base station [3]. Fig. 1 shows that how the sensor field is divided into n=5 clusters with broadcasting n-1=4 different messages from base station. These clusters once they formed will not be changed until the whole network life time. Basically the static clustering reduces the overhead of dynamic clustering [3].

Fig. 1 Cluster Formation by message passing technique Our proposed protocol architecture selects cluster head in each cluster in different way. The methodology described in [3], for cluster head selection is, for the first round Base Station selects randomly one node as a TCH that is responsible for cluster head (CH) selection. After

the first round, the less energy node in cluster will be selected as a TCH (Temporary Cluster Head) that is responsible for Cluster Head selection in that particular cluster. After cluster formation the next important work to be done is of cluster head selection. The proposed Algorithm for Cluster head selection is as under.

Algorithm: Round=1 TCH (Temporary Cluster Head), CH (Cluster Head) While round <=15 If round == 1 then // Randomly select one node as a TCH in Each Cluster N= random (from all nodes) Assign TCH = N * TCH.Energy -- // energy dissipates 50 nj/bit for CH selection CH=MAX_ENERGY (All node in the cluster except TCH) Decrement Energy of CH by 100 nj/bit Else TCH= CH Goto * End Above Algorithm is used for the cluster head selection. According to the Algorithm the node that is selected as a cluster head for the first round of communication will be TCH for the next round. Before the next round start the CH node now act as a TCH, sends out a round start packet to rest of the nodes in the cluster only for the purpose to get their energy level. After getting the energy level of each node it finds out the utmost energy level node as a cluster head (CH) for that particular round. Same process will be continued in each cluster. In this way base station involvement is only for the first round, but after that cluster head selection mechanism will be carried out in each cluster itself. It is an energy efficient way of selecting cluster head (CH). The cluster head (CH) relays its location information to the neighbor CH. In this way each CH in the network share its location information to each other. The cluster which is away from the base station will rout the aggregated packet to base station through CH to CH of the neighboring clusters. In addition to this the base station also broadcast a TDMA schedule to each cluster. Once the TDMA schedule is known by all the nodes in the clusters, the setup phase is completed.

number of nodes in the cluster. For efficient utilizing the energy of each node except CH will be turned off until its allocated transmission time. The CH will awake all the time to receive data from all the nodes in the cluster. Changing of the cluster head (CH) will no effect on the schedule of the cluster operations. The direct communication showed in Fig. 2 not working properly especially when the network diameter is very large. Because clusters are formed in layered fashion, so when increasing number of layers then the border CH will drain their energy very quickly than that of CH that are closest to Base Station. We propose multihope communication instead of direct communication by considering the scalability factor of the network.

Fig. 2 Direct communication mechanism. The total energy expended in the system is greater using multihope communication but it is best suited in the scenario when sensor field diameter is very small. Same greater advantage multihope show for scalable network and utilized energy efficiently to prolong the overall network life time. It also improves the reliability factor as for as data transmission is concerned. The Fig. 3 describes the graphical depiction of multihop communication between cluster head (CH) and Base Station (Sink).

2. Data Communication Phase Each node in the cluster after sensing data, send its data to CH during its pre allocated time slot. The duration of each slot in which a node send its data is constant, so the time in which a frame is send is totally depends upon the

Fig. 3 Multihop Communication between Cluster Head and Base station

5. Radio Energy Dissipation Model Same hardware energy dissipation model as described in [7] is used where the transmitter dissipates energy to run the radio electronics and the power amplifier, and the receiver dissipates energy to run the radio electronic [7, 8], as shown in figure 4.

Fig. 4 Radio energy dissipation model

In this model to transmit k-bit message with a distance d meter, ETx is used by the node which is, Etx (k: d) = Etx-elect (k) + Etx-elect (k: d) Etx (k: d) = Etx-elect * k + Eamp * k * d2)

[2]. Lindsey.S, Raghavendra C.S “PEGASIS: Power Efficient Gathery in Sensor Information Systems” . IEEE Aerospace conference Proceding, 2002. [3]. Amir Sepasi Zahmati, Bahman.A, A.A Beheshti Shirazi, A.S Bakhtiari, “ An Energy Efficient Protocol With Static Clustering for Wireless Sensor Networks” Internation journal of Electronics, circuit and Systems Volume 1 number 2 2007 issn 13074156. [4]. Heinzelman W.R Sinha, A. Wang, A. Chandrakasan. “ A. P Energy – Scalable Algorithm and Protocol for wireless microsensor netowrs Acoustics , Speech and Signal Processing, 2000. IXASSP’00”. Proceeding IEEE 2000International Conferrence on Volume 6, 5-9 june 2000. [5]. Hempel, M. sharif, H.Raviraj, P.hera-san. “ A new Hierarchical Energy Aware Routing Protocol for Sensor Networks” Preceeding of the 38th Annual Hawaii International Conference on 03-06-2005.

Where the radio dissipates Eelect = 50nj/bit to run the transmitter circuitry and Eamp = 100pj/bit/m2 for the transmitter amplifier. To receive k-bit message, a node consumes, Etx (k: d) = Etx-elect (k) Etx (k: d) = Etx-elect * k. Where the radio dissipates Eelec = 50nj/bit to run the receive circuitry. This is the first order radio model.

[6]. Qiangfeng Jiang, Manivannan. D. “Routing Protocol for Wireless Sensor Network” IEEE consumer communication and Networking Conferrence, 5-82004.

6. Conclusion.

[8]. T. Rappaport, Wireless Communication: Principal and practices. Englewood Cliffs, NJ: Prentice Hall, 1996.

We introduces a new cluster based energy efficient routing protocol which reduces the overhead of dynamic clustering and efficiently utilized the energy of whole the system to extend the network lifetime. The energy efficiency at each level of network operation makes this protocol desirable for wireless sensor networks routing. Our proposed protocol indicates the lifetime of network is extended and the overall number of messages received at base station is increased. 7. References. [1]. Heinzleman W.R. Changrakasan, A, Balakrishnan “High Energy Efficient Communication Protocol for Wireless microsensor network systems” Preceeding of 33rd Annual Hawaii International Conference on Jan4-7-2000.

[7]. W. B. Heinzelman, A. Chandrakassan and H. Balakrishnan, “ An Application Specific Protocol for Wireless Microsensor Networks” , IEEE Transactions Wireless Commun. Vol. 1, no. 4 Oct, 2002, PP 660-70.

[9]. D. Hall, Mathematical Techniques in Multisensors Data Fusion. Bostan M.A: Artech House, 1992. [10]. D. Baker, A. Ephrimides,and J.Flynn, “The Design and simulation of a mobile radio network with distributed control” IEEE J. select. Areas Commun., vol. SAC – 2, pp. 226-237, jan 1984. [11]. S. Park and M. Srivastava, “ Power Aware Routing in Sensor Networks using Dynamic Source Routing,” ACM Monet Special issue on Energy conserving Protocols in Wireless Networks, 1999.