Riham Elhabyan
email: riham.elhabyan@carleton.ca

Wei Shi
email: wei.shi@carleton.ca

Marc St-Hilaire
email: marc.sthilaire@carleton.ca

An Obstacle-aware Clustering Protocol for Wireless Sensor Networks with Irregular Terrain

Keywords: Obstacle-aware, Clustering, WSNs

Clustering in Wireless Sensor Networks (WSNs) is considered an efficient technique to optimize the energy consumption and increase the Packet Delivery Rate (PDR). Most of the proposed clustering protocols assume that there is a Line of Sight (LOS) between all the sensors. In real situations, there are obstacles which could interfere this LOS. Moreover, most of the available WSNs simulators assume the use of optimistic path loss models that neglect the effect of the obstacles on the PDR. In this paper, we adopt an obstacle-aware path loss model to reflect the effect of the obstacles on the communication between any the sensors. The Castalia simulator is then adapted to use this the proposed path loss model. Moreover, we propose an obstacle-aware clustering protocol, the NSGA-based, Non-LOS Cluster Head selection (NSGA-NLOS-CH) protocol, to solve the CHs selection problem in WSNs with an irregular field. Simulation results have shown that the effect of the obstacles on the PDR cannot be neglected. Moreover, NSGA-NLOS-CH outperforms other competent protocols in terms of the PDR while maintaining an acceptable energy consumption at the same time.

Introduction

Clustering in Wireless Sensor Networks (WSNs) is considered an efficient technique to optimize the energy consumption. Many clustering protocols have been proposed in the literature to optimize the energy consumption in Wireless Sensor Networks (WSNs). Most of these protocols assume that the sensors are deployed in a Two-Dimensional (2D) network field. However, there is an increasing number of WSNs applications in which the network field is often a Three-Dimensional (3D) rolling terrains, such as volcano monitoring and landslide detection. Although recent studies have proposed clustering protocols for 3D WSNs [START_REF] Hai | Novel fuzzy clustering scheme for 3d wireless sensor networks[END_REF], these studies assume that the field is a 3D volume where sensors can be positioned freely within the whole 3D space. Compared to this free deployment in 3D space, in the case of deployment on rolling fields, sensors are deployed on the exposed surface and not freely within the 3D space. Therefore, these protocols cannot be applied to the rolling terrain either. Clustering protocols developed for 2D fields cannot be applied directly in such applications because the nature of the 3D rolling field may lead to the creation of obstacles in the network field. These obstacles have a substantial impact on the link quality between the communicating sensors as they cause an increased path loss. Therefore, determining the optimal set of CHs on the 3D rolling fields is a critical task.

Data delivery reliability is considered a key requirement in WSNs. In order to realize this requirement, clustering protocols should ensure high-quality links between the cluster members and their associated Cluster Heads (CHs). The Received Signal Strength Indicator (RSSI) is considered a prominent metric to assess the link quality between the transmitter and the receiver sensors. The RSSI calculation depends mainly on the adopted path loss model. Therefore, the performance of clustering protocols critically depends on the ability to accurately model the path loss of the communication signal between the transmitter and the receiver. A common limitation in most of the previously proposed clustering protocols is assuming the free space path loss model. The fundamental assumption behind this model is that the transmitter and the receiver sensors have a Line Of Sight (LOS) communication with no obstacles of any kind [START_REF] Kurt | Path-loss modeling for wireless sensor networks: A review of models and comparative evaluations[END_REF]. In real situations, there are almost always obstacles in the path between the transmitter and the receiver. Therefore, the free space path loss model is considered ideal and optimistic for predicting the path loss between any two sensors since it does not take the obstacles effect between the transmitter and the receiver into account [START_REF] Raheemah | New empirical path loss model for wireless sensor networks in mango greenhouses[END_REF]. Most of the available WSNs simulators assume the use of the free space path loss model [START_REF] Minakov | A comparative study of recent wireless sensor network simulators[END_REF]. The log-normal shadow fading model is proposed as an attempt to construct a more realistic path loss model by simulating the path loss around the sensors. Yet, this model does not account for the effect of the obstacles on the communication signal. Another significant limitation is that most of the existing clustering protocols assume the use of the first order radio model. However, this energy model is idealized and fundamentally flawed for modeling radio power consumption in sensor networks [START_REF] Elhabyan | Particle swarm optimization protocol for clustering in wireless sensor networks: A realistic approach[END_REF].

Castalia is a popular and very efficient WSN simulator that provides a welldesigned channel model [START_REF] Minakov | A comparative study of recent wireless sensor network simulators[END_REF] and adopts a realistic energy consumption model that is based on the characteristics of the Chipcon CC2420 radio transceiver data sheet. However, Castalia adopts the log-normal shadow fading model and hence shares the same drawback as most of the available WSNs simulators with regard to accurately modeling the path loss in case of No Line Of Sight (NLOS) communication, i.e. when there are obstacles between the transmitter and the receiver.

Contributions

As we discussed earlier, obstacles have a great impact on both the design of clustering protocols for WSNs and the simulation and evaluation of the performance of these protocols. Therefore, the purpose of this paper is twofold. First, to design, implement and test an obstacle-aware clustering protocol to solve the CHs selection problem in 3D rolling fields. Since the CHs selection problem has been proven to be a Non-deterministic Polynomial (NP)-hard problem with many conflicting objectives, a Pareto-based Evolutionary Algorithm (EA) is adopted to solve this problem. The proposed protocol takes into consideration the following key requirements: the network's energy efficiency, the network's data delivery reliability, and the protocol's scalability. Second, to test and investigate the performance of the proposed protocol against well-known clustering protocols, in the existence of obstacles and under a realistic energy consumption model. The main contributions of this paper are listed below:

-We adapt an obstacle-aware path loss model to evaluate the effect of the obstacles in the communication between any two sensor nodes. In order to achieve that, we implement a visibility function to find the obstacles in the path between any two sensors. This function is implemented based on the Bresenham's algorithm. Based on the adopted path loss model, a path loss map is derived. The Castalia simulator is then modified to use this map to calculate the path loss and the RSSI values between any two sensors in the network.

-We propose a new EA-based clustering protocol for 3D WSNs where the network field is a 3D rolling terrain. -In order to realize the aforementioned contributions, the network field is modeled using the Digital Elevation Model (DEM) to account for different elevations, and hence obstacles, in the field. The novelties of the proposed research work are as follows: a) To the best of our knowledge, the proposed clustering protocol is the first to consider and test the obstacles' effect on the communication between the sensors, b) Experimental validation are performed on real elevation data for 3D terrains.

Paper Organization

The remainder of this paper is organized as follows. Section 2 presents the related work on protocols designed for 3D WSNs. Section 3 presents the system model and assumptions. The design of the obstacle-aware clustering protocol and the problem formulation are provided in section 4. A detailed analysis of the simulations results is provided in Section 5. Finally, Section 6 concludes this paper and highlights future research directions.

Related Works

The Low Energy Adaptive Clustering Hierarchy for 3D WSNs (LEACH-3D) protocol [START_REF] Baghouri | Low energy adaptive clustering hierarchy for three-dimensional wireless sensor network[END_REF] is a direct extension of the original LEACH protocol and is considered the first clustering protocol designed for 3D WSNs. The first order radio model, which is initially proposed by LEACH, is extended to work for 3D WSNs. Based on this extension, the authors prove that the effect of the 3D environment on clustering protocols cannot be neglected. LEACH-3D uses a variable number of CHs and different number of CHs could be elected each round.

A Fuzzy-based Clustering Scheme for 3D WSNs (FCM-3) is proposed in [START_REF] Hai | Novel fuzzy clustering scheme for 3d wireless sensor networks[END_REF] to apply clustering protocols in 3D WSNs. The proposed protocol assumes the radio model which is proposed in [START_REF] Baghouri | Low energy adaptive clustering hierarchy for three-dimensional wireless sensor network[END_REF]. The adopted fuzzy approach optimizes one objective function which is defined as minimizing the total energy consumption and is constructed by combining the distances between sensor nodes and their corresponding CHs and between the CHs and the Base Station (BS) into the radio model. FCM-3 defines two constraints to ensures single-hop connections for the intra-cluster and inter-cluster communication. Similar to LEACH-3D, the number of CHs is variable. However, experimental results show that FCM-3 achieves the best performance when the number of CHs is from 20% to 30% of the network size, which is considered a high number.

