Two birds with one stone: Wireless access point deployment for both coverage and localization

Wireless access points (APs) divide a plane into small areas where their coverage ranges overlap. A mobile device can be located within a particular small overlapped area based on the unique set of APs covering the device. We formally define an Optimal Loc-deployment problem for both coverage and area localization. Our objective is to deploy a minimum number of APs that provide full communication coverage while achieving the ability to locate a mobile device within a certain area no larger than a given accuracy parameter. We obtain a formula that precisely determines the optimal solution for more than half of the accuracy values. For the rest of the accuracy values, we propose an algorithm that will return an approximation whose difference to the optimal solution is less than ε for any ε > 0. Finally, we conduct extensive numerical evaluation and real experiments to validate our proposed solutions. © 2011 IEEE.