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++.