Sage Journals: Discover world-class research

Abstract

A wireless sensor network is a network consisting of wireless sensor nodes. There are usually requirements that need to be met when deploying a wireless sensor network, one being the placement of nodes. Due to placement requirements and limited node transmission range, a network might be partitioned initially. Therefore, additional relay nodes are added to the network to form an interconnected network. In this article, the minimum relay nodes placement problem in wireless sensor networks is addressed. This problem addresses the placement of relay nodes: the minimum number needed and where the nodes should be placed. The problem is formulated as a Steiner tree problem with minimum Steiner points and a bounded edge length problem, which is NP-hard. In this article, we present a variable-dimension meta-heuristic based on particle swarm optimization called multi-space particle swarm optimization to address the problem. We tested multi-space particle swarm optimization using randomly generated instances of the Steiner tree problem with minimum Steiner points and a bounded edge length problem of varying sizes and found that multi-space particle swarm optimization is effective in addressing the Steiner tree problem with minimum Steiner points and a bounded edge length problem.

Keywords

Relay nodes placement swarm-based meta-heuristic particle swarm optimization variable dimension Steiner tree problem

Introduction

Wireless sensor nodes are programmable sensors that are usually battery-powered and capable of simple data processing and communicating with each other through wireless links to form a wireless sensor network (WSN). A WSN eliminates the need for expensive and troublesome network cabling and makes placement cheap and flexible. There are usually requirements that need to be met when deploying a WSN. One such requirement is the placement of nodes. For example, sensing nodes must be placed at certain locations to allow them to gather data from the data sources, and a base station node might need to be placed in a special control room. Due to the placement requirements and limited node transmission range, a network might be partitioned initially. To form an interconnected network, additional nodes called relay nodes are necessary. While wireless sensor nodes are generally regarded as inexpensive devices, deploying a network with a huge number of nodes or a network to cover a large geographic area still incurs considerable cost; therefore, proper planning needs to be done prior to network deployment to minimize cost while satisfying the other requirements.

The minimum relay nodes placement (MRP) problem can be categorized according to the dimension of the space nodes to be placed. In the two-dimensional (2D) problem, nodes are to be placed in the 2D Euclidean space R² (plane) while in the three-dimensional (3D) problem, nodes are to be placed in the 3D Euclidean space R³ (space). The MRP problem can be further categorized into unconstrained and constrained¹ placement. In unconstrained placement, relay nodes can be placed anywhere in space. In contrast, in constrained placement, relay nodes are to be placed only at certain locations. Both versions of the problem find their uses in different applications. In this article, we consider the unconstrained MRP problem in 2D WSNs and attempt to solve the problem with a novel meta-heuristic based on particle swarm optimization (PSO).²

Our contributions are as follows:

First, a variable-dimension meta-heuristic based on PSO called the multi-space particle swarm optimization (MSPSO) is proposed for use in problems where candidate solutions (for an instance of the problem to be solved) could be of different lengths (having different numbers of dimensions).

Second, the MRP problem in 2D WSNs is modeled as a Steiner tree problem with minimum Steiner points and bounded edge length (STP-MSPBEL) problem and addressed by first transforming it into a different problem that we refer to as the dual problem. To the best of our knowledge, this is the first article to discuss the variable length property for candidate solutions of an instance of the STP-MSPBEL problem, transform the problem into the dual problem, and solve it (the primal problem) using a PSO-inspired optimization method.

This article is organized as follows. First, related works are discussed in section “Related works.” In section “MSPSO to address the STP-MSPBEL problem,” we describe the problem that we attempt to solve and our proposed optimization method. In section “Results and discussion,” our proposed optimization method is used to solve several randomly generated instances of the STP-MSPBEL problem to demonstrate its effectiveness. Finally, we offer conclusions in section “Conclusion.”

Related works

In this article, the MRP problem in 2D WSNs is approached. We formulate the problem as a STP-MSPBEL problem. Research studies in the literature that have approached the STP-MSPBEL problem and other similar problems can be categorized into two main categories. In the first category, works are very similar to one another as they are all based on the minimum spanning tree (MST) heuristic. In the second category, meta-heuristics are used to address the problem. In Lin and Xue,³ the MST heuristic was proposed for the STP-MSPBEL problem, and it was shown that it has a lower bound or worst-case performance of 5. However, the authors of Chen et al.⁴ showed that the algorithm in Lin and Xue³ is actually a four-approximation algorithm. In Lin,⁵ the terminal Steiner tree with bounded edge length (TSTBEL) problem, which is similar to the STP-MSPBEL problem, was introduced. In Cheng et al.,⁶ the authors proposed two heuristics for the STP-MSPBEL problem. One has a performance ratio of 3, while the other has a performance ratio of 2.5. The three-approximate algorithm is similar to the MST heuristic with the exception that degree-3 Steiner points are added to the tree for every subset of three terminals a, b, and c if there exists a point s within the three terminals prior to applying the MST heuristic. In Liu et al.,⁷ the one-connected and two-connected MRP problems were formulated. The one-connected MRP problem (MRP-1) is similar to the TSTBEL problem. The authors employed the minimum disc cover approximation scheme⁸ to initially find an approximate minimum disc cover set and then interconnect the centers of the disks using the 2.5-approximate STP-MSPBEL heuristic. In Lloyd and Xue,⁹ the single-tiered and two-tiered relay node placement problems were discussed. The single-tiered version of the problem is essentially a more generalized version of the STP-MSPBEL problem in that relay nodes and terminal points have different transmission ranges. The MST heuristic was proposed for use in the single-tiered relay node placement problem. The authors proved that the MST heuristic is actually a polynomial-time seven-approximation algorithm for the problem. Two-tiered sensor relay placement was considered in Hao and colleagues,^10,11 in which constant-factor approximation algorithms for several versions of the problem are proposed. In Shishira et al.,¹² the authors provide an extensive survey on optimization algorithms for cloud environments based on three popular meta-heuristic techniques: ant colony optimization (ACO), PSO, and genetic algorithms (GAs). In Harris,¹³ a stochastic algorithm based on the simulated annealing¹⁴ meta-heuristic was proposed to solve the STP problem. As with any other meta-heuristic, there is no guarantee that the optimal solution is ever found. However, the authors found an interesting aspect, which is that the time needed to compute a good solution is much less than that required by the exact algorithm by Cockayne and Hewgill. In Ma and Liu,¹⁵ a swarm-based meta-heuristic emulating the concept of a fish swarm searching for food is proposed to solve the STP problem. The authors encode particles as trees. However, we found that the problem solved is not really the STP problem but the multiple-destination routing (MDR) problem. Similar to Ma and Liu,^15,16 the authors proposed solving the MDR problem with PSO. The authors introduced mutation to introduce new tree structures to the particle population. The MDR problem was approached instead of the STP problem.

