Meriam Bouzouita
email: mariem.bouzouita@supcom.tn

Yassine Hadjadj-Aoul

| Nawel Zangar
email: nawel.zangar@insat.rnu.tn

Gerardo Rubino
email: gerardo.rubino@inria.fr.

Estimating the number of contending IoT devices in 5G networks: revealing the invisible

Keywords: Massive accesses, Multi-class, IoT devices, Access Class Barring, estimation, network's overload

The explosive growth of connected objects is certainly one of the most important challenges facing operators' network infrastructures. Although it has been foreseen for a very long time, it is still not clear how to support such huge number of devices efficiently. A smarter planning of dedicated access slots would certainly limit the burden but remains insufficient since some equipments react to events which cannot be timed. Moreover, barring some IoT devices from accessing the network is very efficient; nevertheless, efficiency is generally linked to precise knowledge of the number of contending devices. Though, before connection establishment, the terminals are invisible to access points and, therefore, it is very difficult to estimate their number. A lower bound of backlogged devices can be determined. However, underestimating this number may lead to a congestion collapse whereas an overestimation implies underutilization of resources. In this paper, we propose a lightweight change to the standard to accurately reveal the state of network congestion by overloading connections' requests with the number of access attempts (number of times the device has been barred as well as number of attempts). Using such information, we propose an accurate recursive estimator of the number of devices. The obtained results demonstrated that the proposed solution not only makes it possible to estimate the number of equipments much better than existing techniques, but also allows determining precisely the number of blocked equipments.

INTRODUCTION

The fast development of radio communications has led to a larger bandwidth demand putting more and more pressure on mobile network's operators (NO). As a consequence, NO are adapting to these changes by proposing the new standard 5G for mobile networks, which envisions to improve support for existing and future services in a more flexible and agile way. In this way, 5G [START_REF] Lin | Flexible 5G M2M network access with cognitive RAN: Survey and design principles[END_REF] will include not only improvements at the core network, which tends to be more virtualized, but also at the access network, which will undergo a massive arrival of the Internet of Things (IoT), behind which there are huge expectations.

The excessive growth of the number of IoT 2 devices represents a real challenge, that needs to be taken into account by NOs, at the risk otherwise of deteriorating all other services. Indeed, the limited radio resources, the random access to the medium and the spectrum sharing between different applications are critical issues in the IoT context 3 . Therefore, radio networks need to be optimized to enable massive access of low cost and energy-efficient IoT devices [START_REF] Abbas | A Survey on Energy Conserving Mechanisms for the Internet of Things: Wireless Networking Aspects[END_REF] .

Low Power Wide Area Networks 5 (LPWAN) were developed to meet all IoT requirements, since their main aims consist in ensuring energy-efficient, simple and low cost devices communicating in long range at a low bit rates. Many solutions emerged, in particular, non-cellular IoTs, operating in unlicensed bands, such as LoRa and SigFox [START_REF] Zhang | Coverage Comparison of GPRS, NB-IoT, LoRa, and SigFox in a 7800 𝑘𝑚 2 Area[END_REF] . These technologies have a fast deployment process focusing more on energy consumption, very long range and low data rate. Nevertheless, the MAC nature of such proprietary LPWAN technologies, i.e. ALOHA-based access, is inefficient to face a massive access of IoT devices [START_REF] Adelantado | Understanding the Limits of LoRaWAN[END_REF] .

More recently, the Third Generation Partnership Project (3GPP) adapted its cellular network to meet the IoT specifications and needs. In release 13, a software upgrade of existing networks is provided to support the newly introduced Narrowband IoT 8 9 10 (NB-IoT) and the Extended Coverage GSM (EC-GSM) as cellular IoT solutions. 3GPP considers RAN overload control as the first priority improvement area; it introduced several overload resolution mechanisms in order to tackle the explosive growth of simultaneous IoT connections [START_REF]RAN Improvements for Machine-type Communications[END_REF] . Hence, several Physical RACH (PRACH) overload resolution methods were defined to improve the support of such devices in LTE-Advanced networks. First, Access Class Barring (ACB) mechanism was defined by 3GPP in Release 8 as an access barring solution for all IoT transmission and an Extended Access Barring, EAB, was defined in release 11 aiming to better prevent RAN overload 12 .

Many implementations of ACB and EAB were introduced in the literature to avoid congestion at the network's access 13 14 15 . Nevertheless, these solutions fail to avoid a synchronized access of IoT devices. Indeed, since the eNodeB ignores the number of IoT devices willing to connect, it cannot predict accurately the overload status, which may lead to a congestion collapse.

In this regard, we focus our research work on improving the NB-IoT network by investigating the Random Access Channel (RACH) for massive IoT accesses. We consider two main states, the number of backlogged devices waiting for EAB check and the total number of devices that pass the EAB check and wait for the random access (RA). As the number of contending devices is invisible until connection establishment, it is very hard to estimate it. In this paper, we propose new extensions and substantial improvements of our previous work. They are summarized in the following points:

• we offer a detailed and up-to-date state of the art;

• we extend our previous simple fluid model [START_REF] Bouzouita | Dynamic adaptive access barring scheme for heavily congested M2M networks[END_REF] , which represents only one class of traffic, to study the access of multi-class IoT devices into a mobile network;

• we refine our initial estimate [START_REF] Bouzouita | Dynamic adaptive access barring scheme for heavily congested M2M networks[END_REF] of the number of terminals, from the different classes of IoT traffic, that have attempted the access;

• we propose an estimation of the number of devices of different classes willing to connect. To the best of our knowledge, this is the first work in the literature addressing this issue.

The most significant novelty of this paper is to propose an accurate and insightful recursive estimation technique of the number of contending devices for each class. Based on the radio resources in terms of successful, collided or idle preambles, we can deduce the average number of terminals that attempted the access and finally we make a step backward to adjust the estimation of the backlogged terminals, waiting for the EAB check. The main specificity of our approach consists in leveraging a crowdsourced information. In fact, we propose to enrich each connection request with the total number of EAB and RA attempts. Thus, we introduce a lightweight change to the standard to allow the eNodeB to be notified about the congestion level.

The integration of the proposed approach will considerably reduce access costs by efficiently supporting a very massive number of terminals, which will allow to go much farther than the 50000 terminals per cell expected by the current standard. Indeed, the more accurate the estimate of the number of terminals, the more effective their access control will be.

The remainder of this paper is organized as follows. Section 2 is dedicated to some related works. Section 3 portrays our proposed model of access for multi-class IoT devices and studies its controllability. Section 4 describes the proposed algorithms given to estimate the number of terminals that attempted the access and those wanting to access. Section 5 is dedicated to the simulation setup and the analysis of our proposition. Finally, conclusions are presented in Section 6 with a summary recapping the main advantages and achievements of the proposed access model.

RELATED WORKS

In order to support an increasing number of IoT devices, networks operators and service providers will have to use different wireless access technologies. A large share of IoT devices will be served by short-range radio technologies operating on unlisenced spectrum (e.g. Wi-Fi and Bluetooth). For these networks, several challenges will need to be addressed in order to make these networks viable solutions for IoT support [START_REF] Hasan | A Survey on Multipath Routing Protocols for QoS Assurances in Real-Time Multimedia Wireless Sensor Networks[END_REF] . Among these, routing [START_REF] Al-Turjman | Cognitive Routing Protocol for Disaster-inspired Internet of Things[END_REF] , providing the requested Quality of Service (QoS)/Quality of Experience (QoE) support, fault tolerance remains open problems, which has been the subject of several works in the literature.

A significant proportion of IoT devices will still be enabled by wireless Wide Area Networks (WANs). These networks have the advantage of covering large areas at low cost. On the one hand, LPWAN networks, operating in unlicensed frequency bands such as LoRa or Sigfox, which have been dedicated to IoT devices, are being deployed on a large scale and provide connectivity to different types of IoT devices. On the other hand, 3GPP networks, generally operating on licensed frequencies, are already widely available worldwide and can offer a reliable connectivity service at a reasonable cost, through notably NB-IoT.

Massive access of IoT devices through wireless wide access networks, and particularly LPWAN, represents one of the most important challenges that network operators will face. Indeed, the intrinsic limits in radio resources, the random access of IoT terminals, whose number continues to grow, presents a real risk of congestion collapse [START_REF] Bouzouita | On the risk of congestion collapse in heavily congested M2M networks[END_REF] , which calls for the development of flexible and efficient scheduling and random access techniques [START_REF] Hussain | Medium access control techniques in M2M communication: survey and critical review[END_REF] .

The fact is, not all LPWAN networks are equal regarding the support of massive IoT devices. Although released much earlier, LoRaWan and Sigfox do not propose a solution to this problem, apart from the limitation of the "Time On Air" (TOA) [START_REF] Adelantado | Understanding the Limits of LoRaWAN[END_REF] . TOA allows reducing the burden at the access but fails in adapting to network conditions' variation. Hence, the optimization of the capacity of LoRaWAN and Sigfox remains an important issue to deal with. On the other hand, RAN overload control was identified very early as a first priority improvement area in 3GPP [START_REF]RAN Improvements for Machine-type Communications[END_REF] . The European Telecommunications Standards Institute (ETSI) also introduced several solutions to overcome such problems in mobile networks [START_REF][END_REF] . Thus, the newly introduced standards for IoT, such as the NB-IoT, benefit naturally from these advances. Among the concepts introduced, the Extended Access class Barring (EAB) technique is certainly the one that attacks the problem at its root, since it allows blocking access attempts for IoT terminals [START_REF]Evolved Universal Terrestrial Radio Access (E-UTRA); Radio Resource Control (RRC)[END_REF] .

To combat the overlapped simultaneous transmissions of multiple devices in a shared radio resource, a non-orthogonal multiple access (NOMA) 23 24 strategy is proposed, where multiple devices are allowed to transmit over the same sub-band and the base station performs successive interference cancellation to decode each device's message. The authors derived the system stability conditions, where the maximum packet arrival rate was found with and without quality of service guarantee and the obtained results allows to clearly improve the NB-IoT strategy [START_REF] Shirvanimoghaddam | On the Fundamental Limits of Random Nonorthogonal Multiple Access in Cellular Massive IoT[END_REF] .

