ABSTRACT
The surging demand for mobile communications and the emerging field of ubiquitous computing require enormous development in the realm of wireless networking. Although many problems in mobile wireless networking can be successfully solved using techniques borrowed from wireline networks, there exists some problems that are very specific to the wireless domain and often computationally very difficult or sometimes even intractable. This is primarily due to the inherent limitations of wireless communications, such as scarce bandwidth, high bit error rate, or location uncertainty. Most of these problems can be mapped to classical optimization problems, with the goal of optimizing some objective functions, say resource utilization, while satisfying all the constraints imposed by the wireless communication systems. The constraints make most of the problems NP-complete or NP-hard [1]. There are two broad approaches to solve such problems. One is to directly compute the exact solution based on the constraints, using a brute force technique. However, this approach is often infeasible in a large-scale problem domain. The other approach is to use a heuristic-based solution that can be computed in feasible time. Although a heuristic may not yield the optimal solution, a carefully designed heuristic may produce a near-optimal solution with low computational complexity. Various attempts have been made to develop efficient heuristics that range from calculus-based search methods to random search techniques. The paradigm of “evolutionary
CHAPMAN: “C4754_C015” — 2005/8/8 — 17:14 — page 220 — #2
computing or programming” essentially provides such heuristics for solving computationally difficult problems, by mimicking the evolution process that the nature uses to eliminate weak forms of life.
