514.txt

C AIRO U NIVERSITY
M ASTER T HESIS
Spatio-Temporal Resources Allocation
Using Data Mining Techniques
Author:
Mohammed Mostafa Ahmed
Supervisors:
Prof. Ehab Ezzat Hassanien
Prof. Aboul Ella Hassanien
Dr. Ayman Taha
A thesis submitted in fulfilment of the requirements
for the degree of Master in Information System
in the
Faculty of Computers and Information
Department of Information System
August 2017i
Abstract
Nowadays, many countries are suffering from the problem of poor distribution of re-
sources that serve the citizens. Our goal is finding best location for resources. In other
words, find the distribution of resources that minimize required resources. Examples of
resources that can make use of required solutions include hospitals, airports, sensors,
malls, schools, wireless sensors, mobile sensors and seismic stations in countries having
a non-uniform population density. We aim to allocate (localization) of resources in op-
timal locations that choose best location for resources to minimize number of resources
and maximize lifetime of this resources.
WSNs have many of applications including medical applications, highway monitoring,
habitat monitoring, military applications, environmental applications, and commercial
applications such as automated grocery checkout, personal health diagnosis, remote
controlled heating and lighting, etc. We present analysis and simulations of the al-
gorithms, demonstrating improved accuracy compared to other schemes although the
accuracy is probably not good enough for some high-end applications
In this thesis, we have made an attempt to address allocation (localization) of sensor
nodes in small and large-scale wireless sensor networks in order to target many of
objectives, some of objectives are minimize active nodes in wireless sensor networks
(WSNs) and determine minimum of multiple sink nodes in large-scale wireless sensor
networks (LSWSNs) using localization of sink nodes. Furthermore, after we determine
the best of location of sensor nodes and sink node for network, we perform transmis-
sion path between sink node and the rest of sensor nodes to find efficiently energy of
lowest cost paths among nodes and compared with similar topology algorithms. We
test extensive simulation on simulated WSNs randomly that show the potential of the
proposed topology management algorithm for identifying the lowest cost paths in order
to minimize energy consumption of network in order to prolong lifetime of WSNs and
all of experiments carried out using MATLAB that execute localization of sensor nodes
with clustering Integration with swarm optimization in order to produce best results for
localization of WSNs.Certification
I, Mohammed Mostafa Ahmed, certify that this thesis titled, “Spatio-Temporal Re-
sources Allocation Using Data Mining Techniques” and the work presented in it has
not been accepted in substance for any academic degree and is not being concurrently
submitted in candidature for any other degree. Any portion of thesis for which I am
indebted to other sources is mentioned and explicit references are given.
Signed:
Date:
iiAcknowledgements
First of all, All praises and thanks to Allah, who supplied me with the courage, the
guidance, and the love to complete my thesis. Also, I can not forget the assistance
of several individuals whose contributions are gratefully acknowledged. Without their
guidance, this thesis could not appear in its current format. I would like to thank my
supervisors, Prof. Ehab Ezzat Hassanien, Prof. Aboul Ella Hassanien, and Dr. Ayman
Taha for their patience and invaluable assistance. Also, i would like to thank all my
friends and my collages how had helped me along the way, especially my dear friend
Ahmed Hafez. Finally, I am grateful to my family ;my father, my mother, my wife, my
brother, and my sisters for their love, support and encouragement.
iiiiv
List of Publications
Published Papers:
1. Mohammed M. Ahmed, Essam H. Houssein, Aboul Ella Hassanien, Ayman Taha,
and Ehab Hassanien, Maximizing lifetime of Wireless Sensor Networks Based
on Whale Optimization Algorithm , In the 3rd International Conference on Ad-
vanced Intelligent Systems and Informatics (AISI2017). Sept. 9-11, 2017, Cairo-
Egypt, 2017.
Under submission Papers:
1. Mohammed M. Ahmed, Essam H. Houssein, Aboul Ella Hassanien, Ayman Taha,
Ehab Hassanien. Multi-Objective Whale Optimization Algorithm for Optimal
Multiple Sink Node Locations in Large-Scale Wireless Sensor Networks.
2. Mohammed M. Ahmed, Essam H. Houssein, Aboul Ella Hassanien, Ehab Has-
sanien, Ayman Taha. Multi-Objective Grasshopper Optimisation Algorithm for
Sink Node Localization in WSNs.Contents
Abstract i
Certification ii
Acknowledgements iii
List of Publications iv
List of Figures
viii
List of Tables x
Abbreviations xi
1 .
.
.
.
. 1
2
5
5
6
7
2
3
Introduction
1.1 Wireless Sensor Networks . . . . . .
1.2 Motivation . . . . . . . . . . . . . . .
1.3 Problem Definition . . . . . . . . . .
1.4 Thesis Objectives . . . . . . . . . . .
1.5 Thesis Contributions and Organization
.
.
.
.
.
.
.
.
.
.
Related Work
2.1 localization of wireless sensor networks .
2.2 Topology Control Protocols . . . . . . . .
2.3 Energy-Ware of wireless sensor networks
2.4 Clustering of wireless sensor networks . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
. .
.
.
. .
.
.
. .
.
.
. .
.
.
. .
.
.
. .
.
.
. .
.
.
. .
.
.
. .
.
.
. 8
8
9
11
11
Literature Review of methodologies
3.1 Swarm optimization algorithms . . . . . . . . . . . . .
3.1.1 Single Swarm optimization . . . . . . . . . .
3.1.1.1 Whale Optimization Algorithm . . .
3.1.1.2 Shrinking encircling preys: . . . . .
3.1.1.3 Spiral bubble-net feeding maneuver:
3.1.1.4 Search for prey: . . . . . . . . . . .
3.1.2 Grasshopper Optimization Algorithm (GOA) .
3.1.3 multi-objective Swarm optimization . . . . . . .
.
.
.
.
.
.
. .
.
.
.
.
.
.
. .
.
.
.
.
.
.
. .
.
.
.
.
.
.
. .
.
.
.
.
.
.
. .
.
.
.
.
.
.
. .
.
.
.
.
.
.
. .
.
.
.
.
.
.
. .
.
.
.
.
.
.
. 12
13
13
13
14
14
15
15
18
v
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.vi
Contents
3.1.3.1
3.1.3.2
3.2
3.3
4
5
Multi-Objective Whale Optimization Algorithm . . .
Multi-Objective Grasshopper Optimization Algorithm
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Data Mining Techniques . . . . . . . . . . . . . . . . . . . . . . . . .
3.2.1 Clustering Data Mining Technique . . . . . . . . . . . . . . . .
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Maximizing lifetime of Wireless Sensor Networks Based on WOA
4.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.1.1 Topology Control Techniques . . . . . . . . . . . . . .
4.1.2 Network Model . . . . . . . . . . . . . . . . . . . . . .
4.1.3 Whale Optimization Algorithm . . . . . . . . . . . . .
4.1.3.1 Shrinking encircling preys: . . . . . . . . . .
4.1.3.2 Spiral bubble-net feeding maneuver: . . . . .
4.1.3.3 Search for prey: . . . . . . . . . . . . . . . .
4.2 The Proposed WOTC Algorithm . . . . . . . . . . . . . . . . .
4.3 Discussion and Comparison Analysis . . . . . . . . . . . . . .
4.3.1 Complexity Analysis . . . . . . . . . . . . . . . . . . .
4.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Multi-Objective Sink Node Localization
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2 Multi-Objective Whale Optimization Algorithm . . . . . . . . . . . .
5.3 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.4 Literature Review . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.5 Methodology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.5.1 Problem Description . . . . . . . . . . . . . . . . . . . . . .
5.5.2 Multi-Objective Optimization . . . . . . . . . . . . . . . . .
5.6 Proposed Multi-Objective Whale Optimization Algorithm (MOWOA)
5.6.1 Overview WOA . . . . . . . . . . . . . . . . . . . . . . . . .
5.6.1.1 Shrinking encircling preys: . . . . . . . . . . . . .
5.6.1.2 Spiral bubble-net feeding maneuver: . . . . . . . .
5.6.1.3 Search for prey: . . . . . . . . . . . . . . . . . . .
5.6.2 Proposed MOWOA . . . . . . . . . . . . . . . . . . . . . . .
5.7 Experimental Results and Discussion . . . . . . . . . . . . . . . . . .
5.7.1 Scenario 1 . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.7.2 Scenario 2 . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.7.3 Evaluation criteria . . . . . . . . . . . . . . . . . . . . . . .
5.7.4 Comparison with Existing Studies . . . . . . . . . . . . . . .
5.8 summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.9 Multi-Objective Grasshopper Optimization Algorithm . . . . . . . .
5.10 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.11 Literature Review . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.12 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
18
18
18
18
.
.
.
.
.
.
.
.
.
.
. 19
20
20
22
23
23
24
24
25
28
33
34
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
. 36
36
37
37
39
41
41
42
43
43
43
44
44
45
48
49
51
56
60
60
61
62
64
66vii
Contents
5.12.1 Topology Control . . . . . . . . . . . . . . .
5.12.2 Network Model . . . . . . . . . . . . . . . .
5.12.3 Multi-Objective Optimization . . . . . . . .
5.12.4 Grasshopper Optimization Algorithm (GOA)
5.13 The proposed MOGOA . . . . . . . . . . . . . . . .
5.14 Experimental Results and Discussion . . . . . . . . .
5.14.1 The Localization Errors . . . . . . . . . . .
5.14.2 Evaluation criteria . . . . . . . . . . . . . .
5.14.3 Discussion . . . . . . . . . . . . . . . . . .
5.15 Summary . . . . . . . . . . . . . . . . . . . . . . .
6
.
.
.
.
.
.
.
.
.
. 66
66
68
69
71
76
79
81
82
86
Conclusion and Future Work
6.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
90
92
Bibliography
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
93List of Figures
4.1
4.2
4.3
4.4
4.5
4.6
4.7
4.8
4.9
4.10 The flowchart of WOA optimized TC (WOTC). . . . . .
Topology results of the A3 and WOTC for 200 nodes. . .
Topology results of the A3 and WOTC for 400 nodes. . .
Topology results of the A3 and WOTC for 600 nodes. . .
Topology results of the A3 and WOTC for 800 nodes. . .
Topology results of the A3 and WOTC for 1000 nodes. .
Number of active nodes for A3 and WOTC . . . . . . .
Energy consumption for active nodes for A3 and WOTC.
Ratio of active nodes to the rest nodes . . . . . . . . . .
Average number of iterations required for convergence .
5.1
5.2 The flowchart of the proposed MOWOA. . . . . . . . . . . . . . . . . . 46
Sink positions with three algorithms MOWOA, MOGWO and MOPSO
for network 2000 nodes . . . . . . . . . . . . . . . . . . . . . . . . . . 51
results of sink nodes for three algorithms. . . . . . . . . . . . . . . . . 52
Energy consumption for three algorithms MOWOA, MOGWO and MOPSO
for network 2000 nodes. . . . . . . . . . . . . . . . . . . . . . . . . . 52
The fitness function convergence. . . . . . . . . . . . . . . . . . . . . . 52
Sink positions with three algorithm MOWOA, MOGWO and MOPSO
for network 2000 nodes . . . . . . . . . . . . . . . . . . . . . . . . . . 54
results of sink nodes for three algorithms. . . . . . . . . . . . . . . . . 55
Energy consumption for three algorithms MOWOA, MOGWO and MOPSO
for network 2000 nodes. . . . . . . . . . . . . . . . . . . . . . . . . . 55
The fitness function convergence. . . . . . . . . . . . . . . . . . . . . . 55
Mean fitness function . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
Best fitness function . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
Worst fitness function . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
Mean fitness function . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
Best fitness function . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
Worst fitness function . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
Schematic flowchart of MOGOA. . . . . . . . . . . . . . . . . . . . . 73
the structure of tree graph. . . . . . . . . . . . . . . . . . . . . . . . . 76
Location of sink node in network size 200. . . . . . . . . . . . . . . . . 78
Comparison of energy consumption. . . . . . . . . . . . . . . . . . . . 78
: The comparison of convergence rate between MOGOA, CSO, and PSO. 79
5.3
5.4
5.5
5.6
5.7
5.8
5.9
5.10
5.11
5.12
5.13
5.14
5.15
5.16
5.17
5.18
5.19
5.20
viii
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
26
30
30
31
31
31
32
32
33
34List of Figures
5.21
5.22
5.23
5.24
5.25
Localization errors with different network size. . . . . . . . . . . . . .
Comparison Results of evaluation criteria. . . . . . . . . . . . . . . . .
Average Time for 3 algorithms per second (s). . . . . . . . . . . . . . .
Behavior of MOGOA on the 2D benchmark. . . . . . . . . . . . . . . .
Best Pareto optimal front obtained by the proposed multi-objective al-
gorithm with 2 objectives for 5 datasets. . . . . . . . . . . . . . . . . .
ix
80
82
83
88
89List of Tables
4.1
4.2
4.3
4.4 Atarraya simulation parameter. . . . . . . . . . .
Results obtained from the A3 algorithm. . . . . .
Results obtained from the WOTC algorithm. . . .
Comparison WOTC algorithm with other studies. .
.
.
. 29
29
30
33
5.1
5.2 Simulation setting parameter. . . . . . . . . . . . . . . . . . . . . . . .
Experimental results obtained from first fitness function for the pro-
posed algorithm MOWOA vs MOGWO and MOPSO algorithms. . . . .
Experimental results obtained from second fitness function for the pro-
posed algorithm MOWOA vs MOGWO and MOPSO algorithms. . . . .
Mean fitness function obtained from the different algorithms. . . . . . .
Best fitness function obtained from the different algorithms. . . . . . .
Worst fitness function obtained from the different algorithms. . . . . . .
Mean fitness function obtained from the different algorithms. . . . . . .
Best fitness function obtained from the different algorithms. . . . . . .
Worst fitness function obtained from the different algorithms. . . . . . .
Comparison MOWOA algorithm with other studies. . . . . . . . . . . .
Simulation parameter. . . . . . . . . . . . . . . . . . . . . . . . . . . .
Comparison of Energy Consumption for three algorithms MOGOA,
CSO and PSO. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Localization errors with a different node number. . . . . . . . . . . . .
summary of the experimental results. . . . . . . . . . . . . . . . . . . .
AverageTime per second (s). . . . . . . . . . . . . . . . . . . . . . . .
Comparison MOGOA algorithm with other studies of sink node posi-
tioning approaches. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
5.3
5.4
5.5
5.6
5.7
5.8
5.9
5.10
5.11
5.12
5.13
5.14
5.15
5.16
x
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
49
53
57
57
57
58
59
59
61
76
77
80
82
83
86Abbreviations
WSNs Wireless Sensor Networks
LSWSNs Large-Scale Wireless Sensor Networks
WOA Whale Optimization Algorithm
GOA Grasshopper Optimization Algorithm
PSO Particle Swarm Optimization
CSO Cat Swarm Optimization
MOO Multi-Objective Optimization
MOWOA Multi-Objective Whale Optimization Algorithm
MOGOA Multi-Objective Grasshopper Optimization Algorithm
MOPSO Multi-Objective Particle Swarm Optimization
MOGWO Multi-Objective Grey Wolf Optimization
MST Minimum Spanning Tree
TC Topology Control
ML Machine Learning
NSGA-II Non-dominated Sorting Genetic Algorithm
xiChapter 1
Introduction
In this chapter, we indicate description of wireless sensor networks (WSNs). The devel-
opment of (WSNs) has been Growing rapidly and is considered an important area for
the creation of new types of applications. WSNs composed of a large number of small
sensor nodes that monitor their environment, process data if necessary (using micropro-
cessors) and send/receive processed data to/from other sensor nodes. All sensor nodes
in network are connected to a sink node in central networks or to other sensing nodes via
a network. the central sink node collects data from all sensor nodes to be used by user.
In many cases, the sink is also capable of activating sensor nodes by broadcasting, by
sending network policy and control information. For WSNs, we have proposed many of
localization techniques with swarm optimization such as Whale Optimization Topology
Control (WOTC), multiple sink node localization using Multi-objective Whale Opti-
mization Algorithm (MOWOA) and Grasshopper Optimzation Algorithm (MOGOA).
In WOTC, we convert whale optimization algorithm into binary version because we
deal with discrete data of sensor nodes in wireless sensor network that obtain 1 de-
scribe active node and 0 describe inactive node in topology network, we use MOWOA
to choose best of multiple sink nodes locations in large scale WSN in order to overcome
two objectives are minimize energy consumption and reduce number of sink nodes to
maximize lifetime of the network. In this chapter, we illustrate overview for wireless
sensor networks.
1Chapter 1. Introduction
1.1
2
Wireless Sensor Networks
Wireless Sensor Networks (WSNs) contain large numbers of small nodes including
a power source, limited memory, communication resources, computational and Sink
Node (SN). Monitoring condition of environmental and gathering information about
the physical environment and send data to gateway of sensor networks that called sink
node. SN has a very large storage and large data processing capabilities. SK is re-
sponsible for receiving data from sensor nodes to the server from where end-user can
access them. The sensors nodes are deployed around the area of the Sink Node and
form groups as per the need of the Sink Node, that are restricted in terms of memory,
energy, computational and transmission power, WSNs are seen as a potentially versa-
tile, tool that use in measurements or monitoring of diverse phenomena is inexpensive
tool. WSNs have various of applications and WSNs issues will illustrate in next section
in detailed.
Wireless Sensor Networks Applications
WSNs applications have increased in recent times in fields such as area monitoring, en-
vironmental sensing, detection forest fires, monitoring air pollution, detection of land-
slide, and monitoring of machine health. In such applications, secure communication is
considered one of the important need among sensor nodes. Wireless sensor network ap-
plications are introduces a wide area of possible applications. Some of many examples
of such applications are:
1. Agriculture - Monitoring the moisture of ground and air temperature can optimize
automated irrigation systems. Systems aware of measurements provided by such
a network are able to determine the amount of water to be used for each area of
irrigation separately. [22, p. 36]
2. Active volcano monitoring - WSN can facilitate the monitoring of active vol-
canos. Concerning the self-organization of WSN sensor nodes, it is easy to deploy
and maintain large number of sensor nodes over volcano, which makes it possibleChapter 1. Introduction
3
to achieve a high spatial diversity data. Analysis of such data may help predict
volcano activity providing more time for evacuation process. [22, p. 38-39]
3. Structure health monitoring - Monitoring health of structures like buildings or
bridges can prevent structure collapse, possibly saving lives by localizing damage
on the structure. [22, p. 17] Traffic control - nodes gather data about speed
and number of vehicles on roads. Systems conscious of such data can propose
alternative routes or ideal speed for cars which may eliminate or at least reduce
traffic jams. [22, p. 26]
4. Pipeline monitoring - Although a sensor node itself has short transmitting range,
it is possible to create a chain from many sensor nodes which can span hundreds
of kilometers of pipe. By measuring pressure it is possible to locate damage or
leak on the pipe. [22, p. 35]
5. Industrial data logging - measurement of industrial processes can optimize quality
assurance of products. For example brick quality depends on the right tempera-
ture and pressure in smelter. When one of these values deviates, system can warn
operating staff or even interrupt the process preventing economic loss. [29]
Key Issues in Wireless Sensor Networks
There are many of the important issues in WSNs are stated below:
1. Energy Efficiency: WSNs consist of Sensor nodes that have limited battery ca-
pacity. This considered a constraint for some of applications and on the lifetime
of sensor node. There are many of sources of battery drainage composed of:
continuous sensing, transmission and reception modes of radio. thence, in order
to increase the network lifetime in unattended environments, efficient algorithms
should be developed at each layer of WSN in concern with the less energy uti-
lization. This includes techniques of data compression, data fusion (removal of
data redundancy), rotation of cluster heads, and adaptive mechanisms for radio
operations.Chapter 1. Introduction
4
2. Routing: WSN changes too frequently; as new nodes are added or die due to little
resources. Thus, in order to increase the coverage, connectivity, and remain up-
dated of network topology, neighbor information should be disseminated timely.
Furthermore, node that transmit should identify the best reliable shortest path to
the sink node/base station. Therefore, routing serves as a bottleneck in overall
efficiency of WSN.
3. Synchronization Time: Sensor Nodes have Synchronizing time that serves as a
basic prerequisite for various applications and protocols such as Time difference
of arrival (TDoA), Time division multiple access (TDMA), Time of arrival (ToA)
and so on. Basic property of WSNs, i.e., co-operation in communication, compu-
tation, sensing and actuation of different nodes solely depends on the time syn-
chronization among nodes [11].
4. Security: This is considered one of the critical issues in WSNs where the aim is to
get battle-field awareness in confidential data monitoring systems. There are three
layers that a node can be compromised at any layer. At application layer is used
to send the bogus data, at network layer is used to change the routing information
and at data-link layer is used to schedule data transfer at inappropriate time slots
resulting in network jam. In such cases, WSN should enable: intrusion detection
to prevent the integrity of collected information and authentication system - to
keep information privacy.
5. Fault-Tolerance: WSNs reliability is oftenly affected via various faults arising
from , battery depletion, hardware malfunctioning, environmental hazards and so
on. Individual node failures should not affect the global performance of WSNs.
This rate of failure may be high in harsh or hostile environments. In such cases,
intended purpose of WSN is achieved by techniques such as load balancing, etc.
In [12] Sensor nodes should have the capability of self-calibrating, self-testing,
self-recovering and so on [12].
6. Localization: This technique of finding physical coordinates of a node in a sensor
field is known as localization. localization of nodes is considered one of the most
important issue. Information sensed by a sensor node becomes useful only whenChapter 1. Introduction
5
its geographic allocation is tagged. Geographical routing is after the localization,
and other issues such as load balancing and spatial querying can also be achieved
[13].
Each issue in WSNs needs deep investigation. Some of these issues like synchroniza-
tion, localization and data gathering needs much more attention. In this thesis, we
focused on the localization issues in WSNs and solved it by swarm optimization and
data mining techniques
Wireless Sensor Networks Localization The objective of localization is to
nd the physical coordinates of sensor nodes. These coordinates can be either global or
relative.
1.2
Motivation
Still Writing
1.3
Problem Definition
This thesis aims to develop an algorithm for localization of sensor nodes and sink node
in a sensor network. The algorithm should be distributed and executed in individual
nodes. The algorithms run in sensor nodes and sink node location, the solution has
to be relatively simple, and each sensor node have limited resources such as memory,
computation and communication overhead. The aim from thesis is to be determine best
position nodes and sink node in network so we use in our work datamining technique
such as clustering to cluster of network of sensor nodes in to sub cluster and deal with
each of cluster to determine active node and sink node and we use swarm optimization
algorithms in order to extract best solution of network topology. Result of these methods
are reducing energy consumption of network in order to extend the network lifetime.Chapter 1. Introduction
6
The entities of a social network naturally fall into communities where the relationships
within a community is dense while the relationships between different communities are
sparse. Communities are also called groups, clusters, cohesive subgroups,or modules
in different contexts. Community detection is one of the fundamental tasks in social
network analysis. Finding a community in a social network is to identify a set of groups,
such that nodes in th same group interact with each other more frequently than with
those nodes outside the group. For instance, Fig.?? shows the effect after applying
community detection over the nodes of the network shown in Fig.??. Nodes are grouped
into two different communities based on modularity optimization (discussed later), with
each group in a different color.
1.4
Thesis Objectives
The main objective of the thesis is to improve the current methods used to localization
of sensor nodes and sink node within small and large-scale wireless sensor network.
Therefore, this research will seek the following targets:
• Find the best location of active nodes in network with network coverage in order
to decrease energy consumption of network to prolong the lifetime of network.
• Find the best location of sink node in small wireless sensor nodes.
• Find the best location of multiple sink nodes locations in large-scale wireless
sensor networks in order to increasing lifetime of network.
These objectives are directed to overcome the weak points in the current methods.
In order to accomplish our goal many swarm optimization algorithms with localization
of sensor nodes and sink nodes from the literature will be considered and their perfor-
mance will be evaluated on various chosen pa- rameters. The parameters will be chosen
in such a way that in effect they will help us to
nd an efficiently adaptable localization algorithm.Chapter 1. Introduction
1.5
7
Thesis Contributions and Organization
We start with some background in chapter 2 which state some overview of WSNs,
mention some WSNs datasets used to test the proposed algorithms, and explores some
related works. Our work is divided into two parts. In the first part, we start by solving
sensor nodes locations and reduce low energy consumption in small WSNs as a single-
objective optimization problem. To achieve this, we developed a discrete version of the
Whale Optimization Algorithm (WOA), called Discrete Whale Optimization Algorithm
(DWOA). This algorithm is introduced in the first part of subsection 5.6.1.
In the second part of our work, we solve the sink node localization problem in small
and large scale WSNs. In the second part of subsubsection 3.1.3.1 and subsubsec-
tion 3.1.3.2; the capabilities of the Whale Optimization Algorithm (WOA) and Grasshop-
per Optimization Algorithm (GOA) are enhanced to choose the best location of sink
node in small WSNs and find best locations for multiple sink node in Large-Scale WSNs
within multi-objective, developing new algorithm called MOWOA and MOGOA. In
chapter subsection 5.6.1; we use gthe Whale Optimization Algorithm (WOA) as an ef-
fective optimization technique to solve this problem as a single-objective optimization
problem, in which we separately use two objective to prolong network’s lifetime, as ob-
jective functions to find best locations of multiple sink nodes in order to reduce energy
consumption and increasethe network’s lifetime. Also we use GOA to solve the single
sink node location problem as a multi-objective optimization approach. For Evalua-
tion, in subsubsection 3.1.3.2; we introduce practical comparison between the results
obtained by our proposed algorithms and other well-known methods proposed in the
literature. Finally we provide conclusion and final remarks in chapter chapter 6.Chapter 2
Related Work
In this chapter background is introduced which state a description for the quality func-
tions and the similarity function used to measure the quality of community structures.
Following that is a description for some wireless sensor network datasets used to test
the proposed WSNs localization algorithms, then a social network tool used to visualize
and analyze the obtained results is mentioned. This chapter also explores some related
works.
2.1
localization of wireless sensor networks
Localization is considered one of the important issues that face wireless sensor net-
works. The aim of localization is to find the coordinates location of the sensor nodes
[22]. These coordinates can be either relative or global. Localization is achieved with
the help of a few location aware nodes usually referred as sink nodes. These sink nodes
are either manually programmed with their physical position or use the global position-
ing system (GPS) to determine their location. the location of sensor nodes is not being
predetermined so a localization system is used in order to provide position information
to the nodes. Localization techniques are used to estimate the coordinates position of
the sensor nodes [25,26]. It can be help of the position of a few sensors and inter-sensor
measurements.
8Chapter 2. Related Work
2.2
9
Topology Control Protocols
In this section, some of the state of the art related to this work is discussed as follow.
Topology Control (TC) composed of two separate components: the topology construc-
tion mechanism and the topology maintenance mechanism. The first mechanism of con-
struction produces a reduced topology with preserving important network properties,
such as network connectivity and coverage, and the second mechanism of maintenance
which changes the reduced topology. It is expected that two mechanisms of TC will
work in an iterative manner until the network energy is depleted, and two components
of TC will increase the network lifetime compared with a continuously run WSN with-
out topology control. The A3 algorithm is evaluated using simulations and compared
with the Energy Efficient CDS (EECDS) [16] and the CDS-Rule-K [17] algorithms.
TC is recognized to save energy and extend the lifetime of wireless sensor networks
and considered one of the most fundamental problems in WSNs [18]. Topology control
decreases energy consumption and prolongs network lifetime. Topology control min-
imizes MAC level contention and improves space reuse. By reducing the number of
working nodes or the transmission power of each node, many of applications that can
use topology control WSNs including national security, surveillance, health care, earth-
quake stations, environmental monitoring. Sensor nodes contain small devices such as
sensors, transceivers, processing, storage resources and possible actuators [19].
There are many of algorithms for topology control. Some of them based on the Graph
Theory such as the work of Li et al. [20] where they proposed a minimum spanning
tree -based algorithm denoted as LMST. Each node of the LMST algorithm starts to
build its local minimum spanning tree of its neighbors. The Step Topology Control
(STC) algorithm considered an extension to the Directed Relative Neighborhood Graph
(DRNG) protocol [21] builds the topology with three or fewer hops between two nodes.
The algorithm deactivates the edges between nodes based on the energy cost across the
hop between them and R. C. Eberhart and J. Kennedy proposed technique to maximize
lifetime network based on scheduling method [22] based automata. Which each nodeChapter 2. Related Work
10
is equipped with a learning automaton, which helps the node to select its proper state
(active or sleep).
Other topology control algorithms applied a number of bio-inspired techniques to build
that topology such as the PSO-minimum spanning tree-based topology control scheme
[23]. The algorithm runs a customized version of the PSO [22], which entitled the non-
dominated discrete particle swarm optimization (NDPSO). The NDPSO algorithm was
applied over a constructed multi-objective minimum spanning tree. The experiments
showed that this based bio-inspired approach prolonged the networks lifetime through
reducing the energy consumption and intercommunications interference.
Matheswaran and Muthusamy proposed a hybrid algorithm of both Bee Algorithm and
Simulated Annealing for a weighted minimal spanning tree (BASA-WMST) [24]. The
algorithm starts by splitting the network into a number of clusters based on the weighted
distance between nodes. The simulating annealing is the escaping algorithm from stick-
ing in local optima. Through a comparison between the BASA-WMST and other bio-
inspired based algorithms, it shows a significant performance improvement that goes
linearly with the networks size expansions.
2.3
Energy-Ware of wireless sensor networks
Some improved algorithms also have been proposed in [25, 26]. These studies indi-
cated that the more maximum the modularity the more robust the approach to detect
communities, hence many optimization techniques applied to optimize the modularity
as an objective such as greedy optimization[26] , extremal optimization [27] , simulated
annealing [28], genetic algorithms (GA) [29].
2.4
Clustering of wireless sensor networks
Another important issue that related to the stability and the performance of the topology
control protocols is a localization of the nodes, especially the sink node within theChapter 2. Related Work
11
wireless network. Fouad et al. [20] applied the standard PSO with the Gaussian jump
as a skipping value to y away from the local minima. The proposed approach selected
the best optimal position for the sink node within a network of stationary sensors. There
are other many applications of bio- inspired algorithm in WSN such as; estimation of
nodes physical coordinates in a 2-dimensional deployment area though a number of
previously located beacon nodes using PSO and bacterial foraging algorithm (BFA)
[21], or solving coverage problem related to the dynamic sensors deployment using
Arti
cial Bee Colony (ABC) [22].Chapter 3
Literature Review of
methodologies
In this chapter, a brief overview over a swarm intelligence optimization algorithms,
called Whale Optimization Algorithm (WOA) [30] and Grasshopper Optimization Al-
gorithm (GOA) [? ] are introduced. Swarm intelligence (SI) has become an important
area in many a variety of fields industrial, commercial sciences, biology, etc. The pri-
mary goal of implementing a functional swarm requires a detailed working knowledge
of swarm-intelligent systems. Swarm intelligence is considered a modern artificial in-
telligence discipline concerned with the design of multi-agent systems. SI is inspired
by behavior of social insects and animals and so on such as whales, grasshopper, wasps,
bees or ants. As later explained, swarm intelligence techniques have already been suc-
cessfully applied to our research field of wireless sensor networks. Although individual
insects and animals are small and quite limited, they are able to achieve huge and/or
complex tasks by means of cooperation. SI systems are distinguished by their robust-
ness and scalability, which usually appear as a result of the distributed conception of the
algorithm and the self-organization principle that governs the whole system
12Chapter 3. methodologies
3.1
13
Swarm optimization algorithms
In this section, presents the Swarm Intelligence (SI) methods for optimization of single
and multiple objective problems. The fundamental difference of Single and Multiple
Objective Optimization problems have been studied in this part. There are two single
swarm intelligence methods, i.e., Whale Optimization Algorithm(WOA) and Grasshop-
per Optimization Algorithm(GOA) and there are two multi-objective swarm intelligence
methods such as Multi-Objective Whale Optimization Algorithm(MOWOA) and Multi-
Objective Grasshopper Optimization Algorithm(MOGOA) has been deeply studied to
understand their ways of solving multiple and many objective problems distinctly. We
uses these swarm optimization algorithms to solve wireless sensor networks localization
problem with data mining techniques that will clarify in next section.
3.1.1
Single Swarm optimization
The aim from this section is to describe single swarm optimizations that we used it in
my thesis, illustrate in this section these swarm optimization in detailed.
3.1.1.1
Whale Optimization Algorithm
Whale Optimization Algorithm (WOA) proposed by Mirjalili et al. [30], is considered
one of swam intelligent application [31] that is a novel nature-inspired meta-heuristic
optimization algorithm, which mimics the social behavior of humpback whales. The
algorithm is in- spired by the bubble-net hunting strategy. They prefer to hunt school of
krill or small fishes close to the surface. Therefore, humpback whales swim around prey
within a shrinking circle and along a spiral-shaped path simultaneously to create distinc-
tive bubbles along a circle or ’9’ -shaped path. To simulate this behavior in WOA, there
is a probability of 50% to choose between the shrinking encircling mechanism and the
spiral model to update the position of whales during optimization. Their formulations
are designed as follows:Chapter 3. methodologies
3.1.1.2
14
Shrinking encircling preys:
In WOA, the currently best candidate solution is assumed as the target prey and the
other search agents try to update their positions towards it. This behavior is represented
by the following formula:
→
−
→
−
→
−
X (t + 1) = X (t) − A. D (3.1)
→
−
→
−
→
−
D = |C X ∗ (t) − X (t)| (3.2)
A = 2.a.r − a (3.3)
C = 2.r (3.4)
→
−
→
−
where X is the historically best position, X is a whale position and t indicates the cur-
rent iteration. a is linearly decreased from 2 to 0 over the course of iterations and r is
a random number uniformly distributed in the range of [0,1]. The sign || denotes the
absolute value.
3.1.1.3
Spiral bubble-net feeding maneuver:
A spiral equation is used between the position of whale and prey to mimic the helix-
shaped movement of humpback whales as follows:
→
−
→
−
X (t + 1) = e bk .cos(2πk).D 0 − X ∗ (t) (3.5)
−
→
→
−
D 0 = | X ∗ (t) − X (t)| (3.6)Chapter 3. methodologies
15
where b is a constant for defining the shape of the logarithmic spiral, and k is a random
number uniformly distributed in the range of [-1,1].
3.1.1.4
Search for prey:
In order to have a global optimizer, when A is greater than 1 or less than -1, the search
agent is updated according to a randomly chosen search agent instead of the best search
agent:
−
→
−−→
→
−
D ” = |C. X(t) rand − X (t)| (3.7)
−
→
−−→
→
−
X (t + 1) = X(t) rand − A. D ” | (3.8)
−−→
Where X(t) rand is selected randomly from whales in the current iteration. Finally, fol-
lows these conditions:
• |A| > 1 enforces exploration to WOA algorithm to find out global optimum avoids
local optima.
• |A| < 1 For updating the position of current search agent best solution is selected.
3.1.2
Grasshopper Optimization Algorithm (GOA)
Grasshopper is considered the type of insects, they are considered a pest due to their
damage to crop production and agriculture. The phases of grasshoppers composed of
egg, nymph, and adult. Grasshopper Optimization Algorithm (GOA) is a new nature-
inspired algorithm that proposed by Mirjalili et al. [? ] that divide the search process
into two tendencies: exploration and exploitation. In exploration, the search agents
are encouraged to move abruptly, while they tend to move locally during exploitation.
These two functions, as well as target seeking, are performed by grasshoppers naturally.Chapter 3. methodologies
16
Therefore, if we find a way to mathematically model this behavior. The mathematical
model for the swarming behavior of grasshoppers is presented as follows
X i = S i + G i + A i
(3.9)
Where X i is the position of grasshopper, S i , G i andA i refer to social interaction, the grav-
ity force on the i-th grasshopper and the wind advection respectively.
Note that to provide random behaviour the equation can be written as X i = r 1 S i + r 2 G i +
r 3 A i where r 1 , r 2 , andr 3 are random numbers in [0,1].
N
S i =
0
(3.10)
s d i j d i j
∑
i = 1
j 6 = i
Where N is the total number of d i j refers to the distance between the i-th and the j-th
grasshopper, and s is the strength of social forces
d i j = |x j − x i | (3.11)
x j − x i
d i j (3.12)
0
d i j =
S function is defined as s(r) = f e
−r
1
− e −r where f indicates the intensity of attraction
and l is the attractive length scale. the parameters l and f change comfort zone, attrac-
tion region, and repulsion region significantly. It should be noted that the attraction or
repulsion regions are very small for some values ( l = 1.0 or f = 1.0 for instance). From
all these values we have chosen l = 1.5 and f = 0.5 .
The G component in Eq.5.14 is calculated as follows:
0
0
G i = −ge g where g is the gravitational constant and e g shows a unity vector towards
the centre of earth.Chapter 3. methodologies
17
The A component in Eq.5.14 is calculated as follows:
0
0
A i = ue w where u is a constant drift and e w is a unity vector in the direction of wind.
After substitute components in equation 5.14
N
X i =
s x j − x i
∑
x j − x i
0
0
−g e g + u e w
d i j
(3.13)
i = 1
j 6 = i
modified version of this equation is proposed as follows to solve optimization problems:








 N

