# Data Acquisition through Mobile Sink for WSNs with Obstacles Using Support Vector Machine

Authors: Guduri Sulakshana; Govardhan Reddy Kamatam
Journal: Journal of Sensors
 (2022)

---

## Abstract

Mobile sink-based data collection in wireless sensor networks has become an attractive research area to mitigate hotspot issues. It further increases the efficiency of the WSN, such as throughput, lifetime, and energy efficiency, while decreasing delay and packet losses. Mobile sink algorithms developed by many researchers in recent years have only contributed to obtain efficient path planning, and only a few researchers have focused on solving the problem of network environment with obstacles. Here, constructing an obstacle-aware path for the mobile sink to collect data in WSN is a challenging issue. In this context, we present the data acquisition through mobile sink for WSNs with obstacles using support vector machine (DAOSVM). The DAOSVM algorithm works in two phases: visiting point selection and path construction. The visiting point selection uses spanning tree approach, and the path selection uses SVM. The computational complexity of the proposed DAOSVM is estimated and compared using the existing techniques, and it is lower. The DAOSVM also outperforms traditional methods concerning multiple performance metrics under various scenarios.


---

## Body

## 1. Introduction

Wireless sensor networks (WSNs) are the finite set of sensor nodes (SNs) deployed randomly in a region of interest to monitor and collect the data [1]. There are several WSN applications, which are air-quality monitoring, climate analysis, industries, defense, smart cities, etc. [2]. The SNs transmit their data using multihop communication to the base station (BS) or sink using relay nodes (RNs). These nodes are operated with low-powered batteries, and to replace them is a costly and hectic task [3]. Instead, energy can be harvested by using rechargeable SNs [4]. But, even here, it is uneconomical as a massive number of SNs have to be used in WSNs. Due to the use of a vast number of SNs and substantial data transmissions through multihop communications, the RNs near the BS drain more energy and die soon. In this case, there is a probability of BS being separated, giving rise to the energy hole or hotspot problem [5–7].Many of the researchers address the energy hole problem by introducing the mobile sink (MS). The MS is a vehicle that visits each SN in the network and receives data packets from them and reports the data to the BS. In this case, the SNs directly report their data to the MS, so there is no involvement of the RN, and hence, the energy consumption is minimized. However, visiting each SN is not the right approach because it takes a long time to reach the end node. Notably, delay-sensitive fields such as medical, industrial, and defense require data immediately. Furthermore, due to SN’s limited buffer overflow, it causes packet loss. Even if they adopt the shortest traveling path to visit all the SNs, it does not address the issue. So, instead of visiting each node in the network, the MS visits a few SNs called rendezvous points (RPs), and other nodes transmit their packets to the nearest RP. Thus, identifying optimal RPs and determining the best path by avoiding the delay and data losses are again challenging issues. However, some of the researchers address these challenges [8–10].Most of the researchers in the literature consider RP as a node or location and used traveling salesman problem (TSP) for MS path constructions. In [11–15], the authors adopted clustering algorithms to determine cluster heads (CHs) and they have considered CHs as RPs. Notably, these approaches have not considered the region of interest’s obstacles in a real-time environment while constructing the MS traveling path. So, there is a chance of getting obstacles in real-time environments, and determining the MS path by considering those obstacles is a more challenging issue. Besides that, the WSNs are operated dynamically with limited human intervention, so self-operated algorithms are needed. This requirement can be fulfilled by machine learning algorithms [1, 16]. However, data transmissions between child nodes and the RP are very high during multihop transmission. Introducing virtual RPs [14] will try to minimize the retransmission overhead by transmitting their data directly to the MS if it they are near the MS path.This article is motivated by these observations and presents data acquisition with mobile sink for WSNs with obstacles using support vector machine (DAOSVM). The DAOSVM initially determines optimal RPs set from the deployed SNs using a minimum spanning tree- (MST-) based clustering mechanism. Once it finds the RPs, the obstacles are identified and use a support vector machine algorithm to construct the path [17] among the RPs and the BS. Further, to lower the packet exchanges between the SNs and RPs, a set of virtual RPs (VRPs), at one-hop distance from the MS path, can be identified. Further, we compare the DAOSVM algorithm with recent and relevant published works such as eACO-MSPD [18], CMS2TO [19], EARTH [6], and ETDC [20] through various simulations and different performance metrics. The primary contributions of this article are listed as follows:
(i)
The proposed DAOSVM identifies the best RPs set from the WSN’s environment using the MST-based clustering mechanism(ii)
The shortest MS tour is determined by using the SVM algorithm between the RPs and the sink(iii)
We also determine the best VRPs set around the MS trajectory to minimize the unnecessary packet transmissions between SNs and the RPs(iv)
Finally, the superiority of the DAOSVM is compared with recently published relevant existing algorithms such as eACO-MSPD [18], CMS2TO [19], EARTH [6], and ETDC [20] using different quality metricsThe remaining sections of this article are organized as follows. In Section2, we study the recently published relevant articles. In Section 3, we discuss the proposed work along with the problem formulation and network model. In Section 4, we analyze the simulation test of existing and proposed works. In Section 5, we conclude the paper.


## 2. Related Work

Several works in the literature introduce path finding strategies for mobile sink while collecting the data for WSNs. This section summarizes most promising works with its advantages and limitations.


### 2.1. Path Construction in Regular WSNs

A typical network in this subsection considers WSNs without any obstacles while constructing a path. From literature [21], we identified several works and they are summarized as follows.Lin et al. [22] used to determine a static path between VPs in WSNs and perform the data fusion using MS. An ant colony optimization- (ACO-) based path construction algorithm is used for event-driven WSNs [8]. In this approach, ACO is used for both RP selection along with pathfinding. Further, the authors extended this work by adding virtual RPs with an improved probability metrics of the ACO in [18]. These approaches not only provide an optimal path but also improve efficiency in terms of energy, lifetime, throughput, delay, etc. Mehto et al. [23] used the PSO approach to construct an efficient path between RPs under the event-driven approach. Mehto et al. used a squirrel search algorithm to partition the WSNs into cluster and cluster heads.In a grid-based sensor deployment with uniform data rate, WSNs are considered in [24] for data collection using a mobile sink. This work is considered a density-based network during the simulation, providing an efficient path along with the best network performance. In [25], multiple MSs are used to acquire the data within the WSN in which uniform data is generated by all the sensor nodes. The network is partitioned according to the multihop manner RPs in the network. A MS-based data collection is presented in [26] in which the delay minimization is considered the primary objective. In this, the sensitive data is performed dynamic routing, whereas the MS acquires the delay insensitive data. Further, they extended this work in [27] to mitigate the hotspot problem. However, this approach results in a longer path and leads to high computational complexity. Another delay-sensitive method using MS is presented in [28] to lower the delay and energy utilization using a spanning tree-based approach.Gupta and Saha [29] proposed an artificial bee colony (ABC) approach for path construction and data collection for WSNs where the data rate is evenly distributed. An optimal set of RPs is identified in [30] using PSO which can provide a longer life to sensor nodes with efficient energy utilization in the network where the data is uniformly distributed. An adaptive data rate control is maintained while performing data collection using MS in [31]. This approach requires low computation and efficient in balancing the energy and network. But, this approach did not consider an obstacle-aware network. A method for MS-based data collection with MS using fuzzy logic for clustering the network to identify the RPs and strategies for path construction for efficient data collection. Using geometric techniques, an efficient path for the mobile sink is introduced in [32].From the above literature, it can be concluded that none of the above works considered an obstacle-aware path for the MS required to acquire data from sensor nodes or RPs. There are few works in the literature which considers obstacle-aware path finding approaches which are discussed in the following subsection.


### 2.2. Path Construction in Obstacle WSNs

In this subsection, we discuss the approaches which are used to construct mobile sink path in an environment of WSNs with obstacles.An artificial intelligence (AI) and ACO approach is used in [12] to construct a path in an obstacle WSN environment and gather data using a mobile sink. Initially, ACO can be used for creating the clusters and AI-enabled approach is meant to construct path for mobile sinks in WSNs to acquire data. In [9], the authors proposed an efficient algorithm for MS path construction and buffer management using the Q-learning approach for WSNs. In this approach, the Q-learning algorithm schedules the MS efficiently to minimize the packet loss rate in the network. This approach has not adopted the VRP selection strategy for improving the data gathering process. In [13], the PSO-based mechanism used to select CHs in WSNs is also useful in constructing a path to the MS. In [6], the authors have proposed a MS tour plan for WSNs with limited buffers and nonuniform constraints.Xie and Pan [33] introduced a cluster-based grid partition in WSNs with obstacles and a determined path for the MS. In this work, a heuristic method is used to decide an efficient path for the mobile element to get the data packets from the SNs while avoiding obstacles during its travel. Obstacle-aware connection management is introduced in [34] using the Delaunay triangulation-based approach for the mobile elements. This approach efficiently manages the connections between the sensor nodes to help route their data efficiently to the base station. In [35], Park et al. invented an iterative clustering mechanism to optimize the route of the MS while acquiring the data packets from SNs. This approach is efficient and intelligent while acquiring and improving the data gathering efficiency. This approach works efficiently and intelligently in improving the data gathering process. An obstacle-aware path for MS is introduced using the cluster-based approach in [36] for WSNs. In [37], Yang et al. present a dynamic path for MS using virtual potential fields in WSNs.From the above study, it is evident that most of the existing algorithms have considered the mobile sink path without considering the obstacles. Even though, in some works, obstacles are considered, they failed in incorporating the VRP selection process to reduce the unnecessary packet transmissions between the SNs and RPs. Furthermore, MS traveling distance can also be optimized and dynamically constructed. All these challenges are addressed in the proposed DAOSVM mechanism.