A Particle Swarm Optimization (PSO)-based Protocol for CHs selection (PSO-CH) [START_REF] Elhabyan | Particle swarm optimization protocol for clustering in wireless sensor networks: A realistic approach[END_REF] is a centralized PSO-based protocol that is used to find the optimal set of CHs. The PSO-CH protocol considers the following properties: the network's energy efficiency, data transmission reliability, and the protocol's scalability. The objective function that is used to evaluate each candidate solution is defined as the weighted sum of three sub-objectives, each of which is related to the aforementioned properties. PSO-CH is designed and implemented under realistic networks settings and realistic energy consumption model. The link quality estimation in PSO-CH is based on the Received Signal Strength Indicator (RSSI) of received packets.

All the aforementioned protocols are applicable to 3D WSNs. However, the path loss model adapted by these protocols ignore the effect of the obstacles on the communication between the sensors. They also assume that the field is a 3D volume where the sensors can be positioned freely within the field. Moreover, all these protocols assume the use of an ideal energy consumption model.

The Surface-Level Irregular Terrain (SLIT) path loss model [START_REF] Chong | Surface-level path loss modeling for sensor networks in flat and irregular terrain[END_REF] is a semiempirical path loss model for WSN with irregular terrain. The SLIT model uses the terrain information, expressed by the DEM data, to provide a fast and an accurate estimation of the large-scale path loss due to the obstacles existing in the field. The total path loss is expressed as a function of both the free-space path loss and the path loss due to the obstacles in the field, which is calculated using the Epstein-Peterson diffraction loss model [START_REF] Epstein | An experimental study of wave propagation at 850 mc[END_REF]. In order to verify the SLIT model, empirical experiments are conducted and the average difference between the measured results and the predicted results from the SLIT model are recorded. Experimental results have shown that the SLIT model provides an accurate path loss model that accounts for the terrain profile.

In this paper, we adopt the SLIT path loss model [START_REF] Chong | Surface-level path loss modeling for sensor networks in flat and irregular terrain[END_REF] and propose an obstacleaware clustering protocol for 3D WSNs to evaluate the effect of obstacles on clustering protocols.

The System Model

The 3D rolling field is modeled using the Digital Elevation Model (DEM). The DEM is a digital representation of a given ground surface topography or terrain. In the DEM, the network field is represented as a matrix of cells, where each cell holds a value that represents the average elevation of the area contained by that cell. DEMs are commonly built using remote sensing technology or from land surveying, and are usually available to download. For example, the geospatial data extraction tool [START_REF]Geospatial data extraction[END_REF] is part of Natural Resources Canada's altimetry system designed to meet the users' needs for elevation data and products. This tool provides data from seamless national datasets based on custom-defined geographic area and customized data options. The main motivation to adopt the DEM in our proposed protocol is to be able to simulate a realistic 3D rolling field and to find the obstacles between any two sensor nodes in the network. The sensors are assumed to be uniformly deployed in a 3D rolling field. Based on the DEM data, the height coordinate of a sensor located at position (x, y) is restricted to the field's elevation at that specific position.

For the energy consumption model, a discrete-based realistic model which is based on the characteristics of the Chipcon CC2420 radio transceiver data sheet [START_REF]Texas Instruments: Chipcon CC2420 radio transceiver data sheet[END_REF] is used. The total energy consumed by sensor node n, consumedE n , is calculated as follows [START_REF] Barberis | Evaluating energy consumption in wireless sensor networks applications[END_REF]:

consumedE n = statej P statej × t statej + tr E transitions (1)
The index statej refers to the energy states of the sensor: sleep, reception, or transmission. P statej is the power consumed in each statej, t statej is the time spent in the corresponding state, and tr is the number of transitions for S. The energy spent in transitions between states, E transitions , is also added to the node's total energy consumption. The different values of P statej and E transitions can be found in [START_REF]Texas Instruments: Chipcon CC2420 radio transceiver data sheet[END_REF].

For the path loss model, we adopt the SLIT path loss model [START_REF] Chong | Surface-level path loss modeling for sensor networks in flat and irregular terrain[END_REF] to find the path loss between any two sensors.

An Obstacle-aware Clustering Protocol for WSNs with Irregular Terrain

The network operating time of the proposed protocol is divided into rounds. Each round consists of two phases, the set-up phase, and the steady-state phase. The operation of these phases is similar to that of [START_REF] Elhabyan | Particle swarm optimization protocol for clustering in wireless sensor networks: A realistic approach[END_REF]. In this paper, we focus on the protocol adopted by the BS in the set-up phase to find the optimal set of CHs and clusters. We refer to the proposed protocol as the NSGA-based, Non-LOS CH selection (NSGA-NLOS-CH) protocol which includes six different processes as illustrated below:

DEM Extraction

The geospatial data extraction tool [START_REF]Geospatial data extraction[END_REF] provided by Natural Resources Canada is used to extract the elevation data for a given network field. Based on the DEM data for a given network field, the BS constructs an elevation matrix that holds the elevation data for all the cells contained by the network field. The ArcGIS software package is utilized to generate and extract the elevation data given the DEM data for that field.

LOS Algorithm

A Line of Sight (LOS) algorithm is needed to find the obstacles in the communication link between any two sensors in the field. In this paper, the Bresenham LOS algorithm is utilized to implement the visibility function. The Bresenham algorithm is often used in computer graphics for line drawing on 2D surfaces. In this paper, we have modified it to be used for LOS determination on 3D rolling fields. In this algorithm, if the elevation of any corresponding points between the transmitter and the receiver does not cut the virtual line drawn between them, then there is a LOS between the transmitter and the receiver. Otherwise, it is said that there is NLOS (non-LOS) between them. In this paper, an obstacle is defined as the point which has an elevation higher than that of the transmitter or the receiver. The LOS algorithm returns a visibility matrix that has N rows and N columns, where N is the total number of sensors. This visibility matrix holds the path loss of all the obstacles between any two sensors in the network.

Path Loss Map Calculation

Based on the visibility matrix, a path loss map is generated by the BS. This map reflects that path loss between any two communicating sensors in the network and is calculated using the SLIT path loss model. The Castalia simulator is then modified to use this path loss map instead of the one provided by the log-normal shadow fading model to calculate the propagation loss and the RSSI values for the links between any two communicating sensors.

Finding the Optimal Set of CHs

Once the modified RSSI values are calculated, the BS runs an EA-based algorithm to find the optimal set of CHs. In this paper, we adopt the Non-dominated Sorting Genetic Algorithm II (NSGA-II) as an optimization tool to find the optimal set of CHs. The problem formulation for the adopted NSGA-based algorithm is provided in the next section. Table 1 presents the main notations used in this paper.

k i Cluster number k generated from Ci, 0 ≤ ki < Ki CH k i Cluster head number k generated from Ci, 0 ≤ ki < Ki |CL k i | Number of sensors clustered in CL k i E(n)
Remaining energy of node n initialE(n) Initial energy of node n RSSI (n,CH k i ) RSSI value for the link from n to CH k i LQ (n,CH k i ) Link quality for the link from n to

CH k i LQ (n,CH k i ) = RSSI(n,CH k i ) -100
Decision Variables In the proposed protocol, a sensor node may be in one of two states: a CH, or non-CH. To find the optimal set of CHs, a random initial population P is generated and evolved by the adopted EA. Each candidate solution (chromosome) C i in P has a dimension equal to the network size minus the BS (i.e., N -1). Binary encoding is adopted to represent each chromosome, where the size of each component of

I i is 1 bit. Let, C i = [X i,1 , X i,2
, X i,3 , ..., X i,N -1 ] be the i th chromosome of P where each component, X i,n , 1 ≤ n ≤ N -1 maps the state of sensor n. Each component X i,n of chromosome C i is initialized with either 1 to indicate that sensor n is a CH node, or 0 to indicate that n is non-CH node. It should be noted that this encoding process will result in a variable number of CHs. Table 2 shows the random sequences created for two individuals in P on a network including 10 sensor nodes other than the BS. Each row presents a solution for a chromosome in P . For example, in chromosome C 1 sensors 2, 5 and 10 are CHs while the rest of the sensors are non-CH nodes.

Table 2. Chromosomes Population

Node ID 1 2 3 4 5 6 7 8 9 10

I1 0 1 0 0 1 0 0 0 0 1 I2 0 0 1 1 1 0 0 0 1 0
The clusters are formed by associating each non-CH node to its closest CH that has the lowest RSSI value. After the clustering process ends, each sensor node belongs to only one cluster and each cluster head node acts as the CH of exactly one cluster.

Objective Functions Each chromosome C i is evaluated according to four objective functions, which are briefly described in Table 3 and defined below.

