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.