1 Introduction

In recent years, wireless sensor networks (WSN) have been wildly used and deployed. The sensor nodes in WSN function to sense and gather the information of the field and are utilized in scenarios such as environment monitoring, battlefield surveillance, intrusion detection, etc. [2–4]. According to Gartner, a US market-research firm, there will be approximately 26 billion devices on the Internet of Things (IoT) by the year 2020 [5]. As the main component of the IoT, WSN could bring more than 30 billion-dollar revenue. Therefore, large amount of funds have been invested in WSN research and development by governments, NGOs and many MNCs such as Google, Cisco, Apple, etc. Up to present, there have been many successful cases. For example, Liu et al. have deployed more than 330 nodes in the wild for forest surveillance [6] and the system was dubbed as GreenOrbs. Similarly, more than 42 Tiger reserves based on WSN have also been established in India [2].

With the rapid development of unmanned vehicles and unmanned aircrafts, sink nodes can be deployed on these unmanned mobile devices and act as mobile sinks. These mobile sinks extend the mobile and dynamic property of WSNs [7]. In traditional WSNs with static sinks, sensors are equipped with batteries and forward data through multi-hops to the sink [8, 9]. Thus, the nodes close to the sink will deplete their batteries faster than the other nodes due to higher data relaying load [10]. As a result, this will lead to unexpected network disconnection and shortening of network lifetime [11]. But with the introduction of mobile sink, data can be collected in a single-hop manner while mobile sink moves through a sensing field. Thus many studies have shown that mobile sink can balance the traffic load, prolong the network’s lifetime, and improve connectivity and positioning capabilities as well [12, 13].

However, the benefits stated above are mainly based on the premise that a comprehensive and effective solution exists for the routing design of the mobile sink [14]. Efficient mobile sink routing protocol should be able to find the shortest path. The reason is that the energy of the mobile sink is limited and a short path can reduce energy consumption of the mobile sink. On the other hand, a short path can also make the mobile sink collect all the data in a short time. In a word, minimization of latency is of great importance, especially in real-time applications.

In this paper, we consider a WSN with multiple static sensor nodes and one mobile sink, and subsequently research how to find the shortest path to the mobile sink. This problem can be formulated into a travelling salesman problem (TSP) [15] when the communication range of the nodes are neglected. In such case, we have to seek the shortest path that traverses each sensor node. The mobile sink can visit every node along this path and at the same time collect the monitor data. Quite a number of relevant approaches have been proposed in the literature. Gupta et al. and Xing et al. [16, 17] studied on a rendezvous-based data collection approach which takes a subset of sensor nodes as the rendezvous points where the mobile sink stays and gathers the data from the sensors. When mobile base station arrives at the rendezvous point, the information of the sensor node will be transmitted to the mobile base station. Similarly, Liu et al. [18] searches the rendezvous points within a hop bound.

Considering the communication range of the mobile sink and the sensor nodes, the problem of the best path planning can be transformed to a special case of travelling salesman problem with neighborhood (TSPN) [19, 20]. In this case, the mobile sink does not need to visit the location of every sensor node on its path. It just needs to pass the point which is involved in communication range of one or more sensor nodes. As demonstrated in [21], the path designed to consider the communication radius will be more flexible and the length of the path can be reduced, while greatly improving the performance of the network.

In this paper, we introduce a novel routing algorithm for mobile sink. The algorithm fully considers the communication ranges of sensor nodes and the mobile sink, and functions based on VD-PSO. In this algorithm, the coordinates of each RP on the path of the mobile sink are treated as a dimension of one particle. Thus the dimensionality of this particle will be determined by the number of RPs on the path. We can see that each particle is a solution, and a swarm of particles formulate a solution space. With the evolution proceeding, we are able to obtain the optimal solution which is the shortest path of the mobile sink.

