Patent Description:
The Fourth Industrial Revolution (or Industry <NUM>) refers to the automation of traditional manufacturing using smart technology such as Internet of Things, cloud computing.

Robotics is part of the Industry <NUM>. Indeed, in smart factories, robots are used to limit human operations. In this framework, communications play a key role. The application's requirements in Industry <NUM> is centered on multiple factors such as reliability, latency, longevity of communication devices. Currently, robots are often connected to a wired infrastructure. Time Sensitive Networking (TSN) is the standard Ethernet-based technology for converged networks of Industry <NUM> due to its capacity to support deterministic latency requirements. More precisely, TSN standard extend the traditional Ethernet data-link layer standards to guarantee data transmission with bounded ultra-low latency, low delay variation (jitter), and extremely low loss, which is ideal for industrial control and automotive applications.

TSN defines Time Aware Shaper (TAS) schedulers for guaranteeing the transmission of high priority deterministic traffic in a bounded time. However, TAS suffers from high overhead for short lived flows and thus degrades communication performance.

In addition, contrary to wireless technologies, TSN based networks cannot provide the required flexibility to support mobile industrial applications required for the factories of the future. Wireless networks have many advantages, including flexibility, low cost, ease of deployment but at the cost of reliability.

It is thus desirable to find a method for resource allocation in a wireless environment that satisfies application's requirements while ensuring good communication performance.

<CIT> discloses a scheduler in a wireless communication system, that may perform scheduling to respond to needs of various terminals, taking into consideration the quality of experience (QoE) in the wireless communication system.

<NPL>" attempts to give an extensive overview of the key facets of QoE-oriented wireless resources scheduling.

At least one of the present embodiments generally relates to a method for allocating a radio resource in a system according to independent claim <NUM>. Further embodiments of the method are provided in dependent claims <NUM>-<NUM>.

A method for allocating a radio resource in such a system is also provided, according to independent claim <NUM>. Further embodiments of the method are provided in dependent claims <NUM>-<NUM>.

A resource scheduler configured for allocating a radio resource in such a system is further provided, according to independent claim <NUM>.

A device hosting an application in such a system is further provided, according to independent claim <NUM>.

A system comprising such a resource scheduler and such a device hosting an application is also disclosed.

A computer program product comprising program code instructions is disclosed that can be loaded in a programmable device, the program code instructions causing implementation of the method according to the various embodiments when the program code instructions are run by the programmable device. A storage medium storing such a computer program is disclosed.

The characteristics of the invention will emerge more clearly from a reading of the following description of at least one example of embodiment, said description being produced with reference to the accompanying drawings, among which:.

The various embodiments are disclosed in the context of a smart factory where moving robots are installed to fulfill various missions such as for example moving from one location to another location in the factory within a certain amount of time. However, these embodiments may also apply in other environments such as for example environments including autonomous vehicles.

<FIG> depicts a system <NUM>, for example as part of a smart factory, in which the present embodiments may be implemented. The system <NUM> comprises a set <NUM> of moving robots 10A to 10D, each being capable of moving from one location to another in the factory. The set <NUM> may also include non-moving robots. The moving robots 10A to 10D are in wireless communication with one or more controlling devices 12A-12B with which they exchange application messages. Each controlling device 12A-12B may be a base station, a MEC (English acronym of "Multi-access Edge Computing") station or a mobile station. The controlling devices 12A-12B are for example configured to plan and monitor the missions of the robots 10A-10D. As an example, on <FIG>, the controlling device 12A transmits application messages comprising data representative of its mission to the robot 10A while the controlling device 12B transmits application messages comprising data representative of its mission to the robot 10C. The mission data may comprise displacement data (e.g. angular speed, linear speed, pressure level, etc), interaction data, motion data, etc. In return, the robot 10A (10C respectively) transmits application messages to the controlling device 12A (12B respectively). The application messages transmitted from the robots to the controlling devices comprise for example monitoring data or environment data. Depending on the applications, the exchanges of application messages may be periodic or aperiodic.

Each robot 10A-10D and each controlling device 12A-12B comprises at least one application module. Thus, an application message is more particularly exchanged between the application module of a robot and the application module of a controlling device. An application module generally comprises a software entity, namely the application, along with hardware elements such as an application buffer.

