Propagation graph

Last updated
Example of a propagation graph with four transmitters (Tx1-Tx4), three receivers (Rx1-Rx3) and six scatterers S1-S6. An edge is drawn from one vertex to another if propagation is possible. PropagationGraph.png
Example of a propagation graph with four transmitters (Tx1-Tx4), three receivers (Rx1-Rx3) and six scatterers S1-S6. An edge is drawn from one vertex to another if propagation is possible.

Propagation graphs are a mathematical modelling method for radio propagation channels. A propagation graph is a signal flow graph in which vertices represent transmitters, receivers or scatterers. Edges in the graph model propagation conditions between vertices. Propagation graph models were initially developed by Troels Pedersen, et al. for multipath propagation in scenarios with multiple scattering, such as indoor radio propagation. [1] [2] [3] It has later been applied in many other scenarios.

Contents

Mathematical definition

A propagation graph is a simple directed graph with vertex set and edge set .

The vertices models objects in the propagation scenario. The vertex set is split into three disjoint sets as where is the set of transmitters, is the set of receivers and is the set of objects named "scatterers".

The edge set models the propagation models propagation conditions between vertices. Since is assumed simple, and an edge may be identified by a pair of vertices as An edge is included in if a signal emitted by vertex can propagate to . In a propagation graph, transmitters cannot have incoming edges and receivers cannot have outgoing edges.

Two propagation rules are assumed

The definition of the vertex gain scaling and the edge transfer functions can be adapted to accommodate particular scenarios and should be defined in order to use the model in simulations. A variety of such definitions have been considered for different propagation graph models in the published literature.

Vector signal flow graph of a propagation graph. PropagationGraphVectorFlowGraph.png
Vector signal flow graph of a propagation graph.

The edge transfer functions (in the Fourier domain) can be grouped into transfer matrices as

where is the frequency variable.

Denoting the Fourier transform of the transmitted signal by , the received signal reads in the frequency domain

Transfer function

The transfer function of a propagation graph forms an infinite series [3]

The transfer function is a Neumann series of operators. Alternatively, it can be viewed pointwise in frequency as a geometric series of matrices. This observation yields a closed form expression for the transfer function as

where denotes the identity matrix and is the spectral radius of the matrix given as argument. The transfer function account for propagation paths irrespective of the number of 'bounces'.

The series is similar to the Born series from multiple scattering theory. [4]

The impulse responses are obtained by inverse Fourier transform of

Partial transfer function

Closed form expressions are available for partial sums, i.e. by considering only some of the terms in the transfer function. The partial transfer function for signal components propagation via at least and at most interactions is defined as

where

Here denotes the number of interactions or the bouncing order.

Animation of power delay profiles calculated from partial transfer functions of a propagation graph model. The red line indicates the delay of the direct path. PropagationGraphPartialResponseAnimation.png
Animation of power delay profiles calculated from partial transfer functions of a propagation graph model. The red line indicates the delay of the direct path.

The partial transfer function is then [3]

Special cases:

One application of partial transfer functions is in hybrid models, where propagation graphs are employed to model part of the response (usually the higher-order interactions).

The partial impulse responses are obtained from by the inverse Fourier transform.

Propagation graph models

The propagation graph methodology have been applied in various settings to create radio channel models. Such a model is referred to as a propagation graph model. Such models have been derived for scenarios including

Calibration of propagation graph models

To calibrate a propagation graph model, its parameters should be set to reasonable values. Different approaches can be taken. Certain parameters can be derived from simplified geometry of the room. In particular, reverberation time can be computed via room electromagnetics. Alternatively, the parameters can ben set according to measurement data using inference techniques such as method of moments (statistics), [5] approximate Bayesian computation., [16] or deep neural networks [17]

The method of propagation graph modeling is related to other methods. Noticeably,

Related Research Articles

<span class="mw-page-title-main">Kalman filter</span> Algorithm that estimates unknowns from a series of measurements over time

For statistics and control theory, Kalman filtering, also known as linear quadratic estimation (LQE), is an algorithm that uses a series of measurements observed over time, including statistical noise and other inaccuracies, and produces estimates of unknown variables that tend to be more accurate than those based on a single measurement alone, by estimating a joint probability distribution over the variables for each timeframe. The filter is named after Rudolf E. Kálmán, who was one of the primary developers of its theory.

Belief propagation, also known as sum–product message passing, is a message-passing algorithm for performing inference on graphical models, such as Bayesian networks and Markov random fields. It calculates the marginal distribution for each unobserved node, conditional on any observed nodes. Belief propagation is commonly used in artificial intelligence and information theory, and has demonstrated empirical success in numerous applications, including low-density parity-check codes, turbo codes, free energy approximation, and satisfiability.

<span class="mw-page-title-main">Array processing</span>

