J-O Galdin-Retailleau

D Klein

J-O Querlioz

Klein

Approximate programming of magnetic memory elements for energy saving

Approximate Programming of Magnetic Memory Elements

for Energy Saving N. Locatelli * , A.F. Vincent, S. Galdin-Retailleau, J-O. Klein and D. Querlioz

Institut d'Electronique Fondamentale, UMR CNRS 8622, University of Paris-Sud, 91405 Orsay, France * e-mail: nicolas.locatelli@u-psud.fr

The high density of on-chip nonvolatile memory provided by memristive elements is highly desirable for many applications. However, it raises concerns about finding the best programming strategies to limit the energy consumption of such systems. Here, we highlight the case of magnetic memory, where several unconventional programming strategies can reduce energy consumption, especially for applications in neuromorphic computing.

STT-MTJ programming

Magnetic Tunnel Junctions programmed through the Spin Transfer Torque effect (STT-MTJs), the basic cells of spin transfer torque magnetic RAM (STT-MRAM), feature fast programming, non-volatility and outstanding endurance. The behavior of such device is presented in Fig. 1 and is reminiscent of a binary bipolar memristor.

The specificity of such devices appears through the stochastic nature of their programming. Indeed, under a programming pulse of given voltage 𝑉 𝑝𝑟𝑜𝑔 and duration ∆𝑡, the STT-MTJ has a non-100% probability 𝑃(𝑉 𝑝𝑟𝑜𝑔 , ∆𝑡) to switch state (Fig. 2). This effect has been extensively studied and the switching statistics can be described through comprehensive analytical models [START_REF] Vincent | Analytical macrospin modeling of the stochastic switching time of spin-transfer torque devices[END_REF]. We consider a STT-MTJ corresponding to a 32nm technology. For any voltage amplitude, models allow us to derive the reduction of the programming bit error rate (ER)the probability of failed switchingas the pulse duration (Fig. 3) and the programming energy (Fig. 4) increase. It appears that the pulse duration gives us an efficient handle to tune the ER. Different programming regimes can then be identified depending on targeted application and error rate. Starting from a programming regime for high-significance data, ensuring ER=10 -10 , we evaluate the energy reduction that can be obtained by accepting an increase of the error rate (Fig. 5).

Disciplined approximate storage

Given a programming voltage 𝑉 𝑝𝑟𝑜𝑔 =0.65V, allowing an increase of the ER to 10 -2 grants a reduction of 62% of the energy expense. Considering the use of a STT-MRAM to store synaptic weights as floating point number in neural networks applications, strategies of disciplined approximate programming can be enforced to reduce the global energy expense [START_REF] Sampson | Approximate storage in solid-state memories[END_REF]: identifying lower-significance part of the data i.e., least significant bits of the weight (LSB), and releasing them from low error-rate constraints. On Fig. 6, we expose the predicted energy reduction factor as a function of the number of bits labelled as lowly significant, and the error rate with which they are programmed. For instance, the reasonable choice of 26 LSB (half of the float significand) with ER=10 -2 grants a 22% energy reduction when compared to a fully highsignificance memory use.

MTJs as stochastic synapses

Further increase of the ER above 10 -2 corresponds to entering a regime of stochastic programming of the devices. This very low energy regime can be implemented to achieve memristive synapses with stochastic plasticity in hardware neural network [START_REF] Vincent | Spin-transfer torque magnetic memory as a stochastic memristive synapse for neuromorphic systems[END_REF][START_REF] Querlioz | Bioinspired programming of memory devices for implementing an inference engine[END_REF]. In such applications, the devices state -thus the synapses conductance-evolves during the learning process according to a stochastic rule, with very high ER, possibly over 90%. In that case, the drastic reduction of the energy expense (86%) comes from exploiting the intrinsic device randomness as an essential feature of the system. In recent work [START_REF] Vincent | Spin-transfer torque magnetic memory as a stochastic memristive synapse for neuromorphic systems[END_REF], we highlighted that a STT-MTJ based hardware neural network has potential to achieve unsupervised learning by testing it against a task of vehicle counting (Fig. 7).

Sensibility to programming variability

As can be seen on Fig. 4, the ER resilience to programming conditions variability (5% variability on the voltage are considered here) increases as the targeted error-rate increases. While releasing low error-rate constraints, systems then tends to become more robust to variability. Notably, neural networks based on stochastic STT-MTJs with ER=90% proved unchanged performances for devices variability up to 17% [START_REF] Vincent | Spin-transfer torque magnetic memory as a stochastic memristive synapse for neuromorphic systems[END_REF].

Conclusion

Deterministic programming strategies are associated to high energy cost and do not suit ideally bio-inspired applications. By contrast, strategies can be developed to consider higher ER programming for energy reduction.

Fig. 1 .

 1 Fig. 1. DC resistance versus voltage for a magnetic tunnel junction (MTJ), composed of a stack of two magnetic layers separated by a tunnel barrier. The resistance of the device relates to the relative orientation of their magnetizations. The magnetization of the free layer is switched through the spin transfer torque (STT) effect.

Fig. 3 .

 3 Fig. 3. Error rate versus programming pulse duration ∆𝒕 for different pulse amplitudes 𝑽 𝒑𝒓𝒐𝒈 .

Fig. 5 .

 5 Fig. 5. Programming energy reduction factor when considering an increase of the error rate from ER=10 -10 , calculated for programming voltage 𝑽 𝒑𝒓𝒐𝒈 =0.65V.

Fig. 2 .

 2 Fig. 2. Illustration of MTJ programming. After applying a pulse of amplitude 𝑽 𝒑𝒓𝒐𝒈 and duration ∆𝒕, the MTJ has a non-100% probability 𝑷 to have successfully switched state.

Fig. 4 .

 4 Fig. 4. Error rate versus average programming energy calculated for programming voltage 𝑽 𝒑𝒓𝒐𝒈 =0.65V and considering 5% variability on programming voltage. Inset shows the energy increase due to variability.

Fig. 6 .

 6 Fig. 6. Energy reduction of the total programming energy for a double precision float considering an increase of the ER for low-significance bits (LSB). Different choices for the number of LSB and high-significance bits (HSB) are presented.

Fig. 7 .

 7 Fig. 7. Hardware neural network architecture with STT-MTJs as stochastic synapses. The system is evaluated against a car detection task, proving 95% detection rate and high resilience to synaptic variability (bottom left inset).

Acknowledgements

This work is supported by Labex NanoSaclay (ANR-10-LABX-0035), ANR COGNISPIN (ANR-13-JS03-0004-01), and FP7 ICT BAMBI (FP7-ICT-2013-C). References


Silvia Mignardi
email: silvia.mignardi@unibo.it

Roberto Verdone Dei

Joint Path and Radio Resource Management for UAVs Supporting Mobile Radio Networks

Keywords: Radio Resource Management, UAVs, Mobile Networks

In this paper we investigate the potential advantages of using a roaming Unmanned Aerial Vehicle (UAV) as base station of a mobile radio network deployed in a city. The design of the UAV dynamic trajectory and Radio Resource Management (RRM) strategies are combined, with the goal to improve the sum throughput of the network. The comparison between joint and separate aerial-terrestrial RRM is discussed. With respect to previous papers, we identified a cost function, used to define the UAV path, improving significantly the performance.

I. INTRODUCTION

The long term evolution of 5G (the 5th Generation of mobile radio communications) is going to be shaped in the next few years. Future networks have to face new challenges: service requests from users and platforms of many different kinds, with very diverse requirements, and the domination of massive machine type communication. In urban environments, data traffic demand will increase significantly, mostly due to video uploads and downloads. As a result, the network will need to be able to adapt efficiently to traffic demand evolutions in space and time.

This flexibility can be achieved by moving infrastructure nodes as a reaction to the spatial and temporal variations of traffic. We assume in this work that the terrestrial network is supported by autonomous Unmanned Aerial Vehicles (UAVs, also denoted as drones); they carry radio equipment connected to the rest of the network through high capacity links [START_REF] Mignardi | On the performance improvement of a cellular network supported by an unmanned aerial base station[END_REF]. They might be fully functional Base Stations (BSs), or simple relays extending the coverage of Terrestrial Base Stations (TBSs). See Fig. 1 for a pictorial representation of an UAV-aided mobile radio network comprising such aerial component. The UAVs will support the terrestrial mobile radio network through their ability to establish links with ground User Equipments (UEs) characterized by large Signal-to-Noise-Ratio (SNR), and the possibility to provide coverage and capacity where TBSs are ineffective.