## 2.1. Path Construction in Regular WSNs

A typical network in this subsection considers WSNs without any obstacles while constructing a path. From literature [21], we identified several works and they are summarized as follows.Lin et al. [22] used to determine a static path between VPs in WSNs and perform the data fusion using MS. An ant colony optimization- (ACO-) based path construction algorithm is used for event-driven WSNs [8]. In this approach, ACO is used for both RP selection along with pathfinding. Further, the authors extended this work by adding virtual RPs with an improved probability metrics of the ACO in [18]. These approaches not only provide an optimal path but also improve efficiency in terms of energy, lifetime, throughput, delay, etc. Mehto et al. [23] used the PSO approach to construct an efficient path between RPs under the event-driven approach. Mehto et al. used a squirrel search algorithm to partition the WSNs into cluster and cluster heads.In a grid-based sensor deployment with uniform data rate, WSNs are considered in [24] for data collection using a mobile sink. This work is considered a density-based network during the simulation, providing an efficient path along with the best network performance. In [25], multiple MSs are used to acquire the data within the WSN in which uniform data is generated by all the sensor nodes. The network is partitioned according to the multihop manner RPs in the network. A MS-based data collection is presented in [26] in which the delay minimization is considered the primary objective. In this, the sensitive data is performed dynamic routing, whereas the MS acquires the delay insensitive data. Further, they extended this work in [27] to mitigate the hotspot problem. However, this approach results in a longer path and leads to high computational complexity. Another delay-sensitive method using MS is presented in [28] to lower the delay and energy utilization using a spanning tree-based approach.Gupta and Saha [29] proposed an artificial bee colony (ABC) approach for path construction and data collection for WSNs where the data rate is evenly distributed. An optimal set of RPs is identified in [30] using PSO which can provide a longer life to sensor nodes with efficient energy utilization in the network where the data is uniformly distributed. An adaptive data rate control is maintained while performing data collection using MS in [31]. This approach requires low computation and efficient in balancing the energy and network. But, this approach did not consider an obstacle-aware network. A method for MS-based data collection with MS using fuzzy logic for clustering the network to identify the RPs and strategies for path construction for efficient data collection. Using geometric techniques, an efficient path for the mobile sink is introduced in [32].From the above literature, it can be concluded that none of the above works considered an obstacle-aware path for the MS required to acquire data from sensor nodes or RPs. There are few works in the literature which considers obstacle-aware path finding approaches which are discussed in the following subsection.


## 2.2. Path Construction in Obstacle WSNs

In this subsection, we discuss the approaches which are used to construct mobile sink path in an environment of WSNs with obstacles.An artificial intelligence (AI) and ACO approach is used in [12] to construct a path in an obstacle WSN environment and gather data using a mobile sink. Initially, ACO can be used for creating the clusters and AI-enabled approach is meant to construct path for mobile sinks in WSNs to acquire data. In [9], the authors proposed an efficient algorithm for MS path construction and buffer management using the Q-learning approach for WSNs. In this approach, the Q-learning algorithm schedules the MS efficiently to minimize the packet loss rate in the network. This approach has not adopted the VRP selection strategy for improving the data gathering process. In [13], the PSO-based mechanism used to select CHs in WSNs is also useful in constructing a path to the MS. In [6], the authors have proposed a MS tour plan for WSNs with limited buffers and nonuniform constraints.Xie and Pan [33] introduced a cluster-based grid partition in WSNs with obstacles and a determined path for the MS. In this work, a heuristic method is used to decide an efficient path for the mobile element to get the data packets from the SNs while avoiding obstacles during its travel. Obstacle-aware connection management is introduced in [34] using the Delaunay triangulation-based approach for the mobile elements. This approach efficiently manages the connections between the sensor nodes to help route their data efficiently to the base station. In [35], Park et al. invented an iterative clustering mechanism to optimize the route of the MS while acquiring the data packets from SNs. This approach is efficient and intelligent while acquiring and improving the data gathering efficiency. This approach works efficiently and intelligently in improving the data gathering process. An obstacle-aware path for MS is introduced using the cluster-based approach in [36] for WSNs. In [37], Yang et al. present a dynamic path for MS using virtual potential fields in WSNs.From the above study, it is evident that most of the existing algorithms have considered the mobile sink path without considering the obstacles. Even though, in some works, obstacles are considered, they failed in incorporating the VRP selection process to reduce the unnecessary packet transmissions between the SNs and RPs. Furthermore, MS traveling distance can also be optimized and dynamically constructed. All these challenges are addressed in the proposed DAOSVM mechanism.


## 3. Proposed Work

In this section, we present the problem formulation, algorithm proposed, illustration, and complexity analysis. In Section3.1, we also discuss the network model and the parameters that affect the WSNs. Section 3.2 describes the detailed data collection process using MS in the obstacle/barrier containing WSNs. Finally, the complexity of the DAOSVM is analyzed, and it is also compared with the existing methods. The notations used in this paper are summarized in Table 1.Table 1
Frequently used notations and their meanings.
NotationMeaningGWSNnNumber of SNsiSensor node indexDAdjacency matrix of distances between nodesSSet of nodesS0Base stationδSi,SjDistance between two nodesrTransmission rangeVVRP setMRP setℝMS communication rangeλkThe time taken to complete a tourkͷkDistance travelled by MS at tourkBBuffer capacityψiiith vector in the datasetTMSTNlNetwork lifetimeSSet of indices for SVsFFairness index of ECBUBuffer utilizationΛiAssociated label to theψi


### 3.1. Problem Formulation

The WSN is considered an undirected and connected graphGS,D, where S=S0,S1,S2,⋯,Sn. Here, S0 is treated as BS and the remaining are the SNs. All these n=S−1 SNs are randomly deployed at fixed locations (no mobility after the deployment) and has unique properties. The D=δSi,Sj∀Si,Sj∈S∧δSi,Sj≤r is the distance adjacency matrix, which includes the S0. Euclidean distance and transmission ranges between two SNs Si and Sj are treated as δSi,Sj and r, respectively. We consider the distance between two SNs Si and Sj as ∞, if they are not in r. The set of RPs are denoted using M, where the RP is supposed to acquire data packets from SNs and VRPs. The V is treated as the set of VRPs, where the VRPs transmit their data directly to MS or the closest RP. The MS acquires the data from RPs or VRPs and submits it to the S0. The MS starts from S0 by traveling around the network while crossing each M and reaches again to S0. This is called a tour. The time taken to complete a tour k is denoted as λk. The distance travelled by MS in a tour k is denoted as ùk. The velocity of the MS is constant during the data collection process, and it is denoted with υ. The MS communication range is indicated as ℝ, and the minimum distance from Vi to the MS must be less than ℝ. The obstacles in the WSN environment are considered O. All the SNs in the network have uniform buffer availability, and it can store a maximum of b bits in its buffer. The buffer occupancy is indicated with pi, where ∀pi≤b.TheE0 is considered the initial energy of SNs, and it is same to all S initially, and it is utilized mainly during sensing phenomenon, data transmitting, and processing. The energy model for the DAOSVM follows the free-space energy model, according to [14]. The needed energy for the amplification is αa, needed energy to process a bit of data is αt, and the circuit needs αr energy to receive a bit. The energy consumption (EC) of the node Si, while transferring B bits to the node Sj is in
(1)Eti,j=αt×B+αa×δij2×B.The nodeSi consumes energy as shown in Equation (2), while receiving B bits from node j.
(2)Eri=αr×B.The EC of a nodeSi during data transmission to Sj∈S and acquiring data from Sj∈S in the tour k is calculated using
(3)Eik=Eti,j+Erj+Δ,whereΔ is the node Si’s energy variation for data processing. The RP set count is indicated using ζ=M, and it is decided using Equation (4), and it is derived based on [38].
(4)ζ=n2π×αaαt×AδMi,S0,whereA is the area of the WSNs in sq m and δMi,S0 is the distance between Mi RP to the BS S0.The lifetime of the WSN (N) is the epoch time till the first SN drains its energy completely, and we consider the metric in terms of minutes [8]. It is measured similarly to
(5)N=∑k=1δλk,whereλk is MS one tour time and δ indicates the # of trips completed by the MS. Therefore, the objective of the DAOSVM is summarized as it prolongs the N and reduces the data acquisition delay by avoiding the obstacles. Finally, the problem statement is to choose the optimal RP set, i.e., M, which maximizes N for obstacle-aware data collection using MS.


### 3.2. Obstacle-Aware Path Determination