K i = N -1 n=1 1, if X i,n = 1 (2)
U i = N - Ki ki=1 |CL ki | (3)
L i = max k=1,2,...,K ∀n∈CL k LQ (n,CH k i ) |CL ki | (4)
E i = N n=1 initialE(n) E(n) , if X i,n = 00 (5)
It should be noted that the calculation for L i in the proposed protocol depends on the newly derived RSSI values which depend on the generated path loss map.

Simulation Results and Analysis

The NSGA-NLOS-CH protocol and the proposed path loss model are implemented in Castalia. In addition, we have implemented both LEACH-3D and PSO-CH. The simulations are performed on elevation data from the Armadillo Peak volcano in British Columbia, as illustrated in Figure 1. The DEM of this field is obtained using the geospatial data extraction tool [START_REF]Geospatial data extraction[END_REF] provided by Natural Resources Canada. In order to generate the elevation data, a 20 × 20 fishnet is constructed using the ArcGIS software on a scaled version of the network field. The network field is scaled down to 100 × 100 meters. The sensors are deployed randomly and their position is restricted by the elevation of the rolling field. The initial energy of the sensors is set as 18720 J. Each round is 500s and the number of rounds is 5. We vary the total number of sensors from 100 to 500. In this section, we consider the following objectives:

1. Investigate the effect of the obstacles on the Packet Delivery Rate (PDR).

2. Compare the performance of all the competent protocols in the existence of obstacles. The comparison is done in terms of the PDR, the number of elected CHs, the energy consumption and the average number of unclustered nodes per round.

We consider two cases to investigate the effect of the obstacles on the PDR. In the first case, we assume that there is a LOS between all the sensors and that there are no obstacles in the rolling field. For this case, the log-normal shadow fading model is used to calculate the path loss and we refer to the proposed protocol as the NSGA-LOS-CH protocol. In the second case, we use the provided elevation data to find the obstacles in the field and we use the proposed obstacle-aware path loss model. For this case, we refer to the proposed protocol as the NSGA-NLOS-CH protocol. Figure 2 shows the PDR for both of these cases. It is clearly shown that ignoring the effect of the obstacles, as in the case of NSGA-LOS-CH, can lead to more optimistic PDR values. It is also noted that the PDR of NSGA-NLOS-CH increases with the increase in the number of sensors. Increasing the number of sensors in the same network field area leads to constructing shorter links for communication with a lower probability of obstacles that could interfere those links. Next, the performance of all the competent protocols is compared in the existence of obstacles. Figure 3 shows the PDR for all the protocols. It is clearly shown that NSGA-NLOS-CH outperforms the other protocols in terms of the PDR. This is due to the fact that NSGA-NLOS-CH clusters the network based on the RSSI values that are derived from the proposed path loss model. This leads to creating clusters that are adopted for the field profile. While PSO-CH uses the RSSI values as criteria for clustering the network, the way the RSSI calculated does not take into consideration the obstacles in the field. LEACH-3D uses a totally random mechanism when electing the CHs and this, in turn, does not guarantee a high PDR. Figure 4 shows the average number of CHs per round for all the protocols. It is noted that the NSGA-NLOS-CH protocol results in a higher number of CHs. Unlike PSO-CH, the number of CHs in NSGA-NLOS-CH is variable. Moreover, NSGA-NLOS-CH uses a Pareto-based approach to optimize all of its objectives concurrently. In the existence of obstacles, a higher number of CHs needs to cluster the whole network in order to achieve the scalability objective. The average consumed energy per sensor is shown in Figure 5. NSGA-CH-NLOS has a slightly higher energy consumption than that of PSO-CH because NSGA-CH-NLOS elects a higher number of CHs as shown in Figure 4. These CHs have to stay active during the whole round which leads to a higher level of energy consumption. On the other hand, LEACH-3D has a very high energy consumption level. Experimental results have shown that LEACH-3D results in a very high number of unclustered sensors. These unclustered sensors stay active during the whole round and consume more energy. On the other hand, both NSGA-CH-NLOS and PSO-CH are able to cluster all the sensors. The average number of unclustered sensors per round is shown in Figure 6. In this paper, we adopt an obstacle-aware path loss model to account for the effect of the obstacles in the network field. In order to locate those obstacles, the 3D rolling field is modeled using the DEM. Based on the adopted path loss model, an obstacle-aware clustering protocol, NSGA-NLOS-CH, is proposed. Simulation results have shown that the effect of the obstacle on the PDR cannot be neglected. Moreover, NSGA-NLOS-CH outperforms both PSO-CH and LEACH-3D in terms of the PDR while maintaining an acceptable energy consumption at the same time.

The coverage problem in 3D WSNs with a rolling field is another fundamental problem. As a future research direction, an integrated solution for both the clustering and coverage problems in an irregular field should be investigated.

Fig. 1 .

 1 Fig. 1. Scaled version of the Armadillo Peak volcano in British Columbia

Fig. 2 .

 2 Fig. 2. PDR for NSGA-LOS-CH and NSGA-NLOS-CH

Fig. 3 .

 3 Fig. 3. PDR

Fig. 4 .

 4 Fig. 4. The average number of CHs per round

Fig.Fig. 6 .

 6 Fig. The average consumed energy per sensor (in Joules)

Table 1 .

 1 Notations

	Symbol	Definition
	P	Population generated from the adopted EA
	N	Total number of sensors
	n	Sensor number n, 0 ≤ n < N
	Ii	Individual number i of P
	Xi,n	Component number n of Ci
	Ki	Total number of clusters generated from Ci
	CL

Table 3 .

 3 The Objective Functions

	Objective Function Description	Goal
	Ki	Minimize the total number of CHs	Save energy
	Ui	Minimize the number of unclustered sensors	Enhance scalability
	Li	Maximize the link quality for the inter-cluster communication Data delivery reliability
	Ei	Maximize the total remaining energy of the CHs	Balance energy consumption


Dmitri Moltchanov

Aleksandr Ometov
email: aleksandr.ometov@tut.fi

On the Fraction of LoS Blockage Time in mmWave Systems with Mobile Users and Blockers

Today, one of the emerging trends for the next generation (5G) networks is utilizing higher frequencies in closer premises. As one of the enablers, small cells appear as a cost-effective way to reliably expand network coverage and provide significantly increased capacity for end users. The ultra-high bandwidth available at millimeter (mmWave, 30-300GHz) and Terahertz (THz, 0.3-3THz) frequencies can effectively realize short-range wireless access links in small cells. Those technologies could also be utilized for direct communications for users in proximity. At the same time, the performance of mobile wireless systems operating in those frequency bands depends on the availability of lineof-sight (LoS) between communicating entities. In this paper, we estimate the fraction of LoS time for randomly chosen node moving according to different mobility models in a field of N moving blocking nodes for both base station and device-to-device (D2D) connectivity scenarios. We also provide an extension to the case of a random number of moving blockers. The reported results can be further used to assess the amount of traffic offloaded to other technologies having greater coverage, e.g., LTE.

Background and Motivation

Due to tremendous increase in traffic demand, researchers in both industry and academia already focus on numerous advanced networking solutions such as client-relaying [START_REF] Deng | Resource Allocation and Interference Management for Opportunistic Relaying in Integrated mmWave/sub-6 GHz 5G Networks[END_REF], heterogeneous networking [START_REF] Galinina | Capturing spatial randomness of heterogeneous cellular/WLAN deployments with dynamic traffic[END_REF], the use of micro/pico/femto cells [START_REF] Prasad | Energy efficiency in massive MIMO-based 5G networks: Opportunities and challenges[END_REF] and Device-to-Device (D2D) communications [START_REF] Ometov | Toward trusted, social-aware D2D connectivity: bridging across the technology and sociality realms[END_REF][START_REF] Pyattaev | Networkassisted D2D communications: Implementing a technology prototype for cellular traffic offloading[END_REF][START_REF] Ometov | Modeling Unreliable Operation of mmWave-Based Data Sessions in Mission-Critical PPDR Services[END_REF] to satisfy the requirements of fifth generation (5G) mobile wireless systems. These mechanisms alone, however, are limited in achieving the required data rates.

One of the initial steps forward is moving up in the frequencies from microwaves to millimeter waves (mmWave, 30 -300GHz) [START_REF] Andreev | Future of Ultra-Dense Networks Beyond 5G: Harnessing Heterogeneous Moving Cells[END_REF] and further to the terahertz (THz, 0.3-3THz) band [START_REF] Petrov | Terahertz band communications: Applications, research challenges, and standardization activities[END_REF] is considered as a viable solution to principally increase the capacity of wireless channels and eventually satisfy the requirements of 5G-grade networks. Operating at those frequencies could be described by the following features: (i) higher throughput; (ii) shorter propagation distances due to higher attenuation; (iii) better spatial resolution due to smaller beamwidth; (iv) smaller antenna size in general; and (v) higher blockage affection.