A robot usually comprises several physical elements, e.g. a wheel, an arm, etc. Thus, a given robot may need to exchange application messages comprising different types of data with a controlling device depending on the concerned physical element. Therefore, in the following, a stream Sk is defined as the set of application messages <MAT> transmitted from (respectively received by) a given physical element of a given robot in the set <NUM> of robots. Said otherwise a plurality of streams may be associated with one and the same robot, e.g. one stream associated with the arm of the robot and one stream associated with each wheel of the robot. In the following, K streams {S<NUM>, ··· , SK} are considered wherein each stream Sk is associated with a given application APPk. There is thus a one-to-one association between an application APPk and a stream Sk. The application APPk pushes messages <MAT> one-by-one into an application buffer of size one message, the messages <MAT> being transmitted at a time instant n using a radio resource to a corresponding receiver, e.g. to a controlling device.

In a wireless environment, the number of radio resources is limited. In the context of radio communication, the number of resources is defined as the number of frequency resources (e.g. subchannels where each subchannel comprises a finite number of frequency blocks) used in a limited amount of time. In order to appropriately allocate these limited radio resources, the system <NUM> further comprises a resource scheduler (RS) <NUM> configured to periodically, i.e. every dt (e.g. dt=<NUM>), allocate an available radio resource to one specific stream Sk. As depicted on <FIG>, every dt there is thus an opportunity, i.e. a time slot, for an application message <MAT> to be sent. As illustrated on <FIG> the robots and more precisely the streams are in competition to get the resource allocation. The resource scheduler <NUM> is thus configured to select one stream among K streams to allocate the radio resource to.

The resource scheduler <NUM> usually comprises a software entity along with hardware elements such as a buffer. The resource scheduler may be located in a base station, a MEC station or a mobile station.

<FIG> illustrates various application parameters that relate to a given application AAPk. The application AAPk is for example an application, located in one of the controlling device, configured to control the motion of an arm of a specific robot, e.g. the robot 10C. The application AAPk may be an application located in a specific robot and configured to monitor the environment of the robot. The application AAPk generates several messages <MAT> at various time instant n with n=<NUM>, <NUM>, <NUM> and <NUM>. These messages are to be sent on a transmission channel Hk between the antenna of a robot, e.g. 10C, associated with the stream Sk and the antenna of a controlling device, e.g. 12B. The transmission channel Hk is characterized by its channel error probability <MAT>.

Each application AAPk has some requirements defined by a set of application parameters whose values may vary temporally, namely a resilience <MAT>, a message lifetime <MAT> and a message period <MAT>.

The resilience <MAT> is the maximum amount of time the application AAPk authorizes for not receiving any message. In case the resilience <MAT> is violated, i.e. the application APPk does not receive any message during a time period superior to <MAT>, an application failure occurs. In this case, the associated robot may enter in a safety mode, e.g. a partial or complete stop with a reinitialization.

The message lifetime <MAT> is the lifetime of a message <MAT> when pushed into the application buffer (also called packet delay budget in the literature). Indeed, the message <MAT> of, for example, any monitoring application is only relevant for a limited time duration in particular because of robot motion. On <FIG>, the lifetime of the first message <MAT> is <NUM> time slots, the lifetime of the second and fourth messages <MAT> is <NUM> time slots and the lifetime of the third message <MAT> is <NUM> time slots.

The message period <MAT> is the time between the life's start of any two consecutive messages. This period may be variable if the application does not need a periodic traffic.

<FIG> depicts a flowchart of a method for resource allocation according to a specific embodiment. The method is implemented by the resource scheduler <NUM>.

The resource allocation comprises selecting, for an available radio resource, a single stream Sk (thus a single application APPk) according to some metrics <MAT>. The metrics <MAT> are defined to balance between the satisfaction of the application's requirements of any single stream, e.g. minimizing the number of application failures due to resilience violation, and the sharing of the radio resources between all devices in a most fair manner.

To this aim, the resource scheduler <NUM> uses for example an α-fair utility-based formalism to ensure a fairness resource allocation between the streams. Accordingly, a local cost function for the kth stream is defined as follows : <MAT> where <MAT> is the average probability of failure of the application APPk at time instant n. The value of α determines the expected fairness of the resource scheduler <NUM>, e.g. α = <NUM> provides a proportional fair, i.e. a balance between throughput of the network while at the same time allowing at least a minimal level of service for all users and α = <NUM> corresponds to a max-min fairness. A global cost function J(n) is then defined as a function of all the local cost functions. For example, J(n) is defined as the sum over k of the local cost functions : <MAT>.

