| Ray-tracing based radio propagation prediction models play important roles in wireless systems design as they consider many physical phenomena such as reflections and diffractions. However, such models are computationally expensive. To address this problem, we proposed various techniques: data reduction, progressive and approximate methods, and distributed computation.; Reduction in complexity of building databases can speed up ray-tracing models but may affect prediction accuracy as data simplification errors are introduced. We proposed footprint simplification methods, inverse midpoint displacement, recursive subdivision, triangulation, and convex-hull method, to achieve high vertex reduction rates, while preserving good footprint shapes. Multi-pass and hybrid methods are constructed with multiple constraints on simplified footprints to exploit complementary property of different simplification methods. Our experiments show that footprint simplification methods can reduce prediction time up to three-fold.; To provide better flexibility, progressive ray-tracing models are suggested to satisfy requirements on faithfulness and fairness of prediction results. The sample generator clusters and traces raypaths according to their expected contributions to prediction results. Two progressive models, source-group-raypath-permute and raypath-interleave, are proposed. Approximate models are constructed to provide mechanisms to trade prediction accuracy for prediction time. The workload estimator determines the number of raypaths to be processed to achieve the specified prediction accuracy. Our experiments demonstrate the effectiveness of the proposed progressive and approximate models.; Diffractions are processed in a stage-by-stage fashion and various source points (transmitters or diffraction corners) and ray-paths require different processing times. We propose a distributed ray-tracing model which is based on a network of workstations (NOW) and is a combination of phase-parallel and manager/workers paradigms. The former coordinates different computation stages, while the latter balances workloads among nodes within each stage. The original computation is partitioned into small tasks with raypath-level or source-point-level granularity. The resulting tasks are distributed to nodes using dynamic scheduling schemes. We also address issues regarding memory consumption, intermediate data assembly, and prediction results generation. The proposed NOW-based ray-tracing system is implemented on a NOW with message passing interface (MPI) and experiments show that it achieves linear speedups under various workload. |