In an instance of the STP-MSPBEL problem, candidate solutions may have different lengths. In the classical PSO, all candidate solutions for an instance of the problem to be solved have the same length. There are few works in the literature on solving problems where candidate solutions can be of different lengths with PSO. However, the idea of applying PSO to solve these problems has been proposed before in other problems. In Pappala and Erlich,¹⁷ a variable-dimension optimization approach based on PSO was proposed to tackle the unit commitment problem (UCP). In Yan and Osadciw,¹⁸ dimension-adaptive particle swarm optimization (DA-PSO) was proposed and demonstrated to solve the Weibull mixture model density estimation problem.

MSPSO to address the STP-MSPBEL problem

Problem formulation

In the MRP problem in 2D WSNs, a set of nodes (their locations in 2D Euclidean space) consisting of both base station and sensing nodes is given. This constitutes the requirement of the placement of nodes during a WSN deployment. Sensing nodes are to collect data from sites and send them to base station nodes. However, due to placement requirements, a sensing node could be placed far from its base station node. As a result, relay nodes might be needed to help relay packets. The following assumptions are made for our study:

There is only one base station node in the entire network.

Base station and sensing nodes can relay data packets.

All nodes have the same maximum transmission range.

Two nodes can communicate if they are within transmission range of each other.

Using assumption (2), because sensing and base station nodes can relay data packets, whether a node is a base station node or a sensing node is not important; hence, we simply treat them as a single type of node. For convenience, we refer to both base station and sensing nodes simply as demand points for the remainder of this article. Based on these assumptions, the MRP problem can then be formulated as a STP-MSPBEL³ problem. In the STP-MSPBEL problem, given a set V of points and a constant R, one interconnects nodes in V with a graph such that (1) the number of points added (called Steiner points) to interconnect all points in the graph (demand and Steiner points) is minimal, and (2) the length of the edge between any two points is bounded by the constant R. In the STP-MSPBEL problem, there is an edge between two points a and b in the graph (i.e. a and b are interconnected) if and only if the Euclidean distance between point a and point b is less than R, that is, $d (a, b) = \sqrt{{(x_{a} - x_{b})}^{2} + {(y_{a} - y_{b})}^{2}} \leq R$ , where $(x_{a} - y_{a})$ and $(x_{b} - y_{b})$ are the coordinates of points a and b, respectively. In the MRP problem, the value of R in the STP-MSPBEL problem corresponds to the maximum transmission range of the nodes. The STP-MSPBEL problem is NP-hard, and the decision version of the problem was proven to be NP-complete in Lin and Xue.³

Multi-space particle swarm optimization

The STP-MSPBEL is a variable-dimension problem. To solve such a problem, we propose the use of a variable-dimension meta-heuristic based on PSO. We name the proposed method as MSPSO.

MSPSO is extended from PSO. The difference between MSPSO and the classical PSO is that in the classical PSO, the search space is of a fixed number of dimensions, while in MSPSO, the search space is the “universe” and consists of different search spaces of different numbers of dimensions. In this article, MSPSO is applied to solve the STP-MSPBEL problem; hence, the entire process is called MSPSO-STP-MSPBEL. To aid in understanding, an overview of the entire MSPSO-STP-MSPBEL process is shown in Figure 1.

Figure 1.

Overview of the MSPSO-STP-MSPBEL process.

The degree of a node is the number of edges incident with that node. In the classical STP problem, Steiner points are of degree 3. According to Lin and Xue,³ in the STP-MSPBEL problem, Steiner points can be of degree 2 or 3. However, in Theorem 1, we state that for the STP-MSPBEL problem, Steiner points can have a degree of at most 5.

Theorem 1

In the STP-MSPBEL problem, Steiner points can have a degree of at most 5.

Proof

Before we prove that Steiner points can have a degree of at most 5 in the STP-MSPBEL problem, we first analyze a similar problem in Chen et al.¹⁹ Figure 2 was used in Chen et al.¹⁹ as an example to prove that the Steinerized MST has a worst-case performance of 4. In Figure 2, the black-colored circles are the demand points. In Figure 2(a), the empty circle is the Steiner point of the optimal solution, and ε is a small positive real number such that the distance from the center to each vertex is within R. In Figure 2(b), the empty circles are the Steiner points of the Steinerized MST. As mentioned in Chen et al.,¹⁹ the tree in Figure 2(a) is the optimal solution; it must be a valid solution. We see that the Steiner points in the optimal tree have a degree of 5. In this article, Figure 3 is used to prove that there are no Steiner points of degree 6 in the STP-MSPBEL problem. Figure 3 presents the regular hexagon. In Figure 3, the white-colored circles are the demand points, while the gray-colored circle is the Steiner point. Initially, we suppose that there is a Steiner point of degree 6 as shown in Figure 3(a). However, in a regular hexagon, the distance between any two vertexes is the same. In that case, the Steiner point is redundant, and thus we arrive at a contradiction. By removing the Steiner point, we could have Figure 3(b). Therefore, we can prove that in STP-MSPBEL, Steiner points have a degree of at most 5.