In this paper, we focus on the EAB technique, which can be used in conjunction with the techniques introduced above. Indeed, the EAB proves its efficiency and remains necessary when an access of massive number of IoT devices is required. The idea introduced is rather simple, since it involves calculating a blocking factor. However, a good implementation would require a good knowledge of the number of terminals willing to attempt access to infer the probability of blocking. Unfortunately, this information is not available in the network. Thus, approaches based on an exact knowledge of the system model make it possible to obtain an optimal controller, as the one introduced in our previous work [START_REF] Bouzouita | Applying nonlinear optimal control strategy for the access management of MTC devices[END_REF] , but are generally not operational in practical situations. This explains the proliferation of system model-agnostic approaches [START_REF] Ksentini | Cellular-based machine-to-machine: overload control[END_REF] .

Most of existing approaches are based on estimating the number of terminals that attempted access, as they cannot have an accurate knowledge of the system's status. Thus, the number of IoT devices that succeeded at the access, knowing the probability of blocking, makes it possible to have an indicator on the number of terminals that wanted to attempt access. In this, we proposed a dynamic adaptive access barring scheme for heavily congested M2M networks [START_REF] Bouzouita | Dynamic adaptive access barring scheme for heavily congested M2M networks[END_REF] . The main idea behind the paper is to, first, determine the optimal number of devices which should attempt access. Then, to propose a system model-agnostic controller, which adapts the blocking probability based on the mismatch existing between the calculated and the targeted number of successes (i.e. optimal one). The obtained results demonstrated a reduced random access delay in addition to reduced re-transmissions, which has a direct impact on the IoT energy consumption. Nevertheless, no traffic differentiation is considered and all IoT devices are treated identically. Using a similar approach for deducing the optimal load, the authors, in previous works 28 29 , proposed to rely on the calculation of the steady state probabilities of a Markov-chain to deduce an efficient control scheme. A similar method was proposed by Yuan-Chi Pang et al [START_REF] Pang | Context-aware Dynamic Resource Allocation for Cellular M2M Communications[END_REF] . This method estimates the number of random access attempts, and then proposed a scheme for resources' allocation. The proposed solution is applicable in many IoT, as it insures a high resource efficiency and low random access delay without a prior knowledge of arrival traffic rate. To offer an individual reliability guarantee per device, another proactive approach [START_REF] Madueno | Massive M2M Access with Reliability Guarantees in LTE Systems[END_REF] is proposed. It consists of two phases, an estimation phase and a

𝑥 1,1 𝑥 1,𝐿,1 𝜆 1 𝜇 1,1 𝑥 1,1 𝜇 2,1 𝑥 1,𝐿,1 subsystem 1 subsystem 2 𝑥 1,𝑖 𝑥 1,𝐿,𝑖 𝑥 2 𝑥 2,𝐿 𝜆 𝑖 𝜇 1,𝑖 𝑥 1,𝑖 𝜇 2,𝑖 𝑥 1,𝐿,𝑖 𝑝 𝑖 𝑥 1,𝑖 𝜃 1 𝑥 2 𝜃 2 𝑥 2,𝐿 𝜃𝑥 2 𝑞 𝑥 2 -1 𝑁 𝑥 2 𝑥 1,𝐾 𝑥 1,𝐿,𝐾 𝜆 𝐾 𝜇 1,𝐾 𝑥 1,𝐾 𝜇 2,𝐾 𝑥 1,𝐿,𝐾 𝑝 1 𝑥 1,1 𝑝 𝐾 𝑥 1,𝐾 FIGURE 1
System model. Subsystem 1 represents the terminals, belonging to different classes (from 1 to 𝐾), that would like to connect; the objects in the state variable 𝑥 1,𝑖 represent those that can try to connect with a probability 𝑝 𝑖 , in the case of a failure they go into the waiting state 𝑥 1,𝐿,𝑖 for a back-off time duration. Subsystem 2 represents the objects coming from the different classes that can try to choose a preamble. In the case of a collision, they may attempt access a number of times. They leave subsystem 2 when they succeed in being the only ones to have chosen a preamble or when they reach the maximum number of attempts (with a rate of 𝜃). serving phase. In the estimation phase, the number of arrivals is estimated and then this information is used to tune the amount of resources allocated in the serving phase.

While efficient and powerful, these techniques fail to avoid a synchronized access for massive M2M devices [START_REF] Bouzouita | On the risk of congestion collapse in heavily congested M2M networks[END_REF] , which may result in some cases to a congestion collapse. On the other hand, only few approaches in the literature proposed to rely on crowd sourcing to estimate the system model state. Without being exhaustive, a crowd sourcing algorithm is proposed to adjust dynamically the back-off times according to congestion level and the traffic's type [START_REF] Bouzouita | Leveraging crowd sourcing technique for an optimized M2M access during emergency situations[END_REF] .

In this way, we propose in this paper to reveal the number of IoT devices willing to connect through crowd sourcing. To the best of our knowledge no one proposed an accurate estimation of such number, especially by class of IoT applications, which emphasizes the originality of our work.

A MODEL OF ACCESS FOR MULTI-CLASS IOT DEVICES

Model's definition

Our model for IoT devices' random access with multiple EAB factors (i.e. one factor per class) is influenced by the single-class system model that we have proposed in our previous work [START_REF] Bouzouita | Dynamic adaptive access barring scheme for heavily congested M2M networks[END_REF] .

The proposed model is a fluid one: the involved quantities and the whole numbers are seen as real (continuous) quantities. When attempting the random access, IoT devices contend for the same available preambles. As depicted by the 3GPP standard, the number of preambles 𝑁 should be an integer in the interval [4..64].

In each RACH opportunity, these preambles are split into successful (i.e. chosen by only one device), collided (i.e. chosen by two or more devices) and idle (i.e. selected by none of the devices) preambles. In the following, we compute the average values of these quantities that we have determined in another paper [START_REF] Bouzouita | Multiple Access Class Barring factors Algorithm for M2M communications in LTE-Advanced Networks[END_REF] . These quantities will be used by our algorithms.

Let's define 𝑞 𝑁 = 1 -1∕𝑁. The average number of successful preambles 𝑁 𝑆 , during the RACH opportunities, is given as follows (this is a classic 'balls into bins' problem):

𝑁 𝑆 = 𝐾 ∑ 𝑖=1 𝑁 𝑖 𝑆 = 𝑞 𝑥 2 -1 𝑁 𝑥 2 , ( 1
)
where 𝑁 𝑖 𝑆 represents the number of successful preambles chosen from class 𝑖. The average number of idle preambles 𝑁 𝐼 is given by the following equation:

𝑁 𝐼 = 𝑁𝑞 𝑥 2 𝑁 .
(2)

From ( 1) and ( 2), we obtain the expected number of failed preambles 𝑁 𝐹 :

𝑁 𝐹 = 𝑁 - ( 𝑁 𝑆 + 𝑁 𝐼 ) . ( 3
)
Now we are ready to describe the evolution of the state variables 𝑥 1,𝑖 (𝑡), 𝑥 1,𝐿,𝑖 (𝑡), 𝑥 2 (𝑡) and 𝑥 2,𝐿 (𝑡), for all 𝑖 ∈ ℂ, based on the model depicted in Fig. 1. The model's dynamics is described by the following system of differential equations: for all 𝑖,

⎧ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎩ d𝑥 1,𝑖 d𝑡 = 𝜆 𝑖 -𝑝 𝑖 𝑥 1,𝑖 -𝜇 1,𝑖 𝑥 1,𝑖 + 𝜇 2,𝑖 𝑥 1,𝐿,𝑖 , (4)
d𝑥 1,𝐿,𝑖 d𝑡 = 𝜇 1,𝑖 𝑥 1,𝑖 -𝜇 2,𝑖 𝑥 1,𝐿,𝑖 , (5)
d𝑥 2 d𝑡 = ∑ 𝐾 𝑖=1 𝑝 𝑖 𝑥 1,𝑖 + 𝜃 2 𝑥 2,𝐿 -(𝜃 + 𝜃 1 )𝑥 2 -𝑥 2 𝑞 𝑥 2 -1 𝑁 , ( 6
)
d𝑥 2,𝐿 d𝑡 = 𝜃 1 𝑥 2 -𝜃 2 𝑥 2,𝐿 . (7)
with the constraints given below:

• 𝑥 1,𝑖 , 𝑥 1,𝐿,𝑖 , 𝑥 2 and 𝑥 2,𝐿 should be nonnegative for all 𝑖,

• 𝜆 𝑖 > 0, 𝜃 1 > 0, 𝜃 2 > 0, 𝜇 1,𝑖 > 0, 𝜇 2,𝑖 > 0 and 𝜃 ≥ 0 for all 𝑖,

• 0 ≤ 𝑝 𝑖 ≤ 1 for all 𝑖.

Steady state analysis

In this section, we direct our focus on the analysis of its steady state performance.

For the sake of simplicity, we consider in the following the case where 𝜃 is equal to 0. Indeed, in a system working properly, this assumption should be valid.

The study of the steady state of the system comes back to consider that the derivatives expressed in equations (4-7) are equal to 0.

⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ 0 = 𝜆 𝑖 -𝑝 𝑖 x1,𝑖 -(1 -𝑝 𝑖 ) x1,𝑖 + 𝜇 2,𝑖 x1,𝐿,𝑖 , (8)
0 = (1 -𝑝 𝑖 ) x1,𝑖 -𝜇 2,𝑖 x1,𝐿,𝑖 , (9)
0 = ∑ 𝐾 𝑖=1 𝑝 𝑖 x1,𝑖 + 𝜃 2 x2,𝐿 -(1 -𝑞 x2 -1 𝑁 ) x2 -x2 𝑞 x2 -1 𝑁 , ( 10
) 0 = (1 -𝑞 x2 -1 𝑁 ) x2 -𝜃 2 x2,𝐿 . (11)
From ( 8) and ( 9), we obtain, for all 𝑖,