The proposed DAOSVM algorithm involves three phases. In the first phase, the algorithm applies the MST-based clustering mechanism (MST-CM). From the MST-CM, it determines the best RPs set for further data collection process. In the second phase, MS path is constructed by avoiding obstacles with the SVM algorithm’s help. In the final stage, the algorithm finds a set of VRPs with the help of which the number of retransmissions between the RPs and SNs can be minimized. For a better understanding of the proposed MS path construction, we provided preliminaries of the SVM in this section. The overview of the proposed work is shown in Figure1.Figure 1
Overview of the proposed obstacle-aware path determination approach.


#### 3.2.1. Preliminaries of SVM

The SVM is a supervised ML algorithm, which can solve the regression or classification problems with better accuracy [1]. The proposed DAOSVM uses a margin maximization mechanism with the help of SVM to address the issue by constructing an optimal hyperplane.Let us consider the datasetψi,Λii=0n, where ψi is the ith vector in the dataset and Λi is the associated label to the ψi and Λi∈−1,+1. This sample is separated with the hyperplane ωTψ±h=0. In case, the training samples are to be linearly separable, and ω and h has to be satisfied which is shown in
(6)ΛiωTψ±h≥1∀i=0,1,2,⋯,n.By using these parameters, the two classes of samples are separated by the two hyperplanes such asH1:ωTψ±h=+1 and H2:ωTψ±h=−1 and ensures that no other data exists between them. 2/ω represents the objective functions for minimizing the parameters as shown in Equation (7) under the constraints of Equaton (6).
(7)Lω=12ω2.The margin maximization can be obtained by using the Lagrange multipliers, as shown below:(8)maxα∑i=1nαi−12∑i,j=1nψiψjΛiΛjαiαj,subjected to Equation (9) and αi≥0∀i=1,2,⋯,n.
(9)∑i=1nαiΛi=0.The training datasetψi with αi (nonzero) are either of the hyperplanes H1 or H2 and are treated as the support vectors (SV), because these data can only be helpful to compute the parameters. From this, a discrimination function is constructed which is shown in
(10)Λ=signωTψ±h=sign∑i∈SαiΛiψiTψ,whereS represents the set of indices for SV. The kernel trick of SVM is used to classify points which are not linearly separable. Various kernels like polynomial and rbf can be used. But here, we have used a polynomial kernel.


#### 3.2.2. RP Selection Strategy

In this phase, the graphG is considered an input and determines the best RP set M. We use MST based clustering mechanism (MST-CM) to determine the best set of RPs, i.e., M with low computational complexity. The initial SNs and base station deployment is illustrated in Figure 2(a). The graph G is constructed by exchanging location information among SNs, and if the distance is less than r between SNs, they are connected with an edge. The G construction is illustrated in Figure 2(b).Figure 2
Steps involved in (a) SNs and BS deployment. (b) WSN graphGS,D. (c) MST using Prim’s algorithms. (d) Clustering the MST. (e) Determine the RP from each cluster.
(a)(b)(c)(d)(e)The MST-CM applies Prim’s algorithm to construct the MST from the WSN graphG. The resultant MST T of the WSN G is shown in Figure 2(c) (there is no difference between the edges with different colors). The MST-CM identifies the longest edges from T using Equation (11) by removing it temporally and compute the next longest node until ζ times.
(11)longijζ=argmaxi,j∈TD.This partition results in the best nearest neighbor set with limited cost. However, removing the most extended node always does not result in the best clustering strategy. So, before removing the node permanently, we use the coefficient of variation (CoV) to each node to decide the efficiency when an extended node is removed while forming the clusters. The CoV is used to measure the consistency, i.e., it can measure how the edge weight (distance between the two nodes) is uniform from one another. The CoV for MST-CM is the ratio of standard deviation (SD) and mean of the edge weights from theT, as shown in
(12)CoVi=σiχ,whereσi is the ith edge SD and χ is the arithmetic mean of the edges in the T. The σi is computed using Equation (13), and χ is computed as shown in Equation (14).
(13)σi=1n∑i=0n−1ei−χ2,whereei is the edge weight of the SN i and χ is
(14)χ=1n∑i=0n−1ei.From Equation (12), it can be seen that decreasing CoV means higher efficiency can be obtained. Before removing any node permanently from the T, we test the CoV. This operation results in ζ+1 clusters from the T. We use a threshold on the CoV to remove the inconsistent edges from the MST (T) to generate the clusters. The cluster set after removing the longest edge depends on the CoV which is illustrated in Figure 2(d). From each cluster ζ, we find the RP using the Equation (15) and it is considered from [38].
(15)Tn=P1−Pr×modP−1×E0−EikE0×ζ,whereP is the probability of choosing the node as RP, E0 is the initial energy of the SN, and ζ is computed as shown in Equation (4). In each round, the SN generates a random threshold value between zero and one and compared it with the Tn to identify the RPs. In the first round of data collection, energy is not affected, but from the second round onwards, the selection of RPs considers energy. This process is illustrated in Figure 2(e).The proposed DAOSVM also involves the reselection of RPs in each round using Equation (15) and energy models. The RP reselection also balances the energy among the SNs. Notably, the SNs near RPs face the same energy hole problem because of the relaying task, if no reselection is involved.


#### 3.2.3. MS Path Determination

The MS path construction phase is a critical and challenging phase as it decides the efficiency of the data gathering process, and it is more complicated when the obstacles are considered. This phase is executed after the RPs setM is decided. This algorithm is extended with two phases: (I) deciding the visiting order and (II) avoiding the obstacles in the path.In phase I, visiting order of the RPs by the MS is decided. There are several algorithms in the literature which can choose the optimal and shortest path for the mobile sink using TSP, ACO, etc., but these require complex computations. Here, we plan to propose a lightweight path selection algorithm to fill the necessity of the shortest path using computational geometry methods [14]. This phase takes the M as an input and produces the path as an output. We assume that all the M are having coordinates X and Y in a plane A. Initially, we determine the maximum and minimum X coordinates from the M and assume a virtual line between these coordinates. So, the plane is split into two parts such as above the line and below the line. Then, all the M’s are arranged below the line in ascending/descending order according to the X coordinates and descending/ascending (opposite to the above) order of M’s according to the X coordinates. Then, concatenate both M’s to get the visiting order of RPs. The algorithm detects the path by avoiding the obstacles in phase II.In phase II, the support vector machine algorithm is applied to construct the path which can avoid the environment’s obstacles. The step-by-step path determination algorithm explained through Figure3. Before starting the algorithm, label the positive and negative obstacles. Note that the red dots indicate the negative obstacles, and green circles indicate the positive obstacles from Figure 3. Here, actual obstacles are highlighted, and the triangles indicate the RPs. Figure 3(a) is the primary example considered for illustration of path construction between two RPs by considering two obstacles of the WSN environment.Figure 3
Mobile sink path construction using support vector machine technique. (a) Example of two RPs and two obstacles for path construction. (b) Deployment of virtual obstacles around the RPs. (c) Determine the patterns of the obstacles. (d) Construct guided sample lines parallel to sample lines. (e) Apply the SVM to determine the initial phase of path. (f) Best MS traveling path between two RPs. (g) Feasible paths between the two RPs by avoiding the obstacles.
(a)(b)(c)(d)(e)(f)(g)Initially, we construct a virtual path between the two RPs (M1 and M2), which is a regular straight line between them. Virtual obstacles are set around the RPs at a certain distance δ≤r from both the RPs and parallel to the straight path. These virtual obstacles are categorized into both positive (right side to the straight line) and negative (left side to the straight line), as shown in Figure 3(b). After that, we determine the pattern of the obstacles and identify the positive and negative obstacles depending on the obstacle centroid. If the centroid of the obstacle is right, then we highlight the obstacle as positive, and in case the centroid is in the left or on the line, we consider the negative obstacle sign as shown in Figure 3(c). The guided samples are arranged parallel to the sample line with a certain distance δg from the line, as shown in Figure 3(d). These lines are adjusted according to the negative virtual obstacles or the points. Depending on the obstacle, the line moves the opposite side, and the guided sample of that side near an obstacle also moves according to the distance of the obstacle to samples.We can now apply the SVM on the sample generated and analyze the results of the SVM learning process. By applying the learning process, the SVM results in support vector set and their weights can decide each point’s region according to positive or negative obstacles. This region also constructs a collision-free separate line in a two-dimensional area, as shown in Figure3(e). We try to determine the line separation from the obstacles by iteratively searching for the next point until Equation (16) results in value zero.
(16)V=∑i∈SαiΛiψiTψ−h.By repeating this, we get the MS path by avoiding the obstacles fromM1 to M2, as shown in Figure 3(f). However, this is a possible path and not the optimal path. We can also terminate the iteration when the V<1.0, exceeding the number of iterations and then threshold values (this case may happen if the distance between the path and obstacles are minimal from both sides). We repeat the same process by adjusting the guided lines (Figure 3(d)) or flipping the positive or negative obstacles to make another pattern to construct several possible paths as shown in Figure 3(g) and choose the best one among them. This process is repeated until all the RPs are visited from M which can complete the traveling tour from BS via RPs to the BS.


#### 3.2.4. VRP Selection

