Masoud Taghavian

Yassine Hadjadj-Aoul

Géraldine Texier

Nicolas Huin

Philippe Bertin

A Fair Approach to the Online Placement of the Network Services over the Edge

Keywords: Network function virtualization, Placement, Branch-and-Bound, Edge, QoS

Unavoidable transition from rigid dedicated hardware devices towards flexible containerized network services, introduced by Network Function Virtualization (NFV), brings novel opportunities while several new challenges. Meeting the expectations of NFV in post-5G networks depends on the efficient placement of the services. The online placement of the network services, demanding strict end-to-end latency requirements over the edge networks, with restricted computing resources presents a challenging problem which is worth investigating. We propose a Branch-and-Bound search approach for finding optimal placements of the network services by applying several different cost functions to maximize the service acceptance. Extensive evaluations has been carried out, and the results confirm significant improvements when we consider a fair distribution of the resources on the edge.

I. Introduction

Network operators adopt Network Function Virtualisation (NFV) and Software-Defined Networking (SDN) in 5G networks to create more flexible networks that can rapidly integrate new services. SDN separates the control and data planes, for centralized and intelligent management of networks using software applications. And, NFV virtualizes the entire classes of network functions using cloud computing technologies, to realize and manage the network services.

In NFV, the service placement is a crucial step which involves allocating physical resources for network services with specific Service Level Agreement (SLA) constraints, requiring heterogeneous resources. In terms of the complexity, the placement problem is proved NP-Complete by reducing the Bin Packing problem to it [START_REF] Chen | A novel algorithm for NFV chain placement in edge computing environments[END_REF]. It is encountered in various NFV uses-cases in post-5G networks, ranging from Virtual Network Function Forwarding-Graph (VNF-FG) placement and Network Slicing, to virtualization of the Core Network (CN), Content Delivery Network (CDN), Internet of Things (IoT).

The placement of services is studied following many objectives. These objectives are addressed as an optimization problem, subject to various constraints including the resources, Quality of Service (QoS) requirements, and other constraints specific to the objective or the use-case.

Resource optimizations, QoS optimizations (e.g., latency, availability, reliability, security), energy consumption, Revenue to Cost (R2C), and Service Acceptance (SA) are among the well-studied objectives [START_REF] Mirjalily | Optimal network function virtualization and service function chaining: A survey[END_REF]. We are interested in maximizing the SA as our objective. SA is defined as the number of services that can be placed over the network subject to the resources and QoS requirements.

Two general categories which are envisaged for the placement problem in the literature are offline and online placements. In an offline placement scenario, we know all the service requests in advance, while in an online placement scenario, we do not have any information about the future service requests, and we need to make a placement for a service request as soon as it arrives (we may also have time restrictions for performing the placement) [START_REF] Mirjalily | Optimal network function virtualization and service function chaining: A survey[END_REF]. Following our objective, in offline placement, although the complexity is not negligible, by a well-defined Integer Linear Programming (ILP) model, we can perform an optimization to find the maximum number of the accepted services (a.k.a. acceptance ratio). In online placement, although we do not know the service requests beforehand (consequently, we can not optimize directly the number of accepted services), we can ensure that the placement of the current service request enhances the chances of accepting the future service requests. This can be done by optimizing a cost function which is consistent with our objective. The scalability is another important requirement which needs to be considered in an online placement solution.

The online placement of the network services, demanding strict End-to-End (E2E) latency requirements, over the edge networks, with restricted computing resources presents a challenging problem that is worth investigating. To meet the required latency of the network services, we can not place them on the clouds far from the end users, where the resources are abundant. Some of the services must necessarily stay on the edge, where we are not generous in spending these resources.

The contributions of the current work can be summarized as follows:

• We model the problem in ILP and resolve the model to obtain the global optimum (which can only be achieved in an offline scenario).

• We propose an efficient approach based on Branchand-Bound (BaB), capable of achieving the optimal and the near-optimal results according to several the cost functions and the search strategies. • We explore several cost functions and demonstrate inconsistency of bandwidth and/or latency optimization, and the benefits of fair placement, with our objective of maximizing the SA. The fairness of our approach can be explained in two ways. On the one hand, our achieved improvements are due to the fair distribution of the resources in our placements. On the other hand, our approach makes a fair compromise between the service provider and the network/cloud provider. The service provider prefers that the realized latency of their services be the lowest possible (ideally zero), whilst the network provider would rather it to be the highest possible, allowing them to push the placement of the services from the edge to the clouds where the resources are abundant and cheaper. The maximum acceptable latency for the realized services is where on which we can work to meet the expectations of both sides.

This paper is organized as follows. First, we explore the related works in Section II. We present our ILP and Column Generation (CG) formulation of the problem in Section III. Next, we describe in detail our BaB approach in Section IV. Then, in Section V we plunge into the evaluations to investigate the effectiveness of our solution. Finally, we conclude and mention the future directions in Section VI.

II. Related Works

Studying the placement algorithms in the literature begins by the introduction of NFV. It is a commonly encountered in various use-cases, considering different categories of the objectives.

A significant part of the studied placement algorithms involves the exact solutions, where the problem is formulated as an ILP or Mixed Integer Linear Programming (MILP) and is solved with solvers and optimizers.

In [START_REF] Morin | VNF placement algorithms to address the mono-and multi-tenant issues in edge and core networks[END_REF], the authors investigate the placement of multiconstrained services to maximise the number of placed service requests, first by proposing an ILP resolution, and then a heuristic. They consider bandwidth and latency for the links, and computing resources for the nodes on an edge-core star-based network topology. Although strict requirements of E2E latency of the service requests and the anti-affinity rules are not studied, but limited node resources was considered on the edge, and they demonstrated that a fair distribution of the resources can improve the number of accepted services.

Jin et al. try to address VNF placement problem in [START_REF] Jin | Latencyaware VNF chain deployment with efficient resource reuse at network edge[END_REF], considering the resource shortage on the edge with latency guarantees. First, they formulate the problem in MILP to minimize the consumption of the computing resources (by sharing and reusing the already placed VNFs), and the bandwidth. Note that using an already placed VNF reduces the cost of placing a new VNF, but it may result in using more bandwidth and latency to access that VNF. Although, they did not consider anti-affinity rules, but they proposed an interesting Depth-First Search (DFS) based algorithm for placing the Virtual Network Functions (VNFs) and the Virtual Links (VLs) to obtain near-optimal solutions for an online placement scenario.

The placement problem on the edge is also investigated in [START_REF] Gouareb | Virtual network functions routing and placement for edge cloud latency minimization[END_REF], using MILP over a batch-based service requests, minimizing the overall network latency. They show that their model can improve the acceptance rate of the services with strict latency requirements, via sharing the already placed VNFs and considering the affinity rules. They define an affinity matrix to identify the VNFs with high-affinity, that can be placed over the same network node. Highaffinity is defined when two VNFs exchange a big amount of data flow, while low-affinity or anti-affinity is considered to allow critical VNFs to be placed on separate network nodes (in case of failure). They proposed a heuristic placement algorithm for big networks and a large number of requests, and they compared it with a Random-Fit algorithm.

Even though the ILP-based methods guarantee the optimality, they could suffer from scalability issues. Performing an exact resolution could require a long execution time for obtaining an optimal solution, which could make restrictions for using in large-scale networks. This limitation presents a significant obstacle in online placement scenarios with time constraints.

Heuristic approaches are often retained, when it comes to the scalability. Best-Fit or Decreasing First-Fit is one of the most well-known and efficient placement heuristic, which places the VNF by sorting the nodes and placing the VNFs over the node with the maximum amount of available resources iteratively. [START_REF] Khebbache | Scalable and cost-efficient algorithms for VNF chaining and placement problem[END_REF] explores heuristic algorithms (especially the Best-Fit algorithm), and the authors propose a multi-stage graph algorithm to find near-optimal solutions in a scalable manner. They evaluate the execution time, the acceptance ratio, and the average cost of the placement in terms of the assigned resources.

In [START_REF] Zhang | Adaptive interference-aware VNF placement for servicecustomized 5G network slices[END_REF], an adaptive heuristic approach is proposed to maximize the total throughput of accepted requests in an edge/core cloud network, considering anti-affinity rules. They try to avoid VNF consolidation to avoid severe performance degradation (a.k.a. VNF interference), making it intolerable for some QoS-sensitive 5G use cases (e.g., autonomous driving and 4K/8K HD video).

Although, designed to obtain a solution in a reasonable time frame, heuristics do not provide quality guarantees, and the risk of getting stuck in local optimums is extremely high.

Meta-heuristic and evolutionary algorithms are another direction addressing the placement problem. In [START_REF] Leivadeas | VNF placement optimization at the edge and cloud[END_REF], a fast sub-optimal Tabu Search based approach is proposed to minimize the end-to-end latency and the overall deployment cost. Despite being powerful in escaping from local optimums, these algorithms suffer from unpredictability, especially in terms of execution time, which is extremely important in online placement.

Advanced AI search mechanisms and recent developments in machine learning techniques, and particularly Deep Reinforcement Learning (DRL), have gained lot of attention due to their promising potential. An ILP placement approach is proposed in [START_REF] Xu | Qos-aware VNF placement and service chaining for iot applications in multi-tier mobile edge networks[END_REF] for low-latency IoT services on Multi-Tier Mobile Edge Networks to maximize the throughput and the SA ratio. They devise a Reinforcement Learning (RL) approach to address the online placement of the requests, but they do not take into account anti-affinity rules.

