Precise modeling of radio propagation is necessary for experiencing the benefits of wireless technology for indoor environments. Among many modeling techniques, the ray tracing based prediction models become popular for indoor wireless radio propagation characterization. Though the ray tracing models are popular, their key deficiency is the slower performance. In this paper, an accelerated technique for three dimensional ray tracing using Adelson-Velski and Landis (AVL) tree data structure is introduced. Here, the AVL tree data structure is coupled with the concepts of quadrant eliminating technique (QET) and nearest neighbor finder (NNF) for optimization and fast characterization of indoor wireless communication. Surface intersection scheme (SIS) is also introduced for optimizing the ray-object intersection time. The AVL tree is used for the effective handling of the objects and environments relative information. The QET technique decreases the ray tracing time by omitting unnecessary object, while NNF decreases the ray-object intersection time by finding the nearest object in an efficient technique. For the validation of the superiority of the proposed technique, a detailed comparison is made with the existing techniques. The comparison shows that the proposed technique has 81.69% lower time consumption than the existing techniques.
Abu Sulaiman Mohammad Zahid Kausar,
Ahmed Wasif Reza,
Kamarul Ariffin Noordin,
Mohammad Jakirul Islam,
"Efficient Radio Propagation Prediction Algorithm Including Rough Surface Scattering with Improved Time Complexity," Progress In Electromagnetics Research B,
Vol. 53, 127-145, 2013. doi:10.2528/PIERB13052023
1. Liu, Z.-Y. and L.-X. Guo, "A quasi three-dimensional ray tracing method based on the virtual source tree in urban microcellular environments," Progress In Electromagnetics Research, Vol. 118, 397-414, 2011.
2. Athanasiadou, G. E., A. R. Nix, and J. P. McGeehan, "A microcellular ray-tracing propagation model and evaluation of its narrow-band and wide-band predictions," IEEE Journal on Selected Areas in Communications, Vol. 18, No. 3, 322-335, 2000.
3. Sarker, M. S., A. W. Reza, and K. Dimyati, "A novel ray-tracing, technique for indoor radio signal prediction," Journal of Electromagnetic Waves and Application, Vol. 25, No. 8-9, 1179-1190, 2011.
4. Tao, Y. B., H. Lee, and H. J. Bao, "Kd-tree based fast ray tracing for RCS prediction," Progress In Electromagnetics Research, Vol. 81, 329-341, 2008.
5. Mphale, K. and M. Heron, "Ray tracing radio waves in wildfire environments," Progress In Electromagnetics Research, Vol. 67, 153-172, 2007.
6. Tayebi, A., J. Gomez, F. M. Saez de Adana, and O. Gutierrez, "The application of ray-tracing to mobile localization using the direction of arrival and received signal strength in multipath indoor environments," Progress In Electromagnetics Research, Vol. 91, 1-15, 2009.
7. Alvar, N. S., A. Ghorbani, and H. R. Amindavar, "A novel hybrid approach to ray tracing acceleration based on pre-processing & bounding volumes," Progress In Electromagnetics Research, Vol. 82, 19-32, 2008.
8. Catedra, M. F., J. Perez, F. S. Adana, and O. Gutierrez, "Efficient ray-tracing techniques for three dimensional analyses of propagation in mobile communications: Application to picocell and microcell scenarios ," IEEE Antennas and Propagation Magazine, Vol. 40, No. 2, 15-28, 1998.
9. Cocheril, Y. and R. Vauzelle, "A new ray-tracing based wave propagation model including rough surfaces scattering," Progress In Electromagnetics Research, Vol. 75, 357-381, 2007.
10. Thiel, M. and K. Sarabandi, "A hybrid method for indoor wave propagation modeling," IEEE Transactions on Antennas and Propagation, Vol. 56, No. 8, 2703-2709, 2008.
11. Lee, H.-S. and H. Kim, "Accelerated three dimensional ray tracing techniques using ray frustums for wireless propagation models," Progress In Electromagnetics Research, Vol. 96, 21-36, 2009.
12. Yun, Z., M. F. Iskander, and Z. Zhang, "Fast ray tracing procedure using space division with uniform rectangular grid," Electronics Letters, Vol. 36, No. 10, 895-897, 2000.
13. Larsen, K. S., "AVL trees with relaxed balance," Journal of Computer and System Sciences, Vol. 63, No. 3, 508-522, 2000.
14. Pinel, N., J. T. Johnson, and C. Bourlier, "A geometrical optics model of three dimensional scattering from a rough surface over a planar surface," IEEE Transactions on Antennas and Propagation, Vol. 57, No. 2, 546-554, 2009.
15. Chan, C. H. and Y. Shi, "Solution to electromagnetic scattering by bi-isotropic media using multilevel Green's function interpolation method," Progress In Electromagnetics Research, Vol. 97, 259-274, 2009.
16. Oren, M. and S. Nayar, "Generalization of Lambert's reflectance model," Proceedings of the 21st Annual Conference on Computer Graphics and Interactive Techniques, ACM, 1994.
17. Brennan, D. A., M. F. Esplen, and J. J. Gray, , Geometry, Cambridge University Press, Cambridge, 1998.
18. Gottwald, S., W. Gellert, M. Hellwich, H. Kustner, and H. Kastner, VNR Concise Encyclopedia of Mathematics, 2nd Ed., Springer, 1990.
19. Wolf, K. B., "Geometry and dynamics in refracting systems," European Journal of Physics, Vol. 16, 14-20, 1995.
20. Tsingos, N., T. Funkhouser, A. Ngan, and I. Carlbom, "Modelling acoustics in virtual environments using the uniform theory of diffraction," Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques, 545-552, 2001.
21. Gil, F., A. R. Claro, J. M. Ferreira, C. Pardelinha, and L. M. Correia, "3D interpolation method for base-station-antenna radiation patterns," IEEE Antennas and Propagation Magazine, Vol. 43, No. 2, 132-137, 2001.
22. Ahmed, B. T., J. L. M. Campos, and J. M. L. Mayordomo, "Propagation path loss and materials insertion loss in indoor environment at WiMAX band of 3.3 to 3.6 GHz," Wireless Personal Communications, Vol. 66, No. 2, 251-260, 2012.
23. Giampaolo, E. D. and F. Bardati, "A projective approach to electromagnetic propagation in complex environments," Progress In Electromagnetics Research B, Vol. 13, 357-383, 2009.
24. Giampaolo, E. D., M. Sabbadini, and F. Bardati, "Astigmatic beam tracing for GTD/UTD methods in 3-D complex environments," Journal of Electromagnetic Waves and Applications, Vol. 15, No. 4, 439-460, 2001.
25. Degli-Esposti, V., "A diffuse scattering model for urban propagation prediction," IEEE Transactions on Antennas and Propagation, Vol. 49, No. 7, 1111-1113, 2001.
26. Degli-Esposti, V., F. Fuschini, E. M. Vitucci, and G. Falciasecca, "Measurement and modelling of scattering from buildings," IEEE Transactions on Antennas and Propagation, Vol. 55, No. 1, 143-153, 2007.