The principle discord between mmWave/THz systems, compared to microwaves, is that there is an extreme difference in the received signal strength in line-of-sight (LoS) and nLoS conditions [START_REF] Deng | 28GHz and 73GHz millimeter-wave indoor propagation measurements and path loss models[END_REF][START_REF] Maccartney | Path loss models for 5G millimeter wavepropagation channels in urban microcells[END_REF]. Such systems are expected to be installed in open indoor and outdoor environments such as conference halls, lobbies, squares, crossroads, parks [11]. Nevertheless, as electromagnetic waves cannot "travel around" the objects whose size is smaller than their wavelengths while the human bodies serve as perfect absorbers [START_REF] Yang | Numerical analysis and characterisation of THz propagation channel for body-centric nano-communications[END_REF], the crowd around the receiver blocks the LoS. To understand performance bounds of mmWave and THz systems, it is essential to predict the probability of having LoS at a particular instant of time as well as the fraction of time there is a LoS between communicating entities in crowded mobile environments.

The question of the LoS propagation blockage has recently received particular attention from the research and standardization community [START_REF] Metis | Initial channel models based on measurements[END_REF][START_REF]3GPP: Channel model for frequency spectrum above 6 GHz (Release 14)[END_REF]. As demonstrated by field measurements in [START_REF] Haneda | 5G 3GPP-like channel models for outdoor urban microcellular and macrocellular environments[END_REF], the loss of LoS path in mmWave systems may result in sharp drops of the (up to 30 ∼ 40dB) in the received signal strength. The first analytical studies on this topic addressed the question of LoS blockage in environments with static users and static blockers [START_REF] Gapeyenko | Analysis of human body blockage in millimeter-wave wireless communications systems[END_REF][START_REF] Bai | Analysis of blockage effects on urban cellular networks[END_REF]. These results have been recently extended to the case of moving blockers and static users in [START_REF] Gapeyenko | On the temporal effects of mobile blockers in urban millimeter-wave cellular scenarios[END_REF] as well as static blockers and moving users in [START_REF] Samuylov | Characterizing spatial correlation of blockage statistics in urban mmwave systems[END_REF]. In these studies, it has been shown that the mobility of both blockers and users drastically affect the blockage statistics leading to additional uncertainly in channel state. However, to the best of the authors' knowledge, there have been no studies addressing the case when both blockers and users are simultaneously mobile.

In this paper, we derive the probability of having nLoS at a random instant of time as well as the fraction of LoS for a user in a group of N + 1 blockers moving around in closed indoor compartment according to the random direction mobility (RDM) and random waypoint (RWP) models. We consider mmWave access point (AP) and D2D scenarios and also sketch the extension to the open outdoor scenarios, where a user and blockers may freely enter and leave the service area of interest. The presented results can further be used to assess the amount of traffic that needs to be offloaded to another type of connection.

The rest of the manuscript is organized as follows. Section 2 provides the system model and depicts the scenarios of interest. Next, we elaborate on the applicability of the model to dynamic conditions and extend it in Section 3. The numerical examples are given in Section 4. The last section concludes the manuscript.

Indoor Closed Compartment Scenario

Two scenarios of interest are described in this section. We focus on both conventional infrastructure-based case, where AP serves the tagged user and the remaining ones act as potential blockers, and D2D scenario, where two users are attempting to initiate direct link that could be blocked by other users. Both users and blockers are mobile and move according to a RDM mobility model [START_REF] Nain | Properties of random direction models[END_REF]. Recall that according to RDM a point first randomly chooses the direction of movement uniformly in (0, 2π). Then, it moves in the chosen direction for exponentially distributed time with constant speed v. The process is restarted at the stopping point.

Access Point Scenario

In the first scenario, we assume N + 1 mobile users (UEs), acting as blockers, that randomly move according to RDM in the coverage area with radius r of a mmWave or THz AP, which height is h T x (AP is selected as transmitter (Tx)). The height of the blockers is assumed to be the constant and equal to h B . The radius of a blocker is r B . The height of the receiver (Rx) associated with the tagged UE is h Rx < h B . We are interested in the probability of nLoS at the arbitrary time instant and the fraction of nLoS. Note that these metrics are symmetric irrespective of which entity (AP or UE) acts as Tx or Rx correspondingly.

We assume that UE is located at the distance x from the AP at time t, as shown in Fig. 1(a). The LoS to the UE could be blocked by the blockers that are located in the so-called LoS blocking zone, marked in gray. The length of this zone is

d(x) = x(h B -h Rx ) h T x -h Rx . (1)
Observing the top view of the scenario, Fig. 2(a), notice that the area of the LoS blocking zone is more complicated than a rectangle. To prevent overlapping there cannot be a blocker located closer than at 2r B to the user. The area of the LoS blocking zone is The existence of the zone around the UE prohibiting the presence of blockers implies that the minimum distance from the AP resulting in non-zero LoS blocking zone is 2r B . Recall that the limiting distribution of the RDM is uniform over the area of interest [START_REF] Nain | Properties of random direction models[END_REF]. Observing the system in stationary regime, the probability of a point uniformly distributed in the circle hitting an LoS blocking area is given by the ratio S B /πr 2 . Generalizing to N blockers, we arrive at

S B = 2r B [x -d(x)] -2r 2 B - 1 2 πr 2 B . (2)
p B (N) = 1 -1 - 2r B [x -d(x)] -2r 2 B -1 2 πr 2 B πr 2 N . (3)
The probability density function (pdf) of a point uniformly distributed in a circle of radius r is given by f (x) = 2x/r 2 . Thus, the probability of having nLoS at a random instant of time, p nL , coinciding with the fraction of nLoS, f nL , is

f nL = r 2r B 2x r 2   1 -1 - 2r B [x -d(x)] -2r 2 B -1 2 πr 2 B πr 2 N   dx. (4)
Integrating ( 4) we arrived at the final result in the following closed-form

f nL = 1 - 4r 2 B r 2 - 4(A-1)r 2 B +B+πr 2 r 2 N+1 [πr 2 -4(A -1)(N + 1)r 2 B + B] 2π N (A -1) 2 (N + 1)(N + 2)r 2 B + (5) + r(2(A-1)r B +πr)+B r 2 N+1 [r(πr -2(A -1)(N + 1)r B ) + B] 2π N (A -1) 2 (N + 1)(N + 2)r 2 B , (6)
where the shortcuts are

A = (h B -h Rx ) h T x -h Rx , B = 2r 2 B - πr 2 B 2 . ( 7
)

D2D Scenario

Since the height of Tx and Rx is assumed to be the same, h T x = h Rx < h B , it suffices to consider two dimensional case, as shown in Fig. 2(b). Given the distance x between Tx and Rx the area of the LoS blocking zone is

S B (x) = 2r B x -4r 2 B -πr 2 B . (8)
Similarly to the AP blocking model, there is no blocking when Tx and Rx are closer than 4r B . Recalling the stationary property of RDM model and the fact that the distance between two points uniformly distributed in the circle of radius πr 2 is given by [START_REF] Moltchanov | Distance distributions in random networks[END_REF]

f (x) = 2x r 2 2 π arccos x 2r - x rπ 1 - x 2 4r 2 , 0 < x < 2r, (9)
we have the following for the fraction of nLoS

f nL = r 4r B f (x) 1 -1 - 2r B x -4r 2 B -πr 2 B πr 2 N dx, (10)
that also coincides with the nLoS blocking probability. Note that the integral cannot be expressed in elementary functions but can be computed numerically.

3 Extensions and applications

Outdoor environment

The scenarios considered previously are unrealistic for outdoor deployments, where blockers/user may freely enter and leave an area of interest. For AP scenario this area coincides with the service area of aN AP while for the D2D case this is the area, where D2D connectivity is feasible, e.g., UE proximity characterized by the short-range radio coverage area. In this section, we address this by introducing dynamics to the model. Let A 0 be the circular service area of an AP and let A 1 be the greater circular area where N blockers are allowed to move according to RDM. We are interested in the probability that a randomly chosen node currently located in the AP service area is in nLoS state. This probability no longer coincides with the fraction of nLoS as the latter needs to be obtained knowing the AP service area residence time of a user.