Some researchers envision the possibility to use mesh topologies and multi-hop links, applying ad-hoc routing protocols to the UAV network. We believe that the ease of establishing Line-of-Sight (LoS) links towards the TBSs, and the need for ultra-reliable and low-latency connection to the core network, suggest to implement simpler approaches without inter-UAV links.

Most of papers dedicated to UAV-aided mobile radio networks analyze the optimal UAV placement, in static scenarios without mobility. Moreover, the issue of Radio Resource Management (RRM) is often not considered. Our work focuses on the opposite on the joint design of the UAV path and RRM. This requires the consideration of all aspects of network dynamic behavior: traffic evolution, radio resource assignment, the mobility of UEs and UAVs. In particular we focus on the provision of high throughput services to ground UEs having non stringent delay constraints. Video streaming is an example of application falling in this category. We show results obtained through dynamic simulations.

We define the dynamic trajectory of the UAVs through a heuristic approach which in previous papers of the same Authors has proven to provide evident improvements in terms of network throughput [START_REF] Mignardi | On the performance improvement of a cellular network supported by an unmanned aerial base station[END_REF]; in this work we modify the approach to account for joint RRM, and discuss possible ways to achieve further improvements in performance, left for further work.

The rest of the paper is organized as follows. Sect. II discusses prior literature works. Sect. III describes the network model and the scenario considered. In Sect. IV we propose our approach to the joint definition of UAV path and RRM strategies. Numerical results and conclusions are presented in Sect. V and VI, respectively.

II. STATE OF THE ART

The Air To Ground (ATG) channel model has been analyzed in papers like [START_REF] Al-Hourani | Modeling air-toground path loss for low altitude platforms in urban environments[END_REF].

As for RRM, [START_REF] Soorki | Resource allocation for machine-to-machine communications with unmanned aerial vehicles[END_REF] investigates optimal resource allocation mechanisms for IoT applications. In [START_REF] Koulali | A green strategic activity scheduling for UAV networks: A sub-modular game perspective[END_REF], scheduling for UAVaided networks is addressed, with the aim of achieving the maximum system performance in terms of encounter rate and energy efficiency. [START_REF] Bor-Yaliniz | The new frontier in RAN heterogeneity: Multi-tier drone-cells[END_REF] introduces a discussion on the integration of UAVs in the next generation of networks.

Clusterization algorithms for UAV scenarios are introduced in [START_REF] Mozaffari | Mobile internet of things: Can UAVs provide an energy-efficient mobile architecture?[END_REF]: the model considers one UAV per cluster. In particular, Authors study the optimal trajectory and deployment in IoT uplink communications to minimize the power transmitted by machine nodes and the energy consumed at UAV side. Moreover, the Authors in [START_REF] Mozaffari | Mobile unmanned aerial vehicles (UAVs) for energy-efficient internet of things communications[END_REF] obtain dynamic trajectories in 3D space to connect IoT devices in the scenario at their activation time. They jointly optimize the transmission power of machine nodes, the overall energy spent in movement and the choice of the next stop for each UAV. Other early results regarding UAVs in cellular networks can be found in [START_REF] Mozaffari | Drone small cells in the clouds: Design, deployment and performance analysis[END_REF]. Authors considered the maximization of downlink coverage in drone small cells by computing the optimal height and minimizing the transmit power. The impact of interference on deployment of multiple UAVs was discussed together with the wanted distance between them, to improve coverage performance. In [START_REF] Sharma | UAV-assisted heterogeneous networks for capacity enhancement[END_REF], UAVs are used to carry relays; the model uses density and cost functions to calculate areas with higher demands and multiple UAVs are deployed depending on these functions. In [START_REF] Chen | Learning radio maps for UAVaided wireless networks: A segmented regression approach[END_REF], [START_REF] Chen | Optimal positioning of flying relays for wireless networks: A LOS map approach[END_REF] new considerations are introduced about the usage of Radio Maps to drive UAVs, in order to exploit the effective environment dependent Path Loss (PL) to drive system performance. One of the early works about the integration of terrestrial infrastructure and aerial platforms is [START_REF] Li | Uav-assisted dynamic coverage in a heterogeneous cellular system[END_REF]. Authors analyze aspects such as radio access, backhaul links and coverage introduced by multiple dronecells. However, they mainly focus on uplink machine type communication and do not consider a joint system resource management that includes trajectory design. [START_REF] Deruyck | Performance evaluation of the dynamic trajectory design for an unmanned aerial base station in a single frequency network[END_REF] introduces a single frequency scenario where TBSs and one UAV operate together to serve underlying users, but the RRM techniques implemented in the terrestrial network work independently with respect to the aerial platform. Moreover, [START_REF] Baek | User scheduling for non-orthogonal transmission in uav-assisted relay network[END_REF] studies user scheduling in the terrestrial network for non-orthogonal transmission in UAV relay networks. Potential interference is analyzed for both backhaul and UAV-UE link with the terrestrial network, and an interference avoidance solution is proposed.

Apart from very few exceptions, all these papers have been published in the last two years; the research field is very recent, and the topic is still addressed under simplistic assumptions. Moreover, there is no paper in the scientific literature addressing relevant issues like joint aerial-terrestrial RRM and combination of RRM with the dynamic path design for UAVs. In contrast, in this paper we introduce the impacts that dynamically defined trajectories and joint RRM between the terrestrial and aerial components of the network, bring to system performance. From this viewpoint, this work is very novel.

III. NETWORK MODEL

A. Network Architecture 5G will rely on networking techniques like SDN (Software Defined Networking) and NFV (Network Functions Virtualization). An NFV Orchestrator will manage the overall network; SDN controllers will be responsible for resources at more local level. We assume (see Fig. 2) that the Mobile Architecture Network Orchestrator (MANO) will manage a UAV Network Controller (UANC) that will be responsible for i) the assignment of radio resources available on the UAVs, ii) defining their trajectories and missions. The UANC through the MANO will be aware of the ground user traffic, and how the TBSs are serving UEs. In particular, an assumption usually made in scientific literature is that the UANC has knowledge of the position of the ground users to be served by UAVs; moreover, we assume that the UANC is aware of the key performance indicators and the radio resources used in TBS-UE links.

B. Traffic Model and Scenario

Services with stringent delay requirements cannot benefit from the aerial component of the network owing to the limited speed of UAVs. For this reason we focus on video streaming; the application requirements include a maximum waiting time (in the order of few seconds) before the streaming starts, and a minimum level of throughput. To evaluate the benefits introduced by the aerial component of the network, we will therefore measure the sum throughput, S, better defined later. We will focus on downlink streaming.

Most papers on UAV-aided mobile radio networks analyze urban environments, because spatial/time traffic variations can be very significant. Such scenario may include macrocells, and small cells. Some macrocell BSs, located on rooftops or towers, can act as UAV Homes; UAVs are normally parked in any Home (where batteries can be charged), and leave it only when required by the UANC, flying along trajectories optimized according to traffic needs. As a reference scenario, we consider an L by L urban area, with four TBSs per site and nine sites deployed on a regular square grid. We focus on a single UAV; its Home is located in the center of the scenario.

In this context, UAVs will serve the UEs (denoted as Unsatisfied Users, UUs) that cannot be served efficiently by the TBSs. UUs are of three types:

• the number of radio resources assigned by the serving TBS is not sufficient, • the TBS-UE link has low SNR,

• the TBS-UE link has low SIR (Signal-to-Interference-Ratio). In most cases, the UUs are confined at the cell edges where normally SIR and SNR is smaller; therefore, the spatial distribution of UUs is not uniform and UAV trajectories will privilege cell borders. Fig. 3 shows an instance of the traffic distribution of UUs, obtained through an LTE-like simulator implementing the network scenario described above [START_REF] Mignardi | On the performance improvement of a cellular network supported by an unmanned aerial base station[END_REF].

C. Air Interface and Radio Channel

For both the aerial and terrestrial air interfaces, we refer to the LTE standard over the 3.6 GHz frequency band, candidate for future 5G service provision in cities.