The cost function J(n) is thus used by the resource scheduler <NUM> to select, at time instant n, one stream among the K streams to allocate a radio resource to.

The practical implementation of the resource allocation comprises steps S40 to S46.

At step S40, the resource scheduler <NUM> receives, from each application APPk, the application parameters representative of its application's requirements at time instant n, i.

At step S42, the resource scheduler <NUM> computes, for each stream Sk (thus for each application APPk), a metric <MAT> responsive to at least part of the received application parameters, i.e. <MAT>, to the average probability of failure <MAT> and further to the channel error probability <MAT>. <MAT> is initialized for n=<NUM>. For example <MAT> <NUM> or <MAT> is set to a random value different from zero. <MAT>is updated later on, at step S46.

Each metric <MAT> is computed as follows : <MAT> where: <MAT> is the number of messages buffered by the application APPk since the application started ; <MAT> is an instantaneous probability of failure of APPk.

At the time instant n, the probability of failure <MAT> is not known. It is thus predicted from <MAT> as follows : <MAT> where <MAT> in the case the stream k is selected to allocate the radio resource to and <MAT> otherwise. <MAT> may be computed in different ways depending on the concern for radio conditions and for application's requirements.

In a first embodiment, the metrics <MAT> take into account the resilience <MAT> in addition to the radio conditions represented by <MAT>. In this embodiment, the function <MAT> may be defined as follows : <MAT> or as follows : <MAT> where <MAT> is set equal to <MAT>, where nk is the last time instant at which a packet for the application APPk has been received. The quantity <MAT> represents the number of time slots before a resilience violation, i.e. an application failure. Either Qk(n) is decreased by one if the stream does not succeed in transmitting the packet or <MAT> is set to the resilience Rk otherwise. Said otherwise, in the case where the packet is correctly transmitted, i.e. if the resource is allocated and the packet is received, then <MAT> is set to the resilience value. In fact, when a transmission succeeded at time instant n, nk is set equal to the value n and thus consequently <MAT> is set equal to <MAT>.

In the case where the packet is not received (because not allocated or allocated but the transmission is unsuccessful), n is increased by <NUM> and thus <MAT> is decreased by one.

In a variant of the first embodiment, <MAT> is multiplied by an average resource usage <MAT>. As an example, the average resource usage <MAT> is computed by counting the number of resource allocations obtained by the stream Sk (or in an equivalent manner by the application APPk) until the current time instant n divided by the total number of time slots until the current time instant n. In another example, the average resource usage provides a uniform resource distribution as <MAT> where K is the number of streams. In another example, <MAT> reflects the resilience with <MAT>. The values of average resource usage thus belong to the interval [<NUM> ;<NUM>]. In this variant, the function <MAT> is thus defined as follows <MAT> or more generally as follows : <MAT>, where H() is a predefined function. As an example, H() is the identity function or an increasing affine function of <MAT>, e.g. <MAT> <NUM>.

In a second embodiment, the message lifetime <MAT> and the message period <MAT> are taken into account in addition to the resilience <MAT> (through <MAT>) and the radio conditions <MAT>. In this embodiment, the function <MAT> may be defined as follows : <MAT> where <MAT> is the number of remaining messages in the resilience window to be buffered, i.e. ( <MAT>) is the number of remaining messages after the current message, and fct() is a predefined function of <MAT> and/or of SNR and/or additional parameters. By multiplying ( <MAT>) by the message lifetime <MAT>, the number of remaining transmission opportunities is obtained as of the next message. For example, in the case of HARQ (English acronym of « Hybrid Automatic Repeat reQuest »), the function <MAT> may be embodied in such a way that it contains the instantaneous probability of failure for the next messages as well as for the current message. For the latter one, the channel error probability is made lower and lower as the time index increases such that <MAT> because the redundancy allows for an SNR increase. As an example, <MAT>.

