A Physarum-Inspired Algorithm for Minimum-Cost Relay Node Placement in Wireless Sensor Networks

Relay node placement, which aims to connect pre-deployed sensor nodes to base stations, is essential in minimizing the costs of wireless sensor networks. In this paper, we formulate the new Node-Weighted Partial Terminal Steiner Tree Problem (NWPTSTP) for minimum-cost relay node placement in two-tiered wireless sensor networks. The objective is to minimize the sum of heterogeneous production and placement costs of relay nodes and the sum of outage probabilities of transmission routes in a routing tree simultaneously. This extends the previous work that considers the costs of relay nodes to be homogeneous. After formulating NWPTSTP for this purpose, we prove that it can be transformed to the existing node-weighted Steiner tree problem. Subsequently, we conduct some theoretical analyses on the emerging Physarum-inspired algorithms to reveal their potential of computing Steiner trees. Based on these analyses, we propose a new Physarum-inspired algorithm for solving NWPTSTP. We conduct computational trials to show that: 1) in comparison to a state-of-the-art approximation algorithm for solving the node-weighted Steiner tree problem, our Physarum-inspired algorithm can produce better solutions in a smaller amount of time; and 2) in comparison to two state-of-the-art relay node placement algorithms, our Physarum-inspired algorithm can design wireless sensor networks with 25% lower relay cost and similar quality of service (specifically, 5% shorter network lifetime, 2% longer delay, and 0% loss of goodput). This indicates the usefulness of our Physarum-inspired algorithm for minimum-cost relay node placement in budget-limited scenarios.