Propagation modeling has attracted much interest because it plays an important role in wireless network planning and optimization. Deterministic approaches such as ray tracing and ray launching have been investigated, however, due to the running time constraint, these approaches are still not widely used. In previous work, an intelligent ray launching algorithm, namely IRLA, has been proposed. The IRLA has proven to be a fast and accurate algorithm and adapts to wireless network planning well. This article focuses on the development of a parallel ray launching algorithm based on the IRLA. Simulations are implemented, and evaluated performance shows that the parallelization greatly shortens the running time. The COST231 Munich scenario is adopted to verify algorithm behavior in real world environments, and observed results show a 5 times increased speedup upon a 16-processor cluster. In addition, the parallelization algorithm can be easily extended to larger scenarios with sufficient physical resources.
TopIntroduction
Propagation modeling serves as a fundamental input in the wireless network planning and optimization process. Especially, in order to determine the interferences for an indoor femtocell base station with the outdoor macrocell, accurate coverage predictions have to be obtained via propagation modeling (Zhang & De La Roche, 2010). Planning and optimization of a wireless network usually requires simulation of hundreds of User Equipments (UE) and the path loss between these UEs and base stations are obligatory to investigate the best servers and handovers etc.
Current propagation models can be divided into three categories: empirical models, semi- deterministic and deterministic models. Empirical models are the simplest models; which are usually based on simple factors such as the carrier frequency and distance. They are extremely fast because of statistical model environmental factors. The semi-deterministic models are enhanced by introducing relevant deterministic factors in the computation. Such models provide higher accuracy than empirical models, thus running time of semi-deterministic models is usually realistically acceptable upon conventional computing power, such as PCs.
The deterministic models consider environmental factors, e.g., buildings and walls, which are time-consuming compared to empirical and semi-deterministic models. However, the deterministic models provide the highest accuracy out of these categories.
Ray-based methods belong to deterministic models and they are based on geometry path finding algorithms (Haslett, 2008). Ray-based methods in general are divided into two subcategories: ray tracing and ray launching. Ray tracing adopts a backward path search technique, which guarantees that exact paths between transmitters and receivers can be computed (Glassner, 1989). Ray tracing offers high accuracy but it is extremely time consuming. The complexity grows exponentially with the number of objects and the maximum ray iterations (Nagy, Dady, & Farkasvolgyi, 2009). Ray tracing is used for precise point-to-point predictions. Several acceleration techniques such as pre-processing (Wolfle, Gschwendtner, & Landstorfer, 1997) or the use of a General Purpose Graphic Processing Unit (GPGPU) (Rick & Mathar, 2007) have been proposed. The performance of ray tracing is usually limited by the inherent complex ray-object intersection tests and many techniques have been proposed over the past years to speed up computation (Degli-Esposti, Fuschini, Vitucci, & Falciasecca, 2009). Ray launching emits the rays from sources; which are separated by a small angle. This method is efficient in an area prediction because the rays are actively followed. However, this approach leads to two inherent problems. The first problem is angular dispersion of ray launching. The distant pixels are less likely to be visited by rays because rays disperse as they are propagated. For example, a distant small object may be missed by rays because a fixed angle is used to separate rays. Secondly, the ray double counting arises when a sample pixel is marked twice by the same rays, which should be avoided because it reduces the accuracy of ray launching. Ray launching is usually faster than ray tracing with less accuracy. The complexity of ray launching grows linearly with the number of objects and maximum ray iteration (Nagy et al., 2009).