KCG Lab

Given a geometric structure of a building B and a location of transmitter T and receiver R inside B. We ould like to calculate all bounded length Radio Paths etween T and R. This work presents a new Radio Paths computation frame work specially designed for complex indoor prediction. We propose a new algorithm (IDRP) utilizing a geometric visibility graph (of B) to traverse all possible bounded paths. Such paths are needed in order to compute the signal strength of T as received at R. We have implemented the IDRP algorithm and performed a set of experiments testing the radio paths over complex buildings. The main conclusion is that the new IDRP is time efficient and can compute all relevant radio paths even on relatively complex building with thousends of walls in a fraction of a second.

 

 

We describe the preprocessing stage in which a Visibility Graph (V G(B)) of the the building in issue is computed. The vertices of the graph are the buildingelements i.e., walls, ceilings, floors. Each simple element such as rectangular shape wall is represented by a pair of vertices - one for each side of the element. While complex elements are divided into several simple shape elements. There is an edge between two vertices in the graph if the two building elements associated with the vertices have a directed line of site (LOS) between them,more formally; Each two building elements which can be connected directly by a straight 3Dline segment (without intersecting any other building element along the way) will be connected by an edge. Observation 1 Any path in the visibility graph corresponds to a single (or non) 3D-geometric radio path in the actual building. Proof. Recall that we only consider straight elements, and each such element is transformed to a pair of vertices in the visibility graphTherefore, a pair of vertices which appear along a given path should be considered as a case of penetration while it should be considered as a reflection otherwise. Based on the constraction of the virtual building for a radio-path we may conclude that for path in the visibility graph connecting T and R, there is at most one valid 3D-geometric path.Computing a visibility graph of a building is a somewhat complex task both from the theoretical aspect and the practical one. Thus, the actual runtime of for such an algorithm over complex building might be high. It is worth noting here that the 3D building case is much more complicated then it is for the planar case. Observation 2 We may compute a relaxed approximation of the visibility graph which is ‘over-connected’. (Still, we need to ensure that if there exist a direct LOS between two building elements there will be an edge between their vertices in the corresponding visibility graph). Observation 3 The visibility graph of a building should only be computed once. Given the locations of T and R we can add them to the visibility graph and connect each of them to the building elements in the room they fall into.

 

1. Given a geometric structure B representing a building.
2. Transform each simple building element into a pair of connected vertices.
3. Divide the building into rooms.
4. Divide each floor and ceiling into patches according to each room projection.
5. Define each door or window in the room as a virtual wall (of zero width).
6. Connect all the inner elements of each room (walls, floor, ceiling, doors and windows). Remark: The actual algorithm is somewhat more complex, (for example consider staircase visibility computation). Moreover, dividing a building into rooms requires several technical approaches.