Energy-e cient Clustering Method for Wireless Sensor Networks by Kyeongdon Lee A thesis submitted to the Graduate Faculty of Auburn University in partial ful llment of the requirements for the Degree of Master of Science Auburn, Alabama August 9, 2010 Keywords: Wireless Sensor Network, Cluster-based routing, LEACH,ELP Copyright 2010 by Kyeongdon Lee Approved by: Alvin Lim, Chair, Associate Professor of Computer Science and Software Engineering Drew Hamilton, Professor of Computer Science and Software Engineering David Umphress, Associate Professor of Computer Science and Software Engineering Abstract Wireless sensor networks have recently emerged as an important computing platform. These sensors are power-limited and have limited computing resources. Therefore the sensor energy has to be managed wisely in order to maximize the lifetime of the network. There have been many studies on considering sensor?s energy. Among these, clustering sensor nodes is a more e cient and adaptive approach in sensor networks having some essential requirements. First, every node in a cluster should elect one clusterhead. Second, clustering must minimize overhead. Third, network topology must be stable. Finally, as sensor nodes are operated; low power, low energy consumption is required. In this thesis, previous work on LEACH protocol is reviewed and a study on the issues related to the network lifetime is carried out. Simply speaking, LEACH requires the knowledge of energy for every node in the network topology used. LEACHs threshold which selects the clusterhead is xed so this protocol does not consider network topology environments. Whereas other protocols, namely HEED and PEGASIS, which are hierarchical routing protocols, do not guarantee the number of clusterheads. Thus, ELP (Enhanced LEACH Protocol) algorithm is proposed, which selects clusterheads using di erent thresholds. New clusterhead election probability consists of the current energy of nodes that is compared to initial energy and current energy of neighbor nodes. In order to evaluate the energy e ciency for the ELP algorithm, the network lifetime of both LEACH and ELP is compared. The network lifetime of ELP shows an increase of more than 23% compared to the LEACH network lifetime. In conclusion, the proposed protocol e ciently manages the energy of sensor nodes resulting in an increase of the network lifetime. ii Table of Contents Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Wireless sensor network . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2.2 Terminologies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2.3 Evaluation Criteria . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.3 Contributions and Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2 Related works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.1 Introduction of Routing in wireless sensor network . . . . . . . . . . . . . . . 7 2.2 Routing model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2.1 One-hop model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2.2 Multi-hop model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2.3 Cluster-based model . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.3 Routing protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.4 Network structure based protocol . . . . . . . . . . . . . . . . . . . . . . . . 10 2.4.1 Flat routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.4.2 Location based routing protocols . . . . . . . . . . . . . . . . . . . . 14 2.4.3 Hierarchical routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.5 Routing protocols based on protocol operation . . . . . . . . . . . . . . . . . 19 2.5.1 Multipath routing protocols . . . . . . . . . . . . . . . . . . . . . . . 19 iii 2.5.2 Query based routing . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.5.3 Negotiation based routing protocols . . . . . . . . . . . . . . . . . . . 20 2.5.4 QoS-based routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.5.5 Coherent and non-coherent processing . . . . . . . . . . . . . . . . . 20 3 Problem Statement, Objective, and Our Approach . . . . . . . . . . . . . . . . . 21 3.1 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.2 Objective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.3 Our approach to solve the problems . . . . . . . . . . . . . . . . . . . . . . . 23 4 Design of Energy e cient cluster head election algorithm . . . . . . . . . . . . . 25 4.1 Network model key features . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 4.2 Design of the cluster head election algorithm . . . . . . . . . . . . . . . . . . 26 4.2.1 Cluster creation and data transmission . . . . . . . . . . . . . . . . . 27 5 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 5.1 Simulation model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 5.2 Simulation Environments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 5.3 Simulation results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 5.3.1 Node lifetime simulation . . . . . . . . . . . . . . . . . . . . . . . . . 32 5.3.2 Energy-time simulation . . . . . . . . . . . . . . . . . . . . . . . . . . 36 5.3.3 Number of Clusterhead simulation . . . . . . . . . . . . . . . . . . . 38 6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 iv List of Figures 1.1 Application of wireless sensor networks . . . . . . . . . . . . . . . . . . . . . 2 1.2 Organization of communication in the sensor networks . . . . . . . . . . . . 3 2.1 One-hop protocol model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2 multihop protocol model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.3 Cluster protocol model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.4 Routing protocols in wireless sensor networks[2] . . . . . . . . . . . . . . . . 11 2.5 SPIN protocols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.6 Problem with blind ooding of sensor data . . . . . . . . . . . . . . . . . . . 12 2.7 Directed di usion steps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.8 Example of virtual grid in GAF . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.9 State transitions in GAF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.10 PEGASIS protocols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.1 Cluster head rotation good-case in LEACH . . . . . . . . . . . . . . . . . . . 22 3.2 Cluster head rotation bad-case in LEACH . . . . . . . . . . . . . . . . . . . 22 5.1 Communication model between the sensor node . . . . . . . . . . . . . . . . 29 5.2 Distributed node in network environment . . . . . . . . . . . . . . . . . . . . 31 5.3 Lifetime using direct transmission, MTE routing, static clustering, and LEACH with 0.5 J/node[7] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 5.4 The number of dead nodes with time(N=100) . . . . . . . . . . . . . . . . . 34 5.5 The number of dead nodes with time(N=200) . . . . . . . . . . . . . . . . . 34 5.6 The number of dead nodes with time(N=300) . . . . . . . . . . . . . . . . . 35 v 5.7 Lifetimes using di erent amounts of initial energy for the sensors . . . . . . . 35 5.8 Energy of a single round . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 5.9 Ensemble average of the energy of all the rounds . . . . . . . . . . . . . . . . 37 5.10 Compare of the energy with PEGASIS protocol . . . . . . . . . . . . . . . . 38 5.11 Number of the clusterhead in LEACH . . . . . . . . . . . . . . . . . . . . . 39 5.12 Number of the clusterhead in ELP . . . . . . . . . . . . . . . . . . . . . . . 39 vi List of Tables 5.1 Simulation Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 5.2 First dead node appears in leach and ELP . . . . . . . . . . . . . . . . . . . 33 5.3 Lifetimes using di erent amounts of initial energy for the sensors . . . . . . . 36 vii Chapter 1 Introduction 1.1 Overview In recent years wireless sensor networks has been a new and hot domain in computer science and technology and has a wide application future. It has enabled the development of a sensor node with a low cost processor, low power, and light weight [1]. The wireless sensor networks consists of small sensor nodes able to detect light, sound, temperature, motion, an intelligent computing devices that enables the processing of data collected from sensors, and communication capabilities with other nodes through wireless networks. Sensor nodes can self-organize to form networks and communicate with each other using their wireless interfaces and transmit to the destination as multi-hop. In large-scale sensor networks, hundreds or thousands of sensor nodes are randomly deployed into a sensing eld. Sensor nodes are especially useful in extremely hostile environments, such as near active area, inside a dangerous chemical plant, or in disaster areas with a nuclear reactor. In addition, potential applications for such large-scale wireless sensor network (WSN) exit in a variety of elds, including environmental monitoring, surveillance, health-care monitoring, and military operations as shown in Figure 1.1 [22][19][20][21]. Also, motivated by the emergence of ubiquitous computing technology[17] as the next generation of computing, a new class of network robots has been introduced. It is a concept that provides the services for person, anytime, anywhere. Since it is inherently based on ubiquitous environments with networked sensors and actuators, it can be considered as one of the most important emerging applications of wireless sensor networks. Distributed networks which consist of sensors to perceive and send data measured in the surrounding environments are developed to reposition and organize sensor nodes to acquire and deliver the corresponding information[5]. To make 1 Figure 1.1: Application of wireless sensor networks wireless sensor networks apply to various applications, e cient design and implementation of wireless sensor networks is required. 1.2 Wireless sensor network 1.2.1 Overview WSN is a very large array of diverse sensor nodes that are interconnected by a commu- nication network. The sensing data are shared between the sensor nodes and are used as input for a distributed estimation system. The fundamental objectives for WSN are reliabil- ity, accuracy, exibility, cost e ectiveness, and ease of deployment[24]. WSN is made up of individual multifunctional sensor nodes. Figure 1.2 shows the communication architecture in WSN. The sensor nodes are usually scattered in a sensing eld. Each scattered sensor node has the capability to collect data and route collected data to the sink by multi-hop 2 Figure 1.2: Organization of communication in the sensor networks architecture. The sink may communicate with the task manage node via Internet. The de- sign of WSN is in uenced by many factors, including fault tolerance, scalability, production costs, operating environment, sensor network topology, hardware constraints, transmission media, and power consumption[1]. The components of a sensor node such as location nding system, mobilize, and power generator may also be present. The sensor node senses the physical quantity being measured and coverts it into an electrical signal. (refer to Figure 1.2) Then, the signal is fed to an A/D converter and is ready to be used by the processor. The processor will convert the signal into data depending on how it is programmed and it sends the information to the network by using a transceiver. The power unit may be supported by solar cells or battery. These sensor nodes operate in an ad-hoc manner and they have speci c features. The design for all protocols focuses on the extension of network lifetime, since sensor nodes have a limited amount of energy. The implicit operations of WSN are a variety of information processing techniques. These are used for the manipulation and analysis of sensing data, 3 the extraction of signi cant features, and the e cient storage and transmission of important information. The protocol and algorithms that have been proposed for traditional wireless ad-hoc networks are not well suited to the requirements of WSN [11]. The speci c characteristics of WSN are as follows: ? Sensor nodes are limited in power, computational capacities, and memory ? Sensor nodes are densely deployed ? The number of sensor nodes will be much more than the number of nodes in ad-hoc network ? Sensor nodes may not have global identi cation because of the large number of sensors ? Sensor nodes mainly use broadcast communication paradigms whereas most ad-hoc networks are based on point-to-point communications 1.2.2 Terminologies Following terminologies are being used in this thesis: ? Sensor node : A sensor node implements the physical sensing of environmental phe- nomena and reporting of measurements through wireless communication. Typically, it consists of ve components that are sense harware, memory, battery, embedded processor, and transceiver. ? Sink node : A sink node receives data collected by individual sensor nodes, and respon- sible for training wireless sensor networks and for maintenance and repair operations. It also provides interface to the outside world. ? Cluster and ClusterHead : In the clustered routing approach, a few sensor nodes with radio range are grouped to form a cluster. Each cluster has a clusterhead, a sensor node which receives data from all other sensor nodes in the cluster, performs data 4 fusion, and transmits the results to the sink node. This greatly reduces the amount of data sent to the sink node and thus improves energy e ciency. 1.2.3 Evaluation Criteria Some evaluation criteria for wireless sensor network protocols are shown in[2] . ? Energy e ciency/system lifetime : As sensor node is battery-operated, protocols must be energy e cient to maximize system lifetime. System lifetime can be measured by generic parameters such as the time until all of the nodes die or by application directed metrics, such as when the network stops providing the application with the desired information about the phenomena. ? Latency : It is the observation of the phenomena within a given delay. The precise semantics of latency are application dependent. ? Accuracy : Obtaining accurate information is the primary objective of the observer, where accuracy is determined by the given application. There is a tradeo between accuracy, latency and energy e ciency. The given infrastructure should be adaptive so that the application obtains the desired accuracy and delay with minimal energy expenditure. ? Fault-tolerance : Sensor nodes may fail due to surrounding physical conditions or when their energy runs out. It may be di cult to replace existing sensor nodes; the network must be fault-tolerant such that non catastrophic failures are hidden from the application. Fault-tolerance may be achieved through data replication. However data replication itself requires energy; there is a tradeo between data replication and energy e ciency. ? Scalability : Scalability for wireless sensor networks is also a critical factor. For large- scale networks, it is likely that localizing interactions through hierarchy and aggregation will be critical for ensuring scalability. 5 1.3 Contributions and Structure The main contribution of this thesis is to reduce energy consumption over all sensor nodes without generating any isolated sensor nodes for wireless sensor networks. Two kinds of topology con guration methods are tried here to achieve the following primary goals. First, the network lifetime will be prolonged by evenly distributing clusterheads over the network with electing probability. Second, energy consumption will be balanced by selecting clusterheads and comparing current energy status on every round. Also, clusterhead number will be shown for comparing original LEACH protocols and proposed protocols. A di erent probability of electing clusterheads in the network eld is proposed here and considering the remaining energy amounts of each node and clusterhead. This thesis is composed as follows. Several related work is reviewed in chapter 2 and the problem formulation, and research objective, is presented. Our approach to solve these problems is shown in chapter 3. In chapter 4, the proposed method is introduced with the existing protocols such as LEACH and PEGASIS. In chapter 5, the simulation results in terms of network lifetime, each and all rounds energy consumptions, and number of clusterhead are shown. As the results of network lifetime simulation, the rst dead node in the proposed al- gorithm appears later than LEACH, also we extend the entire network lifetime. When we compare the energy consumption among the protocols, proposed algorithm has a longer life- time than LEACH and PEGASIS. In the case of number of clusterhead between LEACH and the proposed algorithm, the proposed algorithm shows a larger deviation in the number of CH. Finally we conclude the thesis in chapter VI. 6 Chapter 2 Related works 2.1 Introduction of Routing in wireless sensor network Despite the many applications of wireless sensor networks, these networks have many restrictions, for example, limited energy, limited communication range etc. One of the main design goals of wireless sensor networks is to complete data communication while trying to extend the lifetime and keep the quality of communication. The design of routing protocols in wireless sensor networks is a ected by many challenging factors. Because a distributed network has a lot of sensor nodes and each node is a shared resource, many decisions must be made. There may be many paths from the source to the destination so the routing path is an important topic [11]. First of all, routing models are explained and problems that can occur when applied to sensor networks are examined. 2.2 Routing model 2.2.1 One-hop model It is the simplest model of all in which sensor node directly communicates with BS (Base Station), as seen in Figure 2.1. Sensor nodes have a restricted transmission range. Thus, this model is not proper for wireless sensor networks, in which the energy of sensor node is an important resource. When there is a close distance between node and base station, this model may be the most appropriate model for sensor networks. However, in most sensor networks, the sensor nodes are randomly distributed in abroad area and then perform sensing. Thus, this model is not suitable for sensor network. Also, even if sensors are close to the BS, the collision occurs on dense networks[7]. 7 Figure 2.1: One-hop protocol model 2.2.2 Multi-hop model In this model nodes send data to the neighboring node close to BS. Consequently the data moves from one node to another node with hop unit until it reaches its destination (See Figure 2.2). However, in the networks where the number of sensor nodes reaches thousands of pieces, the multi-hop model indicates very high latency. Another vulnerability, which may appear in this model, is the e ect of black hole. In other words, it is suggested that the closer node to BS needs to play an intermediary role in data toward BS. Accordingly, such nodes form a black hole around BS, and consume energy more quickly than other nodes. When trying to consider energy, even this model cannot become a proper model for sensor networks [7]. 2.2.3 Cluster-based model In cluster-based model, the nodes are grouped in clusters. There is a cluster head in each cluster which plays a role of routing data into other clusters or base stations by gathering data from nodes within its cluster. In this model, data is rst gathered within each cluster and then it follows a method which delivers the data to other clusters or base stations(See Figure 2.3). In Multi-hop based model, all the relay nodes perform data aggregation. On the other 8 Figure 2.2: multihop protocol model hand, in cluster-based model, only cluster head performs data aggregation. Accordingly, cluster-based model can be a model that is more proper for WSN than multi-hop network. In this protocol model, the cluster is formed statically. If the cluster is xed, a problem of black-hole can occur as in multi-hop. Namely, the node, which is the closest to cluster head, not only senses itself, but also plays a role of delivering it to cluster head by receiving data in other node. Thus, such nodes will shorten relative lifetime. 2.3 Routing protocol In this section, previous related works on the routing protocols for wireless sensor net- works is reviewed. First, the classi cation of the clustering protocols is reviewed, and then detail features of hierarchical-based routing for the sub-protocols is presented in detail in this chapter. Even though there are a good many routing protocols, but here the focus is on protocols of wireless sensor networks with xed sensor nodes, not mobile sensor nodes. Routing protocols that deals with wireless sensor networks having xed sensor nodes can be classi ed into at-based routing, hierarchical-based routing, and location-based routing depending on the network structure [2]. In at-based routing, all nodes have the same roles or functionality in hierarchical-based routing, however, nodes will play di erent roles in the network in location-based routing, sensor nodes positions are imposed to transmit data in 9 Figure 2.3: Cluster protocol model the network. If certain system values can be controlled in order to adapt to the real-time network conditions and current energy, the routing protocol is considered adaptive. Further, the protocols can be classi ed into multipath-based, query-based, negotiation-based, QoS- based and coherent- based routing based on the protocol operation. (See Figure 2.4) 2.4 Network structure based protocol 2.4.1 Flat routing In at networks, the sensor nodes play the same role and cooperate together to perform their task. As a result of the large number of sensor nodes, it is not viable to give a unique identi er to each node. The BS sends queries to certain regions and waits for data from the sensors located in the selected regions. For example SPIN and directed di usion were introduced in following part about how to save energy through data negotiation and reduction redundant data. ? Sensor Protocols for Information via Negotiation(SPIN)[10]: SPIN(Sensor Protocols for Information via Negotiation) is a data-centric adaptive routing protocol. SPIN is 10 Figure 2.4: Routing protocols in wireless sensor networks[2] a 3-stage protocol in which the sensor nodes use three types of messages ADV,REQ and Data to communicate. ADV is used to advertise new data, REQ to request data, and DATA is the actual message itself. It rst advertises this data through short ADV messages as nodes receive or send data. The ADV message simply consists of an application-speci c meta-data description of the data itself. This meta-data can describe the type of data and the location of its origin. Nodes that are interested in this data request the data from the ADV sender through REQ messages. Finally, the data is spread over the interested nodes through Data messages the hold the data. Operation of SPIN protocol is illustrated in Figure 2.5. The advantage of SPIN is that it avoids three costly di culties: implosion, overlap, and resource blindness. Implosion occurs in tightly connected networks that use ooding and thus each sensor node receives many overlapped copies of the data as shown in Figure 2.6(a). For large data message, this wastes considerable energy. In SPIN, short ADV message can su er from implosion problem, but the costly transfer of data messages is greatly reduced. Overlap occurs due to the redundant nature of sensor data. Thus two nodes with some common data will both send their data, causing redundancy in data transmission and thus energy waste as shown in Figure 2.6(b). 11 Figure 2.5: SPIN protocols Figure 2.6: Problem with blind ooding of sensor data ? Directed di usion :[12] Directed di usion is a data-centric(DC) protocol based on query in wireless sensor networks. To carry out a sensing task, a querying node creates an interest, which is named according to the attributes of the data or events to be sensed. When an interest is created, it is infused in the network by the sink node. The sink node broadcasts an interest message containing the interest type, duration, and an initial reporting rate to all neighbor nodes. Interests are di used throughout the network toward the sink node using one of a number of forwarding techniques. Figure2.7 shows 12 Figure 2.7: Directed di usion steps a network in which the interest was sent to the region of interest through controlled ooding. Once the interest researches the desired region, sensor nodes within the region process the query and start generating data at the speci ed rate if more than one entry for the same interest type exist, data is generated at the maximum rate of these entries. Data belonging to these interests are forwarded to each node for which a gradient exists at the rate speci ed for each individual gradient. After receiving low rate events from the source recall that the initial reporting rate is set low, the data sink support higher quality paths, which might be chosen as those that go through low latency or those in which the con dence in the received data is considered to be high by some application-speci c measure. Reinforcement message simply consist of the original interest messages set to higher reporting rates. These reinforced routes are set up so that a single or few paths from the event to the sink node are used. 13 Figure 2.8: Example of virtual grid in GAF Figure 2.9: State transitions in GAF 2.4.2 Location based routing protocols In this kind of routing, sensor nodes are addressed depending on their locations. The distance between neighboring nodes can be computed on strengths of incoming signal. Rel- ative coordinates of neighboring nodes can be getting by exchanging information between each other[3]. The location of nodes may be available directly by communicating with a satellite, using GPS(Global Positioning System), if nodes are equipped with a limited power GPS receiver. In order to save energy, some location based protocols request that the sensor nodes should go to sleep if there is no activity. ? Geographic Adaptive Fidelity(GAF) : GAF is a topology control protocol that was originally designed for use in common ad hoc networks[18]. GAF divides the network into a virtual grid and selects a single 14 node from each virtual grid cell to remain active as a designated router at a given time. As long as the cell dimensions are chosen small enough (transmissionrangep5 ) will retain neighbors in all directions and the network will be fully connected. Nodes initially enter the discovery state and listen for messages from other nodes within their cell. If another node within the cell is determined to be the designated router for the cell, the node will be a sleep state and conserve energy. From the sleep state, a node will periodically enter the discovery state. If a node determines that it should be the designated active router for its cell, it will enter the active state and participate in data routing, eventually falling back into the discovery state. As the density of a network implementing GAF increases, the number of activated nodes per grid cell remains constant while the number of nodes per cell increases proportionally. Thus, GAF can allow a network to live for an amount of time approximately proportional to a network?s density. A sample situation is depicted in Figure 2.8 , which is redrawn from [18]. In this gure, node 1 can reach any of 2, 3 and 4 and nodes 2, 3, and 4 can reach 5. Therefore nodes 2, 3 and 4 are equivalent and two of them can sleep. Nodes change states from sleeping to active in turn so that the load is balanced. There are three states de ned in GAF. These states are discovery, for determining the neighbors in the grid, active re ecting participation in routing and sleep when the radio is turned o . The state transitions in GAF are depicted in Figure2.9. Which node will sleep for how long is application dependent and the related parameters are tuned accordingly during the routing process. In order to handle the mobility, each node in the grid estimates its leaving time of grid and sends this to its neighbors. The sleeping neighbors adjust their sleeping time accordingly in order to keep the routing delity. Before the leaving time of the active node expires, sleeping nodes wake up and one of them becomes active. ? Geographic Hash Table(GHT) : GHT provides a convenient, data-centric method which means to store event-based data in wireless sensor networks[14]. Storing data in a dis- tributed manner provides an energy-e cient alternative in large-scale sensor networks. 15 When an event is sensed, the location at which the data related to the event should be stored is found by hashing its key to a location within the network. This location has no sensor node associated with it when it is hashed, but the data will eventually nd a home node closest to the hashed location. Once the location is determined, a data packet is sent using GPSR, although with no destination node explicitly included in the routing packet. Finally the packet will arrive at the closet node to the intended storage location, and GPSR will enter into perimeter mode, routing the packet in a loop around the intended location and eventually sending it back to the sensor node originally initiating the perimeter routing. 2.4.3 Hierarchical routing Hierarchical routing also called cluster-based routing is utilized to perform energy- e cient routing in wireless sensor networks. In a hierarchical architecture, the sensor nodes that have higher energy than others can be used frequently to process and send the informa- tion. It is an e cient way to lower energy consumption within a cluster and by performing data aggregation and fusion in order to decrease the number of transmitted messages to the base station. ? Low Energy Adaptive Clustering Hierarchy(LEACH)[7][8][9] : Heinzelan has proposed Low Energy Adaptive Clustering Hierarchy(LEACH) for e cient routing of data in wireless sensor networks. In LEACH, the sensor nodes elect themselves as cluster heads with some probability and broadcast their decisions. Each sensor node determines to which cluster it wants to belong by choosing the cluster head that requires the minimum communication energy. The algorithm is run periodically, and the probability of becoming a cluster head for each period is chosen to ensure that every sensor node becomes a cluster head at least once within 1/p rounds, where p is 5 percent of the number of all nodes. 16 Figure 2.10: PEGASIS protocols The positive aspect of LEACH is the fact that the sensor nodes will randomly deplete their power supply, and therefore they should randomly die throughout the network. On the other hand, the randomized cluster heads will make it very di cult to achieve optimal results. Since random numbers are utilized, the performance of the system will vary according to the random number generation and will not be as predictable as a system that is based on information that will lead it to make the best decision. LEACH-C was proposed in[6]. Unlike LEACH, where sensor nodes self- con gure themselves into clusters, LEACH-C uses a centralized algorithm that employs the sink between sensor nodes when deciding roles in LEACH, the cluster heads may be chosen such that there is no uniformity throughout the network and certain sensor nodes are focused to join clusters located at large distance from them. During the setup phase of LEACH-C, the sink node receives information regarding the location and energy level of each node in the network. Using this information, the sink node nds a predetermined number of cluster heads and con gures the network into clusters. The cluster groupings are chosen to minimize the energy required for non-cluster head nodes to transmit their data to their respective cluster heads[6]. 17 ? Power E cient Gathering in Sensor Information Systems(PEGASIS) : Power-E cient Gathering in Sensor Information System(PEGASIS)[15] is near optimal for this data gathering application in wireless sensor networks. The key idea in PEGASIS is to form a chain among the sensor nodes so that each node will receive from and transmit to a close neighbor node. Gathered data moves from a sensor node to another node, get fused, and eventually a designated node transmits to the sink node. Nodes take turns transmitting to the sink node so that the average energy spent by each node per round is reduced. The PEGASIS protocol achieves between 100% to 300% improvement when 1%, 20%, 50% and 100% of nodes node die compared to the LEACH protocol. If sensor nodes are not within transmission range of each other, then alternative, possibly multi- hop transmission paths will have to be used. To ensure balanced energy dissipation in the network, an additional parameter could be considered to compensate for sensor nodes that must do more work every round. If the sensor nodes have di erent initial energy levels, then we could consider the remaining energy level for each sensor node in addition to the energy cost of the transmissions. PEGASIS enhances network lifetime by increasing local collaboration among sensor nodes. In PEGASIS, sensor nodes are arranged in a chain topology using a greedy algo- rithm so that each sensor node transmits to and receives from only one of its neighbor nodes.(Figure 2.10) Every round a randomly chosen sensor node from the chain will transmit the aggregated data to the sink node, thus reducing the per round energy consumption compared to LEACH. ? Hybrid Energy-E cient Distributed Clustering(HEED) : HEED[23] uses an iterative cluster formation algorithm, where sensor nodes assign themselves a cluster head prob- ability that is a function of their residual energy and a communication cost that is a function of neighbor nearness. Using the cluster head probability, sensor nodes decide whether or not to advertise that they are a candidate of cluster head for current round. 18 Based on these advertisement messages, each sensor node selects the candidate of clus- ter head with the lowest communication cost which could be the sensor node itself as its tentative cluster head. This procedure iterates, with each sensor node increasing its cluster head probability at each iteration until the cluster head probability is one and the sensor node declares itself a nal cluster head for this round. The advantage of HEED is that sensor nodes only require neighborhood informa- tion to form the clusters, the algorithm terminates in O(1) iterations, the algorithm guarantees that every sensor node is part of just one cluster, and the cluster heads are distributed evenly. 2.5 Routing protocols based on protocol operation 2.5.1 Multipath routing protocols These routing protocols use multiple paths rather than a single path in order to improve the network performance. The fault tolerance of a protocol is measured by the probability that a substitution path exists between a source and a destination when the primary path fails. These substitution paths are kept alive by sending periodic messages. So, network dependability can be increased at the expense of increased overhead of maintaining the substitution paths. 2.5.2 Query based routing In query based routing, the destination nodes propagate a query for data from a node through the network. Then, if the other sensor nodes have this data sends the data which matches the query back to the node. 19 2.5.3 Negotiation based routing protocols This type protocols use high level data descriptors in order to avoid redundant data transmissions through negotiation[13]. Communication decisions are taken based on the resources. The motivation of negotiation based routing protocols is that the usage of ooding to transmit data will produce implosion and overlap. So nodes will receive duplicate copies of the same data. This operation consumes more energy. Therefore, the main idea of negotiation based routing in wireless sensor networks is to prevent duplicate information and decrease redundant data. 2.5.4 QoS-based routing In QoS-based routing protocols, the network has to balance between energy consumption and data quality. In particular, the network has to satisfy certain QoS metrics, for example delay, energy, bandwidth and so on when delivering data to the base station. Sequential Assignment Routing(SAR)[4] proposed is one of the routing protocols for wireless sensor networks. Routing decision in SAR is dependent on three factors: energy resources,QoS on each path, and the priority level of each packet. 2.5.5 Coherent and non-coherent processing Data processing is a major component in the operation of wireless sensor networks. Sensor nodes will cooperate with each other in processing di erent data ooded in the network area. Here are two examples of the proposed wireless sensor networks of coherent and non-coherent data processing-based routing. In non-coherent data processing routing, nodes will locally process the original data before it is sent to other nodes for further processing. In coherent routing, the data is forwarded to collectors after some processing. The processing includes such tasks like time stamping, duplicate suppression. 20 Chapter 3 Problem Statement, Objective, and Our Approach This chapter aims at investigating problems of the existing algorithms and, describe our approach to solve the problems. The problems with LEACH causing Bad-case scenario in formating CH(Cluster Head)s are discussed in this chapter. 3.1 Problem Formulation The residual energy at a node in the sensor network is a signi cant parameter for cluster heads. In this thesis, both of the LEACH and PEGASIS harnessed the residual energy of the node so as to extend lifetime of the sensor network, but both of them were not free from the following problems. LEACH use a random method with a self-organizing clustering based protocol to evenly distribute energy loads between each sensor, coincidently electing CH with a probability. For selecting CHs, each sensor choose a random number between 0 and 1 inclusive[7]. If this is lower than the threshold for node n, T(n), the sensor node becomes a cluster head. The threshold T(n) is given by Eq.(3.1) T(n) = 8 >< >: P 1 P(r mod 1P ); ifn2G 0; otherwise (3.1) P represents a probability of electing as CH out of entire nodes, r means current round, and G is node group that is not elected as head in previous 1=P round. According to the 21 Figure 3.1: Cluster head rotation good-case in LEACH Figure 3.2: Cluster head rotation bad-case in LEACH equation(3.1), LEACH ensures that every node in previous 1=P round exactly becomes CH at least one time. Likewise, high probability of CH alone was in use regardless of creation between LEACH clusters, and therefore LEACH is created in case of adjacent nodes electing cluster headers. In event of this case, a few nodes communicates with CHs stationed in long distance, and also communication between sensor nodes in the network may increase probability of communication collision. With performance of LEACH, a constant number of clusters can be generated each round,and CHs are evenly deployed. However,it cannot be ensured by self-electing method, and thereby LEACH-C algorithm determining CH and cluster was suggested in consideration of location information of sensor node and its energy holding volume at sink. When the cluster head rotation in LEACH protocol, the good-case and the bad-case scenario is displayed. (Figure3.1 and 3.2)[6]. 22 In Figure3.1, cluster heads are put in place in the next round and therefore sensors energy can be e ciently managed via e cient con guration for clusters as expected for the rst time in LEACH. However, as shown in Figure 3.2, it is placed around the edge of cluster head network or adjacent node becomes cluster head. In this case, a speci c node occasionally sends some amounts of data to cluster head through long distance. Accordingly, each energy of nodes in each cluster may not be well managed. This is at odds with initial attempt to decease the energy load between each node by rotating cluster head probabilistically. The most signi cant cause of this case comes from the rotation based on probability of cluster head being elected in LEACH. Thereby, this study employs electing cluster head based on the energy of sensor nodes rather than that of LEACH. 3.2 Objective The primary objective of this study is to implement energy-e cient cluster head election algorithm. The sensor nodes operate with limited energy, the energy savings based on various tra c environments to optimize the maximum life of the entire network to extend the algorithm is to elect a cluster head. Also LEACH has some disadvantages that are already mentioned so a new energy adaptive clustering method is required. In this protocol e orts are made to balance the energy consumption in all cluster process, as the result, we want to prolong network lifetime is required. 3.3 Our approach to solve the problems To solve the problems LEACH has, we consider the fact that number of clusterheads generates unbalance every round and the low energy node may be selected as clusterhead many times. Thereby our study is focused on other protocols in hierarchical routing. What is suggested to resolve this problem of LEACH is the modi ed-LEACH(m-LEACH), where the energy of sensor node is used by leveraging energy as parameter in de ning value 23 of T(n). The value for T(n) in the m-LEACH is de ned as the Eq. (3.2) T(n) = EncurrentEn max P 1 P(r mod 1P ) (3.2) Encurrent represents current energy, and Enmax is the initial energy at node. The m-LEACH more prolongs the network lifetime than LEACH. But it has the disadvantage that it must know every node?s energy status. In the case of HEED, an excellent way to elect CH is used, in which a parameter of the node itself is used in determining CH. When energy of most nodes is low, there is a shortcoming that most of the nodes may become CH because the number of nodes that are reaching 1 is on the rise in case of multiplying probability value of electing CH by multiples of 2. But when all nodes energy is low, HEED can not support optimal CH election probability. In the case of PEGASIS, every round a randomly chosen sensor node from the chain will transmit the aggregated data to the sink node, thus reducing the per round energy consumption compared to LEACH. PEGASIS is an interesting approach, however there is the potential to achieve better performance for many applications because of three reason : (1) the clustering is based on random clusterheads, (2) 100% aggregation is not realistic for many applications, and (3) the chain described in PEGASIS is not an optimal routing model. Our research focus on the LEACH and PEGASIS. HEED does not give the better results than the PEGASIS, so we exclude the HEED. There is performance evaluation in comparison with this two factors and suggesting protocol in chapter 5. In many other theses some mechanisms regarding the energy of sensor node were proposed, but we will focus on LEACH and PEGASIS for comparison in this thesis because there is a di erence between previous work and this thesis regarding focusing on leveraging the network model. 24 Chapter 4 Design of Energy e cient cluster head election algorithm This chapter introduce a new algorithm in order to resolve the problems and to maximize entire lifetime of the sensor network. 4.1 Network model key features The key features of scheme are listed in the followings: ? Sensor network consists of a cluster ? CHs that supply the energy continuously are present in each cluster ? CHs know the location of sensor node and ID ? All except the CH sensor nodes are homogeneous properties and their energy is limited ? CHs can communicate directly with each node within the same cluster ? Each sensor node knows the initial energy and residual energy ? A Round consists Set-up phase and Steady-state-phase ? Cluster Head features - It has more computational power than sensor nodes - Long-distance communication capabilities to communicate with other cluster heads and can communicate with BS - One per cluster exists - Integrate the data from the sensor nodes, then send it to BS 25 4.2 Design of the cluster head election algorithm This following approach presents a protocol to e ciently harness sensors energy which called the ELP (Enhanced LEACH Protocol). The ELP is proposed based on LEACH. As previously discussed, because in cluster-based network model a node nearest to CH not only senses by itself but also conveys data from other sensors to CH, these nodes relatively shorten their lifetime. Therefore the energy-e cient CH electing protocol suggested in this paragraph is for sensor nodes to elect CH in a bid to evenly use energy. It is based on self- organizing, cluster-based protocol, and is capable of avoiding creation of Bad-case scenario cluster without any device checking location information. In the case of LEACH-C, it is e cient to create clusters, but has the issue of overhead cost because each node sends its information to the BS each time prior to being elected. If whole nodes reach 100 (N=100), and targeted cluster head election ratio is 0.05 (p=0.05), the number of CHs accounted for in the entire network will be 5 (N*P). And the number of nodes existing in a cluster reaches up to 20 (1/p). Electing each CH should be repeated every 20 rounds (1/p) in order to elect more energy-e cient CH. As being identical to LEACH, nodes pick any number between 0 and 1 at the time of electing CH. If the selected number at each node is less than T, the node is selected as CH in the round. Throughout this process, each node can have the chance to become cluster head up to k times at maximum in consideration of initial and current energies of each node. In this thesis enhanced-algorithm is proposed as follows: In the following formula, P represents the clusterhead probability. T(n), in de ned, as in Eq. (4.1) T(n) = 8 >< >: pP 1 P(r mod 1P ) pE ci; ifEp Eci 0; otherwise (4.1) 26 Eci represents the current energy of each elected node, Ep means energy of previous node, P is the ratio that ideal cluster heads accounted for in entire nodes (here assume 5%), and r is round. The proposed algorithm uses a new threshold formula. In this formula threshold is in relation to the nodes current energy and the previous energy among sensor nodes. Also a condition is made for electing CH. If the current energy of node is much than the previous energy of node, the node can elect CH. Otherwise, it can not be elected. Also the node energy is decreased and then the probability to elect cluster head is also decreased, resulting in the limitation that any node can not become a cluster head eventually. Therefore, the current energy of each elected node is added for compensating this limitation. Square is applied to compensate the value by multiplying the formula for the cluster head by the energy value. In an attempt to evenly distribute electing cluster heads, according to the Eq.4.1, if the number of nodes that are elected as cluster heads are raised, the probability to elect cluster head decreases, and then the formula increases or decreases the probability every 1=p round under the mod function. Eq.4.1 is used in an algorithm to compensate the probability to elect cluster heads in consideration of nodes energy variation depending on the round. 4.2.1 Cluster creation and data transmission LEACH is applied to cluster creation and data transmission. If a cluster head is elected by the algorithm proposed, each cluster head propagates an ADV(Advertisement) message including its ID. Then the other usual node selects cluster head having big RSS(Received Signal Strength) as its CH and transmits both of its ID and the selected cluster head ID. The CH node that received the ID information begins recognizing nodes within its cluster head, and sending TDMA schedule. The usual nodes send data from their time slot included the TDMA schedule, and save energy by radio o at the other slots. 27 Chapter 5 Performance Evaluation 5.1 Simulation model A typical sensor node consists of four major components: a data processor unit, a micro- sensor, a radio communication subsystem that consists of transmitter/receiver electronics, antenna, an ampli er, and a power supply unit. Although energy is dissipated in all of the rst three components of a sensor node, we mainly consider the energy dissipations associated with the radio component since the objective of this paper is to develop an energy e cient network layer protocol to improve network lifetime. In addition, energy dissipated during data aggregation in the cluster head nodes is also taken into account. For the radio model, same model is used as discussed in [7][25](Figure. 5.1). The energy cost for the transfer of a l-bits data message between two sensor nodes separated by a distance of d meters is given by Eq.(5.1),(5.2). ETx(l;d) = 8 >< >: LEelec + L"fsd2; ifd d0 LEelec + L"mpd4; ifd > d0 (5.1) ERx = LEelec (5.2) where ETx(l;d) indicates the total energy for transmission of the source sensor nodes, and ERx (l) = Eelec * L expresses the energy cost incurred in the receiver of the destination sensor node. The parameters ETx, ERx in equation 5.1 and equation5.2 are the energy consumption 28 Figure 5.1: Communication model between the sensor node for communication. "amp(d) is the energy required by the transmit ampli er to maintain an acceptable signal-to-noise ratio in order to transfer data messages safely. Also both the free-space propagation model and the two-ray ground propagation model are used here to approximate the path loss sustained due to wireless channel transmission. Given a threshold transmission distance of d0 the free-space model is employed when d d0. Using these two models, the energy required by the transmit ampli er "amp(d) is given by Eq.(5.3). Eamp(d) = 8 >< >: "fsd2; ifd d0 "mpd4; ifd > d0 (5.3) where "fs and "mp denote transmit ampli er parameters corresponding to the free-space and the two-ray models. Cluster head and non-cluster head in a round, the energy consumption is given by Eq.(5.4),(5.5). ECH = (nk 1)LEelec + nkLEDA + LEelec + L"fsd2BS (5.4) EnonCH = LEelec + L"fsd2CH (5.5) 29 Cluster head and non cluster head in one cluster, total energy consumption is given by Eq.(5.6). Ecluster = ECH + (nk 1)EnonCH (5.6) Thus, the total energy consumption in the network is given by Eq.(5.7). Etot = Lf2nEelec + nEDA + "fs(kd2BS + nd2CH)g (5.7) We assumed the same set of parameters used in for all experiments throughout this thesis : ETx = ERx = 50nJ=bit , "fs = 100pJ=bit=m2 and "mp = 0:0013pJ=bit=m4. Also, the energy cost for data aggregation is the set as EDA = 5nJ=bit=message[16]. 5.2 Simulation Environments Throughout the simulation, a 100 X 100 network con guration with 100, 200 and 300 nodes is considered where each sensor node is assigned an initial energy of 0.5 J, the amount of transmission energy is 50 nJ=bit, transmit ampli er energy (Eamp) is 100 pJ=bit. In our simulations, all sensor nodes are assumed to carry out sensing operation at a xed rate and always have data to send when they receive messages from the sink node. It is also assumed that all data sent by the previous nodes are aggregated into a data segment with a constant size of 4000 bits. Table 5.1 summarizes the simulation parameters. Figure 5.2 is about the sensor nodes distributed status in simulation environment. In the gure, x stand for sink, and the other marks stand for the nodes. 30 Table 5.1: Simulation Parameters Parameter Value Parameter Value Network size 100X100 "fs 100 pJ=bit=m2 Number of nodes 100 / 200 / 300 "mp 0.0013 pJ=bit=m4 Sink location (50;50) Eelec 50 nJ=bit=report Packet size 4000 bits EDA 50 nJ=bit=report Initial energy 0.5J probability 0.05 Figure 5.2: Distributed node in network environment 5.3 Simulation results In this section, we evaluate the performance of the new energy e cient protocol imple- mented with MATLAB. For simplicity, we assume the followings: ? All nodes know their position ? All nodes have equal initial energy With the simulation parameters listed in the previous section, the performance of our meth- ods is estimated. Also we compared their performance with LEACH protocol. The criteria for performance comparison we used are the sensor lifetime, the energy consumption and cluster formation. 31 Figure 5.3: Lifetime using direct transmission, MTE routing, static clustering, and LEACH with 0.5 J/node[7] We simulated LEACH with a probability of 5% that each node elects itself as a cluster head. Also, we have simulated the di erent cases based on of the number of nodes : 100, 200 or 300. 5.3.1 Node lifetime simulation First of all, in order to compare the proposed algorithm and LEACH protocol, we show the node lifetime simulation results from Heinzelmans reseach paper. As shown in Figure 5.3 that LEACH protocols useful system lifetime gets more than doubled compared to the alternative approaches. It takes approximately 8 times longer for the rst node to die and approximately 3 times longer for the last node to die in LEACH unlike in any of the other protocols. Figure 5.4 show the number of dead nodes, where X-axis presents simulation time and Y- axis presents the number of dead nodes. The life time is an important issue in wireless sensor networks, so it is essential to compare the number of dead nodes number among protocols. Figure 5.4 shows the three cases (100, 200, and 300 nodes). When using a network size of 100 32 x 100 meters, and 100 nodes, the rst dead node appears at round 879 in ELP, whereas the rst dead node appears at round 735 in the LEACH. However, when the number of nodes is increased to 200 or 300, the round in which the rst dead node appears in the LEACH algorithm is later than in ELP, but as time passes, the ratio of dead nodes to live nodes is noticeably less in the ELP algorithm. Given 200 nodes, the rst dead node appears faster than 729 rounds in which the rst dead node in the LEACH algorithm occurs. Accordingly, the rst dead node occurs from 697 rounds. However, the proposed algorithm can be known to get lower in the ratio for the occurrence of dead nodes after 784 rounds, which is that 87 rounds passed. Given 300 nodes, the rst dead node occurs at 596 rounds in ELP, thus the dead node occurs faster than the LEACH algorithm in which the rst dead node occurs at 696 rounds. However, the ratio in the occurrence of dead nodes for the proposed algorithm gets lower after 754 rounds. Thus, lifetime gets longer as a whole. Table 5.2 shows the round in which the rst dead node appears for 100, 200, 300 nodes, in both algorithms. As shown in the Figure 5.5 and 5.6 (N=200 and 300) dead nodes curve is suddenly up from 0 to 200 or 300 nodes. Because there is an unbalanced number of nodes in limited space(100 X 100 m), it spends more energy for the communication of each cluster and within it. For another comparison, the node life time is compared having di erent energy level. To begin with, the initial energy 0.25 J/node is increased by 0.25 J/node. As shown in Figure5.7, there is not much di erence in ELP and LEACH with lower initial energy, but as soon as the energy is increased, the node lifetime of LEACH and ELP gap gets bigger. The data from these experiments is shown in Table 5.3. Table 5.2: First dead node appears in leach and ELP 100 nodes 200 nodes 300 nodes LEACH 735 729 696 ELP 879 697 596 Change round 784 754 33 0 200 400 600 800 1000 1200 1400 1600 0 10 20 30 40 50 60 70 80 90 100 x(time) y(Dead node) LEACH ELP Figure 5.4: The number of dead nodes with time(N=100) 200 400 600 800 1000 1200 1400 1600 0 20 40 60 80 100 120 140 160 180 200 x(time) y(Dead node) LEACH ELP Figure 5.5: The number of dead nodes with time(N=200) 34 200 400 600 800 1000 1200 1400 50 100 150 200 250 300 x(time) y(Dead node) LEACH ELP Figure 5.6: The number of dead nodes with time(N=300) 0 500 1000 1500 2000 2500 3000 0 10 20 30 40 50 60 70 80 90 100 x(time) y(Dead node) LEACH ELP 0.25 J 0.75 J 0.5 J Figure 5.7: Lifetimes using di erent amounts of initial energy for the sensors 35 Table 5.3: Lifetimes using di erent amounts of initial energy for the sensors Energy Protocol First node dies Last node dies 0.25 LEACH 362 651 ELP 387 1192 0.5 LEACH 722 1624 ELP 815 1977 0.75 LEACH 1110 1656 ELP 1423 2681 5.3.2 Energy-time simulation Figure 5.8 and 5.9 show the energy consumption, where X-axis is the simulation time and Y-axis is the total energy consumed during simulation. As shown in Figure 5.8 comparing single rounds in LEACH and ELP, the energy quantity consumed in single round in light of the whole network, is larger in LEACH than in ELP. ELP shows high energy consumption between 10 and 20 nodes, but has less energy that is consumed by the total number of nodes. On the other hand, LEACH is consistent in high energy consumption by each node, and has larger energy consumption in 90 nodes than ELP. As shown in Figure 5.9, ELP has a longer lifetime than LEACH. Comparing the energy consumption in the entire number rounds, it can be seen that the reduction in energy of ELP is slower than the reduction in energy of LEACH. It is known that LEACH consumes all of the energy at 900 rounds, but ELP is nished in about 1300 rounds. This proves that simply changing the cluster head selection method leads to being capable of enhancing the lifetime of the entire network. Also, the energy in the entire network is compared with PEGASIS. As seen from the graph above, PEGASIS is better in energy management more than LEACH, as mentioned already in Chapter 2. In the actual energy use, there is di erence by over 3 times. However, this part aims to show improvement on lifetime of the whole network. Thus, the aim is to examine how much longer its lifetime is than the proposed algorithm. When comparing only the energy aspect, PEGASIS has larger energy of the entire network, 36 0 10 20 30 40 50 60 70 80 90 100 ?0.02 ?0.018 ?0.016 ?0.014 ?0.012 ?0.01 ?0.008 ?0.006 ?0.004 ?0.002 0 Node Energy LEACH ELP Figure 5.8: Energy of a single round 0 200 400 600 800 1000 1200 1400 ?0.5 0 0.5 1 1.5 2 2.5 3 3.5 4 x 10 ?4 round Energy Energy Comparison of LEACH and ELP LEACH ELP Figure 5.9: Ensemble average of the energy of all the rounds 37 860 880 900 920 940 960 980 1000 1020 0 0.5 1 1.5 2 2.5 3 3.5 4 x 10 ?5 round Energy LEACH ELP PEGASIS Figure 5.10: Compare of the energy with PEGASIS protocol up to 880 rounds more than ELP. However,ELP gets smaller in energy consumption from after 880 rounds. And, when approaching 1020 rounds, the lifetime comes to end. In Figure 5.9, ELP can be known to have a longer lifetime in terms of energy consumption than PEGASIS or LEACH. 5.3.3 Number of Clusterhead simulation As for the existing LEACH, 4 6% of the whole nodes, which were proven to be optimization, are selected as CH. Here, the number of formed CH between LEACH and ELP will be compared. Figure 5.11 and 5.12 indicate the number of CH up to 300 rounds when nodes in LEACH and ELP are 100 and 200. In the case of LEACH, CH formation is shown within 4 6% of the whole nodes when number of nodes is 100 and CH formation in the range of 7 12% when the number of nodes is 200. On the other hand, ELP shows CH formation larger than LEACH in the initial round when the number of nodes are 100, and then shows CH formation within the range of 3 7% in the later rounds. Given 200 nodes, it showed CH number smaller than LEACH, having CH in 5 10%. ELP can be known 38 0? 2? 4? 6? 8? 10? 12? 14? 1? 30? 59? 88? 117?146?175?204?233?262?291? LEACH(n=100)? LEACH(n=200)? Figure 5.11: Number of the clusterhead in LEACH 0? 2? 4? 6? 8? 10? 12? 1? 30? 59? 88? 117? 146? 175? 204? 233? 262? 291? ELP(n=200)? ELP(n=100)? Figure 5.12: Number of the clusterhead in ELP to show a larger deviation in the number of CH, when compared to LEACH. The reason is that the square root applied to the probability and energy, did not cause a linear increase in the threshold when considering the energy in the CH selection formula. 39 Chapter 6 Conclusion This thesis proposed routing protocol for increasing lifetime of network by e ciently managing sensor-node energy based on clustering. In wireless sensor network, as LEACH protocol is a typical clustering protocol, it consumes energy e ciently by forming cluster. However, it fails to e ciently compare nodes? energy in the clustering phase, and thus results in forming bad-case scenario, thereby failing to extend network lifetime more lengthily. Ac- cordingly, this thesis applied CH selection threshold by comparing the energy in the current round and the energy in the previous round by using the existing LEACH routing, and al- lowed CH probability to be compensated, thereby providing a change in the whole threshold value. It allowed the residual energy amount to select many nodes with CH according to this amended formula. The e ect extends the whole network lifetime, by applying CH selection variable according to energy consumption and data quantity to the existing CH selection probability. This result could be known to be enhanced the protocol, which was suggested in Chapter 4, and the protocol, which was proposed through comparison between LEACH and PEGASIS, in the whole network lifetime. There had been a case that the rst dead node in ELP occurs rst according to node density. However, there was more number of the surviving nodes than the existing protocol after passage of the certain time. Even the energy amount, which is consumed in the whole network energy and one round, was shown to be less. But there remained a problem about the number of clusterhead. When comparing the number of clusterhead between the ELP and LEACH, ELP has a larger deviation in the number of clusterhead. So it is necessary to reduce a larger deviation, for more reliable communication quality. Therefore further work is about how to solve this problem. 40 Bibliography [1] I. F. Akyildiz and W. Su and Y. Sankarasubramaniam and E. Cayirci, \Wireless sensor networks: a survey," Computer Networks, Vol.38, pp. 393{422, March 2002. [2] Jamal N. Al-Karaki, Ahmed E. Kamal, \ Routing Techniques in Wireless Sensor Net- works: A Survey," IEEE Wireless Communications, Vol 11. pp.6-28, Dec. 2004. [3] S. Capkun, M. Hamdi, J. Hubaux, \ GPS-free positioning in mobile ad-hoc networks," Proceedings of the 34th Annual Hawaii International Conference on System Sciences, pp. 3481-3490, 2001. [4] M. L. Fisher, R. Jaikumar, \ A generalized assignment heuristic for vehicle routing," Networks, Vol 11. Issue 2, pp. 109 - 124, Oct 2006. [5] F. L. Lewis, \ Wireless Sensor Networks," Technologies, Protocols, and Applications ed. , Wiley, New York, 2004. [6] M.J. Handy, M. Haase, D. Timmermann, \Low Energy Adaptive Clustering Hierarchy with Deterministic Cluster-Head Selection", IEEE MWCN, 2002. [7] W. Heinzelman, A. Chandrakasan, and H. Balakrishnan, \Energy-E cient Communi- cation Protocol for Wireless Micro-sensor Networks," Proceedings of the 33rd Hawaii International Conference on System Science (HICSS ?00), Jan 2000. [8] W. Heinzelman, A. Sinha, and A. Wang, A. Chandrakasan, \ Energy-scalable algorithms and protocols for wireless microsensor networks," Proc. International Conference on Acoustics, Speech, and Signal Processing(ICASSP ?00), June 2000. [9] W. Heinzelman, A. Chandrakasan, and H. Balakrishnan,\An application- speci c pro- tocol architecture for wireless microsensor networks," IEEE Transaction on Wireless Networking, 2002. [10] W. Heinzelman, Joanna Kulik, Hari Balakrishnan,\Adaptive protocols for information dissemination in wireless sensor networks," Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, pp. 174-186, 1999. [11] J. Ibriq and I. Mahgoub, \Cluster-Based Routing in Wireless Sensor Networks: Issues and Challenges," Proceeding of the 2004 Symposium on Performance Evaluation of Computer Telecommunication Systems, pp. 759-766, Jul. 2004. 41 [12] C. Intanagonwiwat, R.Govindan, and D. Estrin,\ Directed di usion : scalable and ro- bust communication paradigm for sensor networks," Proceeding of ACM MobiCom ?00, pp. 55-67, 2000. [13] J. Kulik, W. Heinzelman, H. Balakrishnan, \Negotiation-Based Protocols for Dissemi- nating Information in Wireless Sensor Networks,"Wireless Networks,Volume 8, pp.169- 185, March, 2002. [14] Sylvia Ratnasamy, Brad Karp, Li Yin, Fang Yu, Deborah Estrin, Ramesh Govindan, and Scott Shenker,\GHT: a geographic hash table for data-centric storage," Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, pp. 78-87, 2002. [15] S. Lindsey, C. Raghavendra, \PEGASIS: Power-E cient Gathering in Sensor Informa- tion Systems," IEEE Aerospace Conference Proceedings, Vol. 3, 9-16 pp. 1125-1130, 2002. [16] G. Smaragdakis, I. Matta, and A. Bestavros, \SEP: A stable election protocol for clus- tered heterogeneous wireless sensor networks," In Second International Workshop on Sensor and Actor Network Protocols and Applications, 2004. [17] B. Warneke, M. Last, B. Liebowitz, K. Pister, \ Smart Dust: Communicating with a cubic-millimeter computer," IEEE Computer, pp.2-9, January 2001. [18] Ya Xu, Solomon Bien, Yutaka Mori and John Heidemann, \ Topology Control Proto- cols to Conserve Energy in Wireless Ad Hoc Networks," IEEE transactions on mobile computing, 2003. [19] Cees Links, GreenPeak Technologies, http://www.altenergymag.com/emagazine.php [20] Matt Welsh, Harvard University, http://www.snm.ethz.ch/Projects/ SensorNetworkEx- perimentalData [21] R. Myllyl, M. Moilanen, Optoelectronics and Measurement, Optoelectronics and Mea- surement Unit (OPME), http://www.infotech.oulu. /Annual/2007/opme.html [22] ECE, VirginiaTech,http://www.ece.vt.edu/news/fall05/sensornetwork.html [23] O. Younis, S. Fahmy, \HEED: A Hybrid, Energy-E cient, Distributed Clustering Ap- proach for Ad Hoc Sensor Networks," IEEE Transactions on Mobile Computing, 2004. [24] M. Youssef, N. El-Sheimy, \ Wireless Sensor Network: Research vs. Reality Design and Deployment Issues," Communication Networks and Services Research Conference, 2007. [25] Qin Wang, M. Hempstead, and W. Yang,\A Realistic Power Consumption Model for Wireless Sensor Network Devices", In SECON 06: Sensor and Ad Hoc Communications and Networks, pp.286-295, 2006. 42