The selection of VRPs of the proposed work improves the data acquisition process by minimizing the communications between the SNs and the RPs as shown in Figure4. In this work, the VRPs are the SNs V∈S∧VÚM, which can directly communicate with the MS when it traverses in its range r. The VRPs in DAOSVM is determined based on the available time of MS on the trajectory within the range of the SNs.Figure 4
VRP selection strategies.Initially, we choose a line/curveLp=y=fx∀p∈0≤p<M between any two RPs from M. The fx is in the form of ax2+bx+c. We assume that Sixi,yi be a VRP and we determine the distance to the Lp with a particular point qx,y on it which should be less than r. The shortest distance point on Lp from each SN Sixi,yi is computed as shown in
(17)D=xi−x2+yi−y2=xi−x2+yi−ax2+bx+c2.From Equation (17), we can derive the x coordinate of q by applying the derivation of both sides, i.e., dD/dx to zero. Once we get x, we can easily determine the y coordinate of q. Similarly, this process is repeated with each SN to get all the possible paths between RPs. The following illustration gives a better understanding of the VRP selection process. We assume that Si=3,8 and the equation of the curve as y=x2+8; then, Equation (18) briefs the shortest point on the path La.
(18)D=3−x2+8−x2+22=9−6x+x2+8−x2−92=x4+x2−6x+9.Here, we setdD/dx to 0 and solve for x; finally, it returns x=1. We substitute the value of x in y=x2+8, so that we get y=9. So, the nearest point on the Lp to the Si=3,8 is q=1,9. If the Euclidean distance between the δSi,q is less than or equal to the r, then Si is included to V.


### 3.3. Complexity Analysis

The complexity of the first stage is the RP selection which comprises of MST construction, identifying the edges to be removed and RP node selection. The complexity of the MST using Prim’s algorithm isOElogV, where E is the number of edges in the T, and V=n indicates the number of nodes. The complexity to identify the edges to be removed is OE2. The complexity to identify the RPs is On2. Overall, the time complexity of final RP set selection is OElogV+OE2+On2, and the E in T is nn−1/2. After the E value is substituted, the asymptotic complexity of RP set selection is On2logn. The visiting order of M requires Onlogn computational time. The time complexity of path construction by avoiding the obstacles using SVM is OSV3, where SV indicates the number of of support vectors, i.e., SV≈n, so the complexity is treated as On3. The complexity to determine the VRPs set is On2. The overall computational complexity after evaluating all phases is On2logn+On3+On2, and the final asymptotic computational complexity of DAOSVM algorithm is On3.


## 3.1. Problem Formulation

The WSN is considered an undirected and connected graphGS,D, where S=S0,S1,S2,⋯,Sn. Here, S0 is treated as BS and the remaining are the SNs. All these n=S−1 SNs are randomly deployed at fixed locations (no mobility after the deployment) and has unique properties. The D=δSi,Sj∀Si,Sj∈S∧δSi,Sj≤r is the distance adjacency matrix, which includes the S0. Euclidean distance and transmission ranges between two SNs Si and Sj are treated as δSi,Sj and r, respectively. We consider the distance between two SNs Si and Sj as ∞, if they are not in r. The set of RPs are denoted using M, where the RP is supposed to acquire data packets from SNs and VRPs. The V is treated as the set of VRPs, where the VRPs transmit their data directly to MS or the closest RP. The MS acquires the data from RPs or VRPs and submits it to the S0. The MS starts from S0 by traveling around the network while crossing each M and reaches again to S0. This is called a tour. The time taken to complete a tour k is denoted as λk. The distance travelled by MS in a tour k is denoted as ùk. The velocity of the MS is constant during the data collection process, and it is denoted with υ. The MS communication range is indicated as ℝ, and the minimum distance from Vi to the MS must be less than ℝ. The obstacles in the WSN environment are considered O. All the SNs in the network have uniform buffer availability, and it can store a maximum of b bits in its buffer. The buffer occupancy is indicated with pi, where ∀pi≤b.TheE0 is considered the initial energy of SNs, and it is same to all S initially, and it is utilized mainly during sensing phenomenon, data transmitting, and processing. The energy model for the DAOSVM follows the free-space energy model, according to [14]. The needed energy for the amplification is αa, needed energy to process a bit of data is αt, and the circuit needs αr energy to receive a bit. The energy consumption (EC) of the node Si, while transferring B bits to the node Sj is in
(1)Eti,j=αt×B+αa×δij2×B.The nodeSi consumes energy as shown in Equation (2), while receiving B bits from node j.
(2)Eri=αr×B.The EC of a nodeSi during data transmission to Sj∈S and acquiring data from Sj∈S in the tour k is calculated using
(3)Eik=Eti,j+Erj+Δ,whereΔ is the node Si’s energy variation for data processing. The RP set count is indicated using ζ=M, and it is decided using Equation (4), and it is derived based on [38].
(4)ζ=n2π×αaαt×AδMi,S0,whereA is the area of the WSNs in sq m and δMi,S0 is the distance between Mi RP to the BS S0.The lifetime of the WSN (N) is the epoch time till the first SN drains its energy completely, and we consider the metric in terms of minutes [8]. It is measured similarly to
(5)N=∑k=1δλk,whereλk is MS one tour time and δ indicates the # of trips completed by the MS. Therefore, the objective of the DAOSVM is summarized as it prolongs the N and reduces the data acquisition delay by avoiding the obstacles. Finally, the problem statement is to choose the optimal RP set, i.e., M, which maximizes N for obstacle-aware data collection using MS.


## 3.2. Obstacle-Aware Path Determination

The proposed DAOSVM algorithm involves three phases. In the first phase, the algorithm applies the MST-based clustering mechanism (MST-CM). From the MST-CM, it determines the best RPs set for further data collection process. In the second phase, MS path is constructed by avoiding obstacles with the SVM algorithm’s help. In the final stage, the algorithm finds a set of VRPs with the help of which the number of retransmissions between the RPs and SNs can be minimized. For a better understanding of the proposed MS path construction, we provided preliminaries of the SVM in this section. The overview of the proposed work is shown in Figure1.Figure 1
Overview of the proposed obstacle-aware path determination approach.


### 3.2.1. Preliminaries of SVM

The SVM is a supervised ML algorithm, which can solve the regression or classification problems with better accuracy [1]. The proposed DAOSVM uses a margin maximization mechanism with the help of SVM to address the issue by constructing an optimal hyperplane.Let us consider the datasetψi,Λii=0n, where ψi is the ith vector in the dataset and Λi is the associated label to the ψi and Λi∈−1,+1. This sample is separated with the hyperplane ωTψ±h=0. In case, the training samples are to be linearly separable, and ω and h has to be satisfied which is shown in
(6)ΛiωTψ±h≥1∀i=0,1,2,⋯,n.By using these parameters, the two classes of samples are separated by the two hyperplanes such asH1:ωTψ±h=+1 and H2:ωTψ±h=−1 and ensures that no other data exists between them. 2/ω represents the objective functions for minimizing the parameters as shown in Equation (7) under the constraints of Equaton (6).
(7)Lω=12ω2.The margin maximization can be obtained by using the Lagrange multipliers, as shown below:(8)maxα∑i=1nαi−12∑i,j=1nψiψjΛiΛjαiαj,subjected to Equation (9) and αi≥0∀i=1,2,⋯,n.
(9)∑i=1nαiΛi=0.The training datasetψi with αi (nonzero) are either of the hyperplanes H1 or H2 and are treated as the support vectors (SV), because these data can only be helpful to compute the parameters. From this, a discrimination function is constructed which is shown in
(10)Λ=signωTψ±h=sign∑i∈SαiΛiψiTψ,whereS represents the set of indices for SV. The kernel trick of SVM is used to classify points which are not linearly separable. Various kernels like polynomial and rbf can be used. But here, we have used a polynomial kernel.


### 3.2.2. RP Selection Strategy

In this phase, the graphG is considered an input and determines the best RP set M. We use MST based clustering mechanism (MST-CM) to determine the best set of RPs, i.e., M with low computational complexity. The initial SNs and base station deployment is illustrated in Figure 2(a). The graph G is constructed by exchanging location information among SNs, and if the distance is less than r between SNs, they are connected with an edge. The G construction is illustrated in Figure 2(b).Figure 2
Steps involved in (a) SNs and BS deployment. (b) WSN graphGS,D. (c) MST using Prim’s algorithms. (d) Clustering the MST. (e) Determine the RP from each cluster.
(a)(b)(c)(d)(e)The MST-CM applies Prim’s algorithm to construct the MST from the WSN graphG. The resultant MST T of the WSN G is shown in Figure 2(c) (there is no difference between the edges with different colors). The MST-CM identifies the longest edges from T using Equation (11) by removing it temporally and compute the next longest node until ζ times.
(11)longijζ=argmaxi,j∈TD.This partition results in the best nearest neighbor set with limited cost. However, removing the most extended node always does not result in the best clustering strategy. So, before removing the node permanently, we use the coefficient of variation (CoV) to each node to decide the efficiency when an extended node is removed while forming the clusters. The CoV is used to measure the consistency, i.e., it can measure how the edge weight (distance between the two nodes) is uniform from one another. The CoV for MST-CM is the ratio of standard deviation (SD) and mean of the edge weights from theT, as shown in
(12)CoVi=σiχ,whereσi is the ith edge SD and χ is the arithmetic mean of the edges in the T. The σi is computed using Equation (13), and χ is computed as shown in Equation (14).
(13)σi=1n∑i=0n−1ei−χ2,whereei is the edge weight of the SN i and χ is
(14)χ=1n∑i=0n−1ei.From Equation (12), it can be seen that decreasing CoV means higher efficiency can be obtained. Before removing any node permanently from the T, we test the CoV. This operation results in ζ+1 clusters from the T. We use a threshold on the CoV to remove the inconsistent edges from the MST (T) to generate the clusters. The cluster set after removing the longest edge depends on the CoV which is illustrated in Figure 2(d). From each cluster ζ, we find the RP using the Equation (15) and it is considered from [38].
(15)Tn=P1−Pr×modP−1×E0−EikE0×ζ,whereP is the probability of choosing the node as RP, E0 is the initial energy of the SN, and ζ is computed as shown in Equation (4). In each round, the SN generates a random threshold value between zero and one and compared it with the Tn to identify the RPs. In the first round of data collection, energy is not affected, but from the second round onwards, the selection of RPs considers energy. This process is illustrated in Figure 2(e).The proposed DAOSVM also involves the reselection of RPs in each round using Equation (15) and energy models. The RP reselection also balances the energy among the SNs. Notably, the SNs near RPs face the same energy hole problem because of the relaying task, if no reselection is involved.


