A Study On Wireless Sensor Networks Computer Science Essay

Published:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Because of the growing development in the field of micro electromechanical systems to reduce their power consumption and integration, tiny sensors has been made, which have sensor and communication capabilities. These sensors collected data from the environment and after processing, send them to different destinations as electrical signals schema. Thus nodes have at least three main obligations: to feel, send and aggregate data. A lot of researches have been done to reduce the cost and size of sensors. Reduce the cost and size of nodes due to use a large number of these sensors in a wide range [75]. The way for have a network of these sensors is wireless, so that the network has behavior similar to the behavior of ad hoc networks. Structure of these networks presented in figure 2.1.

Figure 2.1 Network Structure

Sensor nodes have limitations in bandwidth and energy consumption. Energy of each node is limited to its battery and in most networks these are not rechargeable, so this is necessary for all designed layers in the architecture of such networks that have high efficiency from the perspective of power consumption.

Wireless sensor networks compared with other wireless networks

Wireless sensor networks have many differences with Ad hoc, Mobile and LAN wireless networks and this due to the architecture, purpose, application, and efficiency of each of these networks. Some of the features and limitations of sensor networks that makes separate them from other networks are as follows [6] [4] [17] [86]:

Number of nodes in sensor networks, much more than the number of nodes in other wireless networks.

Usually sensor nodes are stationary, so not required to Ad hoc and Mobile networks mechanisms for being mobile nodes in sensor networks.

Nodes are prone to damage.

Sensor networks connectivity can be changed regularly.

Communication in sensor networks is broadcast; while in the Mobile wireless networks communications are Point-to-Point.

Sensor networks nodes have limitations on energy constraints, capacity calculations, memory, and process.

The position of sensor nodes in these networks, don't require previous design and they can have random distribution in a region.

In wireless networks all nodes send their data to one or more nodes that called sink and the relationship between networks and users is done through this node(s).

Sensor networks have data-centric nature not address-centric, thus allocated unique address to nodes are not necessarily.

Sensor network architecture

Sensor network consists of many small sensor nodes that have the ability of sense and data processing. These nodes include hardware and software components that are using these components to communicate with each other. Nodes to communicate with each other generally use wireless communication [45]. The structure of sensor networks is that a large number of sensor nodes are scattered in the environment and after collecting information send them to another node or a central receiver or base station. Central receiver can be a fixed or a mobile node with high energy levels and sufficient. In networks with large geographic area can be used to reduce the path length with use several of the sink.

Hardware components

Each node can be a variety of components considering to performance of different sensor networks and different tasks for nodes in network. But in general, each sensor node comprise sensing and processing units, transceiver, analog to digital convertor, power unit, mobilizer, position finding system, memory and GPS if needed. Figure 2.2 is shown the hardware components of a node. We have some hardware constraints on nodes because of being the economic system, expected capabilities and require huge number of nodes in the network. Some of these limitations are as follows: Small physical size for high efficiency and because of not draws attention to nodes in most applications; Construction cost because of need to use large number of nodes in the network; Power consumption because of limitation on energy source and not possible to replacement or recharge nodes battery. In Independence limitation, each node should be able to perform its duties independent of other nodes. Since the increase in Processing power its reason to increase energy consumption, so cannot use of micro controllers with high process power. Every node should be able to adapt its status to new occurred conditions

Fig2.2: Hardware component in WSNs

Software Components

Sensor nodes, generally including operating systems, sensor drivers, communication processor and drivers, and small applications for data processing. There are different used operating systems in sensor networks, but few of them efficient in limitations of wireless sensor networks. Contiki and Tiny OS are some example of operating systems that use in wireless sensor networks [28]. Communication processors are software modules which include base functions for communicate with sensors, and communication drivers include function in relate with radio channel such as clock, concurrency, signal coding and etc. small applications for data processing are used in processing, storing and retrieving data in node layer and data processing, aggregation, manipulation and store data in network layer.

Sensor network applications

Sensor nodes may include various types of sensors that have capabilities such as seismic, low sampling rate, temperature measurement, visual, auditory, radar, meteorology, etc. Nodes that use these sensors are capable to monitor environmental conditions such as temperature, humidity, vehicles mobility, pressure, noise level, presence or absence of a specific object in the environment, the level of mechanical pressure on a common object and features such as speed, direction [87][7]. Because of the nodes ability to environmental monitoring sensor networks can be used in many applications that some of them are:

Military applications

Wireless sensor networks can be an integral part of military command, control, communications computing, intelligence, surveillance, reconnaissance and targeting systems [7]. Due to the dense deployment, availability and low cost specification of sensor nodes, destruction of a node not affect to the whole network in compared with other wireless networks, which make sensor networks a better approach for battlefields.

Environmental applications