Array processing is a wide area of research in the field of signal processing that extends from the simplest form of 1 dimensional line arrays to 2 and 3 dimensional array geometries. Array structure can be defined as a set of sensors that are spatially separated, e.g. radio antenna and seismic arrays. The sensors used for a specific problem may vary widely, for example microphones, accelerometers and telescopes. However, many similarities exist, the most fundamental of which may be an assumption of wave propagation. Wave propagation means there is a systemic relationship between the signal received on spatially separated sensors. By creating a physical model of the wave propagation, or in machine learning applications a training data set, the relationships between the signals received on spatially separated sensors can be leveraged for many applications.

<span class="mw-page-title-main">Finite-difference time-domain method</span>

Finite-difference time-domain (FDTD) or Yee's method is a numerical analysis technique used for modeling computational electrodynamics. Since it is a time-domain method, FDTD solutions can cover a wide frequency range with a single simulation run, and treat nonlinear material properties in a natural way.

In classical electromagnetism, reciprocity refers to a variety of related theorems involving the interchange of time-harmonic electric current densities (sources) and the resulting electromagnetic fields in Maxwell's equations for time-invariant linear media under certain constraints. Reciprocity is closely related to the concept of symmetric operators from linear algebra, applied to electromagnetism.

Fairness measures or metrics are used in network engineering to determine whether users or applications are receiving a fair share of system resources. There are several mathematical and conceptual definitions of fairness.

In wireless communications, channel state information (CSI) is the known channel properties of a communication link. This information describes how a signal propagates from the transmitter to the receiver and represents the combined effect of, for example, scattering, fading, and power decay with distance. The method is called channel estimation. The CSI makes it possible to adapt transmissions to current channel conditions, which is crucial for achieving reliable communication with high data rates in multiantenna systems.

The Egli model is a terrain model for radio frequency propagation. This model, which was first introduced by John Egli in his 1957 paper, was derived from real-world data on UHF and VHF television transmissions in several large cities. It predicts the total path loss for a point-to-point link. Typically used for outdoor line-of-sight transmission, this model provides the path loss as a single quantity.

<span class="mw-page-title-main">MUSIC (algorithm)</span> Algorithm used for frequency estimation and radio direction finding

MUSIC is an algorithm used for frequency estimation and radio direction finding.

Characteristic modes (CM) form a set of functions which, under specific boundary conditions, diagonalizes operator relating field and induced sources. Under certain conditions, the set of the CM is unique and complete (at least theoretically) and thereby capable of describing the behavior of a studied object in full.

<span class="mw-page-title-main">MIMO</span> Use of multiple antennas in radio

In radio, multiple-input and multiple-output (MIMO) is a method for multiplying the capacity of a radio link using multiple transmission and receiving antennas to exploit multipath propagation. MIMO has become an essential element of wireless communication standards including IEEE 802.11n, IEEE 802.11ac, HSPA+ (3G), WiMAX, and Long Term Evolution (LTE). More recently, MIMO has been applied to power-line communication for three-wire installations as part of the ITU G.hn standard and of the HomePlug AV2 specification.

Wi-Fi positioning system is a geolocation system that uses the characteristics of nearby Wi‑Fi access point to discover where a device is located.

In wireless communication, spatial correlation is the correlation between a signal's spatial direction and the average received signal gain. Theoretically, the performance of wireless communication systems can be improved by having multiple antennas at the transmitter and the receiver. The idea is that if the propagation channels between each pair of transmit and receive antennas are statistically independent and identically distributed, then multiple independent channels with identical characteristics can be created by precoding and be used for either transmitting multiple data streams or increasing the reliability. In practice, the channels between different antennas are often correlated and therefore the potential multi antenna gains may not always be obtainable.

Algebraic signal processing (ASP) is an emerging area of theoretical signal processing (SP). In the algebraic theory of signal processing, a set of filters is treated as an (abstract) algebra, a set of signals is treated as a module or vector space, and convolution is treated as an algebra representation. The advantage of algebraic signal processing is its generality and portability.

Zero-forcing precoding is a method of spatial signal processing by which a multiple antenna transmitter can null the multiuser interference in a multi-user MIMO wireless communication system. When the channel state information is perfectly known at the transmitter, the zero-forcing precoder is given by the pseudo-inverse of the channel matrix. Zero-forcing has been used in LTE mobile networks.

Baranyi and Yam proposed the TP model transformation as a new concept in quasi-LPV (qLPV) based control, which plays a central role in the highly desirable bridging between identification and polytopic systems theories. It is also used as a TS (Takagi-Sugeno) fuzzy model transformation. It is uniquely effective in manipulating the convex hull of polytopic forms, and, hence, has revealed and proved the fact that convex hull manipulation is a necessary and crucial step in achieving optimal solutions and decreasing conservativeness in modern linear matrix inequality based control theory. Thus, although it is a transformation in a mathematical sense, it has established a conceptually new direction in control theory and has laid the ground for further new approaches towards optimality.