Most papers in the literature assume that UAVs are equipped with a directional antenna pointing towards the ground, with a fixed aperture angle α. Assuming an ideal antenna without side lobes and with constant gain, the area covered by the BS carried by the UAV (denoted hereafter as footprint) under uniform propagation conditions is a circle of radius r = h • tan α, where h is the drone height. Many works assume that the UAV antenna gain depends on α as G α = 29000/(α) 2 . We add to such gain 3 dB, to account for a minimum level of gain even when α is very large. The larger is the UAV height, the larger is the footprint and the number of UUs that can be served by the UAV. On the other hand, setting h, the larger is α, the larger is the footprint and the smaller is the antenna gain.

TBSs serve ground users through a radio channel affected by the typical impairments of urban environments, like fading and and Non-LoS. The probability of LoS, P , depends on the angle θ between the terrain and the line connecting the UAV to the UE; the larger is θ, the closer to one is P . In this paper, the power loss of aerial links is computed using the ATG model proposed in [START_REF] Al-Hourani | Modeling air-toground path loss for low altitude platforms in urban environments[END_REF].

In particular, the computation of SNR and SIR characterizing both TBS-UE and UAV-UU links follows Eqs. (1, 2):

SN R m,n = P r{m,n} 2 • N 0 • B subc (1)
SIR m,n = P r{m,n}

N T BS i=1 P r{i,n} (2)
where c m,n equals 1 whenever subcarrier set n is assigned to UE m otherwise it is set to 0. N is the total amount of subcarriers and B the total bandwidth. Then:

X m,n = min(SN R m,n , SIR m,n ) (3)
Finally, the computation of throughput gained from each properly served UE (which is the same for UAV-UU and TBS-UE links) is made through Eq. ( 4):

T m = B N N n=1 c m,n log 2 (1 + X m,n ) (4)
The parameter values adopted for simulation purposes are defined in Table I and II.

IV. UAV PATH AND RADIO RESOURCE ASSIGNMENT A. Trajectory Design

As shown earlier, few papers address the optimal design of UAV paths. The dynamic trajectory of UAVs should be defined according to a number of factors: the position of UUs, their traffic requirements, the residual energy available on the UAV, etc. In this paper we refer to the approach used in [START_REF] Mignardi | On the performance improvement of a cellular network supported by an unmanned aerial base station[END_REF], considering all factors above. However, we modified the way we account for them. Assume the UAV is located in Q (x, y, h) at a given instant t, when a new direction of flight has to be chosen. The MANO sends the updated information on UUs, their traffic demand, and radio resources assigned by TBSs, to the UANC. Based on this:

• the UANC groups the UUs in K clusters [START_REF] Mignardi | On the performance improvement of a cellular network supported by an unmanned aerial base station[END_REF]; • for each cluster (i = 1, . . ., K), the centroid is computed; • for each centroid (i = 1, . . ., K), a cost function, C i , is computed (see later); • the centroid having smallest cost function is selected (its distance from Q is denoted as d c ); • the UAV starts flying in the direction of the chosen centroid along a segment travelled during a time interval d c /v, where v is the UAV speed; • during its flight, the UAV serves all UUs covered by its footprint. The cost function in this paper is based on the same factors included in [START_REF] Mignardi | On the impact of radio channel over REM-aware UAV-aided mobile networks[END_REF]. However, one more factor has been added and its expression has been modified as follows.

C i = F d • F δ • F W • F S • F E • (1 + B) (5)
where:

• F d = di dmax ; d i is the distance between Q and the i-th centroid, d max is the maximum of all values of d i limited to a maximum range R;

• F δ = δi δmax ; δ i is the average distance between UUs in cluster i and its centroid, δ max is the maximum of all values of δ i over all K clusters;

• F W = Wi
Wmax ; W i is the number of RRUs already used by the TBSs inside the UAV footprint when the UAV is above the i-th centroid, and W max is the maximum among all values of W i ;

• F S = S (cl) min S (cl) i
considers the estimated sum throughput that will be obtained when the UAV will be above centroid i, S (cl) i (see later); S (cl) min is the minimum sum throughput achievable in the current set of K clusters;

• F E = Ei
Emax ; E i is the energy that the UAV will spend to reach the i-th centroid at constant speed v [START_REF] Zeng | Energy-efficient UAV communication with trajectory optimization[END_REF], computed as

E i = di v (c 1 • v 3 + c2 v )
, and E max is the maximum among all values of E i ;

• the term (1 + B) provides spatial fairness. The sum throughput S is defined as the sum over all interested UEs, S = j T m , of the throughput they perceive when served by a TBS or the UAV; for the m-th user, throughput, reported in Eq.( 4). Note that the factor F E takes into account that the UAV spends energy and has a limited lifetime. However, the simulated scenario takes into account a time of operation of 30 minutes; professional drones having this endurance already exist, and it is expected that in the coming years the available technology for UAVs will still improve.

In summary, apart from the term (1 + B), the cost function described above is the product of a number of factors taking values between 0 and 1. These factors were chosen to jointly reduce energy consumption and improve efficiently sum throughput. The UAV will take the direction identified by the lowest among all K costs; as long as the factors F i are closer to zero, the i-th centroid has higher chance to be chosen.

The approach defined above will determine a UAV path made of segments of different lengths. They are travelled by the UAV at constant speed v, and height from the ground h. Indeed, these two parameters should be subject to optimization (in combination with the choice of the antenna aperture angle α), as they will significantly affect network performance. Paper [START_REF] Mignardi | On the impact of radio channel over REM-aware UAV-aided mobile networks[END_REF] shows that optimal values of α are very large, and that the optimum of h lies between 100 and 140 m in a scenario like the one of this work.

B. Radio Resource Management

As far as the radio resource pool used by the aerial network component to serve the ground users is concerned, there are several options.

The simplest approach is to assume that the UAV serves the UUs using orthogonal frequency bands with respect to the TBSs. We are not interested here in this simple scenario with neither reuse nor interference. We consider the case where TBSs and UAVs use the same Radio Resource Unit (RRU) pool. At each scheduling instant, all TBSs decide through a Round Robin algorithm which camping users to serve, if they met the minimum requirement of SNR and SIR, having the whole RRU pool at disposal. Then, the UANC is made aware of each RRU set already used by any TBS to serve any UE. The UAV, while serving the UUs, should select the set of RRUs that will minimize mutual interference with the underlying terrestrial network.

As long as RRM is separate between the aerial and terrestrial components of the network, the solution proposed in [START_REF] Deruyck | Performance evaluation of the dynamic trajectory design for an unmanned aerial base station in a single frequency network[END_REF] represents the optimal choice; the UAV uses at any instant only those RRUs that are not assigned by the TBSs to the UUs located in its current footprint (which is known by the UANC). Under the assumption of an ideal antenna, the UAV transmission has no impact on ground receivers outside the footprint; inside it, no UE is using the RRUs used by the UAV. Therefore, interference is completely avoided; the UAV is re-using some of the RRUs assigned by the TBS within its cell. In such situation, the UAV will provide additional contribution to the network throughput, and no interference. On the other hand, the availability of RRUs strongly depends on the footprint area covered by the UAV: if the radius is small enough (e.g. 100 m), it is more likely that a large number of RRUs used by TBSs remains out of the drone coverage and then is still available for reuse at the UAV side. The opposite is true when the footprint is larger. For this reason, a trade-off is necessary [START_REF] Mignardi | On the impact of radio channel over REM-aware UAV-aided mobile networks[END_REF].

However, there is margin for further improvement. Let us assume that RRM is performed jointly by the terrestrial and aerial components. For any UE that can be served by both the TBSs and the UAV, the optimal choice is made. The advantage in this case is that there might be situations where a UE in the footprint of the drone will be served with much higher SNR by the UAV, even though it might have been served (with lower throughput) by the TBS. In this case, the network might decide to switch the UE's serving node from the TBS to the UAV, freeing the TBS of respective RRUs usage; however, this means that these RRUs can be re-used by the UAV for the new UU, avoiding interference. The contribution of the UAV to network throughput is expected to be larger with respect to the case of separate RRM.

