Topology control, including topology construction and maintenance phases, is a vital conception for wireless ad-hoc networks of any kind, expressly the wireless sensor networks (WSN). Topology maintenance, the latter phase, concerns several problems, such as optimizing the energy consumption, increasing the data rate, making clusters, and sustaining the connectivity. A disconnected network, among other strategies, can efficiently be connected again using a Movement-based Connectivity Restoration (MCR) method, where a commensurate number of nodes move (or are moved) to the desired positions. However, finding an optimal route for the nodes to be moved can be a formidable problem. As a matter of fact, this paper presents details regarding a direct proof of the NP-Completeness of the MCR Problem by a reduction of the well-studied Steiner Tree Problem using the minimum number of Steiner points and the bounded edge length.
翻译:地形控制,包括地形构造和维护阶段,是无线特设网络(包括无线传感器网络)的重要概念,其中明确包括无线传感器网络(WSN),地形维护,后一个阶段涉及若干问题,如优化能源消耗、提高数据率、建立集群和保持连通性等,一个断开的网络,除其他战略外,可以使用基于运动的连通性恢复(MCR)方法(MCR)有效地再次连接,在这个方法中,将相当数量的节点移动(或移动)到理想位置,但找到最佳的节点移动路线可能是一个棘手的问题。事实上,本文通过使用最低限度的施泰纳点和边缘长度来减少受到良好研究的施泰纳树问题,从而直接证明MCR问题的NP-全度。