Tracking the movements of birds, small animals and insects; large-scale earth monitoring, forest fire detection, environmental pollution study, earth and environmental monitoring in marine, soil and atmospheric contexts; are some environmental application that used in sensor networks [].

Medical applications

Some medical applications for wireless sensor networks are diagnostics, integrated patient monitoring, drug administration in hospitals, tracking and monitoring doctors and patients inside a hospital and etc.

In addition to cases mentioned above sensor networks use in some other applications such as smart transportation systems, monitoring disaster area after accidents, flood or earthquake, smart structures with sensor nodes embedded inside , and research studies ground and under water [7]

Routing in sensor networks

Routing in sensor networks is more challengeable, due to the special features of these networks that built them separate from other networks. The following refers to some of these features are:

For nodes addressing cannot be used the unique addressing and thus IP-based algorithms do not use in these networks.

Nodes have a same behavior with Ad hoc network nodes and need to self auto organization and accordance with the network nodes distribution.

In many applications collect data have more importance than the sender recognition.

Nodes are required to send data from different areas to the sink node.

Nodes have their limitations, such as energy consumption, power processing and storage capacity.

Data collected from the entire network due to overlapping coverage areas of nodes are considerable redundancy and routing algorithms must with use of data aggregation algorithms reduce using bandwidth and energy consumption.

Routing Challenges and Design Issues in WSNs

Many factors influence the routing algorithms are designed. To design a routing algorithm should be noted that these factors. In this section we investigate some of these factors, we will.

Node deployments

How the placement of nodes in the network depends on the application and impact on routing in the network. Placement of nodes in the network can be occurring definite or random. In definite method nodes placed manually and clustering can be performed before and routing does during the predefined paths. In self-organizing approach, nodes are spread randomly over the network and location status of sink and cluster heads have determining role in the energy consumption, scalability and network lifetime.

Data delivery models

Depending on the application, the data delivery model to the sink node can be continuous, event driven, based on request or be a combination of these. In continuous model, each node sends data to sink intermittently and continuous. In event driven and request-based models data transfer is done when the event occurs or request is issued by the sink. In hybrid model, a combination of three methods can be used. Routing algorithms are very affected by the data delivery model.

Node capabilities

Sensor nodes considering some features such as surface energy, processing power, memory size, physical size, hardware and software components and different ability of sense, will have different capabilities and applications. Capabilities of all network nodes can be assume the equal. But in some applications it is necessary that some nodes be different from other nodes. For example, in some hierarchical algorithms cluster heads have more energy, bandwidth and memory than other nodes, and this is due to that these nodes do high volumes of send and receives data operations. In addition, in some applications may be some nodes sense thermal events and some other nodes sense light, humidity, and etc events.

Fault-Tolerance

Each sensor node if its energy reaches completion or is broken, it is not applicable and will be getting out from the network. Sensor nodes were affected by environmental factors and hence failure probability and exit from the network is exists. Therefore, all algorithms in this network must be tolerance than the loss of nodes so that fault creating in each section not causes interruption in work of the whole network. Node failure is generally assumed that will follow the Poisson distribution.

Network dynamics

A sensor network generally has three main components of sensor nodes, base station nodes and events were felt. Regardless of some of the applications which used mobile sensors, nodes are fixed in most architecture. In some cases is necessary to support of being mobile base station or cluster head. Being mobile nodes create enormous challenges in clustering; because constantly changing member nodes in cluster. On the other hand depending on different applications events were felt can be done intermittently, or continuously. Sense events frequently cause that the network to act as a reactive. Whereas in a continuous mode to feel, it is necessary to send the reports to the base station, continuously, so increases the traffic of send a message to the base station.

Coverage

Each node in sensor networks has the specific and limited vision than the surroundings environment. Thus, a set of sensors cover limited space of environment. In some applications is needed that several nodes in cover a particular area of the environment or a specific path of the environment. Thus, one coverage environment is one of the factors affecting routing algorithms in sensor networks.

Data aggregation

Since the nodes may have the same data, therefore there are data redundancy problem in such networks. Hence, the aggregation of data received from multiple nodes can be decreased the number of messages exchanged in the network. For data aggregation can be used various functions such as Suppression, Min, Max and Average. Using these methods can reduce energy consumption and network traffic. Data aggregation can be done by cluster heads; in this case cluster head selection may be limited to selected specific cluster heads. Sometimes it is necessary that for cluster heads considered backup sensor or spin cluster head role in cluster nodes.

Security

Features such as use of wireless communication, dynamic network topology and dependency network to sink node in sensor networks that are caused for insecurity in these networks. Thus, in many applications including military applications, security of these networks is highly regarded.

Real time issues in wireless sensor networks

In some sensor networks, in addition to accuracy of data received, it is necessary that works to be done in a specified time limit and usually short. These networks called Real Time networks. As examples of these types of networks can be noted networks for environmental monitoring in military environments, network monitoring vital signs of patients and networks such as this.