Although, the problem of the placement has been studied for a while in several related areas, but to the best of our knowledge, the placement problem of the service requests with strict E2E latency on the edge network having limited node resources, considering user-location and anti-affinity is not yet addressed in the literature. Generally, the proposed placement approaches try to optimize whether the cost of the resources, or the QoS requirements like bandwidth and latency. A network service requires node resources (a.k.a. computing resources) for deploying its VNFs, and link resources (a.k.a. network resources) for realising its VLs. Supposing that we can not share the already placed VNF, and we need to provide what is required as node resources for deploying the VNFs, the optimization involves placing the VNFs as close as possible to the user-location and the other VNFs, to minimize the bandwidth usage and/or the E2E latency. We will show that this optimisation approach could have a devastating effect on the edge networks with limited node resources, and it needs to be avoided. We will see that it can lead to draining the resources at the proximity of the end users, which results in service rejection. Accordingly, we do not follow an optimization approach toward the bandwidth/latency, however we consider them as constraints which need to be satisfied to achieve maximum SA.

Affinity and anti-affinity rules in cloud-computing provide a mechanism for establishing a trade-off between performance and reliability of the realised service. Affinity asserts putting VNFs on the same network node for increasing inter-networking performance. While, anti-affinity is used to improve the reliability and the availability by preventing certain VNFs of the same service from sharing the same physical resources in order to reduce the impact of a single network node failure [START_REF] Bouten | Semantically enhanced mapping algorithm for affinity-constrained service function chain requests[END_REF]. In this paper, we consider anti-affinity for all the VNFs of the service (i.e., all of the VNFs of a service request are placed over separate network nodes), for the following reasons. First, the anti-affinity rules is effective in satisfying the availability requirements of the services that need to be scaled over separate network nodes (scaling horizontally) to ensure that a node failure would not violate the availability of the whole service [START_REF] Zhu | Availability-aware mobile edge application placement in 5G networks[END_REF]. Moreover, placing the VNFs of the same service over the same network node (a.k.a. VNF consolidation) may cause severe performance degradation (a.k.a. VNF interference), which is not acceptable for some QoS-sensitive 5G use cases [START_REF] Zeng | Demystifying the performance interference of co-located virtual network functions[END_REF]. Last but not least, not considering this constraint results in a remarkable relaxation of the placement problem, so that the gain of using different placement approaches becomes marginal.

III. Model

Table I Notations

Name Description

G = (V, E) Substrate network V Set of nodes of the network E Set of links of the network ω + (v) Outgoing neighboring nodes of v ∈ V ω -(v) Ingoing neighboring nodes of v ∈ V Be Bandwidth available on the directed link from v ∈ F k to j ∈ w + (v) H k = (F k , L k ) Virtual graph of service k F k Set of VNFs to be placed for service k L k Set of VLs between the VNFs of service k ω + (f ) Outgoing neighboring VNFs of f ∈ F k ω -(f ) Ingoing neighboring VNFs of f ∈ F k B l
Bandwidth requested between the two VNFs of

l ∈ L k C f Computing resources requested by f ∈ F k Cv Computing resources available at v ∈ V De Delay experienced on link e ∈ E D k Delay requested for service k ∈ K D l
Delay requested between the two VNFs of l ∈ L k

The placement problem consists in placing a service request graph on an Substrate Network (SN) graph. A service graph k ∈ K, where K is the set of services, is indicated by a directed graph H k = (F k , L k ), containing a set of VNFs F k , and a set of VLs (connecting the VNFs) L k , plus SLAs (reflecting the QoS requirements). A VNF f ∈ F k requests a subset of resources (here we consider CPU C f ), and each VL l ∈ L k demands an amount of bandwidth B l . Likewise, a SN is represented by a directed graph G(V, E) of its nodes V and links E. A node v ∈ V has a resource capacity (C v ), and a link e ∈ E has a bandwidth capacity of B e , as well as QoS metrics (here we consider E2E latency). Finally, we consider that a VNF f ∈ F can only be instantiated on a subset of nodes V f ⊆ V of the SN. In the case of a user location, this subset can be reduced to only one node. The problem is finding the mappings of the VNFs and the VLs of the service requests into the network nodes and the network paths respectively, subject to the constraints. The notations are summarized in Table I.

A. Compact formulation

Variables The ILP contains two sets of binary variables: the first set, x, represents the routing decision, and the second set, y, the service placement decision. More precisely, the variable x l,k e = 1 if the virtual link l of service k ∈ K is using the link e ∈ E; and 0, otherwise. The variable

y f,k v = 1 if the VNF f ∈ F k of the service k ∈ K is instantiated in node v ∈ V f ;
and 0, otherwise. Moreover, for each service k ∈ K, we force y f,k v to 0 for any node v that doesn't belong to V f . Constraints We consider the CPU as a node resource, and the bandwidth as a link resource. In addition, in terms of the QoS metrics, end-to-end latency for the entire service. Note that, our approach does not impose any limitations for adding more resource types or more QoS metrics for nodes, links, or services. A VNF can demand a set of resources of different types (e.g., CPU, GPU, RAM, storage, FPGA, etc.), which can be provided by the network nodes. Consequently, we consider two sets of capacity constraint:

k∈K l∈L k B l x l,k e ≤ B e , ( 1a
)
which is the bandwidth capacity constraint (e ∈ E); and

k∈K f ∈F k C f y f,k v ≤ C v , ( 1b
)
which is the CPU capacity constraints (v ∈ V ). First, we ensure that the VNFs of a service are only placed once throughout the network with:

v∈V y f,k v ≤ 1 ∀k ∈ K, ∀f ∈ F k . (1c)
Moreover, VNFs of the same service k ∈ K cannot be placed on the same network node v ∈ V , ensured with:

f ∈F k y f,k v ≤ 1, ∀v ∈ V f , ∀k ∈ K. ( 1d
)
For each service k ∈ K, we ensure the virtual link l = (f i , f j ) ∈ L k flow conservation at each node v ∈ V with:

e∈ω + (v) x l,k e - e∈ω -(v) x l,k e = y fj ,k v -y fi,k v (1e)
Finally, we bound the end-to-end service latency. We consider the sum of the latency required by VLs as the endto-end service latency, and the sum of the latency provided by placed network paths with the following constraints:

e∈E D e l∈L k x l,k e ≤ D k ∀k ∈ K, ( 1f
) e∈E D e x l,k e ≤ D l ∀k ∈ K, ∀l ∈ L k . ( 1g
)
Objective The objective function is defined as:

max k∈K v∈V y f0,k v , ( 1h
)
where f 0 is the "first" function of the service. We only need to count the number of "first" functions in the objective since the flow conservation constraints ensure that a solution contains no partial embedding. Cuts An ILP solver's performance depends on the problem's relaxation (i.e., the problem without integrality constraints). It evaluates the nodes of its Branch-and-Bound tree with the linear relaxation of the problem. If the linear relaxation solution at the current node is worse than the best integer solution found so far, it can prune the node. The linear relaxation quality (the gap between the integer and relaxation solution) significantly impacts the resolution time since a good relaxation will lead to a faster exploration of the tree. We can improve the lower bound by devising cuts. These constraints are not necessary for the correctness of the model as they are implicitly satisfied by the constraints of the base integer model, but they are usually violated in the relaxed version of the problem.

This formulation has a poor relaxation, however, we can improve it by exploiting the one VNF per node constraint. Since nodes can host only one VNF of the same service, we can define the minimum amount of bandwidth used by each service. For example, let's consider a daisy chain service graph with 3 VNFs (F1, F2, and F3), and 4 VLs connecting F1 to F2, F2 to F1, F2 to F3, and F3 to F2. If each VL would require 1 unit of bandwidth, at least, we require four units of network bandwidth. In mathematical form, we can express the minimum bandwidth usage as:

k∈K v∈V l∈L k B l,k y f0,k v ≤ e∈E B e . ( 1i
)

B. Embedding Decomposition

The previous formulation lacks scalability. To solve larger instances, we can use decomposition methods. Multiple decompositions are available. We focus on the embedding decomposition, where each variable represents a possible embedding of the service onto the physical network. This decomposition is suitable when multiple services share the same configuration (same bandwidth, same number of CPUs, and same latency requirements) as they can share the same embedding and we can easily compute the resource allocation.

Because the number of embeddings is exponential, an embedding-based formulation would require an exponential number of variables (columns). However, a solution only contains a few of them. To generate only useful columns, we use the CG algorithm [START_REF] Desaulniers | Column generation[END_REF]. The algorithm solves large-scale linear programs via a back-and-forth resolution of a master problem and one or multiple pricing problems. Starting from a reduced master problem, the master problem feeds dual values to the pricing problems, and the pricing problems feed improving columns to the master problem. For each service k, we need to generate an embedding γ among all possible embeddings Γ k for the service k.

1) Master problem:

We only need the set of variables z kγ ∈ N to indicate the number of services k allocated on the embedding γ. Each embedding γ is defined by the amount of bandwidth it uses on each link e, denoted by δ e (γ), and the number of CPUs used on each node v, denoted by θ v (γ).

We ensure that, for each service k ∈ K, we do not embed more services than requested with:

γ∈Γ k z kγ ≤ n k , ( 2a
)
where n k is the number of requests requiring the same service k. For each link e ∈ E, we define its capacity constraints as:

k∈K γ∈Γ k δ e (γ)z kγ ≤ B e , (2b)
And for each node v ∈ V , we define its capacity constraints as:

k∈K γ∈Γ k θ v (γ)z kγ ≤ C v . (2c)
Finally, the objective function is written as:

max k∈K γ∈Γ k z kγ . (2d)
2) Pricing problems: Each service k has its own embedding sub-problem. The problem is similar to the compact formulation, so we reuse the same notations for the variables.

• x l e ∈ {0, 1} indicates if the virtual link l ∈ L k of the service is routed through the physical link e ∈ E.

• y f v ∈ {0, 1} indicates if the VNF f ∈ F k of the service is instantiated in node v ∈ V .
The first set of constraints ensures that each VNF ∀f ∈ F is embedded on a physical node:

v∈V y f v = 1. ( 3a
)
Unlike the compact formulation, we write these constraints as equalities to make sure that the service graph is embedded.

The second set of constraints ensures that each node v ∈ V can only host up to one VNF of the service:

f ∈F k y f v ≤ 1 (3b)
We ensure flow conservation for each node v ∈ V and each VL l = (f i , f j ) ∈ L k with:

e∈ω ( v)
x l e -e∈ω -(v)

x l e + y fi v -

y fj v = 0. ( 3c
)
The overall delay of the service is ensured with:

e∈E D e l∈L k x l e ≤ D k , ( 3d
)
and the delay between each virtual link l ∈ L k with:

e∈E D e x l e ≤ D k (3e)
3) Pricing objective function: The pricing problems feed improving columns to the master problem. Improving and non-improving columns differ in their reduced costs as the reduced cost of a variable indicates the improvement of the objective function if the variable enters the solution. The goal of the pricing problem is to find the columns with the best reduced cost. If all variables have a null reduced cost, then the CG algorithm has converged. We can obtain a variable's reduced cost formula from the dual of the master problem. If we define by π the dual values corresponding to the constraints of the primal problem (and let the exponent define the corresponding constraint), the dual problem is formulated as follows:

min k∈K n k π (2a) k + e∈E B e π (2b) e + v∈V C v π (2c) v (4a) s.t. π (2a) + e∈E δ e (γ)π (2b) e + v∈V θ v (γ)π (2c) v ≥ 1 ∀k ∈ K, ∀γ ∈ Γ k (4b)
Columns in the master problem become constraints in the dual problem and are also in exponential numbers. Similarly to the CG algorithm, the row generation algorithm starts from a reduced problem and searches for any violated constraints. Given a dual solution π, the separation problem of the dual searches an embedding that violates constraints (4b), i.e., any embedding γ such that

π(2a) + e∈E δ e (γ)π (2b) e + v∈V θ v (γ)π (2c) v < 1. (5)
Going back to the embedding sub-problem for a given service k, defined by constraints (3), the objective function becomes

min e∈E π(2b) e l∈L k B l x el + v∈V f ∈F k C f π(2c) v y vf . (6)
If the optimal value of this problem is strictly less than 1 -π (2a) k , we know that adding the corresponding embedding into the master problem will improve the solution. Otherwise, no embedding can improve the master problem.

IV. Proposed Solution

In the previous section, we addressed our placement problem using ILP and CG. We can obtain the global optimum (i.e., the maximum feasible number of placed services) with ILP and CG in an offline placement scenario. But, when it comes to the online placement, since we do not know all of the service requests in advance, we need to ensure that the placement of the current service request improves the possibility of accepting the future service requests. This can be done by optimizing a cost function which is consistent with our objective. For simplicity, we use network and service to refer to the topology graphs of the Substrate Network and the Service Request.

Complete placements (terminal states)

Pruning the branches that violate constraints BaB is one of the most popular algorithm design paradigms for solving optimization problems with exponential complexity. There are many types of constraints in the placement problem, which can be satisfied in BaB in an efficient way (the more constraints we have, the more we can prune the tree, resulting in faster search procedure). Moreover, BaB allows a complete and optimal search over the feasible solution space. Fig. 1 represents our BaB search tree. We refer to a node of the search tree as a state to differentiate it from a network node. Each state carries placement information, as well as a complete image of the network with its resources and QoS metrics. The terminal states contains a complete placement of a service over a network.

A. Expanding States

Starting at the root state of the tree, we select a VNF from the service and we generate the corresponding substates to each network node that can provide the required resources (a parent-child relationship). Each state contains a complete image of the network after placing the VNF over the corresponding node. Once a VNF is placed, we can place its outgoing and incoming VLs if both of their end-points are placed. In that case, we search for one of the shortest paths between both end-points to embed the VL, considering the required bandwidth and latency. After placing a VLs, the network image of the state is updated accordingly.

B. VNFs' Selection

At each state, we need to select a VNF to place it over the network. For this selection, we need an ordered list of the VNFs. In order to generate this list, we traverse the service in Breadth-First Search (BFS), starting from the entry point ("first" VNF) of the service (traversing in BFS allows us to have a partial placement of a connected sub-graph of the service on each state, making it possible to be evaluated against constraint violation).

The depth of the corresponding state indicates the position of the VNF in the list of the VNFs to be selected for the placement. The search tree evolves by continuing to select a VNF from the service and then placing it over the network nodes, generating their corresponding sub-states.

The root state of the search tree is located at depth zero, so the states of the first depth contain partial placements of the first VNF of the list. Consequently, the last VNF of the list is placed by the states of the last depth. Thus, if we are placing a service with N number of VNFs over a network with M number of nodes, the depth of the search tree would be N , and the maximum branching factor would be M . Note that our solution does not impose any constraints for sharing a previously placed network function between services. In case we want to share and use exclusively an already placed network function of the same type of the currently placing VNF (whether it is a PNF or a VNF). Since the already placed network function has a known network location (network node), the other branches corresponding to other network nodes are pruned (there are several works considering the VNF sharing, like [START_REF] Yue | Throughput optimization and delay guarantee VNF placement for mapping SFC requests in nfv-enabled networks[END_REF]).

The branches are pruned because of a violation of constraints like:

• Not being able to provide enough node resources for the current VNF • Not being able to find a path for the VLs connecting the currently placed and already placed VNFs because of the lack of the bandwidth • Not being able to find a path that could satisfy the overall E2E latency requirement of the service • Having placed the current VNF over a network node that we already placed another VNF of the same service over that node (anti-affinity)

C. Cost Functions

The cost function evaluates the states, to determine the next state for the expansion on each iteration of the search procedure. It is served as a measurement to allow comparing different states. Since the states represents different partial or complete placements of the service (they may have placed more or less VNFs and VLs), we need to assure that the proposed cost function can compare all of the states.

D. Search Procedure

The search procedure is an iterative procedure involving a list of the states (which we call it fringe, and it only contains the root state at the beginning of the search). On each iteration, we pop and expand the head state from the fringe, and we store the generated sub-states in the fringe. After expanding a state, we evaluate the sub-states against the constraints, and we only store the non-violating sub-states in the fringe (i.e., they are pruned from the tree).

The sequence of the states kept in the fringe specifies the traversal or the direction of the search. To traverse the search tree in DFS, the sub-states of the current state are evaluated and sorted by the cost function, then they are pushed into to the fringe (which is a stack in DFS) in-order, so that the head state (that will be popped for the expansion) has the minimum cost. In Uniform-Cost Search (UCS) traversal, the sub-states of the current state are evaluated by the cost function and they are added into to the fringe. The fringe in the UCS traversal is a sorted list, thus the head state has the minimum cost among all of the states (i.e., UCS traversal is complete and optimal).

The search procedure continues the iterations until whether we succeed to find a terminal state, or we fail by reaching a timeout.

E. Search Strategies

We define a search strategy consisting of a cost function and a search traversal, that can be applied over our BaB formulation. We propose several search strategies, by following three approaches.

1) Latency Optimized Placement: We propose the LatUCS search strategy, which performs UCS traversal, over a cost function which is defined as the sum of the latencies of the realized paths that place VLs. The placements that LatUCS find are optimal (i.e., they have the minimum feasible latency that can be realised for a service request). The idea is to investigate the effect of latency optimization on the objective of SA. It is worth mentioning that optimizing bandwidth instead of the latency would not change the results, since the bandwidth and the latency are optimized at the same time when the VNFs are placed as close as possible to the user-location and to each other.

2) Random Placement: We propose RanDFS search strategy, performing a DFS traversal, over a cost function that returns a random number. The idea is to investigate a worst-case random placement.

3) Fair Placement: We propose several search strategies to realize a fair distribution of the node resources. We propose VarUCS and VarDFS, which perform UCS and DFS traversals over a cost function defined as the variance of the available resources over all network nodes.

In addition, we propose RecUCS and RecDFS, which perform UCS and DFS traversals over a cost function defined as the average of applying reciprocal function over the available resources for only the network nodes that place the VNFs of the service request (cost = 1 ri+1 , the r i represents the available resource of the network node which places the i-th VNF, and the +1 is added to prevent division by zero). We use the cost function proposed in [START_REF] Morin | VNF placement algorithms to address the mono-and multi-tenant issues in edge and core networks[END_REF], which tries to put a high cost for placing a VNF over a network node that is short on the resources.

V. Experimentation

Our implementations are made in Java, and we use the Gurobi solve our model. All of the evaluations are executed on a PC with an Intel Core i7-3687 CPU with 8GB of RAM.

To evaluate our search strategies following our objective of SA, we begin by initializing the network nodes and links with their full capacity of the resources. Then, iteratively, we generate a service request according to the specified parameters, then we try to place it over the network using the specified strategy. If we find a placement for the requested service, we apply the placement over the We perform our evaluations on the BT-Europe and BT-North-America network topologies (selected from the Zoo Topology dataset [START_REF] Knight | The internet topology zoo[END_REF]), with respectively 24 and 36 nodes, and 74 and 152 bi-directional links. We consider 10 units of CPU for each network node and 1 unit of latency for each network link, and daisy chain topology for the service graphs (representing the topology of Service Function Chains (SFCs)). Each service contains 3 to 5 VNFs with bi-directional VLs, and each VNF requires a single unit of CPU.

The user location is fixed at the network node 12 for BT-Europe, and the node 34 for BT-North-America. The E2E latency is calculated as the sum of the latencies of the paths that place the VLs, starting from the user location and passing through each VNF and returning to the user location.

A. Latency Range

Latency is a crucial constraint, which should be set carefully. If a service requires the minimum feasible latency, we may not have many choices for the placement, and it would only be as close as possible to the user location. Similarly, If a service requires a high-enough E2E latency, so that we can place it almost wherever we want, regardless of the selected search strategy, we will end up placing almost the same number of service requests until we drain all of the network node resources. 2, all of the search strategies place almost the same number of services for the lowest feasible latency (6 units), and the highenough latency (14 units). Considering the E2E latency of 8 to 12 (which we call it effective range), LatUCS places the minimum number of services, and CG has the maximum placements. Note that the number of placed services found by the CG is on average almost twice (exactly 1.96 times, or 96% improvement) the number of placements by LatUCS. Even RanDFS can place more services than LatUCS by making random placements (1.31 times more on average).

