## 4 Topology Control
### Re-Deployment
#### 4.4.3 Heuristic Algorithms  
Node optimal placement is a very challenging problem. The work in [97] states that no local algorithm can achieve good approximation factors for the number of relays. Many of them have been proven to be NP-complete or NP-hard, even when only wanting to achieve a \(2-connected\) network [105, 106].  
Since most relay node optimizations are NP-complete or NP-hard problems, many heuristic solutions have been proposed. The work in [104] first uses a minimal spanning tree algorithm over points set \(P\), then inserts new points for those edges longer than \(R\); the resultant tree has no edges longer than \(R\). This algorithm has \(5-approximation\). The work in [102] improves the approximation of [104] and proposes two algorithms that have a performance approximation of three and 2.5, respectively. Note that they simply consider the \(1-connected\), since it is a tree. Similarly, in heterogeneous networks with the nodes with distinct transmission ranges, the node placement for full \(k-connected\) (considering all nodes) and partial \(k-connected\) (not considering the populated nodes) is an NP-hard problem [28]. The algorithms proposed in [28] have two phases: (1) to solve the minimum \(k-connected\) spanning graph for the initial network; and (2) to put the necessary relay node calculated graph in the first phase. According to the first phase, it' is not difficult to know where and how many relay nodes are needed. However, those methods need to know the location of each node.  
The work in [105] proposes the \(O(D\log n)-approximation\) replacement algorithm of the minimal number of relay nodes for a \(2-connected\) network, where \(D\) is \(D(1,2)-diameter\). It assumes that regular nodes have the same communication range, but the relay nodes have double the range of other nodes. The work in [97] tries to maintain the network as connected while minimizing the number of relay nodes. It considers the global and local algorithms. Notice that there are two kinds of nodes: terminal and relay nodes. The difference is that the terminal nodes are stationary, and the range is one, while relay nodes can move and have a range of more than one. The work in [107] proposes a relay node placement algorithm for a \(k-connected\) (not only \(2-connected\)) network based on the particle swarm algorithm, also considering the heterogeneous feature of WSNs where nodes have different communication ranges. Notice that the algorithm runs off-line. The work in [107] considers that heterogeneous WSNs are only for original nodes, for all new joined relay nodes have the same communication range. The work in [108] proves that the algorithms have complexity \(O(n^{6})\) or \(O(cn^{3})\) for any \(k\). The work in [109] proposes two distributed relay node positioning approaches, based on virtual force-based movements and game theory, respectively, to guarantee network recovery by minimizing the movement cost of the relay nodes. The work in [110] aims to position the minimum number of additional relay nodes by the branch-and-cut-based algorithm, such that signals from sensor nodes communicate to the base station within a pre-specified delay bound.