Recall that in the stationary regime N nodes moving in A 1 are uniformly distributed in A 1 [START_REF] Nain | Properties of random direction models[END_REF]. Thus, the number of nodes in A 0 follow binomial distribution with parameter A 0 /A 1 and these nodes are all uniformly distributed in A 0 . Increasing A 1 and N such that λ = N/S A 1 is kept constant p = A 0 /A 1 → 0 and the binomial distribution approaches the Poisson one with parameter λ. Thus, the probability of having LoS at the distance x, p L (x), is given by the void probability of a Poisson process with the area estimated in (2), i.e.,

p L (x) = exp -λ 2r B [x -d(x)] -2r 2 B - 1 2 πr 2 B , (11)
where d(x) is provided in [START_REF] Deng | Resource Allocation and Interference Management for Opportunistic Relaying in Integrated mmWave/sub-6 GHz 5G Networks[END_REF]. The probability that a node is moving according to RDM and located in A 0 at time t experiences nLoS conditions is obtained similarly to (4) with exponential blocking probability replacing the binomial one. It is provided in [START_REF] Yang | Numerical analysis and characterisation of THz propagation channel for body-centric nano-communications[END_REF]. For D2D scenario the integral for nLoS probability is similar to [START_REF] Maccartney | Path loss models for 5G millimeter wavepropagation channels in urban microcells[END_REF], with 1p L (x) from (11) replacing the binomial blocking. It also cannot be solved in elementary functions but can be numerically evaluated with any given accuracy.

p nL = r 2r B 2x r 2 1 -e -λ[2r B [x-d(x)]-2r 2 B -π/2r 2 B ] = = 1 - e λr B ([π+4]r B -2r) (2λrr B + 1) -32λ 2 r 4 B 2λ 2 r 2 r 2 B + e (π-4)λr 2 B 8λr 2 B + 1 2λ 2 r 2 r 2 B . ( 12
)
To evaluate the fraction of nLoS for outdoor deployment, it is necessary to obtain the time corresponding to the UE staying in the service area A 0 . This is a first passage time in a circle for a random point moving according to RDM with some initial position that depends on the size of A 0 and parameters of RDM model. Neither pdf nor mean of this metric can be obtained analytically [START_REF] Weiss | Aspects and applications of the random walk[END_REF]. Nevertheless, one could always use computer simulations or Brownian motion approximation of RDM (see [START_REF] Weiss | Aspects and applications of the random walk[END_REF], Ch. 4) to quantify this metric.

Further extensions

We specifically note that the the model proposed in this paper can be extended in many different ways. First of all, one can use any mobility model having well-defined stationary distribution, for example, random waypoint (RWP) mobility model whose distribution in a square with side A is available in closed form [START_REF] Bettstetter | Stochastic properties of the random waypoint mobility model[END_REF], i.e.,

f X,Y (x, y) = 36 A 6 x 2 - A 2 4 y 2 - A 2 4 . (13)
The only additional step compared to the presented model is to determine the distance to the mmWave AP or the distance between two nodes. This can be done applying the random variables transformation technique. Notably, for the AP to UE case, the transformation of interest reads as r(x, y) = x 2 + y 2 and the procedure is reduced to finding the Jacobian of the transformation [START_REF] Ross | Introduction to probability models[END_REF].

We also would like to specifically note that LoS blockage does not always lead to the outage event, i.e., for a given propagation model the outage even may only occur when the current distance between communicating nodes is higher than the specific value. The result for a fraction of time can be extended to this case as well. Considering AP to UE scenario as an example, we first obtain the fraction of time UE is farther than a certain propagation distance D, then observe that the UE position conditional on being farther than D is still uniformly distributed in the ring (D, R) with density f (x) = 2x/(R 2 -D 2 ) and then determine the fraction of LoS blockage time using f (x).

In this section, we illustrate the obtained numerical results. First, we consider the LoS blockage probability for AP to UE communications scenario. We then address D2D communications case. Finally, we consider the outdoor scenario with a Poisson distribution of the number of blockers.

Consider first the AP to UE indoor communications scenario. Fig. 4 illustrates the fraction of LoS blockage time as a function of systems parameters including mmWave AP height, h A , and UE height, h U for a range of the number of blockers in the compartment. In these illustrations, the height of Rx is set to 1.2 meters, and the height of blockers is 1.7 meters. The radius of the coverage is 30 meters. Expectedly, as the number of blockers increases the probability of LoS blockage increases. Further, it is essential to observe that the change in AP and UE heights does not drastically affect the blockage probability. The most significant effect stems from the number of blockers in the area. The effect of input parameters on the fraction of LoS blockage time for the D2D scenario is illustrated in Fig. 4 as the function of the number of blockers for different radii of the service area. Recall that in this scenario the height of communicating entities is the same. Logically, by keeping the number of blockers constant and increasing the service area of interest the fraction of LoS blockage time increases. Finally, by comparing the results in Fig. 4 with Fig. 3(a) and 3(b), we observe that the fraction of the LoS blockage time for the D2D scenario is significantly bigger. The rationale is that in the case of D2D communications the heights of entities are all the same implying that the area of the LoS blockage zone is significantly larger.

Finally, we compare the fraction of LoS blockage time in indoor and outdoor scenarios for AP to UE case. The comparison is facilitated by parameterizing indoor model In this manuscript, we derived the probability of nLoS and the fraction of time a user spends in nLoS state in a group of N blockers moving according to RDM in the indoor closed compartment for both AP and D2D connectivity cases. We then provided the extension to the case for outdoor deployment, where UEs freely enter and leave the service area. Our results apply to performance analysis of mmWave and THz wireless systems.

The central application area of the proposed model is performance analysis of traffic offloading in heterogeneous multi-layer wireless access networks featuring mmWave and/or terahertz APs. Notably, the fraction of LoS blockage and/or outage time characterize the amount of time resources of systems have larger coverage, and usually smaller capacity needs to be used.

  LoS blocking zone for D2D scenario.

Fig. 1 .

 1 Fig. 1. Considered scenarios.

Fig. 2 .

 2 Fig. 2. Top view of the LoS blocking zone.

Fig. 3 .

 3 Fig. 3. Fraction of LoS blockage time in AP to UE scenario.

Fig. 4 .Fig. 5 .

 45 Fig. 4. The fraction of nLoS for D2D scenario.


Loreto Pescosolido
email: loreto.pescosolido@iit.cnr.it

Marco Conti
email: marco.conti@iit.cnr.it

Andrea Passarella
email: andrea.passarella@iit.cnr.it

D2D Data Offloading in Vehicular Networks with Delivery Time Selection

Keywords: D2D Data offloading, power control, delay-tolerant applications, radio resource management

Within the framework of a Device-to-Device (D2D) data offloading system for cellular networks, we propose a Content Delivery Management System (CDMS) in which the instant for transmitting a content to a requesting node, through a D2D communication, is selected to minimize the energy consumption required for transmission. The proposed system is particularly fit to highly dynamic scenarios, such as vehicular networks, where the network topology changes at a rate which is comparable with the order of magnitude of the delay tolerance. Through extensive system level simulations, we compare the energy consumed by the devices to perform D2D data offloading using the proposed scheme with the energy consumed when using a benchmark scheme (proposed in previous works) without optimal transmission instant selection. The results show that, in specific scenarios, compared to the benchmark system in which the transmission instant is not optimized, the proposed system allows a reduction of the energy consumed for D2D communications above 90%.

Introduction

Device-to-Device (D2D) data offloading in cellular networks [START_REF] Rebecchi | Data Offloading Techniques in Cellular Networks: A Survey[END_REF] is a powerful means to decrease congestion at the base stations, reduce the energy consumption of the overall system, and increase spectral efficiency. The idea is that, whenever a content is requested by a node, if the content is available at any of its neighbors, it must be obtained from it, rather than from the network infrastructure. We indicate the nodes that can potentially hand the desired content to a requesting node as potential content providers. The set of potential content providers, for a given content request, depends on scenario parameters, like the node density and the content popularity, and on the specific protocol design. For delay-tolerant applications, an interesting protocol design option is that, in case a node issuing a content request has no potential content provider in its neighborhood at the time of request, it waits for a predefined interval, called content timeout, within which it is still possible to obtain the content from a new neighbor, encountered in the meantime [START_REF] Whitbeck | Push-andtrack: Saving infrastructure bandwidth through opportunistic forwarding[END_REF][START_REF] Bruno | Offloading through opportunistic networks with dynamic content requests[END_REF]. Only at the expiration of the content timeout, if the content has not yet been obtained, it is transmitted by the infrastructure nodes through an Infrastructure-to-Device (I2D) transmission. This approach is particularly effective in highly dynamic scenarios, such as vehicular networks, where the network topology changes at a fast rate. The use of a content timeout allows to increase the population of potential content providers beyond the set of the requesting node's neighbors at the time of request, extending such population to the nodes that will become its neighbors in the future. In this way, the system obtains an increase of the offloading efficiency, defined as the percentage of contents delivered by using D2D communications between peer nodes (vehicles), rather than using I2D transmissions from the infrastructure nodes, bringing along the aforementioned system-level benefits.