1) Graph Representation of Latency Optimization Effect: Fig. 4 demonstrates remaining available resources of the network nodes at the end of the evaluation for BT-Europe network, placing serivces of 3 VNFs requiring 10 units of latency. We could make 30 placements using LatUCS (Fig. 4(a)), and 50 placements using VarUCS (Fig. 4(b)). In this figure the network nodes with full capacity are shown in black, the ones with no resources in white, and the others in gray-scale proportionate to their percentage of available resources. As mentioned before, by optimizing latency in LatUCS, we drain the resources around the user-location (fixed on node 12), making it impossible to place more than 30 services. By optimizing the variance of the available resources in VarUCS, we prioritize using the nodes having plenty of resources and we avoid using the nodes being short in the resources. Thus, we can reach out the resources on the nodes that are more distant, leading to place more services.

2) Random Service Requests: Until now, we considered a fixed size for the service requests during an evaluation. But, in reality, the service requests can have different sizes and different latency requirements. Now, we generate random services, and repeat these evaluations many times with different seeds of randomness. In each random experiment, we start with generating a service with a random size in a range of [START_REF] Morin | VNF placement algorithms to address the mono-and multi-tenant issues in edge and core networks[END_REF][START_REF] Gouareb | Virtual network functions routing and placement for edge cloud latency minimization[END_REF], with a random latency in the effective range based on its size, and continue placing them, until the specified strategy fails. We compare RecUCS, which performs a fair placement, with LatUCS, which perform latency optimization. As it is shown in Fig. 7 on average we can place 1.9 times more services using RecUCS instead of LatUCS.

C. Fair Placement

Although VarUCS and RecUCS achieve almost the same results by placing 1.78 and 1.83 times more services than LatUCS on average, their execution times are considerably different. Fig. 5 and Fig. 6 show the average execution time of placing the services comprised of 3 and 4 VNFs requiring different E2E latencies over BT-Europe network. As it is shown in Fig. 5, RecUCS can place the services 1.95 times faster on average than VarUCS.

D. Big Picture

1) Service Acceptance: Extensive evaluations were performed, considering both networks of BT-Europe and BT-North-America, with service requests of different sizes (3 to 5 VNFs), requiring an effective range of E2E latency, II shows the average percentage of the number of placements made by our proposed online placement strategies in comparison to our CG results which gives the maximum number of placements in an offline placement scenario.

2) Execution Time: Since the execution time of our strategies grows exponentially by increasing the service size, we represent the logarithm of the average placement execution time in Fig. 8. The complexity of our approach is clearly not polynomial (note that our problem is NP-Hard). The complexity of a our approach depends on the growth of expanded states, which is determined by the search strategy. While, the complexity of our strategies grows exponentially, they do not grow equally. If we can sort the growth of the complexity of our strategies, we can put VarUCS in the first place. RecUCS is placed between VarUCS and RecDFS/VarDFS (which have almost similar growth), and finally RanDFS.

VI. Conclusion

Although the VNF placement problem has been studied for many years, it still hot topic because of the constantly developing use-cases with new requirements and constraints. In this paper, we studied the online placement of the services on the edge networks with related constraints, and we proposed an efficient approach, capable of achieving 93% of the global optimum which can only be achieved in on offline placement.

Figure 1 .

 1 Figure 1. A sample BaB search tree, placing a service with 3 VNFs over a network with 4 nodes

Figure 2 .Figure 3 .

 23 Figure 2. Number of placed services comprised of 3 VNFs requiring different E2E latencies

Figure 4 .Figure 5 .

 45 Figure 4. Remaining available resources at the end of the evaluation by using LatUCS in (a), and VarUCS (b)

Figure 6 .Figure 7 .

 67 Figure 6. Average time of placing services comprised of 4 VNFs requiring different E2E latencies

Figure 8 .

 8 Figure 8. Logarithm of the average placement time for placing different service sizes on BT-Europe network

Table II

 II Our online strategies against global optimal(%)

	RecUCS VarUCS RecDFS VarDFS RanDFS LatUCS
	93.1	90.7	82.2	81.4	66.9	50.8


Cédric Sueur
email: cedric.sueur@iphc.cnrs.fr

Michael A Huffman

Co-Cultures: Exploring Interspecies Culture Among Humans and Other Animals

Keywords: social learning, niche construction, cultural evolution, cultural coadaptation

Highlights

1. Recent advancements in interspecies social learning underscore the fluidity of animal behaviour, revealing complex adaptations to interactions across species, including humans. 2. The concept of 'co-culture' emerges, spotlighting a dynamic, parallel or conjoint cultural evolution between different species, reshaping traditional views of cultural and evolutionary processes. 3. Studies of the parallels between human and animal use of medicinal plants in the same environment, and animal origin stories of some of the major medicinal plants in the pharmacopoeia of traditional societies around the world suggest medicinal cocultures have been evolving throughout our species' history. 4. Studies in urban animal cognition provide insights into how wildlife adapts to humanmodified environments, signalling significant shifts in behaviour and learning. 5. The dynamic field of interspecies networks highlights how complex social and ecological interconnections influence behaviours and strategies for survival and coexistence. 6. The integration of cultural and genetic coevolution in species interactions points to deeper, symbiotic relationships shaping evolutionary pathways in a shared environment.

Introduction

Cross-context responses to novelty in the animal kingdom have increasingly been the focus of study, underscoring the extensive and intricate nature of interspecies interactions. These mechanisms of social learning, transcending species boundaries, are remarkably diverse, encompassing a spectrum from explicit imitation to more nuanced forms of influence such as stimulus enhancement or social facilitation [START_REF] Goodale | Interspecific information transfer influences animal community structure[END_REF][START_REF] Avarguès-Weber | Mechanisms of social learning across species boundaries[END_REF]. This domain of animal cognition is particularly salient in the interactions between non-human animals and humans, especially pronounced in urban environments [START_REF] Lee | Animal Cognition in an Urbanised World[END_REF]. Such settings, with their unique blend of challenges and opportunities, become fertile grounds for novel forms of adaptation and interspecies interaction. A case in point is the observed behaviour of herring gulls, which have adapted to mimic human food preferences during foraging, demonstrating a form of interspecies stimulus enhancement [START_REF] Hacker | Inter-species stimulus enhancement: herring gulls (Larus argentatus) mimic human food choice during foraging[END_REF]. In a similar vein, wild mockingbirds living in urban areas have shown the capacity to differentiate between individual humans, suggesting a level of social cognition that equips these birds to adeptly navigate the complexities of human-dominated landscapes [START_REF] Levey | Wild mockingbirds distinguish among familiar humans[END_REF].

Interspecific social learning, where animals can acquire and adopt novel behaviours from other species [START_REF] Goodale | Interspecific information transfer influences animal community structure[END_REF][START_REF] Seppänen | Interspecific Social Learning: Novel Preference Can Be Acquired from a Competing Species[END_REF], demonstrates the fluidity and adaptability of animal behaviour in the face of interactions with different species. For example, research has demonstrated that wild songbirds leverage interspecific social networks to disseminate information, thereby affecting their survival strategies and behaviours [START_REF] Farine | Interspecific social networks promote information transmission in wild songbirds[END_REF]. These networks represent the complex and nuanced ways in which information flows across species boundaries, profoundly influencing the ecological and social landscapes. The emerging field of interspecies social learning, exploring how different species, including humans, exchange, learn, and co-evolve through social interactions, presents a new and exciting realm of study in anthropology and animal behaviour. This concept is supported by a plethora of studies and theories that collectively unveil the complex dynamics at play in these interspecies relationships, providing insights into the cognitive and behavioural adaptations that arise from these interactions. However, much of the existing research has focused predominantly on one species adapting and modifying its behaviour in response to another, while the process might be more accurately described as bidirectional. In this context, we introduce the concept of 'coculture' or interspecies culture.

Defining the concept of co-culture

In their pioneering work in 2005 [START_REF] Marzluff | Cultural coevolution: How the human bond with crows and ravens extends theory and raises new questions[END_REF], Marzluff and Angell introduced the concept of cultural coevolution, marking a significant milestone in evolutionary studies. Despite its significance, research on co-culture in human and animal evolution remains limited. We emphasise its importance, proposing a dynamic interplay between human culture and the environment. This coevolution involves humans and other culturally developing species. Interactions between humans and these species can accelerate cultural evolution for both. Additionally, this process occurs between non-human species as well. The concept suggests concurrent and reciprocal behavioural development between different species, visible in some populations, leading to joint cultural evolution over time (figure 1) [START_REF] Laiolo | Interspecific interactions drive cultural co-evolution and acoustic convergence in syntopic species[END_REF]. For co-culture to manifest, it is essential for the populations of both species involved occupying the same geographical space and to participate in either direct or indirect interactions.

The co-culture concept not only implies that two cultures are co-evolving in two populations sharing spaces and interacting but that the two populations are sharing a common culture. This framework aligns with and extends the concepts of co-creation and coevolution [START_REF] Herrmann-Pillath | Nature-based solutions as more-than-human art: Coevolutionary and co-creative design approaches[END_REF] in understanding how collaborative processes lead to the formation of new nature-culture structures. It also considers how these processes are intertwined with cultural and ecosystem changes over time. This reflects a dynamic and mostly symbiotic evolution of interspecies relationships, underlining the interactive and interdependent nature of these associations. Furthermore, due to their adaptable nature, cultures are prone to rapid transformations in response to the changing dynamics of social selection. This fluidity propels a cycle of dynamic interactions and fine-tuning to the local environment, highlighting the malleable and responsive character of these interspecies relationships [START_REF] Laiolo | Interspecific interactions drive cultural co-evolution and acoustic convergence in syntopic species[END_REF]. Co-culture can be seen as a specific form of niche construction, where the focus is on cultural modifications of the niche (figure 1) [START_REF] Odling-Smee | Niche construction[END_REF].

