Deploying wireless sensors to achieve both coverage and connectivity

It is well-known that placing disks in the triangular lattice pattern is optimal for achieving full coverage on a plane. With the emergence of wireless sensor networks, however, it is now no longer enough to consider coverage alone when deploying a wireless sensor network; connectivity must also be con-sidered. While moderate loss in coverage can be tolerated by applications of wireless sensor networks, loss in connectivity can be fatal. Moreover, since sensors are subject to unanticipated failures after deployment, it is not enough to have a wireless sensor network just connected, it should be k-connected (for k > 1 ). In this paper, we propose an optimal deployment pattern to achieve both full coverage and 2-connectivity, and prove its optimality for all values of r_c/r_s, where r_c is the communication radius, and r_s is the sensing radius. We also prove the optimality of a previously proposed deployment pattern for achieving both full coverage and 1-connectivity, when r_c/r_s < √3 .Finally, we compare the efficiency of some popular regular deployment patterns such as the square grid and triangular lattice, in terms of the number of sensors needed to provide coverage and connectivity.