Topology control

The purpose of topology control is coordination between the nodes decisions about the domain of send data to reduce interference messages and thus increase network capacity and reduce energy consumption. Topology control methods are divided into two homogeneous and heterogeneous categories. In Homogeneous method, all network nodes have the same domain r and topology control problem exchange to determine the minimum domain r issue. In heterogeneous topology control nodes domain can be vary, but selected domain must be less than initial domain.

Heterogeneous topology control methods are divided to three categories position approaches, direction- based and neighborhood- based. In position approaches assumed that we have accurate information about nodes location. In based-direction approaches assumed that nodes do not have its location status, but can estimate its neighboring nodes location, relatively. In neighborhood-based approaches assume that nodes have minimum information like nodes ID about its neighbor nodes.

Classification of routing algorithms

Considering the characteristics described for sensor networks, many algorithms are designed for routing in these networks. These algorithms can be categorized to three views depending on how the source finds a route to the destination, the network operation and the network structure. Depending on how the source finds a route to the destination these algorithms classified to four categories proactive, reactive, hybrid and cooperative and depending on network operation we have multi-path, query-based, negotiation-based, QoS-based and coherent-based categories. Depending on network structure routing algorithms classified into three categories flat, location-based and hierarchical.

Fig.3.1: Classification of routing algorithms in WSNs

Routing algorithm classification based on route from source to destination

As mentioned routing algorithms in sensor networks depending on how the source finds a route to the destination classified to four categories:

In proactive methods all routes computed and updated periodically in the network. This routes kept in exist tables in the nodes. In proactive methods data transfer rate is high because routes are always certain, but this method is not suitable for updating sensor networks tables for reason such as need to high capacity memory in node, overload due to maintenance and update tables and high message exchange between nodes. In reactive protocols, routes are computed on demand. Hence for routing must be search the route from origin to destination. Hybrid protocols use a combination of these two ideas and use for increase scalability in large networks. Another class of routing protocols is called the cooperative routing protocols. In cooperative routing, nodes send data to a central node. Data aggregated and processed, and then send to destination. Hence reducing network traffic and route cost in terms of energy use.

Network operation-based classification(or protocols)

Routing algorithms in sensor networks are classified into five categories depending on network operation:

Multipath routing protocols: In order to enhance the network performance; increase the fault tolerance and improve reliability on WSNs are the aim of multipath routing algorithms.

Select a path from among several existing route for sending data to the destination is one of the issues raised in these algorithms. In [20] sends data through a path whose nodes have the largest residual energy and this path will be used until its energy falls below the energy of the backup path at which the backup path is used. Thus, the data transfer overhead would not be only on primary path nodes. In [63] proposed the use of a set of optimal paths to increase the lifetime of the network. These paths are selected randomly and depend on the energy consumption of each path. In [27] suggest a multipath routing method that useful in unreliable environments. In this idea, send data over multiple paths from source to destination. However, using this method in addition to energy consumption of network traffic also increases.

Query based algorithms: In this type of algorithms, base station spread data query in the network, then nodes that have requested data, respond to query. Sent requests are usually in a natural language, or in high-level query languages. The rumor routing protocol [18] and Directed diffusion [43] are some example of these algorithms.

Negotiation based routing algorithms: these algorithms use of high level data descriptors in order to eliminate redundant data because of broadcasting. Use of theses algorithms causes decrease energy consumption and data redundant. SPIN [38] and [49] are some of negotiation based algorithms.

QoS-based algorithms: the balance between energy consumption and data quality in network is the aim in this kind of algorithms. One of the first routing algorithms in this field is SAR algorithm [70]. SAR makes decision for routing based on three factors: energy consumption, quality of service on each path and the priority level of each packet. This algorithm use of multi path routing in order to enhance the fault tolerance, so achieving quality of service, reduce energy consumption and fault tolerance are the SAR objectives. Another example of QoS-based routing algorithms is SPEED [35] that in this algorithm, each node maintains information about its neighbors, also with estimation the speed of each packet, this algorithm give the ability to each application to calculate the end-to-end delay for the packets. This algorithm also has the ability of prevent the congestion.

Coherent and non-coherent data processing-based routing: one of the essential operations of WSNs is data processing. Wireless sensor routing algorithms use different data processing methods, but generally these methods cooperate with each other in processing data flooded in the network area. Data processing methods can be classified in two categories of coherent and non-coherent algorithms. In non-coherent algorithms nodes will locally aggregate the raw data before being sent to other. In coherent routing algorithms, the data is forwarded to aggregators after minimum processing. Coherent processing is used to perform energy-efficient routing.

Network structure-based classification(or protocols)

Routing in sensor networks are divided to three categories depends on the network structure:

Flat routings: In these algorithms, nodes play the same role for send data to destination in the network. In flat data centric routing algorithms, data send on the path from the source node to the base station. Thus the middle nodes play routing role. So, because of sensor network characteristics and type of communication, flat routing tends to consume more energy and on the other hand scalability in these algorithms is very low. These algorithms are query based techniques and therefore also called data centric algorithms. SPIN [38] and direct diffusion are samples of this kind of routing algorithms that early works on them as a data centric routing were shown to save energy through data negotiation and elimination of redundant data. These two protocols motivated the design of many other protocols which follow a similar concept. Another flat routing algorithms are Rumor [18], MCFA [18], Gradient-Based Routing [67], CADR and IDSQ [23], ACQUIRE [66], COUGAR [82], Energy Aware Routing [69], Protocols with Random Walks Routing [68].

Location-based routing algorithms: these algorithms are aware about nodes location. Thus, data can be sending towards to the destination and broadcast is not necessary. Thus, base station can only request to send data from a particular region. This approach will be reduces network traffic, increase network capacity and eventually reduce power consumption and network delay. GAF [80], SMECN [52], MECN [65], GEAR [90], MFR, DIR and GEDIR [72], SPAN [21] and GOAFR [48] are some samples of location based routing algorithms.

Hierarchical algorithms: scalability management and reduce energy consumption are the main purpose of hierarchical algorithms or cluster-based routing. In a hierarchical architecture, higher energy nodes can be used to process and send the information while low energy nodes can be used to perform the sensing in the proximity of the target. LEACH [36], PEGASIS [54], TEEN [57], APTEEN [58], MECN [65], SOP [73], Sensor Aggregates Routing (SAR) [29], TTDD [84], VGA [8] and HPAR [51] are samples of hierarchical routing algorithms. Table 3.1 shows the classification of flat, location based, hierarchical and QoS-based algorithms.

Cluster-based routing algorithms

Reduce energy consumption, increase the network lifetime and scalability are the main routing challenging in sensor networks. Solve these problem is the main objectives of hierarchical routing algorithms especially cluster-based algorithms. Therefore, clustering methods are the best selection for routing in sensor networks. In these algorithms, network nodes form a cluster and one node elected as a cluster head.

Cluster heads can be one of the existing sensors in cluster or previously selected by the network's designer, they may also be a normal node similar to other nodes or sensor with richer resources. Clusters' members can be fixed or variant. Cluster heads may create second layer for network or send data to special parts like node or base station. Clustering has some preferences for the purpose of supporting scalability as follows:

Creating route can be locally done in cluster by this method, so the capacity of stored routing table will be decreased in special node, too.

Clustering can also economize in the use of band width, so it has limited range of inter cluster communication to cluster heads and prevent transferring redundant messages between sensors.

Topology of network can be fixed by using clustering in a level of sensors so overload due to the maintenance of topology can be reduced.

Sensors only connect with their own cluster heads and aren't affected by occurred changes in between clusters.

Cluster head can schedule activities of cluster, thus sensors can go into sleep and reduce their own energy consumption and can be used in the order of round robin.

Cluster head can perform collecting aggregated data and reduce the number of repetitive and unimportant messages.

In continuation of this chapter, we will deal with classification of clustering properties and clustering-based routing algorithms from aspect of convergence rate of algorithms. Convergence rate of algorithms will be computed based on the number of messages which are exchanged between nodes for the purpose of clustering.

Classification of clustering properties

Clustering methods for sensor networks can be classified based on clustering objectives and specifications [1]. Algorithm classification has been briefly presented based on goals of clustering and clustering specifications in figure 4.1.

Main objectives of clustering

Clustering may be performed for access to different goals; Tolerability of forms, increase of communication and decrease of delay, minimum number of clusters and maximum longevity of network can be mentioned. We will deal with reviewing these goals in continuation.

Fault-Tolerance: In many applications, sensor networks work in rough environments, therefore nodes are exposed to breakdown and physical risks. In such circumstances, power of cluster heads for Fault-Tolerance normally will be of high significance and prevent losing important gathered data by sensors. On the other hand, when cluster heads apply radio waves with high wave length, being the cluster heads near to each other wills breakdown the exchanged messages. One of the known ways for repairing breakdown cluster heads is re clustering network. Determination of one support for cluster heads is one of the most significant ways of repairing breakdown of cluster heads.

Increased connectivity and reduced delay: Inter cluster communications is one of the fundamental requirements in many applications. This issue will be more important when cluster heads are selected from network sensors set.

The minimal cluster count: Number of clusters will be mentioned specially; in circumstances that cluster heads have sensors with rich resources. Network designers aren't frequently inclined to use these nodes due to high expense of nodes and their high vulnerability and use a few of them in network. This limitation can also be due to complexity of putting these nodes in network. Furthermore, size of these nodes may be larger than other sensors. This feature causes that they become identifiable more easily wheras observing sensors in many applications of sensor networks are so undesirable particularly, in cases like security and military infrastructure and borders protection.