Figure 2.

An input instance to the STP-MSPBEL to prove that the MST heuristic has a worst-case performance of 4 in Chen et al.¹⁹

Figure 3.

A Steiner point in STP-MSPBEL has a degree of at most 5.

The MSPSO-STP-MSPBEL proceeds as follows. Given an instance of the STP-MSPBEL problem, we first try to locate the degree-3 or higher Steiner points. For the sake of convenience, we refer to degree-3 or higher Steiner points simply as degree-3+ Steiner points. To locate the degree-3+ Steiner points, the notion of anchor Steiner points is used. Anchor Steiner points are Steiner points, and together with demand points, they are used as input to the MST construction process to construct a candidate solution to the STP-MSPBEL input problem instance. In other words, anchor Steiner points are candidates for degree-3+ anchor Steiner points. When the anchor Steiner points are located, the remaining non-anchor/regular Steiner points can easily be determined by Steinerizing the edges in the MST formed by the demand points and anchor Steiner points. We name them as anchor Steiner points because they serve as anchors to allow other regular Steiner points of degree-2 to be determined.

The following reasons dictate the use of anchor Steiner points in our article. (1) Because the number of degree-3+ anchor Steiner points is much less than the total number of anchor Steiner points in the optimal solution, it is wiser to search only for the degree-3+ anchor Steiner points rather than to search for all anchor Steiner points because assuming that all anchor Steiner points in a candidate solution have equal probability of matching an anchor Steiner point in the optimal solution, the probability that a candidate solution (a set of anchor Steiner points) is an exact match to the optimal solution decreases with increasing number of anchor Steiner points in the optimal solution. In other words, it is easier for a candidate solution to match only the degree-3+ anchor Steiner points rather than to match all anchor Steiner points. (2) By determining a candidate solution using the MST construction process, a candidate solution is guaranteed to (a) have the minimum number of Steiner points needed among all spanning trees of demand points and anchor Steiner points, and (b) the candidate solution is valid, that is, the tree is spanning (interconnected). The working principle behind MSPSO is simple: MSPSO merely needs to address a subset of points, the anchor Steiner points, that is, how many of them there are and where they should be placed. MSPSO needs no complex algorithm for how to form a Steiner tree and ensure that all points are connected.

The minimum number of anchor Steiner points needed to Steinerize an edge of length l is given in equation (1). In MSPSO, degree-3+ anchor Steiner points are searched for using anchor Steiner points. A particular solution (a set of anchor Steiner points) is only a candidate for the optimal solution. The ideal candidate solution is such that anchor Steiner points are coincident with the degree-3+ anchor Steiner points in the optimal solution. In a candidate solution to an instance of the STP-MSPBEL problem, the total number of anchor Steiner points is given in equation (2)

