Assuming a fixed grid of conceptual
portable unit locations and a threshold power level, the
coverage *f* for a given set of base-station locations
is defined as the ratio of the number of grid points
with received power above the threshold to the total number of
grid points.
Unfortunately, coverage is not a smooth or even differentiable
function of the base-station locations.
The received power at a single point may exhibit
discontinuities because a tiny change in base-station
location--for example, a move around a corner--can cause an
entirely different
pattern of reflected and transmitted rays; for
most buildings of
practical interest, there will be many such points of discontinuity,
distributed unpredictably around the building.
In addition, our definition of coverage
is inherently ``noisy'', i.e., extremely limited in accuracy, since
*f* can assume only a relatively small number of values.

Because *f* is both non-differentiable and noisy, standard powerful
optimization techniques like Newton-based and quasi-Newton methods (see [1]) cannot
be applied effectively.
The methods of choice (in fact, the only known general methods suitable
for such a problem) are usually called
* "direct search*
methods.
Numerous direct search methods were devised during the early 1960s,
mostly based on heuristic low-dimensional intuition.
Even without formal convergence proofs, these methods performed well and
hence remained popular for 30 years.
Quite recently, several researchers in optimization have begun
a re-examination of direct search methods, and rigorous convergence
results have been obtained by Torczon [8] for the class of multidirectional
search methods.

By far the most popular direct search method is the so-called ``simplex
method'' published in 1965 by Nelder and Mead [4] (not to be confused
with the better-known simplex method for linear programming).
The original Nelder-Mead method constructs a simplex
in *d*-space (a figure with *d+1* vertices). At each iteration,
the method evaluates *f* at one or more trial points whose location
depends on the relative values of the
function at the vertices and at earlier trial points. The purpose
of each iteration is to create a new simplex in which the
previous worst vertex (i.e., the vertex with the
smallest value of *f*) has been replaced. The simplex is altered
by reflection, expansion or contraction, depending
on whether *f* is improving. Although usually
quite efficient, the original
Nelder-Mead method can suffer from numerical difficulties when, for
example, the simplex has become highly elongated.

Our optimization technique is an adaptation of the Nelder-Mead method tailored to the wireless problem. Direct search methods typically contain several coefficients (such as the expansion factor in Nelder-Mead) that control the logic at each step of the algorithm. Certain default values for these coefficients are regarded as standard, and appear in off-the-shelf direct search codes (e.g., in [6]). However, it is well known that a careful choice of problem-specific coefficients can noticeably improve efficiency. Our implementation of the modified Nelder-Mead method includes non-standard values for these coefficients, derived from extensive numerical testing with the wireless problem.

Another delicate computational issue affecting efficiency of a direct
search method is the specification of convergence criteria; see
[8] for a detailed discussion of the impossibility of
developing general-purpose convergence tests. Ensuring that
the convergence criteria are not too strict is especially important in the
wireless problem because of the expense of calculating *f*,
the unavoidable approximations made in modeling, and the inherent
noise in the function. Fortunately,
a substantial level of engineering and physical knowledge
about the wireless problem is available that allows us to
define appropriate termination tests.

In a large number of runs on a variety of buildings with up to 1500 walls, the direct search algorithm consistently converges to an acceptable local solution within a reasonable number of iterations. The number of iterations depends approximately linearly on the problem dimension. For one base station (three variables), convergence usually occurs within 15 iterations, requiring about 20 - 25 function evaluations, where each function evaluation involves calculation of a complete threshold coverage map as in Figure 3.

An interesting and initially unexpected conclusion from our earliest computations was that the coverage function has a very large number of local maxima within all buildings tried. These multiple optima arise from the (in retrospect) unsurprising property that, for any location in the building, there is likely to be a nearby ``best point'' for coverage.

Despite the existence of many local optima, there are three
reasons that the wireless problem is
not
a standard global
optimization problem in which we necessarily want to find the largest
local maximum of *f*. First, there are typically several
base-station locations within a given building that produce the same ``best''
coverage, so that the global optimum is not unique.
Second, the coverage
model is only approximate,
so there is no point to making
a distinction between
coverages of (say) 99.2% and 99.3%.
Third, in the practical settings where WiSE will be used,
the best base-station placement
is likely to be influenced by other factors than coverage.
Some of these could be included in the model
as constraints (for example, avoiding certain parts of the building, or
requiring that the base stations be placed at the ceiling), but
other factors (such as ease of installation
and maintenance) would be difficult to model.
It thus seems likely that an effective role for optimization
within WiSE is to provide a selection of options for
favorable base-station locations.

The optimization program is about 500 lines of C++.