In our prior works [START_REF] Pescosolido | Performance evaluation of an energy efficient traffic offloading protocol for vehicular networks[END_REF], [START_REF]Performance analysis of a device-to-device offloading scheme for vehicular networks[END_REF], we have shown that the considered type of D2D data offloading protocols for delay-tolerant applications, are very effective in reducing the overall energy consumption at system level. More in general, this is true for most D2D data offloading protocols, especially when power control is in use. However, there is still significant room for improving the performance of D2D transmissions, by taking full advantage of the delay tolerance of requests.

Consider two nodes, and let us define them as neighbors if and only if their distance is less than or equal to a (nominal) maximum transmission range d max .

In previous works that follow the above described approach, in the case at the time of a content request there are no potential content providers within a range d max from the requesting node (i.e., no neighbor has the requested content in its cache), as soon as the requesting node encounters a potential content provider, the content is transmitted. In this case, it is clear that the transmission takes place at the maximum transmission range of the devices. Therefore, in a system with distance-based power control, all the requests that are not fulfilled at the time of request, inherently require the use of the maximum D2D transmit power. Furthermore, in the opposite case, in which at the time of request there is already a potential content provider, say at distance d < d max , the content delivery requires a transmit power that is higher than what would be required if the delivery was postponed to a later instant, at which the involved (or any other) content provider would be closer than d to the requesting node.

Motivated by this observation, in this work we propose the following approach. When a new request arrives, a controller, running, e.g., at the eNodeB (eNB), exploits knowledge of nodes positions and predicted movements in the near future (in the following content timeout window), to estimate which potential content providers will be in radio range of the requesting node within the content timeout. The content transmission is scheduled with the potential content provider that is predicted to be at the minimum distance from the requesting node, at the point in time when this will happen. In this way, provided that a distance-dependent transmit power control is in use, the smallest possible transmit power will be required. We will show that using this approach the energy consumption of the considered protocol for delay-tolerant application can be dramatically reduced.

The paper is organized as follows. We position our work with respect to the recent research trends in this area in Section 2. In Section 3 we describe our system set-up and a possible MAC (adapted from an existing solution) for an in-band implementation of the proposed D2D Data offloading scheme. In Sec-tion 4 we present the proposed Content Delivery Management System (CDMS). In Section 5 we evaluate the performance of the proposed system through the analysis of system-level simulations results, in terms of the average energy consumption per content delivery required to satisfy a given system-wise traffic demand. Finally, Section 6 concludes the paper summarizing our contribution.

Related work

The use of D2D communications to offload traffic from infrastructure nodes has been investigated for years by the researchers of different communities. Works like [START_REF] Ji | Wireless device-to-device caching networks: Basic principles and system performance[END_REF][START_REF]Fundamental Limits of Caching in Wireless D2D Networks[END_REF] aim at investigating scaling laws and network throughput from a fundamental limits perspective. Works like [START_REF] Lin | Spectrum Sharing for Device-to-Device Communication in Cellular Networks[END_REF][START_REF] Yang | FRESH: Push the Limit of D2D Communication Underlaying Cellular Networks[END_REF] (amongst many others), aim at devising radio resource allocation strategies, and/or other physical layer parameters, like coding rates and transmit power levels, assuming that D2D and/or I2D links to be accomodated are given as an input to the problem. More specific protocol-oriented works have been appearing in the last years as well. The interested reader may want to check, e.g., [START_REF] Rebecchi | Data Offloading Techniques in Cellular Networks: A Survey[END_REF] for an extensive survey. In these works, the objective is to determine and schedule I2D and D2D offloading communications as a function of the request patterns (as opposed to the above mentioned works, in which the link to schedule are an input to the problem). In [START_REF] Whitbeck | Push-andtrack: Saving infrastructure bandwidth through opportunistic forwarding[END_REF], the peculiarity of D2D data offloading for delay-tolerant applications was first addressed. In [START_REF] Bruno | Offloading through opportunistic networks with dynamic content requests[END_REF], a CDMS for contents originated from delay-tolerant applications, suited to a vehicular network scenario, was proposed. In [START_REF] Rebecchi | Circumventing plateaux in cellular data offloading using adaptive content reinjection[END_REF], in a scenario in which content delivery mostly relies on D2D-offloading, a strategy for I2D re-injection of contents in the network is proposed to mitigate the effect of temporal content starving in a certain areas. In [START_REF] Rebecchi | A joint multicast/D2D learning-based approach to LTE traffic offloading[END_REF], in the framework of a content dissemination problem (i.e., when contents need to reach all the nodes, without having been explicitly requested), the authors propose a mixed I2D-multicast and D2D-relaying reinforcement-learning-based strategy, which determines which users should receive the contents through a direct I2D transmission or through D2D relaying from a neighboring device. The above mentioned works, although providing interesting insights from the perspective of offloading efficiency maximization, devote less attention to performance metrics which are closer to physical quantities, like energy consumption and spectrum efficiency. Our work is motivated by the need to take into account such metrics in the system design, and optimize it to maximize them. With the focus on energy consumption minimization, we have been working on a CDMS inspired by [START_REF] Bruno | Offloading through opportunistic networks with dynamic content requests[END_REF], and evaluated analytically its performance in [START_REF]Performance analysis of a device-to-device offloading scheme for vehicular networks[END_REF]. The work in [START_REF]Performance analysis of a device-to-device offloading scheme for vehicular networks[END_REF] investigates the effect of content popularity and vehicles speed on the D2D transmit power by proposing and validating an analytical model for computing the offloading efficiency and the energy consumption, and then selecting the best value for the maximum D2D transmission range. The CDMS considered in [START_REF]Performance analysis of a device-to-device offloading scheme for vehicular networks[END_REF] does not optimize the D2D transmission time, letting the nodes transmit a requested content as soon as they encounter a node requesting it. In this work, differently from the above mentioned ones, we leverage the degree of freedom entailed by delay tolerance by deferring the D2D transmission instant to the time it will require the lowest power, thus achieving impressive performance gains in terms of energy consumption. Finally, we deem it appropriate to take into account accurate channel models, since using relatively simplistic models may result in an inaccurate estimation of the performance gain of a particular design [START_REF] Pescosolido | Performance evaluation of an energy efficient traffic offloading protocol for vehicular networks[END_REF]. Furthermore, we consider it necessary, when dealing with the type of performance metrics discussed above, to integrate in the performance evaluation an actual radio resource management technique. Among the many available, we found it useful to implement the solution proposed in [START_REF] Yang | FRESH: Push the Limit of D2D Communication Underlaying Cellular Networks[END_REF].

3 System model Vehicles enter the street according to a given stationary temporal arrival process, with an average arrival rate of λ t vehicles per second (λ t /2 vehicles per second on each end). Each vehicle n traverses the ROI at an average speed v n , selected as a random variable with probability density function p V (v). Particularly, we select p V (v) as a uniform random variable in a limited speed range [v min , v max ]. Each vehicle has onboard a mobile device, which can be either a human hand-held device or part of the vehicle equipment. Along the street, a set of eNBs is regularly placed. At each instant, each device (vehicle) is under the coverage of an eNB. Each device issues content requests according to a given stationary content request process with an average content request rate of λ Z requests per second, by sending requests messages to the eNB it is associated to at the time of request. The specific content being requested is drawn according to a content popularity distribution p Z (z). Similarly to [START_REF] Whitbeck | Push-andtrack: Saving infrastructure bandwidth through opportunistic forwarding[END_REF][START_REF] Bruno | Offloading through opportunistic networks with dynamic content requests[END_REF], we assume that the content requests can be fulfilled with some delay tolerance, i.e., they must be served at most within a content timeout τ c . A request may be fulfilled either by a potential content provider, through a D2D communication, or by an eNB. In this work we assume that, within the content timeout, the first option (delivery through D2D) is always privileged, and I2D content deliveries are performed only at the end of the content timeout, if it has expired before any potential content provider has been found. The rationale of this is that, in this way, we maximize the advantage of D2D transmissions in offloading traffic from the cellular infrastructure, which is one of the primary goals of any offloading system. A final important notion to introduce is that of the sharing timeout, τ s . This is defined as the time each device keeps a received content in its cache, available for other nodes that it encounters, and after which, to avoid an indefinite increase of the cache occupation, it removes.