To the best of our knowledge, people rarely consider how to find the shortest path in the non-uniformly distributed WSN. However in practice, we have observed that the distribution of sensor nodes is always uneven, especially in wide use. E.g. in military surveillance and environmental monitoring [22], random throwing of sensor nodes is widely applied. As in protection of wall painting in Italy, the locations of the sensor nodes are all dependent on the location of the paint [23]. In these cases, it is hard to control the topology of the network and make it homogenized. Moreover, this non-uniform distribution will make the number of RPs in each path quite different, that is to say the dimensionality of each particle is different. This will make it impossible to express the particle as before, and the traditional iterative formula is also unsuitable for our algorithm. In this scenario, our approach applies variable dimension (VD) to each particle, and adjusts the iterative formula to update it.

During the running time, we discover that the dimensionality of one particle could become closer. That is to say there is more RPs in small areas. Since this is detrimental to energy efficiency, we set a RP merging strategy to deal with this situation. In addition, we also use reverse order and simulated annealing algorithm to improve the convergence speed and precision of the solution. Our simulation results show that VD-PSO can find the shortest path effectively and perform efficiently, especially in non-uniform network deployment.

The main contributions of this paper are summarized as follows:

  • We design a routing algorithm for the mobile sink based on variable dimension PSO. It describes each possible path as a particle with variable dimension and finally finds out the shortest path for the mobile sink.

  • We propose a special strategy to deal with the update proceeding of the particles with different dimensionality. This method makes our algorithm work well in non-uniform network.

  • We further improve the performance of the algorithm by incorporating reverse order and simulated annealing method.

The remainder of this paper is organized as follows. Section 2 formulates the problem we aim to resolve. Section 3 divides the main problem into some subproblems, describes key steps of our proposed algorithm for the problem and illustrates on how to optimize it. Simulation procedure and result analysis are provided in Section 4. Finally, Section 5 concludes the whole paper.

2 Problem formulation

As mentioned previously, the energy of the mobile sink is limited. Thus, if the transceiver circuit of the mobile sink keeps working all the time during the movement, its battery power will run out quickly. Therefore, in practice, we often put the transceiver in sleep mode and wake it up only when the mobile sink arrives at a RP on its path. In this way, the problem of finding the best path for the mobile sink can be divided and formulated as two subproblems:

  1. (1)

    How to choose the location of the RP?

  2. (2)

    How to decide the shortest path which passes through each RP?

According to [21], we know that the first one is a NP-hard problem, and the second subproblem is NP-hard as well. In other words, finding the best travel path of the mobile sink in a large scale WSN is extremely difficult, and it has no polynomial-time solution.

  1. A.

    Finding the best traveling path of the mobile sink

We consider one WSN composed of N static sensor nodes. These N nodes are deployed randomly in an area of R X *R Y . R X and R Y are the ranges of horizontal and vertical coordinates of the deployment area respectively. The communication range of the mobile sink and sensor nodes are all R.

We set T v as one of the paths that the mobile sink travels through. The path consists of multiple RPs and the lines between them. As a result, we can formulate the path as an ordered set of RPs. We denote

$$ {v}_i=\left\{\left({x}_i,{y}_i\right)\left|0<{x}_i<{R}_X,\right.0<{y}_i<{R}_Y\right\} $$

as the coordinate of RP i. A path of mobile sink to move can be characterized by a unique ordered setT v  : 〈v 1, v 2, ⋯v n 〉, where |T v | = n is the number of RPs on the path. And d ij is the distance between the RP i and j.

$$ {d}_{iX}={\displaystyle \underset{k\in X,k\ne i}{ \min }}\left({d}_{ik}\right) $$
(1)

d iX is the shortest distance between node i and point set X. d(T v ) is the length of the path.

We can define the task of finding the best path as:

  1. a.

    Find the shortest path T opt of which the starting-point is S and the traversing finally returns to S.

  2. b.

    The mobile sink must pass through the coverage of each node at least once, that is, for each sensor node i there should be d iTopt  ≤ R.

  1. B.

    Traditional PSO

Particle Swarm Optimization (PSO) is a kind of optimization algorithm based on swarm intelligence. It was proposed in 1995 by Kennedy and Eberhart, who were American psychologist and electrical engineer respectively [24]. In traditional PSO, each particle keeps on learning from past experience of itself and other member’s experience to approach the optimal solution.

