Improved Path Loss Simulation Incorporating Three-Dimensional Terrain Model Using Parallel Coprocessors.
Generally, network or physical layer oriented simulators have been used to enable the performance studies on communication networks. Network layer simulators mainly focus on the performance and behavior of the entire communication networks, such as medium access control issues and network layer aspects. On the other hand, physical layer oriented simulators  focus on point-to-point link performance under specific channel conditions. Due to the increased computational complexity in including complex channel models to study the wireless performance of communication networks, currently available network simulators abstract out such wireless channel or propagation models.
As a consequence, network simulators abstract out the physical layer, while physical layer simulators do not readily consider network characteristics nor do they reflect the functionality of medium access on network layer protocols . To overcome the shortcomings, Mittag et al.  have integrated an IEEE 802.11a and physical layer simulator with NS-3; however the improved accuracy comes at the cost of increased computational effort. Mittag et al. proposed the use of graphic processing unit (GPU) to offset the increased computational complexity as one of their future works.
There exist a number of popular network simulators; however simulators which enable the performance studies on communications networks using GPUs for parallel processing with 3D terrain elevation data are still not available for public usage or research. From [3-7], it can be concluded that significant speedup can be achieved by exploiting GPU. However, different bottlenecks will affect the speedup, such as the parallelization of an algorithm, the runtime of each single independent subprogram, different architecture of GPUs, and different types of used software architecture.
The digital elevation model (DEM)  is a digital model that represents terrain's surface. Djinevski et al. , Liu and Ma , and Chong and Kim  individually showed that using actual terrain elevation data provides higher accuracy for wireless network simulation as wireless propagation is strongly affected by terrain profile regardless of whether it is man-made or natural. However, their work cannot be extended to the well-known network simulators like NS-3 platform as such platform does not support the usage of digital terrain model at the moment.
In both fixed and mobile radio systems, large scale path loss prediction is important to determine the distance between a transmitter and a receiver. Thus, large scale path loss prediction is useful to estimate the radio coverage area. Different models based on statistical and deterministic methods are proposed to calculate the path loss between a transmitter and a receiver. Commonly used statistical methods include Okumura  and Hata  models. Deterministic methods that consider obstacles in the propagation path are expected to produce more accurate predictions of the path loss as compared to the statistical methods.
In this paper, we propose a framework to compute path loss between a transmitter and a receiver in a fixed radio network based on terrain model. As compared to the conventional disk model based on free space loss (FSL)  which estimates the path loss between a transmitter and a receiver solely based on the transmitter-receiver distance, terrain model additionally considers the terrain profile in affecting the path loss. However, the higher accuracy of path loss prediction using terrain model also indicates higher computation effort. To reduce computation time needed for more accurate path loss simulation, we offload the computationally intensive components onto an inexpensive off-the-shelf parallel coprocessor, which is an NVIDIA GPU. More precisely, we load the terrain profile into the Compute Unified Device Architecture (CUDA) texture memory and parallelize the transmitter-receiver path profile computation. The terrain profile between a transmitter and a receiver is extracted from DEM data provided by United State Geological Survey (USGS). To check the effectiveness of our proposed simulation framework, we compare the path loss computed using both conventional disk model and terrain model on seven maps. Besides this, our results also show a speed up of 20x to 42x by using GPU. Lastly, the propose framework is implemented on NS-3 to enable studies on cross-layer optimization.
2. Path Loss Prediction Models
2.1. Disk Model. The disk model is the most commonly used simulation model which assumes that the sensing region is circled around the sensor .
Calculation of FSL is carried out using the distance d obtained through the transmitter-receiver pair coordinates and the predefined frequency of propagation wave f at the beginning of the simulation. The FSL is derived from the Friis free space equation  as follows:
FSL = 32.4 + 20 [log.sub.10] (d) + 20 [log.sub.10] (f). (1)
However, the path loss computation between the transmitter and the receiver using FSL is only accurate if and only if there are no obstacles (which cause the reflection or refraction of waves) between the transmitter and the receiver. Thus, path loss computation using FSL may not be applicable in the real world.
FSL model, an isotropic radio model that implies signal attenuates in all directions with similar magnitude over distance, does not hold well in comparison to real measurement . Meanwhile, nonisotropic models such as deterministic models that analyze the obstructions (terrain, foliage, buildings, antenna height, etc.) in the path profile into computation are proven to be closely matched with the real-measured path loss [15-18].
2.2. Terrain Model. Our proposed model is a deterministic model, a terrain model which computes path loss based on the diffraction loss of multiple knife-edge obstructions using the Epstein-Peterson path geometry method , Fresnel-Kirchhoff's theory, and FSL. The Epstein-Peterson method is a well-known model that estimates the diffraction loss based on obstacles and has relative high accuracy [20, 21] and is proven to be accurate when compared to real-measured path loss . Furthermore, Djinevski et al.  propose the usage of the Epstein-Peterson method for the future GPU-enabled version as well.
3. Heterogeneous System Based Simulation with Terrain Model
As shown in Figure 1, a heterogeneous simulation framework is proposed based on USGS DEM data to produce more accurate transmitter-receiver prediction for radio network. Due to the higher computation complexity after incorporating three-dimensional (3D) terrain model into the simulation, we study the terrain model and offload the two most computationally intensive processes, Terrain Mapping and Path Profile Calculation to the GPU. Since the same map is used when estimating the network coverage, it is important to load the frequently used map into fast access memory (i.e., CUDA texture memory). Besides this, the path profile computation between different locations on a same map can be parallelized. Notice that the one-time DEM extraction can be precomputed offline to make the simulation more practical in the real world.
The proposed simulation framework includes six different processes, that is, DEM Extraction, Terrain Mapping, Path Profile Calculation, Fresnel Zone Calculation, Terrain Peak Calculation, and Path Loss Calculation.
3.1. DEM Extraction. GDAL library , a translator library for raster and vector geospatial data formats, is used to extract the relevant information from USGS DEM data that is needed for transmitter-receiver path loss computation. Redundant information will be discarded in this process.
3.2. Terrain Mapping. The information extracted from DEM is then loaded and relocated to the CUDA texture memory on GPU. There are two reasons for using CUDA texture memory. First, the data reading time is faster since the CUDA texture memory is a cache memory. Second, the simulation achieves faster speed by exploiting the additional feature of the CUDA texture memory where the linear interpolation of data (which is needed in Path Profile Calculation) can be computed easily.
3.3. Path Profile Calculation. To calculate the path profile between a transmitter-receiver pair, coordinates of the transmitter and receiver with antenna height are required. Based on the coordinates given, the terrain profile between the two nodes can be extracted from the DEM data. However, to obtain the terrain height for a specific point along the path profile, the interpolation of its surrounding points needs to be computed. Accumulating the information for each point, the system is then able to complete the path profile between a transmitter and a receiver.
3.4. Fresnel Zone Calculation. After the path profile is calculated and formed, analysis of the terrain is performed to determine the obstacles that block the line of sight (LOS) between a transmitter and a receiver. As shown in Figure 2, visual LOS is the dotted line between the antennas, while radio frequency LOS requires an oval-shaped area to be free from any obstructions. This oval-shaped area is called the Fresnel zone. Obstacles, such as buildings, vegetation, and the ground, that are located inside the Fresnel zone will increase the path loss. When at least 60% of the Fresnel zone is unobstructed, this phenomenon is known as free space propagation.
The general equation for calculating the Fresnel zone radius at any point P in between the transmitter (Tx) and receiver (Rx) is listed as follows:
[F.sub.n] = [square root of n[lambda][d.sub.1][d.sub.2]/[d.sub.1] + [d.sub.2]], (2)
where [F.sub.n] is the nth Fresnel zone radius, [d.sub.1] is the distance of P from one end, [d.sub.2] is the distance of P from the other end, and [lambda] is the wavelength of the transmitted signal. Note that (2) is valid for ideal terrain height; that is, both antennas are 90 degrees perpendicular to the LOS.
One of the challenges faced in computing the path loss using (2) is that in most of the situations, both antennas are not located at the same terrain height. To solve this issue, our proposed simulation framework first performs the matrix rotation such that both antennas are virtually located at the same height. More precisely, as shown in Figure 3, we rotate the path profile in clockwise direction when the left node is with the lower terrain height and vice versa.
Subsequently, the simulation checks whether 60% of the Fresnel zone is blocked by terrains. If blocked, the simulation will proceed to Terrain Peak Calculation; else FSL calculation will be carried out for the free space phenomenon. There are path profiles that have clear LOS but with inadequate 60% clearance of the first Fresnel zone. The ground reflection in our proposed work is ignored in the Terrain Peak Calculation.
3.5. Terrain Peak Calculation. Generally, there exist many peaks (i.e., obstacles) between the transmitter and the receiver. However, not all the terrain peaks will affect the transmitter-receiver path loss computation. To determine whether a peak is a real obstacle, the following check is performed.
First, the function locates the highest peak from the obstacles in the transmitter-receiver path profile. By using the highest peak as the reference point, the function performs the search in both left and right directions to find out the other peaks that block the LOS between one of the antennas and the highest peak. If such a peak is found, then this peak will be considered as the new highest peak of that zone. This process is iterated until all the peaks that block the LOS propagation between the transmitter and the receiver are identified.
Finally, a smoothing function needs to be performed on all the stored terrain information to eliminate shallow irregularities where the peaks are much smaller than the wavelength of the radio frequency used.
3.6. Path Loss Calculation. The transmitter-receiver path loss computation is the addition of two different losses, that is, diffraction loss and free space loss. The diffraction loss is computed based on the Epstein-Peterson path geometry method which requires the coordinates to find the height of the relevant peaks located between the transmitter-receiver pair. For example, as shown in Figure 4, in order to obtain the height of H2 for the loss of Hill 2, draw the line from P1 (top of Hill 1) to P2 (top of Hill 2). The information of H1 and H2 will then be used for diffraction loss computation between Tx and Rx .
Subsequently, the Fresnel-Kirchhoff diffraction parameter v  can be computed as follows:
v = h [square root of 2([d.sub.1] + [d.sub.2])/[lambda][d.sub.1][d.sub.2]], (3)
where h is the height of the obstruction (e.g., H2 from Figure 4), [d.sub.1] is the distance of hill from one end, [d.sub.2] is the distance of hill from the other end, and [lambda] is the wavelength of the transmitted signal. Subsequently, the diffraction loss [G.sub.d] (v) is approximated using the Fresnel-Kirchhoff diffraction [10, 24] as follows:
[mathematical expression not reproducible]. (4)
Lastly, FSL can be computed using (1).
4. Experimental Results
4.1. Experimental Setup. To check the effectiveness of our proposed heterogeneous system based simulation network that makes use of CPU and GPU, we also construct a pure CPU based simulation framework. The CPU based simulation is developed using an Intel[R] Core[TM] i7-4500U CPU @ 1.80 GHz with 4 GB RAM, while the heterogeneous system based simulation uses a consumer grade GPU (GT 720 M) besides the aforementioned CPU.
The 7.5-minute DEM that has a vertical accuracy of 10meter resolution is used as it is the most accurate data available from USGS, which covers an area measuring 7.5 minutes of latitude and 75 minutes of longitude (also known as 7.5-minute quadrangle maps). We select seven maps (i.e., DEM data that represents seven different areas) and categorize them into two categories based on terrain elevation difference. Four maps (i.e., Adelanto, Amboy Crater, Jersey City, and Amsterdam) belong to the first category with terrain elevation difference lesser than 500 meters. Meanwhile, the other three maps (i.e., Arrowhead Butte, Acton, and Caples Lake) belong to the second category with terrain elevation difference of more than 500 meters. The different maps in Category 1 and Category 2 are shown in Figures 5 and 6, respectively.
4.2. Terrain Profile Analysis. Different from the conventional random walk model, we exclude the speed parameter of the mobile nodes as we only focus on the terrain profile analysis to determine the percentage of free space between a transmitter and a receiver. The speed of mobile nodes will not affect the judgment whether a path between a transmitter and a receiver is free from obstacles.
We perform 100 simulations for nine different linear distances ranging from 1 km to 9 km. The summary of the terrain profile analysis is shown in Table 1.
For a graphical illustration purpose, as shown in Figure 7, we take a few examples of 8-kilometer long path profiles for Adelanto. A path between transmitter-receiver pair is considered as a free path if no obstacles are found in the Fresnel zone; otherwise, the path is treated as a blocked path. We ignore the path profiles for other maps as it follows the same analysis of path profiles for Adelanto.
4.3. Path Loss Prediction Using Terrain Model. We perform the heterogeneous based path loss simulation using terrain model and point-to-point model where we fix the location of a transmitter at the centre of a map and compute the path loss between the fixed transmitter with a receiver that is located in every possible location. For comparison, we also perform the CPU based path loss simulation using point-to-point and disk models. For terrain model, additional terrain profiles between a transmitter and a receiver are extracted from DEM data provided by USGS. Notice that the location of fixed transmitter can be easily reallocated to any other location.
Figure 8 shows the path loss simulation calculated based on the disk model in the form of two-dimensional visualized image. All path loss simulations calculated based on the disk model on seven different maps share the same result as the path loss simulation based on the disk model solely depends on the distance between a transmitter and a receiver without considering the terrain profile between these two nodes. This pattern can be easily spotted through the ring shapes where the path loss simulations from the transmitter to the receiver with the same distance are always the same regardless of the terrain profile between the transmitter and the receiver.
Figure 9 shows the path loss simulation calculated based on the terrain model in the form of two-dimensional visualized image. Notice that all path simulations calculated based on the terrain model on seven different maps are all different as the path loss simulation based on the Epstein-Peterson method depends on both distance and terrain profiles between a transmitter and a receiver. Notice that the dark red line indicates higher path loss between a transmitter located at the centre of a map with a selected receiver. Please note that the maximum path loss in Figure 9 is limited to 120 dB to present a clear view with standardized color bar for all seven maps due to there being only a few points in the maps that have path loss above 120 dB.
We present some study cases of path loss simulation based on the terrain model on different map to highlight some important observations as follows.
Observation 1. The path loss between two nodes on two different locations with same distance may vary.
Example. As shown in Figure 10, Zone 1 shows a region with high path loss while Zone 2 has a much lower path loss. Thus, taking terrain profiles into consideration, the path loss between transmitter-receiver pair will be greatly affected.
Observation 2. The path loss between two nodes mainly depends on the irregular terrain profile between these two nodes. To be precise, the path loss between two nodes depends on the number of obstacles (i.e., peaks) that blocks the Fresnel zone between these two nodes.
Example. As shown in Figure 11, Zone 3 shows a region without obstacles and thus the path loss computation follows the disk model. Meanwhile, Zone 4 shows a region full of obstacles and thus the path loss computation follows the terrain model.
Observation 3. The typical strategy that places a transmitter in the highest position may not always result in a lower path loss between the transmitter and other receivers.
Example. As shown in Figure 12, a transmitter can be placed in any location within Zone 5 regardless of the height of the transmitter as most of Zone 5 regions are clear of the obstacles.
4.4. Speed Analysis between CPU Based and Heterogeneous System Based Path Loss Simulations. Figure 13 shows the speed comparison between CPU-only based path loss simulation and a heterogeneous system architecture (HSA) based path loss simulation in two different categories. Both types of path loss simulation are performed based on the terrain model that uses actual DEM data. Notice that, in the conventional CPU architecture, the entire path loss simulation is performed using the CPU-only based path loss simulation. Meanwhile, in the heterogeneous system architecture, a portion of the path loss simulation is parallelized and offloaded to the GPU for parallel processing, to counter the higher time complexity after including terrain model in the simulation. Overall, a simulation speedup of 20x to 42x is achieved for all seven selected maps, by just porting two of the most compute intensive processes into GPU for parallel processing to form the required path profile.
We have proposed an improved path loss simulation that incorporates 3D terrain model and for accelerated computation, GPU. The results obtained suggest that a more accurate path loss between a transmitter and a receiver can be predicted after considering the obstacles that block the Fresnel zone between the two nodes. More importantly, the proposed simulation framework has been integrated as a module into NS-3 for realistic path loss simulation which considers the terrain profiles between the transmitter-receiver pair. A speedup of 20x to 42x is achieved by offloading the computationally intensive components to GPU where the CUDA texture memory and faster interpolation computation are exploited. This framework can also be exploited by radio frequency engineers for speeding up the planning and deployment of transmitters in radio network. In addition, the advantage of this framework allows future research in accelerated computation involving multiple mobile nodes. Lastly, our proposed framework allows researchers to easily implement different path loss simulation models on NS-3 depending on the terrains they want to simulate by varying the parameters since most of these models rely on similar computations.
The authors declare that they have no competing interests.
This work was supported by Universiti Tunku Abdul Rahman under UTAR Research Fund (UTARRF/6200/C68) and MyBrain15 Scholarship. The Tesla K20 used for this research was donated by NVIDIA Corporation.
 T. W. Hwang, C. Y. Yang, G. Wu, S. Q. Li, and G. Y. Li, "OFDM and its wireless applications: a survey," IEEE Transactions on Vehicular Technology, vol. 58, no. 4, pp. 1673-1694, 2009.
 J. Mittag, S. Papanastasiou, H. Hartenstein, and E. G. Strom, "Enabling accurate cross-layer PHY/MAC/NET simulation studies of vehicular communication networks," Proceedings of the IEEE, vol. 99, no. 7, pp. 1311-1326, 2011.
 M. B. Rahaim, J. B. Carruthers, and T. D. C. Little, "Accelerated impulse response calculation for indoor optical communication channels," in Proceedings of the IEEE International Conference on Wireless Information Technology and Systems (ICWITS '12), pp. 1-4, Maui, Hawaii, USA, November 2012.
 A. F. Abdelrazek, M. Kaschub, C. Blankenhorn, and M. C. Necker, "A novel architecture using NVIDIA CUDA to speed up simulation of multi-path fast fading channels," in Proceedings of the IEEE 69th Vehicular Technology Conference (VTC '09), pp. 1-5, IEEE, Barcelona, Spain, April 2009.
 J. B. Carruthers, S. M. Carroll, and P. Kannan, "Propagation modelling for indoor optical wireless communications using fast multi-receiver channel estimation," IEE Proceedings--Optoelectronics, vol. 150, no. 5, pp. 473-481, 2003.
 P. Andelfinger, J. Mittag, and H. Hartenstein, "GPU-based architectures and their benefit for accurate and efficient wireless network simulations," in Proceedings of the 19th Annual IEEE/ACM International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems (MASCOTS '11), pp. 421-424, Singapore, July 2011.
 L. Djinevski, F. Sonja, M. Igor, and T. Dimitar, "Accelerating wireless network simulation in 3D terrain using GPUs," Adhoc & Sensor Wireless Networks, vol. 59, no. 1-4, pp. 253-264, 2015.
 C. Phillips, D. Sicker, and D. Grunwald, "A survey of wireless path loss prediction and coverage mapping methods," IEEE Communications Surveys & Tutorials, vol. 15, no. 1, pp. 255-270, 2013.
 L. Liu and H. Ma, "On coverage of wireless sensor networks for rolling terrains," IEEE Transactions on Parallel and Distributed Systems, vol. 23, no. 1, pp. 118-125, 2012.
 P. K. Chong and D. Y. Kim, "Surface-level path loss modeling for sensor networks in flat and irregular terrain," ACM Transactions on Sensor Networks, vol. 9, no. 2, article 15, 2013.
 Y. Okumura, E. Ohmori, and K. Fukuda, "Field strength and its variability in VHF and UHF land mobile radio service," Review of the Electrical Communication Laboratory, vol. 16, no. 9-10, pp. 825-873, 1968.
 M. Hata, "Empirical formulae for propagation loss in land mobile radio service," IEEE Transactions on Vehicular Technology, vol. 29, no. 3, pp. 317-325, 1980.
 T. S. Rappaport, Wireless Communications: Principles and Practice, Prentice Hall, Upper Saddle River, NJ, USA, 2002.
 H. T. Friis, "A note on a simple transmission formula," Proceedings of the IRE, vol. 34, no. 5, pp. 254-256, 1946.
 G. Zhou, T. He, S. Krishnamurthy, and J. A. Stankovic, "Impact of radio irregularity on wireless sensor networks," in Proceedings of the 2nd International Conference on Mobile Systems, Applications and Services (MobiSys '04), pp. 125-138, Boston, Mass, USA, June 2004.
 W. Su and M. Alzaghal, "Channel propagation characteristics of wireless MICAz sensor nodes," Ad Hoc Networks, vol. 7, no. 6, pp. 1183-1193, 2009.
 G. G. Joshi, C. B. Dietrich, C. R. Anderson et al., "Near-ground channel measurements over line-of-sight and forested paths," IEE Proceedings--Microwaves, Antennas and Propagation, vol. 152, no. 6, pp. 589-596, 2005.
 P. K. Chong, S.-E. Yoo, S. H. Kim, and D. Kim, "Windblown foliage and human-induced fading in ground-surface narrowband communications at 400 MHz," IEEE Transactions on Vehicular Technology, vol. 60, no. 4, pp. 1326-1336, 2011.
 J. Epstein and D. W. Peterson, "An experimental study of wave propagation at 850 MC," Proceedings of the IRE, vol. 41, no. 5, pp. 595-611, 1953.
 V. Jodalen, "An evaluation of the radio propagation models available in WinProp from AWE communications," http://rapporter.ffi.no/rapporter/2015/01525.pdf.
 D. A. Bibb, J. Dang, Z. Yun, and M. F. Iskander, "Computational accuracy and speed of some knife-edge diffraction models," in Proceedings of the IEEE Antennas and Propagation Society International Symposium (APSURSI '14), pp. 705-706, Memphis, Tenn, USA, 2014.
 S. Kasampalis, P. I. Lazaridis, Z. D. Zaharis et al., "Longley-Rice model prediction inaccuracies in the UHF and VHF TV bands in mountainous terrain," in Proceedings of the 10th IEEE International Symposium on Broadband Multimedia Systems and Broadcasting (BMSB '15), pp. 1-5, June 2015.
 F. Warmerdam, GDAL--Geospatial Data Abstraction Library: v1.11.2, http://gdal.osgeo.org.
 W. C. Y. Lee, Mobile Communications Engineering: Theory and Applications, McGraw-Hill, New York, NY, USA, 1997
Zhang Bin Loo, (1) Poh Kit Chong, (2) Kim Yee Lee, (1) and Wun-She Yap (1)
(1) Lee Kong Chian Faculty of Engineering and Science, Universiti Tunku Abdul Rahman, Selangor, Malaysia
(2) Infoblox Malaysia, Selangor, Malaysia
Correspondence should be addressed to Kim Yee Lee; firstname.lastname@example.org
Received 30 July 2016; Revised 13 October 2016; Accepted 18 October 2016; Published 12 January 2017
Academic Editor: Enrico M. Vitucci
Caption: Figure 1: Heterogeneous system overview.
Caption: Figure 2: Radio frequency line of sight.
Caption: Figure 3: Matrix rotation.
Caption: Figure 4: Epstein-Peterson path geometry method.
Caption: Figure 5: Category 1: low elevation terrain profiles.
Caption: Figure 6: Category 2: high elevation terrain profiles.
Caption: Figure 7: Adelanto terrain profiles.
Caption: Figure 8: Path loss simulation based on disk model.
Caption: Figure 9: Path loss simulation based on the Epstein-Peterson method.
Caption: Figure 10: Amsterdam path loss and 3D terrain map.
Caption: Figure 12: Arrowhead Butte path loss and 3D terrain map.
Caption: Figure 13: Comparison of path loss simulation time between CPU based and heterogeneous system based simulations.
Table 1: Terrain profile analysis. Terrain profile Terrain elevation (m) Path (%) Highest Lowest Difference Free space Block Adelanto 1010 838 173 56 44 Amboy Crater 664 179 485 26 74 Jersey City 106 0 106 30 70 Amsterdam 319 73 246 12 88 Arrowhead Butte 6405 5709 696 8 92 Acton 1992 703 1289 7 93 Caples Lake 10382 6576 3806 7 93
|Printer friendly Cite/link Email Feedback|
|Title Annotation:||Research Article|
|Author:||Loo, Zhang Bin; Chong, Poh Kit; Lee, Kim Yee; Yap, Wun-She|
|Publication:||Wireless Communications and Mobile Computing|
|Date:||Jan 1, 2017|
|Previous Article:||Distributed Image Compression Architecture over Wireless Multimedia Sensor Networks.|
|Next Article:||Efficiency Evaluation of Strategies for Dynamic Management of Wireless Sensor Networks.|