$\begin{array}{l} minimum number of anchor Steiner \\ points needed to steinerize an edge = {\begin{matrix} \frac{l (e)}{R} - 1 & if R < l (e) \\ 0 & if R \geq l (e) \end{matrix} \end{array}$ (1)

$n_{Steiner points} = n_{anchor Steiner points} + n_{regular Steiner points}$ (2)

By determininig the solution to an instance of the STP-MSPBEL problem by first locating the degree-3+ anchor Steiner points, we in fact have converted this problem to another problem, which is referred to as the dual problem.

Definition 1: the primal problem (the STP-MSPBEL problem)

Given a set V of terminal points and a constant R, an interconnected graph with the following properties is sought: (1) the number of added points initially not in set V (called anchor Steiner points) should be minimal, and (2) the length of the edge between any two points is bounded by R.

Definition 2: the dual problem

Given a set V of terminal points, the graph with minimum cost that is determined by equation (3) is sought. Extra nodes not in set V (which we call anchor Steiner points in this article) may be added to the graph to reduce cost

$cost = \sum_{e \in E} (\frac{l (e)}{R} + 1) + n_{anchor Steiner points}$

where E is the set of edges in the MST spanned by the demand points and anchor Steiner points, l(e) is the length of an edge $e \in E$ , and $n_{anchor Steiner points}$ is the number of anchor Steiner points in the tree.

Now that the notion of anchor Steiner points is introduced, we state in Theorem 2 that the fitness of a candidate solution is varied only by anchor Steiner points.

Theorem 2

A candidate solution’s fitness is varied only by anchor Steiner points.

Proof

Regular Steiner points are determined by Steinerizing edges in the MST formed by demand points and anchor Steiner points. Because demand points are fixed (their quantity and their position are given), only the anchor Steiner points (their quantity and their position) can affect the MST formed and thus affect the fitness of a candidate solution.

In PSO, a particle’s position in the search space represents a particular solution to the instance of the problem to be solved. In MSPSO-STP-MSPBEL, a particle is encoded as a set of points in 2D Euclidean space, and a point is represented with a pair of numbers that corresponds to their coordinates in the 2D Euclidean space. For example, a candidate solution {(3, 4), (6, 8)} represents that there are two anchor Steiner points and that they are located at coordinates (3, 4) and (6, 8), respectively. Another candidate solution {(2, 5), (6, 7), (4, 6)} specifies that there are three anchor Steiner points and that they are located at coordinates (2, 5), (6, 7), and (4, 6), respectively.

As mentioned earlier, a candidate solution to an instance of the STP-MSPBEL problem could have between zero and infinite anchor Steiner points. To avoid an infinite search, the range limit of the number of dimensions of the spaces is first determined. The maximum value of this range is set according to the following observations: the MST heuristic can be used to get an approximate to the optimal solution to a given instance of the STP-MSPBEL problem. As explained earlier, we try to solve the dual problem to solve the primal problem. In the dual problem, we are to locate degree-3+ anchor Steiner points in the primal problem using anchor Steiner points. Because $n_{Steiner points} \geq n_{anchor Steiner points}$ , there is no point in allowing a candidate solution to the dual problem to have more anchor Steiner points than the estimate of the number of anchor Steiner points in the primal problem (obtained using the MST heuristic) since $n_{Steiner points} = n_{anchor Steiner points} + n_{regular Steiner points}$ ; the resulting candidate solution to the primal problem will have more anchor Steiner points than the solution obtained using the MST heuristic. Because $n_{Steiner points}$ obtained from using the MST heuristic will be quite high, this will result in a long runtime since candidate solutions might initially have long lengths. That is because candidate solutions are searched for unnecessary spaces of high dimension. To help reduce the runtime of our optimization method, the following point is used: in the STP, a full Steiner topology/tree has at most k = N − 2 anchor Steiner points, where N is the number of demand points in an input instance. Because anchor Steiner points are used to search for these points, it is intuitive that we limit the number of dimensions allowed for a particular space to at most N − 2 anchor Steiner points. The minimum of this range is set to 0. The range of the number of dimensions of a particular space is thus as given in equation (4)

$\begin{matrix} range of number of dimensions of a particular space \\ = \\ [0, min (N - 2, number of Steiner points determined \\ by the MST heuristic on the demand points)] \end{matrix}$ (4)

where N is the number of demand points in an input instance.

Initialization of particles

After the range of the number of dimensions of spaces is determined, we generate particles that randomly vary in the number of dimensions. Then, for each particle in the swarm, a number r within the range of dimensions of the spaces (equation (4)) is randomly generated. Each particle then generates r anchor Steiner points. We state in Theorem 3 that anchor Steiner points should be located inside the convex hull formed by the demand points. Hence, anchor Steiner points are generated randomly such that they are located within the convex hull formed by the demand points. The velocity of the particles are set to 0 or initialized randomly.

Theorem 3

All Steiner points (anchor and non-anchor) should be located within the convex hull formed by the demand points.

Proof

There are three points in a triangle; if a fourth point is outside the triangle formed by the three points, a shorter MST could be formed by placing the fourth point along the edge of the triangle or inside the triangle. One method is to place the fourth point along one of the edges of the triangle. Meanwhile, this can be easily extended to other given numbers of points.

Fitness evaluation

In PSO, after each iteration, the fitness values of the particles (recall that the position of a particle represents a particular solution) are evaluated. Because we address the primal problem using the dual problem, evaluation of a particle’s fitness becomes complex. To help understand how this process works, we first review the course of action of a particle as shown in Figure 4. In the dual problem, a particle consists of a set of anchor Steiner points. Initially, a particle consists of an empty set. During the initialization phase, each particle generates a random number r. Each particle then randomly generates r Steiner points (these are called anchor Steiner points) and adds them to the set. After an iteration, the fitness values of the particles are evaluated. The cost function to be used for evaluation of particles is as shown in equation (2). However, one cannot evaluate the fitness of a particle directly using equation (2), as a particle consists of anchor Steiner points only (their number and locations). The remaining non-anchor Steiner points need to be determined before equation (2) is applicable. To determine the remaining non-anchor Steiner points, the MST over all nodes needs to be available. By emulating/mimicking the MST construction process and recording the number of points needed to Steinerize an edge in the MST in the process, we can determine the total number of anchor Steiner points needed for the primal problem. The detailed algorithm for determining the total number of anchor Steiner points needed for the primal problem is presented in Algorithm 1. Algorithm 1 works as follows. Suppose there are initially 10 nodes, from node 0 to node 9. Initially, there are 10 groups of nodes, one group for each node. Additionally, we suppose that nodes 0 and 1 are close to each other and that nodes 8 and 9 are close to each other. Therefore, we can group nodes 0 and 1 together and nodes 8 and 9 together. This leaves eight groups. Now, we have eight groups that are all not connected to each other. Then, we try to join up all eight groups so that in the end, there is only one group. We start with one of the groups, try to find which group it is closest to, and join them with a line. Thus, supposing that group 0 is closest to group 9, we can draw a line between them. However, do not forget that this line may be longer than R, in which case, after drawing this line, we would to place non-anchor Steiner points onto the line. Finally, repeat until all the initial terminal nodes are connected.

Figure 4.

The course of action of a particular particle.

Algorithm 1. Algorithm for determining the total number of anchor Steiner points in a candidate solution for the primal problem.
Given: (1) demand points (2) anchor Steiner pointsOutput: The total number of anchor Steiner points in a candidate solution for the primal problem 1. Assign every node $v_{i}$ to different groups, $gr p_{i} : gr p_{i} \leftarrow v_{i}$ , $0 < \| V \| - 1$ 2. Combine groups that are interconnected into one resulting in a lesser number of n groups, $n \leq \| V \|$ . 3. Initial $numNonAnchorSteinerPointsNeeded \leftarrow 0$ . 4. $While (n > 1) / / tree not spann 4 . ing$ . a. Let $gr p_{0}$ be the source group: $gr p_{src}$ . Get the group among $n - 1$ other groups with the shortest distance to $gr p_{src}$ , call this group the destination group, $gr p_{dst}$ . b. Calculate the number of anchor Steiner points needed to Steinerize the shortest edge between $gr p_{src}$ and $gr p_{dst}$ . Let this answer be $k$ . c. $numNonAnchorSteinerPointsNeeded \leftarrow numNonAnchorSteinerPointsNeeded + k$ d. $n \leftarrow n - 1$ //there is now one group less since we combined $gr p_{src}$ and $gr p_{dst}$ 5. End while 6. Return $numNonAnchorSteinerPointsNeeded + number of anchor Steiner points$

Algorithm 1. Algorithm for determining the total number of anchor Steiner points in a candidate solution for the primal problem.

Given: (1) demand points (2) anchor Steiner pointsOutput: The total number of anchor Steiner points in a candidate solution for the primal problem 1. Assign every node

v_{i}

to different groups,

gr p_{i} : gr p_{i} \leftarrow v_{i}

0 < | V | - 1

2. Combine groups that are interconnected into one resulting in a lesser number of n groups,

n \leq | V |

. 3. Initial

numNonAnchorSteinerPointsNeeded \leftarrow 0

. 4.

While (n > 1) / / tree not spann 4 . ing

. a. Let

gr p_{0}

be the source group:

gr p_{src}

. Get the group among

n - 1

other groups with the shortest distance to

gr p_{src}

, call this group the destination group,

gr p_{dst}

. b. Calculate the number of anchor Steiner points needed to Steinerize the shortest edge between

gr p_{src}

and

gr p_{dst}

. Let this answer be

k

. c.

numNonAnchorSteinerPointsNeeded \leftarrow numNonAnchorSteinerPointsNeeded + k

n \leftarrow n - 1

//there is now one group less since we combined

gr p_{src}

and

gr p_{dst}

5. End while 6. Return

numNonAnchorSteinerPointsNeeded + number of anchor Steiner points

Updating of particle positions part I: updating of the space that particles belong to

After an iteration of the classical PSO meta-heuristic, the best position obtained by the entire swarm (gbest) and particles’ personal best locations (pbest) are updated as necessary. In the classical PSO, particles explore the search space and converge over time, guided by the fitness function toward pbest or gbest. In MSPSO-STP-MSPBEL, we want the particles to behave similarly. However, in the STP-MSPBEL problem, the fitness of a particle is governed by two factors: (1) the number of anchor Steiner points a particle specifies and (2) the positions of these anchor Steiner points. In other words, compared to the classical PSO, not only do we have to update the values of different variables, we also need to update the number of variables (the length) of a solution. In this section, we discuss how the number of anchor Steiner points a particle specifies is updated.

The number of anchor Steiner points in a particle is discrete/integer-valued. The classical PSO was designed to solve continuous problems; hence, a discrete method of updating the number of anchor Steiner points of particles is required. A concept similar to the one employed in the jumping frog optimization (JFO)²⁰ designed for discrete optimization problems is adopted. A random number is generated in the range $[0, 1)$ and the action to take depends on the range the random number falls into. In the range $[0, w)$ , a particle stays in the current space or explores the neighboring space. In the range $[w, w + c_{1})$ , a particle gets attracted to and moves toward the space gbest is located in. In the range $[w + c_{1}, 1)$ , a particle gets attracted to and moves toward the space gbest is located in. The number of anchor Steiner points thus contributes to one dimension of the problem. In the $[0, w)$ range, another random variable in $[0, 1)$ is generated to see whether it should remain in the current space or explore the neighboring space. If this variable falls within $[0, PROB_EXPLORE_NEIGHBORING_SPACE)$ , then the particle explores the space of one dimension lower or higher with equal probability; otherwise, the particle remains in the same space. The reason for the reuse of the same parameters is as follows: in the classical PSO, particles are attracted toward new positions in space in the directions of pbest and gbest, and in MSPSO, we want the particles to behave similarly with respect to the variable number of anchor Steiner points.

Updating of particle positions part II: updating of anchor Steiner point velocities and positions

In this subsection, we discuss how the velocities and positions of anchor Steiner points are updated. As candidate solutions are from different spaces, velocity and position update are non-trivial compared to the classical PSO. During the velocity update of particles, the current position $v^{i}$ could have a different number of dimensions compared to pbest or gbest. However, particles from different spaces can share information with each other. Hence, we employ component-wise updating similar to that proposed in Pappala and Erlich¹⁷ for the UCP. Figure 5 shows the component-wise updating of variables. Component-wise updating is used because particles share information with each other only between identical dimensions. Particles do not anticipate or borrow information from alien or unknown space dimensions.

Figure 5.

Component-wise updating of variables.

The velocity of a particle is updated in two steps. In the first step, we update it toward pbest. Then in the second step, it is updated toward gbest. The position of a particle is updated by simply adding its previous position to the updated velocity. In this process, if the velocity has a longer length (higher number of dimension) than the number of anchor Steiner points specified by the particle, the higher dimensions of the velocity are simply discarded. Alternately, if there are more anchor Steiner points compared to the number of dimensions of the velocity, random velocities are generated for the extra anchor Steiner points.

Transform solution of the dual problem to solution of the primal problem

The MSPSO meta-heuristic is only used to determine the anchor Steiner points. Anchor Steiner points are approximates of degree-3+ Steiner points in the optimal solution for the input instance of the STP-MSPBEL problem. The remaining non-anchor/regular Steiner points still need to be determined. The detailed algorithm to determine the non-anchor Steiner points is described formally in Algorithm 2. First, initial demand points, anchor Steiner points, and the transmission range of nodes are given. Second, we find a source group, destination group, and the shortest edge between them. Third, every statement in the inner while loop in the algorithm are followed to Steinerize a straight line.

Algorithm 2. Algorithm for determining the non-anchor Steiner points.
Given: (1) demand points (2) anchor Steiner points (3) the transmission range of nodes, ROutput: A minimal spanning tree involving the given nodes.
1. Group nodes that are interconnected into a larger group. 2. While (number of groups, $(n > 1)$ )//tree not spanning a. Select the first group as the starting group $gr p_{src}$ . b. Find the group closest in Euclidean distance to $gr p_{src}$ and name it the destination group $gr p_{dst}$ . c. Get the shortest edge between $gr p_{src}$ and $gr p_{dst}$ . Name the point of the edge in $gr p_{src} as$ and the point of the edge in $gr p_{dst} asp t_{dst}$ . d. While ( $d (p t_{src}, p t_{dst}) > R$ )) i. $dif f_{x} = p t_{dst} . x - p t_{src} . x;$ ii. $dif f_{y} = p t_{dst} . y - p t_{src} . y;$ iii. $ratio = R \div d (p t_{src}, p t_{dst});$ iv. Add $(p t_{src} . x + ratio \times dif f_{x}, p t_{src} . y + ratio \times dif f_{y})$ as a non-anchor Steiner point e. End while f. $n \leftarrow n - 1$ //there is now one less group since we combined $gr p_{src}$ and $gr p_{dst}$ 3. End while

Algorithm 2. Algorithm for determining the non-anchor Steiner points.

Given: (1) demand points (2) anchor Steiner points (3) the transmission range of nodes, ROutput: A minimal spanning tree involving the given nodes.

1. Group nodes that are interconnected into a larger group. 2. While (number of groups,

(n > 1)

)//tree not spanning a. Select the first group as the starting group

gr p_{src}

. b. Find the group closest in Euclidean distance to

gr p_{src}

and name it the destination group

gr p_{dst}

. c. Get the shortest edge between

gr p_{src}

and

gr p_{dst}

. Name the point of the edge in

gr p_{src} as

and the point of the edge in

gr p_{dst} asp t_{dst}

. d. While (

d (p t_{src}, p t_{dst}) > R

)) i.