The network maximum lifetime: As the sensor nodes consume energy and energy of nodes is limited, longevity of network is one of the highly important and significant cases in these networks especially, in applications of sensor networks which will be in unfavorable environment. When the cluster heads have richer resources than other nodes of network, minimizing the energy consumption in communication between clusters become more important Adaptive clustering in many cases is such a suitable choice for access to high longevity of network.

Clustering specifications

In this section, a set of clustering specifications including feature of cluster, capability of cluster heads and clustering process will be considered. Based on these specifications, clustering methods will be classified and distinguished. We will deal with considering these specifications [].

Cluster properties:

In most clustering methods, attempt to the created clusters have special features. These features can be related to the internal structures of clusters or manner of relation of cluster with rest of clusters. Some of these features are as follows:

Clusters count: In many clustering methods, cluster heads will be previously specified. Therefore, the number of clusters will be previously determined but in some methods, cluster heads will be randomly selected. Selection of cluster heads randomly and among the existing sensors in network causes that the number of clusters will be variable in network [].

Stability: When the number of clusters is variable and membership of nodes to clusters will be changed during time, we will have adaptive clustering. Otherwise, it will be called stable clustering. In this clustering, sensors won't be interchanged between clusters and are always belonged to one cluster and number of clusters will be also fixed in longevity of network [].

Intra-cluster topology: In some of clustering algorithms, relation between sensors and cluster heads are direct while sometimes it's necessary that the relation of sensors with cluster head to be multi hops specially, when the limit of relation of sensors or number of clusters are so few[].

Inter-cluster connectivity: When the cluster heads don't have capacity of relation with high haul, relation of these cluster heads with base station should be supplied in any way. In such circumstances, routing will be possible by multi hop routes between cluster head and sink. In many methods, it's assumed that cluster heads can directly have access to the sink.

Cluster heads Capabilities

Network model and capability of nodes affect clustering methods. Features of cluster heads which are as follows are among distinction factors of clustering methods.

Mobility: When the cluster heads are mobile, membership of nodes to clusters will be dynamically changed. Therefore, it's necessary the connectivity of nodes to clusters will be managed. In other words, fixed cluster heads will result in having fixed clusters and facilitating network management. In some applications, cluster heads can move during limited distances and change their position for better efficiency of network [].

Type of node: As previously said in some methods, a subset of placed sensors a network will be selected as cluster head and it's in condition that in many methods, cluster heads are special nodes and equipped with significant communicative and computational resources [].

Role of cluster head: A cluster head can only have a relay role for created traffic inside clusters or can also have gathering and combinative role of gathered data by sensors. Sometimes cluster head will act as the sink and have a behavior based on identified phenomena and goals of network [].

Clustering process

Coordination methods during clustering process and characteristics of clustering algorithms may be different for various algorithms. The following features are cases which cause variation of algorithms.

Methodology: In some methods which called centralized methods, central node or base-station will perform clustering off-line and control the membership of nodes to clusters. In distributed method, nodes perform clustering with messages which will send to each other. In hybrid manner, coordinatifon between cluster heads is in distributed form but each of them is responsible for determining member of their own cluster especially, if cluster heads have rich resources [].

Objectives of nodes grouping: Clustering will be carried out for access to goals like fault tolerance, increase of communication and decrease of delay, decrease the number of clusters and maximum longevity of network [].

Cluster-head selection: Cluster head may be previously selected by network designer or randomly from normal nodes of network [].

Algorithm complexity: The time complexity or convergence rate of algorithms can be fixed or dependent on number of cluster heads or number of nodes of network. In algorithms which convergence rate in them are proportional to number of nodes in network, each node needs sending and receiving message from all nodes of network for making decision to belong their own cluster head or membership in one of the clusters but in algorithms with fixed convergence rate, each node by sending and receiving limited number of messages will decide to be cluster head or connect to one of the cluster heads. In next section, clustering algorithms will be considered from aspect of convergence rate [].

Clustering algorithms for sensor networks

Clustering algorithms can be classified based on different criteria. One of these criteria is convergence rate of algorithm. In this manner, clustering algorithms will be divided to algorithms with variable convergence rate and fixed convergence rate. In algorithms with fixed convergence rate , the clusters will be formed after each node exchanges limited number of messages in network while in algorithms with variable convergence rate, it's necessary for clustering nodes to exchanges many number of messages in network by each node. Number of these messages can be proportional to number of network nodes or number of cluster heads. We will deal with reviewing presented algorithms in each section. Algorithms with variable convergence rate are suitable for implementing in networks which number of existing nodes in network is little. In general, algorithms with variable convergence rate have more control on features of clusters than ones with fixed convergence rate.

