## 7 Placement of Nodes
### Placement of Relay Nodes  
In a WSN, if a small set of special nodes, whose main function is packet forwarding, are deployed, the management and network operations in the WSN can be potentially simplified drastically. These nodes are called relay nodes, and have attracted flourishing interests [130; 131; 132; 133; 134]. A fundamental problem which arises when establishing such a network is where to deploy those relay nodes to achieve the required grade of service, while meeting the system constraints. That is the topic of this subsection.  
The problem of relay node placement can be categorized into either single-tiered or two-tiered, according to the data forwarding scheme adopted by the WSN. If both of relay nodes and ordinary sensor nodes can forward packets, this is single-tiered relay node placement. In contrast, in a WSN with two-tiered relay node placement, only relay nodes can forward packets. In a two-tiered system, the relays form a virtual backbone, and must be a connected dominating set (CDS) of the WSN.  
We survey the prior work related to these two types of relay placement. In the following discussion, the transmission ranges for relays and ordinary sensors are denoted \(R\) and \(r\), respectively.  
[PERSON] _et al._[130] developed algorithms to place the minimum number of relay nodes and maintain the connectivity of a single-tiered WSN, under the assumption that \(R=r\), i.e., all relays and ordinary sensors have identical transmission ranges. The problem was modelled by the _Steiner Minimum Tree with Minimum Number of Steiner Points and Bounded Edge Length (SMT-MSP)_ problem, which arose in the study of amplifier deployment in optical networks, and was proved to be NP-hard [135]. Based on a minimum spanning tree, [PERSON] and [PERSON] [135] developed an algorithm to solve the SMTMST problem. They proved it to have an approximation ratio of \(5\), which [PERSON] _et al._[136] tightened to 4. In the same paper, a 3-approximation algorithm was also proposed. Based on [PERSON] and [PERSON]'s algorithm, [PERSON] _et al._[130] proposed a different \(3\)-approximation algorithm and a randomized \(2.5\)-approximation algorithm.  
In order to provide fault-tolerance, [PERSON] _et al._[137] studied how to place minimum number of relays such that the resulted WSN is \(2\)-connected, when relay nodes and ordinary sensor nodes have identical transmission range, i.e., \(R=r\). A constant approximation algorithms with time complexity \(O((kn)^{2})\) was developed. Recently, [PERSON] _et al._[134] improved the results of [PERSON] _et al._ by developing algorithms to compute the optimal node placement for networks to achieve \(2\)-connectivity, under the more general condition that \(R\geq r\). These algorithms aimed to minimise the number of relay nodes while providing fault-tolerance.  
The setting that only relay nodes can perform the packet forwarding is known as the two-tiered infrastructure. [PERSON] _et al._[132] first investigated the two-tiered infrastructure for optimal node placement. Further studies considering an i.i.d. uniformly distributed sensor location with \(R\geq 4r\) were given in [131; 133]. Based on [130] and [131], [PERSON] and [PERSON] [138] developed algorithms to find optimal placement of relay nodes for the more general relationship \(R\geq r\), under single-tiered and two-tiered infrastructures.  
Apart from the above unconstrained relay node placement, in which relay nodes can be placed on anywhere, recent work has started to investigate constrained relay node placement problem which captures the practical consideration such as interferences or forbidden regions prevent relay nodes from being placed on certain positions. Some recent work investigating constrained relay node placement problem is given in [139; 140].