During running time, each particle will trace two optimal solutions at the same time. One is pbest, the best solution that each particle has found until now, and the second is gbest, the best solution that all particles have obtained currently. We assume that the location of i-th article in n-dimensional space is X i  = (x i1, x i2,  ⋯ , x in ). The speed of i-th particle is V i  = (v i1, v i2,  ⋯ , v in ), and the best location it has got is pbest i  = (p i1, p i2, ⋯p in ). The best location of the group is gbest i  = (p g1, p g2, ⋯p gn ).

Each particle updates its speed and location according to formula (2) and (3).

$$ {v}_{id}^{k+1}=\omega \times {v}_{id}^k+{c}_1\times {r}_1\times \left( pbes{t}_{id}^k-{x}_{id}^k\right)+{c}_2\times {r}_2\times \left( gbes{t}_{id}^k-{x}_{id}^k\right) $$
(2)
$$ {x}_{id}^{k+1}={x}_{id}^k+{v}_{id}^k $$
(3)

\( {x}_{id}^k \): The location of d-th dimension of particle i at time k.

\( {v}_{id}^k \): The speed of d-th dimension of particle i at time k.

ω: Inertia weight.

c 1: The step-length for the particle which follows to the best location of itself.

c 2: The step-length that the particle which follows to catch the best location of the group.

r 1 andr 2: Random values between [0,1].

In addition, we set speed interval as [v min, v max] and location interval [x min, x max] to limit the movement of the particle.

As one of the excellent optimization algorithms, PSO has features of both simplicity and fast convergence. However, this traditional PSO cannot be used directly to solve the routing problem of the mobile sink based on our subsequent analysis.

3 Finding the best path with VD-PSO

As analyzed earlier, our goal is to find a traveling path for the mobile sink, and the mobile sink will visit each sensor node at the RPs on the path. In order to solve this problem by PSO, the key question lies in how to establish the relationship between the particle and the traveling path. In other words, a possible path should be represented as a particle that is one feasible solution. Our proposed approach uses a variable dimension particle to express one possible path, and the location of every RP on the path becomes one dimension of the particle. Since every particle may have different dimensionality, there is no way to know in advance how many RPs exist on the path. This results in the fact that the update formula (2) and (3) cannot be applied directly.

In order to solve this routing problem based on PSO, it is required to address the following questions:

  1. a.

    Since we do not know how many RPs should be used, we cannot use the traditional PSO with fixed dimensionality. Thus the question lies in how to represent a feasible solution using PSO method in our problem.

  2. b.

    In a large scale WSN, how to generate an initial particle reasonably and effectively is an important issue.

  3. c.

    Because the dimensionality of each solution may be different, we must find out how to update the speed and location of each particle.

  4. d.

    As the number and the location of RPs change, we need to search in multidimensional solution space of PSO. In this condition, what can be done to accelerate the algorithm and perform more effectively?

The following sections will provide solutions for these problems one by one.

  1. A.

    Solution Presentation and Update Procedure

We can regard one of the traveling paths as a sequence of connected line segments and use v i  = {(v ix , v iy )|0 < v ix  < R X , 0 < v ix  < R Y } as the coordinates of the RP i on the path. We can then indicate the k-th travelling path by an ordered set of location coordinates\( {T}_{\left(k,{n}_k\right)}:\left\langle {v}_{k1},{v}_{k2},\cdots {v}_{k{n}_k}\right\rangle \) , where n k is the number of RPs on path k. Because for each particle the n k may be different, as compared with traditional PSO, the particle here has variable dimensionality, and the number of RPs equals the dimensionality of the solution.

As discussed previously, during running time of PSO, each solution will track the best position of each particle (pbest) and the best position of the group (gbest). n k in each particle is different, and thus we cannot use the traditional formula to update the speed and location of the particle. Herein, we propose a novel method that enables the particle to trace the pbest and gbest efficiently.

When one dimension of the particle needs to update its speed and location, the following can be performed: at first, search every dimension and find the nearest dimension (position) in pbest and gbest. We can subsequently update the dimension of the particle based on these three position vectors. The detailed flow is given below.