One more classification is clustering algorithms for homogeneous or heterogeneous networks. This classification is based on the characteristics and functionality of the sensors in the cluster []. In heterogeneous sensor networks, there are generally two types of sensors, sensors with higher processing capabilities and complex hardware, and common sensors, with lower capabilities. In homogeneous networks, all nodes have the same characteristics, hardware and processing capabilities. In this case every sensor can become a cluster head. Moreover, the CH role can be periodically rotated among the nodes in order achieve better load balancing and more uniform energy consumption.

Other classification centralized or distributed clustering algorithms are based on the used to form the cluster. As mentioned before in methodology of clustering process in centralized method, one or more coordinator nodes or the BS is responsible to partition the whole network off-line and control the cluster membership[].this classification naturally not suitable for large-scale WSNs applications.

Another classification is static or dynamic clustering. A cluster schema is considered as dynamic when it includes regular cluster head reelection or cluster reorganization procedures, simply aiming at the suitable rotation of the cluster head role among the nodes to gain in energy efficiency, or effectively reacts to network topology changes and adapts properly the cluster topology. Dynamic cluster architectures make a better use of the sensors in a WSN and naturally lead to improved energy consumption management and network lifetime [].

Depending on cluster formation and parameters used for cluster head selection, clustering algorithms divide to two categories probabilistic or non-probabilistic. In probabilistic category, an initial probability assigned to each node and used to determine the initial cluster heads. In non-probabilistic category, for cluster head selection and cluster formation more specific criteria are considered, which the cluster formation here is based on the communication of nodes with their and generally requires more exchange of messages.

In this section we summarize some clustering algorithms

LEACH: This is the most common and famous algorithms of wireless sensor network [36], which it still use as the basis for other improved clustering protocols for WSNs. LEACH has some main objective reduce energy consumption among all network nodes beside of improve the network lifetime, reduce the number of communication messages and remove redundancy by performing data aggregation. LEACH is a hierarchical, distributed and one-hop protocol that is ignorant about node location. In this algorithm cluster forms based on received signal strength in a distributed manner and cluster heads are selected randomly, and in order to aid load-balancing, this role is dynamically rotated. Cluster nodes aggregate data and send them to cluster heads and each cluster head forward aggregated data directly to base station. Therefore, LEACH assumes that all nodes in the network are able to reach the base station directly. This algorithm has a centralized data collection that performed periodically. Therefore, this protocol is most appropriate for constant monitoring by the sensor network. LEACH uses a TDMA/CDMA to reduce inter-cluster and intra-cluster collisions. In addition, LEACH has some other characteristics that can refer to the following:

All nodes are homogeneous and have same capabilities and limitations.

Initial energy of all nodes is equal.

The communication channels are bilateral.

Nodes can change the power of transmitter and in this way they control its transmitter range

The operation of LEACH consists of two phases; setup phase and steady state phase that repeated as a repetitive method during network lifetime.

Setup phase: In this phase, the network divide to some Cluster partition and for every Cluster a cluster head selected. At the beginning of phase, each node selects one random number between 0 and 1. Each node that has a lower produced number than threshold [T (n)], then that node will be cluster head.

Where P is the suitable number of cluster head in each round. In this algorithm P is equal to 5%. In the formula of T (n), r is the current round, and G is the collection of nodes that have not been selected as cluster head in the last 1/p round. Afterwards, nodes that select as a cluster heads, advertise their cluster head status to all network, and other nodes after receiving messages from all cluster heads, decide to connecting to the nearest one based on the signal strength and send a message to cluster head about its membership. After the formation of Cluster, each cluster head for inter-cluster communication creates a TDMA schedule and assign a time slot to each node, and broadcast this schedule to all cluster members.

Steady state phase: in this phase, cluster heads aggregate data that gathered by cluster members and then forward them to base station. In order to minimize overhead, the steady state phase duration is longer than the duration of the setup phase. At the end of this phase, in order to create new clusters, the network is switched to setup phase again.

LEACE algorithm has many advantages, the most important of them is introducing new routing method in sensor network which is adoptable with more features and the main needs of sensor network. But also, this algorithm had some disadvantage that the most important of them have been pointed out as follows:

The assumption of same type, limitation and capabilities for nodes is causes for decrease their efficiency in sensor networks in different situation.

The assumption of same initial energy for all networks node in the beginning of work.

There is no mechanism to ensure that the elected cluster-heads will be uniformly distributed over the network.

In setup phase because of count of messages that exchange in whole network, we have high overload in the network.

In this algorithm all nodes must be able to reach the base station directly, so it is not applicable to networks deployed in large areas

Nodes in LEACH are assumed fixed, so it is not applicable for mobile network.

LEACH assumes that all nodes have data to send and so assign a time slot for all node even though some nodes might not have data to transmit

