=Paper=
{{Paper
|id=Vol-3283/Paper21
|storemode=property
|title=Hybrid Optimization Method for WSN Data Collection using Mobile Sink based on TSP Approach
|pdfUrl=https://ceur-ws.org/Vol-3283/Paper98.pdf
|volume=Vol-3283
|authors=Vishnuvarthan Rajagopal,Bhanumathi Velusamy
|dblpUrl=https://dblp.org/rec/conf/isic2/RajagopalV22
}}
==Hybrid Optimization Method for WSN Data Collection using Mobile Sink based on TSP Approach==
https://ceur-ws.org/Vol-3283/Paper98.pdf
Hybrid optimization method for WSN data collection using
mobile sink based on TSP approach
Vishnuvarthan Rajagopal1 and Bhanumathi Velusamy 1
1
Anna University Regional Campus, Coimbatore, Tamil nadu, India
Abstract
The path chosen by the mobile sink for data collection in a wireless sensor network must be
the shortest possible path to reduce the data collection delay and data loss through buffer
overflow. Finding the shortest path is a typical traveling salesman problem (TSP), which is a
NP-hard combinatorial optimization problem. This work proposes the HWOAGWO algorithm
which is a hybrid form of whale optimization algorithm (WOA) and the grey wolf optimization
(GWO) algorithm to solve the TSP problem efficiently. Dimension learning based hunting
strategy is used to avoid the algorithm getting trapped in local optima and slow convergence.
Finally, simulation is used to prove that the proposed HWOAGWO algorithm is better at
obtaining the best pathway over the other state-of-the-art algorithms. The algorithm is also
tested in a real-time outdoor environment to prove its reliability.
Keywords 1
Traveling salesman problem, Optimization algorithm, Wireless sensor network, Mobile sink
1. Introduction
The traveling salesman problem is a combinatorial problem where the salesman visits n cities
cyclically, stopping once at every city and at the end reaching back to the start city in the path with
minimal travel distance [1]. There are number of applications of TSP, namely, microchip
manufacturing, food delivery applications, logistics, X-ray crystallography, etc. Similarly, in wireless
sensor network, mobile sink (MS) moves to each cluster head (CH) or data centered node cyclically for
data collection. The data collecting delay must be as short as possible in order to improve network
performance. Hence, MS must take shortest possible path to collect the data from the CHs. Here, TSP
is applied to find the shortest path for the given set of CHs in the MS [2].
TSP is a NP-hard problem and it is solved by different methods such as optimization algorithms,
branch and bound techniques, dynamic programming techniques, etc. in the literature. In particular,
optimization algorithms such as genetic algorithm (GA), ant colony optimization (ACO) algorithm,
WOA, and GWO [3] are the most commonly used technique. In recent years, many hybrid and
improved optimization algorithms have been proposed to solve TSP as these algorithms find better
solution and takes very short time. In [4], a study on solving the TSP problem using different improved
and modified genetic algorithms is conducted. Through this study, it can be inferred that, the
probabilities of mutation and crossover affect the performance of GA. In particular, mutation
probability has more influence in convergence speed and the solution. Though GA offers many
advantages such as extensive feasible solutions and ease of combining with other technologies, it is
very less efficient when compared with other optimization algorithms.
Ant colony optimization algorithm [5] is another optimization approach widely used in the literature
to solve TSP. The main characteristics of ACO are adaptability, distribution and randomness. ACO
finds and memorizes the tour cost solutions and updates the pheromone trial based on the memorized
ACI’22: Workshop on Advances in Computation Intelligence, its Concepts & Applications at ISIC 2022, May 17-19, Savannah, United States
EMAIL: rvvarthan@gmail.com (A. 1); vbhanu_02@yahoo.com (A. 2)
ORCID: 0000-0002-3236-3389 (A. 1)
©️ 2020 Copyright for this paper by its authors.
Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
CEUR Workshop Proceedings (CEUR-WS.org)
197
tour cost. It is a kind of positive feedback mechanism and offers major advantages such as parallel
computation and optimum solution. But the major setback of ACO is that it can easily get trapped in
local optimum solution and operational inefficiency due to ant’s diversity. In [2], GWO is modified
using swap operator and swap sequence where each wolf holds a TSP solution. But identifying the
optimal set of swap operator is a major setback in this approach. It can be observed that, GWO performs
better in refining the solution (exploitation phase) but it suffers by easily getting trapped in local optima.
Amongst the metaheuristic algorithms, WOA is the powerful algorithm to find the global solution
for the optimization problems as it can avoid local optima, capable to explore and exploit the search
space [6]. To enhance the algorithm further, many variants were proposed in literature, namely,
hybridized algorithms such as WOA-PSO, WOA-BAT, WOA-ANN etc. Some of the works were
studied in [6] and main inference from the study is that, WOA performs better in finding the best
solution that is exploration phase but lacks performance in refining the solution (exploitation phase).
Hence basic WOA cannot produce better solution.
To summarize, there are many algorithms in the literature to solve TSP but most of them suffer with
slow convergence speed and getting trapped in local optima. So, in this work, WOA algorithm is used
as its performance is proven to be better than the other algorithms. Although WOA performs better in
finding the best solution, it lacks in refining optimum solution. Leveraging the advantage of exploitation
phase of GWO, WOA is hybridized with GWO in this work. Further, to avoid getting trapped in local
optima, dynamic learning-based hunting strategy is adopted in this work. Hence, in this research, we
present HWOAGWO, a new hybrid metaheuristic algorithm for avoiding premature convergence,
improving WOA's exploitation phase, and extending network lifetime. The main contributions of the
paper are:
1. HWOAGWO algorithm is proposed in which WOA is hybridized with GWO to improve the
performance of WOAs exploitation phase and alleviate the premature convergence.
2. The proposed algorithm is used in MS to solve the TSP problem for finding the shortest path
to commute between the CHs for data collection.
3. The result of the proposed HWOAGWO algorithm is compared against other state-of-the-arts
such as GA, WOA, and GWO. In addition, the proposed model is implemented in outdoor
environment to prove its reliability.
2. Proposed algorithm - HWOAGWO to solve TSP
WOA performs better in the exploration phase but not in the exploitation phase, hence we propose
a hybrid WOAGWO strategy to improve the exploitation phase in this paper. The proposed hybrid
WOAGWO technique is then used to determine the shortest path for the MS to travel in order to reach
all of the CHs. The CHs in the network are given as input to the algorithm, and population limit is set
to number of different possibilities of tour. The distance of the selected tour path is set as the fitness
function (f) of the search agent. The agent with best f score is considered as α-score and initially it is
chosen randomly. The algorithm starts the hunt by locating the prey using
𝑋(𝜏 + 1) = 𝑋 ∗ (𝜏) − 𝐴. 𝜉 (1)
where 𝜉 = ζ. 𝑋 (𝜏) - X(𝜏) and X is the position vector (P) and 𝑋 ∗ is the best position of the whale
∗
(𝑃𝐵 ) found by the algorithm so far. The coefficient vectors A and ζ are calculated by, A=a x (2.x-1) and
ζ =2.x. x is a random vector in the interval of [0,1]. The whale locates itself near the prey by adjusting
2𝜏
the vectors A and ζ. a is decreased from 2 to 0 for shrinking encircling mechanism based on a = 2 - ( 𝑀 )
Here, M is the maximum iteration allowed and 𝜏 represents iteration number. Based on A and p (a
random value generated by the algorithm between 0 and 1), the algorithm chooses its action:
(a) If p < 0.5 and |A|<1 then the whale is positioned based on Eq. (1). (b) if p<0.5 and |A|>1 then
the exploration phase is initiated. A is chosen either in A < -1 or A > 1, to position the whale far away
from the current.
Hence, the search agents' positions are updated using the equation below.
𝑋(𝜏 + 1) = 𝑋𝑟𝑎𝑛𝑑 − 𝐴. 𝜉 (2)
where, 𝜉 = ζ. 𝑋𝑟𝑎𝑛𝑑 - X and 𝑋𝑟𝑎𝑛𝑑 is randomly chosen position of the whale.
198
(c) Exploitation phase is initiated if p > 0.5. Based on the GWO approach, the whale's position is
updated: the best 3 search agents are considered as α, β, and γ and with positions 𝑋α , 𝑋β , and 𝑋γ , the
prey encircling is determined as below
𝑋𝑖1 (𝜏) = 𝑋𝛼 (𝜏) - 𝐴𝑖1 . 𝜉𝛼 (𝜏); 𝑋𝑖2 (𝜏) = 𝑋𝛽 (𝜏) - 𝐴𝑖2 . 𝜉𝛽 (𝜏); 𝑋𝑖3 (𝜏) = 𝑋𝛾 (𝜏) - 𝐴𝑖3 . 𝜉𝛾 (𝜏) (3)
where,
𝜉𝛼 = ζ𝛼 x 𝑋𝛼 − 𝑋(𝜏); 𝜉𝛽 = ζ2 x 𝑋𝛽 − 𝑋(𝜏); 𝜉𝛾 = ζ3 x 𝑋𝛾 − 𝑋(𝜏) (4)
Figure 1: HWOAGWO
The following equation calculates the first candidate for the new position of search agent 𝑋𝑖 (𝜏)
named 𝑋𝑖−𝐺 (𝜏 + 1):
𝑋𝑖−𝐺 (𝜏 + 1) = (𝑋1 + 𝑋2 + 𝑋3 )/3 (5)
The possibility of algorithm getting trapped in local optima is high in this approach. So, dimension
learning-based hunting (DLH) mechanism [1] is employed in this work. 𝑋𝑖 (𝑡) =𝑋𝑖1 , 𝑋𝑖2 , .. 𝑋𝑖𝑑 , where
d is the dimension number of the problem, gives the position of the search agent i at the 𝜏 𝑡ℎ iteration.
In DLH mechanism, individual hunting of the search agents is considered and is learned by its
neighbors. So, the neighbors 𝑁𝑖 (𝜏) of 𝑋𝑖 (𝜏) are constructed and is given by
𝑁𝑖 (𝜏) = {𝑋𝑗 (𝜏)|| 𝐷𝑖 (𝑋𝑖 (𝜏), 𝑋𝑗 (𝜏)) ≤ 𝑅𝑖 (𝑡), 𝑋𝑗 (𝜏) ∈ Pop} (6)
Where 𝐷𝑖 (𝑋𝑖 (𝜏), 𝑋𝑗 (𝜏)) is the distance between the position vector i and j at iteration τ and the radius
𝑅𝑖 (τ) is given by
𝑅𝑖 (τ) = ||𝑋𝑖 (τ) - 𝑋𝑖−𝐺 (τ+1)|| (7)
199
After 𝑁𝑖 (τ) construction, multi-neighbor learning is performed. The 𝑑 𝑡ℎ dimension of the neighbor
𝑋𝑖,𝑑 (τ) chosen from 𝑁𝑖 (τ) and the random search agent 𝑋𝑟,𝑑 (τ) from the population are used to determine
each dimension of the search agents new position.
𝑋𝑖−𝐷,𝑑 (τ+1) = 𝑋𝑖,𝑑 (τ) + rand x (𝑋𝑛,𝑑 (τ) - 𝑋𝑟,𝑑 (τ)) (8)
In selection and updating phase, the best candidate is selected among 𝑋𝑖−𝐺 (τ+1) and 𝑋𝑖−𝐷 (τ+1).
𝑋 (τ + 1), 𝑖𝑓𝑓(𝑋𝑖−𝐺 ) < 𝑓(𝑋𝑖−𝐷 ) (9)
𝑋𝑖 (τ+1) = { 𝑖−𝐺
𝑋𝑖−𝐺 (τ + 1), 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒
The flowchart of HWOAGWO is presented in Fig \ref{Algorithm}.
Table 1
Tour cost comparison
# of cities GA GWO WOA HWOAGWO
10 28 26.6 25.6 24.2
20 39.6 38.6 36.6 34.6
30 53.1 50.1 47.1 45.1
Figure 2: (a) TSP shortest path; (b) TSP comparison graph; (c) Delay
3. Results and discussion
In this section, traveling salesman problem is solved using the proposed HWOAGWO algorithm
and results are compared with GA [4], WOA [7] and GWO [8]. The results were taken as the average
of 10 individual run, population is kept fixed at 100 and the iteration is varied from 100 to 500. To test
the performance of the algorithms, cities with their location is fed as input to the algorithm. In Table
[1], 10, 20 and 30 cities with randomly generated location is given as input, and their corresponding
tour cost is compared after 100 iterations. The results show that, the proposed HWOAGWO algorithm
converges faster as it yields better tour cost than other algorithms.
Fig. 2(a) shows the best shortest path for the 50 cities (randomly placed) is fed as input and its
corresponding tour cost and here the x and y axis in the graph represents the distance in meter. In fig.
2(b), the tour cost obtained by each algorithm at 100, 200, 300, 400 and 500th iteration is compared. It
is evident from the figure that the HWOAGWO attains better outcome and outperformed GA, GWO
and WOA. Faster convergence observed with the proposed algorithm is mainly due to hybridized WOA
and GWO algorithm with adopted DLH strategy. It can also be noted from the figure that, as the iteration
increases, the tour cost decreases. This phenomenon is because, as the number of iteration increases,
the optimization algorithm converges better thereby yielding better shortest path.
In MATLAB, 50 homogenous sensor nodes with an initial energy of 0.5J are deployed at random in
a 100 m x 100 m region. LEACH is used to select the CHs and the location of the CHs are sent to MS.
Then MS computes the shortest path using the optimization algorithms (GA, WOA, GWO and
HWOAGWO). To test the performance, data collection delay of the network caused by each algorithm
is measured and the corresponding values are plotted in fig. 2(c). Evidently, the proposed work collects
data with very minimal delay than other existing algorithms. Hence, it is quite evident that the proposed
HWOAGWO algorithm produces better path with minimal tour cost in very short time.
The proposed work is also implemented in real time to test its reliability. Five arduino uno based
sensor nodes and a MS designed using raspberry pi 3 are used in this work and the nodes are placed in
20 m x 20 m area as shown in Fig. 3(a). The sensor nodes and sink are equipped with zigbee xbee s2c
200
radio modules for communication. In this work, the sensor network without any obstacles is considered.
All the respective parameters and their values for the real time implementation is given in Table 2.
Table 1
Real-time parameters
Parameter Value
Area 20 m X 20 m
Controller Arduino UNO
Radio module Zigbee XBee S2C
Radio range 1200 m
GPS module Ublox NEO-6M
Environment Outdoor
Motor driver L298N motor driver
As all the nodes are static, the location of the nodes is predetermined and the information are loaded
in the MS while the MS is equipped with NEO-6M GPS module. It has the horizontal position accuracy
of 2.5 m. In fig. 3(b), the graphical notation for the implementation is shown where the vertices
represent sensor nodes and the edges represents the distance between the nodes. In the MS, the
computation of shortest path is done with point A being the start point. The best path traversed by MS
is shown in Fig. 3(c) which is identified by the proposed algorithm. The tour cost of the corresponding
path is 54 m. Hence showing that the path found by the algorithm is reliable.
Figure 3: (a) TSP real time arrangement; (b) Graphical representation; (c) MS traversed path
4. Conclusion
In this paper, a hybrid optimization technique termed HWOAGWO is proposed for shortest path
selection for data collection using mobile sink in wsns. A dynamic learning-based hunting mechanism
is used to boost convergence speed and prevent the algorithm from being stuck in local optima.
According to the obtained results, the proposed work can converge faster than the existing algorithms
and is reliable in finding a shortest path. The sensor network with obstacles will be considered for the
future work.
5. Acknowledgements
The University Grant Commission (UGC), Government of India, funded the first author's research
[UGC-CSIR NET-JRF].
6. References
[1] M. H. Shahraki, S. Taghian, S. Mirjalili, "An improved grey wolf optimizer for solving engineering
problems." Expert Systems with Applications (2021), 166, 113917.
[2] C. Sun, "A Study of Solving Traveling Salesman Problem with Genetic Algorithm. "2020 9th
International Conference on Industrial Technology and Management (ICITM) (2020), 307-311.
201
[3] M. Krishnan, Y. Mo Jung, S. Yun, "An Improved Clustering with Particle Swarm Optimization-
Based Mobile Sink for Wireless Sensor Networks." 2018 2nd International Conference on Trends
in Electronics and Informatics (ICOEI) (2018), 105, 1024-1028.
[4] S. Li, Y. Wei, X. Liu, H. Zhu, Z. Yu, "A New Fast Ant Colony Optimization Algorithm: The
Saltatory Evolution Ant Colony Optimization Algorithm." Mathematics (2022), 10, 925.
[5] B. D. Shivahare, M. Singh, A. Gupta, S. Ranjan, D. Pareta, B. M. Sahu, "Survey Paper: Whale
optimization algorithm and its variant applications." 2021 International Conference on Innovative
Practices in Technology and Management (ICIPTM), (2021), 77-82.
[6] S. Mirjalili, A. Lewis, "Discrete Grey Wolf Optimizer for symmetric travelling salesman problem."
Advances in Engineering Software (2016), 95, 51-67.
[7] K. Panwar, K. Deep, "Mobile data gathering with load balanced clustering and dual data uploading
in wireless sensor networks." Applied Soft Computing (2021), 105, 107298.
202