We assume that the dimension j of particle m:\( {T}_{\left(m,{n}_a\right)} \) needs to update the speed and location, and the best solution of its own is \( pbes{t}_{\left(m,{n}_b\right)} \) until now. Now we search every dimension of \( pbes{t}_{\left(m,{n}_b\right)} \) to find the dimension which is nearest to dimension j and record it as k. At the same time if the best solution of the group is \( gbes{t}_{\left({n}_c\right)} \), we search it to find the dimension which is nearest to dimension j and record it as l. Thereafter, we update the speed and location of particle m according to the formula (4) and (5).

$$ {v}_{mj}^{i+1}=\omega \times {v}_{mj}^i+{c}_1\times {r}_1\times \left( pbes{t}_{mk}^i-{x}_{mj}^i\right)+{c}_2\times {r}_2\times \left( gbes{t}_l^i-{x}_{mj}^i\right) $$
(4)
$$ {x}_{mj}^{i+1}={x}_{mj}^i+{v}_{mj}^i $$
(5)

The trace method is illustrated in Fig. 1.

  1. B.

    Algorithm acceleration

Fig. 1
figure 1

Updating process of tracing the nearest dimension

Full size image

During the running time, each particle will search in the multi-dimension solution space using the update method described above. Within the updating process of the particle, the spatial position of each particle will approximate to the spatial position of the global optimum particle step by step. As a result, we notice that some of the dimensions of one particle will get increasingly closer, which means the optimal solution of TSPN tends to have less dimensionality. Moreover, the less dimensionality of the particle has, the shorter length of the path will be. Nevertheless, in this process, as some dimensions get closer, it also means that the RPs on the path will be closer. This would lead to the result of which several RPs are located in a very small area. Our simulation results also show that this phenomenon would happen, and in some cases, it occurs more frequently.

On the other hand, as mentioned, in a real application scenario, while the mobile sink collects the packets along the route, the transceiver of it does not work all the time. Generally, it only wakes up and starts to work at the moment when the mobile sink arrives at each RP. When the mobile sink leaves the PR, the transceiver will be put into sleep mode or closed in order to save energy. Hence, if the RPs gets too close, the mobile sink would wake up and close the transceiver frequently. This is not a good solution with regard to energy-saving and system efficiency.

In order to prevent this phenomenon from happening, we propose a strategy to merge adjacent RPs. In this strategy, we select the midpoint of segment constituting these two RPs as a potential RP that can be called pRP, if the distance between two RPs is less than a preset threshold. If over this potential RP the mobile sink’s working region can cover the entire sensor nodes that original two RPs can cover, we replace the two adjacent RPs with the potential RP and delete these two RPs from route of the mobile sink. In order to introduce this strategy in our algorithm, we need to analyze this strategy initially and solve two key problems thereafter: The first is how close the adjacent RPs should be for them to be merged. The second is how to choose the replace point on the segment connecting two adjacent RPs.

Regarding the first problem, we find that when two adjacent RPs get close enough, there will be a large overlapping area in their working region. Hence if we select one point in the overlapping area of these two RPs as a new RP, the mobile sink’s working area, at this point, would contain the sensor nodes including two original RPs with high probability. (Based on this idea and aiming to simplify the analysis, we use one point on the segment that connects two adjacent RPs as the new RP to replace original two RPs.)

We first adopt the geometric method to analyze this problem. We use the segment’s distance dist seg as the standard of measurement. While dist seg is less than a preset thresholddist THR , we merge these two RPs. In order to analyze this problem efficiently, let v i  : (x i , y i ) and v j  : (x j , y j )be the coordinates of two RPs which are close to each other. Let L be the length of the segment between v i andv j . Generally, we can assume that the working region of a mobile sink is the same, so it can be seen as a circle with radius R. We set the coverage area (working region) of RP v i and v j as C i and C j , similarly, set the overlap area as C ij . In Fig. 2(a) to Fig. 2(c), it is obvious to find that C ij  = 0 when dist seg  = 2R. And the formulaC ij  = πR 2 holds when dist seg  = 0. Whilst 0 < dist seg  < 2π, πR 2 > C ij  > 0.holds.

Fig. 2
figure 2

Overlapping area with different dist seg

Full size image