LEACH-C: This is a centralized version of LEACH [37]. The goal of this algorithm is removing inappropriate distribution of Cluster and reduces the setup-phase overload. In this algorithm base station is responsible for clustering and use of a centralized algorithm instead of distributed algorithm.

PEGASIS: this algorithm is the developed version of LEACH[54] .the aim of this algorithm is reducing nodes energy consumption, increasing network lifetime, reducing bandwidth with allow only local coordination between nodes that are close together and removing overhead due to setup phase.

Instead of forming clusters, it is based on forming chains of sensor nodes. Each node connects only with its neighbor and one node is responsible for routing the aggregated data to the sink. Since the overhead caused by dynamic cluster formation, is eliminated, multi hop transmission and data aggregation is employed. However excessive delay is introduced for distant nodes, especially for large networks and single leader can be a bottleneck.

Node C0 and C4 forwards the obtained data to C1 and C3, respectively. Node C1 and C3 aggregates the data and forward it to C2. C2 is responsible for sending the gathered data to the base station. This algorithm for large networks has very high and unreachable latency, so its reason for disappear scalability.

MuMHR: this is a multi hop, multi path and distributed algorithm that reduced cost due to setup phase with using timer [33]. In this algorithm for crating flexibility against cluster heads failure, select a backup cluster head for each cluster head. Also, in this algorithm, base station has information about address of network nodes.

CMEER: The goal of the algorithm is multi hop routing and reducing energy consumption [44]. In this method assumed nodes used with uniform distribution in network. The network nodes divided with regard to the amount of closeness to the sink. Then clusters are formed in accordance with LEACH method. In data transmission phase, each cluster head for multi hop to transfer of information try to find a cluster head in a higher level, if received an answer send aggregated data to it otherwise send data to the sink, directly.

RCCT: Improving cluster forms, decrease setup-phase overload and distribution cluster heads energy between cluster-members are the main objectives of this algorithm [31]. For achieving these objectives, this algorithm changed in setup and steady state phase. In setup-phase, cluster heads select based on the threshold that presented in. Then cluster heads send a message in limited distance that denote with d and announced that they are select as a cluster head. In steady-state for energy consumption balance, increase fault-tolerance and use of energy level, each node beside of sending gathered data announced to cluster head about its remaining amount of energy

LALEACH: As mentioned in the previous section LEACH algorithm do the clustering formation and cluster head selection and cluster heads responsible to gatherings the information from cluster nodes and forward them to base station. In LEACH protocol the cluster head never is changed, and so consumes more energy. And this it causes the decreasing of the network lifetime. In LALEACH algorithm, exchange the role of cluster head in cluster in each period dynamically, by the learning automata. In this algorithm considered a learning automaton for each cluster. The number of the actions of automata equals with the number of clusters nodes. The way for of cluster head selection is that the learning automata choose an action that its number is more than the other between its actions. LALEACH use TDMA mechanism.

The simulation result of LALEACH algorithm that compared with LEACH, HEED and Extended HEED protocols, show that the network lifetime in LALEACH algorithm is more than the others[].

MuELSC (Multi-hop Hierarchical Routing with Energy and Location aware Static Clustering): Reducing energy consumption and setup-phase overload, increase network lifetime and multi-hop routing from cluster heads to base station are the main objectives of MuELSC algorithm. This algorithm is a hierarchical algorithm with static clustering and multi-hop routing. MuELSC has information about location and energy of nodes and effort to create cluster with suitable shape and size and appropriate situation from base station. In order to decrease energy consumption, Clusters and cluster-members are fixed until end of network lifetime. To reach nodes energy balancing, the role of cluster head change periodically between cluster-members based on remaining level of energy. In the first of algorithm, nodes compute their location by localization algorithms and send their location information to base station. Then base station does act of clustering and announced nodes about their cluster and cluster heads. Afterward, cluster-members and then cluster head with TDMA mechanism for time scheduling send gathered and aggregated data to base station. So, this algorithm has four nodes location computation, initial clustering, nodes time scheduling and next round cluster head selection phases.

Conclusion

In this chapter sensor networks were studied and their various applications and architecture was expressed. Nowadays, wireless sensor networks in many applications are used and every day new applications of such networks are proposed. Considering the many challenges and applications of these networks, many researches on them is ongoing. One of research areas in WSNs is routing algorithms. Many factors are effective on design of routing algorithms in sensor networks, that we discussed in the in other section of this chapter. Then the algorithms classified based on route from source to destination, network operation and network structure and offer samples of each group. Hierarchical routing algorithms are the most important class of routing algorithms that energy distribution between network nodes, reducing energy consumption and increase scalability are their main objectives. Cluster-based routing algorithms evaluated in the next part of this they analyzed and categorized based on clustering methodology, the method of cluster head selection and algorithm complexity. In the next part we described some clustering based routing algorithms based on cluster features, cluster capability and the process of clustering, and then we presented sample of algorithms.

