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