## 4 Survey of Existing Works
### Ant Colony Optimization
#### 4.2.2 ACO in WSN Deployment  
Most of the previous works assume that in WSNs a sensing field is an open space. In [83] [PERSON] _et al._ considered the sensing field as an arbitrary-shaped region with possible obstacles. They eliminated the constraints of existing results by assuming a random relationship between the communication range and the sensing range. In the Forbidden City of China, [PERSON] _et al._[84] demonstrated a real application of a WSN system for relic protection. The authors developed a hardware named the EasiNet and the corresponding mesh-architecture of the system was constructed. A sensor deployment optimization tool based on ant colony optimization technology (DT-ACO) is proposed which guarantees the network connectivity, full optimized WSN sensing coverage, as well as minimized number of sensor nodes. A novel power-aware cross-layer scheme (PACS) is designed towards the challenge of adjustable lifetime and surveillance accuracy. It enables satisfactory system lifetime and surveillance accuracy in general applications. PACS was implemented into both sensing nodes and the sink. The sensing nodes use PACS to measure the degree of over-consumption, save the transmissions by data prediction, and adaptively adjust prediction accuracy. The sinks use PACS to cooperate with the sensing nodes when the prediction algorithm proceeds. The mesh architecture of the system achieves prolonged lifetime and an improvement on the data delivery rate than traditional methods [85, 86] during real applications. [PERSON] _et al._ have another relatively recent work [86] published in 2010, where they formulated the minimum-cost CGP \(k\) coverage problem in real sensor network system. An improved ant colony algorithm EasiDesign is proposed to achieve the approximate solution to this optimization problem. They mainly focus on two kinds of practical problems: optimizing the routing hops and avoiding obstacles. They first gave a new pheromone updating rule which considers not only the number of sensors but also the routing cost in the constructed solution, and then they designed an obstacle detection component to guide the ants to go around the obstacles. The obstacle avoidance and the routing cost trade off strategies ensure that the EasiDesign can work efficiently. The simulation results show that EasiDesign uses less sensor nodes than the existing works in the same scenario. The optimum configuration of key parameters in EasiDesign proves that it achieves better performance than the traditional ant colony algorithm. With routing optimization method, EasiDesign largely reduces system routing cost by a small number of redundant sensors. Like previous research work they have demonstrated the performance through a real sensor network system for the environment monitoring in the Forbidden City. In [87] the authors considered the problem of sensor deployment to achieve complete coverage of the service region and maximize the lifetime of WSNs. They modeled the deployment problem as the multiple knapsack problem. The ACO algorithm provides a natural and intrinsic way of exploration of search space for multiple knapsack problems (MKP). Their proposed node deployment scheme based on ACO algorithm addressed five deployment scenarios for performance evaluation. The simulations show that the network lifetime can be increased by increasing the energy and density of the sensors closer to the sink. Also it was claimed that this deployment scheme can perform better than other existing schemes and can prolong the network lifetime significantly in any WSN scenario. The problem of minimum cost and connectivity guaranteed grid coverage (MCGC) is one of the most critical issues for the implementation of WSNs. In [88], a novel algorithm, ant colony optimization with three classes of ant transitions (ACO-TCAT) is proposed to solve this problem. The goal of the algorithm is to improve the quality of the solution space and raise the searching speed.