The above assumptions are quite general. It is clear that, for the purpose of performance evaluation, specific models need to be assumed for all the involved random processes. For the sake of readability, we leave the description of the specific assumptions used for our performance evaluation to Section 5.

MAC and physical layer implementation

The purpose of this work, besides the presentation of the proposed CDMS, is also the evaluation of its performance with realistic medium access control and radio resource management strategies, also including physical layer aspects such as multipath frequency selective fading of the radio channels. We focus on inband D2D offloading, in which D2D communications and I2D ones share the same spectrum. We have considered a LTE-like multi-carrier system in which the radio resources are organized as a time-frequency grid of Physical Resource Blocks (PRBs) of fixed bandwidth and duration. We have selected a very flexible Radio Resource Reuse (RRR) scheme, which allows concurrent D2D and I2D communications. Particularly, we have implemented, with some modifications, the resource-sharing oriented scheme recently proposed in [START_REF] Yang | FRESH: Push the Limit of D2D Communication Underlaying Cellular Networks[END_REF]. However, we adapted the algorithms in [START_REF] Yang | FRESH: Push the Limit of D2D Communication Underlaying Cellular Networks[END_REF] to use different transmit power levels across concurrent links, and included multiple eNBs and spatial frequency reuse for I2D communications (besides D2D ones) in the design. Additionally, it is worth mentioning that the solution proposed in [START_REF] Yang | FRESH: Push the Limit of D2D Communication Underlaying Cellular Networks[END_REF] is evaluated under a flat fading channel assumption, whereas our implementation includes frequency selective channels. Further details on the considered channel model are provided in Section 5.

Time is organized in control intervals. In each control interval, a set of ID2 and D2D links have to be scheduled for transmission. The set of I2D and D2D links to schedule in each control interval is determined by the CDMS according to the procedure described in Section 4. Radio Resource allocation is performed by a RRR agent residing at the eNBs. We assume that the position of each device is known to the RRR agent, and hence, it can compute the distance between any node pair.

First, the RRR agent, taking in input the distance d between transmitter and receiver of each link to be scheduled, computes the transmit power of each link. This is done by inverting an expression for the nominal per-subcarrier capacity C, of the kind C = log 2 (1 +P c g(d)/σ 2 c ), with respect to the per-subcarrier transmit power P c . In the above expression, σ 2 c is the thermal noise power on each subcarrier 1 and g(d) is a nominal (deterministic) path loss expression 2 , which is selected by the system according to the deployment scenario (urban, denseurban, rural, micro-cell, macro-cell, I2D, D2D, etc...). The so obtained value of 1 σ 2 c is computed as the thermal noise power spectral density N0 = -174 dBm/Hz, plus a 10 dB receiver noise figure, times the subcarrier bandwidth. 2 The function g(d) is one of the components of our channel model, the other component being random frequency selective fluctuations added on top of g(d), see Section 5. In this work, we assume that g(d) is computed according to Equations 5-4, 5-5, and 5-6 in [START_REF]ICT METIS Project Deliverable 1.4[END_REF]. Interestingly, the considered channel model distinguishes between I2D and D2D channels, using different path loss functions in the two cases. This is one of the main reasons to opt for this model.

P c is increased by a suitable link margin M , which is required to compensate the presence of random fluctuations and frequency selectivity, and of the interference that may come from concurrently transmitting links. Note that both these effects are taken into account in the implementation we used in our performance evaluation.

Second, the set of links is partitioned3 into RRR sets in order to satisfy a set of cross-interference mitigation constraints. The constraints are computed using an estimation of the interference across links obtained by computing the nominal channel gain g between any link transmitter and any link receiver among the set of links to be scheduled. A suitable amount of PRBs is assigned to each RRR set. This amount is a function of the number and size of the contents that have to be by each link in the RRR set. D2D links in the same RRR set can use the same radio resources, since their belonging to the same set stands for the fact that their cross-interference is sufficiently low not to compromise the communications. I2D links originating from the same eNB are assigned radio resources in an exclusive way, selected as a portion of the pool of PRBs assigned to the RRR set they have been included in. In its portion of PRBs, however, each I2D link is subject to the interference coming from the D2D links included in the same RRR set. Finally, I2D links originating from different eNBs, that are included in the same RRR set, can be assigned the same portion of PRBs within the pool of PRBs assigned to that RRR set. If the RRR set partitioning and consequent PRBs allocation to each RRR set, due to the cross-interference constraints and to the limited number of PRBs in a control interval, prevent to accomodate the transmission of all the data required by any of the links, the data to be transmitted are pruned until reaching a feasible amount. The pruned transmissions will be rescheduled in the next control interval. Pruning is performed giving a higher scheduling priority to content deliveries related to requests whose content timeout is closer to expire. Therefore, I2D communications have a higher priority then D2D ones, since they are by design related to content requests whose timeout has already expired. If, due to pruning, the content timeout of any content request expires, the corresponding delivery is redirected to be performed by an eNB.

A more detailed description of the considered RRR scheme and physical layer model is outside the scope of this work, and will be provided in a future work.

Content Delivery Management System with optimized delivery time

In this work, we assume that the proposed protocol is executed under the supervision of an entity that we call CDMS. This is a distributed software agent under the control of the network operator. Most of its functions, explained in the following of this section, are executed at the eNBs. Whenever a content request is generated by a user, it reaches the CDMS, which is responsible for handling it from the time it is issued by a device until its fulfillment, deciding how and when the content request will be satisfied, either through D2D or through I2D communications. The basic functions of such a CDMS have been described in detail in our previous work [START_REF]Performance analysis of a device-to-device offloading scheme for vehicular networks[END_REF] (see also [START_REF] Pescosolido | Performance analysis of a device-to-device offloading scheme in a vehicular network environment[END_REF]). The main contribution of this paper, thus, consists in a novel algorithm used by the CDMS to estimate the optimal transmission instant for D2D communications.

The CDMS acts on a distributed database containing the up-to-date list of each node's position and an estimation of their trajectories for the next τ c seconds. Each device may obtain a estimation of its speed and trajectory in the next seconds, either through the use of GPS or, if it is part of the vehicle electronic equipment, directly from the speedometer, and send it periodically to the eNBs. Alternatively, the devices can send the GPS information only to the eNB, leaving the burden of trajectory estimation to the CDMS. In general, different combinations are possible, whose details are outside the scope of this work. In this way, essentially, the CDMS has a picture of how the network topology will evolve in the next seconds 4 . Each device k has an internal content cache C k populated with previously downloaded contents. We assume that, at any time, the CDMS also has an index of the contents in each node's cache, and the instants at which each content will be removed from the node's cache due to the expiration of the associated sharing timeout. Each eNB keeps the above described information for all the nodes in its coverage and all the nodes in the adjacent eNBs cells. This is obtained by a periodic exchange of information among eNBs performed through high speed fiber connections, or dedicated radio channels, forming a mesh-type backhaul network. A high level abstraction of the CDMS architecture is depicted in Fig. 2.

On a coarse timescale, with respect to a given content request, the requesting node and the proposed CDMS act as follows. Upon receiving a request of content z from a node j, the eNB performs the following operations:

1. It compares the estimated trajectory of the requesting node j, for the next τ c seconds, with those of all the nodes that have content z in their caches. In practice, the set of potential content providers is limited by a maximum speed parameter v max , the content timeout τ c , and the maximum D2D transmission range d max . These parameters are system parameters known to the CDMS and which determine the set of nodes that the requesting node j is supposed to encounter before the content timeout for the request of content z expires. 2. It truncates the estimated trajectory of each potential content provider with the instant its sharing timeout for content z will expire, if such instant comes before the expiration of the considered request content timeout, obtaining what we call "filtered" trajectories. 3. On the basis of the filtered trajectories of all the potential content providers, it computes which potential content provider, say device k, will reach the shortest distance from device j, the value of such distance, say d (z) (j,k) , and the instant t (j,k) . 5. During the content timeout, the CDMS, with respect to the considered content request, keeps track of any device other than j and k which (i) is not included in the initial set of potential content providers and (ii) is supposed to encounter node j within the content timeout. If any such node receives the same content z during the content timeout, the closest distance it will reach from node j is computed, and if it is found to be shorter than d

(j,k) , the content delivery is rescheduled to be performed by the newly found potential provider, say k , at the time it will supposedly be at the newly found shortest distance.