Interspecies culture cases

-

Human-animal medicinal cultures Throughout human history, the acquisition of some medicines has been attributed to the observation of wild animals' use of many different plants to treat perceived illness or otherwise alter their physiological or psychological state for positive benefits [START_REF] Álvaro | The origins of zoopharmacognosy: How humans learned about self-medication from animals[END_REF][START_REF] Huffman | Animals as a source of medicinal wisdom in indigenous societies[END_REF]. Recently this practice became a science in itself, proposed as a means of acquiring new medicinal plants for human use [14]. The study of animal self-medication has revealed many examples of shared pharmacopeia by humans and animal species sharing the same habitats [START_REF] Huffman | Ethnobotany and zoopharmacognosy of Vernonia amygdalina, a medicinal plant used by humans and chimpanzees[END_REF][START_REF] Huffman | Observations on the illness and consumption of a possibly medicinal plant Vernonia amygdalina (Del.), by a wild chimpanzee in the Mahale Mountains National Park, Tanzania[END_REF][START_REF] Petroni | Medicinal plants in the diet of woolly spider monkeys (Brachyteles arachnoides, E. Geoffroy, 1806)-a bio-rational for the search of new medicines for human use?[END_REF][START_REF] Viviano | Do porcupines self-medicate? The seasonal consumption of plants with antiparasitic properties coincides with that of parasite infections in Hystrix cristata of Central Italy[END_REF]. Not only do humans acquire animal medicines, but wild animals living in humandominated landscapes also acquire new plants of medicinal value.

-

Japanese macaques and Sika deer interactions

Direct interactions between Japanese macaques and Sika deer exemplify the evolution of interspecies relationships. Initially, these species developed close spatial proximity, benefiting mutually from their coexistence. Macaques, when feeding in trees, inadvertently drop food which becomes an energy source for deer, enhancing their foraging efficiency through gleaning, as noted by Tsuji et al. [START_REF] Tsuji | A friend in need is a friend indeed: feeding association between Japanese macaques and sika deer[END_REF]. This interaction fosters a strong cohabitation dynamic between the deer and macaques. An unusual aspect of this relationship is the deer's coprophagia, particularly around macaque sleeping sites, where they consume the macaques' faeces [START_REF] Nishikawa | Coprophagy-related interspecific nocturnal interactions between Japanese macaques (Macaca fuscata yakui) and sika deer (Cervus nippon yakushimae)[END_REF]. As this relationship evolved, some macaques have been observed grooming deer, a behaviour suggesting a deepening of their interspecies bond. On Yakushima Island, this interaction has progressed into a unique co-culture, with macaques riding on Sika deer [START_REF] Pelé | Interspecies sexual behaviour between a male Japanese macaque and female sika deer[END_REF]. Similar behaviours were observed between rhesus macaques (Macaca mulatta) and sambar deer (Rusa unicolor), indicating the potential for such complex interspecies interactions to occur in other environments and species [START_REF] Prasad | Grooming of sambar (Rusa unicolor) by rhesus macaque (Macaca mulatta) in Sariska Tiger Reserve, Rajasthan, India[END_REF]. Interestingly, these interactions have led to interspecies sexual behaviours, as observed in Yakushima and Minoo prefecture, Japan. These instances involve male macaques engaging sexually with female Sika deer and, conversely, female macaques with male deer. Such interactions highlight the capacity for highly complex and unusual behaviours to develop between different species living in close proximity. The evolution of their interactions - from shared foraging and grooming to more complex behaviours like riding and interspecies sexual activities - demonstrates a significant level of social and behavioural adaptation between two distinctly different species. They learned from each other and developed co-cultural behaviours.

-

Humans and liminal animals in urban environment

The varying behaviours of Japanese macaques towards humans, shaped by human reactions, are a clear manifestation of co-culture. In designated monkey parks, these macaques fed by keepers for tourist viewing, a practice initiated to divert them from crop fields. This feeding has led to a peaceful coexistence, with macaques positively adapting to human presence. Conversely, in areas where they are perceived as pests, aggressive human actions have resulted in macaques developing fearful or hostile behaviours towards humans. These contrasting scenarios illustrate how the same two species, humans and macaques, develop different co-cultural relationships based on their shared environment and interactions. This phenomenon of co-culture, reflecting varying degrees of pacifism or aggression, is not limited to Japanese macaques but is also evident in interactions between humans and other primate species, such as rhesus macaques and langurs in India, toque macaques and langurs in Sri Lanka, and baboons in Africa. These examples underscore the broader concept of human-wildlife coexistence in urban and anthropogenic environments, where shared behaviours and adaptations emerge from the ongoing interaction between species. These co-cultures are majority symbiotic coadaptations in our mind but can also be not symbiotic but negative as farmers and maize-stealing crows, tourists and bears or corvids [START_REF] Marzluff | Cultural coevolution: How the human bond with crows and ravens extends theory and raises new questions[END_REF].

-

Cooperative hunting

The cooperative hunting between dolphins and humans exemplifies co-culture, where both species adapt behaviours for mutual benefit [START_REF] Ansmann | Dolphins restructure social system after reduction of commercial fisheries[END_REF][START_REF] Daura-Jorge | The structure of a bottlenose dolphin society is coupled to a unique foraging cooperation with artisanal fishermen[END_REF]. In this tradition, fishermen and bottlenose dolphins collaboratively catch mullet. Dolphins herd fish towards the shore, signalling fishermen to cast nets. This synchronisation boosts both species' foraging success, reflecting a shared understanding of hunting techniques. This practice has strengthened socio-economic and cultural ties between humans and dolphins. However, it faces threats from tourism and environmental changes, highlighting the fragile nature of this interspecies relationship. This dynamic showcases the potential of interspecies collaboration and the importance of preserving such unique relationships. The interactions between honeyguides and human hunters [START_REF] Searcy | Human-wild bird cooperation[END_REF], cases of cultural cooperation between animal species such as wolves and ravens [START_REF] Stahler | Common ravens, Corvus corax, preferentially associate with grey wolves, Canis lupus, as a foraging strategy in winter[END_REF], preferential mixed bat species roosting [START_REF] Kelm | Mixed-species groups in bats: non-random roost associations and roost selection in neotropical understory bats[END_REF], mixed species group formation in callitrichine primates [START_REF] Heymann | The behavioural ecology of mixedspecies troops of callitrichine primates[END_REF], and many other species combinations [START_REF] Goodale | Mixed company: a framework for understanding the composition and organization of mixed-species animal groups[END_REF] demonstrate complex dynamics of interspecies collaborating and culturally adapting to each other's reactions and coactions over time.

-

Signal convergence

Interspecies signal convergence, as described in the context of bird species [START_REF] Laiolo | Interspecific interactions drive cultural co-evolution and acoustic convergence in syntopic species[END_REF][START_REF] Tobias | Species interactions and the structure of complex communication networks[END_REF] using similar acoustic signals in proximity, aligns closely with the concept of co-culture. In coculture, different species develop concurrent and interrelated behaviours through direct or indirect interactions. The phenomenon of signal convergence among bird species represents a form of co-culture where interspecies communication networks extend beyond individual species boundaries, leading to clustered and synchronised signals. This may also occur in other species as tamarins [START_REF] Sobroza | Convergent character displacement in sympatric tamarin calls (Saguinus spp.)[END_REF]. This convergence indicates a deeper level of social communication that transcends species-specific boundaries, highlighting a form of cocultural evolution. The birds' similar ecological niches and interactions drive this convergence, suggesting that instead of diverging to minimise interference, their signals have evolved to become more similar, effectively enhancing interspecies communication. This pattern contradicts the traditional view of signal divergence to avoid misidentification and represents a novel form of interspecies interaction and adaptation, a core aspect of coculture.

Future research perspectives

-

Interspecies social learning

Future research in interspecies social learning [START_REF] Goodale | Interspecific information transfer influences animal community structure[END_REF][START_REF] Seppänen | Interspecific Social Learning: Novel Preference Can Be Acquired from a Competing Species[END_REF] is pivotal in understanding how species, including humans, mutually influence each other's learning and behaviours in shared environments. This field challenges the notion that learning is exclusively intraspecific, as evident in studies where birds and horses learn from other species, leading to behavioural adaptations and preferences that exemplify convergent evolution. For example, migrant flycatchers adopting habitat preferences from resident tits demonstrate increased interspecies habitat overlap. A form of solitary object play, stone handling, has been documented in Japanese macaques since its emergence in the mid-1970s, and is culturally transmitted among members in the group [START_REF] Huffman | Cultured Japanese macaques: a multidisciplinary approach to stone handling behavior and its implications for the evolution of behavioral tradition in nonhuman primates. The Japanese Macaques 33[END_REF]33]. More recently, stone handling has been shown to occur under free-ranging and captive conditions in four geographically isolated macaque species (M. fuscata, M. fascicularis, M. mulatta, M. cyclopis) in the fascicularis subgroup [START_REF] Nahallage | Comparison of stone handling behavior in two macaque species: implications for the role of phylogeny and environment in primate cultural variation[END_REF][START_REF] Nahallage | Stone handling, an object play behaviour in macaques: welfare and neurological health implications of a bio-culturally driven tradition[END_REF]. A comparison of the stone handling behavioural patterns of 10 troops of Japanese macaques across Japan found intergroup variation in the number and types of behaviours exhibited [START_REF] Leca | Japanese macaque cultures: inter-and intra-troop behavioural variability of stone handling patterns across 10 troops[END_REF]. At Takasakiyama Monkey Park, two closely situated, provisioned monkey groups exhibited the highest similarity in behavioural patterns, specifically in stone handling than combinations of the other groups studied. This behaviour primarily occurs post-feeding in open areas rich in stones. The significant number of shared behaviours between these groups, more than in others, is attributed to their proximity and daily opportunities for the subordinate group to observe the dominant group's stone handling post-feeding, thereby learning and adopting more of the same behaviours.