Therefore, when C ij is smaller, the probability of finding a suitable coverage region to contain the overlap region of two adjacent RPs is lower. According to the basic geometry theory, this overlapping region can be seen as a combination of two shapes of which each shape can be considered as a fan minus a triangle. Hence we can obtain

$$ \begin{array}{l}\alpha =2 \arccos \left(\frac{L/2}{R}\right)\\ {}{C}_{ij}=2\left(\frac{\alpha }{360}\pi {R}^2-\frac{L}{2}\sqrt{R^2-{\left(\frac{L}{2}\right)}^2}\right)\end{array} $$

In this formula, α is the central angle degree corresponding to the fan. Based on this formula, we can illustrate the overlapping area vs. dist seg , as shown in Fig. 3. From Fig. 2(b), it is evident that dist seg is proportional to normalization of the overlapping area. Taking into consideration of algorithm complexity and success rate of merge strategy, we choose the dist seg as the finaldist THR when C ij  = 0.8πR 2 holds.

Fig. 3
figure 3

Selection of dist THR

Full size image

For the second problem, let v k  : (x k , y k ) be the midpoint of segment that connects two RPs above and we still consider the working region of mobile sink as a circle with radius R. According to Fig. 4(a) to Fig. 4(c), it is evident that the circle does not cover all overlapping region if we choose an arbitrary point not on the segment between v i and v j as new RP. Consequently, we should choose a point on the segment connecting v i and v j as the new RP. However, the question now lies in how to determine which point is the best point. In fact, the node number covered by working region of v i and v i is usually not the same. Hence if the working region of v i covers more nodes, it should select one point closer to v i as the new RP and vice versa. Unfortunately, this step needs extensive computation. To simplify the algorithm implementation, we use the midpoint v k of the line directly as the new RP.

  1. C.

    Reverse order

Fig. 4
figure 4

Selection of new RP

Full size image

In basic PSO Formula 2, in order to improve the precision of the algorithm, we often restrict the variation range of particle’s speed within a certain interval[v min, v max]. However at the same time, these restrictive measures also narrow the search scope of the particle. At the beginning of the operation, the initial path is generated randomly to increase the search scope. In a large scale WSN, almost every initial path is far away from the optimal path. If we restrict the speed of the particle, it will take long time to approach the optimal solution. On the other side, if we do not restrict the speed of the particle, it is difficult for the final path to avoid being trapped into local optimum.

In this paper, we introduce reverse order strategy of parthenogenesis algorithm (IPGA) to improve searching speed of the particle without sacrificing the accuracy. In each iteration, each particle performs local tuning according to reverse order strategy. The results of simulation show that this strategy not only increases the searching speed of particles, but also reduces the time complexity of iterations.

In our algorithm, a particle is constituted of an ordered set of location coordinates. Reverse order strategy is equivalent to exchanging the order of some part of this set with a probability of P. Here the single-point reverse strategy is adopted. Initially, we generate random integer n i and n j for particle \( {T}_{\left(m,{n}_a\right)} \), of which length is n a . Thereafter, the order of the coordinates between n i and n j is reversed to generate a new particle \( {T}_{\left(m,{n}_a\right)}^{\ast } \).

  1. D.

    Simulated annealing algorithm

In traditional PSO algorithm, the particle converges fast at the beginning. However in subsequent iterations, convergence speed would slow down as the distance between particles becomes shorter. This would lead the particle to fall into a local optimal solution. In order to strengthen the search ability of particles, we introduce a simulated annealing method into the iterative process of VD-PSO. A bad solution (particle) will be accepted with a certain probability in each iteration.

After completing the previous steps of updating and merging, each particle evaluates the new and the old solutions and then it will accept a bad solution with a certain probability according to Formula (6).

