On the coverage problems arising in Wireless LAN planning

by

Edoardo Amaldi
Politecnico di Milano 

Wireless Local Access Networks (WLANs) are expected to become pervasive in working
environments as well as public areas (airports, railway stations, etc) since
they will replace traditional wired local networks indoor and allow flexible access
outdoor. Although the small systems currently installed are planned using rules of
thumb, their rapid spread and size increase call for quantitative methods to
determine cost efficient solutions with service quality guarantees.

A WLAN consists of a set of access points (antennas) each of which is able to serve
a subset of users within hearing distance. Since a user can access the network
only if no other user is simultaneously connected to the same access point or is
interfering with it, the network capacity is naturally measured as the sum over all
users of their probability of accessing the network.
Given a set of candidate sites where to locate the access points and for each candidate
site the subset of users that are within hearing distance, an important issue in WLAN
planning is to select a subset of candidate sites in which to install access points
so as to maximize network capacity. Two contrasting objectives arise: on the one hand
we wish to cover the service area with as many access points as possible to increase the
transmission parallelism, on the other hand we wish to minimize the overlapping between
adjacent access points to reduce interference.

We show that the resulting optimization problems can be seen as extensions of the
classical set covering or maximum coverage problems. Since solutions with many access
points serving small, possibly non-overlapping, subsets of users should be privileged,
the interactions between selected access points (the overlaps between the corresponding
subsets of users) must be accounted for. Different formulations based on quadratic and
hyperbolic programming are investigated and preliminary computational results are presented.