Under human-created conditions, the possible transmission of stone behaviour to a previously non-stone handling group of rhesus macaques from a stone handling group of Japanese macaques living adjacent to them has been reported [START_REF] Nahallage | Comparison of stone handling behavior in two macaque species: implications for the role of phylogeny and environment in primate cultural variation[END_REF]. Separated by a concrete wall with limited visual access, two monkey groups could partially see and hear each other. Observations revealed that when the Japanese macaques engaged in stone handling, the rhesus macaques, seemingly influenced by the sounds, began similar activities. A comparison showed high similarity in their stone handling behaviours. Despite the lack of direct contact, this artificial setup highlights the impact of visual and auditory stimuli in fostering shared cultural traditions between species. Human-animal interactions, like human-dog play [START_REF] Merritt | Dances with dogs: interspecies play and a case for sympoietic enactivism[END_REF] or human-horse communication [START_REF] Bernauer | How do horses (Equus caballus) learn from observing human action?[END_REF], reveal co-cognitive processes emerging from collective interactions. All these examples help to elucidate the underpinning concept of co-culture.

-

Interspecies social networks

The study of interspecies social networks aligns with the concept of co-culture by examining how different species, like humans and macaques, interact and adapt their behaviours within shared environments [START_REF] Balasubramaniam | Implementing social network analysis to understand the socioecology of wildlife co-occurrence and joint interactions with humans in anthropogenic environments[END_REF]. These interactions form complex social networks where each species influences and learns from the other, leading to shared patterns of behaviour, risk taking, and resource utilisation. This mutual adaptation and learning exemplify coculture, where species co-evolve and co-create shared sociological spaces and networks [START_REF] Sueur | Mechanisms of network evolution: a focus on socioecological factors, intermediary mechanisms, and selection pressures[END_REF]. These studies demonstrate that through social networks, interspecies relationships are not just incidental but are integral to the behavioural and ecological strategies fostering a dynamic, bidirectional exchange.

-

Urban animal cognition

Studying urban animal cognition [START_REF] Lee | Animal Cognition in an Urbanised World[END_REF] in relation to co-culture involves understanding how animals adapt their cognitive abilities to thrive in urban environments, which are significantly different from their natural habitats. This adaptation is a part of the co-culture concept, where animals and humans mutually influence each other's behaviours and environment. Urbanisation presents unique challenges for wildlife, requiring animals to modify their behaviours, learning, memory, and problem-solving skills to navigate new threats and exploit novel resources. These cognitive adaptations are a response to the dynamic and often unpredictable urban landscapes. In the same way, humans adapt their urban environment to welcome or chase animals. Management-induced selection may significantly affect the adaptive or non-adaptive evolutionary processes of urban populations, yet few studies explicate the links among conflict, wildlife management, and urban evolution [41,[START_REF] Alberti | Urban driven phenotypic changes: empirical observations and theoretical implications for eco-evolutionary feedback[END_REF]. By adapting to human-modified environments and sometimes engaging with humans directly, urban animals demonstrate a co-cultural relationship, where their cognitive evolution is intricately linked to the human-shaped ecosystem. This interplay highlights the reciprocal effects and adaptive responses between humans and wildlife, central to the concept of co-culture.

-

Cultural and genetic coevolution

The concept of co-culture, where both species involved evolve and change, offers a nuanced understanding of cultural and genetic coevolution (figure 1) [START_REF] Whitehead | The reach of gene-culture coevolution in animals[END_REF]. In co-culture, both species mutually influence and adapt to each other's presence, leading to joint evolutionary changes. This process reflects a bidirectional interaction, where the cultural behaviours and genetic traits of one species shape and are shaped by those of the other with feedback between both species. Such interactions result in shared adaptations that are beneficial for both species, underscoring a symbiotic relationship rather than one dominated by control. This perspective emphasises the collaborative aspect of domestication, viewing it as a coevolutionary process rooted in mutualism, with both species playing active roles in shaping this dynamic evolutionary pathway. Co-culture extends and enriches Henrich's ideas about the collective brain and cultural evolution [START_REF] Henrich | The secret of our success: how culture is driving human evolution, domesticating our species, and making us smarter[END_REF] as well as evolution of networks [START_REF] Sueur | Mechanisms of network evolution: a focus on socioecological factors, intermediary mechanisms, and selection pressures[END_REF][START_REF] Sueur | Socioconnectomics: Connectomics Should Be Extended to Societies to Better Understand Evolutionary Processes[END_REF].

Conclusion

The exploration of co-cultures, highlighting interspecies culture among humans and animals, opens a transformative perspective on how different species co-evolve and mutually influence each other's behaviour and cognition. This concept challenges the traditional understanding of culture and learning as species-specific phenomena, emphasising the intricate dynamics of interspecies interactions in various contexts, notably in urban environments. This research underscores the significance of co-culture in understanding the dynamics of interspecies relationships, where behaviours evolve concurrently and mostly symbiotically, leading to novel nature-culture structures. The study of co-cultures is a frontier in understanding the interconnectedness of life, emphasising the need for further research in this field to unravel the complexities of these evolutionary processes and their implications for conservation, urban planning, and our broader understanding of animal cognition and behaviour. ). Adapted from [START_REF] Marzluff | Cultural coevolution: How the human bond with crows and ravens extends theory and raises new questions[END_REF], it illustrates how a spectrum of phenotypes within a population results from a combination of genetic, individually acquired, and culturally learned information. The evolution of populations is depicted through the transmission of genetic and cultural information across generations. The interaction between Population 1 of Species 1 and Population 1 of Species 2 exemplifies the impact on both natural selection, affecting inclusive fitness, and cultural selection, influencing the cultural fitness of memes. These reciprocal interactions between species' populations can drive the coevolution of genes, showcasing the complex interplay of genetic and cultural factors in evolutionary processes.

Figure 1 :

 1 Figure 1: This figure presents an advanced model integrating gene-culture coevolution with niche construction concepts, demonstrating the genetic and cultural coevolution across multiple populations (Pop1, Pop2, Pop3, etc.) of two interacting species over time (t1, t2, etc.). Adapted from[START_REF] Marzluff | Cultural coevolution: How the human bond with crows and ravens extends theory and raises new questions[END_REF], it illustrates how a spectrum of phenotypes within a population results from a combination of genetic, individually acquired, and culturally learned information. The evolution of populations is depicted through the transmission of genetic and cultural information across generations. The interaction between Population 1 of Species 1 and Population 1 of Species 2 exemplifies the impact on both natural selection, affecting inclusive fitness, and cultural selection, influencing the cultural fitness of memes. These reciprocal interactions between species' populations can drive the coevolution of genes, showcasing the complex interplay of genetic and cultural factors in evolutionary processes.


Fatima Zahra Mardi

Miloud Bagaa

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

Nabil Benamar
email: n.benamar@umi.ac.ma

Heuristic-Deep Q-Network-based Network Slicing in LoRaWAN

Keywords: Network Slicing, LoRaWAN network, Resource allocation, deep Q-Network (DQN)

Due to the increase in the number of Internet of Things (IoT) devices in recent years, managing and supporting the diversity of services is becoming more difficult. Network Slicing will be the solution, in which the network slices are tailored to the requirements of the services. In this paper, network slicing is investigated in LoRaWAN networks using the Heuristic-Deep Q-Network (H-DQN) solution that manages the network resource allocation. We propose an intra-service allocation based on the deep Q-Network (DQN) algorithm by allocating virtual resource blocks to services. In addition, the intra-service allocation is based on a heuristic algorithm that assigns the transmission probability to the LoRa nodes of each service for each block in a way to maximizes the Packet Delivery Rate (PDR) of the network while ensuring that the priority of services is maintained. Simulation results show that the proposed approach improves the PDR, and ensures prioritization among services.

I. INTRODUCTION

With the growth of the Internet of Things (IoT) technology, billions of IoT devices are connecting and communicating through standard communication protocols to accommodate networks with varying application areas [START_REF] Akpakwu | A survey on 5g networks for the internet of things: Communication technologies and challenges[END_REF]. IoT applications require an increasing number of end devices that offer low power consumption, low-cost communications, high coverage, and long-range communications [START_REF] Haxhibeqiri | A survey of lorawan for iot: From technology to application[END_REF]. To address these challenges, Low-Power Wide Area Network (LPWAN) technology has been proposed as a new set of technologies for the IoT to achieve the objectives above at once. They promise, indeed, convenient connectivity for large-scale IoT deployments.

The LoRa Wide Area Network (LoRaWAN) radio communication technology is based on LoRa, which is a spread spectrum modulation technique derived from the Chirp Spread Spectrum (CSS) technology to communicate over long distances [START_REF] Van Den Abeele | Scalability analysis of large-scale lorawan networks in ns-3[END_REF]. The CSS modulation in LoRa converts each data symbol into a chirp, which is a signal whose frequency linearly increases or decreases over time [START_REF] Nguyen | Efficient design of chirp spread spectrum modulation for low-power wide-area networks[END_REF]. LoRaWAN is an open-source standard LPWAN protocol developed by LoRa Alliance [START_REF] Alliance | Lorawan r1. 0 open standard released for the iot[END_REF]. It defines the Medium Access Control (MAC) layer specifications that build on the LoRa physical layer. In addition, the LoRaWAN network architecture has a star topology, which can support many IoT devices that can send data to the server through the gateways.

As for the MAC layer, every IoT device adopts aloha as an access protocol, whereby multiple users attempt to send data simultaneously over the same channel, which leads to increased collisions. Meanwhile, due to the increase in the number of IoT devices belonging to various applications with varying service requirements, the amount of traffic keeps rising, making it difficult to ensure even the slightest guarantee of the needs of the multiple applications.

To overcome these challenges, Network Slicing (NS) has emerged as a technological solution to support different services on the same shared physical layer through wireless resource allocation mechanisms that can be divided to meet the specific service requirements for each slice.

