In this thesis, we propose heuristic methods for computing a minimal cost deployment pattern achieving the full coverage and wireless connectivity in arbitrary 3D target space with both static and mobile obstacles.
For the case with only static obstacles, we propose a heuristic algorithm that achieves k-coverage of the monitoring area with the minimal deployment cost. The proposed algorithm puts sensor nodes one by one on a grid point of the deployable area in the descending order of the cost-performance value (i.e., how many monitoring points are covered by putting a sensor at the deployment point per unit deployment cost). For the case with both stationary and moving obstacles in the target area, e.g., a walking person, we propose another heuristic algorithm to achieve mobile k-coverage, that is, for arbitrary position of a moving obstacle, any point located in the target monitoring area has a line-of-sight to and is located in the sensing range rs of at least k sensors. In our method, first we provide a sufficient condition for mobile k-coverage: the half-sphere of radius rs centered at a monitoring point bounded by the vertical plane containing the point includes at least k sensor nodes. Based on this condition, we devise a heuristic that puts at least one sensor node in each spherical wedge for each monitoring point.
Through evaluation, we showed that our proposed method achieves a deployment cost for a 3D WSN that is 45% smaller than triangular lattice pattern that is optimal when deployment cost is uniform over the deployable area. Moreover, we used both proposed methods to deploy wireless devices in a real indoor environment and confirmed that the obtained WSN deployment in the real space accurately achieves full-coverage with only static obstacles and mobile k-coverage when an additional mobile obstacle exists.