A further consideration is related to latency. The separate RRM does not include any sort of feedback to the terrestrial network, therefore the TBS scheduler activity is not delayed or impacted by the UAV operation. The situation may be different when using joint RRM, but only for those UEs that change the serving node: in fact, in this case the network may issue an handover in favour of the UAV to serve the selected users.

C. Joint Trajectory Design and RRM

It is worth noting that the choice of the cost function reported above, includes the consideration of the expected number of radio resources that will be available in the cluster to be visited next, through the factor F W . According to the RRM technique used in this paper, the number of RRUs available in each cluster is variable depending on how many UEs are served by the TBSs in the UAV footprint. Therefore, the design of the UAV trajectory is performed accounting for the specific type of RRM strategy envisaged for the network; in other words, the UAV trajectory is RRM-dependent.

Nevertheless, one step further might be taken, by joining the decision on the next direction with the RRU assignment. This is left for future investigation.

V. NUMERICAL RESULTS

Numerical results are obtained through a dynamic LTE-like simulator described in [START_REF] Mignardi | On the performance improvement of a cellular network supported by an unmanned aerial base station[END_REF], with parameters set as in Tables I and II.

Figure 4 shows the throughput gain achieved as a function of UAV speed, where the throughput gain in percentage, G, is computed following Eq. ( 6):

G = S U AV S tot (6)
The terms S U AV and S tot represent the sum throughput achieved by the UAV, and by the terrestrial network only, respectively. In the analysis of values assumed by G, it has to be considered that they are obtained from a single UAV in a large network (see Table I).

In the figure, the lowest curve represents the outcome achieved through the first separate RRM solution mentioned in Sec. IV-B. On the opposite, the uppest curve is obtained by implementing a joint RRM decision between aerial and terrestrial network, as mentioned before. As expected, the second case provides better performance results in terms of throughput gain. In fact, in this solution RRUs are scheduled taking into account and comparing the different downlink channel conditions. Moreover, both curves show the same behavior when varying drone speed. As its value increases, performance results increase as well. This happens because the UAV is able to reach UUs in a faster way. However, when speed is larger, the UAV is not able to satisfy the user application requirements, as it flies away before the video is fully downloaded. For this reason, a maximum in the curves is present and a tradeoff value to set for speed must be applied.

The comparison between the two curves shows that the maximum does not change with the RRM strategy used. Whatever the value of UAV speed, joint RRM provides a significant improvement in gain with respect to separate RRM. Moreover, it is worth noting that in previous papers of the same Authors where exactly the same settings were used, the gain is always lower [START_REF] Mignardi | On the performance improvement of a cellular network supported by an unmanned aerial base station[END_REF]; the choice of the new cost function significantly increases the performance improvement achieved through one UAV in this scenario.

Figure 5 shows performance outcome while enlightening the influence of energy consumed. The total energy spent is computed as the previously mentioned E i . The two parameter values c 1 and c 2 featuring the drone's mechanical characteristics are set as c 1 = 9.26 • 10 -4 and c 2 = 2250, as in [START_REF] Zeng | Energy-efficient UAV communication with trajectory optimization[END_REF]. Authors state that the minimum energy spent is obtained for a drone speed of 30 m/s, and the same behaviour applies in this scenario. Therefore, with this speed not only the energy consumption is less, but also the network improves in performance in terms of throughput gain. Thus, higher speeds for the UAV are preferable with respect to low velocity of 10-15 m/s. In Fig. 6 the performance gain is shown with respect to another parameter, M , that is the average number of UUs present inside a cluster. This value is dependent on the total number of clusters, K, chosen as input for the clusterization algorithm. The curve related to a separate RRM is more dependent on this parameter, where for a larger number of users inside each cluster, the throughput gain increases (variations in G below 0.01% are considered as negligible due to statistical reasons). Therefore, for this case it is more advantageous to drive the UAVs through bigger clusters. However, for what concerns the aforementioned joint RRM, the performance gain obtained is almost equal for different values of M . Then, the clusterization algorithm appears to be more robust. In fact, the difference in performance gain while changing parameter M is small: the slight modifications are probably due to the realistic high randomness present in the scenario.

We conclude the analysis by understanding the different roles of every fraction in the new cost function. We analyzed the behavior of both, factors F i of the cost function and weighted C i averaged costs throughout a simulation.

The mass distribution obtained for each factor F i is shown in Fig. 7. Clearly, some factors have a distribution that is quite different than the others; as a result, the role of each factor is rather different. One possibility to overcome this problem would consist in using different exponents, φ i , applied to the different factors F i . This might provide some degrees of freedom to be properly used for optimizing system performance. This is left for further work.

However, we can infer from Fig. 7 that the most impacting factor between the five is F S , i.e. the ST factor. Its values are mostly close to 0, then it drives the product to smaller costs. On the contrary, F δ has values closer to 1, thus affecting less the overall cost. The other factors behave in a similar way, having then comparable weighs. Finally, F S is the factor mostly shaping the mass distribution of the cost function. Figure 8 shows the mass distribution of the obtained costs to compare for the best centroid selection, during a simulation run. Most values are very small, showing that the path is chosen by the algorithm based on minimal differences among cost values. This suggests that there is margin for further improvement.

VI. CONCLUSIONS

This paper has proposed a new expression for the cost function used to determine the UAV path, with respect to [START_REF] Mignardi | On the impact of radio channel over REM-aware UAV-aided mobile networks[END_REF]. Moreover, the role of joint aerial-terrestrial RRM has been emphasised. The two facts together bring to a significant performance improvement with respect to [START_REF] Mignardi | On the impact of radio channel over REM-aware UAV-aided mobile networks[END_REF].

The cost function introduced in this paper has been generated according to a heuristic approach. No one ensures that a better way to define its expression does not exist. Five factors driving the cost function have been identified based on the drone hardware and mechanics, as energy and distance, and the final scope on performance, as ST, user density and RRUs availability. Finally, the impact of each factor is analysed and performance results of the system are encouraging. The analysis of the distribution of values for the different factors combined in such expression, might bring to interesting considerations related to the possibility to give different weights to the factors, e.g. through some (different) exponents. This is left for further works.

Fig. 1 .

 1 Fig. 1. An UAV-Aided Mobile Radio Network.

  ISBN 978-3-903176-05-8 c 2018 IFIP

Fig. 2 .

 2 Fig. 2. Reference network architecture.

Fig. 3 .

 3 Fig. 3. Network scenario.

Fig. 4 .

 4 Fig. 4. Throughput gain with varying UAV speed.

Fig. 5 .

 5 Fig. 5. Throughput gain with varying energy consumed.

Fig. 6 .

 6 Fig. 6. Throughput gain while varying M .

Fig. 7 .

 7 Fig. 7. Probability mass distribution of the different factors in the cost function.

Fig. 8 .

 8 Fig. 8. Probability mass distribution of obtained C i .


Amitabha Bagchi

Federico Corò

Cristina M Pinotti

Vlady Ravelomanana

Border Effects on Connectivity for Randomly Oriented Directional Antenna Networks

We study the possibility of creating a fully connected ad-hoc network with bidirectional links between nodes equipped with randomly oriented directional antennas deployed in a circular planar region. The major contribution of our paper is to show that in the directional antenna setting there are always isolated nodes, no matter how high the transmission power of the antennas. We observe, however, that the isolated nodes are confined to a narrow annulus near the boundary of the region. We propose two solutions to achieve full connectivity in the directional setting: T-core that reorients isolated antennas towards the centre of the circular region, and Greedy that simply flips the antenna orientation. We show that the former heuristic, which needs information of the location of the centre of the region, achieves full connectivity with high probability and that, even the latter, which requires no extra information, is able to eliminate most of the isolation.

Introduction

Directionality of antennas focuses transmission power in a particular direction. It is well known that the millimeterwave cellular wireless networks need to be significantly redesigned to fully achieve the requirement of highly directional and adaptive transmissions [START_REF] Chebrolu | FRACTEL: a fresh perspective on (rural) mesh networks[END_REF], [START_REF] Carmi | Connectivity guarantees for wireless networks with directional antennas[END_REF], [START_REF] Rappaport | Millimeter wave mobile communications for 5g cellular: It will work![END_REF]. So, moving beyond point-to-point communication, it is crucial to understand how a connected network can be spontaneously formed by a set of nodes all equipped with directional antennas. In this paper, we specifically concern ourselves with connected networks that have bidirectional links since such networks can more easily perform complex coordination tasks (target tracking, event detection, routing, fault recovery etc) that can be very valuable in several settings. This paper presents an exploratory attempt to study the possibility of building ad-hoc connected mesh networks with bidirectional links using directional antennas.

