This example shows the result of
covering a medieval monastery.
For up-to-date information, visit the homepage of Thom Fruehwirth.
A new tool optimizes the placement of radio transmitters for local wireless communications at company sites. It uses the latest in constraint-based programming technology.
Wireless communications is maybe the trend of the nineties. In Germany, for example, every third phone sold today is mobile. With the introduction of the European standard for digital cordless telecommunication (DECT) cordless local area networks are possible. Mobile communications comes to company sites. No cabling is required and the employees can be reached at any time at any place. However, planning of wireless digital networks is quite different from planning traditional wire-based systems. Small, local radio transmitters have to be installed to provide the wireless devices with signals. The specifics of radio wave propagation at the installation site have to be taken into account. Computer-aided planning can ease the difficulties encountered.
POPULAR won the Telecom application contest of Telecom Italia at CP'98, the annual conference on constraint programming, in October 1998. The system was featured on Bavarian Radio (Bayern 2, Hi-Tech Magazin) in November 1998.
POPULAR (Planning of Picocellular Radio) was developed in collaboration with industry and research institutions in Germany: The SIEMENS Research and Development Department, the SIEMENS Personal Networks Department (PN), the European Computer-Industry Research Center (ECRC) and the Institute of Communication Networks at the Aachen University of Technology.
POPULAR was implemented within one man year in the ECRC Constraint Logic Programming System ECLiPSe, which includes the latest in constraint technology. In particular, the constraint handling rules library was essential for a rapid, flexible and efficient implementation of the geometric constraints that appear in this placement problem. Constraint handling rules are a high-level language extension to implement arbitrary constraint systems. One version of POPULAR is part of the demo suite of ECLiPSe.
Given a blue-print of the building and information about the materials used for walls and ceilings, POPULAR computes the minimal number of transmitters and their location by simulation and subsequent optimization.
First, the characteristics of the building are computed using a grid of test points. Each test point represents a possible receiver position. For each test point the space where transmitter can be put to cover the test point is calculated. This is done by simulating the propagation of radio waves through the walls and ceilings of the building. If the grid is sufficiently small, we can expect that if two neighbouring test points are covered, the space inbetween - hence the whole building - can also be covered.
In the optimization phase, it is made sure that there is at least one transmitter inside each radio cell. The resulting opimization problem is solved using constraint technology. Coverages are intersected to find common locations for transmitters. Starting from an initial, non-optimal solution, other solutions are computed using a branch-and-bound method so that the number of transmitters is minimized.
Even though the problem is very complex in general, an optimal placement for building with up to 100 rooms is found by POPULAR within a few minutes. The overall quality of the solutions produced by POPULAR is comparable to those of a human expert.
This example shows the result of
covering a medieval monastery.
Th. Frühwirth and P. Brisset, Optimal Placement of Base Stations in Wireless Indoor Telecommunication, Winner of telecom application contest, Fourth International Conference on Principles and Practice of Constraint Programming (CP98), Pisa, Italy, October 1998, Color Slides (ps.Z), Paper (ps.Z).
Th. Frühwirth and P. Brisset, Optimal Planning of Digital Cordless Telecommunication Systems, Third International Conference on The Practical Application of Constraint Technology (PACT97), London, U.K., April 1997, Slides (ps.Z), Paper (ps.Z).
Th. Frühwirth, J.-R. Molwitz and P. Brisset, Planning Cordless Business Communication Systems, IEEE Expert Magazine, Special Track on Intelligent Telecommunications, February 1996, revised version of Technical Report ECRC-95-32 (ps.Z).
Introduction in German (ps.Z) and Slides in German (ps.Z).