In a variant, the function <MAT> may be defined as follows : <MAT> where <MAT> is set equal to <MAT> with rk being the first time instant wherein the considered message is considered for the scheduling (i.e. it's the life's start of the considered message)). Here, <MAT> represents a number of transmission opportunities before a resilience violation occurs. <FIG> illustrates the principle of transmission opportunities for each message of a given stream Sk. <FIG> is similar to <FIG>. Therefore, the elements in common are labelled with the same numeral references. On <FIG>, there are <NUM> opportunities to transmit the first message, two opportunities for the second message and three opportunities for the third message.

In a variant of the second embodiment, <MAT> is multiplied by an average resource usage <MAT> and <MAT> is thus defined as follows : <MAT> or more generally as follows: <MAT>, where H() is a predefined function. As an example, H() is the identity function or an increasing affine function of <MAT>, e.g. <MAT>.

In this second embodiment and its variant, <MAT> is thus split into a number of remaining transmission opportunities in the next buffered messages to come and an estimated number <MAT> of remaining transmission opportunities in the current message, i.e. before the current message death. When considering that at low layers (PHY, MAC) there might be Hybrid ARQ mechanisms, the instantaneous current packet probability of failure is not only dependent on <MAT>. Any HARQ-based receiver that accumulates redundancy each time a packet is not well decoded but transmitted (channel failures) observes a reduced current packet probability of failure even considering a constant channel error probability. Indeed, by increasing the redundancy, the probability of well decoding the received packet is increased as if the signal-to-noise ratio (SNR) was greater.

At step S44, the resource scheduler <NUM> compares the metrics <MAT> and, responsive to this comparison, selects a stream k* to allocate the radio resource to. The message <MAT> of the selected stream is thus sent through the channel Hk* to the receiver.

At this step, <MAT> and <MAT> for any k ≠ k*.

Depending on the definition of the cost J(n) : <MAT>.

At step S46, the average probability of failure <MAT> is updated for each k. The updated value <MAT> is to be used for the calculation of the metrics <MAT>. The probability of failure <MAT> is updated as follows:- For APPk* in the case where the packet corresponding to the sent message is received <MAT> and <MAT> is updated at the same time as follows : <MAT>.

At step S48, each instantaneous probability of failure <MAT> computed at S42 is transmitted to the corresponding application APPk. The transmitted instantaneous probability of failure <MAT> is received by the application APPk which uses it for updating at least one of its application parameters in order to try to decrease the instantaneous probability of failure at time instant (n+<NUM>).

The steps S40 to S48 are repeated iteratively while n is incremented. Thus, n is thus representative of an index of iteration.

<FIG> depicts a flowchart of a method for updating application parameters according to a specific embodiment. The method is implemented in an application module by an application APPk.

In a step S60, the application APPk receives information, e.g. the instantaneous probability of failure <MAT> provided by the resource scheduler <NUM>. <MAT> is only known by the scheduler, i.e. the application is not able to compute it. Consequently, transmitting this information to the application makes it possible for the application to adapt its requirements so as to decrease the probability of failure in the future so that <MAT>.

In a step S62, the application APPk updates at least one of its application parameters responsive to the received information. As depicted on <FIG>, the application APPk uses as inputs <MAT> and <MAT> to obtain an updated application parameter <MAT>. More generally, the application APPk uses as inputs <MAT>,<MAT>, and optionally <MAT>, to obtain an updated application parameter <MAT> and optionally updated application parameters <MAT>. <MAT> is a variable directly related to the application e.g. the velocity of the associated physical element like an arm, a wheel, etc..