<span class="mw-page-title-main">Point-set registration</span> Process of finding a spatial transformation that aligns two point clouds

In computer vision, pattern recognition, and robotics, point-set registration, also known as point-cloud registration or scan matching, is the process of finding a spatial transformation that aligns two point clouds. The purpose of finding such a transformation includes merging multiple data sets into a globally consistent model, and mapping a new measurement to a known data set to identify features or to estimate its pose. Raw 3D point cloud data are typically obtained from Lidars and RGB-D cameras. 3D point clouds can also be generated from computer vision algorithms such as triangulation, bundle adjustment, and more recently, monocular image depth estimation using deep learning. For 2D point set registration used in image processing and feature-based image registration, a point set may be 2D pixel coordinates obtained by feature extraction from an image, for example corner detection. Point cloud registration has extensive applications in autonomous driving, motion estimation and 3D reconstruction, object detection and pose estimation, robotic manipulation, simultaneous localization and mapping (SLAM), panorama stitching, virtual and augmented reality, and medical imaging.

Sparse dictionary learning is a representation learning method which aims at finding a sparse representation of the input data in the form of a linear combination of basic elements as well as those basic elements themselves. These elements are called atoms and they compose a dictionary. Atoms in the dictionary are not required to be orthogonal, and they may be an over-complete spanning set. This problem setup also allows the dimensionality of the signals being represented to be higher than the one of the signals being observed. The above two properties lead to having seemingly redundant atoms that allow multiple representations of the same signal but also provide an improvement in sparsity and flexibility of the representation.

Lightfieldmicroscopy (LFM) is a scanning-free 3-dimensional (3D) microscopic imaging method based on the theory of light field. This technique allows sub-second (~10 Hz) large volumetric imaging with ~1 μm spatial resolution in the condition of weak scattering and semi-transparence, which has never been achieved by other methods. Just as in traditional light field rendering, there are two steps for LFM imaging: light field capture and processing. In most setups, a microlens array is used to capture the light field. As for processing, it can be based on two kinds of representations of light propagation: the ray optics picture and the wave optics picture. The Stanford University Computer Graphics Laboratory published their first prototype LFM in 2006 and has been working on the cutting edge since then.

<span class="mw-page-title-main">Method of moments (electromagnetics)</span> Numerical method in computational electromagnetics

The method of moments (MoM), also known as the moment method and method of weighted residuals, is a numerical method in computational electromagnetics. It is used in computer programs that simulate the interaction of electromagnetic fields such as radio waves with matter, for example antenna simulation programs like NEC that calculate the radiation pattern of an antenna. Generally being a frequency-domain method, it involves the projection of an integral equation into a system of linear equations by the application of appropriate boundary conditions. This is done by using discrete meshes as in finite difference and finite element methods, often for the surface. The solutions are represented with the linear combination of pre-defined basis functions; generally, the coefficients of these basis functions are the sought unknowns. Green's functions and Galerkin method play a central role in the method of moments.

