Improved Scheduling Algorithm Using Dynamic Tree Construction for Wireless Sensor Networks
©2016
Academic Paper
85 Pages
Summary
The Wireless Sensor Network (WSN) composed of several nodes is used for different types of monitoring applications. The objective of deploying WSN is to observe a particular site for monitoring physical parameters like temperature, light, pressure, humidity or the occurrence of a phenomenon. The Sleep/Wake up scheduling for Wireless Sensor Networks has become an essential part of its working.
In this book, the details of Low Energy Adaptive Clustering Hierarchy (LEACH) which introduces the concept of clustering in sensor networks, Energy-Efficient Clustering routing algorithm based on Distance and Residual Energy for Wireless Sensor Networks (DECSA) which describes scheduling based on distance and energy, and the Energy efficient clustering algorithm for data aggregation (EECA) are discussed. The LECSA (Load and Energy Consumption based Scheduling Algorithm) are also discussed.
In this book, the details of Low Energy Adaptive Clustering Hierarchy (LEACH) which introduces the concept of clustering in sensor networks, Energy-Efficient Clustering routing algorithm based on Distance and Residual Energy for Wireless Sensor Networks (DECSA) which describes scheduling based on distance and energy, and the Energy efficient clustering algorithm for data aggregation (EECA) are discussed. The LECSA (Load and Energy Consumption based Scheduling Algorithm) are also discussed.
Excerpt
Table Of Contents
4
PREFACE
The Wireless Sensor Network (WSN) composed of several nodes are used for different types of
monitoring applications. The objective of deploying WSN is to observe a particular site for
monitoring physical parameters like temperature, light, pressure, humidity or the occurrence of a
phenomenon. The Sleep/Wake up scheduling for Wireless Sensor Networks has become an
essential part of its working. In this work, the details of Low Energy Adaptive Clustering
Hierarchy (LEACH) which introduced the concept of clustering in sensor networks, Energy-
Efficient Clustering routing algorithm based on Distance and Residual Energy for Wireless
Sensor Networks (DECSA) which describes about scheduling based on distance and energy and
the Energy efficient clustering algorithm for data aggregation (EECA) were discussed. The
LECSA (Load and Energy Consumption based Scheduling Algorithm) has also been discussed.
Based on that, in this book, the cluster head finds the nearest active node in the neighbor cluster
and then it forwards its data to it. From all the cluster heads the data reaches the sink not directly,
but by using a self-organized efficient routing algorithm.
5
TABLE OF CONTENTS
CHAPTER 1
1 INTRODUCTION ... 11
1.1 Outline of the Project ... 19
1.1.1 SLEEP/WAKE-UP ... 20
1.1.2 DECSA ... 20
1.1.3 LEACH ... 20
1.1.4 EECA ... 21
1.1.5 LECSA ... 21
1.1.6 GSTEB ... 21
1.2 Literature survey ... 22
1.3 Problem Definition ... 25
1.4 Objective ... 26
1.5 Chapter Organization ... 26
CHAPTER 2
2 DESI
GN AND ANALYSIS ... 28
2.1 Introduction ... 28
2.2 Analysis ... 28
2.2.1 Project Specification ... 28
2.2.1.1Existing system ... 29
2.2.1.2 Disadvantages of Existing system ... 29
2.2.1.3 Proposed system ... 29
2.2.1.4 Advantage of Proposed System ... 30
2.2.2 Hardware and Software Requirements ... 30
2.2.2.1 Hardware Requirements ... 30
2.2.2.2 Software Requirements ... 30
6
2.2.2.3 Introduction to NS2 ... 31
2.3 Design ... 33
2.3.1 System Flow Diagram ... 34
2.3.2 Data Flow Diagram ... 35
2.3.3 UML Diagram ... 38
2.3.3.1 Class Diagram ... 38
2.3.3.2 Use Case Diagram ... 39
2.3.3.3 Sequence Diagram ... 40
2.3.3.4 Collaboration Diagram ... 41
2.3.3.5 Activity Diagram ... 42
CHAPTER 3
3 DESIGN AND IMPLEMENTATION ... 43
3.1 System Architecture ... 43
3.1.1 Components of GSTEB ... 43
3.1.1.1 Initial Phase ... 43
3.1.1.2 Tree Construction Phase ... 43
3.1.1.3 Self-Organized Data Collecting &Transmitting ... 44
3.1.1.4 Information Exchange ... 44
3.1.1.5 Sensor Node ... 44
3.1.1.6 Cluster ... 46
3.1.1.7 Cluster Head ... 46
3.1.1.8 Base Station ... 46
3.1.1.9 End User ... 46
3.1.2 Architecture of GSTEB ... 47
3.2 Algorithms ... 47
3.2.1 Clustering ... 48
3.2.2 K-Hop ... 48
3.2.3 Master &Slave ... 49
3.2.4 TDMA Scheduling ... 49
7
3.2.5 LECSA ... 50
3.2.6 Re-Election ... 51
3.2.7 Multi-Input &Output ... 51
3.3 Description Of Modules ... 52
3.3.1 Cluster Formation of WSN ... 52
3.3.2 LEACH ... 52
3.3.3 GSTEB ... 52
3.3.4 Initial Phase ... 53
3.3.5 Tree Construction ... 53
3.3.6 Information Exchanging ... 53
3.4 Implementation ... 54
3.5 Testing ... 55
CHAPTER 4
4 EXPERIMENTAL STUDY, RESULTS AND DISCUSSSION ... 57
4.1 Description of the Experiments conducted ... 57
4.2 Output with Description ... 57
4.3 Experimental Results ... 58
4.3.1 Throughput ... 59
4.3.2 Packet Loss ... 60
4.3.3 Delay Ratio ... 61
4.3.4 Channel Measurement ... 62
4.3.5 Protocol Frequency ... 63
4.3.6 Source Frequency ... 64
4.3.7 Destination Frequency ... 65
8
CHAPTER 5
5 CONCLUSION &
FUTURE WORK ... 66
5.1 Summary ... 66
5.2 Conclusion ... 67
REFERENCES ... 68
A APPENDICES ... 70
A.1 Screen Shots ... 70
9
TABLE OF FIGURES
FIG No
FIGURE NAME
PAGE No
1.1
Wireless Sensor Networks
12
1.2 Sensor
Node
13
1.3 DECSA
Architecture
22
1.4 LEACH
Architecture
23
1.5 EECA
Architecture
23
2.1
Simplified User's View of N
32
2.2 System
Flow
Diagram
35
2.3
Level 0: Generation of Nodes
36
2.4
Level 1: Cluster Formation
36
2.5
Level 2: Initial Cluster Head Selection
37
2.6
Level 3: Scheduling and Data Transmission
37
2.7 Class
Diagram
38
2.8
Use Case Diagram
39
2.9
Sequence Diagram
40
2.10
Collaboration Diagram
41
2.11 Activity
Diagram
42
3.1 Sensor Node
45
3.2
GSTEB Architecture
47
4.1
Formation of cluster and Data Transfer
58
4.2
Throughput Comparison of Routing Protocols
59
4.3
Packet Loss Comparison of Routing Protocols
60
4.4
Delay Ratio Comparison of Routing Protocols
61
4.5
Channel Measurement Comparison of Routing Protocols
62
4.6
Protocol Frequency Comparison of Routing Protocols
63
4.7
Source Frequency Comparison of Routing Protocols
64
4.8
Destination Frequency Comparison of Routing Protocols
65
10
LIST OF SYMBOLS AND ABBREVIATIONS
ACRONYM
ABBREVIATIONS
ADC
Analog to Digital Converter
BS
Base
Station
BCH
Base Station Cluster Head
CBM
Condition Based Maintenance
CH
Cluster
Head
DAC
Digital to Analog Converter
DECSA
Distance Energy Cluster Structure Algorithm
DFD
Data Flow Diagram
EECA
Energy Efficient clustering Algorithm
ICH
Initial Cluster Head
ISM
Industrial, Scientific and Medical
LEACH
Low Energy Adaptive Clustering Hierarchy
LECSA
Load and Energy Consumption Based Scheduling Algorithm
NS2
Network
Simulation
GSTEB
Generalized Self-Organized Tree Based Energy-Balance Routing
LIST OF TABLES
TABLE NO
TABLE NAME
PAGE NO
4.1 Configuration Parameters of the Simulation Results ... 57
4.2 Node IDS of Each Cluster ... 58
11
CHAPTER 1
INTRODUCTION
The sensor networks are infrastructures to collect data from the environment and the data can be
used to study many problems like climate change, animal migrations, and behavior changes of
buildings. The sensor nodes are deployed over a geographical area to monitor physical
phenomena. The wireless sensor networks (WSN) is defined as a network of devices denoted as
nodes that can sense the environment and communicate the information gathered from the
monitored field through wireless data networks. The wireless sensor networks consist of
hundreds of thousands of tiny, inexpensive and battery-powered wireless sensing devices which
organize themselves into multi-hop radio networks.
The wireless sensor networks are a self-organizing ad hoc network with potential
applications in autonomous monitoring, surveillance, military, healthcare, and security. The
sensor nodes consist of three major subsystems. They are computed, communication and
sensing. The computation subsystem has an embedded processor, program memory and data
memory. The communication subsystem has a low power radio operating at ISM band
frequency. The sensing subsystem is used to convert the external world phenomena into an
equivalent electrical quantity which in turn is digitized from analog to digital converters.
The wireless sensor networks are characterized by sensing and communication coverage.
The communication coverage refers to how well the sensor nodes are in communication range of
each other. The sensing coverage refers to how well the terrain under monitoring is sensed by all
the sensor nodes. The wireless sensor network is to determine the node density which is one of
the primary challenges faced by the design of large WSN. The requirements of wireless sensor
networks are fault tolerance, increased lifetime, scalability, power management, security and
budget.
The wireless sensor networks are composed of tiny individual nodes that are programmed
in embedded systems. They are capable of interacting with their environment through variou
1
s
sensors and processing information locally and communicating this information wirelessly with
their neighbors.
Approved by Sathyabama University, Chennai 2015.
12
Fig: 1.1: Wireless Sensor Networks
Sensor Node
A sensor node, also known as a mote is a node in a wireless sensor network that is capable of
performing some processing, gathering sensory information and communicating with other
connected nodes in the network. A mote is a node, but a node cannot always be a mote.
13
Fig: 1.2: Sensor Node
Components
The main components of a sensor node are a micro-controller, transmitter external memory,
power source and one or more sensors.
Controller
The controller performs tasks, processes data and controls the functionality of other components
in the sensor node. While the most common controller is a micro-controller, other alternatives
that can be used as a controller are: a general purpose desktop microprocessor, digital signal
processors, FPGAs and ASICs. A micro-controller is often used in many embedded systems such
as sensor nodes because of its low cost, flexibility to connect to other devices, ease of
programming, and low power consumption. A general purpose microprocessor generally has
higher power consumption than a micro-controller; therefore it is often not considered a suitable
choice for a sensor node. Digital Signal Processors may be chosen for broadband wireless
communication applications, but in Wireless Sensor Networks the wireless communication is
often modest: i.e., simpler, easier to process modulation and the signal processing tasks of actual
sensing of data is less complicated. Therefore the advantages of DSPs are not usually of much
importance to wireless sensor nodes. FPGAs can be reprogrammed and reconfigured according
to requirements, but this takes more time and energy than desired.
14
Transceiver
Sensor nodes often make use of ISM band which gives free radio, spectrum allocation and global
availability. The possible choices of wireless transmission media are Radio frequency (RF),
Optical communication (Laser) and Infrared. Lasers require less energy, but need line-of-sight
for communication and are sensitive to atmospheric conditions. Infrared, like lasers, needs no
antenna, but it is limited in its broadcasting capacity. Radio frequency based communication is
the most relevant that fits most of the WSN applications. WSNs tend to use license-free
communication frequencies: 173, 433, 868, and 915 MHz; and 2.4 GHz. The functionality of
both transmitter and receiver are combined into a single device known as transceivers.
Transceivers often lack unique identifiers. The operational states of wireless sensor networks are
transmitting, receive, idle, and sleep. Current generation transceivers have built-in state machines
that perform some operations automatically.
Most transceivers operating in idle mode have a power consumption almost equal to the
power consumed in receiving mode. Thus, it is better to completely shut down the transceiver
rather than leave it in the idle mode when it is not transmitted or receiving. A significant amount
of power is consumed when switching from sleep mode to transmit mode in order to transmit a
packet.
External memory
From an energy perspective, the most relevant kinds of memory are the on-chip memory of a
micro-controller and Flash memory--off-chip RAM is rarely, if ever, used. Flash memories are
used due to their cost and storage capacity. Memory requirements are very much application
dependent. Two categories of memory based on the purpose of storage are: user memory used
for storing application related or personal data, and program memory used for programming the
device. Program memory also contains identification data of the device if present.
Power source
The sensor node consumes power for sensing, communicating and data processing. More energy
is required for data communication than any other process. The energy cost of transmitting 1 kB
a distance of 100 meters (330 ft) is approximately the same as that used for the execution of 3
million instructions by a 100 million instructions per second/W processor. Power is stored either
15
in batteries or capacitors. Batteries, both rechargeable and non-rechargeable, are the main source
of power supply for sensor nodes. They are also classified according to electrochemical material
used for the electrodes such as NiCd (nickel-cadmium), NiZn (nickel-zinc), NiMH (nickel-metal
hydride), and lithium-ion. Current sensors are able to renew their energy from solar sources,
temperature differences, or vibration.
Sensors
Sensors are hardware devices that produce a measurable response to a change in a physical
condition like temperature or pressure. Sensors measure physical data of the parameter to be
monitored. The continual analog signal produced by the sensors is digitized by an analog-to-
digital converter and sent to controllers for further processing.
A sensor node should be small in size, consume extremely low energy, operate in high
Volumetric densities, be autonomous and operate unattended, and be adaptive to the
environment. As wireless sensor nodes are typically very small electronic devices, they can only
be equipped with a limited power source of less than 0.5-2 ampere-hour and 1.2-3.7 volts.
Sensors are classified into three categories: passive, omni-directional sensors; passive,
narrow-beam sensors; and active sensors. Passive sensors since the data without actually
manipulating the environment by actively probing. They are self-powered; that is, energy is
needed only to amplify their analog signal. Active sensors actively probe the environment, for
example, a sonar or radar sensor, and they require continuous energy from a power source.
Narrow-beam sensors have a well-defined notion of direction of measurement, similar to a
camera. Omni-directional sensors have no notion of direction involved in their measurements.
The overall theoretical work on WSNs works with passive, omni-directional sensors.
Each sensor node has a certain area of coverage for which it can reliably and accurately report
the particular quantity that it is observing. Several sources of power consumption in sensors are:
signal sampling and conversion of physical signals to electric ones, signal conditioning, and
analog-to-digital conversion. Spatial density of sensor nodes in the field may be as high as 20
nodes per cubic meter.
16
Applications of Wireless Sensor Networks
Area Monitoring
Area monitoring is a common application of WSNs. In area monitoring, the WSN is deployed
over a region where some phenomenon is to be monitored. A military example is the use of
sensors to detect enemy intrusion; a civilian example is the Geo-fencing of gas or oil pipelines.
When the sensors detect the event being monitored (heat, pressure), the event is reported to one
of the base stations, which then takes appropriate action (e.g., send a message on the internet or
to a satellite). Similarly, wireless sensor networks can use a range of sensors to detect the
presence of vehicles ranging from motorcycles to train cars.
Air Pollution Monitoring
Wireless sensor networks have been deployed in several cities (Stockholm, London or Brisbane)
to monitor the concentration of dangerous gases for citizens. These can take advantage of the ad-
hoc wireless links rather than wired installations, which also make them more mobile for testing
readings in different areas.
Forest Fires Detection
A network of Sensor Nodes can be installed in a forest to detect when a fire has started. The
nodes can be equipped with sensors to measure temperature, humidity and gases which are
produced by fires in the trees or vegetation. The earlier detection is crucial for a successful action
of the firefighters; thanks to Wireless Sensor Networks, the fire brigade will be able to know
when a fire is started and how it is spreading.
Greenhouse Monitoring
Wireless sensor networks are also used to control the temperature and humidity levels inside
commercial greenhouses. When the temperature and humidity drops below specific levels, the
greenhouse manager must be notified via e-mail or cell phone text message, or host systems can
trigger misting systems, open vents, turn on fans, or control a wide variety of system responses.
17
Landslide Detection
A landslide detection system makes use of a wireless sensor network to detect the slightest
movements of soil and changes in various parameters that may occur before or during a
landslide. And through the data gathered it may be possible to know the occurrence of landslides
long before it actually happens.
Machine Health Monitoring
Wireless sensor networks have been developed for machinery condition-based maintenance
(CBM) as they offer significant cost savings and enable new functionalities. In wired systems,
the installation of enough sensors is often limited by the cost of wiring. Previously inaccessible
locations, rotating machinery, hazardous or restricted areas, and mobile assets can now be
reached with wireless sensors.
Water/wastewater Monitoring
There are many opportunities for using wireless sensor networks within the water/wastewater
industries. Facilities not wired for power or data transmission can be monitored using industrial
wireless I/O pollution control board.
Agriculture
Wireless sensor network within the agricultural industry is increasingly common; using a
wireless network frees the farmer from the maintenance of wiring in a difficult environment.
Gravity feed water systems can be monitored using pressure transmitters to monitor water tank
levels, pumps can be controlled using wireless I/O devices and water use can be measured and
wirelessly transmitted back to a central control center for billing. Irrigation automation enables
more efficient water use and reduces waste.
Structural Monitoring
Wireless sensors can be used to monitor the movement within buildings and infrastructure such
as bridges, flyovers, embankments, tunnels, etc... enabling Engineering practices to monitor
assets remotely without the need for costly site visits, as well as having the advantage of daily
data, whereas traditionally this data was collected weekly or monthly, using physical site visits,
18
involving either road or rail closure in some cases. It is also far more accurate than any visual
inspection that would be carried out.
Natural Disaster Prevention
Wireless sensor networks can effectively act to prevent the consequences of natural disasters,
like floods. Wireless nodes have successfully been deployed in rivers where changes of the water
levels have to be monitored in real time.
Interior Monitoring
Observing the gas levels at vulnerable areas needs the usage of high-end, sophisticated
equipment, capable to satisfy industrial regulations. Wireless internal monitoring solutions
facilitate keep tabs on large areas as well as ensure the precise gas concentration degree.
Exterior Monitoring
External air quality monitoring needs the use of precise wireless sensors, rain wind resistant
solutions as well as energy reaping methods to assure extensive liberty to machines that will
likely have tough access.
Environmental/Earth Monitoring
The term Environmental Sensor Networks have evolved to cover many applications of WSNs to
earth science research. This includes sensing volcanoes, oceans, glaciers, forests, etc.
Air quality Monitoring
The degree of pollution in the air has to be measured frequently in order to safeguard people and
the environment from any kind of damages due to air pollution.
Factors Influencing Sensor Network Design
A sensor network design is influenced by many factors, which include fault tolerance;
scalability; production costs; operating environment; sensor network topology; hardware
constraints; transmission media; and power consumption.
19
These factors are important because they serve as a guideline to design a protocol or an
algorithm for sensor networks. In addition, these influencing factors can be used to compare
different schemes.
Fault Tolerance
Some sensor nodes may fail or be blocked due to lack of power, physical damage or
environmental interference. The failure of sensor nodes should not affect the overall task of the
sensor network. This is the reliability or fault tolerance issue. Fault tolerance is the ability to
sustain sensor network functionalities without any interruption due to sensor node failures. The
fault tolerance level depends on the application of the sensor networks
1.1 OUTLINE OF THE PROJECT
Design of an energy efficient wireless sensor networks through clustering and scheduling based
on node weighting parameter has been proposed. It is to overcome the disadvantages of LEACH,
DECSA, EECA and LECSA. The LEACH (Low Energy Adaptive Clustering Hierarchy) is an
application specific protocol architecture for wireless sensor networks. The DECSA (Distance
and Energy Cluster Structure Algorithm) is based on the classic clustering and routing algorithm,
it considers both the distance and residual energy. The EECA (Energy Efficient Clustering
Algorithm) is designed to select a head node for data aggregation to reduce the energy of data
transmitted. The LECSA (Load and Energy Consumption based Scheduling Algorithm) the
energy efficiency of wireless sensor networks.
From LEACH, DECSA, LECSA and EECA. The GSTEB (General Self-Organized Tree-
Based Energy-Balance routing protocol) in proposed has a better performance than other
protocols in balancing energy consumption, thus prolonging the lifetime of WSN. By
implementing it, the energy consumption of the overall network is reduced. The GSTEB which
builds a routing tree using a process where, for each round, BS assigns a root node and
broadcasts this selection to all sensor nodes. Subsequently, each node selects its parent by
considering only itself and its neighbors' information, thus making GSTEB a dynamic protocol.
20
1.1.1 SLEEP/WAKE-UP
Wake-up scheduling the transceiver of sensor node have active state, sleep state and idle state.
During its active state data is transferred to sink node. If the transceiver is in idle state it
moves to sleep mode to save the lifetime of wireless sensor network. The energy of
transceiver must be saved so it is moved to active mode at the required time. Remaining time it is
moved to sleep mode. Each frame consists of sleep and wake-up mode by using the sleep/wake
up protocol.
1.1.2 DECSA
In Distance Energy Cluster Structure Algorithm (DECSA) it examines both the distance and
residual energy information of the nodes. DECSA protocol can be divided into initialization
stage and working stage. In the initialization stage the election of cluster head is elected and
coordinates with its cluster member. The cluster's head considers the node's energy consumption
and communication between the node. After the election of cluster head, elect the base station
cluster head based on the threshold level. In the working stage cluster head collects the data from
the cluster member and transmits the data to their nearest cluster head. Then, the cluster head
collects the transmitted data to the base station to balance the energy consumption and process
the data transmission of the network.
1.1.3 LEACH
LEACH (Low Energy Adaptive Clustering Hierarchy) is one of the classic clustering protocols.
LEACH protocol can save more energy than the plane, multi-hop routing protocols, and static
network clustering algorithm. In LEACH, the nodes organize themselves into local clusters and
one node acting as the cluster head. All other non-cluster head nodes transmit their data to the
cluster head. The cluster head node receives data from all the cluster nodes and performs signal
processing functions on the data and transmits data to the BS. The operation of LEACH is
divided into rounds. Each round begins with a set-up phase when the clusters are organized,
followed by a steady-state phase when data are transferred from the nodes to the cluster head on
to the BS. LEACH forms clusters by using a distributed algorithm, where nodes make
autonomous decisions without any centralized control.
21
1.1.4 EECA
Energy Efficient clustering Algorithm (EECA) is used to process the data aggregation. EECA
algorithm separates the sensor network into a cluster head and its cluster member. In EECA
phases can be divided into setting phase and steady pace. In setting phase cluster head allocates
(TDMA) time slot to cluster members. In steady phase cluster member, send the data to the
cluster head within its time slot. Then, the cluster head transmits aggregate data to sink nodes.
By considering the cluster head corresponding cluster head is selected and aggregation tree is
constructed to save energy.
1.1.5 LECSA
In LECSA (Load and Energy Consumption Based Scheduling) protocol is based on two
functions. One is clustering and another one is scheduled. Initially cluster head is selected on
highest alpha value. The Node transmits the data based on the ascending order to the cluster
head. The scheduling is performed by using (TDMA) based protocol. The data can be transferred
to the cluster head, then cluster head send the data to sink node. So the cluster head should
have high energy transmission. In each round the cluster head can dynamically change from one
node to another. So that the energy consumption of the nodes are decreased. The energy
consumption is reduced.
1.1.6 GSTEB
The main task of WSN is to periodically collect information of the interested area and transmit
the information to BS. A simple approach to fulfilling this task is that each sensor node transmits
data directly to BS. However, when BS is located far away from the target area, the sensor nodes
will die quickly due to much energy consumption. On the other hand, since the distances
between each node and BS are different, direct transmission leads to unbalanced energy
consumption. To solve these problems the proposed system is developed to overcome the
disadvantages of existing systems.
Details
- Pages
- Type of Edition
- Erstausgabe
- Year
- 2016
- ISBN (PDF)
- 9783960675334
- ISBN (Softcover)
- 9783960670339
- File size
- 5.2 MB
- Language
- English
- Institution / College
- Anna University – University College of Engineering Panruti
- Publication date
- 2016 (April)
- Keywords
- Wireless Sensor Network Load and Energy Consumption based Scheduling Algorithm Energy efficient clustering algorithm Low Energy Adaptive Clustering Hierarchy Monitoring application Distance Energy Cluster Structure Algorithm