A natural question that arises when we consider the possibility of forming such a network in directional antenna setting is: if each node is assumed to be randomly positioned in a two-dimensional field, and if it orients its antenna along a randomly chosen direction, what is the probability that the network is connected? A similar question has been posed for omnidirectional networks. The seminal work of Gupta and Kumar [START_REF] Gupta | Critical power for asymptotic connectivity in wireless networks[END_REF] employs theory from the area of continuum percolation and random graphs to provide a critical transmission range to achieve connectivity assurances as n grows to infinity for omnidirectional networks.

The main contribution of this paper is to show that in our directional antenna model, the Directional Antenna Random Geometric Graph (DARGG), it is not possible to achieve connectivity just by fixing a critical radius. We show that, in DARGG, nodes that are disconnected from the network exist with high probability if the radius of connectivity is taken to guarantee the same number of neighbours as the Gupta-Kumar radius guarantees in omnidirectional random graphs. We also give via simulations evidence that DARGG remains disconnected even at higher radii despite the fact that higher radii bring the guarantee of a higher number of neighbours.

However, we present an interesting finding regarding the disconnectedness of our DARGG: the disconnected nodes are confined to a narrow annulus at the border of the region of interest. This conclusion is important in two ways. Firstly, it tells us that the border effects that Gupta and Kumar handled cursorily because they did not affect their main result are crucial in the case of DARGG. Secondly, and more constructively, it gives us an idea on how to rectify the lack of connectedness in DARGG. We consider two simple decentralized methods for connecting the disconnected nodes to the network. The first, T-core, deterministically reorientats disconnected towards the center. This method eliminates all disconnections but requires the node to know where the center of the field is. The second method, Greedy, randomly flips the orientation of an isolated node by π radians. This method does not require any location information but is still able to reduce the extent of disconnection significantly without completely eliminating it.

Paper organisation. We first discuss related work, with a specific discussion on the pitfalls of the Gupta-Kumar approach in the directional case (Section 2). In Section 3, we describe our model in detail and compare both theoretically and experimentally the directional model DARGG with two benchmark models: Erdős-Bollobás Random Geometric Graph (EBRGG) and Vertex-Based Random Geometric Graph (VBRGG) proposed, respectively, by Gupta and Kumar in [START_REF] Gupta | Critical power for asymptotic connectivity in wireless networks[END_REF] and by Bagchi et al. in [START_REF] Bagchi | Optimal radius for connectivity in duty-cycled wireless sensor networks[END_REF]. We demonstrate that DARGG is unrelated to the two benchmark models and we show that, although DARGG achieves a high level of connectivity at the benchmark radius at which EBRGG and VBRGG achieve connectivity, it remains disconnected at this radius. This sets us up to present our heuristics for raising the connectivity level to 100%, which we do in Section 4 along with rigorous mathematical analysis that establishes how well they perform.

Related work

Since the last decade, researchers have begun to study millimeter-wave directional networks due to their ability to save power, minimize interference, to penetrate urban spaces, and to offer unprecedented spectrum and multi-Gigabit-per-second (Gbps) data rates to a mobile device [START_REF] Rappaport | Millimeter wave mobile communications for 5g cellular: It will work![END_REF], [START_REF] Maccartney | Rural macrocell path loss models for millimeter wave wireless communications[END_REF], [START_REF] Rappaport | Overview of millimeter wave communications for fifth-generation (5g) wireless networks with a focus on propagation models[END_REF]. Attention has also been devoted specifically to the connectivity problem in directional antennas [START_REF] Kranakis | Maintaining connectivity in sensor networks using directional antennae[END_REF], [START_REF] Li | Asymptotic connectivity in wireless ad hoc networks using directional antennas[END_REF], [START_REF] Okorafor | On the relevance of node isolation to the k-connectivity of wireless optical sensor networks[END_REF]. In the literature, two approaches are used to achieve connectivity in directional networks. The first approach involves computing antenna orientations to ensure connectivity. In the second approach the devices are allowed to randomly orient themselves and connectivity is ensured by tuning other antenna parameters (e.g. power) such that connectivity is ensured in this scenario.

Since our work is in the random orientation paradigm, and due to the constraints of space, we only survey those papers within this paradigm. We observe that this paradigm assumes that a generalisation of the "Gupta-Kumar approach" proposed in [START_REF] Gupta | Critical power for asymptotic connectivity in wireless networks[END_REF] will work to ensure connectivity in the directional model. In this paper, we will show that there are some serious pitfalls in working with this assumption.

The first of the two groups who followed a Gupta-Kumar approach, Li et al. [START_REF] Li | Asymptotic connectivity in wireless ad hoc networks using directional antennas[END_REF], faced the issue of dependency of connections, i.e., given a node u and two other nodes, v and w that were within transmission range, the probability that u is connected to both v and w is, in general, less than the product of the probabilities of the events "u is connected to v" and "u is connected to w." In other words these events are negatively correlated. To see this let us consider a beamwidth of 2θ = 2π/3 (although any value less than π will work for this example). Consider the following example: Place u at the origin of the real plane and place v at (-1,0) and w at (1,0), assume connection range to be 1.5. Because of the way v and w have been placed, and because the beamwidth is less than π, if u is connected to v the probability that it is also connected to w is 0. This dependency was not encountered by Gupta and Kumar since, due to the omni-directional nature of their connectivity function, once we know that v and w are within u's range, connectivity is given. Although Li et al. identified the problem of dependency, they viewed it as a limited problem and, in fact, appear to have spotted some kind of positive correlation pertaining to antenna side-lobes, and, relying on some mathematically non-rigorous findings in the area of statistical mechanics, they went ahead and assumed that Gupta-Kumar's results are valid. As our results show, this is not the case.

The second group of researchers [START_REF] Bagchi | Connectivity of a dense mesh of randomly oriented directional antennas under a realistic fading model[END_REF], which included two of the authors of this paper, applied a general theorem they had provided in an earlier work [START_REF] Bagchi | Optimal radius for connectivity in duty-cycled wireless sensor networks[END_REF] where, to handle the problem of connectivity in a duty-cycled network, they had defined a careful generalisation of Gupta-Kumar's model that took vertex-based dependencies into account. However, the generalisation, called the Vertex-Based Random Geometric Graph (VBRGG), crucially depended on the fact that the connectivity function was independent of the position of the nodes. In fact, in the example offered above, the probability of u being connected to both the nodes is 0. However if we shift v to some other position, say

(1/ √ 2, 1/ √ 2)
, then there is some non-zero probability of u being connected to both v and w. The problem is this: the extent of negative correlation between the connectivity functions can change with position, even when the two nodes are at the same distance from the common node.

In summary, both group of researchers were unable to spot subtleties within the directional setting that were absent in the omni-directional scenario considered by Gupta and Kumar.

The connectivity problem in DA networks

In this section, we first present the DARGG model to represent DA networks. We then show that it is incomparable to the two benchmark generalisations of the Gupta-Kumar model mentioned in Section 2. Then, we show the radius that ensures connectivity in the benchmark models is not able to ensure connectivity in DARGG. We also discover that the isolated nodes are localized to the boundary of the region. This will lead in the next section to simple and decentralized methods to connect the network.

The DARGG(n, r, θ) model

We consider Directional Antenna networks (briefly, DA) formed by n nodes located uniformly and independently at random in a disk D of unit area. The center O of D is called the origin. Each node is equipped with a directional antenna that chooses, independently of all the other nodes, its orientation ψ at random in [0, 2π]. All the antennas have the same beamwidth 2θ. The random choices of the location and orientation set up a randomly configured network of directional antennas.

Transmission region. To model the directionality of the antennas we consider an idealized gain function that concentrates the antenna gain uniformly in a sector. To formalise this, let us introduce notation: Given a point z ∈ R 2 , two angles -θ ∈ [0, π/2] and ψ ∈ [0, 2π] -and a real r > 0, the sector S r,θ (z, ψ) is a sector of radius r and width 2θ centred at z, with the property that the ray originating at z that bisects the sector forms an angle of ψ with the positive x-axis.