Table 2.1 Comparison of Clustering Algorithms

Clustering Approaches

Time

Complexity

Node

Mobility

Cluster

Overlap

In-Cluster

Topology

Cluster

Count

Clustering

Process

CHs

Selection

CHs

Rotation

Multi

Level

LBC [5]

N/A

No

No

1-hop

Fixed

Centralized

Preset

No

No

MSNDP [6]

N/A

No

No

1-hop

Variable

Centralized

Preset

No

No

LCA [7]

Variable

Possible

No

1-hop

Variable

Distributed

ID-based

No

No

AC [9]

Variable

Yes

No

1-hop

Variable

Distributed

ID-based

No

No

DCATT [10]

N/A

No

No

1-hop

Fixed

Manual

Preset

No

No

LEACH [11]

Constant

Limited

No

1-hop

Variable

Distributed

Prob/random

Yes

No

EEHC [13]

Variable

No

No

k-hop

Variable

Distributed

Prob/random

Yes

Yes

HEED [14]

Constant

Limited

No

1-hop

Variable

Distributed

Prob/energy

Yes

No

LEACHC [12]

N/A

Limited

No

1-hop

Variable

Centralized

Prob/random

Yes

No

TLEACH [15]

Constant

Limited

No

1-hop

Variable

Distributed

Prob/random

Yes

Yes

MOCA [16]

Constant

Limited

Yes

k-hop

Variable

Distributed

Prob/random

Yes

No

TCCA [17]

Variable

No

No

k-hop

Variable

Distributed

Prob/energy

Yes

No

EECS [18]

Constant

No

No

1-hop

Constant

Distributed

Prob/energy

Yes

No

EEMC [19]

Variable

No

No

k-hop

Variable

Distributed

Prob/energy

Yes

Yes

RCC [21]

Variable

Yes

No

k-hop

Variable

Hybrid

Random

No

No

CLUBS [22]

Variable

Possible

Yes

2-hop

Variable

Distributed

Random

No

No

FLOC [23]

Constant

Possible

No

2-hop

Variable

Distributed

Random

No

No

RECA [24]

Constant

No

No

1-hop

Variable

Distributed

Random

Yes

No

HCC [27]

Variable

Possible

Yes

k-hop

Variable

Distributed

Connectivity

No

Yes

HC [28]

Variable

Possible

No

1-hop

Variable

Distributed

Connectivity

No

No

MMDC [29]

Variable

Yes

No

k-hop

Variable

Distributed

Connectivity

No

No

EEDC [30]

Variable

No

No

1-hop

Variable

Centralized

Connectivity

No

No

CAWT [31]

Constant

No

No

2-hop

Variable

Distributed

Connectivity

No

No

EACLE [32]

Variable

No

No

2-hop

Variable

Distributed

Proximity

Yes

No

ACE [33]

Constant

Possible

Yes

k-hop

Variable

Distributed

Connectivity

No

No

WCA [38]

Variable

Yes

No

1-hop

Variable

Distributed

Weight-based

No

No

DWEHC [39]

Constant

No

No

k-hop

Variable

Distributed

Weight-based

No

No

TASC [40]

Variable

No

No

2-hop

Variable

Distributed

Weight-based

No

No

GS3 [25]

Variable

Possible

Yes

k-hop

Constant

Distributed

Preset

No

No

GROUP [26]

Variable

No

No

k-hop

Controlled

Hybrid

Proximity

No

No

Writing Services

Essay Writing
Service

Find out how the very best essay writing service can help you accomplish more and achieve higher marks today.

Assignment Writing Service

From complicated assignments to tricky tasks, our experts can tackle virtually any question thrown at them.

Dissertation Writing Service

A dissertation (also known as a thesis or research project) is probably the most important piece of work for any student! From full dissertations to individual chapters, we’re on hand to support you.

Coursework Writing Service

Our expert qualified writers can help you get your coursework right first time, every time.

Dissertation Proposal Service

The first step to completing a dissertation is to create a proposal that talks about what you wish to do. Our experts can design suitable methodologies - perfect to help you get started with a dissertation.

Report Writing
Service

Reports for any audience. Perfectly structured, professionally written, and tailored to suit your exact requirements.

Essay Skeleton Answer Service

If you’re just looking for some help to get started on an essay, our outline service provides you with a perfect essay plan.

Marking & Proofreading Service

Not sure if your work is hitting the mark? Struggling to get feedback from your lecturer? Our premium marking service was created just for you - get the feedback you deserve now.

Exam Revision
Service

Exams can be one of the most stressful experiences you’ll ever have! Revision is key, and we’re here to help. With custom created revision notes and exam answers, you’ll never feel underprepared again.