x1,𝑖 = 𝜆 𝑖 𝑝 𝑖 . ( 12
)
Replacing the value of x1,𝑖 in (9), we have

x1,𝐿,𝑖 = 1 -𝑝 𝑖 𝑝 𝑖 𝜆 𝑖 𝜇 2,𝑖 . ( 13
)
By adding equations ( 10) and ( 11) we have

-x2 𝑞 x2 -1 𝑁 + 𝐾 ∑ 𝑖=1 𝜆 𝑖 = 0. (14)
Write 𝜆 = ∑ 𝐾 𝑖=1 𝜆 𝑖 . We have

x2 𝑞 x2 -1 𝑁 = 𝜆.
The numerical solution to this equation in x2 can be easily obtained following a fixed-point approach (see next subsection), by iterating the sequence (𝑠 𝑛 ) 𝑛≥0 , with 𝑠 0 = 𝜆 and

𝑠 𝑛+1 = 𝑠 𝑛 (1 -𝑞 𝑠 𝑛 -1 𝑁 ) + 𝜆. ( 15
)
The convergence is very fast (a few iterations provide a very precise value). We can also note that the solution to ( 14) can be written in terms of the Lambert 𝑊 function, defined by 𝑊 (𝑥)e 𝑊 (𝑥) = 𝑥 [START_REF] Corless | On the Lambert 𝑊 function[END_REF] . This function is available in most scientific libraries and numerical analysis tools. We have

x2 = 𝑊 (𝑞 𝑁 𝜆). ( 16
)
Knowing x2 , the last component of the unique stationary point follows from (11):

x2,𝐿 = 1 𝜃 2 (1 -𝑞 x2 -1 𝑁 ) x2 . ( 17
)
So, the stationary or equilibrium point of the dynamical system is given by

x1,𝑖 = 𝜆 𝑖 𝑝 𝑖 , x1,𝐿,𝑖 = 1 -𝑝 𝑖 𝑝 𝑖 𝜆 𝑖 𝜇 2,𝑖 , x2 = 𝑊 (𝑞 𝑁 𝜆), x2,𝐿 = 1 𝜃 2 (1 -𝑞 x2 -1 𝑁 ) x2 .

Optimal number of IoT devices

Having too many contending IoT devices causes irremediably collisions and, therefore, an inefficient access; having too few devices would result in under-utilization of resources. The main idea, in this section, is to derive an optimal number of contending devices 𝑥 2 , which maximizes the success access probability.

All the devices passing successfully the EAB check will contend for the same 𝑁 radio resources to access the network. The optimal number of devices 𝑥 * 2 , from the different classes, performing an RA at the same time is the number 𝑥 2 maximizing 𝑁 𝑆 . To compute it, we propose to analyze the nonlinear equation given in 1). We provide here, a short summary following a direct approach, avoiding the classic use of the Lambert function 𝑊 defined on any complex number 𝑧 by 𝑊 (𝑧) = 𝑤 ⇐⇒ 𝑧 = 𝑤e 𝑤 34 as in previous subsection.

Let's us define function 𝑓 by means of 𝑓 (𝑥) = 𝑥𝑞 𝑥-1 for 𝑥 ≥ 0, where 0 < 𝑞 < 1. We have 𝑓 (0) = 𝑓 (∞) = 0 and 𝑓 ′ (𝑥) = 𝑞 𝑥-1 (1 + 𝑥 ln 𝑞), giving a maximum at 𝑥 = 𝑥 * = -1∕ ln 𝑞, whose value is -1∕(e𝑞 ln 𝑞). Replacing 𝑞 by 𝑞 𝑁 = 1 -𝑁 -1 and 𝑥 by x2 , this already gives us the stability condition of the "right side" of the model, that is, concerning the convergence of 𝑥 2 (𝑡) and 𝑥 2). Knowing that 0 < 𝑟 𝑎 < x * 2 allows to easily find 𝑟 𝑎 numerically, for instance using a Newton scheme [START_REF]wikipedia, Newton's method[END_REF] , or using a fixed-point method as in previous subsection. Let us provide a bit more details here. We defined the sequence (𝑠 𝑛 ) 𝑛≥0 by 𝑠 0 = 𝜆 and 𝑠 𝑛+1 = 𝜆∕𝑞 𝑠 𝑛 -1 𝑁 . Write back 𝑞 instead of 𝑞 𝑁 to simplify the presentation. We can first check by induction that this sequence is increasing. At the beginning of the sequence, 𝑠 1 > 𝜆 = 𝑠 0 because 𝑞 𝑦 < 1 for all 𝑦 > 0. Then, assuming that 𝑠 0 < 𝑠 1 < ⋯ < 𝑠 𝑛 , we must prove that 𝑠 𝑛 < 𝑠 𝑛+1 , that is, that

𝜆 𝑞 𝑠 𝑛-1 -1 < 𝜆 𝑞 𝑠 𝑛 -1 ⇐⇒ 𝑞 𝑠 𝑛 -1 < 𝑞 𝑠 𝑛-1 -1 ,
which is true because function 𝑥  → 𝑞 𝑥-1 is decreasing and 𝑠 𝑛-1 < 𝑠 𝑛 . So, (𝑠 𝑛 ) 𝑛≥0 is strictly increasing.

Then, we can check that the sequence is upper-bounded, for instance by 𝑥 * . First, for 𝑠 0 ,

𝑠 0 = 𝜆 < 𝜆 𝑞 𝑥 * -1 ,
and since 𝑥 * 𝑞 𝑥 * -1 = 𝑥 * ∕(e 𝑞), then 𝑞 𝑥 * -1 = 1∕(e 𝑞) and we have 𝑠 0 < 𝜆 𝑞 𝑥 * -1 = e 𝑞𝜆 < 𝑥 * . Then, assuming that 𝑠 𝑛 < 𝑥 * , we have 𝑠 𝑛+1 = 𝜆 𝑞 𝑠 𝑛 -1 < 𝜆 𝑞 𝑥 * -1 . Now, we conclude as we did for 𝑠 0 . This proves that when 𝑛 → ∞, 𝑠 𝑛 ↑ 𝑟 𝑎 ; as we stated before, the convergence is very fast.

Concerning the "left" part of the model (that is, the variables indexed by 1), the stationary point is always stable. This can be checked by any standard technique. Intuitively, the dynamics is similar as that of 𝑥 in the ODE 𝑥 ′ = 𝑎 -𝑏𝑥, with 𝑎, 𝑏 > 0: for any 𝑥(0), 𝑎, 𝑏, we have 𝑥 → 𝑎∕𝑏 and the equilibrium is stable. One can even solve explicitly that part of the differential system (for instance, using Maple or Mathematica) and observe that the solutions are continuous in the initial conditions.

In the following, we denote by x * 2 the value that maximizes the number of successful preambles' transmissions, that is, x * 2 = -1∕ ln 𝑞 𝑁 . Fig. 2 shows the evolution of function 𝑓 .

Controller synthesis

Having described the system's dynamics, let's now study its controllability. It can be clearly noted that the system, described in equations (4-7), is not controllable as a whole, as there is no means to act on the arrivals and, thus, on the number of the devices in the states 𝑥 1,𝑖 (𝑡) and 𝑥 1,𝐿,𝑖 (𝑡), for all 𝑖.

In the following, we then propose to study the partial controllability 36 of the system. We consider the subsystem represented by equations ( 6) and (7), which corresponds to subsystem 2, as indicated in Fig. 1. For the sake of simplification, we apply the same EAB factor 𝑃 or 𝑃 eab for the different classes, i.e. 𝑝 𝑖 = 𝑃 for all 𝑖 ∈ ℂ. Let, also, assume that ∑ 𝐾 𝑖=1 𝑥

]

, 𝐵 =

[ 𝑥 1 0 ] and 𝐴 = [ -(𝜃 + 𝜃 1 ) -𝑞 𝑥 2 -1 𝑁 ln(𝑞 𝑁 )𝑥 2 -𝑞 𝑥 2 -1 𝑁 𝜃 2 𝜃 1 -𝜃 2
] .

Matrices 𝐴 and 𝐵 are, respectively, the system matrix and the control matrix. Matrix 𝐴 relates to how the current state affects the state change. However, matrix 𝐵 determines how the system input affects the state change. It can be easily verified that the subsystem described above is controllable (as the rank of

[ 𝐵 𝐴𝐵 ] = 2
). Consequently, the whole system is partially controllable in its state variables 𝑥 2 and 𝑥 2,𝐿 . If these states are observable, one can deduce that a feedback controller can be designed to make the variables, and in particular 𝑥 2 (𝑡), converge to the optimal value, as defined in 3.3.

The subsystem described in equations (6-7) is non linear. Instead of proposing a non-linear control technique, as we did in a previous work [START_REF] Bouzouita | Applying nonlinear optimal control strategy for the access management of MTC devices[END_REF] , we propose, in what follows, the use of simple Proportional Integral Derivative (PID) controller [START_REF] Astrom | Advanced PID Control[END_REF] , as we are focusing on the estimation of the state variables, in this paper, and not on its control.

Instead of using a continuous PID controller, as suggested by the model, we opted to use a discrete version. Indeed, the real system that we control works in discrete time (i.e. frame by frame processing) and since the PID controller is agnostic of the model, it is more appropriate to use a discrete version.

The discrete PID regulator can be described by the following equation:

𝑃 eab (𝑛) = 𝐾 𝑝 𝑒(𝑛) + 𝐾 𝑖 𝑛 ∑ 𝑘=0 𝑒(𝑘) + 𝐾 𝑑 (𝑒(𝑛) -𝑒(𝑛 -1)), (19)
where 𝑛, 𝑃 eab , 𝑒, 𝐾 𝑝 , 𝐾 𝑖 and 𝐾 𝑑 represent respectively the instant, the controller output, the difference between the measured value -which will be described in the following section -and the targeted value (i.e. optimal value obtained in 3.3), the proportional gain, the integral gain and the derivative gain.

The main objective behind the PID controller is to make the total number of IoT devices attempting the access (i.e. 𝑥 2 ) converge to the optimal one 𝑥 * 2 . The analysis of the impact of the controller on the estimation accuracy will be analyzed in the performance evaluation section.