As discussed above, each of our n nodes chooses its location, u ∈ D and its orientation ψ u independently of all other random choices. Choosing a value r that is related to the transmission power available to the antenna, and determining θ based on the extent to which the antenna is able to focus its power footprint along the direction of its orientation, our modeling assumption is this: The antenna at point u is able to transmit to all the points in sector S r,θ (u, ψ u ). Point-to-point communication. Given the transmission pattern described above, point-to-point communication between two antennas u and v is said to be possible only if u ∈ S r,θ (v, ψ v ) and v ∈ S r,θ (u, ψ u ), i.e., if each of them lie in the other's transmission region (we abuse notation to use u to denote both the antenna and its location).

Fig. 1 illustrates the parameters involved in the definition of point-to-point communications in DA.

Definition 1. Two antennas u and v can directly communicate only if they satisfy the following conditions:

1) the distance d(u, v) ≤ r;

2) the angle β u formed by the orientation ψ u and the line that connects u and v is no larger than θ; 3) the angle β v formed by the orientation ψ v and the line that connects u and v is no larger than θ.

Condition 2 says that v is in the transmission area of u, whereas Condition 3 says that u is in the transmission area of v. So, any point-to-point undirected (u, v) communication occurs if the two directed communications u → v and v → u exist. More specifically, if only one of these two directed communications occurs, it is ignored in our model.

In conclusion, any DA network whose antennas follow the idealized sector model of radius r and width θ will be referred to as DARGG(n, r, θ) which is a random graph model whose underlying graph G = (V, E) is built by associating a vertex to each antenna in DA, and adding an undirected edge (u, v) ∈ E if u and v can establish a pointto-point communication.

Marginal probability of edge formation in DARGG(n, r, θ). Since the position and the orientation of the antennas are modelled by independent random variables, we compute the probability that a single edge belongs to E as a joint probability. Hence, P((u, v) ∈ E) = θ 2 π r 2 because v belongs to the circle of radius r centered at u with probability πr 2 given that D has unit area, u has probability θ π to be oriented towards u, and the same probability has v to be oriented towards v.

Comparing DARGG, EBRGG, and VBRGG

As discussed in Section 2 the question "What is the best (smallest) value of r that ensures (with high probability) that DARGG(n, r, θ) is connected?" is misleading.

Let us recall the definition of the two random geometric graph models that are generalisations of the Gupta-Kumar model, that are closely related to DARGG(n, r, θ), but are qualitatively different in terms of their properties. The first of these models was described by Gupta and Kumar themselves [START_REF] Gupta | Critical power for asymptotic connectivity in wireless networks[END_REF], and also studied by Bollobás et al. [START_REF] Bollobás | Random Graphs[END_REF]. In this model, we call it EBRGG(n, r, p), n nodes are placed randomly in D and an edge is placed between a pair of nodes (u, v) with distance d(u, v) ≤ r with probability p. All random choices of location of nodes and of placement of edges are taken to be independent in this model.

The second model was described by a team that included two of the authors of this paper [START_REF] Bagchi | Optimal radius for connectivity in duty-cycled wireless sensor networks[END_REF] to study the connectivity of duty-cycled networks. In this model, VBRGG(n, r, p), the nodes are placed randomly in D as before. As before, only those nodes u, v which have d(u, v) ≤ r can have an edge placed between them. However, to determine which of these eligible pairs actually have an edge placed between them, we work with a random variable ψ and equip each node u with a copy of the random variable ψ which we call ψ u . If ψ is defined on a domain X, we also have a function f : X × X → {0, 1} that determines whether u and v are connected. Further, we have that if ψ 1 and ψ 2 are two independent copies of ψ then P(f (ψ 1 , ψ 2 ) = 1) = p. Again we note that all random choices of the locations of the nodes and the copies of ψ are independent of each other. Besides an important implicit assumption in [START_REF] Bagchi | Optimal radius for connectivity in duty-cycled wireless sensor networks[END_REF] is that the function f is independent of the locations of the nodes and depends only on the choice of the copies of ψ.

Setting γ = θ 2 /π 2 , we now compare DARGG(n, r, θ) to EBRGG(n, r, γ) and VBRGG(n, r, γ) since the marginal probability of edge placement between any two nodes is the same in all three models. DARGG(n, r, θ) and EBRGG(n, r, γ) are unrelated. To demonstrate the difference between DARGG(n, r, θ) and EBRGG(n, r, γ), we return to an example presented in Section 2. Let us call this Example A: Place u at the origin of the real plane and place v at (-1,0) and w at (1,0), assume r = 1.5 (hence, r is greater than the radius of D) and θ = π/3. In DARGG(n, r, θ), the probability of both edges (u, v) and (u, w) existing simultaneously is 0 because v and w can never reside on the same sector of width 2π/3, whereas in EBRGG(n, r, γ) the probability is γ 2 > 0. From this example we see that there are cases where the edge set of EBRGG(n, r, γ) is a superset of the edge set of DARGG(n, r, θ). However, there are situations where the domination is in the opposite direction. Let us call this Example B: Consider the example above, except we move v to (1 -, 0) for a very small so that v and w are right next to each other and v lies on the line joining u to w. In this case, fixed the sector of u, independently from the value of θ, either both v and w reside in the sector of u or none. So if φ v and φ w are both oriented towards u, and both v and w reside in the sector of u, then the probability that the two edges (u, v) and (u, w) simultaneously exist is 1. Hence the probability that u is connected to both v and w in DARGG(n, r, θ) is θ 3 /π 3 , i.e. the product of the probabilities of the three events (a) S 1.5,θ (u, ψ u ) contains both v and w, (b) S 1.5,θ (v, ψ v ) contains u, and (c) S 1.5,θ (w, ψ w ) contains u. On the other hand, in EBRGG(n, r, γ) the probability of both these edges existing is γ 2 = θ 4 /π 4 < θ 3 /π 3 . So DARGG(n, r, θ) has a higher probability of having both these edges. Without formalizing this overly we note that these two examples can be used to argue that there is no stochastic domination between these two models in either direction.

DARGG(n, r, θ) and VBRGG(n, r, γ) are unrelated. The locations of the three nodes in Example A and Example B discussed above also serve to show that DARGG(n, r, θ) and VBRGG(n, r, γ) are unrelated. Let us consider the probability of placement of both edges (u, v) and (u, w) in VBRGG(n, r, γ). In Example A, the probability is again γ 2 > 0 as opposed to 0 in the case of DARGG(n, r, θ). Similarly, in Example B the probability of both edges existing is γ 2 for VBRGG(n, r, γ) which is less than θ 3 /π 3 which is the probability for DARGG(n, r, θ). Hence neither of these two models dominates the other.

A benchmark for the connectivity radius of DARGG(n, r, θ). At this point, the initial question about which is the radius that guarantees the connectivity in DARGG is still open. We recall that in [START_REF] Bagchi | Optimal radius for connectivity in duty-cycled wireless sensor networks[END_REF] it has been proved the critical transmission radius for ensuring connectivity w.h.p. in VBRGG(n, r, γ) as n → ∞ is

R(n, γ) = log n + c nπγ (1)
where c = lim n→∞ c(n) = ∞ as n → ∞. The same critical transmission radius has been conjectured in [START_REF] Gupta | Critical power for asymptotic connectivity in wireless networks[END_REF] for the EBRGG(n, r, γ). Since we have no better clues, we proceed our experimental research of the critical transmission in DARGG(n, r, θ) having in mind as a benchmark the radius R(n, γ) in Eq. 1.

An experimental study of connectivity

We now present, in brief, the results of an extensive simulation study. We show that DARGG does not achieve connectivity even at very high radii and that the disconnected nodes are to be found near the boundary. Further, we show that the nature of boundary effects across DARGG, EBRGG, and VBRGG is very different at similar radii. Finally, in preparation for our connectivity-fixing heuristics (Section 4) we show that the benchmark radius that achieves full connectivity for VBRGG and EBRGG achieves a high connectivity for DARGG and serves as a good platform from where we can apply our heuristics to achieve full connectivity.

