Determining location with diffraction propagation
Files
Proposal slides.
Introduction
Radio propagation plays an important role in many robotics applications. The purpose of this project will be to simulate the effects of radio diffraction between a source and receiver. These effects are very important in the transmission of radios waves between agents that cannot maintain line of sight operations. The following sections will introduce propagation and diffraction in greater detail.
Propagation Overview
Radio waves are used for many important purposes- communication with between agents and information retrieval from a base-station. A novel use of radio waves and the networks that use them is localization [14,15]. My project will be focusing on agent localization via radio propagation. I will simulate the propagation of radio waves between an agent and at least one base-station or broadcaster.
There are four primary means of radio wave propagation in environments [11]. The simplest is propagation through unbounded space. Even when ignoring obstructing geometry, determining the wave propagation between two points is still a challenging problem. There are many wave effects that result in difference between the transmitted signal and the received signal. These include signal attenuation over distance, the Doppler effect from moving source or receiver, and fading due to interference from other propagation sources.
In closed regions, when a wave front encounters a new medium with differing properties, reflection and transmission occur at the boundary. Reflection is the scattering of the wave front with respect to the normal of a planar surface, as with mirrors. Transmission is the passing of the wave through the new medium. Both effects may introduce a new polarization on the propagating wave, as well as a new frequency attenuation. The effect different materials have on transmission is notably complex and has been the subject of many studies and experiments [11].
Since most physical boundaries are finite, they must be bounded. This introduces edges and the wave effect of diffraction. Diffraction is the scattering of a wave around the edge, continuing propagation in the region out of line of sight of the source. There are many considerations when simulating diffraction. This ranges from the shape of the edge encountered, the shape of the wave front arriving at the edge, the wavelength of the signal relative to the edge size, and the geometry of the source and receiver relative to the edge [11,12,13].
Diffraction
There are many theories of diffraction that can achieve accurate simulation of the effect. The fundamental basis for diffraction was laid by Huygens, who put proposed an approximation of diffraction as many secondary point sources from which wave propagation continued. This was later formalized by Kirchoff, resulting in the Kirchoff-Huygens approximation. This approximation is difficult to work with, as only simple scenes can be solved analytically; general conditions require a complex numerical solution. Simpler approximations were derived for more common diffraction cases. The Geometrical Theory of Diffraction [12] and the Uniform Theory of Diffraction [13] are both much simpler calculations, but subject to certain restrictions.
I will be using the UTD to perform diffraction calculations. This method requires certain conditions of the wave and the scene. Only certain boundary conditions may be calculated, the signal wavelength must be high enough that the edge length is infinte in comparison, and the source and the receiver must be far from the edge.
Since I will be simulating diffraction effects at interactive rates, the UTD is an excellent candidate for calculating the diffraction in a scene. It is a very inexpensive calculation compared to other diffraction theories and can handle typical scene conditions with ease. Possible simuation environments include urban scenes with large buildings and other structual geometry.
I will be adapting a frustum tracing propagation engine to calculate diffraction paths for RF transmission. Frustum tracing provides a method of fast approximate visibility calculations and can be tuned for accuaracy by the user. Handling direct transmission and reflection are trivial, but modifications will need to be made to adequately model diffraction.
Related research
There have been other simulations of diffraction. The most accurate of these are numerical simulations. However, they come with high computational requirements. Work in this area focuses on several different implementation to solve wave equations such as BEM, FEM, digital wave guides, and finite difference time domain.
I will focus on geometric solutions to diffraction for radio and sound wave fronts. There has been research in using analytical solutions to diffraction theories to calculation diffraction propagation [1,5]. There has also been work with Fresnel volumes to estimate obstruction [2,3]. Raytracing has also been used to simulation diffraction effects [6]. Recently, there have been advances in beam tracing [4] to the point where it can perform interactive diffraction [7,8].
However, all of these methods suffer from certain limitations. They are largely restricted to simple static scenes or constrained by large computational requirements. Frustum tracing [9,10] presents a balanced approach to accuracy and computation speed, showing interactive audio propagation on complex dynamic scenes. Currently, frustum tracing can only calculation direct propagation and reflection. Due to its advantages in rendering complex scenes quickly, it is would be ideal to adapt to radio transmission and extend with a complementary diffraction method. This is what I propose to do in this project.
Tasks
2008-10-23
Implement appropriate diffraction propagation volumes and path solver. In order to calculate diffraction between two points, a possible propagation path must be found. This requires exploring the scene with respect to the visibility of the propagating wave. If it is possible that the source wave reaches a receiver, the attenuation effects of the signal must be calculated. The calculation of attenuation with the UTD requires that a single path from the source to the receiver be found.
2008-11-10
Allowances must be made for phase variation of the signal as it propagates. I will implement a robust system for determining the final phase of the signal that reaches the receiver. This will involve computation and combination of a chain of complex attenuation values at each interaction with scene geometry via a transmission effect (restricted to diffraction and reflection).
2008-12-04
Final evaluate the system and attempt to determine convergence. Since the accuracy of frustum tracing can be determined by the user, I will generate results detailing the effects of different accuracy settings on different scenes. Scenes will include: a city scene with large buildings, an urban scene with several houses, and indoor scene for very short wave transmission.
References
Fresnel:
[1] Torres et al., Computation of edge diffraction for more accurate room acoustic auralization, J. of the Acoustical Society of America, 2001
[2] Bertoni, Coverage prediction for mobile radio systems operating in the 800/900 MHz frequency range, IEEE Transactions on Vehicular Technology, 1988
[3] Tsingos et al., Soundtracks for computer animation: sound rendering in dynamic environments with occlusions., Proceedings of Graphics Interface, 1997
[4] Aveneau et al., Rendering polygonal scenes with diffraction account, Seventh International Conference on Computer Graphics and Visualization, 1999
[5] Stam, Diffraction shaders, ACM Computer Graphics, proc. SIGGRAPH, 1999
[6] Rajkumar et al., Predicting RF Coverage in Large Environments using ray-beam tracing and partitioning tree represented geometry, Wireless Networks, 1996
[7] Tsingos et al., Modeling Acoustics in Virtual Environments Using the Uniform Theory of Diffraction, ACM Computer Graphics, proc. SIGGRAPH, 2001
[8] Funkhouser et al., A beam tracing approach to acoustic modeling for interactive virtual environments, ACM Computer Graphics, proc. SIGGRAPH, 1998
[9] Lauterbach et al., Interactive Sound Propagation in Dynamic Scenes Using Frustum Tracing, IEEE Visualization, 2007
[10] Chandack et al., AD-Frustum: Adaptive Frustum Tracing for Interactive Sound Propagation, IEEE Visualization, 2008
[11] Bertoni, Radio Propagation for Modern Wireless Systems, Prentice Hall, 2000
[12] Keller et al., Geometrical theory of diffraction, J. of the Optical Society of America, 1962
[13] Kouyoumjian, A uniform geometrical theory of diffraction for an edge in a perfectly conducting surface, Proc. IEEE, 1974
[14] Monster et al., Practical WiFi Localization for Autonomous Industrial Vehicles, Australasian Conference on Robotics and Automation, 2006
[15] Bahl et al., User location and tracking in an in-building radio network, Tech Report- Microsoft research, 1999