dif f_{x} = p t_{dst} . x - p t_{src} . x;

ii.

dif f_{y} = p t_{dst} . y - p t_{src} . y;

iii.

ratio = R \div d (p t_{src}, p t_{dst});

iv. Add

(p t_{src} . x + ratio \times dif f_{x}, p t_{src} . y + ratio \times dif f_{y})

as a non-anchor Steiner point e. End while f.

n \leftarrow n - 1

//there is now one less group since we combined

gr p_{src}

and

gr p_{dst}

3. End while

Results and discussion

We implemented MSPSO-STP-MSPBEL in C/C++ in Ubuntu 15.10. To demonstrate the feasibility of the proposed method, we generate random instances of the STP-MSPBEL problem, use our program to obtain approximate solutions to these instances, and compare our results with those obtained by the MST heuristic and approximation algorithm. Random instances of the problem of varying input size (number of demand points) were generated with two instances for each input size. In all instances, we assume node placement in a square region of 1000 units by 1000 units. In PSO, the number of particles (swarm size) determines how many different agents are used to solve a given input instance. If more particles are used, the probability of finding a better solution increases. Due to the inherent complexity of the STP-MSPBEL problem, 2000 particles were used in all instances. To allow sufficient iterations for particles to search for a good solution, the MSPSO-STP-MSPBEL was programmed to terminate after 500 iterations. As PSO is based on the concept of iterative search, if a low value of number of iterations is used, the particles might not converge by the time the search process is terminated. In all instances, we assume that the transmission range of all nodes R = 25 units. The values of w, c1, and c2 are set as 0.2, 0.35, and 0.45, respectively. We run the program on a system with an Intel Core i5-5200U processor and 8 GB of RAM.

