## 7 Placement of Nodes
### Placement of Ordinary Nodes  
The foremost step required for a WSN to perform its designed functions is deploying all the sensor nodes to form a WSN. As mentioned previously, sensors can be placed exactly on carefully engineered positions, or thrown in bulk on random positions [3]. Each of these will be considered in turn. Most work on deterministic placement seeks to determine the \"optimal\" placement pattern. Different optimality criteria are used, according to the applications and goals of the WSNs. A common objective is to minimise the number of required sensors needed, subject to the constraint that the whole sensingfield is monitored by the deployed sensors. This is equivalent to finding the minimum number of nodes such that every position in the sensing field is within the sensing field of at least one node. Minimising the number of sensors can take the form of an \"art gallery\" problem [112], which aims to find the minimum set of locations for security guards inside a polygonal art gallery, such that the boundary of the entire gallery is visible by at least one of the security guards. [PERSON] [113] proposed a randomized algorithm to solve the art gallery problem to find locations for sensor nodes. However, in the art gallery problem, all security guards are assumed to have infinite vision if there is no obstacles. This assumption does not hold for WSNs in which sensor nodes have limited sensing ranges. It was shown that arranging sensors at the centres of regular hexagons is optimal for a WSN with a large sensing field, given that all the sensor nodes have identical limited sensing ranges [114]. This result has long been known in mathematics community; see [PERSON] [115]. There is also some recent work published discussing the node deployment scheme through the maximization of coverage, through techniques such as Virtual Force Algorithm and Tabu Search, see [116, 117, 118]. The above work on the node placement only considered the coverage constraint that the WSN needs to be able to observe any positions within the sensing field. They did not include the discussion about the connectivity, or they implicitly assumed that the WSN formed by the obtained pattern was connected, regardless the transmission ranges of sensor nodes. Nevertheless, this assumption may not be true. To find the optimal node placement pattern subject to both the coverage and connectivity constraints, [PERSON] and [PERSON] [119] modelled the problem as an optimization problem that minimizes the number of required sensor nodes, under the constraints that any position of the sensor field is under surveillance of at least one node and all nodes are connected. However, the paper did not find a general solution. Instead, it discussed a wide range of regular sensor network deployment patterns. These patterns include circular, star, and grid patterns, such as triangular, square and hexagonal grids. [PERSON] _et al._[120] proved that a strip-based pattern is nearly optimal for this problem for large networks in two-dimensional space. The strip-based pattern, nodes are arranged along many parallel horizontal strips, and nodes in different horizontal strips can communicate via some nodes located as a vertical ribs. [PERSON] _et al._[121] extended the work in [120] by proving that this strip-based pattern is the asymptotic optimal pattern for an infinite network. A slight modification of the asymptotic optimal strip-based pattern, which is optimal to achieve coverage and \(2\)-connectivity was also proposed in [121]. This modified pattern has two vertical ribs of nodes on either end of the sensing fields instead of a single vertical rib. Very recently, [PERSON] _et al._[122] published new results, which proposed optimal sensor placement patterns to achieve coverage and \(k\)-connectivity (\(k\leq 6\)). Note that \(k\)- connectivity can provide fault tolerance. Above work assumed that the WSN was deployed in an open area, without obstacles such as buildings or stationary.