Simulation setup. We generate n sensors placed uniformly at random in a unit disk, with n being chosen fairly large, 2 • 10 5 ≤ n ≤ 10 6 , since the study of the critical transmission radius is carried out in a dense network setting. For each point we then choose the orientation ψ at random in [0, 2π]. We set the parameter θ ∈ { π 6 , π 4 , π 3 , π 2 }. We vary the sector radius r from 0 to the largest possible radius R D = 1 √ π in D and beyond. As said, we consider of particular interest the radius in Eq. 1. In this paper, since γ = θ 2 π 2 , R(n, γ) = log n+log log n πn π θ will be denoted as R(n, θ) to stress the dependency with the beamwidth, or simply R when the values n and θ are clear from the context.

Having fixed a value of the beamwidth θ and of the transmission radius r, in DARGG, we add an edge (u, v) to E if u ∈ S r,θ (v, ψ v ) and v ∈ S r,θ (u, ψ u ). We build an instance of the EBRGG(n, r, γ) model with γ = θ 2 π 2 , as follows: For each pair of nodes at distance at most r, we generate a random number x uniformly distributed in [0, 1], and we add the edge (u, v) if x ≤ θ 2 π 2 . Moreover, we generate an instance of the VBRGG(n, r, γ) with γ = θ 2 π 2 by adding the edge (u, v) if and only if

ψ u ∈ I[π + ψ v -θ, π + ψ v + θ] 2π and ψ v ∈ I[ψ u -θ, ψ u + θ] 2π
, where I[a, b] 2π are the orientations that fall in the sector spanned while counterclockwise moving the ray a over b. Finally, we simulate the RGG model by setting θ = π in the DARGG model.

For each instance of the above random graphs, the experiment consists in computing the connected components, and tracing their number and their sizes. We also count the number of isolated nodes and trace their position in D. Each experiment is repeated at least three times and the average value is reported.

DARGG is always disconnected. At first, we study if an arbitrary large radius can be used to connect the network under the DARGG model. We start studying the number of isolated nodes when the sector radius varies between R D and 2R D , i.e., from half the maximum possible distance between two points all the way up to the maximum possible distance between any two points. When the sectors have radius 2R D , any two antennas, independently of their position in D, are possible neighbors. Note that R D is more than 110 times the critical radius of the RGG model when n = 2 • 10 5 , and more than 240 times when n = 10 6 .

Table 1 reports the results for n = 2 • 10 5 and n = 10 6 . There are always isolated nodes even when the radius is as long as the radius of the deployment area. As one can see, when the radius grows from R D to 2R D and θ < π 2 , the number of isolated nodes remains the same for all cases. For all values of θ, the number of isolated nodes marginally decreases while the radius increases from R to R D . We conclude that increasing the radius from the benchmark radius R to R D or beyond does not improve the network connectivity, if θ < π 2 . Finally, observe that the case θ = π 2 behaves more likely the omnidirectional case than θ < π 2 . Isolated nodes are close to the boundary. We observed experimentally and we report in Table 2 that as the radius r increases spatial pattern emerges in the isolated nodes of DARGG(n, r, θ): for small values of radius r, the isolated nodes are spread throughout D but when r increases, they progressively move towards the outer corona δD of width equal to half of the transmission radius. This leads us to believe that the restriction of isolated nodes to the outer corona is experimental evidence of the boundary effects. The boundary effects, that Gupta-Kumar in RGG and the authors of [START_REF] Bagchi | Optimal radius for connectivity in duty-cycled wireless sensor networks[END_REF] in VBRGG found easy to handle, lead to significant complications in the directional setting.

Comparing boundary effects across DARGG, VBRGG, and EBRGG. Figures 2 and3 plot the percentage of connectivity, that is, the size of the largest connected component versus the total number n of nodes, for different radii. EBRGG and VBRGG reach 100% percentage of connectivity, thus forming a unique connected component when r is equal to their critical radius, while DARGG does not. One must say that the size of the largest connected component in DARGG increases when θ increases. In particular, for θ = π 2 , as reported in Table 1, only few nodes are left out. The 100% of connectivity is reached by EBRGG and VBRGG for all values of θ we have tested.

We have now evidence via simulations that the border effect appears in DARGG but does not appear in the other two models at the values of n we have chosen. Thus, the border effect is a characteristic of DARGG not shared by at least the two other models that are closest to it without being explicitly directional.

High connectivity at the benchmark radius in DARGG. In the following, we show that in DARGG, although there are isolated nodes when r = R(n, θ), the benchmark radius ensures a very high connectivity. In our simulations, the largest connected component always involves above 99% of the nodes, while the second largest connected component consists of very few nodes or even a single node.

For each value of θ and n, we run the following set of experiments: we compute the percentage of connectivity from r = 0 up to the first radius that reaches 99% of connectivity using an incremental step of 0.0005. Moreover, we compute the percentage of connectivity with the benchmark radius r = R(n, θ). We report the results in Figures 4 and5, respectively, when n = 2 • 10 5 and n = 10 6 . All the curves present what is known in the random graphs literature as a "first-order phase transition phenomenon", that is, a small increment of the radius leads to a big jump in the connectivity percentage. The phenomenon is slightly more evident for n = 10 6 than for n = 2 • 10 5 . The black dot in each curve marks the percentage of connectivity that we can reach using the critical transmission radius R(n, θ). As the curves show, the percentage of connectivity increases with the beamwidth θ. All the values of θ reach 99% of connectivity when r ≈ R(n,θ)

2

. The growth of connectivity from R(n,θ) 2 to the benchmark radius R(n, θ) is almost null and incredibly slow. As one can see in Fig. 6, only the experiments that use omnidirectional antennas, which exactly fall in the RGG model, lead to a connected network in a strict sense (i.e. 100%). All the other networks are above 99% at r = R(n, θ), as well illustrated in Fig. 6 and7, which zoom in on the top part of the curves of Fig. 4 and5, respectively. When n = 10 6 , although the percentage of connectivity becomes closer to 100%, the networks remain disconnected in a strict sense for all values of θ. Discussion of simulation findings. In conclusion, we believe that our benchmark radius guarantees connectivity except for the nodes on the distal corona. The DARGG model is affected by border effects, especially for small values of θ, because the nodes oriented outside the disk have a limited number of nodes candidate to be neighbours. Inspired by this analysis, we propose in the next section two solutions to achieve full connectivity.

0.5 1 1.5 2 2.5 3 •10 -2 97 98 99 100 • • • • • radius percentage of connectivity omni θ = π/2 θ = π/3 θ = π/4 θ = π/6

Border effects and isolated nodes

In this section, we theoretically prove that if the radius is set to the benchmark radius R, there are still isolated nodes and all of them belong to the outercorona δD of the disk, thus confirming our experimental results. We also prove that these isolated vertices have their antennas oriented in such a way that their sectors do not intersect the core. Definition 2. Given n and θ, let the outercorona δD be the part of D comprised between the two circumferences centered at the field origin O and of respective radii R D and R D -R 2 . Let the area of outercorona be

A δD = R √ π - R 2 π
4 . Let n BOUNDARY be the number of nodes falling in the outercorona δD. Definition 3. Given n and θ, let the core denote D -δD, that is, D except the outercorona δD. Let the area of core be

A D-δD = 1 -R √ π + R 2 π 4 .
Let n CORE be the number of nodes falling in the outercorona δD.

From our experimental work, we know that the isolated vertices concentrate in the outercorona when the benchmark transmission radius R is adopted. The following lemma tells us that w.h.p. the number of nodes falling in the outercorona is

√ n log n ± O( √ n).
Lemma 1. Recalling γ = θ 2 π 2 , the number of nodes n BOUNDARY that fall in the outercorona satisfies:

P n BOUNDARY - n log n γ > √ n ≤ O log n n (2)
and