In general, we found that our program can address the generated instances with better results compared to those obtained using the MST heuristic. For practical input instance size, we found that our program has a fast runtime. For instance, referring to Table 4, for an input instance size of 200 demand points, our program was able to obtain a runtime of just over 3 h. Runtime is an important criterion in this article. If one algorithm takes an unacceptable amount of time to search for a good solution, it becomes useless. The lower runtime also indicates the lower computation complexity. From Tables 1 to 4, we observed that the runtime accelerates with increasing input instance size. This is because the fitness evaluation process of a particle requires that the MST construction process be emulated/mimicked, and this takes (n²) time, where n is the number of nodes. In our program, we employed the traditional method of updating the MST when anchor points are added, removed, or changed in position. If a more efficient method of updating the MST is used, such as dynamic MST construction, better runtime performance is possible. However, implementing such an efficient MST updating process algorithm is not the focus of this article. Meanwhile, we compared our program with an approximation algorithm, in which we first select a critical node from the uncovered sensor nodes and then determine the location of the relay node based on the principle of preferring to cover the sensor node closer to the critical node. We found that our program has better performance compared to the approximation algorithm. Moreover, PSO is an iterative search technique, and thus one should not compare its runtime to simple heuristics such as the MST heuristic. For example, with no termination criteria, PSO continues to search for the optimal solution continuously, even if it has already found it.

Table 1.

Summary of three instances with 25 demand points.

Instance	1	2
Number of relay nodes in the solution obtained by our program (including anchor Steiner points)	123	111
Number of relay nodes in the solution obtained by the MST heuristic	129	117
Number of relay nodes in the solution obtained by the approximation algorithm	124	113
Improvement	4.65%, 0.80%	5.13%, 1.77%
Number of anchor Steiner points by our program	6	5
Runtime of the our program	59.5 s	58.1 s
Runtime of the MST heuristic	62.6 s	62.2 s
Runtime of the approximation algorithm	61.3 s	61.1 s
Runtime improvement	4.95%, 2.93%	6.59%, 4.9%

