Cost-Efficient Deployment for Full-Coverage and Connectivity in Indoor 3 D WSNs
Cost-Efficient Deployment for Full-Coverage and Connectivity in Indoor 3 D WSNs
复制标题
DOI：
--
复制
发表时间：
2010
影响因子：
1.9
通讯作者：
Marc T. Kouakou;Shinya Yamamoto;K. Yasumoto;Minoru Ito
中科院分区：
文献类型：
--
作者：
Marc T. Kouakou;Shinya Yamamoto;K. Yasumoto;Minoru Ito
在无线传感器网络中，目标区域的覆盖范围和传感器节点之间的无线连接是无线传感器网络所需性能的重要标准。在室内环境中，目标场位于一般的3D空间中，因此为此类环境部署的WSN称为3D WSN。即使目标区域没有障碍物，3D 覆盖和连接的传感器节点部署问题也是 NP 困难的。此外，还没有研究系统地检验考虑障碍和部署成本的最佳 3D WSN 部署。在本文中，我们提出了一种新的启发式算法，用于计算接近最佳的传感器节点部署，最大限度地降低实现有障碍物的 3D 目标空间的全覆盖和节点连接的成本。首先，我们通过一组网格点来表示目标 3D 空间中的监控区域以及传感器节点可部署区域。我们的算法按照可部署区域点的性价比值（即每单位部署成本，可部署区域点覆盖了多少个监控空间点）的递减顺序，将传感器节点逐一放置在可部署区域的网格点上。然后，算法添加额外的节点来覆盖每个节点感知区域被障碍物遮挡的阴影区域。此外，为了保证所有WSN节点之间的连通性，该算法添加额外的节点和/或将每个未连接的传感器节点一一移向最近连接的传感器节点，以减少额外节点的数量。我们在 UbiREAL 模拟器中实现了我们提出的方法，并通过模拟评估了性能。因此，我们证实我们提出的方法可以为室内环境中的 WSN 部署提供可靠且经济高效的解决方案。
In WSNs, coverage of the target field and wireless connectivity among sensor nodes are important criteria in terms of the performance required for WSN. In indoor environments, the target field is in general 3D space, thus WSNs deployed for such environments are called 3D WSNs. The sensor node deployment problem for 3D coverage and connectivity is NP-hard even without obstacles in the target field. Furthermore, no study has systematically examined the optimal 3D WSN deployment considering both obstacles and deployment cost. In this paper, we propose a new heuristic algorithm for computing a near optimal sensor node deployment that minimizes the cost for achieving the full coverage and node connectivity of a 3D target space with obstacles. First, we represent the monitoring area as well as the sensor node deployable area in the target 3D space, by a set of grid points. Our algorithm puts sensor nodes one by one on a grid point of the deployable area in the descendant order of the cost-performance value (i.e., how many monitoring space points are covered by the deployable area point per unit deployment cost) of the deployable area points. Then, the algorithm adds extra nodes to cover the shadow area of each node’s sensing region cut off by the obstacles. Moreover, to ensure the connectivity among all WSN nodes, the algorithm adds extra nodes and/or moves each unconnected sensor node one by one towards the closest connected sensor node in order to reduce the number of extra nodes. We implemented our proposed method in the UbiREAL simulator and evaluated the performance through simulations. As a result, we have confirmed that our proposed method can provide reliable and cost-efficient solutions for WSN deployment in indoor environments.