부산대학교 도서관

The operational cost-effectiveness of wireless sensor networks depends on the placement of heterogeneous nodes: base stations, sensor nodes, and relay nodes. To achieve the global optimality of minimum-cost heterogeneous node placement, we find the locations of base stations, sensor nodes, and relay nodes, simultaneously. The objective is to minimize the sum of node production and placement costs and transmission outage probabilities in the routing tree. First, we formulate this minimum-cost heterogeneous node placement problem as a new NP-hard Steiner tree problem. Then, to solve this problem for both small and large instances, we propose an exponential-time exact algorithm, a polynomial-time heuristic algorithm, and several post-processing algorithms. On a personal computer, our exact algorithm is sufficiently fast to produce optimal solutions for small instances with dozens of vertices, while our heuristic and post-processing algorithms can, respectively, produce and improve suboptimal solutions for large instances with 100 000 vertices and 1 000 000 edges within 6 s. We also compare the heuristic and optimal solutions for small instances with dozens of vertices and show that the ratios between the respective solution costs are generally below 1.35, and our post-processing algorithms can improve this number to 1.1. This indicates that our heuristic and post-processing algorithms are likely to produce near-optimal solutions in practice and are useful for minimum-cost heterogeneous node placement when computational resources are scarce.