MST: minimum spanning tree.

Table 2.

Summary of three instances with 50 demand points.

Instance	1	2
Number of relay nodes in the solution obtained by our program (including anchor Steiner points)	159	171
Number of relay nodes in the solution obtained by the MST heuristic	166	173
Number of relay nodes in the solution obtained by the approximation algorithm	165	171
Improvement	4.22%, 3.63%	1.2%, 0%
Number of anchor Steiner points by our program	7	7
Runtime of our program	421.5 s	463.3 s
Runtime of the MST heuristic	474.7 s	522.7 s
Runtime of the approximation algorithm	465.2 s	499.1 s
Runtime improvement	11.2%, 9.39%	11.36%, 7.17%

MST: minimum spanning tree.

Table 3.

Summary of three instances with 100 demand points.

Instance	1	2
Number of relay nodes in the solution obtained by our program (including anchor Steiner points)	212	228
Number of relay nodes in the solution obtained by the MST heuristic	221	234
Number of relay nodes in the solution obtained by the approximation algorithm	219	230
Improvement	4.07%, 3.19	2.98%, 0.86%
Number of anchor Steiner points by our program	9	9
Runtime of our program	2092.0 s	1962.2 s
Runtime of the MST heuristic	2346.6 s	2314.4 s
Runtime of the approximation algorithm	2241.7 s	2246.1 s
Runtime improvement	10.84%, 6.68%	15.21%, 12.64%

MST: minimum spanning tree.

Table 4.

Summary of three instances with 200 demand points.

Instance	1	2
Number of relay nodes in the solution obtained by our program (including anchor Steiner points)	267	277
Number of relay nodes in the solution obtained by the MST heuristic	281	286
Number of relay nodes in the solution obtained by the approximation algorithm	278	280
Improvement	4.98%, 3.96%	3.15%, 1.07%
Number of anchor Steiner points by our program	14	11
Runtime of our program	9074.5 s	11060.3 s
Runtime of the MST heuristic	12456.4 s	13146.1 s
Runtime of the approximation algorithm	10234.1 s	11902.4 s
Runtime improvement	27.14%, 11.33%	15.86%, 7.08%

MST: minimum spanning tree.

25 demand points

Instance #1

Figure 6(a) shows the result obtained using our program, Figure 6(b) shows the result obtained using the MST heuristic, and Figure 6(c) shows the result obtained using the approximation algorithm. In these figures, black dots are demand points, red dots are anchor Steiner points, blue dots are regular Steiner points, and brown dots are Steiner points obtained using the MST heuristic and approximation algorithm.

Figure 6.

(a) Result obtained using our program, (b) result obtained using the MST heuristic, and (c) result obtained using the approximation algorithm.

Instance #2

Figure 7(a) shows the result obtained using our program, Figure 7(b) shows the result obtained using the MST heuristic, and Figure 7(c) shows the result obtained using the approximation algorithm. In these figures, black dots are demand points, red dots are anchor Steiner points, blue dots are regular Steiner points, and brown dots are Steiner points obtained using the MST heuristic and approximation algorithm.

Figure 7.

(a) Result obtained using our program, (b) result obtained using the MST heuristic, and (c) result obtained using the approximation algorithm.

Summary

Table 1 shows the summary of the three input instances with 25 demand points.

50 demand points

Instance #1

Figure 8(a) shows the result obtained using our program, Figure 8(b) shows the result obtained using the MST heuristic, and Figure 8(c) shows the result obtained using the approximation algorithm. In these figures, black dots are demand points, red dots are anchor Steiner points, blue dots are regular Steiner points, and brown dots are Steiner points obtained using the MST heuristic and approximation algorithm.

Figure 8.

(a) Result obtained using our program, (b) result obtained using the MST heuristic, and (c) result obtained using the approximation algorithm.

Instance #2

Figure 9(a) shows the result obtained using our program, Figure 9(b) shows the result obtained using the MST heuristic, and Figure 9(c) shows the result obtained using the approximation algorithm. In these figures, black dots are demand points, red dots are anchor Steiner points, blue dots are regular Steiner points, and brown dots are Steiner points obtained using the MST heuristic and approximation algorithm.

Figure 9.

(a) Result obtained using our program, (b) result obtained using the MST heuristic, and (c) result obtained using the approximation algorithm.

Summary

Table 2 shows the summary of the three input instances with 50 demand points.

100 demand points

Instance #1

Figure 10(a) shows the result obtained using our program, Figure 10(b) shows the result obtained using the MST heuristic, and Figure 10(c) shows the result obtained using the approximation algorithm. In these figures, black dots are demand points, red dots are anchor Steiner points, blue dots are regular Steiner points, and brown dots are Steiner points obtained using the MST heuristic and approximation algorithm.

Figure 10.

(a) Result obtained using our program, (b) result obtained using the MST heuristic, and (c) result obtained using the approximation algorithm.

Instance #2

Figure 11(a) shows the result obtained using our program, Figure 11(b) shows the result obtained using the MST heuristic, and Figure 11(c) shows the result obtained using the approximation algorithm. In these figures, black dots are demand points, red dots are anchor Steiner points, blue dots are regular Steiner points, and brown dots are Steiner points obtained using the MST heuristic and approximation algorithm.

Figure 11.

(a) Result obtained using our program, (b) result obtained using the MST heuristic, and (c) result obtained using the approximation algorithm.

Summary

Table 3 shows the summary of the three input instances with 100 demand points.

200 demand points

Instance #1