### 3.2.3. MS Path Determination

The MS path construction phase is a critical and challenging phase as it decides the efficiency of the data gathering process, and it is more complicated when the obstacles are considered. This phase is executed after the RPs setM is decided. This algorithm is extended with two phases: (I) deciding the visiting order and (II) avoiding the obstacles in the path.In phase I, visiting order of the RPs by the MS is decided. There are several algorithms in the literature which can choose the optimal and shortest path for the mobile sink using TSP, ACO, etc., but these require complex computations. Here, we plan to propose a lightweight path selection algorithm to fill the necessity of the shortest path using computational geometry methods [14]. This phase takes the M as an input and produces the path as an output. We assume that all the M are having coordinates X and Y in a plane A. Initially, we determine the maximum and minimum X coordinates from the M and assume a virtual line between these coordinates. So, the plane is split into two parts such as above the line and below the line. Then, all the M’s are arranged below the line in ascending/descending order according to the X coordinates and descending/ascending (opposite to the above) order of M’s according to the X coordinates. Then, concatenate both M’s to get the visiting order of RPs. The algorithm detects the path by avoiding the obstacles in phase II.In phase II, the support vector machine algorithm is applied to construct the path which can avoid the environment’s obstacles. The step-by-step path determination algorithm explained through Figure3. Before starting the algorithm, label the positive and negative obstacles. Note that the red dots indicate the negative obstacles, and green circles indicate the positive obstacles from Figure 3. Here, actual obstacles are highlighted, and the triangles indicate the RPs. Figure 3(a) is the primary example considered for illustration of path construction between two RPs by considering two obstacles of the WSN environment.Figure 3
Mobile sink path construction using support vector machine technique. (a) Example of two RPs and two obstacles for path construction. (b) Deployment of virtual obstacles around the RPs. (c) Determine the patterns of the obstacles. (d) Construct guided sample lines parallel to sample lines. (e) Apply the SVM to determine the initial phase of path. (f) Best MS traveling path between two RPs. (g) Feasible paths between the two RPs by avoiding the obstacles.
(a)(b)(c)(d)(e)(f)(g)Initially, we construct a virtual path between the two RPs (M1 and M2), which is a regular straight line between them. Virtual obstacles are set around the RPs at a certain distance δ≤r from both the RPs and parallel to the straight path. These virtual obstacles are categorized into both positive (right side to the straight line) and negative (left side to the straight line), as shown in Figure 3(b). After that, we determine the pattern of the obstacles and identify the positive and negative obstacles depending on the obstacle centroid. If the centroid of the obstacle is right, then we highlight the obstacle as positive, and in case the centroid is in the left or on the line, we consider the negative obstacle sign as shown in Figure 3(c). The guided samples are arranged parallel to the sample line with a certain distance δg from the line, as shown in Figure 3(d). These lines are adjusted according to the negative virtual obstacles or the points. Depending on the obstacle, the line moves the opposite side, and the guided sample of that side near an obstacle also moves according to the distance of the obstacle to samples.We can now apply the SVM on the sample generated and analyze the results of the SVM learning process. By applying the learning process, the SVM results in support vector set and their weights can decide each point’s region according to positive or negative obstacles. This region also constructs a collision-free separate line in a two-dimensional area, as shown in Figure3(e). We try to determine the line separation from the obstacles by iteratively searching for the next point until Equation (16) results in value zero.
(16)V=∑i∈SαiΛiψiTψ−h.By repeating this, we get the MS path by avoiding the obstacles fromM1 to M2, as shown in Figure 3(f). However, this is a possible path and not the optimal path. We can also terminate the iteration when the V<1.0, exceeding the number of iterations and then threshold values (this case may happen if the distance between the path and obstacles are minimal from both sides). We repeat the same process by adjusting the guided lines (Figure 3(d)) or flipping the positive or negative obstacles to make another pattern to construct several possible paths as shown in Figure 3(g) and choose the best one among them. This process is repeated until all the RPs are visited from M which can complete the traveling tour from BS via RPs to the BS.


### 3.2.4. VRP Selection

The selection of VRPs of the proposed work improves the data acquisition process by minimizing the communications between the SNs and the RPs as shown in Figure4. In this work, the VRPs are the SNs V∈S∧VÚM, which can directly communicate with the MS when it traverses in its range r. The VRPs in DAOSVM is determined based on the available time of MS on the trajectory within the range of the SNs.Figure 4
VRP selection strategies.Initially, we choose a line/curveLp=y=fx∀p∈0≤p<M between any two RPs from M. The fx is in the form of ax2+bx+c. We assume that Sixi,yi be a VRP and we determine the distance to the Lp with a particular point qx,y on it which should be less than r. The shortest distance point on Lp from each SN Sixi,yi is computed as shown in
(17)D=xi−x2+yi−y2=xi−x2+yi−ax2+bx+c2.From Equation (17), we can derive the x coordinate of q by applying the derivation of both sides, i.e., dD/dx to zero. Once we get x, we can easily determine the y coordinate of q. Similarly, this process is repeated with each SN to get all the possible paths between RPs. The following illustration gives a better understanding of the VRP selection process. We assume that Si=3,8 and the equation of the curve as y=x2+8; then, Equation (18) briefs the shortest point on the path La.
(18)D=3−x2+8−x2+22=9−6x+x2+8−x2−92=x4+x2−6x+9.Here, we setdD/dx to 0 and solve for x; finally, it returns x=1. We substitute the value of x in y=x2+8, so that we get y=9. So, the nearest point on the Lp to the Si=3,8 is q=1,9. If the Euclidean distance between the δSi,q is less than or equal to the r, then Si is included to V.


## 3.2.1. Preliminaries of SVM

The SVM is a supervised ML algorithm, which can solve the regression or classification problems with better accuracy [1]. The proposed DAOSVM uses a margin maximization mechanism with the help of SVM to address the issue by constructing an optimal hyperplane.Let us consider the datasetψi,Λii=0n, where ψi is the ith vector in the dataset and Λi is the associated label to the ψi and Λi∈−1,+1. This sample is separated with the hyperplane ωTψ±h=0. In case, the training samples are to be linearly separable, and ω and h has to be satisfied which is shown in
(6)ΛiωTψ±h≥1∀i=0,1,2,⋯,n.By using these parameters, the two classes of samples are separated by the two hyperplanes such asH1:ωTψ±h=+1 and H2:ωTψ±h=−1 and ensures that no other data exists between them. 2/ω represents the objective functions for minimizing the parameters as shown in Equation (7) under the constraints of Equaton (6).
(7)Lω=12ω2.The margin maximization can be obtained by using the Lagrange multipliers, as shown below:(8)maxα∑i=1nαi−12∑i,j=1nψiψjΛiΛjαiαj,subjected to Equation (9) and αi≥0∀i=1,2,⋯,n.
(9)∑i=1nαiΛi=0.The training datasetψi with αi (nonzero) are either of the hyperplanes H1 or H2 and are treated as the support vectors (SV), because these data can only be helpful to compute the parameters. From this, a discrimination function is constructed which is shown in
(10)Λ=signωTψ±h=sign∑i∈SαiΛiψiTψ,whereS represents the set of indices for SV. The kernel trick of SVM is used to classify points which are not linearly separable. Various kernels like polynomial and rbf can be used. But here, we have used a polynomial kernel.


## 3.2.2. RP Selection Strategy