FINE-GRAINED ESTIMATION OF THE NUMBER OF IOT DEVICES

Optimizing network resources' usage necessarily requires the convergence of the number of devices attempting the access to the optimal number determined in the previous section. To reach such objective, one need to be able to effectively block the devices before they even attempt access. Barring them certainly implies to know the number of terminals wanting to access the network, those which are in the states variables 𝑥 1 or 𝑥 1,𝐿 . However, the devices in these states are not connected yet and thus invisible from the network's perspective.

We propose, in this paper, to estimate the number of IoTs, in state 𝑥 1 , indirectly via the number of terminals, in state 𝑥 2 , which successfully access the network. Specifically, we propose, from the number of successes, to estimate the terminals that attempted the access. This estimate will then be used to refine the estimate of the number of terminals wanting to access.

Estimation of the number of contending devices (𝑥 2 )

Several methods in the literature proposed estimating the number of terminals that attempted the access, as introduced in the state of the art section. The originality of our approach lies in the use of the "balls into bins" model, which perfectly represents the access process. Thus, based on the model, defined in section 3.1, we can certainly infer a first estimator of the number of devices attempting the access (i.e. the number of terminals in state variable 𝑥 2 ). Indeed, the number of devices succeeding in the access (𝑁 𝑆 ), the number of unused preambles (𝑁 𝐼 ), and the number of collided preambles (𝑁 𝐹 ) can give an idea of the number 𝑥 2 . end if

Algorithm 1 Optimized

16: x2 ← (1 -𝜂) x2 + 𝜂 x2 [𝑛] 17: x2,𝑖 [𝑛] ← 𝑁 𝑖 𝑆 [𝑛] 𝑁 𝑆 [𝑛] × x2 [𝑛], ∀𝑖 ∈ ℂ 18: return x2 , x2,𝑖 ∀𝑖 ∈ ℂ 19: end function
In order to avoid very large oscillations in the measurement of the parameters 𝑁 𝑆 , 𝑁 𝐼 and 𝑁 𝐹 , we propose in the following to consider one measurement per second, which corresponds to 100 frames. This ensures that the measures reflect reality and are therefore not the result of a completely random phenomenon.

Since a successful preamble concerns only one device and a collided preamble will concern at least two devices, a minimal number of devices 𝑥 2,𝑚𝑖𝑛 can be determined by 𝑁 𝑆 [𝑛] + 2𝑁 𝐹 [𝑛] (see line 5). This number represents a lower bound, which could be improved using the proposed model.

From equations ( 1) and ( 2), one can deduce 𝑥 2 knowing the other values, which can be measured by the access point. Since equation (1) presents two solutions, it is preferable to estimate this number from equation (2). Indeed, the solution of equation ( 2) is equal to ln(𝑁 𝐼 ∕𝑁)∕ ln(𝑞 𝑁 ), which is solvable only when we have the number of 𝑁 𝐼 different from 0 (see line 10).

When there is no more preamble available (𝑁 𝐼 = 0), reflecting a large number of IoT objects that attempted access, it is possible to measure the extent of congestion by looking at the number of terminals that have successfully accessed. It is in this sense that we consider only the stable solution of equation (1) (see Algorithm 1 for more details). The estimation of the number of contending devices x2 is, then, corrected using the factor expressed in line 16. The correction consists in considering the average (Exponential Weight Moving Average "EWMA") values instead of the instantaneous one.

Note that the absence of unused preambles and the absence of successful IoT devices may lead to an underestimation of the number of terminals within the state variable 𝑥 2 . Indeed, in this case there is no way to really estimate the extent of the congestion. Therefore, it is necessary to couple this estimate with a relatively effective controller.

The estimation of the number of devices per class can, then, be obtained in line 17. We just assumed here that the proportion of successes for each class corresponds to the proportion of devices attempting the access.

Crowd-based estimation of the number of IoT devices wanting the access (𝑥 1 )

To the best of our knowledge, the estimate of the number of equipment wanting to connect has not been addressed in the literature. The difficulty of this estimation is the absence of direct parameters to estimate such number. However, the blocking effects (i.e. barring factor) combined with the number of successful accesses certainly give an indication, more or less precise, of the number of IoT devices that have attempted the access. In fact, when the blocking factor in not too big (for very small values of 𝑃 eab ), the number of devices wanting to connect can be directly derived from the number of devices who just accessed the 𝑥 2 state, since its represents a known fraction 𝑃 eab of the total number of devices wanting to access.

The number of devices who just reached the state variable 𝑥 2 can be approximated by the difference between the number of estimated devices x2 [𝑛] and the IoT devices that was already there, which might be represented by the difference between the last estimate value x2 [𝑛 -1] and those that succeeded in the access (𝑁 𝑆 [𝑛 -1]) (see line 9 of Algorithm 2). The number of devices wanting to connect for each class can be deduced in a similar way (see line 11). Note that we are not considering here the number of devices aborting the transmission as a good system should completely avoid such case.

When the barring factor is too big (the access probability too small) the estimation of the number of devices cannot be estimated using the methodology explained above. Therefore, we propose using crowd sourcing to estimate such number. In fact, as there is no direct or indirect ways to estimate such number, we propose to overload the number of connections and accesses attempts in the connection request message sent by each IoT device. In this way, the reception of the connection requests' messages by the eNodeB becomes very informative since it allows to know the average number of attempts at each step, and thus the congestion level of the network.

We start by defining an ideal realistic target for the average number of attempts 𝑁 * eab , which should be more than one and smaller than three to have reasonable number of attempts. We, then, defined two thresholds: a minimum threshold 𝑁 𝑚𝑖𝑛 and the maximal threshold 𝑁 𝑚𝑎𝑥 around which the average should oscillate. An average number of attempts bigger than 𝑁 𝑚𝑎𝑥 means an underestimation of the congestion level, and requires, then, an adjustment upwards of the number of devices by adding to it a small quantity 𝛽 x1 [𝑛]. On the other hand, an average number small than 𝑁 𝑚𝑖𝑛 means an overestimation of the congestion level, which requires the adjustment of the number of devices downwards. The same technique was used to estimate the number of devices of the different classes.

In the current standard, the number of connections and accesses attempts may be overloaded into the "RRC connection request", which is sent just after a successful preamble transmission (i.e. reception of the "Random access response" (RAR) from the eNodeB) through the CCCH logical channel [START_REF][END_REF] . To be compliant with the actual version of the standard, 8 bits could be taken from the 40 bits "randomValue" field of the request. 3 bits could be reserved for each number (this gives the possibility to record up to 7 access attempts, which is more than enough for a stable system.) and 2 bits (set to 0) to indicate that the last 6 bits will be used to store such numbers.

x1 [𝑛] ← x2 [𝑛] -( x2 [𝑛 -1] -𝑁 𝑆 [𝑛 -1]) 𝑃 acb [𝑛] 11: x1,𝑖 [𝑛] ← x2,𝑖 [𝑛] -( x2,𝑖 [𝑛 -1] -𝑁 𝑖 𝑆 [𝑛 -1]) 𝑃 acb [𝑛]
, ∀𝑖 ∈ ℂ 12:

estimation for various loads. The obtained average values and the confidence intervals were computed for 30 experiments for each network's load value. In the third set of experiments, we test the impact of our proposed controller on the estimation's method.

Note that the error bars (in subsections 5.2 and 5.3) are obtained for 95% confidence intervals.

Estimation efficiency

Fig. 3 and Fig. 4 show respectively the existing gap between the real number 𝑥 1 and the estimated one x1 , and between the real value 𝑥 2 and the estimated one x2 . It can be seen that only very small fluctuations exist between 𝑥 1 and x1 and between 𝑥 2 and x2 , which proves the accuracy of our estimation. Similarly, as shown in Fig. 6, the estimated x2 , corresponds to the sum of x2,𝑖 estimated separately per class. This is a direct consequence of our assumption that the proportion of successes for each class corresponds to the proportion of devices attempting the access.

Estimation accuracy for various loads

Fig. 7 depicts the evolution of the estimation error of 𝑥 1 , 𝑥 1,1 and 𝑥 1,2 for various loads. It can be clearly seen that when the network's load increases, the average estimation error (of 𝑥 1 , 𝑥 1,1 and 𝑥 1,2 ) increases. More specifically, a remarkable increase (≃ 13%) is noted when 𝜆 = 20 and then we obtain a more accurate estimation (≃ 5%). In fact, when the network is more congested, 𝑥 1 (and respectively 𝑥 1,1 and 𝑥 1,2 ) tends to reach stable values and then the estimation's error is reduced. We also observe that the estimation error of 𝑥 1,1 is very slightly higher than 𝑥 1 and 𝑥 1,2 , because of the reduced arrival rate of such emergency applications. Indeed, when arrivals are infrequent, there are less observed data, the confidence level is reduced and then the estimation's error is increased.

Fig. 8 shows the evolution of the estimation error of 𝑥 2 , 𝑥 2,1 and 𝑥 2,2 for various loads. We can easily remark that when the network's load increases, the average estimation error (of 𝑥 2 , 𝑥 2,1 and 𝑥 2,2 ) increases slightly, but doesn't exceed 8%. Besides, the estimation error of 𝑥 2,1 is slightly higher than 𝑥 2 and 𝑥 2,2 , because of the infrequent arrivals of such class. The same explanation as above justifies this behaviour.

Impact of the controller on the estimation accuracy

To show the impact of using the proposed PID adaptation controller on our estimation's method, we compare, in the following, its behaviour with simple approaches using fixed EAB probabilities.