Figure 12(a) shows the result obtained using our program, Figure 12(b) shows the result obtained using the MST heuristic, and Figure 12(c) shows the result obtained using the approximation algorithm. In these figures, black dots are demand points, red dots are anchor Steiner points, blue dots are regular Steiner points, and brown dots are Steiner points obtained using the MST heuristic and approximation algorithm.

Figure 12.

(a) Result obtained using our program, (b) result obtained using the MST heuristic, and (c) result obtained using the approximation algorithm.

Instance #2

Figure 13(a) shows the result obtained using our program, Figure 13(b) shows the result obtained using the MST heuristic, and Figure 13(c) shows the result obtained using the approximation algorithm. In these figures, black dots are demand points, red dots are anchor Steiner points, blue dots are regular Steiner points, and brown dots are Steiner points obtained using the MST heuristic and approximation algorithm.

Figure 13.

(a) Result obtained using our program, (b) result obtained using the MST heuristic, and (c) result obtained using the approximation algorithm.

Summary

Table 4 shows the summary of the three input instances with 200 demand points.

Conclusion

In this article, the single-tiered MRP problem in 2D Euclidean space is approached. The problem can be formulated as a STP-MSPBEL. In the literature, most algorithms proposed to solve the problem are based on the MST heuristic. In this article, a novel variable-dimension meta-heuristic based on PSO was proposed to address the problem. The optimization method was put to the test for several randomly generated instances of the problem. We found that the method is effective in obtaining good approximate solutions to those instances of the problem. For the majority of cases, a better approximate solution was obtained compared to that obtained from the MST heuristic.

Footnotes

Academic Editor: Antonio-Javier García-Sánchez

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research,authorship,and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research,authorship,and/or publication of this article: This project is supported by Introduction of high-level talents and overseas returnee’s scientific fund in Nanjing Forestry University (No. GXL015) and Natural Science Foundation of the Jiangsu Higher Education Institutions of China (Grant No. 16KJB510016).

References

Misra

Hong

Xue

. Constrained relay node placement in wireless sensor networks: formulation and approximations. IEEE/ACM T Network 2010; 18(2): 434–447.

Kennedy

Eberhart

. Particle swarm optimization. In: Proceedings of ICNN’95—international conference on neural networks, Perth, Western Australia, 27 November–1 December 1995, vol. 4, pp.1942–1948, https://www.cs.tufts.edu/comp/150GA/homeworks/hw3/_reading6%201995%20particle%20swarming.pdf

Lin

Xue

. Steiner tree problem with minimum number of Steiner points and bounded edge-length. Inform Process Lett 1999; 69(2): 53–57.

Chen

Ding-Zhu

Xiao-Dong

. Approximations for Steiner trees with minimum number of Steiner points. Theor Comput Sci 2001; 262(1): 83–99.

Lin

. Terminal Steiner tree with bounded edge length. In: Proceedings of the Canadian conference on computational geometry (CCCG 2007), Ottawa, ON, Canada, 20–22 August 2007, pp.121–123. Division of Chemical Education.

Cheng

Wang

. Relay sensor placement in wireless sensor networks. Wirel Netw 2008; 14(3): 347–355.

Liu

Wan

Jia

. On optimal placement of relay nodes for reliable connectivity in wireless sensor networks. J Comb Optim 2006; 11(2): 249–260.

Hochbaum

Maass

. Approximation schemes for covering and packing problems in image processing and VLSI. J ACM 1985; 32(32): 130–136.

Lloyd

Xue

. Relay node placement in wireless sensor networks. IEEE T Comput 2011; 56: 134–138.

10.

Hao

Tang

Xue

. Fault-tolerant relay node placement in wireless sensor networks: formulation and approximation. In: Proceedings of the workshop on high performance switching and routing, Phoenix, AZ, 19–21 April 2004, vol. 56, pp.246–250. New York: IEEE.

11.

Tang

Hao

Sen

. Relay node placement in large scale wireless sensor networks. Comput Commun 2006; 29(4): 490–501.

12.

Shishira

Kandasamy

Chandrasekaran

. Survey on meta heuristic optimization techniques in cloud computing. In: Proceedings of the international conference on advances in computing, communications and informatics, Jaipur, India, 21–24 September 2016, pp.1434–1440. New York: IEEE.

13.

Harris

. A stochastic optimization algorithm for Steiner minimal trees. Congr Numer 1995; 105: 1–11.

14.

Kirkpatrick

Vecchi

. Optimization by simulated annealing. Science 1983; 220(4598): 671–680.

15.

Liu

. An artificial fish swarm algorithm for Steiner tree problem. In: Proceedings of the IEEE international conference on fuzzy systems, Jeju Island, Korea, 20–24 August 2009, pp.59–63. New York: IEEE.

16.

Liu

. A particle swarm optimization for Steiner tree problem. In: Proceedings of the 2010 sixth international conference on natural computation (ICNC), Yantai, China, 10–12 August 2010, vol. 5, pp.2561–2565. New York: IEEE.

17.

Pappala

Erlich

. A variable-dimension optimization approach to unit commitment problem. IEEE T Power Syst 2010; 25(3): 1696–1704.

18.

Yan

Osadciw

. Density estimation using a new dimension adaptive particle swarm optimization algorithm. Swarm Intell 2009; 3(4): 275–301.

19.

Chen

Ding-Zhu

Xiao-Dong

. Approximations for Steiner trees with minimum number of Steiner points. J Global Optim 2000; 18(1): 17–33.

20.

García

FJM

Pérez

JAM

García

FJM

. Jumping frogs optimization: a new swarm method for discrete optimization (Documentos De Trabajo Del Deioc), 2008, https://estinv.webs.ull.es/Investigacion/pdfs_dt/DT_DEIOC_3_2008.pdf