In this phase, the graphG is considered an input and determines the best RP set M. We use MST based clustering mechanism (MST-CM) to determine the best set of RPs, i.e., M with low computational complexity. The initial SNs and base station deployment is illustrated in Figure 2(a). The graph G is constructed by exchanging location information among SNs, and if the distance is less than r between SNs, they are connected with an edge. The G construction is illustrated in Figure 2(b).Figure 2
Steps involved in (a) SNs and BS deployment. (b) WSN graphGS,D. (c) MST using Prim’s algorithms. (d) Clustering the MST. (e) Determine the RP from each cluster.
(a)(b)(c)(d)(e)The MST-CM applies Prim’s algorithm to construct the MST from the WSN graphG. The resultant MST T of the WSN G is shown in Figure 2(c) (there is no difference between the edges with different colors). The MST-CM identifies the longest edges from T using Equation (11) by removing it temporally and compute the next longest node until ζ times.
(11)longijζ=argmaxi,j∈TD.This partition results in the best nearest neighbor set with limited cost. However, removing the most extended node always does not result in the best clustering strategy. So, before removing the node permanently, we use the coefficient of variation (CoV) to each node to decide the efficiency when an extended node is removed while forming the clusters. The CoV is used to measure the consistency, i.e., it can measure how the edge weight (distance between the two nodes) is uniform from one another. The CoV for MST-CM is the ratio of standard deviation (SD) and mean of the edge weights from theT, as shown in
(12)CoVi=σiχ,whereσi is the ith edge SD and χ is the arithmetic mean of the edges in the T. The σi is computed using Equation (13), and χ is computed as shown in Equation (14).
(13)σi=1n∑i=0n−1ei−χ2,whereei is the edge weight of the SN i and χ is
(14)χ=1n∑i=0n−1ei.From Equation (12), it can be seen that decreasing CoV means higher efficiency can be obtained. Before removing any node permanently from the T, we test the CoV. This operation results in ζ+1 clusters from the T. We use a threshold on the CoV to remove the inconsistent edges from the MST (T) to generate the clusters. The cluster set after removing the longest edge depends on the CoV which is illustrated in Figure 2(d). From each cluster ζ, we find the RP using the Equation (15) and it is considered from [38].
(15)Tn=P1−Pr×modP−1×E0−EikE0×ζ,whereP is the probability of choosing the node as RP, E0 is the initial energy of the SN, and ζ is computed as shown in Equation (4). In each round, the SN generates a random threshold value between zero and one and compared it with the Tn to identify the RPs. In the first round of data collection, energy is not affected, but from the second round onwards, the selection of RPs considers energy. This process is illustrated in Figure 2(e).The proposed DAOSVM also involves the reselection of RPs in each round using Equation (15) and energy models. The RP reselection also balances the energy among the SNs. Notably, the SNs near RPs face the same energy hole problem because of the relaying task, if no reselection is involved.


## 3.2.3. MS Path Determination

The MS path construction phase is a critical and challenging phase as it decides the efficiency of the data gathering process, and it is more complicated when the obstacles are considered. This phase is executed after the RPs setM is decided. This algorithm is extended with two phases: (I) deciding the visiting order and (II) avoiding the obstacles in the path.In phase I, visiting order of the RPs by the MS is decided. There are several algorithms in the literature which can choose the optimal and shortest path for the mobile sink using TSP, ACO, etc., but these require complex computations. Here, we plan to propose a lightweight path selection algorithm to fill the necessity of the shortest path using computational geometry methods [14]. This phase takes the M as an input and produces the path as an output. We assume that all the M are having coordinates X and Y in a plane A. Initially, we determine the maximum and minimum X coordinates from the M and assume a virtual line between these coordinates. So, the plane is split into two parts such as above the line and below the line. Then, all the M’s are arranged below the line in ascending/descending order according to the X coordinates and descending/ascending (opposite to the above) order of M’s according to the X coordinates. Then, concatenate both M’s to get the visiting order of RPs. The algorithm detects the path by avoiding the obstacles in phase II.In phase II, the support vector machine algorithm is applied to construct the path which can avoid the environment’s obstacles. The step-by-step path determination algorithm explained through Figure3. Before starting the algorithm, label the positive and negative obstacles. Note that the red dots indicate the negative obstacles, and green circles indicate the positive obstacles from Figure 3. Here, actual obstacles are highlighted, and the triangles indicate the RPs. Figure 3(a) is the primary example considered for illustration of path construction between two RPs by considering two obstacles of the WSN environment.Figure 3
Mobile sink path construction using support vector machine technique. (a) Example of two RPs and two obstacles for path construction. (b) Deployment of virtual obstacles around the RPs. (c) Determine the patterns of the obstacles. (d) Construct guided sample lines parallel to sample lines. (e) Apply the SVM to determine the initial phase of path. (f) Best MS traveling path between two RPs. (g) Feasible paths between the two RPs by avoiding the obstacles.
(a)(b)(c)(d)(e)(f)(g)Initially, we construct a virtual path between the two RPs (M1 and M2), which is a regular straight line between them. Virtual obstacles are set around the RPs at a certain distance δ≤r from both the RPs and parallel to the straight path. These virtual obstacles are categorized into both positive (right side to the straight line) and negative (left side to the straight line), as shown in Figure 3(b). After that, we determine the pattern of the obstacles and identify the positive and negative obstacles depending on the obstacle centroid. If the centroid of the obstacle is right, then we highlight the obstacle as positive, and in case the centroid is in the left or on the line, we consider the negative obstacle sign as shown in Figure 3(c). The guided samples are arranged parallel to the sample line with a certain distance δg from the line, as shown in Figure 3(d). These lines are adjusted according to the negative virtual obstacles or the points. Depending on the obstacle, the line moves the opposite side, and the guided sample of that side near an obstacle also moves according to the distance of the obstacle to samples.We can now apply the SVM on the sample generated and analyze the results of the SVM learning process. By applying the learning process, the SVM results in support vector set and their weights can decide each point’s region according to positive or negative obstacles. This region also constructs a collision-free separate line in a two-dimensional area, as shown in Figure3(e). We try to determine the line separation from the obstacles by iteratively searching for the next point until Equation (16) results in value zero.
(16)V=∑i∈SαiΛiψiTψ−h.By repeating this, we get the MS path by avoiding the obstacles fromM1 to M2, as shown in Figure 3(f). However, this is a possible path and not the optimal path. We can also terminate the iteration when the V<1.0, exceeding the number of iterations and then threshold values (this case may happen if the distance between the path and obstacles are minimal from both sides). We repeat the same process by adjusting the guided lines (Figure 3(d)) or flipping the positive or negative obstacles to make another pattern to construct several possible paths as shown in Figure 3(g) and choose the best one among them. This process is repeated until all the RPs are visited from M which can complete the traveling tour from BS via RPs to the BS.


## 3.2.4. VRP Selection

The selection of VRPs of the proposed work improves the data acquisition process by minimizing the communications between the SNs and the RPs as shown in Figure4. In this work, the VRPs are the SNs V∈S∧VÚM, which can directly communicate with the MS when it traverses in its range r. The VRPs in DAOSVM is determined based on the available time of MS on the trajectory within the range of the SNs.Figure 4
VRP selection strategies.Initially, we choose a line/curveLp=y=fx∀p∈0≤p<M between any two RPs from M. The fx is in the form of ax2+bx+c. We assume that Sixi,yi be a VRP and we determine the distance to the Lp with a particular point qx,y on it which should be less than r. The shortest distance point on Lp from each SN Sixi,yi is computed as shown in
(17)D=xi−x2+yi−y2=xi−x2+yi−ax2+bx+c2.From Equation (17), we can derive the x coordinate of q by applying the derivation of both sides, i.e., dD/dx to zero. Once we get x, we can easily determine the y coordinate of q. Similarly, this process is repeated with each SN to get all the possible paths between RPs. The following illustration gives a better understanding of the VRP selection process. We assume that Si=3,8 and the equation of the curve as y=x2+8; then, Equation (18) briefs the shortest point on the path La.
(18)D=3−x2+8−x2+22=9−6x+x2+8−x2−92=x4+x2−6x+9.Here, we setdD/dx to 0 and solve for x; finally, it returns x=1. We substitute the value of x in y=x2+8, so that we get y=9. So, the nearest point on the Lp to the Si=3,8 is q=1,9. If the Euclidean distance between the δSi,q is less than or equal to the r, then Si is included to V.


## 3.3. Complexity Analysis

The complexity of the first stage is the RP selection which comprises of MST construction, identifying the edges to be removed and RP node selection. The complexity of the MST using Prim’s algorithm isOElogV, where E is the number of edges in the T, and V=n indicates the number of nodes. The complexity to identify the edges to be removed is OE2. The complexity to identify the RPs is On2. Overall, the time complexity of final RP set selection is OElogV+OE2+On2, and the E in T is nn−1/2. After the E value is substituted, the asymptotic complexity of RP set selection is On2logn. The visiting order of M requires Onlogn computational time. The time complexity of path construction by avoiding the obstacles using SVM is OSV3, where SV indicates the number of of support vectors, i.e., SV≈n, so the complexity is treated as On3. The complexity to determine the VRPs set is On2. The overall computational complexity after evaluating all phases is On2logn+On3+On2, and the final asymptotic computational complexity of DAOSVM algorithm is On3.


## 4. Results and Discussion