x
−
x
0
ub
−
lb

j
i 
d
d
X i = c  ∑ c
s|x dj − x i d |
 + T d

2
d i j 


 i = 1



j 6 = i
(3.14)
The first c from the left is very similar to the inertial weight (w ) in PSO. It reduces the
movements of grasshoppers around the target. In other words, this parameter balances
exploration and exploitation of the entire swarm around the target.
The second c decreases the attraction zone, comfort zone, and repulsion zone between
grasshoppers. Considering the component c
ub d −lb d
s|x dj − x i d |
2
in
The coefficient c reduces the comfort zone proportional to the number of iterations and
is calculated as follows:
c = c max − l
c max − c min
L
(3.15)
where cmax is the maximum value, cmin is the minimum value, l indicates the current
iteration, and L is the maximum number of iterations. In this work, we use 1 and
0.00001 for cmax and cmin respectivelyChapter 3. methodologies
3.1.3
18
multi-objective Swarm optimization
The aim from this section is to describe multi-objective swarm optimizations which
contains two or more objectives are conflicting in nature to solve problems that we used
it in my thesis, illustrate in this section these multi-objective swarm optimization in
detailed.
3.1.3.1 Multi-Objective Whale Optimization Algorithm
3.1.3.2 Multi-Objective Grasshopper Optimization Algorithm
3.2
3.2.1
3.3
Data Mining Techniques
Clustering Data Mining Technique
Summary
In This chapter we formulated the proposed algorithms that we used it to solve problem
of localization of sensor nodes and sink node in WSNs and LSWSNs as a single ob-
jective optimization problem and multi-objective optimization problem. We introduced
three proposed algorithms: first one, is to discover active nodes and inactive nodes
within small WSNs, this algorithm is called WOTC 5.6.1; second one, is to discover lo-
cation of sink node in within small WSNs to overcome conflicting multi-objective, this
algorithm is called MOGOA 3.1.3.2.Third one is to discover the location of multiple
sink node in LSWSNs to reduce energy consumption and reduce number of sink nodes
locations that covered region in order to prolong the lifetime network using 3.1.3.1 .
Finally, the results for applying the proposed algorithms on real world and benchmark
datasets are presented and discussed.Chapter 4
Maximizing lifetime of Wireless
Sensor Networks Based on WOA
In this chapter we use Whale Optimization (WO) as an effective optimization technique
to choose best network topology to prolong the network lifetime. We use WO to solve
this problem as a single-objective optimization problem. The lifetime of wireless sen-
sor networks (WSNs) is considered one of the most challenges that face the topology
control of WSNs. Topology control of WSNs is a technique to optimize the connec-
tions between nodes to reduce the interference between them, save energy and extend
network lifetime. We proposed an algorithm based on Whale Optimization Algorithm
(WOA) called WOTC, to overcome challenges that face topology control and maximiz-
ing the WSNs lifetime with minimizing the number of active nodes that coverage the
area in order to save energy. A comparative analysis was conducted between the pro-
posed WOTC algorithm and the A3 topology construction algorithm, the simulations
were carried out using Attaraya a simulator. Consequently, the results showed that the
final topology obtained by WOTC is better than A3 topology depending on the number
of neighbors and their energies for active nodes, use a graph traversal function to ensure
that all nodes which selected in a network are covered in the best topology selection.
19Chapter 4. Maximizing lifetime of Wireless Sensor Networks Based on WOA
4.1
4.1.1
20
Preliminaries
Topology Control Techniques
WSNs that impact on its operational lifetime, a number of algorithms were designed for
conserving the nodes energy. The topology control protocols are of these algorithms that
attempt to reduce the energy consumption within WSNs. A topology control protocol
is a process of controlling the number of active links between nodes, or selecting a
minimum subset of nodes to join the working backbone [32].
The objective of topology control protocol (TC) [33] is to minimize energy consump-
tion to prolong the lifetime of the topology control network and maintaining its con-
nectivity. Topology control composes of two main phases, topology construction, and
topology maintenance. The first topology construction is responsible for construct a
reduced topology of active nodes while reducing nodes’ transmission power or turning
off some nodes. The topology maintenance is responsible for periodically repairing
the previously constructed topology with the collaboration of formerly inactive nodes,
issues of topology control in WSNs are coverage and connectivity, first coverage cat-
egorized into a blanket, barrier and sweep coverage, second connectivity categorized
into temporal and spatial control.
Topology control in WSNs have many of definitions, there are authors such as [34],
[35], [36], [37], [38] that describe topology control technique is nodes dynamically
change their transmission range to gain energy saving and prolong the network lifetime.
The definition of clustering techniques is not considered as topology control because
the transmission power of nodes is usually not adjustable. The techniques use any con-
trolled parameter to configure the network topology for achieving energy saving, clus-
tering techniques do fulfill the definition of topology control since a set of nodes called
cluster heads is capable of controlling their set of neighbors in the network.Topology
control algorithms energy efficient can be classified into centralized or distributed algo-
rithms depending on the approach adopted for constructing the networks. Some paper
focus on Centralized approaches such as [39], [40], [41] that provide accurate globalChapter 4. Maximizing lifetime of Wireless Sensor Networks Based on WOA
21
information and inplemenation of these approaches are expensive in practice due to
significant communication overheads required for gathering information. These ap-
proaches are unfeasible for WSNs that typically have a large number of sensor nodes.
For this reason, distributed approaches are preferable to centralized approaches.
Many of researches focus on power control, for example, authors in [42], [43], [44]
use technique that controls the nodes transmission power but it does not aim to achieve
the energy efficiency of an entire network. Paolo [66] depicts power control as a tech-
nique that nodes transmit power to achieve a node such as energy efficient algorithms of
the wireless transceiver. Another power control technique mentioned in [38] is the tech-
nique that aims to select the best transmit power level for a single wireless transmission.
Techniques that aim to achieve the energy efficiency of the entire network instead of a
node-wide or channel-wide perspective are considered to power control.
The main challenge for these protocols is how to achieve this energy conservation with-
out sacrificing the important networks characteristics such as connectivity and sensing
coverage [33]. Therefore, any new topology control algorithm is to be designed not
only to fit distributed, self-configuration nodes but also it should consider not to use ex-
tra hardware modules such as GPS and mobility motors; to conserve node energy. The
A3 [45], and the A3Cov [46] are of these algorithms that used to construct a Connected
Dominating Set (CDS) of active nodes out of a fully connected graph. Both algorithms
are based on a weighted distance-energy-based metric. This metric is calculated based
on the Received Signal Strength Indicator (RSSI) of an initial discovery message, along
with the residual energy of the receiver node. While the difference between the two
algorithms is the more area coverage offered by A3Cov, both of them provide a virtual
backbone of nodes that guarantees connectivity among all nodes within the network.
This backbone takes the sensing lead while the rest of nodes turn themselves off (a
sleep mode) in order to save their energy for future maintenance procedures.Chapter 4. Maximizing lifetime of Wireless Sensor Networks Based on WOA
4.1.2
22
Network Model
Assume that in this paper there is only one central static sink node in the network and
there are sensor nodes have the same data generation rate are deployed randomly in a
convex region R, and also assume that the deployment of sensor node meets both the
coverage and the connectivity requirements of the networks. the sink node is far away
from the nodes, the sensor nodes are able to sense data and distribute it to the central
sink node.
Assume wireless sensor network with a set of sensing nodes and single sink node. Both
are distributed randomly and uniformly in a given region R = L × L, where L is the side
length. The sensing nodes have limited memory, bandwidth, and different energy. The
sink node has memory and bandwidth, the base station is far away from the nodes, but
it is connected with a set of sensor nodes. The sensor nodes are able to sense data and
distribute it to the sink node.
This paper consider the following assumptions about the sensor network model N: Let
N = {n 1 , ..., n k } be a set of sensor nodes that are distributed randomly and uniformly in
a given region R. All sensor nodes have the same capabilities such as sensing range and
limited memory but different of power energy. Assume N AN = {n 1 AN , ..., n kAN } be set of
active nodes in the network.
And assume that no node has any global information, e.g., the total number of nodes
n, and k is the maximal number of neighbors in the network. Assume that each node
knows its neighbors. Let N(u) denote the set of neighbors of u. We will refer to the
number of neighbors of u as the node degree of u, and denote it by η(u) = |N(u)|.
Assume that there is only one static sink node in the networks and the sensors with the
same data except to different in energy for each sensor node that are deployed randomly
in a convex region R . Assume that the distribution of sensors meets both the coverage
and the connectivity requirements. The network lifetime is defined as the time when the
first node fails. The network is divided into clusters (sub-regions). Every cluster region
is identified by a sensor node s i , which exists in this cluster. Hence the sensor node isChapter 4. Maximizing lifetime of Wireless Sensor Networks Based on WOA
23
also called the cluster head. Every sensor node will accept the incoming packets with
probability one and will update its buffer if the flag is set to one.
4.1.3
Whale Optimization Algorithm
Whale Optimization Algorithm (WOA) proposed by Mirjalili et al. [30], is considered
one of swam intelligent application [31] that is a novel nature-inspired meta-heuristic
optimization algorithm, which mimics the social behavior of humpback whales. The
algorithm is in- spired by the bubble-net hunting strategy. They prefer to hunt school of
krill or small fishes close to the surface. Therefore, humpback whales swim around prey
within a shrinking circle and along a spiral-shaped path simultaneously to create distinc-
tive bubbles along a circle or ’9’ -shaped path. To simulate this behavior in WOA, there
is a probability of 50% to choose between the shrinking encircling mechanism and the
spiral model to update the position of whales during optimization. Their formulations
are designed as follows:
4.1.3.1
Shrinking encircling preys:
In WOA, the currently best candidate solution is assumed as the target prey and the
other search agents try to update their positions towards it. This behavior is represented
by the following formula:
→
−
→
−
→
−
X (t + 1) = X (t) − A. D (4.1)
→
−
→
−
→
−
D = |C X ∗ (t) − X (t)| (4.2)
A = 2.a.r − a (4.3)Chapter 4. Maximizing lifetime of Wireless Sensor Networks Based on WOA
C = 2.r
24
(4.4)
→
−
→
−
where X is the historically best position, X is a whale position and t indicates the cur-
rent iteration. a is linearly decreased from 2 to 0 over the course of iterations and r is
a random number uniformly distributed in the range of [0,1]. The sign || denotes the
absolute value.
4.1.3.2
Spiral bubble-net feeding maneuver:
A spiral equation is used between the position of whale and prey to mimic the helix-
shaped movement of humpback whales as follows:
→
−
→
−
X (t + 1) = e bk .cos(2πk).D 0 − X ∗ (t) (4.5)
−
→
→
−
D 0 = | X ∗ (t) − X (t)| (4.6)
where b is a constant for defining the shape of the logarithmic spiral, and k is a random
number uniformly distributed in the range of [-1,1].
4.1.3.3
Search for prey:
In order to have a global optimizer, when A is greater than 1 or less than -1, the search
agent is updated according to a randomly chosen search agent instead of the best search
agent:
−
→
−−→
→
−
D ” = |C. X(t) rand − X (t)| (4.7)
−
→
−−→
→
−
X (t + 1) = X(t) rand − A. D ” | (4.8)Chapter 4. Maximizing lifetime of Wireless Sensor Networks Based on WOA
25
−−→
Where X(t) rand is selected randomly from whales in the current iteration. Finally, fol-
lows these conditions:
• |A| > 1 enforces exploration to WOA algorithm to find out global optimum avoids
local optima.
• |A| < 1 For updating the position of current search agent best solution is selected.
4.2
The Proposed WOTC Algorithm
This section describes the design and the implementation issues of whale optimization
algorithm for topology control (WOTC) as shown in Figure 4.1.
→
−
The whales position in WOA X = x[1],x[2],.,x[n] which represent candidates solutions.
The algorithm applies to enhancement the topology control problem in WSNs. The
→
−
candidate solution X is converted into a binary vector using a sigmoid function, this
→
−
workaround has been used for similar problems [47]. Each whales position X ; x[i]
takes either the values 1 or 0 which means the node i within the final topology is active
→
−
or inactive, respectively. Equation 4.9 is used to convert X into Bi (the binary vector)
through the application of a sigmoid. This approach only updated whale position vector
is forced to be binary; see Algorithm 3 using the main updating equation as shown in
Equation 4.9.
B(i) =


 0 if sigmoid(X[i]) < rand

 1 if sigmoid(X[i]) ≥ rand