P n CORE -n + n log n γ > √ n ≤ O log n n . (3)
Proof. For any of the node i (i ∈ {1, • • • , n}, let X i = 1 if the node i belongs to the core (D -δD) and 0 otherwise. That is n CORE = n i=1 X i . Since the nodes are uniformly distributed, P[X i = 1] = A (D-δD) because D has unit area. By linearity of expectation, we have

E[n CORE ] = n i=1 E(X i ) = A (D-δD) n
We also have

E[n 2 CORE ] = E[ n i X 2 i + i =j X i X j ] = A (D-δD) n + A 2 (D-δD) (n 2 -n) .
Thus:

Var(n CORE ) = E[n 2 CORE ] -E[n CORE ] 2 = = A δD A (D-δD) n = O( n log n) .
Applying the Chebyshev's inequality with a = √ n leads to the lemma

P [ |n CORE -E[n CORE ]| > a] ≤ Var[n CORE ] a 2
Define an internal node to be a node falling in the core D -δD. The following statement tells us that for the radius R there is asymptotically almost surely no isolated internal node.

Lemma 2. With probability at least 1 -O(e -c ), there are no isolated internal nodes.

Proof. Let {v 1 , v 2 , • • • , v nCORE } be the set of internal nodes, that is the vertex set inside D -δD. For each v i of this set, let A i be the event v i is an isolated vertex. This time, let X i = 1 if A i occurs and 0 otherwise and set X = X 1 +• • •+ X nCORE . We will show that E[X] → 0 as n is large. As an internal node, v i is isolated iff no other vertex connected to it. Another node v j falls in the sector of v i with probability θR 2 and -given the orientation of v i -in order to create the edge (v i , v j ), we need v j to be oriented toward v i . Such an orientation occurs with probability θ π . Thus, P[ 1)) we get using the benchmark radius

X i = 1] ≤ A D -θ 2 π R 2 n-1 = 1 -θ 2 π R 2 n-1 . As x → 0, (1 - x) = e -x (1 + o(
R: P[X i = 1] ≤ 2e -log n-c . By linearity of expectation, E[X] ≤ nP[X i = 1] ≤ 2e -c and by Markov's inequality P[X > 0] ≤ 2e -c because Pr(X ≥ 1) ≤ E(X)
1 . That is with probability at least 1 -O(e -c ) none of the core vertices is isolated.

Using similar arguments and the fact that the number of nodes in D -δD is w.h.p.

n CORE = n -n log n/γ + O( √ n)
we can prove a slightly more powerful result:

Corollary 1. With probability at least 1 -O(e -c ), all the internal nodes have at least one internal neighbor.

The following lemma corroborate our experimental intuition. For nodes in δD, it is most likely that they are isolated once their sector does not intersect the core. Lemma 3. Let v be a vertex of the outercorona δD. Suppose that the sector S R,θ (v, ψ v ) does not intersect the core. Then, with probability at least

1 -O log 3/2 n n 1/2 v is isolated.
Proof. If the sector of v does not intersect the core then v cannot be connected to any of the n CORE vertices in D -δD. Then, v is connected to a vertex u ∈ δD with probability θ π . A | S R,θ (v,ψv) δD | where the first factor is the probability that u is oriented toward v, the second factor reflects the fact that u is in the sector of v and simultaneously in the outercorona.

Since

A |S R,θ (v,ψv) δD| ≤ θR 2 , the probability that v is isolated is 1 - θ π A | S R,θ (v,ψv) δD| nBOUNDARY ≥ 1 - θ 2 π R 2 nBOUNDARY
As typical values of the random variable n BOUNDARY is of order O( √ n log n) with high probability, we can conclude that v is isolated with probability larger than

exp -O log 3/2 n n 1/2 = 1-O log 3/2 n n 1/2 .

Reconnecting isolated nodes

In the following, we consider two reorientation algorithms. The first algorithm, T-core, flips the orientation of the isolated nodes toward the origin O of D. This algorithm requires that the center of the network is known by all the nodes and that they are equipped with a GPS device. The second algorithm, Greedy, flips the isolated nodes by adding π to their orientation. This algorithm works very well in practice.

Analysis of T -core algorithm. Let v be a node falling in δD whose orientation ψ v has been reoriented toward the center. In contrast with Lemma 3, v can have now all of the n nodes as potential neighbours. Then, v is isolated

with probability 1 -θ 2 π (R 2 -d(v) 2 ) n-1 where d(v) is a random real variable uniformly distributed in [0, R 2
] since v is in δD and at distance d(v) from the internal circumference that limit the outercorona. Now for any node v falling in the boundary, let X v = 1 if v is isolated and X v = 0 otherwise. After the reorientation of the isolated nodes, the expected number of isolated vertices is then re-oriented vertexv 1 -

θ 2 π R 2 (1 -d (v) 2 ) n-1
, where d (v) is a random variable uniformly distributed in [0, 1/2]. By Lemma 1, we have to sum on at most O( √ n log n) values. Thus, using again (1x) ∼ e -x (as x → 0) and approximating the summation by an integral, the expectation above is asymptotically ≤ O( n log n). for large x, we get after some algebra To analyze the greedy algorithm, we compute the probability that after the greedy flip, an isolated node v still does not meet the core. We define such a node butterfly. As illustrated in Fig. 8, the probability that a node v is a butterfly is P[v is a butterfly] = 1 -2(α(x)+θ) π where α(x) = arcsin 1/ √ π-R/2

1/ √ π-R/2+x
with x is a random variable uniformly distributed in [0, R/2]. For any of the node i in the outercorona δD, let X i = 1 if the node i is a butterfly and 0 otherwise. Let the number of butterfly nodes be n BUTTERFLY = v∈δD 1 -2(α(x)+θ) π .

By Lemma 1 and by using the approximation of α(x) for R → 0, it can be proved: Lemma 5. The expected number of isolated nodes after the Greedy flip algorithm is at least of order O(log n).

Conclusion

In this paper, we studied the issues involved in creating a connected mesh network with bidirectional links using directional antennas. We showed that there is no critical radius that alone guarantees connectivity as instead it happens for omnidirectional networks. We proved that the disconnected nodes are confined to a narrow corona at the border of the region of deployment and we presented two decentralized random protocols for network formation which rely on adequate transmission power and some additional local reconfiguration.

As a future work, we intend to extend our study to the robustness of DARGG for discovering the largest percentage of nodes that can be destroyed still preserving the network functionality.

Figure 1 .

 1 Figure 1. The parameters involved in setting a communication between two antennas.

Figure 2 .Figure 3 . 6 Figure 4 .

 2364 Figure 2. The size of largest connected component in EBRGG, VBRGG and DARGG model when θ = 30 with n = 2 • 10 5 .

= π/ 6 Figure 5 .

 65 Figure 5. The percentages of connectivity when n = 10 6

Figure 6 . 6 Figure 7 .

 667 Figure 6. The percentages of connectivity above 97% when n = 2 • 10 5

  x 2 ) dx .

Since

  nwhere erf is the standard error function (see Abramowitz and Stegun [13, Section 7.1.1]), using the asymptotic approximation

Lemma 4 .O 1 n 1 / 4

 4114 x 2 dx ≤ O 1 n 3/4 log n for large n. Thus the expected number of isolated nodes after reorientation is at most O 1 n 1/4 log 1/4 n . Using Markov's inequality, the following important observation follows: All the nodes of the outercorona after the T -core reorientation are no more isolated with probability at least 1log 1/4 n .Analysis of the Greedy algorithm.

Figure 8 .

 8 Figure 8. A butterfly and illustration of its probability.

Figure 9 .

 9 Figure 9. The average number of isolated nodes when n = 10 6 in DARGG(n, R, γ) (without any reorientation), with T -Core, and Greedy algorithms. The error bars represent the 95% confidence interval.

Fig. 9

 9 Fig. 9 reports the effectiveness of the reorientation algorithms experimentally tested.

TABLE 1 .

 1 NUMBER OF ISOLATED NODES

		n	r R	π 6 1144	π 4 561	π 3 266	π 2 26
		2 • 10 5	R D	1129	530	233	2
			2R D	1129	530	233	1
			R	2591	1271	618	74
		10 6	R D	2522	1222	543	4
			2R D	2522	1222	543	4
		TABLE 2. PERCENTAGE OF ISOLATED NOTES
	θ	π/2	π/3	π/4		π/6
	r	R	R/2	R	R/2	R	R/2	R	R/2
	δD	100	3	100	6.1	100	10.1	100	16.1
	D -δD	0	97	0	93.9	0	89.9	0	83.9

The work has been partially supported by GEO-SAFE (H2020-691161), by "RISE" Fondazione CR-PG, code 2016.0104.021, by the "GNCS -INdAM".