$$ p=\left\{\begin{array}{l}1\kern13em {C}_1\\ {} \exp \left(-\frac{E\left({T}_{\left(m,{n}_m\right) new}\right)-E\left({T}_{\left(m,{n}_m\right) old}\right)}{T(t)}\right)\kern1em {C}_2\end{array}\right. $$
(6)
$$ T\left(t+1\right)=k\times T(t) $$
(7)

In Formula (6):

  • case C1: if \( E\left({T}_{\left(m,{n}_m\right) new}\right)<E\left({T}_{\left(m,{n}_m\right) old}\right) \)

  • case C2: if \( E\left({T}_{\left(m,{n}_m\right) new}\right)\ge E\left({T}_{\left(m,{n}_m\right) old}\right) \)

\( {T}_{\left(m,{n}_m\right) new} \) and \( {T}_{\left(m,{n}_m\right) old} \) : The particle before and after the previous steps of updating and merging.

\( E\left({T}_{\left(m,{n}_m\right) new}\right) \) and \( E\left({T}_{\left(m,{n}_m\right) old}\right) \) :The fitness value of these two particles.

p: The probability of accepting the new particle.

T : The temperature of iteration.

Formula (6) shows that, if the fitness value of the new particle is lower than the old one, we replace the old particle by the new particle with probability 1. If the fitness value of the new particle is greater than the old one, we replace the old particle by the new particle with probability p.

Formula (7) shows the annealing temperature of the algorithm. At the beginning of iteration, we set a larger initial temperature T(t 0), and k is positive and slightly less than 1. As the iteration continues, temperature T becomes lower gradually. Therefore the replacement probability also becomes lower when the new particle is worse than the old one. In the subsequent stages of iteration, the replacement probability approximates to zero since the temperature is very low.

  1. E.

    Evaluation Function

The goal of this paper is to find out the best travelling path for the mobile sink. The length of the best path should be the shortest one. Therefore, we use the length of the path as the fitness value of the particle. The smaller the fitness value is, the better the particle would be and vice versa.

  1. F.

    Algorithm Flow

We describe VD-PSO Algorithm for TSPN as follows:

  • Step1. Initialization of TSPN problem: Initialize the parameters of the TSPN problem, such as the sensor nodes number of the WSN, the size of simulation region, etc.

  • Step2. Initialization of VD-PSO algorithm: Set the number of particles, set the learning factors and a random velocity, then set generation t = 0. Each particle represents a random feasible solution.

  • Step3. Calculate each particle’s fitness value and update the pbest and gbest.

  • Step4. For every dimension, each particle searches and finds the nearest dimension in its pbest and gbest, updates the velocity and position according to Formula (4) and (5) based on these two nearest dimensions then generates one new particle.

  • Step5. Calculate the new and the old particles’ fitness value for every particle. If the new particle’s fitness value is less than the old one, use the new particle to replace the old particle.

  • Step6. Each particle searches every dimension of itself to find whether the distance between two adjacent dimensions is less than the threshold dist THR . If so, combine these two dimensions using the adjacent RPs merge strategy and generate a new particle.

  • Step7. Calculate the new and old particles’ fitness value again. If the new particle’s fitness value is less than the old one, use the new particle to replace the old particle.

  • Step8. Each particle reverses some part of itself with some preset probability P and then generates one new particle.

  • Step9. Calculate the new and old particles’ fitness value again. If the new particle’s fitness value is less than that of the old one, use the new particle to replace the old particle.

  • Step10. Update each particle’s fitness value and update the pbest and gbest.

  • Step11.t = t + 1, If t < M, go to step 4, and continue to iterate, or else, stop iterations. Now the gbest is the best solution which the algorithm has found.

4 Simulation

The simulation scene of the proposed approach is a square area of about 500 m on each side. The coordinate of the start point (SP) of the mobile sink is (250,250), that is, the start point is located at the center of the simulation scene. We assume that the working range of the mobile sink can be changed from 20 m to 100 m. There are 50 to 100 sensor nodes to be deployed randomly in the simulation region. We perform the simulation with different sensor node number for 50 times, and average all the results together.

In order to evaluate the performance of our algorithm, we mainly study the length of the path that the mobile sink travels. The path starts from the SP (x f , y f ) and returns to this point after visiting each RP. As the path length becomes shorter, the mobile sink spends less time to gather data or recharge each node of the entire network. At the same time, the shorter path length means the lower energy consumption of the mobile sink and better maintainability of the whole system. Thus the length of the traveling path is crucial to evaluate the performance of this kind of TSPN algorithm.

In our simulation, we study the length of the path in two cases:

  1. (1)

    With the fixed working range of the mobile sink, we deploy different number of sensor nodes in the simulation field.

  2. (2)

    With the fixed number of sensor nodes, we change the working range of the mobile sink.

In order to evaluate the algorithm performance, we perform simulation using three different algorithms, TSP, COM (Combination Algorithm) and our proposed VD-PSO algorithm. TSP expresses the shortest path length that the mobile sink goes through each sensor node only once. COM algorithm originates from literature [12] and it combines the data collection while these sensor nodes can be covered by a RP’s communication range.

Initially, the working range of the mobile sink is set to 50 m and 100 m, 50 to 100 sensor nodes are deployed in the simulation field. In each case, we record the length of the path which is obtained by each algorithm.

As shown in Fig. 5 and Fig. 6, when the number of the sensor node increases, all path lengths obtained using these three algorithms increase. However, we can observe that the path length of TSP is the longest one among the three. This is due to fact that the TSP algorithm does not consider the working range of the mobile sink, and therefore the mobile sink must traverse the location of each sensor node. In other words, the location of each sensor node is exactly the same as the PR’s location in TSP algorithm. Thus as the number of the sensor nodes increases, the path length increases substantially.

Fig. 5
figure 5

Path length with different numbers of sensor nodes (R = 50 m)

Full size image
Fig. 6
figure 6

Path length with different numbers of sensor nodes (R = 100 m)

Full size image

The performance of COM is better than TSP algorithm. This is because COM algorithm can merge some PRs according to overlapping degree of the mobile sink’s working range, and COM algorithm can gradually reduce the number of RPs. Based on this, COM algorithm can reduce the path length to some extent. Therefore the algorithm performance is improved partially.

According to Fig. 5, we can observe that the VD-PSO algorithm improves the performance significantly. When there are 100 sensor nodes in the network and the working radius is set to 50 m, the path length obtained by VD-PSO algorithm decreases nearly a quarter than COM. Figure 6 demonstrates the similar result, in which VD-PSO algorithm reduces the path length by about 45 %. In general, with the fixed working range of mobile sink, VD-PSO algorithm can greatly reduce the length of the path. This also means that VD-PSO algorithm can achieve much better performance.

In another setting, 50 and 100 sensor nodes are deployed in the same field, and the working range of the mobile sink is increased from 20 m to 100 m gradually. As illustrated in Fig. 7, the path length of TSP is the same as the value when working radius is fixed. For COM algorithm, it can merge more RPs as the working range of the mobile sink increases. Consequently, the path length decreases, since the working range is shortened. Based on the simulation configuration above, we can observe that the performance of VD-PSO is the best. It is able to achieve approximately 20 % performance improvement as compared with COM. Similarly, as shown in Fig. 8, VD-PSO algorithm can obtain 50 % performance improvement when compared with COM algorithm. This confirms the effectiveness and efficiency of our proposed algorithm.

Fig. 7
figure 7

Path length with different communication radius(N = 50)

Full size image
Fig. 8
figure 8

Path length with different communication radius(N = 100)

Full size image

5 Conclusion

In this paper, we propose a Variable Dimensions Particle Swarm Optimization algorithm to resolve the TSPN problem in WSN with a mobile sink. With this routing algorithm, the mobile sink could collect the data efficiently, and it will be helpful for us to locate the target [25, 26]. In the algorithm, we adopt a variable dimensions particle to represent the feasible solution of TSPN.

During the VD-PSO algorithm runtime, each particle needs to trace the best solutions of local and global optimal solutions which have different dimensions. Herein, we creatively adopt the nearest particle dimension fitting method to solve the updating problem and this significantly accelerates the searching speed of the particles. In the iteration process, the simulated annealing algorithm and reverse order method is introduced into VD-PSO algorithm. These two methods greatly improve the global searching ability of the VD-PSO algorithm and enable the particles to escape from the local extremum.

Simulation results demonstrate that the VD-PSO algorithm of this paper can solve the routing problem of the mobile sink in WSN effectively. The algorithm has the advantages of both fast convergence speed and good stability. This study is significant for mobile sink routing design in large scale WSN, particularly the scenario of non-uniform deployment.