In this section, we provide the theoretical and simulation results of the proposed model. The proposed DAOSVM and existing eACO-MSPD [18], CMS2TO [19], EARTH [6], and ETDC [20] methods are implemented using the Python simulator (v3.10.0). The packet size is considered 30 bytes, and data communication rate to be 80 kbps to 250 kbps [39]. We consider two scenarios of the network: (i) varying the area size and (ii) varying the number of SNs. In the first scenario (WSN#1), we considered 100×100 m with a maximum of 100 SNs deployed randomly and treated as a small network with few obstacles. In the second scenario (WSN#2), we increased the area size from 100m×100m to 1000m×1000m, and the number of SNs increased up to 1000. The deployment and packet generations in the networks are considered according to Sah et al. [40], and MQTT application protocols considered. In WSN#2, we have increased the number of obstacles. The E0 of all S is equal, i.e., 100 J. The EC of αt and αr are 42 mW (0.042 J) and 29 mW (0.029 J), respectively. We conduct the simulation by varying the communication range between 15 meters and 50 meters. The traveling speed of the MS during the data collection is set to 1 Mbps. The proposed DAOSVM compared with eACO-MSPD, CMS2TO, EARTH, and ETDC algorithms with various performance metrics such as energy consumption (EC), fairness index (FI), network lifetime (NL), buffer utilization (BU), average path length (APL), and packet delivery ratio (PDR).


### 4.1. Average Energy Consumption

The network’s AECμet is calculated as the average energy dissipated from all the SNs until a particular simulation time t is achieved, which is shown in Equation (19). The higher the μet will lower the Nl, and vice versa.
(19)μet=1n∑i=1nEit.We examine the AEC of the proposed and existing algorithms in the two scenarios WSN#1 and WSN#2, as shown in Figure5. In Figure 5(a), the small network with 100 SNs average EC is examined by varying the simulation times between 100 ms and 600 ms. The μe of DAOSVM in WSN#1 is improved over the existing methods eACO-MSPD, EARTH, ETDC, and CMS2TO by 1.5-9 mJ, 2.7-19 mJ, 3.4-27 mJ, and 4.5-33 mJ, respectively, while changing the simulation times. From Figure 5(b), we noticed that the proposed DAOSVM improved the AEC by 2.3-24 mJ compared to eACO-MSPD, 5.1-29 mJ compared to EARTH, 6.5-32 mJ compared to ETDC and 8.4-36 mJ compared to CMS2TO algorithms. The best AEC is achieved in the DAOSVM due to an optimal selection of RPs and obtaining a best path. The VRP selection process also minimizes the energy consumption by avoiding packet transmissions to the RPs when MS is in its range.Figure 5
Average EC of (a) WSN#1 and (b) WSN#2.
(a)(b)


### 4.2. Fairness Index of AEC

Achieving a best AEC of the WSN does not mean that energy is balanced among the SNs in a network. To determine the equal share of a bottleneck is represented the fairness index (FI) of the EC, and it is denoted asF. The FI of any SN EC is in the range between zero and one. The F value nearer to one indicates the best FI, and near-zero means the lower FI. The FI of EC is computed as shown in
(20)F=1−2×σeH−L,where the standard deviation of EC denoted asσe, H=maxEik, and L=minEik. The higher the SD, the lesser the FI value and vice versa. The SD of the EC at tour k is computed using
(21)σe=1n∑i=1nEi−μe2.The FI of the proposed and existing methods is evaluated for WSN#1 and WSN#2 in Figure6. The FI of the first scenario with 100 SNs is compared by varying the simulation time which is shown in Figure 6(a). The FI of DAOSVM in WSN#1 is improved by 0.8-3% compared to eACO-MSPD, 1.6-5% compared to EARTH, 3.1-6.5% compared to ETDC, and 4-9% compared to CMS2TO algorithms. From Figure 6(b), we notice the improvement of the FI over the existing methods eACO-MSPD, EARTH, ETDC, and CMS2TO by 1-4%, 2.5-7%, 3.1-8.5%, and 4.5-10%, respectively, for the WSN#2. The improved FI in the proposed work indicates balancing the energy among the SNs in the network. This improvement is also achieved by considering the best VRP set. This VRP set helps to minimize the data relay between the SNs and RP by transmitting it directly to the MS (in the communication range).Figure 6
Fairness index of EC of (a) WSN#1 and (b) WSN#2.
(a)(b)


### 4.3. Network Lifetime

The network lifetime (NL) is an essential parameter to decide the performance of the WSNs [41]. The NL for the proposed DAOSVM algorithm is computed using Equation (5).We test theNl of DAOSVM, eACO-MSPD, CMS2TO, EARTH, and ETDC by varying SNs between 40 and100 for WSN#1 and 100 and 1000 WSN#2, as shown in Figure 7. After performing the various simulation tests, we confirm that the proposed work outperforms compared with the existing algorithms. Figure 7(a) compares the NL of the DAOSVM with eACO-MSPD, CMS2TO, EARTH, and ETDC. The Nl of the DAOSVM is longer by 208-349 minutes than eACO-MSPD, 231-497 minutes compared to EARTH, 320-564 minutes compared to ETDC, and 396-571 minutes compared to CMS2TO algorithms. Figure 7(b) shows the Nl of DAOSVM which is increased by 120-290 minutes than eACO-MSPD, 199-487 minutes than EARTH, 287-522 minutes than ETDC, and 342-603 minutes than CMS2TO algorithms.Figure 7
Network lifetime of (a) WSN#1 and (b) WSN#2.
(a)(b)


### 4.4. Average Path Length

The average path length (APL) of the MS is calculated as the ratio of total distance traveled by the MS and the number of tours completed, as shown in(22)μt=1φ∑k=1φͷk.The OAPC performs the RP reselection, and path reconstruction can be done depending on the network condition changes. Unlike eACO-MSPD, CMS2TO, EARTH, and ETDC, the proposed DAOSVM algorithm varies the traveling distance based on the number of obstacles and also bring dynamic changes in the WSNs. Theμt is computed in WSN#1 and WSN#2 by varying the number of obstacles in WSNs, as shown in Figure 8. In both scenarios, the path length increases because of avoiding the obstacles over the network. Here, while avoiding the obstacles, the path length increases slightly compared to the Euclidean distance between two RPs. However, the μt with no obstacle is always less than or equal to the existing CMS2TO, eACO-MSPD, EARTH, and ETDC algorithms in both scenarios. In WSN#1, the μt is 120 m when 100 SNs without obstacles is considered. In WSN#2, the μt value is 320 m without obstacles.Figure 8
Average path length of (a) WSN#1 and (b) WSN#2.
(a)(b)


### 4.5. Buffer Utilization

The amount of the buffer used in an unit time is treated as buffer utilization (BU). It is directly proportional to the PDR. The capacity of the buffer also affects RP selection, because the best BU node may improve the data gathering process and reduce loss of data packets. The buffer capacity also affects the number of RPs. Increasing the buffer size will reduce the amount of RPs. Due to this, the tour length of the MS may also be reduced. The average BU of the proposed work and existing works computed at timeT is depicted using
(23)BU=∑i=1npib×n.In both scenarios, if thepi>b, the SN drops the packets. Figure 9 evaluates the BU of the DAOSVM, eACO-MSPD, CMS2TO, EARTH, and ETDC concerning two scenarios WSN#1 and WSN#2 by considering 100 and 1000 SNs, respectively. From Figure 9(a), we observe that the BU of proposed DAOSVM increased by 3-5% as compared to eACO-MSPD, 7-9% as compared to the EARTH, 13-15% as compared to ETDC, and 14-17% as compared to CMS2TO algorithms. Figure 9(b) shows that the DAOSVM algorithm BU increased by 2.5-3.5% than eACO-MSPD, 8.5-12% than EARTH, 14.5-16% than ETDC, and 16-18% than the CMS2TO algorithms. An improvement of BU in DAOSVM over the existing methods can be observed due to the efficient scheduling of the MS during the data collection process. Because of the efficient BU, the packet drop ratio is also reduced in the proposed DAOSVM algorithm.Figure 9
Buffer utilization of (a) WSN#1 and (b) WSN#2.
(a)(b)


### 4.6. Packet Delivery Ratio

It is the ratio of total # of packets received by theS0 which is denoted by R, and the # of packets generated by S (either through the nearest RP/directly to the MS) is indicated using τ during the time T. It is calculated using
(24)PDR=Rτ,whereR≤τ, and the computational strategy of τ is shown in
(25)τ=∑i=1nPSi,wherePSi indicates the number of packets collected from the environment by a SN Si. The higher the PDR indicates the efficient data collection process and vice versa. It also shows the efficiency of MS scheduling over the network and reaches before the buffer overflows. The PDR of the proposed and existing algorithms are compared in Figure 10. This simulation considers the SN data generation similar to all the DAOSVM and existing algorithms. The PDR of the proposed and existing methods recorded during the simulation runs between 100 ms to 600 ms by varying 50 ms gap for both scenarios WSN#1 and WSN#2.Figure 10
Packet delivery ratio of (a) WSN#1 and (b) WSN#2.
(a)(b)The amount of the buffer used in a unit time is treated as buffer utilization (BU).From Figure10(a), we noticed that the proposed DAOSVM increases the PDR by 10-12% than eACO-MSPD, 11-15% than EARTH, 12-17% than ETDC, and 12-19% CMS2TO algorithms in the first scenario. Similarly, the performance improvements are also observed in WSN#2, as shown in Figure 10(b). Here, we find that the OAPC improves the PDR by 8-10% compared to the eACO-MSPD, 9-12% compared to EARTH, 10-14% compared to ETDC, and 11-16% as compared to CMS2TO algorithms.


## 4.1. Average Energy Consumption

The network’s AECμet is calculated as the average energy dissipated from all the SNs until a particular simulation time t is achieved, which is shown in Equation (19). The higher the μet will lower the Nl, and vice versa.
(19)μet=1n∑i=1nEit.We examine the AEC of the proposed and existing algorithms in the two scenarios WSN#1 and WSN#2, as shown in Figure5. In Figure 5(a), the small network with 100 SNs average EC is examined by varying the simulation times between 100 ms and 600 ms. The μe of DAOSVM in WSN#1 is improved over the existing methods eACO-MSPD, EARTH, ETDC, and CMS2TO by 1.5-9 mJ, 2.7-19 mJ, 3.4-27 mJ, and 4.5-33 mJ, respectively, while changing the simulation times. From Figure 5(b), we noticed that the proposed DAOSVM improved the AEC by 2.3-24 mJ compared to eACO-MSPD, 5.1-29 mJ compared to EARTH, 6.5-32 mJ compared to ETDC and 8.4-36 mJ compared to CMS2TO algorithms. The best AEC is achieved in the DAOSVM due to an optimal selection of RPs and obtaining a best path. The VRP selection process also minimizes the energy consumption by avoiding packet transmissions to the RPs when MS is in its range.Figure 5
Average EC of (a) WSN#1 and (b) WSN#2.
(a)(b)


## 4.2. Fairness Index of AEC

Achieving a best AEC of the WSN does not mean that energy is balanced among the SNs in a network. To determine the equal share of a bottleneck is represented the fairness index (FI) of the EC, and it is denoted asF. The FI of any SN EC is in the range between zero and one. The F value nearer to one indicates the best FI, and near-zero means the lower FI. The FI of EC is computed as shown in
(20)F=1−2×σeH−L,where the standard deviation of EC denoted asσe, H=maxEik, and L=minEik. The higher the SD, the lesser the FI value and vice versa. The SD of the EC at tour k is computed using
(21)σe=1n∑i=1nEi−μe2.The FI of the proposed and existing methods is evaluated for WSN#1 and WSN#2 in Figure6. The FI of the first scenario with 100 SNs is compared by varying the simulation time which is shown in Figure 6(a). The FI of DAOSVM in WSN#1 is improved by 0.8-3% compared to eACO-MSPD, 1.6-5% compared to EARTH, 3.1-6.5% compared to ETDC, and 4-9% compared to CMS2TO algorithms. From Figure 6(b), we notice the improvement of the FI over the existing methods eACO-MSPD, EARTH, ETDC, and CMS2TO by 1-4%, 2.5-7%, 3.1-8.5%, and 4.5-10%, respectively, for the WSN#2. The improved FI in the proposed work indicates balancing the energy among the SNs in the network. This improvement is also achieved by considering the best VRP set. This VRP set helps to minimize the data relay between the SNs and RP by transmitting it directly to the MS (in the communication range).Figure 6
Fairness index of EC of (a) WSN#1 and (b) WSN#2.
(a)(b)


## 4.3. Network Lifetime

The network lifetime (NL) is an essential parameter to decide the performance of the WSNs [41]. The NL for the proposed DAOSVM algorithm is computed using Equation (5).We test theNl of DAOSVM, eACO-MSPD, CMS2TO, EARTH, and ETDC by varying SNs between 40 and100 for WSN#1 and 100 and 1000 WSN#2, as shown in Figure 7. After performing the various simulation tests, we confirm that the proposed work outperforms compared with the existing algorithms. Figure 7(a) compares the NL of the DAOSVM with eACO-MSPD, CMS2TO, EARTH, and ETDC. The Nl of the DAOSVM is longer by 208-349 minutes than eACO-MSPD, 231-497 minutes compared to EARTH, 320-564 minutes compared to ETDC, and 396-571 minutes compared to CMS2TO algorithms. Figure 7(b) shows the Nl of DAOSVM which is increased by 120-290 minutes than eACO-MSPD, 199-487 minutes than EARTH, 287-522 minutes than ETDC, and 342-603 minutes than CMS2TO algorithms.Figure 7
Network lifetime of (a) WSN#1 and (b) WSN#2.
(a)(b)


## 4.4. Average Path Length

The average path length (APL) of the MS is calculated as the ratio of total distance traveled by the MS and the number of tours completed, as shown in(22)μt=1φ∑k=1φͷk.The OAPC performs the RP reselection, and path reconstruction can be done depending on the network condition changes. Unlike eACO-MSPD, CMS2TO, EARTH, and ETDC, the proposed DAOSVM algorithm varies the traveling distance based on the number of obstacles and also bring dynamic changes in the WSNs. Theμt is computed in WSN#1 and WSN#2 by varying the number of obstacles in WSNs, as shown in Figure 8. In both scenarios, the path length increases because of avoiding the obstacles over the network. Here, while avoiding the obstacles, the path length increases slightly compared to the Euclidean distance between two RPs. However, the μt with no obstacle is always less than or equal to the existing CMS2TO, eACO-MSPD, EARTH, and ETDC algorithms in both scenarios. In WSN#1, the μt is 120 m when 100 SNs without obstacles is considered. In WSN#2, the μt value is 320 m without obstacles.Figure 8
Average path length of (a) WSN#1 and (b) WSN#2.
(a)(b)


## 4.5. Buffer Utilization

The amount of the buffer used in an unit time is treated as buffer utilization (BU). It is directly proportional to the PDR. The capacity of the buffer also affects RP selection, because the best BU node may improve the data gathering process and reduce loss of data packets. The buffer capacity also affects the number of RPs. Increasing the buffer size will reduce the amount of RPs. Due to this, the tour length of the MS may also be reduced. The average BU of the proposed work and existing works computed at timeT is depicted using
(23)BU=∑i=1npib×n.In both scenarios, if thepi>b, the SN drops the packets. Figure 9 evaluates the BU of the DAOSVM, eACO-MSPD, CMS2TO, EARTH, and ETDC concerning two scenarios WSN#1 and WSN#2 by considering 100 and 1000 SNs, respectively. From Figure 9(a), we observe that the BU of proposed DAOSVM increased by 3-5% as compared to eACO-MSPD, 7-9% as compared to the EARTH, 13-15% as compared to ETDC, and 14-17% as compared to CMS2TO algorithms. Figure 9(b) shows that the DAOSVM algorithm BU increased by 2.5-3.5% than eACO-MSPD, 8.5-12% than EARTH, 14.5-16% than ETDC, and 16-18% than the CMS2TO algorithms. An improvement of BU in DAOSVM over the existing methods can be observed due to the efficient scheduling of the MS during the data collection process. Because of the efficient BU, the packet drop ratio is also reduced in the proposed DAOSVM algorithm.Figure 9
Buffer utilization of (a) WSN#1 and (b) WSN#2.
(a)(b)


## 4.6. Packet Delivery Ratio

It is the ratio of total # of packets received by theS0 which is denoted by R, and the # of packets generated by S (either through the nearest RP/directly to the MS) is indicated using τ during the time T. It is calculated using
(24)PDR=Rτ,whereR≤τ, and the computational strategy of τ is shown in
(25)τ=∑i=1nPSi,wherePSi indicates the number of packets collected from the environment by a SN Si. The higher the PDR indicates the efficient data collection process and vice versa. It also shows the efficiency of MS scheduling over the network and reaches before the buffer overflows. The PDR of the proposed and existing algorithms are compared in Figure 10. This simulation considers the SN data generation similar to all the DAOSVM and existing algorithms. The PDR of the proposed and existing methods recorded during the simulation runs between 100 ms to 600 ms by varying 50 ms gap for both scenarios WSN#1 and WSN#2.Figure 10
Packet delivery ratio of (a) WSN#1 and (b) WSN#2.
(a)(b)The amount of the buffer used in a unit time is treated as buffer utilization (BU).From Figure10(a), we noticed that the proposed DAOSVM increases the PDR by 10-12% than eACO-MSPD, 11-15% than EARTH, 12-17% than ETDC, and 12-19% CMS2TO algorithms in the first scenario. Similarly, the performance improvements are also observed in WSN#2, as shown in Figure 10(b). Here, we find that the OAPC improves the PDR by 8-10% compared to the eACO-MSPD, 9-12% compared to EARTH, 10-14% compared to ETDC, and 11-16% as compared to CMS2TO algorithms.


## 5. Conclusion

Construction of the optimal MS traveling path and selecting the best RP set is a challenging task during the data collection in WSNs. It is more challenging in case of obstacles over the network in the traveling route. This paper uses the support vector machine to construct the obstacle-aware mobile sink path. In this, we also compute the best RPs and VRPs set and reselection, where VRPs are the nodes that can directly transmit their data to the MS. The RP set is selected and reselected using the minimum spanning tree-based clustering mechanism. The VRP selection mainly depends on the path between the RPs and the distance between the SNs, and the route should be within the communication range of MS. The proposed DAOSVM is compared with eACO-MSPD, CMS2TO, EARTH, and ETDC using a simulation run with various performance metrics such as AEC, FI, network lifetime, BU, average path length, and packet delivery ratio. These comparisons concluded that the proposed work outperforms the existing algorithms. In a future work, we consider the velocity control and waiting time at VPs are considered while scheduling the mobile sink.



---

*Source: 4242740-2022-08-25.xml*