Fig. 9 and Fig. 10 show respectively the evolution of the estimation error of 𝑥 2 and 𝑥 1 for various loads. We can easily check the rapid degradation of the estimation's accuracy of 𝑥 2 (≃ 70% of estimation's error) and 𝑥 1 (≃ 100% of estimation's error) when a fixed EAB approach is applied and when the network's load increases. Only 5% of estimation's error is measured when an adaptive approach is used, independently from the network's load. To justify such behaviour, we show in Fig. 11 and Fig. 12, respectively, the evolution of the number of Idle preambles 𝑁 𝐼 and successful preambles 𝑁 𝑆 for various loads. We can clearly remark that when the network is undergoing a severe congestion (i.e our system is no more stable) and if a simple EAB approach is adopted, 𝑁 𝐼 is nearly equal to zero (i.e. resources' over-utilization) and 𝑁 𝑆 decreases gradually and becomes intolerable. However, when an adaptive PID controller is applied, 𝑁 𝐼 and 𝑁 𝑆 are slightly reduced but tend to reach stable values and then a more stable system, even if the network's load increases. In such a case, our estimation's method remains efficient. Nonetheless, this efficiency is deteriorated when a fixed EAB approach is used. Hence, the efficiency of our estimation's solution is closely related to the action of the controller in insuring the stability of the system.

CONCLUSION

One of the key challenges associated with the growth of connected IoT devices in 5G networks is to deal with the congestion collapse issue, particularly when a massive amount of simultaneous IoT arrivals occurs. To limit such a burden, many current solutions consider using barring probabilities at the access to reduce the amount of incoming devices. Nonetheless, the efficiency of such techniques remain closely related to an accurate knowledge of the number of contending IoT devices. Hence, a better estimation of the number of devices willing to connect, would efficiently help to overcome the risk of congestion.

Based on a model of access for multi-class IoT devices, we have, in this paper, proposed to enrich the connection requests with the number of access attempts to make the base station aware of the congestion's status. Using such information, we propose a novel crowd sourcing recursive algorithm to estimate the number of devices.

The obtained results demonstrated the efficiency of our proposition as we obtained estimated values very near to the real ones. We also investigated the trade-off existing between the estimation's accuracy and the use of an efficient controller. Indeed, the efficiency of the proposed method of estimation requires a stable system, and thus an efficient controller should be activated.

FIGURE 3 FIGURE 4 2 FIGURE 5

 3425 FIGURE 3 Evolution of 𝑥 1 & x1 as a function of time

2 FIGURE 6

 26 FIGURE 6 Evolution of x2 , x2,1 & x2,2 as a function of time

2 FIGURE 7 2 FIGURE 8

 2728 FIGURE 7Evolution of the estimation error of 𝑥 1 vs 𝜆

2 FIGURE 9

 29 FIGURE 9Evolution of the estimation error of 𝑥 2 vs 𝜆

2 FIGURE 10

 210 FIGURE 10Evolution of the estimation error of 𝑥 1 vs 𝜆

2 FIGURE 12

 212 FIGURE 11 𝑁 𝐼 vs 𝜆

  The parameters used are listed below: 𝑥 1,𝑖 (𝑡) number of backlogged devices from class 𝑖 at time 𝑡, where 𝑖 ∈ ℂ = {1, 2, … , 𝐾}, 𝐾 thus being the number of considered classes; 𝑥 1,𝐿,𝑖 (𝑡) number of blocked devices from class 𝑖 waiting for a re-attempt at time 𝑡, after having failed an EAB check; 𝑥 2 (𝑡) total number of devices from the different classes that pass the EAB check and wait to start RA attempt at time 𝑡; 𝜆 𝑖 arrival rate of devices from class 𝑖. Different traffic patterns will be considered in the following, depending on the type of IoT applications; 𝜇 1,𝑖 rate of EAB failure for class 𝑖, which is equal to 1 -𝑝 𝑖 ;

	𝜇 2,𝑖	rate of EAB re-attempts for class 𝑖;
	𝜃 1	rate of RA failure, which is equal to 1 -𝑞 𝑁 𝑥 2 -1	when 𝜃 is equal to 0 (see last item);
	𝜃 2	rate of RA re-attempts;
	𝜃	rate at which the devices abort the transmission after reaching the maximum number of RA attempts; in a correctly
		dimensioned system, we should have 𝜃 = 0;
	𝑝 𝑖	EAB factor for class 𝑖.

  2,𝐿 (𝑡): 𝜆 ≤ -1∕(e𝑞 𝑁 ln 𝑞 𝑁 ) = 𝑁 * 𝑆 . If 𝜆 < 𝑁 * 𝑆 , then we have two solutions to the equation 𝜆 = x2 𝑞 x2 -1 𝑁 , say 𝑟 𝑎 and 𝑟 𝑏 , with 𝑟 𝑎 < -1∕ ln 𝑞 𝑁 = x * 2 < 𝑟 𝑏 , where 𝑟 𝑎 leads to stability and 𝑟 𝑏 to instability (see Fig.

  Successful RA vs number of contending devices.The analysis of the function 𝑓 (𝑥) = 𝑥𝑞 𝑥-1 , for 𝑥 ≥ 0, where 0 < 𝑞 < 1, shows that it has an optimum 𝑁 * 𝑆 corresponding to 𝑥 * 2 = -1∕ ln 𝑞 𝑁 number of devices. Apart from this optimum, it corresponds to a particular number of successful RA two possible solutions (𝑟 𝑎 , 𝑟 𝑏 ).

	𝑁 * 𝑆
	# of successful RA
	𝑟 𝑎	𝑥 * 2		𝑟 𝑏
		# of contending IoT devices
	FIGURE 2 where	𝑋 =	[	𝑥 2 𝑥 2,𝐿

1,𝑖 = 𝑥 1 . For this subsystem's dynamics, we can write, in its state space, d𝑋 d𝑡 = 𝐴(𝑋)𝑋 + 𝐵(𝑋)𝑃 ,

(18)

  𝑥 2 estimation

	6: 7:	if 𝑁 𝑆 [𝑛] > 𝑁 * 𝑆 then 𝑁 𝑆 [𝑛] = 𝑁 * 𝑆
	8:	end if
	9: 10: 11:	if 𝑁 𝐼 [𝑛] ≠ 0 then ln( 𝑥 2,idle [𝑛] ← ln 𝑞 𝑁 𝑁 𝐼 [𝑛] 𝑁 ) x2 [𝑛] ← max(𝑥 2,𝑚𝑖𝑛 [𝑛], 𝑥 2,idle [𝑛])
	12: 13:	else 𝑥 2,success [𝑛] ←	𝑊 (𝑞𝑁 ln 𝑞 𝑁 𝑁 𝑆 [𝑛]) ln 𝑞 𝑁
	14:

1: global: 𝑁, 𝑁 * 𝑆 , 𝑁 𝑆 , 𝑁 𝐹 , 𝑁 𝐼 , and 𝑁 𝑖 𝐼 , ∀𝑖 ∈ ℂ 2: 3: function X2ESTIMATE(𝑛) 4: require: 𝛿, 𝜂, 𝛽, 𝑁 𝐼,min , 𝑁 𝐼,max , samples 5: 𝑥 2,𝑚𝑖𝑛 [𝑛] ← 𝑁 𝑆 [𝑛] + 2𝑁 𝐹 [𝑛] x2 [𝑛] ← max(𝑥 2,𝑚𝑖𝑛 [𝑛], 𝑥 2,success [𝑛]) 15:

Algorithm 2

 2 Optimized 𝑥 1 estimation 1: global: 𝑁 * eab , x2 , 𝑁 𝑆 , 𝑁 * 𝑆 , 𝑃 acb , and 𝑁 𝑖 𝑆 , x𝑖 2 , 𝑁 𝑖 acb , ∀𝑖 ∈ ℂ 𝛼 1 ∈ [0, 1], 𝛼 2 > 1, 𝜂, 𝜖 = 10 -6 , 𝛽

	2:
	3: function X1ESTIMATE(𝑛)
	4:
	5: 6:	𝑁 𝑚𝑖𝑛 ← 𝛼 1 𝑁 * acb 𝑁 𝑚𝑎𝑥 ← 𝛼 2 𝑁 * acb
	7:	x1 ← (1 -𝜂) x1 + 𝜂 x1 [𝑛 -1]
	8:	x𝑖 1 ← (1 -𝜂) x𝑖 1 + 𝜂 x𝑖 1 [𝑛 -1], ∀𝑖 ∈ ℂ
	9:	if 𝑃 eab [𝑛] ≥ 𝜖 then
	10:

require:

TABLE 1

 1 Basic simulation parameters

	Parameter	Value
	Simulation duration	30s
	Number of preambles 𝑁	54
	𝑥 * 2	54
	Backoff parameter	20ms
	ac-BarringTime	4s

end if 32: end function

PERFORMANCES EVALUATION

In order to evaluate the accuracy of the estimations, we built from scratch a discrete events' simulator in C representing the access of multi-class IoT devices in a Telco network. Table 1 summarizes the parameters used under this simulator.

We assume that there is one access point and that IoT devices are activated according to a Poisson traffic model where interarrivals are exponentially distributed. We considered two classes of service: the first class refers to emergency and prioritized applications and the second class refers to non prioritized applications (e.g. smart metering applications) which are delay tolerant. We also adopt a RACH configuration where one RACH opportunity occurs every 10ms with 54 preambles at each opportunity. When a RACH trial is declared unsuccessful, a device can retry the RA after a backoff time chosen uniformly between 0 and the backoff parameter fixed in Table 1. As described in the standard, a limited number of attempts (10 attempts) is considered here before aborting the transmission. Note that there is no dropout in the first phase and that the number of attempts is therefore unlimited. On the other hand, any failure in the EAB check blocks the device from a new trial during an ac-BarringTime.

In the following, we performed a series of experiments. In the first experiment, we evaluated the estimation accuracy of the number of contending devices as a function of the time. In the second set of experiments, we analyzed the accuracy of the


Pham Tran

Anh Quang

Yassine Hadjadj-Aoul
email: yassine.hadjadj-aoul@irisa.fr

Abdelkader Outtagarts
email: abdelkader.outtagarts@nokia-bell-labs.com

Deep Reinforcement Learning based QoS-aware Routing in Knowledge-defined networking

Keywords: Knowledge-defined networking, Software-defined networking, Routing, Deep Reinforcement Learning

Knowledge-Defined networking (KDN) is a concept that relies on Software-Defined networking (SDN) and Machine Learning (ML) in order to operate and optimize data networks. Thanks to SDN, a centralized path calculation can be deployed, thus enhancing the network utilization as well as Quality of Services (QoS). QoS-aware routing problem is a high complexity problem, especially when there are multiple flows coexisting in the same network. Deep Reinforcement Learning (DRL) is an emerging technique that is able to cope with such complex problem. Recent studies confirm the ability of DRL in solving complex routing problems; however, its performance in the network with QoSsensitive flows has not been addressed. In this paper, we exploit a DRL agent with convolutional neural networks in the context of KDN in order to enhance the performance of QoS-aware routing. The obtained results demonstrate that the proposed approach is able to improve the performance of routing configurations significantly even in complex networks.

Introduction

Routing optimization and particularly traffic engineering are the most fundamental networking task and, therefore, has been extensively studied in a number of contexts. The emergence of Software-Defined networking (SDN) paradigm unveiled new capabilities in routing. In SDN, the control plane and the forwarding plane are separated. A centralized controller is responsible for computing routing decisions, thus reducing the complexity of network elements. Moreover, it is able to monitor the demands and availability of resources globally; therefore, it is capable of matching the resource needs optimally. However, the size of the solution space as well as the complexity of the optimization problem are increased since SDN paradigm adds degree of freedoms in routing (flow-based forwarding vs destination-based forwarding) and the centralized controller has to solve the problem with a global view. As a result, new solutions of routing for SDN have been proposed [START_REF] Akyildiz | A roadmap for traffic engineering in sdn-openflow networks[END_REF][START_REF] Layeghy | SCOR: software-defined constrained optimal routing platform for SDN[END_REF]. In [START_REF] Clark | A knowledge plane for the internet[END_REF], the author proposed a Knowledge plane (KP), which is based on machine learning and cognitive techniques, to control the network. The KP is able to offer many advantages to networking, such as automation and recommendation and it may lead to a paradigm shift on the way we operate, manage, and optimize the data networks.

Machine learning (ML) techniques has been adopted and made breakthroughs in a number of application areas. ML algorithms can be classified into three categories: supervised learning (SL), unsupervised learning (USL), and reinforcement learning (RL). While SL and USL focuses on classification or regression tasks, RL algorithms learn to identify the best action series in order to maximize a given objective function (i.e reward). The most important advantages of ML is its capability of dealing with complicated problems; thus it is intuitive to exploit ML in the network domain where the complex problems are common [START_REF] Wang | Machine learning for networking: Workflow, advances and opportunities[END_REF]. In the context of routing, RL has been confirmed that it outperforms other ML techniques [START_REF] Valadarsky | A machine learning approach to routing[END_REF]; therefore, this paper focuses only on RL techniques.

RL techniques have been exploited to solve routing optimization [START_REF] Boyan | Packet routing in dynamically changing networks: A reinforcement learning approach[END_REF]. They are also used in QoS routing [START_REF] Lin | Qos-aware adaptive routing in multilayer hierarchical software defined networks: A reinforcement learning approach[END_REF]; however, table-based RL agents cannot provide efficient solutions for unseen network states. Deep Reinforcement Learning (DRL) is able to provide solutions for unseen network states, which cannot be achieved by traditional table-based RL agents. Moreover, it overcomes the iterative improvement process of optimization and heuristics by having a DRL agent providing a near-optimal solution in one single step. Recent breakthroughs in deep neural networks [8,[START_REF] Arulkumaran | A brief survey of deep reinforcement learning[END_REF] has improved the performance of DRL; thus paving a way for adopting DRL in the context of networking. Deep convolutional neural networks [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF] has proved its efficiency in various applications, e.g. image processing; therefore, the adoption of deep convolutional neural networks in the context of networking may offer some advantages.

In [START_REF] Valadarsky | A machine learning approach to routing[END_REF], the authors studied on the impacts of inputs and action spaces to the performance of machine learning in the context of routing problems. The results in the paper confirmed learning the link weights with traffic matrix outperforms other approaches. The link weights may have real positive values which cannot be solved by the well-known Deep Q Network algorithm [START_REF] Mnih | Human-level control through deep reinforcement learning[END_REF] since it can handle only discrete and low-dimensional action space [START_REF] Lillicrap | Continuous control with deep reinforcement learning[END_REF]. The authors in [START_REF] Lillicrap | Continuous control with deep reinforcement learning[END_REF] addressed the needs of continuous control by proposing a Deep Deterministic Policy Gradient (DDPG) algorithm. The capability of DDPG in solving routing problem has been confirmed in [START_REF] Stampa | A deep-reinforcement learning approach for software-defined networking routing optimization[END_REF]. However, the author in [START_REF] Stampa | A deep-reinforcement learning approach for software-defined networking routing optimization[END_REF] focused on minimize the mean latency in the network and did not address the QoS routing problem with multiple metrics (e.g. latency and packet loss rate).

In this paper, we study on a DDPG agent which learns to make the QoS-aware routing decisions. Unlike to the DDPG agent presented in [START_REF] Stampa | A deep-reinforcement learning approach for software-defined networking routing optimization[END_REF] which used fully connected layers, we take advantages of convolutional neural networks in order to extract the mutual impacts between flows in the networks; thus being able to provide better routing configurations. The rest of this paper is structured as follows. A brief review of KDN can be found in Section 2. A problem formulation followed by the proposed convolutional DRL network, which can improve the routing performance, is presented in section 3. The performance of the proposed DRL network is verified by simulations, presented in Section 4.

Knowledge-defined networking

In the context of SDN architecture, a concept of Knowledge plane (KP) has been introduced in [START_REF] Clark | A knowledge plane for the internet[END_REF]. The addition of a KP to the conventional SDN paradigm unveils a new paradigm, what is called Knowledge-Defined Networking (KDN). In KDN, the data plane is responsible for storing, forwarding and processing data packets. Practically, it comprises line-rate programmable forwarding hardware which operate without being aware of the rest of the network and depend on the other planes to populate forwarding tables and update configurations.

The control plane exchanges operational states in order to inform the data plane about forwarding and processing rules. In SDN, a logically centralized SDN controller is responsible for this task. It programs the data plane via a southbound interface. The role of the management plane is to guarantee the proper operation and performance of the network in the long term. Its main tasks are to monitor the network and to provide network analytic. In fact, this task is could also be handled by the SDN controller. The KP exploits the control and the management planes to provide a comprehensive view and control over the network. Based on ML approaches, it is capable of learning the behavior of the network and operating the network appropriately.

The KDN paradigm uses a control loop to provide automation, optimization, validation, and estimation. Fig. 1 describes the basic steps of the KDN control. The role of the analytics platform is to collect information to provide a completely global view of the network. It monitors the data plane elements in real-time and retrieves the control and management states from the SDN controller.

ML algorithms are able to learn the network behavior; thus, they play an important role in KP. The current and historical data offered by the analytics platform are fed to learning algorithms so as to generate knowledge. The decision maker (e.g. human decision or automatic decision) will give a decision based on knowledge and execute it via the northbound SDN controller API.

3 Convolutional Deep Learning for QoS-Routing

Network model

We consider a framework in which a decision maker repeatedly selects routing configurations. Each flow is identified by the source and the destination. Traffic and QoS demands of each flow may be different. For instance, the video streaming may require a low latency and packet loss while web surfing is tolerant to packet loss and latency. Thus, we introduce a metric QF(R), named the number of qualified flows of routing configuration R, which is the number of flows that meet their QoS requirements when applying the routing configuration R.

We model the network as a capacitated indirected graph G = (V, E, c), where V and E are the vertex and edge sets, respectively, and c : E ← R + assigns a capacity to each edge. The number of nodes is N = |V| and the number of links is L = |E|.

Traffic demands of flows are presented in a N × N matrix, named Traffic Matrix (TM), in which the entry (i, j) is the traffic demand between source i and destination j. Based on this matrix, the decision maker computes a Lvector, named link-weight vector, which is composed of weights of links in order to describe the routing configurations. This vector is exploited to calculate a forwarding table using the Dijkstra algorithm.

Deep RL agent model

The proposed RL agent is an off-policy, actor-critic, deterministic policy gradient algorithm [START_REF] Silver | Deterministic policy gradient algorithms[END_REF] that interacts with the data network through states, actions, and rewards [START_REF] Sutton | Reinforcement learning: An introduction[END_REF]. The state is the TM while the action is the link-weight vector. We define two reward functions:(1) the mean of QoS metrics (e.g. latency and end-to-end packet loss) and (2) the mean of qualified flows QF (R).

The objective of the agent is to identify the optimal policy π mapping from the state space S to the action space A, π : S → A, that maximizes the expected reward (minimize the mean of QoS metrics or maximize the number of qualified flows). It is done by repeatedly ameliorating its knowledge of the connections between the state, action, and reward over the means of deep neural networks of the actor and the critic.

A vanilla approach adopting the Deep Deterministic Policy Gradient (DDPG) to solve routing problem has been introduced in [START_REF] Stampa | A deep-reinforcement learning approach for software-defined networking routing optimization[END_REF]. In that paper, the actor and critic networks consists of dense layers connected serially. Consequently, the input is a vector in which each entry is the amount of a flow. This approach may not be able to explore the mutual impacts between flows. Consequently, we propose an extra module comprising multiple convolutional layers before the dense layers in order to allow the DRL network to learn the mutual impacts between flows more efficiently. Moreover, it is able to feed the proposed DRL network with multiple channels in order to provide a more comprehensive view of demands (e.g. latency and packet loss rate requirements). The details of this proposal is presented in the next Section.

Convolutional DRL for QoS-Routing

Conventional neural network includes dense neural network layers. Unlike to fully connected layer in which each neuron connects to every neuron in the previous layer, a convolutional layer is only connected to a few local neurons in the previous layers; therefore it is relatively simpler than the fully connected layer. Moreover, it is able extract and learn mutual impacts of adjacent flows, thus enhancing the efficiency of routing configurations. TM is the input of the convolutional layers. There are M convolutional layers in critic network as well as in actor network. In fact, the value of M as well as the hyper-parameter of convolutional layers (e.g. stride size, filter size, etc.) may impact the DRL's performance. In the proposed architecture we may, also, have several max pooling layers. Having several layers of max pooling has the disadvantage of removing too much information, which significantly degrades the performance. However, a thorough study of these parameters is beyond the scope of our paper. We use the same value of M and hyper-parameters for both critic network and actor networks in all configurations in simulations. The output of M convolutional layers is flattned and fed into D dense layer as the vanilla approach in order to compute the action (i.e. link-weight vector).

Simulation

To assess the performance of proposed approach we use a network topology BtEurope [START_REF]The internet topology zoo[END_REF] of 24 nodes and 37 full-duplex links, with uniform link capacities (10 Mbps). The OMNeT++ discrete event simulator [START_REF] Varga | Discrete event simulation system[END_REF] (v5.4.1) was used to obtain the latency and packet loss rate under given traffic conditions (TM) and routing configurations (R). We generate non-spare TM using a gravity model [18]. The total traffic entering (exiting) the network is generated by an exponential distribution with the mean 1000. The packet intervals of each flows follows an exponential distribution with the rate given in TM. The packet size is fixed at 1000 bits. We consider two QoS metrics: latency and packet loss rate. The QoS requirements of each flow is generated uniformly in range 1 ms to 100 ms for latency and 0 to 30% for packet loss rate.

Adam [START_REF] Kingma | Adam: A method for stochastic optimization[END_REF] is used for learning the neural network parameters. The learning rates for actor and critic networks are 10 -4 and 10 -3 , respectively. The discount factor γ is 0.99. The soft target is updated with the coefficient of τ = 0.001. The batch size is 32. For the dense neural network learning, we reuse the configurations in [START_REF] Stampa | A deep-reinforcement learning approach for software-defined networking routing optimization[END_REF], in which the number of dense layers is D = 2 with a numbers of units equal to 91 and 42, respectively. For the proposed approach, we used only one max pooling layer and 3 convolutional layers with 24 filters. The number of dense layers in the proposed approach is D = 1, with 42 units.

We runs 10 simulations with different random seeds. The results are the mean of these runs. Each run is composed of 100 episodes, where one episode includes 50 different TMs.

Homogeneous capacity networks

The DDPG with dense neural networks is the approach used in [START_REF] Stampa | A deep-reinforcement learning approach for software-defined networking routing optimization[END_REF] and the DDPG with convolutional neural networks is the proposed DRL network proposed in Section 3. For each type of DRL network, the objective could be maximizing the mean of QoS metrics or maximizing the mean of QFs. The combination of dense neural networks with the maximizing tmean QoS objective and maximizing mean of QFs objective are denoted as Dense-QoS and Dense-QF, while Conv-QF and Conv-QoS are the combination of convolutional neural networks with the QF objective and the mean QoS objective.

Fig. 4 shows the mean latency under difference configurations of neural networks and objectives. The mean latency of Dense-QoS is slightly worse than of Dense-QF. It also applies to the packet loss rate and the mean number of QFs as shown in Fig. 5 and Fig. 6. It is because the QF objective aims to maximize the number of flows satisfying the QoS requirements and thus being able to distribute traffic better. As a result, the lower congestion level can be obtained and it leads to a better performance in the mean of QFs as well as the mean of QoS. Consequently, we focus on the mean QF objective in the following simulations.

Heterogeneous capacity networks

In contrast to the previous section, the network composes of links with different capacities, i.e 10 Mbps, 20 Mbps, 50 Mbps, and 100 Mbps. This topology has higher capacity; however it is also more complicated than homogeneous networks. The QoS requirements are from 1 ms to 100 ms for latency and 0 to 30% for packet loss rate.

Both latency and packet loss rate of Conv-QF are better than of Dense-QF as shown in Fig. 8

Conclusions

Knowledge Defined Networking is a potential paradigm for future data networks. This paper studied the structures of neural networks in deep reinforcement learning (DRL) in the context of routing. By adopting convolutional neural networks, the proposed mechanism is able to learn the mutual impacts between flows in the networks; therefore, it is able to provide a better routing configurations. The gaps is even broadened in heterogeneous capacity networks, indicating the advantages of convolutional neural networks in coping with complex scenarios. In future, we intend to extend this work by modifying DDPG algorithm in order to enhance the performance as well as apply it to more complicated problem in networking.

-10

0

  Fig. 1: KDN operation

Fig. 2 :

 2 Fig.2: Neural network architecture used in[START_REF] Stampa | A deep-reinforcement learning approach for software-defined networking routing optimization[END_REF]

Fig. 3 :

 3 Fig. 3: Convolutional Neural network architecture

Fig. 4 :Fig. 5 :Fig. 6 :Fig. 7 :

 4567 Fig. 4: Mean Latency of Dense vs Convolutional networks

Fig. 9 :Fig. 10 :

 910 Fig. 8: Mean Latency in Heterogeneous networks

Fig. 11 :

 11 Fig. 11: Empirical CDF of ∆ QF


Jack Hodgkiss
email: jack.hodgkiss@stu.mmu.ac.uk

Soufiene Djahel
email: s.djahel@mmu.ac.uk

Yassine Hadjadj-Aoul
email: yassine.hadjadj-aoul@irisa.fr

An Advanced Coordination Protocol for Safer and more Efficient Lane Change for Connected and Autonomous Vehicles

Keywords: ITS, Smart Cities, Connected and Autonomous Vehicles (CAVs), Road Safety

In this paper we will explore novel ways of utilizing inter-vehicle and vehicle to infrastructure communication technology to achieve a safe and efficient lane change manoeuvre for Connected and Autonomous Vehicles (CAVs). The need for such new protocols is due to the risk that every lane change manoeuvre brings to drivers and passengers lives in addition to its negative impact on congestion level and resulting air pollution, if not performed at the right time and using the appropriate speed. To avoid this risk, we design two new protocols, one is built upon and extends an existing protocol, and it aims to ensure safe and efficient lane change manoeuvre, while the second is an original solution inspired from mutual exclusion concept used in operating systems. This latter complements the former by exclusively granting lane change permission in a way that avoids any risk of collision. Both protocols are being implemented using computer simulation and the results will be reported in a future work.

I. INTRODUCTION

The continuous evolution of urbanization and the associated increase in the fleet of vehicles make our cities more and more congested. This evolution incites the research community to rethink the current organization and management of services offered to cities inhabitants, such as transport and energy supply and consumption, in particular through a more intensive use of Information and Communication Technologies (ICT).

In the field of transport, Intelligent Transportation Systems (ITS) are certainly one of the most important building blocks to relieve roads (i.e. reducing traffic congestion) and make commuters journeys safer and more pleasant. ITS could be, indeed, used in different ways to optimize vehicles' circulation, such as making traffic light sequence more dynamic, increasing or decreasing the maximum speed in an area or rerouting traffic away from a road incident. ITS could also be very useful in alerting emergency services in the event of an accident, while helping them to arrive as quickly as possible by, for example, controlling traffic lights so that a Green route is created for the emergency vehicle, which will reduce the emergency services response time allowing for an increase in survival rates for all those involved in this event [START_REF] Djahel | Adaptive traffic management for secure and efficient emergency services in smart cities[END_REF].

The introduction of Connected and Autonomous Vehicles (CAVs) technology will certainly be a major step towards mak-ing ITS more efficient. In fact, these vehicles could interact faster and in more efficient way with the traffic management system to better control and mitigate traffic congestion, increase road safety and reduce air pollution [START_REF] Djahel | A communications-oriented perspective on traffic management systems for smart cities: Challenges and innovative approaches[END_REF]. They may also coordinate with one another over a communication medium using an agreed protocol to safely and efficiently undertake advanced vehicular manoeuvres.

Vehicle-to-Vehicle (V2V) communication technology is currently being developed by the automotive industry to allow vehicles to communicate with one another through establishing a wireless Ad-Hoc network operating in the 5.9 GHz frequency band. The inclusion of V2V communication in vehicles, more specifically CAVs, will make it possible to go even further in optimizing road traffic not only by reducing journey times but also by improving safety through a local collaboration of vehicles. This paper focuses on such aspect by exploiting the periodic exchange of beacon messages between vehicles as well as between vehicles and the road infrastructure to make lane change, which is considered as one of the major sources of road incidents, a safer and more efficient manoeuvre.

Enhancing lane change manoeuvre safety and efficiency has been the subject of several contributions in the literature. The authors, in [START_REF] Nilsson | If, when, and how to perform lane change maneuvers on highways[END_REF], proposed an algorithm for advanced driver assistance system (ADAS) that enables autonomous vehicles to calculate not only the lane manoeuvre but also; if it is desired and when it should take place. Although it is efficient, this solution may not meet the needs of all drivers due to safety constraints. In fact, a successful ADAS must be capable of adapting not only to the vehicle but also to the driver behavior, as stated in [START_REF] Butakov | Personalized driver/vehicle lane change models for adas[END_REF]. Thus, a personalized ADAS is needed to improve the effectiveness and ultimately its widespread use to reduce the collisions rate when performing lane change manoeuvres. To overcome the full customization issue, which makes the lane change manoeuvre a very complex problem given the diversity of drivers and their behaviour, we propose in this paper a novel lane change protocol, underpinned by an original lane change permission management solution, exploiting the collaboration between vehicles as well as the support of the road infrastructure.

The remainder of the paper is organized as follows. Section II gives an overview on lane change manoeuvre and outline its main safety requirements. In Section III, we describe in detail the key idea and operations of our two proposed protocols. In Section IV, we conclude the paper and present our future work plan.

II. LANE CHANGE MANOEUVRE

In this Section, we will briefly present the different steps involved in a lane change manoeuvre as well as the main requirements for undertaking it in a safe manner.

A. An overview Fig. 1 illustrates the first stage within the lane change manoeuvre, where vehicle A intends to move to the lane at its right. Before it can do this there must be a sufficient gap between its target position and the vehicles surrounding that area. To create this gap the vehicle A can broadcast its intention to change lane using IEEE802.11p beacon messages, as defined in the Wireless Access in Vehicular Environments (WAVE) Standard [START_REF]Ieee standard for wireless access in vehicular environments (wave)multi-channel operation[END_REF], to nearby vehicles. Fig. 2 shows the second stage in the lane change manoeuvre, where vehicles; B, C and D respond to vehicle A's request to change lane acknowledging its reception and confirming their willingness to cooperate with it to make this manoeuvre safe and efficient. Such cooperation includes adjusting their position based on vehicle A's current position and its projected position in the target lane, by accelerating or decelerating, if needed.

The final stage within the lane change manoeuvre is depicted in Fig. 3, where vehicle A has successfully changed its position to move to the target lane between vehicles B and D.

B. Safe lane change requirements

For any lane change procedure to be safe and efficient it must meet a number of requirements. The first requirement would be that all vehicles involved in a lane change (e.g., vehicles A, B, C and D shown in Figures 1, 2 and 3,) should follow the driving policies precisely such as not exceeding the speed limit enforced within the area and using indicators to alert nearby human drivers and pedestrians of their intention to change lane. Moreover, any dangerous lane change manoeuvres to be undertaken by two vehicles in close proximity should be avoided/postponed till it is safe to do so. Another requirement would be that vehicles in the target lane should cooperate by creating an adequate gap by either accelerating or decelerating until the available space is sufficient and guarantees the safety distance. Finally, this lane change procedure should minimize the negative impact on traffic by performing this manoeuvre as fast as possible without risking human lives in addition to avoiding halting the traffic flow in the target lane or the vehicle's current lane.

III. PROPOSED PROTOCOLS

Although a number of works have been proposed in the literature, which use inter-vehicles coordination to safely undertake a lane change or other manoeuvres, such as [START_REF] Butakov | Personalized driver/vehicle lane change models for adas[END_REF], [START_REF] Bashiri | A platoon-based intersection management system for autonomous vehicles[END_REF] and [START_REF] Petrillo | A collaborative control strategy for platoons of autonomous vehicles in the presence of message falsification attacks[END_REF], their performance is still limited in terms of either the achieved efficiency or safety level. Therefore, we present in this Section our two complementary protocols aiming to overcome the above limitations.

A. How to acquire a Lane change permission?

Here, we propose an original protocol to efficiently manage the lane change permission requests sent by vehicles intending to move a new lane. In this protocol the ability to change lane (towards a specific lane in case of a road with more than two lanes in each direction) within a given road segment is considered as a shared resource, similar to threads competing to read/write a shared data in operating systems where mutual exclusion is required, among all vehicles moving in the same direction. Therefore, the autonomous vehicles will act as if the ability to change lane is a resource shared throughout the vehicular network and once one vehicle, e.g., A, has its ownership no other vehicle in its close proximity can attempt a lane change manoeuvre until the ownership is released by A after completing its manoeuvre.

If the ability to change lane is currently held by another vehicle then all other vehicles must wait until it has been released back to the network. The vehicles will gain access to the resource of changing lane by forming a list operating on the first in first out (FIFO) principle in order to ensure no vehicle gets stuck waiting to have access.

This protocol has been proposed as it is believed to improve safety of lane change manoeuvres as it would ensure that within close-proximity no two vehicles may change lane simultaneously as this may result in a collision. There exists a number of challenges that must be solved before implementing this protocol. Firstly, this protocol requires that closeproximity is accurately defined since the resource is shared among nearby vehicles. Secondly, a robust mechanism that efficiently manages the shared resource (i.e. the capability of changing lane) and enforces its rules among all vehicles is required.

One way to define the scope of close-proximity is to consider the following conditions that should be met. Two vehicles, A and B, are in close-proximity if they are; (i) moving in the same direction, (ii) within communication range of each other, (iii) located either in the same lane or in two adjacent lanes, and (IV) using other on-board sensors such as LIDAR. Once these conditions are met, the rules of our proposed protocol need to be enforced to prevent any vehicle from changing lane without owning of this capability (i.e., permission to change lane) as this may lead to fatal consequences. To this end, we propose to split the road into a set of segments on which individual vehicles may request and acquire ownership of lane change capability. This would be implemented by creating a structure managed by either the Traffic Light Controller (TLC) or the Road Side Unit (RSU) that holds "road segment id", "lock value" and "vehicle id". This structure would allow all vehicles within the network to look-up a given road segment to determine if they are capable of taking ownership of the lane change capability or have to enter some blocked state waiting until the resource is released by the current owner. The TLC and RSU shall be used to store the state of a given road segment and relay this information to vehicles checking if they can change lane in addition to other vehicles confirming that a given vehicle can change lane, as illustrated in Fig. 4. Algorithm 2 describes how lane change requests are handled in this protocol. Fig. 5 illustrates two possible scenarios where a road segment has more than two lanes in each direction. In this case, we distinguish two situations where a lane change manoeuvre undertaken by more than one vehicle can take place simultaneously. Vehicles 'A' and 'C' may change their current lane and move to lanes 3 and 1, respectively, as even though they are departing from the same lane they are targeting two different lanes, which significantly reduces the risk of a collision. However, vehicle 'B' may not undertake a lance change at this moment as it may collide with Vehicle 'A' if they both attempt this manoeuvre simultaneously.

B. ILACH+

Once the capability of changing lane is acquired by a vehicle it then executes ILACH+. This protocol is an extension and improvement of the Intelligent Lane CHange assistant (ILACH) protocol proposed in [START_REF] Younes | A vehicular network based intelligent lane change assistance protocol for highways[END_REF]. Before presenting the main features of ILACH+ we will first briefly describe the key working principle of ILACH.

ILACH was developed to assist drivers in safely changing lanes to prevent fatal collisions on highways. It employs intervehicle communication capabilities to periodically collect data about neighbor vehicles for awareness purposes. Such data ranges from location, speed, direction and destination information. Each vehicle running ILACH uses this data to determine the distance between itself and its projected new location within the target lane known as D switch , the time needed for the vehicle to reach this location in the target lane known as T switch , and the distance between the position in the target lane the vehicle is aiming for and the first vehicle within that lane known as D gab . These values are used by ILACH protocol to determine if it should recommend an immediate lane change to the driver (or autonomous vehicle), or change the speed of the vehicle to allow the vehicle blocking/preventing the lane change to pass.

In ILACH+, we propose to improve ILACH by enabling collaboration between vehicles to achieve high safety and efficiency level when changing lanes. This means that instead of just recommending whether to change lane or not, as in ILACH, ILACH+ assists the vehicle to make lane change happen while respecting all safety and efficiency requirements. This is done by adding a new feature to ILACH whereby the vehicle intending to change its current lane can request and receive assistance from the nearby vehicles in both lanes (its current lane and its target lane). The vehicles in the target lane make appropriate adjustments to their speed to create an adequate gap for the requester vehicle while the vehicle in front of it, for example, accelerates to let it adjust its speed to move to the target lane. This feature has been proposed as it is not always possible for the vehicle intending to change lane to adjust its speed due to traffic density level within its current lane and the lack of collaboration between vehicles.

It should still default to rely on the vehicle with the desire to change lane to adjust its speed whenever possible without requiring further assistance, if the traffic conditions in both lanes permit. However, if traffic conditions are not in its favor then it should request assistance from the appropriate vehicles, using inter-vehicle communication, which in turn will make some adjustments to their speed by either accelerating or decelerating and then alerting the requester vehicle about the changes made so that it can initiate the lane change manoeuvre. Another benefit that ILACH+ brings is that it also notifies the surrounding vehicles of a vehicle's intention to change lane so that any receiver vehicle would postpone its lane change, if it desires to move to the same target lane, to prevent any possibility of collision or slowing down other vehicles 1 . By including this feature surrounding autonomous vehicles may anticipate the vehicle's manoeuvre and prepare for this scheduled event, leading to higher efficiency and safety level. The main operations of ILACH+ are summarized in the Algorithm 1.

IV. CONCLUSION

This paper introduced two novel complementary protocols that leverage vehicular communication to enable Connected and Autonomous Vehicles (CAVs) to perform lane change manoeuvre at the highest safety and efficiency level. The first protocol grants exclusive permission for lane change to a single vehicle within a given range and requires central management of lane change capability by the smart road infrastructure in place such as Traffic Light Controllers and Road Side Units. The second protocol, dubbed ILACH+, extends and improves an existing work by introducing the 1 Here, we assume that the penetration rate of vehicles compliant with our proposed protocols is not 100%.

Algorithm 2: ILACH+ main operations Data: V i : the vehicle intending to change its current lane; V i • S: current speed of vehicle i; Lane 1 : the current lane of V i ; Lane 2 : the lane that V i intends to move to (i.e., target lane); V j : the first vehicle on Lane 2 ; N Loc : the expected location of V i on Lane 2 ; D gab : the distance between V j and N Loc ; T gab : the required time for V j to reach N Loc ; D switch : the distance between V i and N Loc ; T switch : the required time for V i to reach N Loc in the case that it accelerates V i requests that V j creates an adequate gap; GoTo line 1 12 end 13 end cooperation between nearby vehicles during a lane change manoeuvre. We believe that both protocols can significantly enhance safety and efficiency of lane change manoeuvre for CAVs. As a future work, we are implementing both protocols using computer simulation to test their performance under varying scenarios.

1 if ( D gab T switch < V j • S)

Fig. 1 .Fig. 2 .Fig. 3 .

 123 Fig. 1. The first stage in a lane change manoeuvre

Fig. 4 .

 4 Fig. 4. Illustration of the exchange between Traffic Light Controllers (TLC)/Road Side Units (RSU) and autonomous vehicles to check the state of the lane change capability (locked or available)

Algorithm 1 :Fig. 5 .

 15 Fig. 5. Illustration of two lane change scenarios: permitted (vehicle A and C) and forbidden (vehicle A and B)

  then 2 V i is recommended to move to Lane 2 3 else 4 if (V i has the ability to adjust its own speed due to low traffic density) then 5 if (T switch 2 < T gab ) then 6 V i is recommended to move to Lane 2 and accelerate

	7	else
	8	V i should decrease its speed until V j passes
		it; GoTo line 1
	9	end
	10	else
	11