References

  1. 1 2 Pedersen, Troels; Fleury, Bernard (2006). "A Realistic Radio Channel Model Based in Stochastic Propagation Graphs" (PDF). Proceedings 5th MATHMOD Vienna: 324–331.
  2. 1 2 Pedersen, T.; Fleury, B. H. (2007). "Radio Channel Modelling Using Stochastic Propagation Graphs". 2007 IEEE International Conference on Communications. pp. 2733–2738. doi:10.1109/ICC.2007.454. ISBN   978-1-4244-0353-0. S2CID   8479930.
  3. 1 2 3 4 Pedersen, Troels; Steinbock, Gerhard; Fleury, Bernard H. (2012). "Modeling of Reverberant Radio Channels Using Propagation Graphs". IEEE Transactions on Antennas and Propagation. 60 (12): 5978–5988. arXiv: 1105.4542 . Bibcode:2012ITAP...60.5978P. doi:10.1109/TAP.2012.2214192. S2CID   14429206.
  4. Lu, S. X. (2011). "Characterization of the random scattering induced delay power spectrum using Born series". 2011 IEEE International Symposium on Antennas and Propagation (APSURSI). pp. 3317–3319. doi:10.1109/APS.2011.6058692. ISBN   978-1-4244-9563-4. S2CID   8166055.
  5. 1 2 Adeogun, R.; Pedersen, T.; Gustafson, C.; Tufvesson, F. (2019). "Polarimetric Wireless Indoor Channel Modeling Based on Propagation Graph" (PDF). IEEE Transactions on Antennas and Propagation. 67 (10): 6585–6595. Bibcode:2019ITAP...67.6585A. doi:10.1109/TAP.2019.2925128. S2CID   96454776.
  6. Stern, K.; Fuglsig, A.J.; Ramsgaard-Jensen, K.; Pedersen, T. (2018). "Propagation graph modeling of time-varying radio channels" (PDF). 12th European Conference on Antennas and Propagation (EuCAP 2018). pp. 22 (5 pp.). doi:10.1049/cp.2018.0381. ISBN   978-1-78561-816-1. S2CID   115436690.
  7. Steinbock, Gerhard; Gan, Mingming; Meissner, Paul; Leitinger, Erik; Witrisal, Klaus; Zemen, Thomas; Pedersen, Troels (2016). "Hybrid Model for Reverberant Indoor Radio Channels Using Rays and Graphs". IEEE Transactions on Antennas and Propagation. 64 (9): 4036–4048. Bibcode:2016ITAP...64.4036S. doi:10.1109/TAP.2016.2589958. S2CID   34442470.
  8. Tian, L.; Degli-Esposti, V.; Vitucci, E. M.; Yin, X. (2016). "Semi-Deterministic Radio Channel Modeling Based on Graph Theory and Ray-Tracing". IEEE Transactions on Antennas and Propagation. 64 (6): 2475–2486. Bibcode:2016ITAP...64.2475T. doi:10.1109/TAP.2016.2546950. hdl: 11585/536072 . S2CID   29844181.
  9. Gan, Mingming; Steinbock, Gerhard; Xu, Zhinan; Pedersen, Troels; Zemen, Thomas (2018). "A Hybrid Ray and Graph Model for Simulating Vehicle-to-Vehicle Channels in Tunnels". IEEE Transactions on Vehicular Technology. 67 (9): 7955–7968. doi:10.1109/TVT.2018.2839980. S2CID   52305255.
  10. Miao, Yang; Pedersen, Troels; Gan, Mingming; Vinogradov, Evgenii; Oestges, Claude (2018). "Reverberant Room-to-Room Radio Channel Prediction by Using Rays and Graphs" (PDF). IEEE Transactions on Antennas and Propagation. 67 (1): 484–494. doi:10.1109/TAP.2018.2878088. S2CID   58669645.
  11. Pedersen, Troels; Steinbock, Gerhard; Fleury, Bernard H. (2014). "Modeling of outdoor-to-indoor radio channels via propagation graphs". 2014 XXXIth URSI General Assembly and Scientific Symposium (URSI GASS). pp. 1–4. doi:10.1109/URSIGASS.2014.6929300. ISBN   978-1-4673-5225-3. S2CID   25407801.
  12. Adeogun, Ramoni; Bharti, Ayush; Pedersen, Troels (2019). "An Iterative Transfer Matrix Computation Method for Propagation Graphs in Multiroom Environments". IEEE Antennas and Wireless Propagation Letters. 18 (4): 616–620. Bibcode:2019IAWPL..18..616A. doi:10.1109/LAWP.2019.2898641. S2CID   106411757.
  13. Pratschner, S.; Blazek, T.; Zöchmann, E.; Ademaj, F.; Caban, S.; Schwarz, S.; Rupp, M. (2019). "A Spatially Consistent MIMO Channel Model With Adjustable K Factor". IEEE Access. 7: 110174–110186. Bibcode:2019IEEEA...7k0174P. doi: 10.1109/ACCESS.2019.2934635 . S2CID   201620704.
  14. Cheng, Wenpu; Tao, Cheng; Liu, Liu; Sun, Rongchen; Zhou, Tao (2014). Geometrical channel characterization for high speed railway environments using propagation graphs methods. 16th International Conference on Advanced Communication Technology. pp. 239–243. doi:10.1109/ICACT.2014.6778956. ISBN   978-89-968650-3-2. S2CID   9210011.
  15. Zhou, Tao; Tao, Cheng; Salous, Sana; Tan, Zhenhui; Liu, Liu; Tian, Li (2014). "Graph-based stochastic model for high-speed railway cutting scenarios". IET Microwaves, Antennas & Propagation. 9 (15): 1691–1697. doi: 10.1049/iet-map.2014.0827 .
  16. Bharti, A.; Adeogun, R.; Pedersen, T. (2020). "Learning Parameters of Stochastic Radio Channel Models From Summaries". IEEE Open Journal of Antennas and Propagation. 1: 175–188. doi: 10.1109/OJAP.2020.2989814 . S2CID   215861548.
  17. Adeogun, Ramoni (2019). "Calibration of Stochastic Radio Propagation Models Using Machine Learning" (PDF). IEEE Antennas and Wireless Propagation Letters. 18 (12): 2538–2542. Bibcode:2019IAWPL..18.2538A. doi:10.1109/LAWP.2019.2942819. S2CID   203994446.