Optimal Wireless Access Point Placement for Location-Dependent Services

In mobile computing scenarios, context-aware applications are more effective in relieving from the mobile user the burden of introducing information that can be automatically derived from the environment. In particular, the physical position of the mobile system (and hence of the user) is fundamental for many types of applications. User position estimation methods based on strength of the radio signals received from multiple wireless access points have been recently proposed and implemented by several independent research groups. In this paper a new approach to wireless access point placement is proposed. While previous proposals focus on optimal coverage aimed at connectivity, the proposed method integrates coverage requirements with the reduction of the error of the user position estimate. In particular, this paper proposes a mathematical model of user localization error based on the variability of signal strength measurements. This model has been designed to be independent from the actual localization technique, therefore it is only based on generic assumptions on the behavior of the localization algorithm employed. The proposed error model is used by local search heuristic techniques, such as local search, a prohibition-based variation and simulated annealing. Near-optimal access point placements are computed for various kinds of optimization criteria: localization error minimization, signal coverage maximization, a mixture of the two. The different criteria are not expected to be compatible: maximizing signal coverage alone can lead to degradation of the average positioning error, and vice versa. Some experiments have been dedicated to quantify this phenomenon and to introduce possible trade-offs.