Variable-dimension swarm meta-heuristic for the optimal placement of relay nodes in wireless sensor networks. (March 2017) - Xu, Yi-Han; Jiao, Wan-Guo; Wu, Yin; Song, Jun
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.