Beam Ray Tracing for Wireless LANS

The project here was initiated by an interest in providing an open source GPL tool that will allow installers of wireless LANS to simulate the signal strength of one or more wireless Access Points in an arbitrary building. This will help the installer to decide how many Access Points are needed, and where they should be sited without the need for extensive and costly site mapping.

The project has a range of challenges, particularly in the mathematical description of the building topology. Obtaining useful electromagnetic properties of building materials is also difficult, and will continue to be so as these properties can vary immensely between very similar materials (particularly wood). The tool will provide representative values for common materials.

In beamtracing, a geometric tree of 3D beams emanates from sources and from reflections at, and transmissions through, walls in a building. This tree is used to trace back from a large number of potential receiver points to the sources, allowing the signal strength to be determined accurately (in the mathematical sense) at the receiver points. In raytracing, rays emanate from a source and the program attempts to find those that reach (usually) a single point of view or camera. Beam tracing thus can be more efficient where the number of receiver points is large, however the geometric computational algorithms are non-trivial.

The only thing currently preventing the application from giving useful results is the completion of the coding of the electromagnetic model. The current state of the application provides a display of signal strengths throughout the building, but only the free space loss is included in the model. Reflections and transmissions are given by fixed coefficients independent of incidence angle and material properties of the walls. There are some minor computational problems to be fixed, and in addition it only seems to work on my 64-bit machine, not on a 32-bit PC - interesting.

Documentation: (OpenOffice 2.0 Format)

Original proposal paper
Development paper (dynamically changing as the project develops).

Source:

C++ code for the core application is essentially complete but requires extensive testing. It is being developed with KDevelop 3.3.3/gcc 4.1.1. Configuration is done using qmake (see the README and INSTALL files). The MingW Windows port of gcc 3 in Dev-C++ from Bloodshed Software was used in the initial non-GUI part of the development, but is now not used. For the GUI, Trolltech's QT IDE was used initially, after which all development has been done in KDevelop using their QT port. Windows will not be targetted for further development but it should be adaptable with the Trolltech QT environment.
Currently the topology partitioning module that reads from an "internal" format building definition file is functionally complete. This builds the datastructures that will be used by beamtrace to trace quickly through the building during simulation. Partitioning is run once on the building specifications, and the results can be re-used for different placements of the source(s). It needs to be run again only if the building specifications are changed. The wall material properties can also be changed without needing to rerun the partitioning
The beamtrace section is also essentially complete. This builds a tree of reflected and transmitted beams. From each grid point in the building, a ray is recursively traced back to the source using the beamtree. This procedure is efficient and precise.
A GUI has been developed to run the partitioning and beamtracing. This is useable but will be expanded as options are added. The advantage of the GUI is that 2D views of the building topology and the signal distribution can be provided. This has already proved helpful in tracking down certain problems.
Input from a CAD program is desirable. Currently Blender looks promising as a possible 3D opensource graphical building definition utility.

Work to be done:

Testing of Topological Partitioning and Beamtrace - in progress.
Review of error condition testing - in progress.
Electromagnetic interaction with walls - in progress.
Some improvements in Partitioning to test initially that walls are regular planar polygons - to be done.
Separate out the material properties definition from the building topology specification - to be done.
Save topological datastructures for reloading to Beamtrace - to be done.
Interface for CAD input of building topology. Currently a simple text input format is used - to be done.
Refactoring for performance enhancement of time-consuming computational sections - to be done.
Add parallel processing to speedup the beamtrace part - to be done.

Bugs

Missing beams when the source is exactly coincident with a wall, even a transparent one. This is understood to be due to a failure of the geometry algorithm in dealing with a source on the opposite side of a wall but close to it. A fix is relatively simple in concept but may require some extensive effort.
Does not work with 32-bit CPUs, cannot locate the source in a cell. The problem here is identified as arising from roundoff error. It is a problem on all CPUs, but coincidentally was not obvious on a 64-bit CPU. A fix requires testing for numbers very close to zero and replacing them with a floating point zero. This is different to the question of testing equality between two floating point numbers that are identical except for roundoff error.

Screen Shots

The solid lines are the original walls, and the dotted lines are transparent walls added by the topological partitioning. There is no legend yet. The colours range through the rainbow from red at highest signal strength to blue as the lowest. White represents signal strength below the lowest threshold.

In the first image the back reflection from the wall on the left of the source can be seen to enhance the lower part of the signals near the source.

The second one below shows an odd linear artefact parallel to the walls (upper right). These are results of reflections from the horizontal corners between walls and floor or ceiling.

This one has the source very close to a wall (but not coincident).

This one shows missing beams (bottom left) when the source is on a wall, in this case a transparent one. This is due to a bug in the geometry algorithms (see above).

Timing measurements done on a 2.8GHz Xeon CPU, 512MB DDR2 memory system. Smaller resolutions failed due to lack of memory (excessive paging occurred).

Warning: this author uses another popular PC operating system sparingly and on an emergency basis only. All software is developed on and for Linux, which is the only OS worth spending time and effort on (well - maybe OSX also). Note however that he considers this other OS to have a well defined place with non-technical users, where Linux and other open-source software still have yet break in, if they ever do.

Contact: My email address can be constructed from the username "ksarkies" and the ISP DNS address internode.on.net in the usual way.