(4.9)
Where rand is a random number drawn from uniform distribution [0,1], and sigmoid(a)
is defined in Equation (10).
Sigmoid(a) =
f (x) =
∑
n
i=1
1
1 + e −10(a−0.5)
B[i]
neighbor i .E i
(4.10)
(4.11)Chapter 4. Maximizing lifetime of Wireless Sensor Networks Based on WOA
26
F IGURE 4.1: The flowchart of WOA optimized TC (WOTC).
Where neighbor i number of neighbors for each node i, E i is the initial energy in node i,
the equation supports the proposed algorithm to focus on the solution with the minimum
possible number of active nodes with low energy consumption from them. One draw-
back of equation 4.11 is the fairness between nodes; since the nodes with low energy
with a high number of nodes that covered from it.
During implementation of proposed algorithm for topology network when intialize of
each position using uniform distribution result in that approximately 50% of the nodeChapter 4. Maximizing lifetime of Wireless Sensor Networks Based on WOA
27
will be active this may lead to large convergence time for the algorithm and does not
ensure a great diversity of the search agent in the search space. To overcome this prob-
lem, we vary the probability of a node being active in the initialization step. Therefore
the population is divided into five groups each has 20% search agents. The groups are
initialized with different percent of initial active nodes: 10%, 25%, 50%, 80% and 90%,
respectively.
The fitness function alone does not ensure that the final topology will cover all nodes,
so a graph traversal function is used to check if all nodes are covered by neighbors of
active nodes in the topology. The breadth-first search is used to traversing the graph that
if the active nodes do not cover all nodes then the function penalize the fitness value.
Description of the function used to calculate the fitness value is outline in Algorithm 2.
Input: A graph represents the nodes and their neighbors with energies in the input
WSN
2: Output: The final reduced topology
3: Randomly Initialize the whales population Xi(i = 1, 2, ..., n).
4: Initialize the number of maximum iteration convergence windows check. while
t <= itermax do
1:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
end
ForEach search agent Xi do
Convert the position into a binary version using Equation 9
Calculate the fitness of search agent i using Equation 11
End ForEach
X = the best search agent.
Calculate and Update a; A, C, p and l.
ForEach search agent Xi do if p < 0.5 then
end
If(|A| < 1)
Update the position of the current search agent by the Eq.(1)
Else (|A| ≥ 1)
Select a random search agent (X rand )
Update the position of the current search agent by the Eq.(8)
EndIf
Else (p ≥ 0.5)
Update the position of the current search by the Eq.(5)
EndIf
End ForEach
EndWhile
Algorithm 1: pseudo code of WOTC algorithm.Chapter 4. Maximizing lifetime of Wireless Sensor Networks Based on WOA
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
28
Input: Bi binary vector that representing a topology. N number of nodes within the
network. SN refer to the sink node
Output: The fitness value of the input solution
Create hashset of all active nodes within the B vector.
Create empty hashset Coverlist, to contain all covered nodes
Create empty queue Q.
Enqueue SN in Q
Fitness = 0.
WhileQ is not empty
Dequeue node u from Q.
1
Fitness+ =
neighbor i .E i
mark u as Visited
ForEach node v adjacent to u do
If v is not in the Coverlist then
add v to Coverlist.
EndIf
If v is active and is not visited then
Enqueue v in Q.
EndIf
End ForEach
EndWhile
If number of nodes in C6 = n then
Fitness = ∞
EndIf
Algorithm 2: Calculating fitness value per each population solution.
4.3
Discussion and Comparison Analysis
The proposed WOTC based algorithm was implemented and evaluated using a Java-
based simulation tool called Atarraya [48]. Table 5.11 illustrates a summary of the most
important simulation parameters that were adjusted for the experimental scenarios.
The experiments were not conducted to evaluate the quality of the route but focus on
reducing the number of active nodes that to cover the deployment area and preserves
the networks connectivity. Therefore, the performance analysis of the proposed algo-
rithm focuses on decrease the number of active nodes and the total energy within the
constructed tree of active nodes.
The simulations of nodes are assumed to mimic the characteristics of simple sensors
with the energy model that defined in [49]. The lifetime of network use (DGTTRec)Chapter 4. Maximizing lifetime of Wireless Sensor Networks Based on WOA
29
T ABLE 4.1: Atarraya simulation parameter.
Parameter Value
Deployment area
Number of nodes
Sensor node model
Node communication
Node sensing
Node location distribution
Node energy distribution
Max energy 600m 600m
100,200,300,400,500,600,700,800,900,1000
Simple
range 100m
range 20m
Uniform
Uniform
1000 milliamperes-hour (mA-h )
topology maintenance protocol which proved as the best maintenance policy for the A3
construction protocol [46]. Since the results vary due to the uncontrolled random de-
ployments of sensor nodes, the performance analysis calculated the mean of 10 deploy-
ment scenarios per each networks density and for each different scenario the average of
NRuns = 10 different runs of the algorithm with 500 times for maximum of iteration
that is calculated for both algorithms A3 and the WO-TC, Tables 4.2 and 4.3 summa-
rizes all obtained results, where N, T, AN, Energy and Ratio means the network size,
total network energy, number of active nodes, Energy consumption and Ratio of active
nodes to the rest nodes respectively.
T ABLE 4.2: Results obtained from the A3 algorithm.
N T AN Energy Ratio
100
200
300
400
500
600
700
800
900
1000 48852
94623
153785
198407
244942
306955
354704
388703
455076
500135 30
44
40
44
46
42
40
41
49
46 12500
22799
19131
23214
25188
19437
20514
18401
29720
25833 0.3
0.22
0.13
0.11
0.092
0.07
0.057
0.051
0.054
0.046
Topology results of the A3 and WOTC algorithms are shown in Figures 4.2, 4.3, 4.4,
4.5 and 4.6 for network size 200, 400, 600, 800 and 1000 respectively, red color rep-
resent active nodes and blue color represents inactive nodes. In the reduced topology,
red nodes represent the active nodes that construct the networks topology, only edgesChapter 4. Maximizing lifetime of Wireless Sensor Networks Based on WOA
30
T ABLE 4.3: Results obtained from the WOTC algorithm.
N T AN Energy Ratio
100
200
300
400
500
600
700
800
900
1000 48852
94623
153785
198407
244942
306955
354704
388703
455076
500135 28
38
37
39
41
38
37
37
37
39 11153
17391
17118
19007
19197
18851
18173
16661
21082
16829 0.28
0.19
0.12
0.098
0.082
0.063
0.053
0.046
0.041
0.039
( A ) A3 algorithm.
( B ) WOTC algorithm.
F IGURE 4.2: Topology results of the A3 and WOTC for 200 nodes.
( A ) A3 algorithm.
( B ) WOTC algorithm.
F IGURE 4.3: Topology results of the A3 and WOTC for 400 nodes.
between active nodes or edges between active nodes and non-active nodes are shown.
Other edges edges between non-active nodes are not shown.
The main target of constructing a reduced topology has been achieved where the numberChapter 4. Maximizing lifetime of Wireless Sensor Networks Based on WOA
600 600
500 500
400 400
300 300
200 200
100 100
0
31
0
0
100
200
300
400
500
600
0
100
( A ) A3 algorithm.
200
300
400
500
600
( B ) WOTC algorithm.
F IGURE 4.4: Topology results of the A3 and WOTC for 600 nodes.
600
500
400
300
200
100
0
0
100
( A ) A3 algorithm.
200
300
400
500
600
( B ) WOTC algorithm.
F IGURE 4.5: Topology results of the A3 and WOTC for 800 nodes.
600
500
400
300
200
100
0
0
( A ) A3 algorithm.
100
200
300
400
500
600
( B ) WOTC algorithm.
F IGURE 4.6: Topology results of the A3 and WOTC for 1000 nodes.
of active nodes (AN) decreased using the WOTC proposed algorithm compared to the
A3 algorithm. Figure 4.7 shows finding that the number of active nodes is linearly
increased with the growth of networks size. Figure 4.8 illustrates energy consumption
for active nodes in a network and Figure 4.9 illustrates the ratio between active nodesChapter 4. Maximizing lifetime of Wireless Sensor Networks Based on WOA
32
obtained by both algorithms to the remaining number of nodes. During implementation
whenever we increase maximum iteration in WOTC Algorithm, WOA optimization
produce best results with a minimum of active nodes that coverage area with low energy
consumption to save lifetime network.
F IGURE 4.7: Number of active nodes for A3 and WOTC
F IGURE 4.8: Energy consumption for active nodes for A3 and WOTC.
However, a brief comparison with the previous related studies is presented in Table
5.10. The information about the number of nodes (N), distribution methods, techniques
(used reduce the number of active nodes and maximize the lifetime) reported in previous
studies are presented in Table 5.10. Consequently, it is seen that the proposed WOTC
algorithm providing the best performance in comparison to the recent approaches de-
scribed in Table 5.10 in terms of number of nodes and energy consumption.Chapter 4. Maximizing lifetime of Wireless Sensor Networks Based on WOA
33
F IGURE 4.9: Ratio of active nodes to the rest nodes
T ABLE 4.4: Comparison WOTC algorithm with other studies.
Ref. Techniques N Distribution
[50] Active Nodes Scheduling 110 AGN randomly
[51] SACR protocol 100: 500 Randomly Distributed
[52] Scheduled activity EADC 100 Randomly
[53] Energy Balanced Topology Control 200 200 nodes placed in random locations.
[54] PSO 100 Uniform distribution
Proposed WOTC 100:1000 Dividing nodes to 5 groups
4.3.1
Complexity Analysis
A major difference between proposed algorithm and A3 algorithm is the centralized
computing within the first algorithm compared to the distributed computing within the
A3. The WOTC algorithm to be operated over the sink node, the nodes consume some
energy in the initial neighbors discovery process. In this section we outline the expected
runtime of WOTC algorithm over the central sink node. The runtime of WOTC algo-
rithm is parameter dependent that it depends on the total number of iterations, the cost
of calculating the fitness value of each search agent, and the cost of updating the search
agents positions.Chapter 4. Maximizing lifetime of Wireless Sensor Networks Based on WOA
34
The expected runtime of the first part is linear time of the number of nodes O(n), The
second part depend on the number of active node and the expected cost is O(n AV * d)
where n AV is number of active nodes in the solution and d is the expected average node
degree in the network. In the worst case in which a solution has all its nodes active; i.e.
n AV =n , the expected runtime will be O(n*d) which equals to total number of edges in
the network.
In this work measured the required number of iterations that have been taken by the
proposed algorithm to converge to a solution, which is the average of all runs of the
algorithm for each network scenario from the same experiment as before. Figure4.10
summarizes the average number of iterations required for convergence and its standard
deviation. As observed from the figure it had fast conversion to a solution within a range
of 1200 to 1500 iterations for a network consisted of 1000 nodes.
F IGURE 4.10: Average number of iterations required for convergence
4.4
Summary
This paper introduces a topology control protocol based on Whale Optimization intelli-
gent approach for wireless sensor nodes. The paper provides a discrete binary version
of the original Whale algorithm in which the position of each Whale is calculated and
represented in binary format. Moreover, the algorithm introduces a function that min-
imizes the number of active nodes with low energy consumption within the selectedChapter 4. Maximizing lifetime of Wireless Sensor Networks Based on WOA
35
nodes without losing the network coverage and connectivity characteristics. Also, the
paper introduces a performance analysis between the proposed algorithm and the A3
topology construction algorithm. The experimental results showed the advantages of
the proposed algorithm in terms of a significant reduction in the number of active nodes
within the constructed topology compared to the A3 algorithm. Moreover, the iterations
required to converge to a suitable solution are within acceptable ranges.Chapter 5
Multi-Objective Sink Node
Localization
5.1
Introduction
In this chapter, we need to convert swarm optimization algorithms into version multi-
objective to overcome on multiple conflicting objectives that face Wireless Sensor Net-
works (WSNs) and large-Scale Wireless Sensor Networks (LSWSNs).
In the first part of this chapter we introduce practical comparison between the results
obtained by our proposed algorithm MOWOA algorithm (discussed in chapter chapter 3
and other well-known methods proposed in the literature, which are accepted as proven
ways for community detection in single dimensional social networks. In the second part
of this chapter we compare the results obtained by our proposed algorithms MOGOA
with the results of CSO and PSO also discussed in chapter chapter 3.
36Chapter 5. Multi-Objective Sink Nodes Localization
5.2
37
Multi-Objective Whale Optimization Algorithm
The sink node location problem in the large-scale wireless sensor networks (LSWSNs)
plays a vital role in the data processing and the control center, the rest of sensor nodes
are responsible for sensing interesting events and transmitting the related information
to sink node. LSWSNs are divided into a number of subnetworks (clusters) which con-
sist of a number of sensor nodes and a cluster head (CH) to deal with subnetwork to
determine the optimal location of CH. Cluster heads are also sensor nodes, and they
have considerably more resources such as powerful batteries, large memory, long range
antenna, etc. The two main objectives of this paper are; choose the best location of mul-
tiple sink node and low-energy consumption to prolong the lifetime of the network to
solve the multi-objective problems based on the whale optimization algorithm (WOA).
The multiple sink node location problems in LSWSNs are discussed and multi-objective
whale optimization algorithm (MOWOA) to obtain the optimal minimal of multiple sink
nodes locations with reducing the energy consumption is proposed. Consequently, the
energy consumption will reduce depending on the value of transmissions data from sen-
sor nodes to various sinks in order to extend the lifetime of the LSWSNs. Furthermore, a
fitness function is introduced to balance the number of sink nodes and energy consump-
tion to maximize the network lifetime. Experimental results illustrates that the proposed
MOWOA algorithm significantly enhances the large-scale network lifetime compared
with the multi-objective gray wolf optimization (MOGWO) and multi-objective particle
swarm optimization (MOPSO).
5.3
Introduction
Wireless sensor networks (WSNs) consists of sensor nodes that contain small devices
such as sensors, transceivers, processing, storage resources and possible actuators [19].
There are many of applications that WSNs can be motivated it such as seismic stations,
battlefield surveillance, health monitoring, habitat monitoring, home automation, and
traffic control, WSNs can be deployed in region of earthquake to track and monitorChapter 5. Multi-Objective Sink Nodes Localization
38
locally or remotely seismic wave that occurred in specific region [? ][? ] through
designing the locations of seismic sensing stations. Unlike traditional networks, WSNs
are self-organized, application specific and data-centric, and large-scale wireless sensor
networks (LSWSNs) composed of thousands of sensor nodes that can work for their
life expectancy, one year or more. Through cooperative processing among these sensor
nodes, LSWSNs are used in civil, military areas, and health organizations. An optimal
sink node location strategy can strongly increase the lifetime of network and decreases
the energy consumption by decreasing the distance between the sensor and sink nodes
[? ]. Therefore, the sink node location in LSWSNs in order to reduce their transmitting
data time from source to sink and to provide better energy-efficiency to prolong network
lifetime is introduced in this paper.
The sink nodes in LSWSNs forward the messages directly to both of the sink nodes and
the farthest one to save their energy. Many sensor nodes will become quickly unable
to communicate with the base station and the network becomes nonoperational [? ].
So in this paper the choose of the best location of sink nodes to receive all messages
from sensor nodes without consuming their energies quickly. Consequently, the whale
optimization algorithm was enhanced to overcome this drawback as follows. First, each
objective function is treated separately, and all objective functions are evaluated for
each whale. Generally, a non-dominant solution (best position) is used to guide the
whales called a leader. In each iteration, non-dominant solutions are stored to detect
Pareto-optimal solutions that are stored in a memory called an external archive (EA) [?
].
The following fundamental key issues are considered in MOWOA algorithm such as;
evaluating the objective functions, selecting the leaders from the EA to promote diver-
sity in the EA and maintaining the EA. The neighborhood topology used for information
exchange. In this paper, the main objective of MOWOA algorithm is to minimize the
distance between the sink node and the remnant sensor nodes in LSWSNs and effi-
ciently reduce power consumption of the sensor nodes that are the furthest from sink
node.Chapter 5. Multi-Objective Sink Nodes Localization
39
The rest of the paper is organized as follows. In Section 5.4 the related work is in-
troduced. Section 5.5 presents an overview of the problem description and the multi-
objective optimization problem. Section 5.6 briefly, introduces the concepts of whale
optimization algorithm and the proposed MOWOA. The performance evaluation of the
proposed algorithm with the existing algorithms is presented in Section 5.7. Conclu-
sions are presented in Section ??.
5.4
Literature Review
Even though the sink node location is an obvious problem in WSNs and LSWSNs, the
literature has been dealt with sink node location rarely compared to other areas, like
routing protocols and localization etc. in WSNs. Although however,many studies, such
as, [? ] have introduced an algorithm (MSPOP) for multiple sink node design network
in LSWSNs which claim that finding the optimal location of sink nodes. Also, [? ]
have proposed position multiple sink nodes in WSN and route traffic flow from all of
the sensors to these multiple sink nodes and address different sink location methods
with different intentions for the main purpose of network lifetime extension. Heinzel-
man et al., [? ] have proposed the Low-energy adaptive clustering hierarchy (LEACH)
and the distributed cluster formation technique that enables self-organization of large
numbers of nodes and rotating cluster head positions, that solve energy constrained in
WSNs field is included. Also, the determination of sink node location in a small WSNs
based on cat swarm optimization algorithm (CSO) has been proposed in [? ]. In the
evaluation process, the proposed work is compared with the sink node location determi-
nation algorithm based on the particle swarm optimization (PSO) algorithm proposed
by Mohamed et al., [55].
Other algorithms have been applied a number of bio-inspired techniques to node lo-
cation in WSNs such as artificial bee colony algorithm for multi-objective [? ], and
multi-objective node location [? ]. Improving the speed of the sink location procedure
use a greedy simulated annealing search heuristic that converges fast to a near-optimal
location which proposed by [? ]. Sensor node location algorithm using multi-objectiveChapter 5. Multi-Objective Sink Nodes Localization
40
PSO with fuzzy logic to select the best compromised solution on the Pareto front has
been proposed by pradhan and panda [? ]. Rani and Devarajan [? ] has proposed PSO
with fuzzy logic in which three objectives are used.
In addition, a hybrid algorithm of both bee algorithm and simulated annealing for a
weighted minimal spanning tree (BASA-WMST) has been proposed in [24]. While the
bee algorithm responsible for information exchange within the network, the simulating
annealing is the escaping algorithm from sticking in local optima. Through a compar-
ison between the BASA-WMST and other bio-inspired based algorithms, it shows a
significant performance improvement that goes linearly with the networks size expan-
sions. Some of the researchers have proposed a sink node location strategies like the
one introduced by Chen and Li [? ] which contain the energy and lifetime oriented
strategies in both the single-hop and multiple-hop WSNs. Energy and lifetime oriented
introduced by Chen and Li had outperformed the energy-oriented strategy in terms of
networks lifetime presented by the work of Hou et al., [? ] that developed an effi-
cient polynomial-time heuristic algorithm (SPINDS), which attempted to increase the
network lifetime by iteratively moving a relay node to another enhanced location.
Another algorithm to solving the problem of multiple base station locations and elec-
trostatic model is applied to determine sinks locations is introduced in [? ]. Slama et
al. [? ], have utilized a graph partitioning techniques to obtain the smaller and balanced
sub-networks over which existing sink location for small to medium scale WSNs. In
addition to the aforementioned, most researchers focused on the energy conservation
like [? ][56] and several studies like [? ] handle locating the multiple sinks in LSWSNs
and the location of integration points in multi-hop wireless networks is optimized. Fi-
nally, a multi-objective optimization problem for sensor node location to maximizing
the coverage with minimum energy consumption has studied by Abidin, Husna Zainol
[? ].
up to our knowledge, all the techniques have been proposed to deal with the sink node
location in general for WSNs and specially for LSWSNs have been focused on a single
fitness objective function. so, theses techniques either cover limited of objectives or fail
to incorporate several application specific requirements into the performance measureChapter 5. Multi-Objective Sink Nodes Localization
41
of the heuristic. The main objective of our proposed MOWOA algorithm in this paper
is a balance between cardinality of sink node and energy consumption based on WOA
methodology. The proposed MOWOA algorithm primarily finds optimal locations of
sink node in LSWSNs in order to reduce distances from sensor nodes in a network with
saving the energy consumption.
5.5
5.5.1
Methodology
Problem Description
LSWSNs, consist of thousands of sensor nodes. these sensor nodes are distributed
either randomly or uniformly in a given region area R =L × L, where L is the area
side length. The sensor nodes have restricted both of memory and bandwidth. The
sensor nodes are able to receive data and distribute it to the sink nodes. In LSWSNs,
all sensor nodes transmits data to the sink node, the bottleneck around this sink node
represents the major constraint. According to aforementioned, this limits the network
performance, particularly the network lifetime. Indeed, as all the sensor data has to
be forwarded to sink node. In this paper, the whole network area is divided into a
number of subnetworks, which makes the cluster distribution uniform to reduce the
energy consumption, the farther distance between cluster head and rest of nodes will
make the inter-cluster head nodes consume more energy. Dividing the entire WSN
into a number of regions with each region assigning with a cluster head so that the
communication consumption between the members of the cluster and the cluster nodes
can be maintained at a low level.
The main objective in LSWSNs design prolong the network lifetime to place sink nodes
in an optimal location to decreases the average distance of sensor nodes from its neigh-
bor’s sink with low energy consumption. Cluster-based schemes improve network life-
time; however, most popular algorithms of clustering such as LEACH, k-means use
the concept of one hop for intra-cluster which leads to the larger average transmissionChapter 5. Multi-Objective Sink Nodes Localization
42
distance. In this paper, MOWOA-based cluster formation technique with multiple ob-
jectives is proposed for intra-cluster data aggregation with a connected dominated set
(CDS). Multiple sink node is considered one of a possible solution for LSWSNs to
minimize the distance between each sensor node and the nearest sink node, leading to
saving energy consumption for transmission operations. In order to achieve this, the
multiple sinks should be optimally deployed within the sensed area, so this paper aims
to propose an algorithm to choose the optimal location of sink node with low energy
consumption.
5.5.2
Multi-Objective Optimization
Many of optimization problems are naturally multi-objective that usually have two or
more objectives which in conflict each other. Multi-objective optimization (MOO) cre-
ated to overcome a number of conflicting objectives simultaneously. In multi-objective
optimization, there are some solutions but none of them can be said the winner. There-
fore, EA is built to store a historical record obtained along the search space for the
non-dominated vector. The EA is constructed in the initialization phase. Then, all ob-
tained solution are rearranged according to non-domination compared with each other
in the space to choose the non-dominated solution. finally, all non-domination solution
are stored in EA.
Formulating as a multi-objective problem is necessary in some cases, especially when
the problem involves more than one objective functions and several constraints. The
objective functions are typically conflicting; the task of MOO is to find a trade-off
between the conflicting objectives. Unlike single objective problem optimization, the
results of MOO are usually a set of solutions.
→
−
→
−
The point X ∗ ∈ Ω is an optimal of Pareto if, for all X ∈ Ω and g = 1, 2, ..., k either,
→
−
→
−
∀i g( f i ( X ) = f i ( X ∗ ))
,
or there is at least one i ∈ g such that :
→
−
→
−
f i ( X ) ≥ f i ( X ∗ )
The general multi-objective evolutionary optimization problem (MOEP) [? ], can beChapter 5. Multi-Objective Sink Nodes Localization
43
→
−
formulated as follow; finding the vector X ∗ = [x 1 ∗ , x 2 ∗ , ..., x n ∗ ] T that satisfies the n inequal-
→
−
→
−
ity constraints: q i ( X ) ≥ 0 i = 1, 2, ..., n the equality constraints w i ( X ) = 0 i = 1, 2, ..., p
and optimizes.
→
− →
−
→
−
→
−
→
−
f ( X ) = [ f 1 ( X ), f 2 ( X ), ..., f k ( X )] T
MOO problem is decomposed into a number of single objective subproblems and they
are optimized concurrently. Whale optimization algorithm (WOA) is a popular meta-
heuristic that is particularly well-suited for this class of problems. Traditional WOA,
is accommodated to solve the multi-objective problems by using specialized fitness
functions, introducing methods to promote solution diversity, and other algorithms.
MOWOA is done based on decomposition by applying non-dominated Pareto optimal.
5.6
Proposed Multi-Objective Whale Optimization Al-
gorithm (MOWOA)
5.6.1
Overview WOA
Whale Optimization Algorithm (WOA) proposed by Mirjalili et al. [30], is considered
a novel nature-inspired meta-heuristic optimization algorithm, which mimics the social
behavior of humpback whales. The algorithm is inspired by the bubble-net hunting
strategy. The mathematical formulations are constructed as follows:
5.6.1.1
Shrinking encircling preys:
The presently best candidate solution is considered as the target prey and rest search
agents aims to choose their positions depending on it. This situation is formulated as
follows:
→
−
→
−
→
−
X (t + 1) = X (t) − A. D
(5.1)Chapter 5. Multi-Objective Sink Nodes Localization
44
→
−
→
−
→
−
D = |C X ∗ (t) − X (t)| (5.2)
A = 2.a.r − a (5.3)
C = 2.r (5.4)
→
− →
−
where X , X , t, and r are illustrates the best solution, the whale position, current itera-
tion and a random number within [0, 1] respectively and a is linearly decreased from 2
to 0 over with the number of iterations.
5.6.1.2
Spiral bubble-net feeding maneuver:
the relation between the position of the prey and whale to mimic the helix-shaped move-
ment of humpback whales is calculated by the spiral Equation as follows:
→
−
→
−
X (t + 1) = e bk .cos(2πk).D 0 − X ∗ (t) (5.5)
−
→
→
−
D 0 = | X ∗ (t) − X (t)| (5.6)
where b and k are a constant for defining the shape of the logarithmic spiral, and a
random number uniformly within this range [-1, 1] respectively.
5.6.1.3
Search for prey:
The randomly updating of the search agent and avoiding the local optima (|A| > 1 or
|A| < −1) is calculated as follows:Chapter 5. Multi-Objective Sink Nodes Localization
45
−
→
−−→
→
−
D ” = |C. X(t) rand − X (t)| (5.7)
−
→
−−→
→
−
X (t + 1) = X(t) rand − A. D ” | (5.8)
−−→
Where X(t) rand is selected randomly from whales in the current iteration accordingly to
these conditions:
• |A| > 1 enforces exploration to WOA algorithm to find out global optimum avoids
local optima.
• |A| < 1 for updating the position of current search agent best solution is selected.
5.6.2
Proposed MOWOA
Many real-life optimization problems are solved by multiple objectives. There are many
multiple objectives that are conflicting that to be optimized and obtaining the best so-
lution consider a difficult task. The diversity techniques have been developed in the
operations research field to tackle these kind of problems. Furthermore, meta-heuristics
that find approximate solutions have attracted great interest over the last decades. Also,
the multi-objective evolutionary algorithms (MOEAs) have been became a very interest-
ing technique to solve the multi-objective optimization problems. Many of researchers
use many of optimization to solve these multi-objective problems such as MOPSO [? ],
MOGWO [? ] and others.
This work was proposed a new algorithm based on the whale optimization algorithm
to solve the multi-objective problem called MOWOA. WOA is a ”population-based
algorithm” so, each whale represents a solution in the multi-dimensional space. Also,
the previous best experience for each whale has recorded and each whale must know
the leader solution (experience) has founded by the whole swarm. Due to the concept of
multi-objective optimization at each generation, the EA is updated. Over the progress of
evolution process, EA has updated by currently new solutions. Continuously, each newChapter 5. Multi-Objective Sink Nodes Localization
46
solution is compared with the closest non-dominated solution to decided the best one
to keep it in the EA. So, EA must be limited accordingly to the directly proportional
to the computational time and the number of comparisons. Finally, if the number of
non-dominated solutions exceeds the allocated size of EA, then remove the crowded
members using the crowding distance [? ]. The framework of the proposed MOWOA is
depicted in Figure 5.1 and the detailed MOWOA algorithm is illustrated in Algorithm
3.
F IGURE 5.1: The flowchart of the proposed MOWOA.Chapter 5. Multi-Objective Sink Nodes Localization
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
Input: A graph represents the nodes and their neighbors with energies
Output: Locations of sink nodes
Initialize the whales population X i , (i = 1, 2, ..., n).
Initialize a; A, C, p and l
Calculate the objective values for each search agent
Obtain non-dominated solutions and initialized EA
X = SelectLeader(EA)
Exclude leader X from EA temporarily to avoid selecting the same leader
Add back leader to EA
Initializing start of iteration t = 1 and initialize Maximum of iteration T.
while t <= T do
end
11: ForEach candidate network solution X i do
if p < 0.5 then
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
end
If(|A| < 1)
Update position of current node by Eq.5.14
Else (|A| ≥ 1)
Select a random search agent (X rand )
Update position of current node by Eq.5.8
EndIf
Else (p ≥ 0.5)
Update position of current node by Eq.5.18
EndIf
End ForEach
Update a; A, C, p and l.
Calculate the objective values for each search agent
Obtain non-dominated solutions
Update EA if EA is full then
end
Run the grid mechanism to omit one solution
27: Add the new solution to EA
28: EndIf if Every new added solutions to EA located outside the hypercubes then
29:
30:
31:
32:
33:
34:
35:
36:
end
Update the grids to cover the new solution(s)
EndIf
X=SelectLeader(EA)
Exclude X from EA temporarily to avoid selecting the same leader
Add back leader to EA
t=t+1
EndWhile
return EA (contains sink nodes locations)
Algorithm 3: Pseudo code of the proposed MOWOA.
47Chapter 5. Multi-Objective Sink Nodes Localization
48
As mentioned before, this paper introduce a solution to the multi-objective optimization
problem, where the first objective function is minimizing optimal sink node location in
a LSWSNs. The second objective function is reducing energy consumption for the net-
work; this function will be managed as a constraint. Then, the multi-objective problem
is turned into a mono-objective constrained problem. WOA is adapted in order to ac-
complish the multi-objective optimization by the way similar to MOPSO proposed in
[? ] combine two new phase. In the first phase, EA is responsible for ”storing non-
dominated Pareto optimal solutions obtained” and in the second one is the strategy of
leader election in which their task to select the whale leader solution from EA for the
hunting process.
5.7
Experimental Results and Discussion
This section discusses the results of the proposed algorithm. MOWOA compared with
MOGWO and MOPSO. Table 5.11 illustrates a summary of the most important sim-
ulation parameters that were adjusted for the experimental scenarios of the proposed
algorithm for the multi-objective sink node location. Tables 5.2 and 5.3 summarizes
all obtained results, where N, CP, SN and EC means the network size, comparison pa-
rameters, sink nodes and energy consumption respectively. The simulation nodes are
supposed to mimic functions of Crossbows Mica Mote sensors with energy model in-
troduced in [46]. Then, the dynamic global time-based topology recreation (DGTTRec)
topology maintenance protocol has utilized to test the whole networks lifetime, which
was proved as the best maintenance policy for A3 protocol [49]. Moreover, when the
time threshold (T=1000)is exceeded, the adapted triggering criterion for the construc-
tion reduces the new topology.
Frequently, the proposed techniques in the literatures are utilized medium size WSN
(typically less than 100 nodes) to evaluate theses techniques. On the other hand, LSWSNs
composes of hundreds or thousands of sensor nodes can be deployed, the location of
multiple sinks still requires advanced studies. When the number of nodes is limited, the
paths between each node and its closest sink is relatively short. However, the proposedChapter 5. Multi-Objective Sink Nodes Localization
49
T ABLE 5.1: Simulation setting parameter.
Parameter Value
Deployment area
Number of nodes
Sensor node model
Node communication
Node sensing
Node placement
Node energy
Max energy 1000m * 1000m
1000,200,...,5000
Mica Mote
range 100m
range 20m
Uniform
Uniform
2000 (mA-h )
T ABLE 5.2: Experimental results obtained from first fitness function for the proposed
algorithm MOWOA vs MOGWO and MOPSO algorithms.
N
1000
2000
3000
4000
5000
CP MOWOA MOGWO MOPSO
SN
EC
SN
EC
SN
EC
SN
EC
SN
EC 12
11119
11
8852
8
10401
9
8026
9
6370
12
10464
13
10403
8
8924
12
9263
8
12261
14
13061
10
11112
8
10689
7
9356
8
7542
MOWOA algorithm is deployed in LSWSNs according to two scenarios depending on
two different fitness function.
5.7.1
Scenario 1
To evaluate the performance of the proposed MOWOA compared with MOGWO and
MOPSO in terms of the number of sink nodes and energy consumption, Equation 5.9 is
utilized as the fitness function of the proposed algorithm.
Fitness =
1
.
1
N neighbor ∑ N neighbor E neighbor
i=1
(5.9)Chapter 5. Multi-Objective Sink Nodes Localization
50
Where N neighbor denotes the number of sensor neighbor served by sink node, and E neighbor
energy for each sensor node for sink’s neighbors.
To test the cardinality of sink nodes of the proposed algorithm, 30 iterations was tested
on the same network. The final result of the proposed algorithm in depicted in Table 5.2
in terms of number of sink nodes and energy consumption for each algorithm.
Figure 5.2a,5.2b and 5.2c, demonstrates the best cardinality of sink nodes have been
obtained from MOGWO, MOPSO and MOWOA respectively, for network of size 2000
nodes and the red points represents the sink nodes in the network.
Figure5.3 represents results of the cardinality of sink nodes curve from the proposed
algorithm compare with other algorithms MOGWO and MOPSO in all LSWSNs that
obtained in Table 5.2, in Figure 5.3 shows number of sink nodes obtained from the
proposed algorithm have been decreased by 25% when the network size increase up
to 5000 nodes with low energy consumption compared with MOGWO and MOPSO
algorithms.
Figure 5.4 represents the results of energy consumption obtained from the proposed al-
gorithm and other algorithms MOGWO and MOPSO in all LSWSNs size. Also, Figure
5.4, shows that the average energy consumption achieved by the proposed algorithm
has been decreased by 13% compared to MOGWO and MOPSO algorithms.
This test is concerned in testing the convergence of the fitness function. All fitness val-
ues of each iteration were collected and represented as a curve in the following Figure
5.5. The fitness values are highly different at the beginning, then the convergence de-
creases to be close values at the end of the process. This depends on the number of sink
nodes multiplied by the number of iterations. Figure 5.5 shows the convergence of the
fitness function of the compared algorithms.Chapter 5. Multi-Objective Sink Nodes Localization
51
( A ) MOGWO
( B ) MOPSO
( C ) MOWOA
F IGURE 5.2: Sink positions with three algorithms MOWOA, MOGWO and MOPSO
for network 2000 nodes
5.7.2
Scenario 2
To evaluate the performance of the proposed MOWOA algorithm with MOGWO and
MOPSO in terms of the number of sink nodes locations and energy consumption, Equa-
tion 5.10 is utilized as the second fitness function of the proposed algorithm.Chapter 5. Multi-Objective Sink Nodes Localization
52
F IGURE 5.3: results of sink nodes for three algorithms.
F IGURE 5.4: Energy consumption for three algorithms MOWOA, MOGWO and
MOPSO for network 2000 nodes.
F IGURE 5.5: The fitness function convergence.
Fitness =
AN
.
1
N neighbor ∑ N neighbor E neighbor
i=1
(5.10)
Where N neighbor denotes the number of sensor neighbor served by sink nodes, AN is the
number of active nodes in network, and E neighbor , energy for each sensor node neigh-
bors.Chapter 5. Multi-Objective Sink Nodes Localization
53
To test the cardinality of sink nodes of the proposed algorithm, 30 iteration was tested
on the same network. The experimental results of the number sink nodes and energy
consumption are illustrated in Table 5.3.
T ABLE 5.3: Experimental results obtained from second fitness function for the pro-
posed algorithm MOWOA vs MOGWO and MOPSO algorithms.
N
1000
2000
3000
4000
5000
CP MOWOA MOGWO MOPSO
SN
EC
SN
EC
SN
EC
SN
EC
SN
EC 10
8958
7
7301
7
7512
5
4186
6
5348
12
13025
11
9796
9
8718
6
4741
7
6892
14
14199
10
11955
10
10213
6
4997
7
6892
Figure 5.6a,5.6b and 5.6c, illustrates the best cardinality of sink nodes have been ob-
tained from MOGWO, MOPSO and MOWOA respectively, for network of size 2000
nodes and the red points represents the sink nodes in the network.
Figure5.7 represents results of the cardinality of sink nodes curve from the proposed
algorithm compare with other algorithms MOGWO and MOPSO in all LSWSNs that
obtained in Table 5.3, in Figure 5.7 shows number of sink nodes obtained from the
proposed algorithm have been decreased by 17% when the network size increase up
to 5000 nodes with low energy consumption compared with MOGWO and MOPSO
algorithms.
Figure 5.8 represents the results of energy consumption from the proposed algorithm
and other algorithms in all LSWSNs size that demonstrated in Table 5.3. its clear that
the average energy consumption for the proposed algorithm have been decreased by
19% compared to MOGWO and MOPSO algorithms. All fitness values of each iteration
were collected and represented as a curve in Figure 5.9. The fitness values are highly
different at the beginning, but converge to close values at the end of the process. This
depends on the number of sink nodes multiplied by the number of iterations. Figure5.9
shows the convergence of the fitness function.Chapter 5. Multi-Objective Sink Nodes Localization
54
( A ) MOGWO
( B ) MOPSO
( C ) MOWOA
F IGURE 5.6: Sink positions with three algorithm MOWOA, MOGWO and MOPSO
for network 2000 nodes
Its clear from Figure 5.7 that the number of sink node obtained by the proposed algo-
rithm is the best compared to other algorithms. due to the fact of minimal transmission
cost from the source nodes to the sinks for MOWOA. Also, the balance between a num-
ber of sink nodes and energy consumption that nodes and sink consumed in the network
through MOWOA.
An observation for the results that obtain in Tables 5.2 and 5.3, the proposed MOWOAChapter 5. Multi-Objective Sink Nodes Localization
55
F IGURE 5.7: results of sink nodes for three algorithms.
F IGURE 5.8: Energy consumption for three algorithms MOWOA, MOGWO and
MOPSO for network 2000 nodes.
F IGURE 5.9: The fitness function convergence.
algorithm has been achieved better results in terms of the number of sink nodes and
energy consumption over all the network sizes compared to other existing algorithms.
Furthermore, the experimental results show that MOWOA chooses the optimal location
of sink node so, the number of sink node is reduced and greatly reduce energy con-
sumption, which can lead to longer network lifetime. Also, As shown in Figure 5.3, 5.4
and 5.5 in first scenario and Figure 5.7, 5.8, and 5.9 in the second scenario, the balance
between the number of sink nodes and energy consumption are better with proposed
MOWOA algorithm.Chapter 5. Multi-Objective Sink Nodes Localization
56
Moreover, it is observed that when the number of sink nodes increases beyond a certain
threshold does not effect on the energy consumption at the same time the neighbour of
the sink nodes increases in which the average energy consumption is reduced.
5.7.3
Evaluation criteria
In this paper, the LSWSNs datasets are consisted of network sizes (N) from 1000 to
5000 nodes. The algorithm is run repeatedly for M = 10 times for statistical significance
of the results. The following measures are used to validate and evaluate the proposed
algorithm:
1. Mean fitness function is the average of the fitness function value obtained from
running the algorithm M times. The Mean fitness function is calculated as shown in
equation 5.24.
f i
∑ M
Mean = i=1
M
(5.11)
where f i is the best fitness value obtained at run i.
2. Best fitness function is the minimum of the fitness function value obtained from
running the algorithm M times. The Best fitness function is calculated as shown in
equation 5.25.
M
Best = min f i
i=1
(5.12)
where f i is the best fitness value obtained at run i.
3. Worst fitness function is the maximum of the fitness function value obtained from
running the algorithm M times. The Worst fitness function is calculated by Equation
5.26.
M
Worst = max f i
i=1
where f i is the best fitness value obtained at run i.
(5.13)Chapter 5. Multi-Objective Sink Nodes Localization
57
Evaluation of scenario 1
T ABLE 5.4: Mean fitness function obtained from the different algorithms.
N MOWOA MOGWO MOPSO
1000
2000
3000
4000
5000
Average 0.3402
0.1304
0.65
0.251
0.203
0.315
0.506
0.240
0.403
0.184
0.360
0.339
0.312
0.401
.156
0.442
0.435
0.349
T ABLE 5.5: Best fitness function obtained from the different algorithms.
N MOWOA MOGWO MOPSO
1000
2000
3000
4000
5000
Average 4.13
1.26
6.75
3.51
2.58
3.65
5.42
3.12
5.36
2.34
3.17
3.88
4.56
2.01
5.76
6.12
3.68
4.43
T ABLE 5.6: Worst fitness function obtained from the different algorithms.
N MOWOA MOGWO MOPSO
1000
2000
3000
4000
5000
Average 4.78
1.41
7.23
4.54
2.86
4.164
5.84
3.43
5.73
2.61
3.46
4.214
4.80
2.64
6.01
6.34
3.91
4.74
Table 5.4 outlines the performance of the algorithms using the fitness function men-
tioned in Equation 5.9. This Table shows the average fitness obtained over M runs
and is calculated using equation 5.24. The best performance is achieved by the pro-
posed MOWOA proving its ability to choose optimal sink nodes locations effectively.
Similar results are seen in Table 5.5 and Table 5.6 that outlines the best and the worst
fitness function obtained over M runs and is calculated using Equations 5.25 and 5.26
respectively. Also, Figures 5.10, 5.11 and 5.12 shows the graphical representation of
the results obtained from scenario 1.Chapter 5. Multi-Objective Sink Nodes Localization
58
F IGURE 5.10: Mean fitness function
F IGURE 5.11: Best fitness function
F IGURE 5.12: Worst fitness function
Evaluation of scenario 2
T ABLE 5.7: Mean fitness function obtained from the different algorithms.
N MOWOA MOGWO MOPSO
1000
2000
3000
4000
5000
Average 6.36
2.68
1.41
6.83
5.52
2.34
3.67
6.84
6.81
1.73
5.42
4.89
6.50
4.75
6.86
2.48
5.34
5.19Chapter 5. Multi-Objective Sink Nodes Localization
59
T ABLE 5.8: Best fitness function obtained from the different algorithms.
N MOWOA MOGWO MOPSO
1000
2000
3000
4000
5000
Average 5.95
2.35
1.32
6.48
5.17
4.25
3.81
6.53
6.62
1.48
5.31
4.75
6.39
4.64
6.76
2.24
5.14
5.03
T ABLE 5.9: Worst fitness function obtained from the different algorithms.
N MOWOA MOGWO MOPSO
1000
2000
3000
4000
5000
Average 5.34
2.13
1.21
6.32
5.08
4.01
3.81
6.95
6.92
1.84
5.63
5.23
6.74
4.79
6.88
2.51
5.47
5.28
Also, the proposed MOWOA algorithm outperforms the other compared algorithms as
shown as follows. Table 5.7 outlines the performance of the algorithms using the fitness
function mentioned in Equation 5.10. This Table shows the average fitness obtained
over M runs and is calculated using equation 5.24. The best performance achieved by
the proposed algorithm is an evidence of the ability of this algorithm to choose the
optimal sink nodes locations effectively and efficiently. Similar results are seen in Table
5.8 and Table 5.9 that outlines the best and the worst fitness function obtained over M
runs and is calculated using Equations 5.25 and 5.26 respectively. Furthermore, Figures
5.13, 5.14 and 5.15 demonstrates the graphical representation of the results obtained
from scenario 2.
F IGURE 5.13: Mean fitness functionChapter 5. Multi-Objective Sink Nodes Localization
60
F IGURE 5.14: Best fitness function
F IGURE 5.15: Worst fitness function
5.7.4
Comparison with Existing Studies
However, a brief comparison with the previous related studies is presented in Table
5.10. The information about the number of sink nodes, distribution methods, techniques
(methods have been used to choose the number of sink node) reported in previous stud-
ies are presented in Table 5.10. Consequently, it is clear that the proposed MOWOA
algorithm providing the best performance in comparison with the recent algorithms de-
scribed in Table 5.10 in terms of minimizing the number of sink nodes and energy
consumption in order to increase the network lifetime
5.8
summary
A multiple sink node location algorithm is proposed in this paper by applying the whale
optimization algorithm to solve the multi-objective problems in Large-scale Wireless
Sensor Networks (LSWSNs) called MOWOA. In addition, a new fitness functions are
introduced to choose the minimal cardinality of sink nodes and reduce the total energyChapter 5. Multi-Objective Sink Nodes Localization
61
T ABLE 5.10: Comparison MOWOA algorithm with other studies.
Ref
[? ]
Techniques N
PSO-based
multiple-
sink
[? ]
PSO with
exhaustive
search
[? ]
Multiple
sink loca-
tion
Proposed MOWOA
Remark
300 Energy de-
creased
300 Lifetime
increased
100 Energy de-
creased
1000:5000 Optimal
sink node
location
consumption. The proposed MOWOA algorithm is designed with different numbers of
the sensor node environments and two scenarios with different fitness function to eval-
uate the proposed algorithm and solving the multi-objective problems in LSWSNs. The
experimental results have been illustrated that the proposed MOWOA algorithm ob-
tained a better results compared to MOGWO and MOPSO in terms of the minimizing
the number of sink nodes and saving energy consumption. Consequently, the experi-
mental results indicate that proposed algorithm have been obtained a better efficiency
on reducing the total average energy consumption in the whole LSWSNs and energy
consumption of the LSWSNs has been reduced by 19% compared with the other algo-
rithms. .
5.9
Multi-Objective Grasshopper Optimization Algorithm
Saving energy has become one of the main challenges in wireless sensor networks
(WSNs) and their applications. Sink node localization refers to the process of locating
the position of sink node so, considers one of the important stages in WSNs that affect in
network lifetime. This paper studies the problem of determining the sink node locationChapter 5. Multi-Objective Sink Nodes Localization
62
in WSNs, there are many objectives are to prolong network lifetime, the first objec-
tive is to choose best nearest sink node position and the second is to minimize energy
consumption and reducing localization error for WSNs. In order to solve this multi-
objective problem, a grasshopper optimisation algorithm (GOA) is adopted to deal with
the multi-objective problem. In this paper, a multi-objective grasshopper optimization
algorithm (MOGOA) for selecting the optimal localization of sink node in WSNs is
proposed. In MOGOA, after determining the location of sink node using a greedy algo-
rithm for obtaining the minimum spanning trees to create transmission paths from the
sink node to the rest of sensor nodes. In order to evaluate the capability of MOGOA
for handling the optimal sink node localization in WSNs, a set of different network size
have been used and applied on all the comparison algorithms such as particle swarm
optimization (PSO) and cat swarm optimization (CSO). Simulation results proved that
the proposed algorithm was determined the optimal sink node localization and reducing
the total energy consumption by 5.6 % compared with other two algorithms, which can
prolong the lifetime of the network in an efficient way.
5.10
Introduction
Wireless sensor networks (WSNs) usually have a huge number of sensor nodes. The
sensor nodes collect data in the monitoring area and transmit the data to sink node for
further processing, WSNs are spatially distributed sensors to monitor environmental or
physical conditions, such as pressure, temperature, sound, there are many of applica-
tions for WSNs such as potential applications surveillance, seismic waves monitoring,
habitat monitoring, traffic monitoring, healthcare, disaster relief, and disaster manage-
ment [? ]. They are applied to monitor the inside and outside environment, factory
and process automation, earthquake, and so forth. WSNs have received more and more
attention from industry and academia. Sensor node sent data to one or more base sta-
tions that serve the whole network. WSNs have characteristics that pose technical chal-
lenges include dense ad-hoc deployment, spatial distribution, dynamic topology, and
constraints in memory, bandwidth, computational resources, and energy [? ]. Local-
ization is considered one of the main challenges related to WSNs. There are two typesChapter 5. Multi-Objective Sink Nodes Localization
63
of localization of WSNs algorithms are: range-based algorithms [? ] and range-free
algorithms [? ] that depend on physical attributes of the wireless signals transmitted
between antennas The base station utilizes information that receives from other nodes to
build a map of the network and estimate the position of the sensor, a sink node address in
self-configuration topology raises another issue that influences the performance of the
WSN in terms of delay, energy, and operational lifetime. Therefore, the position of sink
node should be accurately selected so other nodes will not use much power to deliver
their data to that location. As a consequence, the networks lifetime will be maximized.
In an effort to solve multi-objective problems [? ], this paper proposes a multi-objective
version of the recently proposed GOA [? ] called (MOGOA). Although the current
algorithms in the literature are able to solve a variety of problems, they are not able
to solve all optimization problems. This work proposes the multi-objective GOA with
the hope to better solve some the problem of finding the best location of sink node in
a single static sink with reducing energy consumption to prolong network lifetime in
WSNs environment. Moreover, after choosing the location of sink node in the network
uses the method of the greedy algorithm [? ] such as prim’s algorithm [? ] that finds a
minimum spanning tree (MST) [? ] algorithm for shortest paths in networks to create
transmission paths for the sensor nodes to the sink node. Finally, the performance of
the proposed MOGOA is compared with other swarm optimization algorithms such as
particle swarm optimization (PSO) [55] and cat swarm optimization (CSO) [? ]. The
rest of the paper is organized as follows. In Section 5.11 literature review are presented.
Section 5.12, the preliminaries of optimization in a multi-objective, the topology control
techniques and the basic grasshopper optimization algorithm are introduced. The multi-
objective grasshopper optimization algorithm MOGOA is illustrated in Section 5.13.
Section 5.14, briefly reviews the experimental results for various performance measures
of the comparison algorithms. Finally, Section 4.4 provides the conclusion for this
paper.Chapter 5. Multi-Objective Sink Nodes Localization
5.11
64
Literature Review
This section, focus on other researches have proposed for localization of sensor node
in wireless sensor network. In [? ], the position based algorithms as deterministic and
randomized using proposed model called a MANET by a unit disk graph is presented
where two nodes are connected if and only if their Euclidean distance is at most the
transmission range. The localized energy aware routing algorithms, where each node
forwards the routing packets based only on the position or geographic coordinates of
itself, its neighboring nodes, and the destination. But in this work, to choose the position
of sink node in any location in the network in order to minimize energy consumption
and extending lifetime of the network.
Some of the researches focus on WSNs with a single static sink node. If the sensor nodes
are uniformly deployed in a regular geometric region, such as a circular region or a rect-
angular region, the sink node will be placed at the center of the region. Most researches
and simulations were carried out based on this placement strategy. Efrat et al. [? ] and
Jun and Hubaux [? ] proposed the P-Median Problem (PMP)model to determine the
sink node placement, which was proved to be non-deterministic polynomial-time hard
(NP-hard). Jun, L. [? ] has proved that the center of the circle is the optimal position for
a base station in WSNs, but the conclusion is only suitable for the uniform deployment
of nodes. Bogdanov proposed in [? ], the sink node position was chosen to maximize
the weight of data flows to reduce the energy consumption. In work [? ] focuses on
finding the optimal sink node position with respect to relay nodes in order to prolong
the WSN lifetime. An algorithm based on particle swarm optimization (PSO) is used
to find the best position, and some of the researches on lifetime optimization algorithm
with fixed nodes for WSNs such as in paper [? ] proposes an ant colony optimization
approach for maximizing the lifetime of heterogeneous wireless sensor networks, in
[? ] constructs optimal clustering architecture and designs energy-aware cluster-head
rotation and routing protocol to maximize network lifetime.
Heinzehnan et al. proposed to optimize sink node position in [57] through experimental
results that the sensor nodes are far from a sink node drain their energy faster than otherChapter 5. Multi-Objective Sink Nodes Localization
65
nodes in the sensor network. Rahman M.N., Matin M.A.[? ] proposed method to find
the optimal sink node position with respect to relay nodes in order to prolong the WSN
lifetime based on particle swarm optimization (PSO) Multi-objective optimization algo-
rithms MOO used to solve different optimization problems relating to WSNs and their
general application in various fields. An overview of theory and methods of evolution-
ary multi-objective optimization are presented in paper [? ], That clarify basic principles
of multi-objective optimization and evolutionary algorithms, and various concepts al-
gorithmic namely, fitness assignment, eliticism and diversity assurances. A survey of
evolutionary multi-objective algorithms applied to different engineering application is
provided in [? ]. Evolutionary computing (EC) algorithms search the space by utilizing
a set of search operators that contact in a social way to achieve the optimal solution
[31]. Chun-Wei Tsai et al. in [? ] proposed a high-performance NSGA-II algorithm
for solving multi-objective optimization problems that leverage the strengths of firefly
algorithm. This is also inspired by non-dominated sorting. Some of the researchers
introduced strategies placement of sink node that proposed by Chen and Li [? ] which
contain the energy-oriented and lifetime oriented strategies in both the single-hop and
multiple-hop WSNs. The two strategies adopted a routing cost based Ant routing algo-
rithm. According to their conclusion, the lifetime-oriented strategy had outperformed
the energy-oriented strategy in terms of networks lifetime such as, and Hou et al. in [? ]
developed an efficient polynomial-time heuristic algorithm (SPINDS), which attempted
to increase the network lifetime by iteratively moving a relay node to another enhanced
location Other works focused on multiple sink nodes placement in WSNs such as this
work [? ] have proposed an approach to finding positions of multiple stationary sink
nodes. Sensor nodes allow communicating with one or multiple sinks through multiple
paths in order to improve the network lifetime. Oyman, E.I., Ersoy [? ], finding the
optimal placement for a given number of sinks is equivalent to the clustering problem
and should be solved using a clustering algorithm, and other works focus on single
sink node such as in [55], have proposed PSO to choose the optimal sink node location
within a deployment area, and [? ] using CSO to choose best position of sink node.
In the other hand, this paper proves that proposed MOGOA choose the best location of
sink node in deployment area with low energy consumption.Chapter 5. Multi-Objective Sink Nodes Localization
5.12 Preliminaries
5.12.1 Topology Control
66
The objective of topology control protocol (TC) [33] is to minimize energy consump-
tion to prolong the lifetime of the topology control network and maintaining its con-
nectivity. Topology control composes of two main phases, topology construction, and
topology maintenance. The first topology construction is responsible for construct a
reduced topology of active nodes while reducing nodes’ transmission power or turning
off some nodes. The topology maintenance is responsible for periodically repairing
the previously constructed topology with the collaboration of formerly inactive nodes,
issues of topology control in WSNs are coverage and connectivity, first coverage cat-
egorized into a blanket, barrier and sweep coverage, second connectivity categorized
into temporal and spatial control. TC protocols techniques based on reducing the trans-
mission power of sensors to remove unnecessary interconnected links [33]. Although
this reduction in links prolongs the lifetime of the network, this strategy does not pre-
vent the transmission of redundant information when several nodes are close to each
other. In paper [46] establish a communication hierarchy between nodes by turning off
redundant and unnecessary nodes for future usage. The reduces topology is built by
activating the minimum number of nodes that can provide a complete communication
coverage for the network connected dominating set (CDS) problem [? ]. The A3 al-
gorithm [45] provides a solution for establishing a minimum CDS through based on a
weighted distance-energy-based metric. However, this may not be enough to establish
a close to optimal CDS since it works with a number of restriction parameter; once of
them is the assumption of the centrality of the sink node location within deployment
area.
5.12.2
Network Model
Assume that in this paper there is only one static sink node in the network and there
are sensor nodes have the same data generation rate are deployed randomly in a convexChapter 5. Multi-Objective Sink Nodes Localization
67
region R, and also assume that the deployment of sensor node meets both the coverage
and the connectivity requirements of the networks. the sink node is far away from the
nodes, the sensor nodes are able to sense data and distribute it to the sink node.
Assume wireless sensor network with a set of sensing nodes and single sink node. Both
are distributed randomly and uniformly in a given region R = L × L, where L is the side
length. The sensing nodes have limited memory, bandwidth, and different energy. The
sink node has memory and bandwidth, the base station is far away from the nodes, but
it is connected with a set of sensor nodes. The sensor nodes are able to sense data and
distribute it to the sink node.
This paper consider the following assumptions about the sensor network model N: Let
N = {n 1 , ..., n k } be a set of sensor nodes that are distributed randomly and uniformly in
a given region R. All sensor nodes have the same capabilities such as sensing range and
limited memory but different of power energy. Assume N AN = {n 1 AN , ..., n kAN } be set of
active the node in network.
And assume that no node has any global information, e.g., the total number of nodes
n, and k is the maximal number of neighbors in the network. Assume that each node
knows its neighbors. Let N(u) denote the set of neighbors of u. We will refer to the
number of neighbors of u as the node degree of u, and denote it by η(u) = |N(u)|.
Assume that there is only one static sink node in the networks and the sensors with the
same data except to different in energy for each sensor node that are deployed randomly
in a convex region R . Assume that the distribution of sensors meets both the coverage
and the connectivity requirements. The network lifetime is defined as the time when the
first node fails. The network is divided into clusters (sub-regions). Every cluster region
is identified by a sensor node s i , which exists in this cluster. Hence the sensor node is
also called the cluster head. Every sensor node will accept the incoming packets with
probability one and will update its buffer if the flag is set to one.Chapter 5. Multi-Objective Sink Nodes Localization
5.12.3
68
Multi-Objective Optimization
Multi-objective optimization problems are created to solve two or more objectives which
in conflict each other. Steps of multi-objective optimization (MOO) to overcome a num-
ber of conflicting objectives simultaneously, there is an External Archive (EA) is created
to keep a historical record of the non-dominated vectors found along the search process.
In the initialization phase, initialize the external archive. After initializing the solutions
and calculating the value of every solution they are sorted based on non-domination,
each solution is compared with other solutions in the population to find which one is the
non-dominated solution. Then put all non-dominated solutions that considered Pareto
front set into the external archive. The single-objective optimization that contains only
one solution as the global optimum which is considered in contrast multi-objectives
that contain a set of non-dominated solutions should be found in order to get a good
approximation to the Pareto front (PF) [? ] that Pareto optimal (PO) solutions consist of
solutions that are not dominated by any other solutions. A solution X is said to dominate
Y if X is better or equal to Y in all attributes. Secondly, even if an algorithm can find
solution points on the Pareto front, there is no guarantee that multiple Pareto points will
distribute along the front uniformly, often they do not. Thirdly, algorithms work well for
single objective optimization usually do not directly work for multi-objective problems.
Formulating as a multi-objective problem is necessary in some cases, especially when
the problem involves more than one objective functions and several constraints. The
objective functions are typically conflicting; the task of MOGOA is to find a tradeoff
between the conflicting objectives. Unlike single objective problem optimization, the
results of MOO are usually a set of solutions.
→
−
→
−
The point X ∗ ∈ Ω is an optimal of Pareto if, for all X ∈ Ω and g = 1, 2, ..., k either,
→
−
→
−
∀i g( f i ( X ) = f i ( X ∗ ))
,
or there is at least one i ∈ g such that :
→
−
→
−
f i ( X ) ≥ f i ( X ∗ )
The general multi-objective evolutionary optimization problem (MOEP) [? ], can be
→
−
formulated as follow; finding the vector X ∗ = [x 1 ∗ , x 2 ∗ , ..., x n ∗ ] T that satisfies the n inequal-
→
−
→
−
ity constraints: q i ( X ) ≥ 0 i = 1, 2, ..., n the equality constraints w i ( X ) = 0 i = 1, 2, ..., pChapter 5. Multi-Objective Sink Nodes Localization
69
and optimizes.
→
− →
−
→
−
→
−
→
−
f ( X ) = [ f 1 ( X ), f 2 ( X ), ..., f k ( X )] T
Grasshopper optimization is a popular meta-heuristic that is particularly well-suited for
this class of problems. Traditional GOA is customized to accommodate multi-objective
problems by using specialized fitness functions, introducing methods to promote so-
lution diversity, and other approaches. MOGOA is done based on decomposition by
applying non-dominated Pareto Optimal. MOO problem is decomposed into a number
of single objective subproblems and they are optimized concurrently.
5.12.4
Grasshopper Optimization Algorithm (GOA)
Grasshopper is considered the type of insects, they are considered a pest due to their
damage to crop production and agriculture. The phases of grasshoppers composed of
egg, nymph, and adult. Grasshopper Optimization Algorithm (GOA) is a new nature-
inspired algorithm that proposed by Mirjalili et al. [? ] that divide the search process
into two tendencies: exploration and exploitation. In exploration, the search agents
are encouraged to move abruptly, while they tend to move locally during exploitation.
These two functions, as well as target seeking, are performed by grasshoppers naturally.
Therefore, if we find a way to mathematically model this behavior. The mathematical
model for the swarming behavior of grasshoppers is presented as follows
X i = S i + G i + A i
(5.14)
Where X i is the position of grasshopper, S i , G i andA i refer to social interaction, the grav-
ity force on the i-th grasshopper and the wind advection respectively.
Note that to provide random behaviour the equation can be written as X i = r 1 S i + r 2 G i +
r 3 A i where r 1 , r 2 , andr 3 are random numbers in [0,1].Chapter 5. Multi-Objective Sink Nodes Localization
N
S i =
70
0
(5.15)
s d i j d i j
∑
i = 1
j 6 = i
Where N is the total number of d i j refers to the distance between the i-th and the j-th
grasshopper, and s is the strength of social forces
d i j = |x j − x i | (5.16)
x j − x i
d i j (5.17)
0
d i j =
S function is defined as s(r) = f e
−r
1
− e −r where f indicates the intensity of attraction
and l is the attractive length scale. the parameters l and f change comfort zone, attrac-
tion region, and repulsion region significantly. It should be noted that the attraction or
repulsion regions are very small for some values ( l = 1.0 or f = 1.0 for instance). From
all these values we have chosen l = 1.5 and f = 0.5 .
The G component in Eq.5.14 is calculated as follows:
0
0
G i = −ge g where g is the gravitational constant and e g shows a unity vector towards
the centre of earth.
The A component in Eq.5.14 is calculated as follows:
0
0
A i = ue w where u is a constant drift and e w is a unity vector in the direction of wind.
After substitute components in equation 5.14
N
X i =
∑
s x j − x i
x j − x i
0
0
−g e g + u e w
d i j
(5.18)
i = 1
j 6 = i
modified version of this equation is proposed as follows to solve optimization problems:Chapter 5. Multi-Objective Sink Nodes Localization

71







 N

x
−
x
0
ub
−
lb

j
i 
d
d
X i = c  ∑ c
s|x dj − x i d |
 + T d

2
d i j 


 i = 1



j 6 = i
(5.19)
The first c from the left is very similar to the inertial weight (w ) in PSO. It reduces the
movements of grasshoppers around the target. In other words, this parameter balances
exploration and exploitation of the entire swarm around the target.
The second c decreases the attraction zone, comfort zone, and repulsion zone between
grasshoppers. Considering the component c
ub d −lb d
s|x dj − x i d |
2
in
The coefficient c reduces the comfort zone proportional to the number of iterations and
is calculated as follows:
c = c max − l
c max − c min
L
(5.20)
where cmax is the maximum value, cmin is the minimum value, l indicates the current
iteration, and L is the maximum number of iterations. In this work, we use 1 and
0.00001 for cmax and cmin respectively
5.13
The proposed MOGOA
In order to propose the multi-objective version of the GOA algorithm, MOGOA should
follow the same search behaviour to be considered as an extended version of the GOA
algorithm. In this paper apply the GOA strategy for solving multi-objective optimiza-
tion problems, it is obvious that the original scheme has to be modified, the solution set
of a problem with multiple objectives does not consists of a single solution. Instead,
in multi-objective optimization, proposed algorithm aims to find a set of different solu-
tions that called Pareto optimal (PO) set. Multi-objective optimization is concerned withChapter 5. Multi-Objective Sink Nodes Localization
72
optimization problems. For such problems, there is no single solution, which simulta-
neously optimizes each objective. There are many of Pareto Optimal (PO) solutions.
A solution is called (PO). While solving multi-objective optimization problems, the
goal is to find a set of PO solutions, and/or choose the trade-offs in satisfying different
objectives.
According to the concept of multi-objective optimization, the external archive updated
at each iteration, new solutions enter the external archive. In each solution compared
with every non-dominated solution in the external archive to choose new solution should
stay in the archive. As the computational time is directly proportional to the number of
comparisons, the external archive (EA) that save non-dominated Pareto optimal (PO)
solutions and should be limited. Finally, if the number of non-dominated solutions ex-
ceeds the allocated size of EA. The Multi-Objective Evolutionary Algorithms (MOEAs)
found to be very successful to solve multi-objective optimization problems. Some of
researches use many of optimization to solve these multi-objective problems such as
Multi-Objective Cuckoo Search Optimization (MOCSO), Multi-objective gray-wolf op-
timization (MOGWO) [? ], [? ] respectively and other algorithms, the new proposed
algorithm that called multi-objective Grasshopper optimization MOGOA which is pre-
cisely the approach adopted in the work reported in this paper. The flowchart of an
MOGOA is presented in Figure 5.16 and the detailed Pseudo code of the MOGOA are
illustrated in Algorithm 4.
Considering the multi-objective optimization problem as a minimization problem, it can
be described in mathematical terms as follows:
min[ f 1 (x), f 1 (x), ..., f n (x), n > 1 and x ∈ X] Where f is a scalar function and X is the
(implicit) set of constraints that can be defined as X = {x ∗ ∈ R m : h(x) = 0g(x) ≥ 0}m
Fundamentally, a vector x ∗ ∈ Xis said to be Pareto optimal for the problem if either all
other vectors x ∈ X have a higher value for at least one of the fitness function fi, with i =
1, ...,n, or have the same value for all the objective functions. The image of all the Pareto
solutions is called Pareto front. The points on the Pareto front are called non-dominated
points and its shape indicates the nature of the trade-off between objective functionsChapter 5. Multi-Objective Sink Nodes Localization
73
F IGURE 5.16: Schematic flowchart of MOGOA.
During implementing proposed algorithm using the following equations 5.21 and 5.22
to compute the fitness value (g i ) that contain many objectives for each grasshopper g i :
f (g 1 ) =∝ 1
N(g)
+ ∝ 2
Σ ni=1 E(g i )
f (g 2 ) =∝ 3
N AN
N
d g
(5.21)
(5.22)
where N(g i ) is the number of total number of neighbor nodes for node g i in the network,
and where ∝ 1 , ∝ 2 , and ∝ 3 are random numbers ranged in [0, 1]. Assume the parameter
setting of is ∝ 1 = 0.2, ∝ 2 = 0.5, ∝ 3 = 0.7, N AN refers to number of active nodes, N total
number of nodes and d g is the distance between the position of the grasshopper g and
the center of the deployment area.Chapter 5. Multi-Objective Sink Nodes Localization
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
74
Input: A graph represents the nodes and their neighbors with energies
Output: The final Network with location of sink node
Initialize the grasshopper population X i (i = 1, 2, ..., n).
Initialize c max , c min .
Calculate the fitness function for each search agent
Find the non-dominated (PO)solutions and initialized EA with them
T = SelectLeader(EA) is best search agent
Exclude leader T from EA temporarily to avoid selecting the same leader
Add back leader to EA
Initializing start of iteration l=1 and initialize Maximum of iteration Max iter .
while t <= Max iter do
11:
12:
13:
14:
15:
16:
17:
end
Update c using Eq.
For each search agent
Normalize distances between grasshoppers
Update position of grasshopper
Calculate the fitness function for each search agent
Find the non-dominated solutions
Update EA with respect to non-dominated solutions
if EA is full then
18:
end
Run the grid mechanism to omit one of the current archive members
19: Add the new solution to EA
20: EndIf
if any of the new added solutions to EA is located outside the hypercubes
then
21:
22:
23:
24:
25:
26:
27:
28:
29:
end
Update the grids to cover the new solution(s)
EndIf
End for each
T=SelectLeader(EA)
Exclude T from EA temporarily to avoid selecting the same leader
Add back leader to the archive
t=t+1
EndWhile
Return archive (contains pareto optimal solution of location of sink node)
Algorithm 4: Pseudo code of the MOGOA.
Although a number of researches assume that the sink node location deployed in the
center point of the deployment area according to topology construction protocols such
as A3 and A3COV [45] [46] respectively. This assumption for determining sink node
location is not ideal. So, it should optimize the position of sink node in order to reduce
energy consumption for the network to prolong network lifetime. Grasshopper positionChapter 5. Multi-Objective Sink Nodes Localization
75
−
represent position of candidate sink node that is represented by →
g = {g 1 , ..., g n } in 2D
(Two-dimensional) space which is equivalent to the nodes’ positions (posi(t) = Xi(t),
Yi(t)), the proposed algorithm assume the random deployment of a number of search
agents (Grasshopper) (g = {g 1 , g 2 , ..., g m }) , m refers to number of search agents, the
final result obtains the nearest best sink node position in network. Algorithm 1 depicts
the MOGOA-based Sink Node Localization Algorithm. After a number of predefined
iterations, the algorithm gets the nearest node to the search agent as sink node to be used
within the final constructed topology. After choosing location of sink node in network
used Prims shortest path algorithm to make transmission path from sink node to the rest
of sensor nodes.
A tree is a type of graph theory where there is a top most node called root and other
nodes are spanned about the root. Any node at depth d-1 is apparent to a node at depth
d if both are connected. In WSN problem, the sink node is the root. Other sensor nodes
are connected to the sink as shown in Figure 5.17. Here we have used Prim’s algorithm
to find a minimum path for transmission of data from the sensor node i to the sink node
(SK). From the sensor node arrangement, a graph G is created containing all the sensor
nodes. An adjacency matrix is created which contains the information which nodes in
the graph G is connected.
An edge (u, v) can belong to G only if the distance between the nodes u and v ∈ G
is shorter than the maximum communicating radius range and applied Prims shortest
path algorithm from each of the sensor nodes to the sink node. The output returned
by the algorithm is the cost of the path, which is utilized in calculating the cost of the
minimum path from a sensor node i to the sink node (SK) and the sequence of nodes
in the path, which can help us to determine the number of sensor nodes from which the
nodes receives data and transfer it to the SK in. Hence using graph theory helps us to
reduce the huge computational effort in formulating the Fitness function functions.Chapter 5. Multi-Objective Sink Nodes Localization
76
F IGURE 5.17: the structure of tree graph.
5.14
Experimental Results and Discussion
In this section, the results of proposed MOGOA-based algorithm was coded using MAT-
LAB to choose the best position of sink node. Compare MOGOA with two different
algorithms: PSO, CSO in the same network. The simulation parameters in Table 1 that
were adjusted for the experimental scenarios. The nodes within the simulation are as-
sumed to mimic the characteristics of Crossbows Mica Mote sensors with the energy
model defined in [45].
T ABLE 5.11: Simulation parameter.
Parameter
Value
Deployment area
600m * 600m
Number of nodes
200,400,600,800,1000
Sensor node model
Mica Mote
Node communication range 100m
Node sensing
range 20m
Node placement
Uniform
Node energy
Uniform
Max energy
2000 (mA-h )
∝ 1
0.1
∝ 2
0.7
∝ 3
0.3
Proposed algorithm MOGOA is compared with a sink node location algorithm based
on the Particle Swarm Optimization (PSO) approach [55] and Cat Swarm Optimization
(CSO) [? ]. This algorithm aims to produce a network with minimal energy consump-
tion. The result of the experiment is optimal for deploying the sink node in the WSNs.Chapter 5. Multi-Objective Sink Nodes Localization
77
Table 5.12 shows the total energy consumption for three algorithms in the same net-
work scenarios. After choosing sink node location to reconstruct network according to
sink node positions for reducing energy consumption for network to extending network
lifetime
In Figure 5.18 Obtain location of sink node for 200 nodes in network and after deter-
mining the position of sink node in the network using proposed algorithm MOGOA by
the fitness function, use the greedy algorithm [? ] [? ] with minimum spanning tree
to create the data transmission paths the sink node localization problem is also solved
by MOGOA approach with the transmission paths built by the greedy algorithm for
the compare. The proposed algorithm is tested with 5 different numbers of the sensor
node environments. The results are compared to the power consumption of the sink
node allocated by CSO and PSO approach. The experimental results indicate that pro-
posed algorithm presents better efficiency on reducing the total power consumption in
the whole WSNs.
T ABLE 5.12: Comparison of Energy Consumption for three algorithms MOGOA,
CSO and PSO.
N MOGOA CSO PSO
200
400
600
800
1000 20023
37102
57735
69512
81654 20865
39320
58840
71329
83455 21084
41217
60654
73849
84987
In Figure5.19 shows the communication energy consumption of MOGOA, CSO, and
PSO with varying number of nodes. This may be explained by the chosen fitness func-
tion of the proposed algorithm that enforces to place the sink node within the region
that contains the highest number of sensor nodes. The proposed optimization algo-
rithm saved approximately 5.6% of the spent energy over another algorithm CSO, PSO
through the initial topology reduction phase. The main idea of such saving energy for
the network through choose the nearest best location of sink node and reduce transmis-
sion path from the sink node to all sensor nodes in the whole network large number of
sensors around the sink node those will be marked as children to that node.Chapter 5. Multi-Objective Sink Nodes Localization
78
( A ) MOGOA.
( B ) CSO.
( C ) PSO.
F IGURE 5.18: Location of sink node in network size 200.
F IGURE 5.19: Comparison of energy consumption.
In figure5.20 depicts that convergence rate for fitness function according to a numberChapter 5. Multi-Objective Sink Nodes Localization
79
F IGURE 5.20: : The comparison of convergence rate between MOGOA, CSO, and
PSO.
of iteration. An observation in results of sink node location and energy consumption
for network When the number of nodes is increased, MOGOA finds more optimal sink
node location than CSO and PSO does. This result may be attributed to the process of
MOGOA of determining the moving directions and distances of the nodes by building
the transmission path from the sink node to others node in the network using Transmis-
sion Path Construction Using Greedy Algorithms such as Prim’s Minimum Spanning
Tree (MST) algoritm. When the number of the nodes is extremely low, the difference in
the results between the three algorithms is not evident. Therefore, when increased num-
ber of network size observe proposed algorithm reduce energy comparing with other
algorithms. The goal is to improve network lifetime by reducing energy consumption
through deploy sink node position in best nearest location, MOGOA can still provide
network lifetime that is slightly higher than CSO and PSO.
5.14.1
The Localization Errors
The localization error (LocErr) is generally related to the node communication radius R.
The aim of localization errors are defined to evaluate the localization performance of the
proposed algorithm compared with another algorithm CSO and PSO. The localization
error defined by formula 5.23, which is used to evaluate the performance of each node
being estimated, which is further applied to evaluate the performance of all the nodes
being estimated:Chapter 5. Multi-Objective Sink Nodes Localization
80
p 0
0
(x − x) 2 + (y − y) 2
× 100%
LocalizationErr =
R
0
(5.23)
0
Where (x , y ) are the sink node estimated coordinates, (x, y) are the sink node real
coordinates and R refers to communication range.
T ABLE 5.13: Localization errors with a different node number.
N
200
400
600
800
1000
MOGOA 17.6% 13.4% 17.1% 16.3% 12.8%
CSO
19.3% 14.2% 17.5% 17.4% 14.1%
PSO
20.7% 16.3% 17.7% 18.0% 17.7%
F IGURE 5.21: Localization errors with different network size.
Reducing of localization error is considered one of the goals of proposed algorithm. In
Table 5.13 depicts Localization Error when network size is varied. In this simulation,
analyze the effect of change of a number of network size on the localization error.
Localization error is estimated on the proposed algorithm MOGOA by taking different
values of network size. Table 5.13 shows values of localization error. Figure 5.21 show
that estimation error decreases as the number of network size increases. As it can also
be observed that proposed algorithm has smaller location error in general with respect
to a different number of network size.Chapter 5. Multi-Objective Sink Nodes Localization
5.14.2
81
Evaluation criteria
In this paper, the WSNs datasets consist of network sizes (N) from 200 to 1000 nodes.
The algorithm is run repeatedly for M = 100 times for statistical significance of the re-
sults. The following measures are used to validate and evaluate the proposed algorithm:
1. Mean fitness function is the average of the fitness function value obtained from
running the algorithm M times. The Mean fitness function is calculated as shown in
equation 5.24.
Mean =
∑ M
i=1 f i
M
(5.24)
where f i is the best fitness value obtained at run i.
2. Best fitness function is the minimum of the fitness function value obtained from
running the algorithm M times. The Best fitness function is calculated as shown in
equation 5.25.
M
Best = min f i
i=1
(5.25)
where f i is the best fitness value obtained at run i.
3. Worst fitness function is the maximum of the fitness function value obtained from
running the algorithm M times. The Worst fitness function is calculated by Equation
5.26.
M
Worst = max f i
i=1
(5.26)
where f i is the best fitness value obtained at run i.
4. Standard deviation gives the variation of the fitness function value obtained from
running the algorithm M times. It is an indicator of the stability and robustness of
the algorithm. Larger values of standard deviation would suggest wandering results
whereas smaller value suggests the algorithm converges to the same value most of the
times. The Standard deviation is calculated as shown in the equation 5.27.Chapter 5. Multi-Objective Sink Nodes Localization
r
Std =
1
Σ M ( f i − mean) 2
M − 1 i=1
82
(5.27)
where f i is the best fitness value obtained at run i.
4 . Average Time for 100 iterations in each dataset of nodes: Average time gives the
variation of the fitness function value obtained from running the proposed algorithm
during implementing in MATLAB
5.14.3
Discussion
T ABLE 5.14: summary of the experimental results.
MOGOA
CSO
PSO
Mean Best
Worst Std
Mean Best
Worst Std
Mean Best
Worst S
200 4.0028E- 4.0028E- 1.4303E- 2.118E- 4.2037E- 4.2037E- 1.2404E- 2.045E- 4.6040E- 4.6040E- 1.3604E- 2
02
02
01
03
02
02
01
03
02
02
01
0
400 2.0435E- 2.0435E- 1.7443E- 1.488E- 2.3905E- 2.3905E- 1.8690E- 2.226E- 2.9435E- 2.9435E- 2.0943E- 5
02
02
01
04
02
02
01
04
02
02
01
0
600 1.4722E- 1.4722E- 2.1372E- 4.254E- 1.7922E- 1.7922E- 2.4692E- 3.787E- 1.6722E- 1.6722E- 2.6372E- 6
02
02
01
04
02
02
01
04
02
02
01
0
800 1.0649E- 1.0649E- 1.4665E- 8.347E- 1.3649E- 1.3649E- 1.8365E- 8.081E- 1.5649E- 1.5649E- 1.9765E- 7
02
02
01
04
02
02
01
04
02
02
01
0
1000 8.9371E- 8.9371E- 9.7937E- 1.007E- 1.0937E- 1.0937E- 1.0794E- 1.081E- 9.9371E- 9.9371E- 1.3694E- 1
03
03
02
03
02
02
01
03
03
03
01
0
Avg 1.8954E- 1.8954E- 1.5515E- 9.067E- 2.1690E- 2.1690E- 1.6989E- 9.070E- 2.3556E- 2.3556E- 1.8876E- 1
02
02
01
04
02
02
01
04
02
02
01
0
N
F IGURE 5.22: Comparison Results of evaluation criteria.Chapter 5. Multi-Objective Sink Nodes Localization
83
Table 5.14 depicts the average testing performance of the different optimizers over the
different data set. The performance of MOGOA is better than CSO and PSO for all the
used fitness functions over the test data sets. By comparing the performance of different
fitness functions used; In Table 5.14 that outlines the mean, best, worst and Standard
deviation fitness function obtained over M runs and is calculated using Equations 5.24,
5.25, 5.26 and 5.27 respectively. These results of testing performance for different
optimizers obtains the best performance is achieved by the proposed MOGOA proving
its ability to choose the nearest best position of sink node with low energy consumption.
For further effective evaluation of the performance of all the algorithms, graphical anal-
ysis has also been done. The bar graphs of convergence of various evaluation criteria
using MOGOA algorithm and other algorithms CSO and PSO have been shown in Fig-
ure 5.22 which help to analyze the convergence rate of each algorithm more effectively.
All these evaluation criteria have been taken on 100 iterations to clearly notice and
analyze the convergence of all the algorithms.
T ABLE 5.15: AverageTime per second (s).
N MOGOA CSO PSO
200
400
600
800
1000
Average 2719.75 s
3872.04 s
5106.56 s
5877.38 s
6568.89 s
4828.92 s 3135.41 s
4243.17 s
4953.49 s
5987.13 s
6763.79 s
5016.60 s 2957.64 s
4389.67 s
4876.88 s
6138.47 s
6835.34 s
5039.60 s
F IGURE 5.23: Average Time for 3 algorithms per second (s).Chapter 5. Multi-Objective Sink Nodes Localization
84
Average Time for three algorithms obtain in Table 5.15 and Figure 5.23 that clarify
run time of proposed algorithm is better than compared to the rest of the other algo-
rithms that takes less time than others when finding nearest best position of sink node
in network with low energy consumption.
In this experiment in Figure 5.24 was performed on the 2D version of fitness function
using 5 datasets from the network. The main objective of this experiment was to monitor
the behavior of the MOGOA qualitatively. Five diagrams have been drawn for each
dataset of the nodes using same fitness function in Figure5.24 in addition to the shape
of the fitness function. These diagrams are:
Search history: this diagram show location history of sensor nodes (grasshoppers) dur-
ing optimization.
Attraction/repulsion rates: this diagram shows the number of times that all artificial
grasshoppers attracted or repelled each other during optimization.
The trajectory of the first grasshopper in the first dimension: this diagram shows the
value of the first variable of the first grasshopper in each iteration.
Average fitness: this diagram indicates the average fitness function of all nodes in each
iteration.
Convergence curve: this diagram shows the fitness function of the best solutions ob-
tained so far (target) in each iteration.
In Figure 5.24 shows that the repulsion rate is lower. These results demonstrate that
MOGOA efficiently balances exploration and exploitation to approximate the global
optimum and in this figure, depicts that the trajectory of the grasshoppers exhibits large,
abrupt changes in the initial steps of optimization. This is due to the high repulsion rate
which causes exploration of the search space by MOGOA, which is due to the comfort
zone and attraction forces between the grasshoppers. This guarantees that the proposed
MOGOA algorithm explores and exploits the search space and converges towards a
point eventually. To confirm results of this behavior in improving the fitness function
of grasshoppers, average fitness of grasshoppers and convergence curves are providedChapter 5. Multi-Objective Sink Nodes Localization
85
in Figure5.24. The curves clearly show descending behavior on all of the datasets.
This proves that MOGOA improves the accuracy of the approximated optimum over
the course of iterations.
These tables show that the MOGOA algorithm outperforms the other algorithms with
respect to all of the assessment indicators. This concludes that the grasshopper algo-
rithm is powerful in exploring the search space and the multi-objective grasshopper
swarm optimization algorithm aids in choose nearest best position of sink node with
low energy consumption and reduce localization error compared with other algorithms
CSO and PSO to prolong network’s lifetime.
multi-objective optimization gives a large number of alternative solutions located on
or near the Pareto-optimal front. The shapes of the best Pareto optimal front obtained
by the proposed algorithm 5 datasets are illustrated in Figure 5.25. Inspecting this
figure, it may be observed that MOGOA provide a very good convergence toward all
the true Pareto optimal fronts. The most interesting pattern is that the Pareto optimal
solutions obtained by MOGOA show higher on all datasets. The Pareto-optimal front
can be achieved in order to determine best location of sink node and obtain low power
consumption. The algorithm was proposed to find a trade off between the minimum
energy consumption and maximizing network’s lifetime.
In Table 5.16 presented a brief comparison with the previous related studies. The infor-
mation about the location of single sink node, number of nodes in network, techniques
(methods have been used to choose the number of sink node) and purposes from studies
are reported in previous studies are presented in Table5.16 Consequently, it is clear that
the proposed MOGOA algorithm providing the best performance in comparison with
other algorithms in terms of the position of sink node and energy consumption in order
to maximize the network lifetime.Chapter 5. Multi-Objective Sink Nodes Localization
86
T ABLE 5.16: Comparison MOGOA algorithm with other studies of sink node posi-
tioning approaches.
5.15
Ref Techniques N Remark
[? ] LMID algorithm Very
Small
WSNs 50 nodes Choose position
of base station
(sink node)
[? ] The query-based
WSN Small WSNs 100
nodes offers a signifi-
cant Energy con-
sumption
[? ] (1 )-an optimal
approximation al-
gorithm is based
on several novel
techniques Small WSNs 100
nodes guarantee
(1)-
optimal network
lifetime
[? ] node placement
algorithm Small WSNs 300
nodes single-sink
WSNs,
energy
consumption and
network lifetime
Proposed MOGOA 200:1000 nodes Position single
sink node, save
energy consump-
tion to prolong
network’s
life-
time
Summary
this part represents Grasshopper optimization algorithm to solve a multi-objective prob-
lem that faces localization of sink node, two main objectives, the first objective is to find
the optimal location of the sink node within a topology control protocol and second ob-
jective with low energy consumption for the network to extending network lifetime.
After getting the location of the sink node using proposed MOGOA reconstructs net-
work according to sink node position use the greedy algorithm with minimum span-
ning tree to create the data transmission paths. The proposed optimization algorithm
saved approximately 5.6% of the spent energy over another algorithm CSO, PSO. Also,Chapter 5. Multi-Objective Sink Nodes Localization
87
MOGOA improves the localization error and decrease the convergence rate. Compared
with different swarm localization algorithm CSO and PSO. The experimental results
indicate that proposed algorithm is tested with 5 different datasets of the sensor nodes
environments and presents better efficiency on choosing best location of sink node and
reducing the total power consumption in the whole WSNs comparing with other algo-
rithms CSO and PSO.Chapter 5. Multi-Objective Sink Nodes Localization
( A ) Behavior 200 nodes in 100 iteration.
( B ) Behavior 400 nodes in 100 iteration.
( C ) Behavior 600 nodes in 100 iteration.
( D ) Behavior 800 nodes in 100 iteration.
( E ) Behavior 1000 nodes in 100 iteration.
F IGURE 5.24: Behavior of MOGOA on the 2D benchmark.
88Chapter 5. Multi-Objective Sink Nodes Localization
( A ) Results of pareto front MOGOA on f1 and
f2 for 200 nodes.
( B ) Results of pareto front MOGOA on f1 and
f2 for 400 nodes.
( C ) Results of pareto front MOGOA on f1 and
f2 for 600 nodes.
( D ) Results of pareto front MOGOA on f1 and
f2 for 800 nodes.
( E ) Results of pareto front MOGOA on f1 and
f2 for 1000 nodes.
F IGURE 5.25: Best Pareto optimal front obtained by the proposed multi-objective
89Chapter 6
Conclusion and Future Work
6.1
Conclusion
Discrete group search optimizer (DGSO) is an optimization technique suitable for de-
tecting community structure hidden within undirected single dimensional social net-
works. The locus-based adjacency encoding scheme is adopted to represent a com-
munity structure. This encoding scheme has a major advantage that, the number of
communities is not required to be specified as a prior setting, thus it enables the algo-
rithm to detect the number of communities automatically. Experiments in real world
networks showed the ability of this method to correctly detect community structures
based on the quality function used (modularity). A comparison with other recently
proposed methods shows that DGSO is very competitive with such methods.
Discrete group search optimizer for community detection in multidimensional social
networks (DGSO-MDNet), is an optimization technique suitable for detecting commu-
nity structure hidden within undirected multidimensional social networks. This algo-
rithm is extended from DGSO by performing a set of modifications in the initialization
phase, and the objective function used. Experiments on synthetic and real world net-
works showed the ability of these method to correctly detect community structures that
maximize modularity across all network dimensions without any prior knowledge about
90Chapter 6. Conclusion
91
the number of communities. This algorithm is also unrestricted by the number of di-
mensions in the network.
Genetic algorithm is an optimization technique proved to be efficient by many re-
searches over the past years. GA works effectively for the community detection in mul-
tidimensional social networks problem, in single-objective and multi-objective cases.
Many fitness functions have been proposed to capture the intuition of multidimen-
sional communities which has been used in the literature; hence single-objective GA
was applied with two different objective quality functions in order to evaluate their
performance. Also multi-objective GA was applied to solve the community detection
in multidimensional social networks, as a multi-objective optimization problem. This
multi-objective optimization approach aims to find community structure that simulta-
neously maximizes modularity, as an objective function, over all network dimensions,
where number of objectives needed to be optimized equals the number of dimensions.
This approach exploits the benefits of these objectives and discovers the communities
hidden in the network structure by selectively exploring the search space, without the
need to know in advance the exact number of communities. This number is automati-
cally determined by the optimal adjustment of objectives’ values. An interesting aspect
of the multi-objective approach is that it aims to find the optimal community structure
in the presence of trade-offs between all conflicting objectives, so it returns a set of
solutions which are called Pareto-optimal solutions. Each of these solutions satisfies
a different trade-off between all objectives and thus guarantees diverse partitioning of
the network consisting of various number of communities. The locus-based adjacency
encoding scheme is applied again to represent a community structure. Experiments on
synthetic and real world networks showed the ability of GA based method to correctly
detect community structures that maximize modularity across all network dimensions.
These algorithms have the advantage, that it does not need any prior knowledge about
number of communities and unrestricted by the number of network’s dimensions. Also
using multi-objective genetic algorithm, we can detect a shared community structure
taking into account the importance of a certain relation(s), however, this can not be
achieved using the single objective GA and DGSO-MDNet algorithms that returns only
one solution.Chapter 6. Conclusion
92
All algorithms proposed in this work are iterative, improving solution over iterations.
The convergence rate is the speed at which the iterative algorithm approaches its limit.
It worth mentioning that a faster convergence rate does not mean good result, it only
means that the algorithm converges to a specific solution faster. The convergence rate
GA is noticeably faster than convergence rate of DGSO-MDNet algorithm.
6.2
Future Work
To continue this area of research there exist many more improvements and tests that
can be considered for these proposed algorithms. As the size of real world social net-
works increases continuously, increasing scalability of our proposed method will be
investigated in the future. Also we plan to enhance the capabilities of this algorithm
to discover overlapped communities. Also all proposed algorithms assume a static net-
work or snapshot of a social network at specific time, ignoring the fact that real world
social networks naturally evolve over time. This fact affects the nature and figuration
of the community structure hidden within these networks over time. So we also plan to
focus on how to extend algorithms proposed here, or propose new algorithms that can
discover communities in a dynamic social network.Bibliography
[1] Jiliang Tang, Xia Hu, and Huan Liu. Social recommendation: a review. Social
Network Analysis and Mining, 3(4):1113–1133, 2013.
[2] Diana Crane. Invisible colleges; diffusion of knowledge in scientific communities.
1972.
[3] Changjun Fan, Kaiming Xiao, Baoxin Xiu, and Guodong Lv. A fuzzy clustering
algorithm to detect criminals without prior information. In Advances in Social
Networks Analysis and Mining (ASONAM), 2014 IEEE/ACM International Con-
ference, pages 238–243. IEEE, 2014.
[4] Clifford Weinstein, William Campbell, Brian Delaney, and Gerald O’Leary. Mod-
eling and detection techniques for counter-terror social network analysis and intent
recognition. In 2009 IEEE Aerospace conference, pages 1–16. IEEE, 2009.
[5] M Tasgin and H Bingol. Community detection in complex networks using genetic
algorithm. arXiv:cond-mat/0604419, 2006.
[6] Chuan Shi, Cha Zhong, Zhenyu Yan, Yanan Cai, and Bin Wu. A new genetic
algorithm for community detection. Complex Sciences, 5:1298–1309, 2009.
[7] Mark EJ Newman and Michelle Girvan. Finding and evaluating community struc-
ture in networks. Physical review E, 69(2):026113, 2004.
[8] Clara Pizzuti. Ga-net: A genetic algorithm for community detection in social
networks. In Parallel Problem Solving from Nature–PPSN X, pages 1081–1090.
Springer, 2008.
93References
94
[9] Clara Pizzuti. Community detection in social networks with genetic algorithms.
In Proceedings of the 10th annual conference on Genetic and evolutionary com-
putation, pages 1137–1138. ACM, 2008.
[10] Aykut Firat, Sangit Chatterjee, and Mustafa Yilmaz. Genetic clustering of so-
cial networks using random walks. Computational Statistics and Data Analysis,
51:6285–6294, 2007.
[11] Chuan Shi, Cha Zhong, Zhenyu Yan, Yanan Cai, and Bin Wu. A multi-objective
optimization approach for community detection in complex network. pages 1–8,
Barcelona, Spain, 2010.
[12] Clara Pizzuti. A multi-objective genetic algorithm for community detection in
networks. In Tools with Artificial Intelligence, 2009. ICTAI’09. 21st International
Conference, pages 379–386. IEEE, 2009.
[13] Rohan Agrawal. Bi-objective community detection (bocd) in networks using ge-
netic algorithm. In Contemporary Computing, pages 5–15. Springer, 2011.
[14] Kalyanmoy Deb, Amrit Pratap, Sameer Agarwal, and TAMT Meyarivan. A fast
and elitist multiobjective genetic algorithm: Nsga-ii. Evolutionary Computation,
IEEE Transactions, 6(2):182–197, 2002.
[15] David W Corne, Nick R Jerram, Joshua D Knowles, Martin J Oates, et al. Pesa-
ii: Region-based selection in evolutionary multiobjective optimization. In Pro-
ceedings of the Genetic and Evolutionary Computation Conference (GECCO2001.
Citeseer, 2001.
[16] Zeng Yuanyuan, Xiaohua Jia, and He Yanxiang. Energy efficient distributed con-
nected dominating sets construction in wireless sensor networks. In Proceedings
of the 2006 international conference on Wireless communications and mobile com-
puting, pages 797–802. ACM, 2006.
[17] Kevin M Passino. Biomimicry of bacterial foraging for distributed optimization
and control. IEEE control systems, 22(3):52–67, 2002.
[18] Yu Wang. Topology control for wireless sensor networks. pages 113–147, 2008.95
References
[19] Ian F Akyildiz, Weilian Su, Yogesh Sankarasubramaniam, and Erdal Cayirci. A
survey on sensor networks. IEEE Communications magazine, 40(8):102–114,
2002.
[20] Ning Li, Jennifer C Hou, and Lui Sha. Design and analysis of an mst-based
topology control algorithm. IEEE Transactions on Wireless Communications,
4(3):1195–1206, 2005.
[21] Ning Li and Jennifer C Hou. Localized topology control algorithms for het-
erogeneous wireless networks. IEEE/ACM Transactions on Networking (TON),
13(6):1313–1324, 2005.
[22] Russell Eberhart and James Kennedy. A new optimizer using particle swarm the-
ory. In Micro Machine and Human Science, 1995. MHS’95., Proceedings of the
Sixth International Symposium on, pages 39–43. IEEE, 1995.
[23] Habib Mostafaei and Mohammad Reza Meybodi. Maximizing lifetime of target
coverage in wireless sensor networks using learning automata. Wireless Personal
Communications, 71(2):1461–1477, 2013.
[24] Matheswaran Saravanan and Muthusamy Madheswaran.
A hybrid optimized
weighted minimum spanning tree for the shortest intrapath selection in wireless
sensor network. Mathematical Problems in Engineering, 2014, 2014.
[25] Filippo Radicchi, Claudio Castellano, Federico Cecconi, Vittorio Loreto, and
Domenico Parisi.
Defining and identifying communities in networks.
Pro-
ceedings of the National Academy of Sciences of the United States of America,
101(9):2658–2663, 2004.
[26] Vincent D Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefeb-
vre. Fast unfolding of communities in large networks. Journal of Statistical Me-
chanics: Theory and Experiment, 2008(10):P10008, 2008.
[27] Jordi Duch and Alex Arenas. Community detection in complex networks using
extremal optimization. Physical review E, 72(2):027104, 2005.References
96
[28] Jian Liu and Tingzhan Liu. Detecting community structure in complex networks
using simulated annealing with k-means algorithms. Physica A: Statistical Me-
chanics and its Applications, 389(11):2300–2309, 2010.
[29] Ahmed Ibrahem Hafez, Hossam M. Zawbaa, AboulElla Hassanien, and Aly A.
Fahmy. Networks community detection using artificial bee colony swarm opti-
mization. In Proceedings of the Fifth International Conference on Innovations in
Bio-Inspired Computing and Applications IBICA 2014, volume 303 of Advances
in Intelligent Systems and Computing, pages 229–239. Springer International Pub-
lishing, 2014.
[30] Seyedali Mirjalili and Andrew Lewis. The whale optimization algorithm. Ad-
vances in Engineering Software, 95:51–67, 2016.
[31] Aboul Ella Hassanien and Eid Emary. Swarm intelligence: principles, advances,
and applications. CRC Press, 2016.
[32] Mohamed Mostafa M Fouad, Mostafa-Sami M Mostafa, and Ahmed Reda Da-
wood. Sopk: second opportunity pairwise key scheme for topology control proto-
cols. In Intelligent Systems, Modelling and Simulation (ISMS), 2012 Third Inter-
national Conference on, pages 632–638. IEEE, 2012.
[33] Mo Li, Zhenjiang Li, and Athanasios V Vasilakos. A survey on topology con-
trol in wireless sensor networks: Taxonomy, comparative study, and open issues.
Proceedings of the IEEE, 101(12):2538–2557, 2013.
[34] Steve A Borbash and Esther H Jennings. Distributed topology control algorithm
for multihop wireless networks. In Neural Networks, 2002. IJCNN’02. Proceed-
ings of the 2002 International Joint Conference on, volume 1, pages 355–360.
IEEE, 2002.
[35] Martin Burkhart, Pascal Von Rickenbach, Rogert Wattenhofer, and Aaron
Zollinger. Does topology control reduce interference?
In Proceedings of the
5th ACM international symposium on Mobile ad hoc networking and computing,
pages 9–19. ACM, 2004.References
97
[36] Li Li, Joseph Y Halpern, Paramvir Bahl, Yi-Min Wang, and Rogert Wattenhofer.
A cone-based distributed topology-control algorithm for wireless multi-hop net-
works. IEEE/ACM Transactions on Networking (TON), 13(1):147–159, 2005.
[37] Errol L Lloyd, Rui Liu, Madhav V Marathe, Ram Ramanathan, and Sekharipu-
ram S Ravi. Algorithmic aspects of topology control problems for ad hoc net-
works. Mobile Networks and applications, 10(1-2):19–34, 2005.
[38] Paolo Santi. Topology control in wireless ad hoc and sensor networks. ACM
computing surveys (CSUR), 37(2):164–194, 2005.
[39] Limin Hu. Topology control for multihop packet radio networks. IEEE transac-
tions on communications, 41(10):1474–1481, 1993.
[40] Esther Jennings and Clayton Okino. Topology control for efficient information
dissemination in ad-hoc networks. In International Symposium on Performance
Evaluation of Computer and Telecommunication Systems SPECTS, volume 2002,
2002.
[41] Ram Ramanathan and Regina Rosales-Hain. Topology control of multihop wire-
less networks using transmit power adjustment. In INFOCOM 2000. Nineteenth
Annual Joint Conference of the IEEE Computer and Communications Societies.
Proceedings. IEEE, volume 2, pages 404–413. IEEE, 2000.
[42] Alaa Muqattash and Marwan Krunz. A single-channel solution for transmission
power control in wireless ad hoc networks. In Proceedings of the 5th ACM inter-
national symposium on Mobile ad hoc networking and computing, pages 210–221.
ACM, 2004.
[43] Mohammad Z Siam, Marwan Krunz, Alaa Muqattash, and Shuguang Cui. Adap-
tive multi-antenna power control in wireless networks. In Proceedings of the
2006 international conference on Wireless communications and mobile comput-
ing, pages 875–880. ACM, 2006.References
98
[44] Andrew Y Wang and Charles G Sodini. On the energy efficiency of wireless
transceivers. In Communications, 2006. ICC’06. IEEE International Conference
on, volume 8, pages 3783–3788. IEEE, 2006.
[45] Pedro M Wightman and Miguel A Labrador. A3: A topology construction algo-
rithm for wireless sensor networks. In Global Telecommunications Conference,
2008. IEEE GLOBECOM 2008. IEEE, pages 1–6. IEEE, 2008.
[46] Pedro M Wightman and Miguel A Labrador. A3cov: a new topology construction
protocol for connected area coverage in wsn. In Wireless Communications and
Networking Conference (WCNC), 2011 IEEE, pages 522–527. IEEE, 2011.
[47] Eid Emary, Hossam M Zawbaa, and Aboul Ella Hassanien. Binary grey wolf
optimization approaches for feature selection. Neurocomputing, 172:371–381,
2016.
[48] Miguel A Labrador and Pedro M Wightman. Topology Control in Wireless Sensor
Networks: with a companion simulation tool for teaching and research. Springer
Science & Business Media, 2009.
[49] Yanli Cai, Minglu Li, Wei Shu, and Min-You Wu. Acos: An area-based collabo-
rative sleeping protocol for wireless sensor networks. Ad Hoc & Sensor Wireless
Networks, 3(1):77–97, 2007.
[50] Zixiang Wang, Senlin Zhang, Meikang Qiu, and Meiqin Liu. Scheduling active
nodes of clusters in wsns to minimize energy.
[51] S Balaji, Y Harold Robinson, and M Rajaram. Scsbe: Secured cluster and sleep
based energy-efficient sensory data collection with mobile sinks. Circuits and
Systems, 7(08):1992, 2016.
[52] Nooshin Nokhanji, Zurina Mohd Hanapi, Shamala Subramaniam, and Mo-
hamad Afendee Mohamed. A scheduled activity energy aware distributed clus-
tering algorithm for wireless sensor networks with nonuniform node distribution.
International Journal of Distributed Sensor Networks, 2014.References
99
[53] Xiaoyu Chu and Harish Sethu. An energy balanced dynamic topology control
algorithm for improved network lifetime. In Wireless and Mobile Computing,
Networking and Communications (WiMob), 2014 IEEE 10th International Con-
ference on, pages 556–561. IEEE, 2014.
[54] Shanmugasundaram Thilagavathi and Bhavani Gnanasambandan Geetha. Energy
aware swarm optimization with intercluster search for wireless sensor network.
The Scientific World Journal, 2015, 2015.
[55] Mohamed Mostafa Fouad, Vaclav Snasel, and Aboul Ella Hassanien. Energy-
aware sink node localization algorithm for wireless sensor networks. International
Journal of Distributed Sensor Networks, 11(7):810356, 2015.
[56] Benjie Chen, Kyle Jamieson, Hari Balakrishnan, and Robert Morris. Span: An
energy-efficient coordination algorithm for topology maintenance in ad hoc wire-
less networks. Wireless networks, 8(5):481–494, 2002.
[57] Wendi Rabiner Heinzelman, Anantha Chandrakasan, and Hari Balakrishnan.
Energy-efficient communication protocol for wireless microsensor networks. In
System sciences, 2000. Proceedings of the 33rd annual Hawaii international con-
ference on, pages 10–pp. IEEE, 2000.