The requesting node, upon issuing a request, just waits for the content to be delivered to it. At the end of the content timeout, if it has not yet received the content, it will anyway receive it from the network infrastructure through an I2D transmission.

On a finer time scale, the operations described above are executed, in practice, in discrete-time, according to control intervals of duration typically much lower than the content timeout. For instance, the content timeout can be in the order of one minute, and the control interval duration is in the order of 1 second. The scheduled content delivery instants t (z) (j,k) are hence computed in terms of number of control intervals, and mapped to the future control intervals, contributing, at the prescribed time, to the input to the RRR and allocation scheme described in Section 3.2.

Performance evaluation

To evaluate the performance of our system, we used a custom simulator written in Matlab 5 . Our simulator implements a state of the art frequency selective channel model selected from [START_REF]ICT METIS Project Deliverable 1.4[END_REF][START_REF] Gpp | Study on 3D channel model for LTE (Release 12)," 3rd Generation Partnership Project[END_REF], which includes random Lognormal shadowing and Rician small scale multipath fading 6 .

We considered a two-lane street chunk of length 1.8 Km and width 20 m. The two lanes correspond to opposite marching directions. Four eNBs are placed at the horizontal coordinates of 0, 600, 1200, and 1800 m, respectively, at the center of the street (see Fig. 1), with height 10 m. The distance between the center of the two lanes is 10 meters. This is also the closest distance a vehicle can get to any vehicle marching in the opposite direction. We modeled the vehicles arrival as a temporal Poisson Point Process (PPP). In all the simulations whose results are presented in the following, the vehicle arrival rate was kept fixed at λ t = 1/3 vehicles per second. Similarly, we used a PPP for modeling the request arrival process of each node, and kept the content request rate per device fixed at λ Z = 1/6 requests per second (10 content requests per minute). The content requests processes of different devices were set to be statistically independent. The selected content popularity distribution was a Zipf distribution with parameter α = 1.1, i.e., p Z (z) ∼ 1 ζ(α) z -α , truncated to a library size of 10 4 contents. The sharing timeout was also fixed and equal to τ s = 600 seconds. The content size was fixed and equal to a payload of 500 KBytes, which we assumed to be encoded in a packet of 625 KBytes using a FEC coding rate equal to 0.8. The MAC parameters we used (see Subsection 3.2) are as follows: each control interval lasts one second, and is divided in time slots of duration 1 ms. Each PRB lasts for 1 time slot and has width 200 KHz. In each PRB bandwidth, there are 12 subcarriers, the overall system bandwidth is 10 MHz, and in each control interval, a maximum of 50000 PRBs could be scheduled to concurrent I2D and D2D transmissions (possibly spatially reusing the same PRBs across non-interfering links).

The following set of results shows the performance obtained by letting a system parameter vary while keeping the rest of the parameters fixed. We focus on three parameters: the speed range [v min , v max ] in which each vehicle's speed falls, the content timeout τ c , and the maximum D2D transmission distance. For each value of the varying system parameter, we run 10 independent i.i.d simulations, each lasting 1 hour, reinitializing the random number generator seed with the same state at the beginning of each batch of 10 simulations. Each simulation is initialized with a random number of vehicles, positions, speeds, and cache content of each node according to the results in our previous work 6 We implemented the Geometry-based Stochastic Channel Model (GSCM) described in [START_REF]ICT METIS Project Deliverable 1.4[END_REF][START_REF] Gpp | Study on 3D channel model for LTE (Release 12)," 3rd Generation Partnership Project[END_REF], up to the detail of generating the spatially correlated large scale parameters (LSPs): delay spread, shadow fading standard deviation, and Rician K-factor mean and variance, according to the procedure described in [START_REF]ICT METIS Project Deliverable 1.4[END_REF]. These parameters are then used to generate the random component of the set of spatially correlated frequency selective channels between any two points in a square grid with spatial step-size of 5m, representing the region of interest. The frequency response experienced by each transmission is obtained by adding the so generated random component on top of the deterministic path loss component g(d) described in Section 3.2, taking the random component between the grid points closest to the transmitter and receiver, respectively. [5], in which we computed the steady state average number of vehicles and cache content distribution. In each simulation, we used a different independent realization of the whole set of random component of the channels between any two points in the grid, and between any eNB and any point in the grid. The next figures show the average value of the offloading efficiency and of the energy, E D2D , consumed by D2D transmissions, measured in dB Re 1mJ 7 . Each value is displayed along with the related 95% confidence interval. Dark bars refer to a benchmark scheme, in which offloading is performed as soon as there is a potential content provider within range. Light bars refer to the proposed scheme. Fig. 3 shows the system performance with different selections of the speed range (measured in m/s). The increase in offloading efficiency with increasing vehicles speed, although a higher speed entails a lower vehicles' density (if the vehicle arrival rate is the same), is due to the fact, with higher speeds, the rate at which vehicles encounter each other increases, and hence the number of potential content providers met during the content timeout increases. From the energy consumption point of view, it can be seen that the proposed system allows for a more than 10 dB reduction of the energy consumed by the devices, on average, to deliver contents to their neighbors. This reduction is considerable, since it represents a more than 90% energy saving, and is consistent across the different selected values of the speed range.

Fig. 4 shows the behavior of the two systems with different values of the maximum range d max within which potential content providers, for each content request, are searched by the CDMS. The offloading efficiency increases accordingly to the increase of d max , but the energy consumption increases as well. This happens because the additional D2D offloading opportunities obtained by widening the potential content providers search space, come at the price of a higher required transmit power (for those additional opportunities), since the related involved transmission range is inevitably higher. Keep in mind that, due to the finite content timeout, the requesting node cannot wait indefinitely for those additional, farthest, potential content providers, to come close to it. The relative gain of the proposed D2D offloading transmission instant selection scheme, how- ever, is consistently in the order of magnitude of 10 dB, with worst case 7 dB, which represents an 80% energy saving.

Finally, Fig. 5 displays the performance trend with respect to an increase of the content timeout. As expected, for both the benchmark and the proposed system, the offloading efficiency increases, since possibility of encountering potential content providers, within a larger time window, obviously increases. What is even more interesting, however, is the increase of the relative gain, in terms of energy consumption, of the proposed system with respect to the benchmark, with larger content timeouts. This happens because, with larger a time window, the probability that a potential content provider comes very close to the requesting device increases, thus entailing a lower transmit power during the content transmission. With a content timeout of 120 seconds, the energy saving for D2D offloading transmissions achieves 97%.

Conclusion

We have proposed a content delivery management system for D2D data offloading in cellular networks tailored to scenarios, such as vehicular networks, where the topology varies at a fast rate, and to delay-tolerant applications. We evaluated the system level performance using an accurate system level simulator which includes a radio resource reuse scheme for allocating resources over a time-frequency radio resource grid, and incorporates a quite detailed channel model including small scale frequency selective fading. The proposed system, in which the D2D transmission instant is selected to minimize the transmission range, allows energy savings of around 90% in most of the considered settings, peaking at 97% for a delay tolerance of 2 minutes. The proposed system exploits the availability of nodes mobility predictions at the CDMS. As a future research direction, we plan to investigate the effect of trajectory prediction mismatches.

3. 1 1 .Fig. 1 .

 111 Fig. 1. Sketch of the considered scenario.

Fig. 2 .

 2 Fig. 2. High level abstraction of the distributed CDMS.

4 .

 4 It schedules the transmission of content z from the potential provider k to the requesting node j at the time instant t (z)

Fig. 3 .

 3 Fig. 3. Offloading efficiency and energy consumption with varying speed range. Benchmark offloading scheme (dark bars) and proposed scheme (light bars).

7Fig. 4 .

 4 Fig. 4. Offloading efficiency and energy consumption with varying maximum D2D transmission distance dmax. Benchmark offloading scheme (dark bars) and proposed scheme (light bars).

0Fig. 5 .

 5 Fig. 5. Offloading efficiency and energy consumption with varying content timeout. Benchmark offloading scheme (dark bars) and proposed scheme (light bars).

The RRR set partitioning algorithm is similar to [9,Algorithm 1].

In this work, we assume a perfect prediction of the vehicles' trajectory for an amount of time equal to the content timeout, leaving the evaluation of the robustness of the system with respect to trajectory prediction errors to a future work.

The reason to use a custom simulator, as opposed to classic network simulators like ns-3 or OMNET++, is to obtain a fine grain control on the physical layer aspects, retaining an acceptable level of scalability, using a state of the art channel model.

Acknowledgement

This work was partially funded by the EC under the H2020 REPLICATE (691735), SoBigData (654024) and AUTOWARE (723909) projects.