In our approach, we apply network slicing to the LoRaWAN transmission protocol. Therefore, this study's primary research issue is finding an allocation technique that improves the network performance and ensures the prioritization between services. The main contributions of this paper are:

• We propose a much finer allocation of resources by subdividing channels into time slots of fixed duration, allowing IoT LoRa nodes to be orchestrated on the resulting resources' blocks. • We propose an inter-service allocation based on a DQN algorithm to allocate resources' blocks to services. • According to the DQN allocation, we propose an intraservice allocation based on a heuristic algorithm to assign access probabilities to the LoRa nodes belonging to the services. The remainder of the paper is organized as follows. In Section II, we present the related work. In Section III, we discuss the system model. Section IV presents the network slicing problem. Sections V presents the proposed H-DQN solution. Section VI demonstrates the performance of the proposed solution and discusses the obtained results. Finally, section VII concludes the paper.

II. RELATED WORK

Due to the many benefits of the network slicing paradigm for improving overall system performance and meeting network quality of service standards, its practical deployment has been the topic of several evaluations.

As network slicing is a concept emerging from cellular mobile networks, its application was first focused on use cases in these networks. The author in [START_REF] Alfoudi | An efficient resource management mechanism for network slicing in a lte network[END_REF] suggested the use of network slicing in LTE Networks by proposing a network slicing resource management (NSRM) system to distribute the required resources to each slice while considering resources' isolation between multiple slices. The authors in [START_REF] Popovski | 5g wireless network slicing for embb, urllc, and mmtc: A communicationtheoretic view[END_REF] investigate the benefits of non-orthogonal sharing of RAN resources to facilitate uplink communications between a set of eMBB, mMTC, and URLLC devices and a single base station.

More recently, some works have started to explore the possibility of applying this concept in LPWANs and in particular LoRaWan networks. The authors in [START_REF] Messaoud | Online gmm clustering and mini-batch gradient descent based optimization for industrial iot 4.0[END_REF] suggested a framework for Industry 4.0, which is based on LoRaWAN and software-defined networking by proposing an online Gaussian mixture model (OGMMC) and dynamic mini-batch gradient descent (MBGD) algorithms to provide the slice allocation to the available channels. Meanwhile, the authors in [START_REF] Dawaliby | Adaptive dynamic network slicing in lora networks[END_REF] have proposed a channel allocation in LoRaWAN network employing the maximum likelihood estimation (MLE) method to estimate the resources' requirements of the different slices. Using the above estimate, the authors were able to derive a new strategy for resources allocation avoiding slice starvation while meeting the QoS requirement of the slices. The authors in [START_REF] Mardi | An efficient allocation system for centralized network slicing in lorawan[END_REF] have proposed a centralized network slicing solution in LoRaWAN relying on a coalitional game. The initial coalitions were formed using the K-Means algorithm, and the strategy consisted in moving LoRa nodes from one coalition to another in a way to increase network performance while guaranteeing the appropriate SLA for each network slice. However, the latter approach has a high convergence latency that may not be compatible with networks where changes are relatively frequent.

As the data increases, the resource allocation faces more and more difficulties to satisfy the demands of the slices. With this in mind, researchers are increasingly resorting to deep reinforcement learning. The authors in [START_REF] Messaoud | Deep federated q-learning-based network slicing for industrial iot[END_REF] have leveraged Deep Federated Q-Learning (DFQL) strategy in LoRaWAN network for the channels' assignment based on the Transmission Power (TP) and the Spreading Facor (SF) adjustments and previous agents' experiences. The aim is to improve the QoS rewards of each slice members. However, resource allocation based on channels is very limited. In fact, in such a system, we allocate to a slice one or more channels, which means that we are quickly confronted with the limit of the number of channels. Indeed, as the number of services increases, it will be complicated to satisfy the demands of the supported services. By adding the time dimension, the resources become more numerous, and the allocation of the latter can be very tight.

In contrast to the previous solutions, in this paper, we propose a new approach to ensure fair resource allocation relying on the temporal subdivision of channels in a LoRaWAN network. We have also used H-DQN algorithm to improve the Packet Delivery Rate (PDR) while ensuring the priority between different services.

III. SYSTEM MODEL

A. Network infrastructure

Without loss of generality, we consider, in the following, a scenario for LoRaWAN network slicing, consisting of one LoRa gateway GW, a set of Lora nodes N = {1, • • • , n} randomly distributed in the communication area, within the radius of this gateway, the whole forming a star topology.

We denote by B the total Resource Blocks (RBs) in the network based on time and frequency, C = {1, • • • , c} denote the set of resource channels available at the gateway in the frequency dimension, and T = {1, • • • , t} denote the set of time slots in the time dimension. Hence, we define each block as {b ij : i ∈ T, j ∈ C}, we assume that a given block b ij ∈ B is assigned to only one service s ∈ S, where S denote the set of services.

∀m, n ∈ S, B m ∩ B n = ∅. ( 1
)
where B k denotes the set of blocks assigned to the service k ∈ S.

The slicing framework consists of splitting the total resource blocks into several virtual networks (slices) by allocating blocks to different slices of the network. For this purpose, we consider that each slice is associated with a service, let denote by S = {1, • • • , s} the set of supported services. We consider that a given LoRa node n ∈ N belongs to one service, and N s denote the set of LoRa nodes within a service s ∈ S.

∀k, l ∈ S, N k ∩ N l = ∅.
(2)

N = | k∈S N k | (3)

B. Communication model

As a channel, We consider the log distance path model with shadowing [START_REF] Bor | Do lora lowpower wide-area networks scale?[END_REF]. The path loss is based on the distance d between the LoRa node n and the gateway (GW), which is given by Equation 4. For the shadowing, we assumed a normal distribution with zero mean and

σ 2 variance X σ ∼ N 0, σ 2 [12] L pl,n (d) = L pl (d 0 ) + 10Γ log d d 0 + X σ (4)
where L pl (d 0 ) is the mean path loss at the reference distance d 0 in dB, and Γ is the path-loss factor.

The received signal power P rx from the LoRa node n at the gateway, is described in Eq. 5 [START_REF] Bor | Do lora lowpower wide-area networks scale?[END_REF].

P rx = P tx,n + G -L -L pl,n (5)
where P tx,n is the LoRa node's transmit power, G the antenna power gains, L the power losses at the transmitter, and L pl,n is the path loss.

In order to guarantee a successful packet delivery from LoRa node n to the GW, the power P rx must be larger than the receiver sensitivity S rx for a specific Spreading Factor (SF) [START_REF] Bor | Do lora lowpower wide-area networks scale?[END_REF]. On the other hand, the primary cause of packet loss is collision, which occurs when at least two LoRa nodes attempt to transmit packets simultaneously. In fact, the collision is impacted by a variety of factors including carrier frequency (CF), spreading factor (SF), transmission power, and time [START_REF] Bor | Do lora lowpower wide-area networks scale?[END_REF]. The main objective here is to maximize the service's PDR by ensuring priority between competing services.

IV. PROBLEM FORMULATION

The objective of this paper is based on: 1) Inter-service allocation, which consists in assigning the total Resource Blocks (RBs) to the services. 2) Intra-service allocation, which consists in assigning a transmission probability to LoRa nodes within a service for each block b ij in order to maximize the PDR of the services, while ensuring prioritization between them.

Without loss of generality, we consider, in the following, three services, that differ in term of priority. The priority of the services is indicated by the desirable level of PDR for each service. Since the first service is the highest priority, it should have the highest PDR compared to the other services. The second service, on the other hand, has a higher priority than the third one, while the third one has the lowest priority and should have the lowest PDR rate.

To ensure the priorities of the services, the first step consists in allocating the intra-service resources in an optimized way by assigning the RBs between the services. A second step consists in assigning inter-service resources through the assignment of transmission probabilities to LoRa nodes taking into account the respect of priorities between the services with the objective of maximizing all the services' PDR.

Let X bij ,s ∈ {0, 1} a boolean decision variable, which is equal to 1 if a block b ij ∈ B is used by a service s ∈ S, otherwise, it equals to 0. Let denote by Y n,bij a continuous variable that shows the probability of a LoRa node n ∈ N s of a service s ∈ S to transmit in the block b ij .

As stated before, the objective is to maximize the PDR adopted by each service. This can be formulated as follow:

P DR s = bij ∈B X bij ,s × P DR bij ,s , ∀s ∈ S (6)
, whereby P DR bij ,s is the PDR of a service in a specific block

b ij P DR bij ,s = n∈Ns Y n,bij N s n - n∈Ns N c n n∈Ns Y n,bij N s n (7)
, whereby N s n denotes the number of packets sent by each LoRa node n ∈ N s in the block b ij and N c n is the total number of colliding packets. To this end, the assignment optimization problem is formulated as follows:

max ∀s∈S U s = P DR s × w s subject to ∀s ∈ S, ∀n ∈ N s , ∀b ij ∈ B : Y n,bij ≤ X bij ,s (8a)
∀b ij ∈ B : s∈S X bij ,s = 1 (8b) ∀j, j ′ ∈ C, ∀i ∈ T, ∀s ∈ S, N s,bij ∩ N s,b ij ′ = ∅. (8c) ∀s ∈ S, ∀n ∈ N s , ∀b ij ∈ B : Y n,bij ≤ 1 (8d) ∀s ∈ S, ∀n ∈ N s , ∀b ij ∈ B : Y n,bij ≥ 0 (8e) ∀b ij ∈ B : s∈S n∈Ns Y n,bij = 1 (8f) ∀s ∈ S, ∀n 1 , n 2 ∈ N s ∧ n 1 ̸ = n 2 : bij ∈B Y n1,bij - bij ∈B Y n2,bij ≤ ϵ (8g)
, whereby w s is a weight factor for each service. Constraint (8a) ensures that a LoRa node can only use a block if it is already assigned to its service. The constraint (8b) ensures that each block must be assigned to one and only one service. Furthermore, (8c) ensure that if a service s ∈ S is assigned to the blocks sharing the same i ∈ T in the time domain, LoRa nodes belonging to this service cannot be shared between two channels j, j ′ ∈ C in the frequency domain, i.e., the LoRa nodes in block b ij are not the same as those in the block b ij ′ . The constraints (8d) (8e) ensure the range of probability values that cannot be less than 0 or greater than 1. The probability allocation constraint (8f) implies that for each block assigned to a service, the sum of probability of the LoRa nodes in that service is equal to 1, while constraint (8g) ensures the equiprobability between LoRa nodes that belong to the same service.