In a variant depicted on <FIG>, a Lin-memory is used. Thus, the application APPk receives several instantaneous probabilities of failure <MAT> provided for time instants tε{(n- Lin),. As an example, Lin=<NUM>,<NUM>,<NUM>. The application APPk uses as inputs <MAT> and <MAT> to obtain updated application parameters <MAT>. As an example, Lout=<NUM>,<NUM>,<NUM>.

More generally, the application APPk uses as inputs <MAT>, <MAT> and optionally <MAT>, to obtain updated application parameters <MAT> and optionally updated application parameter <MAT>.

The updating function Fupdate may be defined in different ways.

In a first embodiment, the application initially considers a maximum probability of failure <MAT>. The value <MAT> is determined based on the performance's needs of the application. If the received value <MAT> then the application allows for a greater resilience such that <MAT>. This way, the stream Sk obtains more transmission opportunities. In an example, If the received value <MAT> is greater than the maximum probability of failure <MAT>, the resilience is increased by ΔR time slots, i.e. <MAT>, e.g. ΔR=<NUM>. In this embodiment, only the resilience parameter is updated. Otherwise (i.e. if <MAT>, the resilience is not modified. In a variant, the resilience is decreased in the case where <MAT> is significantly lower than <MAT>,.

In a second embodiment, probabilities of failure <MAT> are estimated from <MAT> as follows: <MAT> where Γ is a matrix and fctt(·) is a function that combines its input values. For example, fctt() is a function that outputs the average, variance, median or maximum of its input values. In a variant, fctt() is the identity function.

Given some precomputed relationships between the probability of failure and the application's requirements, the application APPk may updates its application parameters <MAT> and <MAT> or at least one of them, e.g. the resilience, to ensure that the estimated probabilities of failure <MAT> are lower than the previous ones, i.e. than <MAT>. Supposing <MAT> is constant over time, the application APPk can estimate Pek from the formula log <MAT>. Since <MAT> directly depends on the application's parameters, APPk can choose new application parameters therefrom to change the value of the <MAT>, j ≥ <NUM>.

In a third embodiment, the application APPk is a control application for a motor of a wheel of a robot. The variable <MAT> represents an angular speed provided by the motor to the wheel at time instant n. The application messages are monitoring information periodically required with the period <MAT> which is directly computed from the angular speed, e.g. <MAT>. Given a maximum probability of failure <MAT>, if <MAT>, then the application reduces the angular velocity such that <MAT> <MAT>. In an example, <MAT> is decreased by ΔX, i.e. <MAT>, e.g. ΔX=<NUM>/s or <NUM>/s. The value ΔX is determined based on the performance's needs of the application. Consequently, the period of the application messages increases such that <MAT>. If the application requires the same number of transmission opportunities within a resilience window, then the resilience is increased such that <MAT>. For example, the resilience is increased by ΔR time slots, i.e. <MAT>, e.g. ΔR=<NUM>.

In this embodiment, <MAT> is not updated.

In a fourth embodiment, one of the controlling devices 12A-12B acts as a global application that manages all the single applications APPk. In the case where too many probabilities of failure <MAT> are above their threshold <MAT>, then the controlling device that acts as a global application asks for a re-planification of the missions. Some streams, thus some applications APPk, may be stopped for a while and some others may have their application parameters redefined.

In a fifth embodiment, the application APPk knows some mathematical relationships between <MAT> and one or more of the parameters <MAT>. Said otherwise, the application APPk knows the following function <MAT> <MAT>. In another embodiment, only one application parameter or a subset of them is considered as an input of the function G(), e.g. <MAT>. In this case, the other application parameters are not updated.

The application APPk thus computes at least one new application parameter among <MAT> and optionally <MAT> from <MAT> by inverting G(), <MAT> is determined by the application APPk so that it is lower than the received <MAT>. For example, <MAT> is determined as follows: <MAT>, e.g. Δf=<NUM>%. The value Δf is determined based on the performance's needs of the application.

In one specific embodiment, the application APPk learns the function G() offline. In a variant, the application scans all the possible values of all the application parameters and selects the set of values that either minimizes <MAT> or leads <MAT> close to an arbitrary target value of <MAT>.

In a sixth embodiment, the application APPk transmits to the resource scheduler the target failure probability <MAT>. In this embodiment, the resource scheduler, instead of the application APPk, updates at least one application parameter to ensure a probability of failure <MAT> lower than or equal to <MAT>.

From <MAT>, the resource scheduler thus determines values <MAT> or at least one of them so that <MAT>. The determined value(s) is(are) transmitted to the corresponding application APPk.

In a variant, the resource scheduler only determines a single value of <MAT> and transmits it to the corresponding application APPk. In this variant, the values <MAT> and <MAT> are not updated. Thus, they are set equal to the values previously given by the application, i.e. <MAT>.

In another variant, the resource scheduler determines pairs of values of <MAT> while <MAT> is not updated, i.e. <MAT>. Since the number of possible pairs might be very high, the resource scheduler may select a finite number of them, for example by taking the values of <MAT> in a limited search space, such as a linear quantization between a maximum and minimum value.

In another variant, the application APPk informs the resource scheduler of the requested feedbacks, for example, a set of values <MAT> satisfying <MAT>, for a fixed value of <MAT> or any combination of this type. In this case, the application APPk transmits to the resource scheduler <MAT>, and <MAT>. For its part, the resource scheduler determines a set of values <MAT> satisfying <MAT> and fulfilling the resilience constraint, i.e. <MAT>.

As depicted on <FIG>, the application parameters updated by the resource scheduler may be either transmitted to the application APPk as proposals or directly implemented within the application hardware.

In a seventh embodiment illustrated by <FIG>, <MAT> is used to compute <MAT>. <MAT> and <MAT> are thus transmitted to the application APPk which updates at least one of its application parameters in the same manner as mentioned in the first to sixth embodiments, using <MAT> as an additional parameter used to update the application parameter. As an example related to the fourth embodiment, G() is defined as <MAT>.

<FIG> illustrates schematically an example of hardware architecture of a resource scheduler according to a specific embodiment.

The resource scheduler <NUM> comprises, connected by a communication bus <NUM>: a processor or CPU (acronym of "Central Processing Unit") <NUM>; a random access memory RAM <NUM>; a read only memory ROM <NUM>; a storage unit <NUM> such as an hard disk or such as a storage medium reader, e.g. a SD (acronym of "Secure Digital") card reader; and at least one set of communication interfaces COM <NUM> enabling the resource scheduler <NUM> to transmit and receive data.

The processor <NUM> is capable of executing instructions loaded into the RAM <NUM> from the ROM <NUM>, from an external memory (such as an SD card), from a storage medium (such as the HDD), or from a communication network. When the resource scheduler <NUM> is powered up, the processor <NUM> is capable of reading instructions from the RAM <NUM> and executing them. These instructions form a computer program causing the implementation, by the processor <NUM>, of the method described in relation to <FIG>. The method described in relation to <FIG> may be implemented in software form by the execution of the set of instructions by a programmable machine, for example a DSP (acronym of "Digital Signal Processor"), a microcontroller or a GPU (acronym of "Graphics Processing Unit"), or be implemented in hardware form by a machine or a dedicated component (chip or chipset), for example an FPGA (acronym of "Field-Programmable Gate Array") or an ASIC (acronym of "Application-Specific Integrated Circuit"). In general, the resource scheduler <NUM> includes electronic circuitry adapted and configured for implementing the method described in relation to <FIG>.

<FIG> illustrates schematically an example of hardware architecture of a device <NUM> hosting an application APPk according to a specific embodiment. The device <NUM> may be a robot or a controlling device.

The device <NUM> comprises, connected by a communication bus <NUM>: a processor or CPU (acronym of "Central Processing Unit") <NUM>; a random access memory RAM <NUM>; a read only memory ROM <NUM>; a storage unit <NUM> such as an hard disk or such as a storage medium reader, e.g. a SD (acronym of "Secure Digital") card reader; and at least one set of communication interfaces COM <NUM> enabling the device <NUM> to transmit and receive data.

Claim 1:
A method for allocating a radio resource in a system comprising a resource scheduler and a set of devices, each device hosting at least one application, each application transmitting messages to at least one receiver on a transmission channel, characterized in that the method comprises, executed by the resource scheduler, at least one iteration n of :
a) receiving (S40), from each application, application parameters representative of requirements for said application at iteration n ;
b) computing (S42), for each application, a metric from an instantaneous probability of failure of said application, from an average probability of failure of said application computed at iteration (n-<NUM>) and further from a channel error probability of said transmission channel, wherein the average probability of failure of said application and said instantaneous probability of failure of said application are computed from at least one of the received application parameters and from said channel error probability of said transmission channel ;
c) comparing (S44) the metrics and, responsive to said comparison, selecting the application to allocate the radio resource to ;
d) updating (S46), for each application, the average probability of failure at iteration n from the average probability of failure of said application computed at iteration (n-<NUM>) ; and
e) transmitting (S48) said instantaneous probability of failure computed at iteration n to each application, said instantaneous probability of failure at iteration n being used by said application to update at least one of its application parameters, said updated at least one application parameters being used by the resource scheduler at an iteration (n+<NUM>) to allocate a new radio resource.