The problem described above is a Mixed Integer Linear Program (MILP), which is by definition NP-hard. It can therefore only be solved for small problem instances. Therefore, we propose a suboptimal solution in the next section to deal with large network instances.

V. PROPOSED SOLUTION In this section, we propose a resource allocation solution to maximize the PDR while guaranteeing priority among services in two steps. In the first step, we dynamically allocate resource blocks to services depending on their weights based on a Deep Q-Network (DQN) algorithm. In the second step, we allocate the transmission probability for each LoRa node on each service based on a heuristic algorithm. Fig. 1 illustrates the proposed framework for resource allocation.

A. Deep Q-Network (DQN)

1) Deep Q-Network background: In Deep Q-network method, there are mainly two processes, which are the training and the testing. The training process is generated by the interactions with an environment/simulator and the agent in order to observe the agent's state and learn the weights to play the actions that give the best reward. In the testing process, for each time step, the agent observes the environment/simulator, and then accordingly chooses the action based to its trained DQN. In each episode, the environment is built by a random allocation of RBs to the services. In each time step, the agent takes an action for its current state randomly or using the action with the largest Q-value. Afterwards, it updates the allocation of resource blocks to the services. After that, the heuristic algorithm is executed to allocate the probability of the LoRa nodes belonging to a service for each block as described in section (V-B). Next, the environment/simulator provides the reward R(t) and the next state S(t + 1).

For each time step, where the DQN makes a decision, the agent's experience e t , which is defined as a tuple and e t = (S(t), a(t), R(t), S(t + 1)) and includes state transitions, actions and rewards, is stored in the replay memory M . As a result, the agent trains the network by sampling a random batch of experiences from M at each iteration in order to achieve an efficient learning.

Eventually, to calculate the loss function depicted in eq. 9. The Deep Neural Network (DNN) approximates the target Q-values, then the network weights are updated using the gradient descent to reduce the loss function.

L(w) = E (y DQN (t) -Q(s, a, w)) 2 (9)
where y DQN denotes the target Q-value and it is given as follows:

y DQN (t) = r(s, a) + γ max α ′ ∈A Q (s ′ , a ′ , w) ( 10
)
where γ is a discount factor to provide less weight to the future reward, r(s, a) is the corresponding reward to the state-action pair (s, a). for each time step do Apply the heuristic algorithm, Section (V-B) 12:

The agent Observe Reward R t and the next state S t+1 , end for 21: end for 2) Resource blocks allocation model: Based on a scenario containing a single base station with three types of services sharing the RBs, LoRa gateway is considered as the agent that manages the distribution of RBs to services. In the general case, the LoRa Network Server (LNS) will be in charge of such a function.

We define the state space, the available joint actions, the reward function as follows:

State: The LoRa gateway agent learns the environment's state at each time step t. The state at time t is defined as:

S(t) = J j=1 S j (t)
, whereby S j (t) is the state of service j at time step t, which is related to the satisfaction of the PDR, and the percentage of RBs used by each service, and it is expressed as:

S j (t) = [α t-1 j , β t-1 j ] (11)
, whereby α t-1 j refers to the satisfaction of the PDR of service j at the previous time step t, and β t-1 j refers to the percentage of resources occupied by service j at the previous time step t.

Actions: The set of all possible actions that can be taken by the LoRa gateway agent denoted as:

A(t) = (a t 1 , • • • , a t k ).
At each time step t, based on the currently observed state S(t), the LoRa gateway agent takes the appropriate action a t k ∈ A(t) that maximizes the reward R(t), and then the environment provides the next state S(t + 1). Each action includes a percentage of 5% 1 of RBs that must be transferred from one service to another. The set of available actions are:

∀s 1 , s 2 ∈ S, A(t) = ([s 1 → s 2 ], [s 2 → s 1 ], {No action taken}) (12) The action a t 1 = [s 1 → s 2 ]
consists of an exchange of RBs by transferring 5% of RBs from service s 1 to another service s 2 , while the action a t k = {No action taken} is used when no action need to be taken (i.e.,convergence of the algorithm).

Reward: After allocating RBs between services by selecting the best action, and allocating the probability of access of LoRa nodes by a heuristic algorithm as described in the next section. The environment returns a reward of the system, which is defined, to guide the gateway agent to make decisions to achieve its goal. The goal is to maximize the PDR of each service while ensuring the priority between the services, which can be expressed as follows: end for 13: end for

R(t) = max( s∈S P DR s × w s ) (13)
In this section we propose a heuristic to allocate the access probability of the LoRa nodes belonging to the different services.

At each time step t, when RBs are allocated among services by choosing the action adopting the DQN algorithm, the heuristic algorithm is designed to allocate the access probability p [n] of each LoRa node belonging to a service S i in each block b ij allocated for a service with the respect of the extremity of the probabilities as presented in constraints (8d), (8e) and the equi-probability between LoRa nodes of a service as expressed in constraint (8g). After assigning the probabilities to the LoRa nodes, the environment/simulator returns a reward to be used by the DQN, so the system is in the form of a closed loop between DQN and the heuristic to satisfy the needs of each service. The proposed heuristic is presented in algorithm .

VI. NUMERICAL RESULTS

In this section, we study the performance of our proposed method for resource allocation. The DQN was created and trained in Python 3.9 using the PyTorch framework. The DQN have two fullly connected hidden layers with 256 neurons each, as well as an input and an output layers. We used the Rectified linear unit (ReLU) as an activation function, and the Adam optimized with a learning rate β. we consider 300 episodes, each one is composed of 100 time steps, where the resource blocks (RBs) are reset in each episode.

For the simulation, the model built on LoRaSim [START_REF]Lorasim[END_REF], the LoRaWAN Slicing scenario consists of multiple services sharing the resources blocks of a LoRa gateway GW that is deployed in a square area of 10 × 10 km 2 . The LoRa nodes used are randomly assigned to services, with each LoRa node assumed to belong to one and only one service. In our architecture, we consider T = 12 with a 1H slot in the time domain. We also considered three channels for the frequency domain.

RBs are assigned to services, with each block assumed to be assigned to a single service in which the LoRa nodes belonging to it send their packets.

Table I summarizes the different parameters used in the LoRaWAN network.

A. Loss function Evaluation

In Fig. 3, we show the convergence of the loss function used to train the DQN. The loss function, as shown in Eq. 9, is formed as an indicator that the model is successfully trained. We can see that the values of the loss function reach convergence by decreasing to a small number tending to zero, which proves that the learning method improves with the

B. Packet Delivery Rate Evaluation

We notice, in Fig. 2, that the PDR of each service, decreases when the number of nodes increases. This is due to the fact that the number of transmitted packets increases, which puts pressure on the resource blocks. So that in the case of a low number of nodes, there is no huge pressure on the resources assigned to a service, which leads to a better PDR, and therefore many packets will be transferred successfully.

The results in Figures 2a,2b, and 2c indicate that the first service performs better than the second service and the second service performs better than the third service, this is due to the weight parameter that represents the priorities between services. This means that RBs are assigned to services based on maximizing the PDR while respecting the priority between services.

VII. CONCLUSION

In this paper, we propose an allocation scheme for slicing the LoRaWAN network using the H-DQN algorithm to guarantee the priority between services and improve the network PDR. First, an inter-service method was proposed using the DQN algorithm to allocate resource blocks to services. Then, an intra-service method was proposed using the Heuristic algorithm to allocate access probabilities to the devices they own within the services. Simulation results showed that the proposed approach improves the Packet Delivery Rate (PDR) while guaranteeing prioritization between services.

Fig. 1 :

 1 Fig. 1: H-DQN solution

Algorithm 1

 1 DQN Algorithm. Input: Agent Gateway, Environment simulator. Output: Trained DQN 1: The generation of the network parameters. 2: The initialization of the agent's DQN hyper-parameters. 3: for each episode do

8 :

 8 Choose action a t 9: a t = a random action with probability ϵ max a Q * (s t , a; w)

13 :

 13 Store the experience e t in replay memory M , 14: if batch size then 15: samples a random batch of experiences from M , 16:Calculate an estimated Q-value Q(s, a)

B 4 : 9 :

 49 . Proposed heuristic Algorithm Heuristic Algorithm. Input: Allocated Resource Blocks based on DQN. Output: Allocated probability of access to LoRa nodes.1: function PROBABILITY(N ) 2: length = len(S i ) for each LoRa node n ∈ S i to N do for each time step t do 10: for each block b ij do

3 Fig. 2 :Fig. 3 :

 323 Fig. 2: Packet Delivery Rate Evaluation

TABLE I :

 I Simulation Parameters

	Parameters name	Value
	Simulation time	3600000 ms
	Duration of time slot (T)	300000 ms
	Number of LoRa Gateway	1
	Carrier Frequency (CF) / Channels number	868 MHz / 3
	Transmission Power (TP)	14 dBm
	Spreading Factor (SF)	{7,8,9,10,11,12}
	Bandwidth (BW)	125 KHz
	Coding Rate (CR)	4/5
	Learning rate β	0.0001
	Discount factorγ	0.99
	Mini batch size	64

A smaller percentage could be considered, but with the risk of a slower convergence.

ACKNOWLEDGEMENTS

This work was partially supported by the Intelligentsia, ANR project.