Eleonora Tagliabue
email: eleonora.tagliabue@univr.it

Marco Piccinelli

Diego Dall'alba

Juan Verde

Micha Pfeiffer

Riccardo Marin

Stefanie Speidel

Paolo Fiorini

Stéphane Cotin

Intra-operative Update of Boundary Conditions for Patient-specific Surgical Simulation

Keywords: Intra-operative model update, Boundary conditions, Biomechanical modeling

Patient-specific Biomechanical Models (PBMs) can enhance computer assisted surgical procedures with critical information. Although pre-operative data allow to parametrize such PBMs based on each patient's properties, they are not able to fully characterize them. In particular, simulation boundary conditions cannot be determined from preoperative modalities, but their correct definition is essential to improve the PBM predictive capability. In this work, we introduce a pipeline that provides an up-to-date estimate of boundary conditions, starting from the pre-operative model of patient anatomy and the displacement undergone by points visible from an intra-operative vision sensor. The presented pipeline is experimentally validated in realistic conditions on an ex vivo pararenal fat tissue manipulation. We demonstrate its capability to update a PBM reaching clinically acceptable performances, both in terms of accuracy and intra-operative time constraints.

Introduction

An up-to-date Patient-specific Biomechanical Model (PBM) of the surgical scenario can bring benefits to the surgical practice in several ways. In computerassisted interventions, such PBM can guide surgeons towards the structures of interest, which might be hidden from the partial view available intra-operatively [START_REF] Mendizabal | Data-driven simulation for augmented surgery[END_REF]. A further application is in the field of autonomous robotic surgery, where a PBM of the current surgical condition is required for verification of the robotic actions in a controlled environment, before execution [START_REF] Choi | On the use of simulation in robotics: Opportunities, challenges, and suggestions for moving forward[END_REF]. Moreover, PBMs can play the role of virtual sensors to estimate interaction forces between instruments and tissues when direct force measurement systems are not available, and provide a feedback to the surgeon [START_REF] Haouchine | Vision-based force feedback estimation for robot-assisted surgery using instrument-constrained biomechanical threedimensional maps[END_REF]. The predictive power of such PBMs highly relies on their accurate parametrization, which has to be tailored to each new patient. Patient-specific geometry and tissues' elastic properties can be extracted from pre-operative anatomical images or using ad-hoc modalities such as elastographic techniques, allowing to build a PBM with personalized properties [START_REF] Galbusera | Image-based biomechanical models of the musculoskeletal system[END_REF]. However, information available before the intervention is often insufficient to fully characterize PBMs to the extent required to achieve clinically accepted accuracy. In particular, there is usually no way to delineate the adhesions between neighboring organs from pre-operative data. Such adhesions define simulation Boundary Conditions (BCs), thus they are key to obtain an accurate model [START_REF] Miller | On the prospect of patient-specific biomechanics without patientspecific properties of tissues[END_REF][START_REF] Peterlik | Image-driven stochastic identification of boundary conditions for predictive simulation[END_REF][START_REF] Nikolaev | Estimation of boundary conditions for patient-specific liver simulation during augmented surgery[END_REF]. As a consequence, reliable BCs can be estimated only from data that are collected intra-operatively [START_REF] Peterlik | Image-driven stochastic identification of boundary conditions for predictive simulation[END_REF][START_REF] Nikolaev | Estimation of boundary conditions for patient-specific liver simulation during augmented surgery[END_REF][START_REF] Mendizabal | Data-driven simulation for augmented surgery[END_REF].

The problem of intra-operative estimation of BCs has been tackled by only few works. In [START_REF] Plantefève | Patient-specific biomechanical modeling for guidance during minimally-invasive hepatic surgery[END_REF][START_REF] Nikolaev | Estimation of boundary conditions for patient-specific liver simulation during augmented surgery[END_REF], the position of BCs is initialized based on statistical atlases, leading to a method which is not robust to inter-patient variations. Other approaches [START_REF] Peterlik | Model-based identification of anatomical boundary conditions in living tissues[END_REF] propose to update BCs exploiting additional intra-operative sensors, undermining their direct applicability to the standard clinical practice. In [START_REF] Peterlik | Image-driven stochastic identification of boundary conditions for predictive simulation[END_REF][START_REF] Nikolaev | Estimation of boundary conditions for patient-specific liver simulation during augmented surgery[END_REF], authors propose to use stochastic filters to estimate the elasticity of the hepatic ligaments, exploiting intra-operative observations of the tissue state. However, the filters' inference time strongly depends on their parameters initialization, which is highly sensitive to each patient's properties, possibly introducing a degradation in the performances from case to case.

A recent research trend has focused on the usage of Deep Neural Networks (DNNs) to update a biomechanical model based on intra-operative data [START_REF] Mendizabal | Physics-based deep neural network for real-time lesion tracking in ultrasoundguided breast biopsy[END_REF][START_REF] Brunet | Physicsbased deep neural network for augmented reality during liver surgery[END_REF][START_REF] Pfeiffer | Learning soft tissue behavior of organs for surgical navigation with convolutional neural networks[END_REF][START_REF] Pfeiffer | Non-rigid volume to surface registration using a data-driven biomechanical model[END_REF][START_REF] Saeed | Prostate motion modelling using biomechanically-trained deep neural networks on unstructured nodes[END_REF]. These works have shown that DNNs can learn biomechanical models even when trained with synthetic data only, while guaranteeing very low inference time. Furthermore, Pfeiffer et al. [START_REF] Pfeiffer | Learning soft tissue behavior of organs for surgical navigation with convolutional neural networks[END_REF][START_REF] Pfeiffer | Non-rigid volume to surface registration using a data-driven biomechanical model[END_REF] demonstrated that DNNs can also learn a surface representation, thus being able to handle any input geometric model. However, all these works have focused on the estimation of the full 3D displacement field to accomplish the task of intra-operative registration, either without taking advantage of any PBM parametrization inferred from preoperative data or assuming that BCs are fixed and a-priori known.

In this work, we present a complete pipeline that allows to continuously update an existing PBM by estimating model BCs, starting directly from the raw intra-operative point cloud of the deforming anatomy provided by a vision sensor and without relying on any a-priori assumption about their location. We conduct an experimental validation of the complete framework on an ex vivo human model, including the anterior renal fascia (Gerota's fascia), the pararenal adipose tissue and the kidney. The manipulation of these tissues is a key step during most of surgical kidney procedures (most importantly during partial nephrectomy). Obtained results demonstrate that the proposed pipeline is able to update a real PBM, respecting clinically acceptable requirements both in terms of accuracy and timing, thus allowing to account for possible intra-operative changes of the BCs caused by surgical manipulations.

Method

In order to provide an up-to-date PBM that continuously follows the current surgical scenario, we rely on a framework involving two independent processes which run concurrently. The first process is entirely dedicated to a physics-based simulation of the surgical environment capable of real-time performances [START_REF] Taylor | High-speed nonlinear finite element analysis for surgical simulation using graphics processing units[END_REF]. Such simulation leverages the PBM created from pre-operative data, characterized by both the undeformed 3D geometry of the anatomy and its known mechanical properties. The second process is devoted to a strategy for updating PBM parametrization during the intervention, starting from intra-operative sensor data. In this work, we focus on this second task. In particular, we present a pipeline to update simulation BCs from the 3D point cloud of the surgical scene with a very short latency1 . This allows the simulation to continuously reflect the changes introduced in the environment by surgical manipulations (Fig. 1). Pre-processing The acquired raw 3D point cloud passes through an initial pre-processing step. First, both color and spatial segmentation are performed to extract the current view of the deformed Intra-Operative Surface (IOS) from the full anatomical point cloud. The extracted IOS is then rigidly aligned to its corresponding portion of the PBM, based on geometric features and known spatial relations estimated at the beginning of surgery.

Displacement estimation

We calculate the Intra-Operative Displacement field (IOD) which maps each point in the IOS to its corresponding one on the undeformed PBM. To achieve this, we estimate a correspondence with a nearestneighbor pairing between the point cloud and the PBM, and we refine it using the ZoomOut method [START_REF] Melzi | Zoomout: spectral upsampling for efficient shape correspondence[END_REF]. This non-rigid approach is entirely intrinsic, promotes isometric solutions (i.e., correspondences that preserve the surface distances between the points), and has approximately linear complexity. Thus, ZoomOut guarantees a trade-off between accuracy and timing, making it ideal for realtime precision surgical operations, where we assume the folding and bending of the surface preserves surface geometry (i.e., boundaries and metric) without introducing dramatic stretching.

Voxelization In order to exploit convolutional filters, input information is converted into a grid-like volume of dimension 64 × 64 × 64 and side length 30 cm. The PBM is encoded into the grid using its signed distance field and the IOD through a Gaussian interpolation.

BANet The boundary condition update is performed by BANet, a DNN estimating at which points a given deformable tissue is attached to the surrounding environment [START_REF] Tagliabue | Data-driven intra-operative estimation of anatomical attachments for autonomous tissue dissection[END_REF]. BANet has been validated on phantom data with simple geometry, but has never been applied to a real PBM and within a realistic clinical situation. BANet is a U-shaped network, which consists of an encoding and a decoding path. The former contains four stages of downsampling, each reducing the spatial resolution by half, resulting in a bottleneck layer which is 4 3 grid cells in size. This allows information to travel across the spatial domain. Additional skip-connections enable the network to carry fine detail forward where necessary. To ensure a high inference speed, downsampling and upsampling are done via simple MaxPool and interpolation functions. The network is trained to approximate the function f (P BM, IOD) = AP , where AP is the binary voxel field representation of the attachment points. The training dataset is composed of synthetic samples representing adipose tissues PBMs (with different random geometries and mechanical parameters) and annotated with randomly extracted BCs. In this work, we use the publicly available implementation of BANet with the provided pre-trained weights [START_REF] Tagliabue | Data-driven intra-operative estimation of anatomical attachments for autonomous tissue dissection[END_REF].

PBM update Finally, BANet-estimated BCs are mapped from grid space to the original PBM space, giving the Intra-Operative Model (IOM). This step completes the proposed pipeline, and the obtained IOM is used to update the intra-operative simulation running in the synchronous process.

Experiments and Results

Validation of the presented method is carried out on ex vivo pararenal fat tissue manipulation (Fig. 2a). Tissue's PBM is initialized with the specimen 3D geometry, generated from manual segmentation of its CT scan, and discretized with 65,538 tetrahedral elements. Its biomechanical properties are selected to be aligned with those observed for adipose tissues (i.e., St Venant Kirchhoff material with Young's modulus 3 kP a and Poisson ratio 0.45) [START_REF] Alkhouli | The mechanical properties of human adipose tissues and their relationships to the structure and composition of the extracellular matrix[END_REF]. Leveraging on the constructed PBM (Fig. 2b), it has been also possible to generate a synthetic dataset based on a real anatomical model. Such dataset allows us to evaluate method performances within a scenario which is influenced neither by sensor noise nor by inaccuracies introduced by ZoomOut, since the IOD can be estimated by directly matching corresponding points in the deformed and the undeformed configurations.

The capability of the method to update the PBM such that the virtual environment resembles the current tissue condition is assessed by comparing the deformed state in the simulated environment with the available ground truth deformed configuration. The deformed state in the virtual environment is obtained by performing a finite element (FE) simulation where model BCs are defined by the proposed approach and computing the Root Mean Squared Error (RMSE) between the simulated and the ground truth configurations. A stateof-the-art direct solver [START_REF] Schenk | Solving unsymmetric sparse systems of linear equations with Pardiso[END_REF] is used together with an iterative Newton-Raphson method to solve the non-linear system of equations in the static domain, within the open-source SOFA framework [START_REF] Faure | Sofa: A multi-model framework for interactive physical simulation[END_REF]. The obtained simulation result is weakly sensitive to possible inaccuracies in the selected mechanical parameters, since the driving input to the simulation is represented by a displacement (i.e., the same displacement which is applied to the corresponding ground truth configuration) [START_REF] Miller | On the prospect of patient-specific biomechanics without patientspecific properties of tissues[END_REF].

Synthetic adipose tissue manipulation

A synthetic dataset of 600 samples of adipose tissue manipulation is generated following the same training data generation strategy used in [START_REF] Tagliabue | Data-driven intra-operative estimation of anatomical attachments for autonomous tissue dissection[END_REF], but keeping the considered PBM fixed (Fig. 2b). The median RMSE (interquartile range IQR) calculated on all the 3D model points between the deformed IOM and the corresponding reference sample is 1.4 (0.7 -3.2) mm, indicating an overall good matching (Fig. 3a). Since ground truth BCs are available for the synthetic dataset, we further assess prediction accuracy by computing the Dice coefficient (DSC) [START_REF] Taha | Metrics for evaluating 3d medical image segmentation: analysis, selection, and tool[END_REF], which measures the overlapping area between ground truth and predicted BCs. Median (IQR) value for DSC is 0.51 (0.40 -0.60). Fig. 3b andc show that the network is challenged by the complex geometry and fails to accurately identify BCs when they are distributed along the sharp edges of the mesh, especially when the amount of visible surface is very small and does not capture the region undergoing the highest deformation. However, when the visible surface captures the region with greatest deformation (Fig. 3b), BANet is able to provide a plausible prediction, which leads to a precise matching between the simulated and the reference configuration. Upper row: ground truth deformed configuration (green) and simulated deformed configuration obtained when using predicted BCs (yellow), with the considered visible surface (light blue). Pink mesh represents the deformed configuration when BCs are unknown, thus undefined. Lower row: ground truth BCs (green) and predicted BCs (red) in grid space. (a) Good overlap between simulated and ground truth configurations (RMSE=1.6 mm), due to good prediction accuracy (DSC=0.68). (b) Good overlap (RMSE=1.7 mm) is possible even if prediction is not the same as the ground truth one (DSC=0.09). (c) High RMSE (14.6 mm) is due to an inaccurate prediction (DSC=0.02), when visible surface does not provide enough information about tissue state.

Real adipose tissue manipulation

The presented pipeline is employed to update the PBM during ex vivo pararenal tissue manipulation. An expert surgeon is asked to grasp the human tissue with a laparoscopic tool from four pre-defined points, whose position is known in the 3D model space thanks to CT-visible markers, and lift it to the maximum reachable extent that prevents tissue tearing (Fig. 2a). After pulling the tissue from all the points, the surgeon introduces a change in BCs by dissecting some tissue adhesions, and repeats the acquisitions. Acquired data are relative to three different initial states (i.e., two dissection stages); however, it has not been always possible to lift from all the grasping points due to excessive tissue damage introduced by dissection. Intra-operative point clouds capturing deformed tissue states are acquired through an Intel RealSense D435 RGB-D camera. Collected images allow to extract the displacement applied to the tissue by the surgeon, by tracking a STag marker attached to the instrument (Fig. 2a) [START_REF] Benligiray | Stag: A stable fiducial marker system[END_REF]. To evaluate the presented method, point clouds at regular lifting steps of 10 mm are extracted and passed through the complete pipeline described in Section 2. As soon as a new estimate of BCs is available, we perform a FE simulation to the obtained IOM applying the same input displacement applied by the surgeon. We then calculate the RMSE between each point in the acquired point cloud and its corresponding one, as estimated by ZoomOut, in the deformed IOM.

Table 1 reports the average RMSE over 10 runs of the whole pipeline, relative to the error at rest (average 3.62 mm, which includes contributions of segmentation and registration errors) at increasing pulling levels. The reason why we report results over multiple runs is that we rely on an approximate nearest neighbour for ZoomOut to minimize the computational overhead, which might however introduce some differences between different runs. The average time required to update the synchronous PBM simulation is 1.44 ± 0.14 s (with an average of 0.039 s dedicated to pre-processing, 1.39 s to displacement estimation, and 0.013 s to BANet), tested on a workstation with an AMD Ryzen7 3700X CPU and NVIDIA RTX 2070 SUPER graphics card. This update rate allows to provide feedback to the operating surgeon and/or the autonomous system based on a model reflecting the changes in clinical settings with a latency compatible with standard surgical workflows. Average RMSEs remain below 5 mm in almost all the cases, which is aligned with the accuracy levels required for model-guided intra-operative applications in the context of minimally-invasive surgery [START_REF] Pfeiffer | Non-rigid volume to surface registration using a data-driven biomechanical model[END_REF][START_REF] Brunet | Physicsbased deep neural network for augmented reality during liver surgery[END_REF][START_REF] Mendizabal | Data-driven simulation for augmented surgery[END_REF]. Furthermore, obtained RMSEs are significantly lower than the ones achieved when BCs are unknown, thus they cannot be defined and the simulation remains unconstrained (last column in the table). In general, RMSE increases with increasing deformation. This might be due to the fact that the high deformations cause poor surface estimation from [START_REF] Sharp | A laplacian for nonmanifold triangle meshes[END_REF], which assumes that the point cloud already represents the desired surface without noise or topological artifacts. In such case, ZoomOut promotes a disturbed correspondence (i.e., isometric to a wrong surface). To improve this step, investigating the point cloud denoising techniques seems a promising future direction. This further motivates the worse RMSE values obtained in correspondence to grasping point B, whose point clouds are partially occluded by the surgical tool.

Discussion and Conclusion

In this work, we have presented a complete pipeline that allows to update a patient-specific pre-operative model for surgical assistance, based on data acquired during the intervention. Validation experiments have shown that the presented pipeline can be used to successfully update a PBM exploiting data coming directly from intra-operative sensors, while respecting both accuracy and time constraints compatible with standard minimally-invasive surgical applications. The quality of the final result is influenced by the different sources of errors that are introduced throughout the various stages of the pipeline, from an imprecise initial rigid alignment, to the presence of sensor noise and inaccurate computation of corresponding points. In future works, we plan to improve the pre-processing stage, for instance by reconstructing the point cloud from the stereo-endoscope view [START_REF] Allan | Stereo correspondence and reconstruction of endoscopic data challenge[END_REF]. Inaccurate surface matching can be addressed by either letting the network implicitly solve the surface correspondence problem as in [START_REF] Pfeiffer | Non-rigid volume to surface registration using a data-driven biomechanical model[END_REF], by providing salient points extracted from camera view to ZoomOut, or by improving surface estimation [START_REF] Williams | Deep geometric prior for surface reconstruction[END_REF]. In particular, relying on DNN to directly solve for surface correspondences seems promising to further improve the time performances of the current implementation, where ZoomOut is responsible of the main computational overhead. By providing an update of model BCs with a very short delay, our method could handle situations with dynamically changing BCs, for example involving dissection, sutures removal or topological changes.

However, due to the fact that the surgical environment is intrinsically evolving in time and the network has shown to benefit from the availability of more informative input data, we expect that the robustness of the prediction will be improved by considering time dynamics and we will tackle this in future works.

Fig. 1 .

 1 Fig. 1. Overview of the pipeline to update PBM boundary conditions. (a) Initial data: IOS and PBM; (b) rigidly aligned data; (c) estimated IOD, where brighter color is associated with highest displacement; (d) voxelized representation, where grid cells are colored based on the signed distance field from PBM surface; (e) estimated BCs in grid space; (f) PBM annotated with estimated BCs, giving the intra-operative model IOM.

Fig. 2 .

 2 Fig. 2. (a) An example tissue manipulation. The surgeon manipulates the pararenal fat and anterior fascia with a laparoscopic instrument, grasping from point A. Point clouds of the tissue state are acquired with an RGB-D camera capturing the scene from the same perspective of the picture. (b) The PBM of the ex-vivo perinephric tissue. The position of the grasping points is marked with a letter and a green circle.

Fig. 3 .

 3 Fig. 3. Results on the synthetic dataset considering input displacements above 25 mm.Upper row: ground truth deformed configuration (green) and simulated deformed configuration obtained when using predicted BCs (yellow), with the considered visible surface (light blue). Pink mesh represents the deformed configuration when BCs are unknown, thus undefined. Lower row: ground truth BCs (green) and predicted BCs (red) in grid space. (a) Good overlap between simulated and ground truth configurations (RMSE=1.6 mm), due to good prediction accuracy (DSC=0.68). (b) Good overlap (RMSE=1.7 mm) is possible even if prediction is not the same as the ground truth one (DSC=0.09). (c) High RMSE (14.6 mm) is due to an inaccurate prediction (DSC=0.02), when visible surface does not provide enough information about tissue state.

Table 1 .

 1 RMSE between ground truth point clouds and their corresponding points in the virtual environment when using predicted BCs, at increasing deformation levels[mm]. Acquisitions are grouped by grasping point (A, B, C, D) and initial tissue state[START_REF] Alkhouli | The mechanical properties of human adipose tissues and their relationships to the structure and composition of the extracellular matrix[END_REF][START_REF] Allan | Stereo correspondence and reconstruction of endoscopic data challenge[END_REF][START_REF] Benligiray | Stag: A stable fiducial marker system[END_REF]. Reported errors are relative to the error at rest and represent the average over 10 runs of the entire pipeline. Missing values are due to failures in instrument tracking. Last column reports the RMSE obtained when no BCs are defined in the virtual environment (MeanUC ).Grasp State 10 mm 20 mm 30 mm 40 mm 50 mm Mean Std MeanUC

	A	1 2	--	0.94 -	1.06 1.42	1.28 2.42	6.81 2.75	2.52 2.48 24.93 2.20 0.65 31.99
		1	2.96	6.75	-	-	-	4.86 1.90 13.02
	B	2	5.05	9.91	11.47	-	-	8.81 2.84 27.06
		3	3.27	11.71	9.12	3.92	-	7.01 3.60 31.53
		1	-	1.65	2.49	-	-	2.07 0.42 18.66
	C	2	5.30	2.54	3.84	-	-	3.89 1.42 14.23
		3	2.59	4.61	6.93	10.76	-	6.22 3.04 18.79
		1	1.07	-	-	-	-	1.07 0.00	7.72
	D	2	-	1.32	1.57	3.98	5.25	3.03 1.71 19.76
		3	1.51	2.28	3.57	-	-	2.45 0.85	7.29
	Mean		3.11	4.64	4.61	4.47	4.94
	Std		1.50	3.90	3.52	3.32	1.80

Project available at https://gitlab.com/altairLab/banet

Acknowledgements Authors would like to thank the preclinical research staff at IHU Strasbourg for their assistance and support during the experiments. This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No. 742671 "ARS"), from French state funds managed within the "Plan Investissements dAvenir" and from the ANR (reference ANR-10-IAHU-02).


Jean-Baptiste Bordier
email: jean-baptiste.bordier@irisa.fr

Christopher Merlhe
email: christopher.merlhe@irisa.fr

Philippe Fabian
email: philippe.fabian@univ-eiffel.fr

Sébastien Baey
email: sebastien.baey@lip6.fr

Dylan Garnaud
email: garnaud.dylan@orange.fr

Keryann Bussereau
email: keryann.bussereau@soprasteria.com

Erwan Livolant
email: erwan.livolant@boost-conseil.com

Cédric Gueguen
email: cedric.gueguen@irisa.fr

Buffer Occupancy and Link State Opportunistic Routing for Wireless Mesh Networks

Keywords: Wireless Network, Multihop Network, Opportunistic Routing, Multipath Fading, Quality of Service

published or not. The documents may come

I. INTRODUCTION

Routing in wireless multihop networks raises a lot of interest. Advances in this field will open the path to new features in ad-hoc and hybrid networks. Using mobile terminals as relays for instance will allow to offload macro cells relying on satellite cells [START_REF] Gueguen | Incentive scheduler algorithm for cooperation and coverage extension in wireless networks[END_REF]. Routing is also key to support the development of multimedia applications. These real-time applications have indeed stringent quality of service constraints, in particular in terms of delay [START_REF] Gonzalez | Resource allocation for block-based multi-carrier systems considering qos requirements[END_REF], and also require improved user connectivity when offered in a mobile context.

An efficient routing solution should be designed to identify the optimal path, that is the set of links that provide overall the best throughput and lowest latency. It is widely acknowledged that on a given path, the link with minimal throughput strongly jeopardizes the global Quality of Service (QoS) and Quality of Experience (QoE). As a result, many papers define the optimal path as the one whose bottleneck is the least constraining. However, if routing protocols build their decision only considering the path bottleneck value, the probability to over-exploit the network best path is high and could result in a high packet delay risk. In addition, the lack of load balancing will induce low system link profitability reducing the global system capacity. Numerous solutions have been proposed for wired networks. However, these proposals are not applicable to wireless networks because of the particularities of radio wave propagation. These require adaptive routing strategies that are able to dynamically take into account the variability of the link throughput as well as the router load, resulting in the continuous selection of a high throughput and low loaded path.

A significant physical phenomenon observed in wireless networks is multipath fading. Since propagation is not guided, the radio waves emitted by an antenna propagate in all directions, encounter different obstacles and some of them will eventually recombine at the receiving antenna. As those waves travel on paths with different lengths, they reach the receiving antenna with a different phase. Depending on how much in phase (or out-of-phase) these sub-signals arrive, constructive or destructive interference occurs. If sub-signals are in phase, constructive interference produces a strong received signal which may be harnessed using a high order modulation to obtain a high short term throughput. If signals are close to phase opposition, destructive interference yield poor received signal power and result in low short term throughout. As a consequence of this multipath fading phenomenon, channel state varies quickly across time, every few milliseconds [START_REF] Goldsmith | Wireless Communications[END_REF]. On a longer time scale, the channel state also varies due to path loss and shadowing if nodes are mobile. The achievable throughput is thus affected because the modulation scheme of the transmission must be adapted. In the following, we define the short term Link State Information (LSI short ) as the measure of the rapidly-changing throughput values due to multipath fading. LSI short values are computed on a short time scale, as opposed to average Link State Information (LSI avg ) which is the arithmetic mean of the short term values collected over a larger time scale.

In order to take multipath fading into account, algorithms based on metrics like hop number or the mean Signal to Noise Ratio (SNR) are not efficient because they identify the mean best path in the best case. For instance, in Optimized Link State Routing (OLSR), the rate at which routing information is sent between nodes is in the order of the second [START_REF] Clausen | Rfc7181: The optimized link state routing protocol version 2[END_REF][START_REF] Ferronato | Analysis of routing protocols olsr, aodv and zrp in real urban vehicular scenario with density variation[END_REF]. As aforementioned, multipath fading happens on a much shorter time scale. The mean best path is not systematically the short term best path because the latter changes quickly over time. This is why the well-known Ad-hoc On-demand Distance Vector (AODV) [START_REF] Das | Ad hoc On-Demand Distance Vector (AODV) Routing[END_REF][START_REF] Singh | Mobility-aware relay selection in 5g d2d communication using stochastic model[END_REF] is also non optimal in terms of throughput. The path selected by AODV is the one providing the best throughput at a given time, overlooking variations of radio conditions and leading to sub-optimal performance.

Recent technical advances give access to measures of the instantaneous radio propagation conditions, like LSI short . This allows to design a solution that adapts the path between a source and a destination, as a function of multipath fading, taking inspiration from advances in scheduling protocols [START_REF] Wong | Multiuser OFDM with adaptive subcarrier, bit, and power allocation[END_REF][START_REF] Viswanath | Opportunistic beamforming using dumb antennas[END_REF][START_REF] Gueguen | A fair opportunistic access scheme for multiuser OFDM wireless networks[END_REF]. For instance, if a node is experiencing strong interference at some point, an opportunistic algorithm can decide to route traffic to an alternative node instead.

In the literature, opportunistic routing refers to packet forwarding solutions based on geolocalisation [START_REF] Costantino | Losero: a locality sensitive routing protocol in opportunistic networks[END_REF] or algorithms that use an increased number of nodes to transmit data [START_REF] Biswas | Exor: Opportunistic multi-hop routing for wireless networks[END_REF]. The first aims at taking profit of user locations to gain efficiency in the routing of packets. This can benefit to the network coverage but without any delay bound guarantee. The second exploits the radio links diversity to increase the overall communication reliability. Extremely Opportunistic Routing (ExOR) [START_REF] Biswas | Exor: Opportunistic multi-hop routing for wireless networks[END_REF] is an emblematic instance of this family of solutions. ExOR combines MAC and routing functionalities. A first packet is sent to multiple nodes of the multihop wireless networks. Based on this transmission experience, the best node is then elected to forward a batch of packets. With this method, long distance but lossy links are advantageously exploited while it would have been discarded by classic routing algorithms. Performance evaluation over a large 802.11 testbed shows significant throughput gain for most links using ExOR compared to classic routing solutions. A major drawback is however traffic increase and subsequent congestion in the network due to packet transmission duplication. This was not properly evaluated in the testbed. Other opportunistic routing proposals include [START_REF] Athanasopoulou | Back-Pressure-Based Packet-by-Packet Adaptive Routing in Communication Networks[END_REF] and [START_REF] Mao | Energy-efficient opportunistic routing in wireless sensor networks[END_REF]. In [START_REF] Athanasopoulou | Back-Pressure-Based Packet-by-Packet Adaptive Routing in Communication Networks[END_REF], a back pressure adaptive algorithm is proposed. Routing and scheduling components are decoupled in the algorithm by designing a probabilistic routing table that is used to route packets per destination queues. [START_REF] Mao | Energy-efficient opportunistic routing in wireless sensor networks[END_REF] minimizes the overall network energy consumption working on a smart management of the forwarder list with priorities. Static and dynamic transmission power management strategies are investigated to elaborate a performant energy opportunistic routing policy. [START_REF] Darehshoorzadeh | Modeling and comparison of candidate selection algorithms in opportunistic routing[END_REF] proposes a generic Markov model to evaluate candidate selection algorithms. The necessary inputs are the candidate list of each node, the link delivery probability, and the maximum number of re transmissions in each node.

All these routing algorithms were primarily designed for ad hoc networks and base their decisions on average SNR values, assuming a relatively SNR stability in the medium term time scale. However, a substantial gain may be drawn taking into account the short term SNR fluctuations that occur in wireless networks. We think that a fully "opportunistic" routing solution in the sense of "opportunistic" scheduling solutions, taking inspiration in Maximum Signal to Noise Ratio (MaxSNR) [START_REF] Wong | Multiuser OFDM with adaptive subcarrier, bit, and power allocation[END_REF][START_REF] Ostovari | Cooperative internet access using helper nodes and opportunistic scheduling[END_REF], Proportional Fair (PF) [START_REF] Viswanath | Opportunistic beamforming using dumb antennas[END_REF][START_REF] Liu | Analysis of proportional fair scheduling under bursty on-off traffic[END_REF] or Weighted Fair Opportunistic (WFO) [START_REF] Gueguen | A fair opportunistic access scheme for multiuser OFDM wireless networks[END_REF], has a high potential. Taking profit of SNR short term variations in wireless networks, these resource allocation algorithms optimize the system capacity, with a strong impact on packet delay and user satisfaction. The potential of fully opportunistic routing is argued in [START_REF] Chen | Opportunistic routing and scheduling for wireless networks[END_REF] through a preliminary theoretical study. A global framework is proposed here to develop routing algorithms but assuming a perfect knowledge of instantaneous SNR values. This is rather theoretical. Practical routing solutions should be designed to work even with missing values of SNR, which would be more realistic. Moreover, an in-depth benchmarking with classical routing remains to be done. Link State Opportunistic Routing (LSOR) [START_REF] Gueguen | Link state opportunistic routing for multihop wireless networks[END_REF] has been conceived to incorporate the short term SNR measures in the path identification decision. As a result, LSOR dynamically adapts the optimal path at each time instant as a function of radio conditions. LSOR is designed to adapt to the various granularity of channel state information available in practical implementations. This leads to improve performance at the expense of a tendency to over-exploit the same link. In [START_REF] Ma | A routing metric for load-balancing in wireless mesh networks[END_REF], authors propose a Load Balancing Algorithm using Weighted Cumulative Expected Transmission Time metric (WCETT-LBA) that takes into account mean buffer occupancy information but does not consider multipath fading short term fluctuations. This achieves high load-balancing but does not optimize throughput.

In this paper, we propose to extend and merge LSOR and WCETT-LBA and we present a new Opportunistic Buffer Occupancy Routing (OBOR) solution. Like LSOR, it takes into account the radio condition variations in order to always select an efficient path in terms of throughput but adds, in its decision algorithm, collected buffer occupancy information in order to avoid best link over-exploitation. The result is a balanced protocol that better shares the traffic load in the whole network, reducing high packet delay occurrences, increasing links profitability and consequently system capacity. OBOR reaches better throughput and delay compared to state-of-the-art solutions. OBOR could also allow extending cell coverage by being combined with a non-conventional opportunistic scheduler such as in [START_REF] Gueguen | Incentive scheduler algorithm for cooperation and coverage extension in wireless networks[END_REF].

The paper organization is as follows: the next section presents the state of the art. Then, the third section describes our OBOR solution in details. In Section IV, we compare OBOR performance with state-of-the-art solutions. The fifth section discusses overhead. Last section (VI) concludes the paper.

II. STATE OF THE ART

Routing problems have been an important research field for years, leading to the implementation of several protocols. In this section, we chose to describe four well known relevant algorithms found in the literature. We dissociate opportunistic protocols from traditional ones such as AODV and OLSR, which do not integrate the wireless environment particularities. WCETT-LBA attempts to postpone network congestion using load balancing strategy but experiences the same issues (not considering short term SNR values). In contrast, opportunistic protocol such as LSOR fully exploits wireless network specificities which brings much better performance.

A. Optimized Link State Routing

OLSR is one of the non-opportunistic routing protocol. It uses routing tables to compute the path to destination. To keep the topology up to date, it sends control messages regularly [START_REF] Jacquet | Optimized link state routing protocol for ad hoc networks[END_REF]. Instead of testing all its neighbors, a node chooses a few neighbors and sends them a control message. Those chosen neighbors are called multipoint relays [START_REF] Huhtonen | Comparing AODV and OLSR routing protocols[END_REF]. A node's multipoint relay will be the one responsible for forwarding control messages to other "normal" nodes. The normal nodes will just process the information and will not forward it. The protocol is indeed efficient in a scaling scenario on huge a topology thanks to its lower flooding and broadcasting compared to Link State Routing (LSR) [START_REF] Eom | Information-dynamics-conscious development of routing software: A case of routing software that improves link-state routing based on future link-delay-information estimation[END_REF]. One other OLSR advantage is the absence of delay while establishing a route since all nodes already have routing tables (in steady system). To send a packet, the transmitting router simply has to look inside its routing table and to send the packet to its selected neighbor.

But as explained before, OLSR's main drawback is that it is not opportunistic and does not consider wireless network specificities like multipath fading 1 . Routing tables are built only considering average throughput values. This is the only value taken in consideration on path selection. As an example, if a path has a high quality average throughput but during the opening of the connection it is prone to destructive interference, it might obtain terrible throughput values and still be chosen by OLSR. Also, the longer is the path, the higher is the probability for OLSR to be subject to such a situation.

B. Adhoc On-Demand Distance Vector

AODV chooses a route by using flooding [START_REF] Das | Ad hoc On-Demand Distance Vector (AODV) Routing[END_REF]. Route Requests (RREQs) packets [START_REF] Ade | Performance comparison of AODV, DSDV, OLSR and DSR routing protocols in mobile ad hoc networks[END_REF] are sent whenever a source needs to send data to a new destination. When a node (other than destination) receives a RREQ, it broadcasts to all its neighbors. If a node receives a second RREQ, this one will be ignored. The chosen route will be the one used by the first RREQ reaching destination. Then, the destination node will send back to the source a Route Response (RREP) packet using the chosen path. Meanwhile, every RREQ reaching destination will be ignored. One advantage of AODV is that the chosen route will be the best in terms of throughput at first (Fig. 2(a)). But there are three main drawbacks: the first is path load, the second is nonconsideration of multipath fading and the last but not least, the high connection establishment delay. Concerning the buffer occupancy drawback (path load), one example can easily be found: during the route calculation, one node can be heavily loaded exceptionally due to destructive interference, but on average this node is part of the best average route. Indeed, the RREQ will reach destination later due to buffer occupancy and the best average path will not be chosen. The selected route will be the best for a short moment but might not be effective afterwards (for instance when the fully loaded buffer will become empty). The second drawback is the non-consideration of multipath fading. It means the selected route will always be the same until connection closes. It will be exposed to throughput variations and will not consider it. In the worst scenario, AODV could take the least efficient average route because it would be lucky at the path selection time due to favourable multipath fading conditions and it will stick to it. It could have terrible performance during the whole connection. Even if AODV would take the best average route, this one might have some low throughput values which constantly change because of multipath fading effect. It means that to get the best path, protocols must look over adaptive and dynamic solutions. Finally, the last drawback is the delay to open a connection. Selecting a route can be long because it needs to wait for the RREQ to reach destination from source, and then wait again for the RREP to travel back to source. This is not suitable for real time applications.

C. WCETT-LBA

Weighted Cumulative Expected Transmission Time with Load Balancing Algorithm (WCETT-LBA) is based on a new metric trying to avoid selection of overloaded paths. However, WCETT-LBA considers only average router queue length (BOavg) and mean transmission rate values (LSIavg). Multipath fading is not considered, reducing selected path throughput efficiency. In addition, being based on average path selection router queue length does not guarantee low packet delay at long term. Considering short term Buffer Occupancy (BOshort) values would have been more profitable. Indeed, it is always more profitable to consider updated and accurate values than average values to optimize system efficiency.

D. LSOR

Link State Opportunistic Routing (LSOR) protocol takes into consideration the known multipath fading values in the route selection process. LSOR uses the same base as OLSR but with this supplementary information, short term SNR will be considered when selecting the best path. This path will be dynamically chosen and corrected whenever short term SNR will change due to multipath fading. To be realistic, LSOR is designed with different levels of links knowledge making it usable in practice. LSOR heavily decreases packet delay and enhances system capacity in opposition to traditional (OLSR, AODV) and existing opportunistic (ExOR) routing solutions. However, without considering the router buffer occupancy load, the path selected by LSOR can experience high delays. Other paths with lower (but still efficient) radio conditions and with lower traffic load could provide better QoS/QoE.

E. Discussion

State-of-the-art solutions have their pros and cons. OLSR always knows the whole topology but only considers mean LSI values such as link throughput. Even if this solution could select the "best" route, this would only be an average best route. The real best path over time varies quickly (on a time scale of 50 ms [START_REF] Truman | A measurement-based characterization of the time variation of an indoor wireless channel[END_REF]). Taking only the average best route and sticking to it will always be equal or less efficient than selecting the "real best" route based on short term throughput values. In other words, a protocol that selects the route adapting to short scale radio conditions variation will always pick up the best real path over time, which consequently widely increases system throughput capacity and decreases packet delay.

AODV protocol is capable of finding the best instantaneous route in short term values, but will never change it, even with radio condition variations due to destructive interference. It will lead to decrease system performance when a variation of radio conditions will occur since the first and last selected route will not statistically always be the best over time.

To conclude this state of the art section, existing solutions from literature are far from exploiting optimal throughput of the links of a topology. Indeed, they are widely outperformed by LSOR which takes into consideration LSI short . However, continuously selecting the best path can cause congestion, drastically increasing packet delays. Consequently, in order to increase network performance, the focus can not be put only on the throughput but additionally on load level of each path. WCETT-LBA attempts to solve this issue. However, it is not designed in order to consider LSI and BO values with different knowledge levels (LSI avg & BO avg or LSI short & BO short ) making it inefficient in practice. A possible improvement could be to consider both channel state information in order to provide efficient throughput and buffer occupancy information in order to avoid routers congestion. This could allow to exploit all routes proportionately to their throughput and traffic load.

III. BUFFER OCCUPANCY AND LINK STATE OPPORTUNISTIC ROUTING (OBOR)

All routing solutions' main goal is to find the best path in order to maximize user satisfaction by providing them with a low delay for instance. This usually means selecting the best route in terms of throughput value. However, traditional solutions found in literature are not built in order to consider the multipath fading effect that can severely affect the performance of their decision. In addition special attention should be given to avoid best path over-exploitation in order to reduce the risk of congestion and the probability to experience high packet delays. OBOR, described in this section, is conceived in order to solve this problem.

A. OBOR principle

OBOR manages the routing decision in order to find an efficient path in terms of throughput but with acceptable buffer occupancy. From queuing theory and particularly following Little's law [START_REF] Little | Building Intuition[END_REF], the mean expected duration spent in a system (here, the mean packet delay) is equal to the average number of packets in the system divided by its mean throughput. For a specific link of a router, the metric used can be defined as:

C link(i,i+1) = (1 + BO i ) LSI i,i+1 , (1)
where BO i is the router i Buffer Occupancy and LSI i,i+1 the known link throughput between the node i and i+1. Considering the time taken to travel across a full built path from source to destination, the mean expected packet delay is consequently defined as:

C path = dest-1 i=source (1 + BO i ) LSI i,i+1 = dest-1 i=source C link(i,i+1) (2)
The objective of OBOR in order to guarantee high QoS and QoE is consequently to find the path j such as:

j = argmin p dest-1 i=source (1 + BO i ) LSI i,i+1 , p = 1,..., P, (3)
with p the path index and P the number of possible paths between the source and the destination. In our opportunistic routing vision, route value relies on the short term values of the channel states and router buffer occupancy sizes. In the perfect scenario, we can consider a full knowledge of this values. However, some of them can change faster or could flood too much signaling to allow full data collection. To get a more realistic context, only a few of these values should be considered as known. We specifically built OBOR in order to adapt to varying degrees of knowledge. In the rest of the paper, we will define the number of hops where OBOR will collect short term LSI and BO values as the parameter k. OBOR could be implemented based on many algorithms: we propose a solution inspired from Dijkstra's algorithm [START_REF] Brassard | Fundamentals of algorithmics[END_REF] to find the path with the minimum delay cost in the network. The metric used in (1) dynamically deals with the following rules according to the router knowledge: The metric used in (1) dynamically deals with the following rules according to the router knowledge: if short term LSI (LSI short ) and BO (BO short ) values can be collected and are known (the link is not farther than k hops away from the searching node), then they are considered in the OBOR route selection process. Otherwise, mean BO (BO avg ) and LSI (LSI avg ) values are considered.

Fig. 1 is a representation of a possible form for the OBOR solution's flowchart with:

• i is one of the system node • C path(i) is the link cost from a node to its neighbor i • C previous(i) is the sum of all links cost to build the path from the source to i • A node checked is a node that have been chosen considering his C previous(i)

• A visited node is a node which have already computed the algorithm during the path discovery The algorithm is executed by every node, starts at an opening of a connection and restarts every time short term throughput or router buffer occupancy values change at less or equal than k hops away. Note that it is possible that some distant links on a path (where the short term LSI and BO values are obsolete or unknown) finally experience high multipath fading or sudden high router load. That is why OBOR is not a pure source routing protocol. The decision is distributed. The emitter router will narrowly find the best possible route (primary path) considering the values that it is able to obtain at this node (as described above). Throughout the route, instantaneous channel quality and router queue information knowledge evolve at each hop. It permits transitional nodes to rework the primary route if a better path is found (appearance of good SNR or low buffer occupancy at the considered hop, but that the source cannot read due to signaling delay restrictions). Consequently, intermediate nodes might be able to adjust the original selected route if they determine that another link grant a more optimal end to the path (since the first route was rated with more average (non-accurate) BO and LSI values and have led to a different route tree selection). Applying these rules, packets will not always be sent on the original route and might be deviated to previously non-selected links that are revealed as better ways. Naturally, every single time a packet travels through a new hop, the receiving node is aware of new real LSI values closer from destination.

Considering this distributed approach, the packets managed by OBOR experience lower average delay than with AODV, OLSR, WCETT-LBA and LSOR that do not consider short term LSI and BO. B. Operation modes of OLSR, AODV, LSOR and OBOR solutions A perfect topology example would be like on Fig. 2. In this topology packets are sent by the source which is the router called "A" to destination named "H". Average links throughput values are written in black and short term values in red. Fig. 2(a) illustrates how OLSR and AODV would process the routing problem in this topology at t = 0 ms. As expected, OLSR selects the best average route while AODV chooses the best short term throughput route 2 . This example depicts OLSR behaviour which could lead to select a link with a very low short term throughput value. Indeed, we can read a short term throughput value of 3 Mbps on the link (E-H), value which ignored from OLSR. By considering the average value of 15 Mbps instead in its research for the best route, it will select this link. Hence, at this very specific moment, AODV will have a better bottleneck value, 8 Mbps on the (C-D) link, when OLSR bottleneck will be quite lower. But then AODV's problem will be the non-consideration of multipath fading, so it will not change its initial route in the future. Consequently, the last selected link of AODV (G-H) which has a low average value will presumably slow down data transmission in the future (see below).

For this example, parameters k is equal to two hops. It means the node using LSOR to find the best route to the destination will be able to know short term values on links up to two hops away. Short term values farther than 2 hops are considered obsolete (older than 50 ms), inaccurate (i.e. unreliable) and consequently, average throughput values will be taken into account to select the potential best route. Fig. 2(b) illustrates the information known by the access point with this assumption (k = 2) and the route originally selected by LSOR on the access point. Here, using the access point knowledge of the topology, it identifies that the best route is the one with a 9 Mbps bottleneck (A-B-E-H). Consequently, this node delivers packets to mobile B. Note that, in this case, the last link of the selected route has a low short term throughput value (Fig. 2(a)) and will affect system to a sub-optimal chosen route (because the access point does not know the short term value of the last link and uses the mean value). However, on Fig. 2(c), packets travelled to one hop closer to the destination and mobile B is now the processing node. Furthermore, B being closer to destination, it can read the short term throughput values. B node has got the information that E-H link has low throughput values due to multipath fading effect. Knowing this information, B adjusts the path and sends packets on the route (B-F-H) with a higher bottleneck than the original path selected by the access point. But even if it is profitable in terms of throughput, the LSOR selected path relies on mobiles experiencing high traffic load (specifically nodes B and F). It will decrease drastically users' QoE because of the experienced high packet delay.

In order to solve this problem, OBOR considers, in addition to LSI short , the BO short values in the routing decision process. Fig. 2(d) highlights OBOR behaviour. The primary path (A-C-D-G-E-H) obtained by the access point's knowledge offers a good throughput limited by a bottleneck of 8 Mbps (a bit less than with LSOR) but it goes through routers with empty or very low buffer occupancy. At the next step, node C does not change the primary path (Fig. 2(e)). However, at the third step, node D which is near the destination and taking the opportunities of new LSI and BO information, identifies link (G-E) as worse than link (G-H) and adequately changes the primary path (Fig. 2(f)).

Let's take a snapshot (Fig. 2(g)) of the route selected by AODV and OBOR with parameter k equal to 2 but when radio conditions have changed, 50 ms later. AODV's route has not been modified (A-C-D-G-H) and the consequences are clear: (A-C) link, the bottleneck of the route, has dropped to 1 Mbps due to multipath fading and AODV is clearly missing the best path, even though it was the best at the path selection instant (also note that node C is overloaded). Hence, AODV shows great performance at the route selection and only occasionally thereafter. AODV's chosen path will most of the time not be optimal. OLSR also sticks to the original path (A-B-E-H), and the bottleneck (now B-E) will now offer 4 Mbps as throughput values, which can be considered as mediocre performance. On the other hand, OBOR detected a variation in the topology's short term values and the algorithm has been run in order to select the new best route (A-B-F-H), experiencing a bottleneck of 8 Mbps and low router buffer occupancy for each node composing the path).

IV. PERFORMANCE EVALUATION A. Simulation context description

In simulations, the channel gain between two nodes is defined such as:

G = h • 10 Xσ 10 • d ref d α (4)
where h represents the Rayleigh multipath fading, which is modeled by an exponential distribution, X is a standard Gaussian random variable, σ is the standard derivation of shadowing in dB, d ref is the reference distance, d is the distance between nodes and α is path loss exponent. Rayleigh multipath fading variations induce short term throughput values. These values change every 50 ms [START_REF] Truman | A measurement-based characterization of the time variation of an indoor wireless channel[END_REF] which corresponds to the coherence time of the channel. We denote the SNR of a link as η and it is modeled such as:

η = P transmit • G N 0 (5)
with P transmit the power of transmission for nodes and N 0 the thermal noise power density. To compute LSI short Shannon's formula is used:

LSI short = log 2 (1 + η Γ ) (6)
where parameter Γ is a SNR correction factor that takes into account the difference between the information-theoretic performances and the practical implementation of the MCS [START_REF] Seo | A proportional-fair power allocation scheme for fair and efficient multiuser OFDM systems[END_REF], taking into account BER target denoted by E. It is defined as follows:

Γ = - ln(5E) 1.5 (7)
Performance evaluation is provided by a discrete event time simulator. Packets are generated each tick of time for each mobile. Mobiles run realistic Variable Bit Rate (VBR) application that generate high volume of data with tight delay requirements which significantly complicates the task of routing protocols. A Youtube streaming traffic was used to model VBR applications [START_REF] Horvath | Modelling of youtube traffic in high speed mobile networks[END_REF]. In our simulation we decided to use a classical square grid topology with n the number of nodes on a side. It permits an easy analysis of the solutions' performance variation function of the size n of the network. We ran different simulations for different values of n that gave similar results. In the following we show routing algorithms performance evaluation on topology n = 4. Fig. 3 represents the layouts of the 2 different scenarii described in the next section:

• First, we study a single source context in order to highlight the interest of the proposed solution in a simple scenario. In this one, we study the impact of the asymmetry of the topology with one source on the routing protocols performance. The average throughput of best links is always 12.5 Mbps: this path is made of the top and right links. The worst path is 7.5 Mbps on average and it is composed of the links on the bottom and left. Others path are "medium" paths, with an average of 10 Mbps. • The second represents a two sources context where the abilities of each protocol in avoiding path over-exploitation can be underlined. Indeed, algorithms without load balancing strategy often make best links become clogged, while others will balance the load and survive longer in time. The second scenario also allows to analyze the algorithms' scalability with two sources. The average best path now has two sources from router "1" (Fig. 3) to destination. It is necessary to differentiate algorithm(s) that would send packets from the first source (top left "1") on the best average path through the second source (top right "4"), increasing congestion, from algorithm(s) that would instead avoid sending packets from the first source through the second one, yielding to a better load balancing. The average links throughput stays constant between scenarii 1 and 2. On Fig. 3 the throughput values mentioned on the links are mean LSI values. We consider that each node has the same transmission possibilities. Therefore, mean LSI values can be regarded as a function of path loss and shadowing between nodes which determine the average LSI short values. In both scenarii, the proposed solution is compared to AODV, OLSR and WCETT-LBA. In addition, an optimal version of LSOR (i.e. LSOR 6 ) using full knowledge of LSI short has been implemented to be compared with. Even if it is not achievable in practice, [START_REF] Gueguen | Link state opportunistic routing for multihop wireless networks[END_REF] demonstrates that when n = 4, LSOR 6 (with k = 6) provides the best results. In order to study the impact of the link state knowledge k as well as the refreshing rate frequency (RRF) values on the proposed solution performance, different versions of OBOR have been implemented such as: OBOR

B. Studied KPIs

This study focuses on four Key Performance Indicators (KPIs) to evaluate the performance of each solution:

• The system limit capacity is defined as the traffic load reachable (in Mbps) by each protocol before the system congestion. Higher the value is, higher the system is able to process packets. • The mean packet delay is the mean delay (in ms) to transmit one packet, hence defined as the time between the creation and the arrival of the packet at the destination. • The system delivery ratio is the ratio (in %) between packets sent and received, denoted as SDR.

• The energy consumption is defined as the mean energy consumed to send one bit between two nodes (in mJ/bit). In this study, we consider the consumption of a mobile while transmitting equals to a constant amount of energy per time tick of 157 mW [START_REF] Gueguen | Fair energy efficient scheduler providing high system capacity for wireless networks[END_REF].

C. Scenario 1: single-source context Fig. 4 illustrates every protocol results within an asymmetric topology for n = 4 (Fig. 3).As aforementioned, in the best cases, OLSR chooses the best mean route. The best mean route is distinctly identified as the top right one here in our topology. Concerning AODV, it usually chooses the one with the best short term LSI values (statistically the lowest packet delay) at the connection opening and then never changes it over time. So the topology aspect at the transmission opening is truly crucial for AODV. It sometimes chooses the best average path, some other time the worst one or the medium one. Here we can see in Fig. 4 that OLSR is way better than AODV. AODV might choose the worst average path, which could only be good at the opening of transmission moment, while OLSR will always take the average best path that is better on the long term.

As explained in section II-C, WCETT-LBA is an algorithm based on average values. It will select its path considering both average throughput and average router buffer occupancy. The changing route frequency of WCETT-LBA is about one second. It predominantly selects the top right path unless it is overloaded. When this path is overloaded, the algorithm selects another route with lower average LSI values that is statistically less efficient on the long term (longer than 50 ms) and, even if load balancing is allowed, this last route will experience increased difficulties (the top right path has more chances of being efficient on the long term (i.e. time scale of one second)). This explains why it is better than AODV but worse than OLSR (Fig. 4).

Concerning LSOR solution, at low traffic load, it provides the best performance regarding the delay (Fig. 4(b)) since it continuously chooses the best short term path in terms of throughput while no congestion risk occurs. However when the traffic load increases, the same selected path could be successively chosen and could become overloaded. This can significantly increase packet delay and cause the SDR to drop. Taking radio condition specificities in its routing path selection, LSOR widely outperforms AODV, WCETT-LBA and OLSR in terms of system limit capacity by reaching a value of up to 12 Mbps (Fig. 4(a)).

As explained in section IV-A, different assumptions about available knowledge k of short term LSI and BO have been tested as well as the refreshing rate frequency values. OBOR 1 means a node is able to use a short term LSI and short term BO value up to one hop. This allows each node to partially adapt both to the path load fluctuation and to multipath fading variations avoiding selecting some temporary overloaded path or bad path in terms of throughput. It drastically affects the system by increasing the whole throughput capacity, increasing the load before the congestion limit of the network by reducing delay (Fig. 4(b) and 4(a)). The more the acknowledgment of short term LSI and BO values (k), the more precise will be the adjustment of the route by every node to prevent overloaded nodes and multipath fading variations. It increases OBOR's capacity by splitting the single source load on the whole network (Fig. 4(a)). As anticipated, the higher k is, the lower will be the arriving packet delay (in every traffic load scenario) and the later the network congestion limit will be reached. For every n (sizes of networks), values of k exist such that:

k ≥ 2(n -1), (8)
k complete = 2(n -1). (9)
A knowledge k as in (8) also assumes that all short term LSI and BO values of every network's single links and nodes are known and readable. In a small n topology this is possible but when n starts to increase, it becomes an idealistic assumption and unrealistic from a technical point of view. For the sake of completeness, we ran simulations for all scenarii applying every existing k values between 1 and k complete . In those scenarii, n equals to 4 means that to get a complete knowledge, k must be higher or equal to 6. Consequently, k = 6 represents the full knowledge of short term LSI and BO in the topology. In these idealistic scenarii, OBOR protocol will systematically find the best route based on short term values. From this point, expanding the knowledge k over 6 will not change anything. However, to reach a total knowledge at k complete , it might represent a high overhead and it is a strong assumption. In state-of-the-art radio access management research [START_REF] Wong | Multiuser OFDM with adaptive subcarrier, bit, and power allocation[END_REF][START_REF] Viswanath | Opportunistic beamforming using dumb antennas[END_REF][START_REF] Ostovari | Cooperative internet access using helper nodes and opportunistic scheduling[END_REF][START_REF] Liu | Analysis of proportional fair scheduling under bursty on-off traffic[END_REF][START_REF] Anchun | Dynamic resource management in the fourth generation wireless systems[END_REF], the knowledge k = 1 assumption is extensively approved since short term LSI (i.e. short term Signal to Noise Ratio) are frequently analysed during the process of scheduling. Since the assumption k = 1 can always be treated as valid, OBOR 1 results illustrate the minimum guaranteed gain delivered by OBOR. Yet, it is important to note that k ∈ R and k ∈ ]1, 3] can also bring a discussion (Section IV-E) but is studied generally possible/feasible. Therefore, in the following, we focus our study to k = 1 and k = 2.

Limit capacity results (Fig. 4(a)) illustrate OBOR performances for different k and RRF values. For instance, OBOR + 2 means that this version of OBOR has a refresh rate up to 25 ms and a LSI knowledge of two hops. Short term LSI will be the same for 2 route decisions but the BO value can change drastically during 25 ms, even more with a high traffic load. This upgrade permits to be even more accurate about avoiding path overload and network congestion. As illustrate in Fig. 4(a), quicker is refreshing time, slightly better are the results in term of system limit capacity. Concerning the impact of k values on OBOR performance, note that performance of OBOR 2 and OBOR 6 are very closed. Considering OBOR 6 can be seen as OBOR optimum in this topology, these results underline that full knowledge is not required to reach high performance. From this point, as OBOR 2 almost reaches OBOR optimum performance with a lower overhead (i.e more realistic) while delay and SDR KPIs are highly related to the system limit capacity, we chose to do not display OBOR 6 versions on these two last KPIs for presentation matters. Focusing on energy, Fig. 4(d) represents the energy consumed by each transmitted bit for a traffic load of 15 Mbps transmission. Solutions that do not consider multipath fading never optimize throughput and the transmission takes a longer time. That is why OBOR and LSOR widely outperform traditional routing protocols (respectively OLSR, WCETT-LBA and AODV). In addition, making efficient load balancing allows to transmit the traffic load faster. More nodes are solicited but for a shorter duration that reduces their time of activity, highly greedy in energy consumption. OBOR takes into account the wireless radio condition like LSOR in order to continuously optimize path throughput but, adding buffer occupancy consideration, packet delay is reduced and less energy is consumed.

To recap this scenario's results, WCETT-LBA and AODV deliver interesting performance on a low traffic load but are widely outperformed by all other protocols with an increased traffic load. OLSR is better since it chooses the best mean path. However, as soon as short term LSI are considered, LSOR and OBOR clearly outperform the other solutions. This gap increases with k. LSOR 6 being an algorithm with a full vision of short term LSI values, it is clearly good with a low traffic load (Fig. 4(b)). With medium and high traffic loads, it has difficulties to keep a good delay and its delivery ratio drops (Fig. 4(c)). Even with the knowledge of only LSI short and BO short of one hop (k = 1), the less powerful version (OBOR 1 ) of OBOR still outperforms the best version of LSOR considering full knowledge (LSOR 6 ) after 12 Mbps. It can nearly reach 13.5 Mbps before congestion. Indeed, the capacity to balance the load across the network makes it an efficient algorithm to ensure a good scalability when time to increase traffic load comes. It avoids links over-and/or under-exploitation. In addition, the higher the knowledge level k is, the more efficient OBOR becomes (i.e. OBOR 2 > OBOR 1 ). This is similar for the refresh routing time. The higher the routing decision frequency is, the better are the abilities of OBOR to avoid congested paths and its capacity to reduce delays and increase system capacity (i.e. OBOR 2 < OBOR + 2 ).

D. Scenario 2: multi-sources context

Our second scenario is based on multi-sources topology (2 sources (Fig. 3)). The scenario allows to study the abilities of each solution to avoid selecting a same path for both sources and consequently links over-exploitation. Fig. 5 shows the results for this scenario. Both sources produce the same quantity of data. Traffic load information are the data created in the whole network.

The first thing to notice is the OLSR case. As shown in Fig. 3, the average best path goes through both sources. Choosing this path, OLSR transferred the data from the first source to the second that quickly leads to congestion (Fig. 5(b) and (Fig. 5(a))). With OLSR, system capacity is consequently the same for scenario 1 (Fig. 4(a)) and 2 (Fig. 5(a)).

With AODV, selected paths depend on initial radio conditions. Sometimes the path of the first source does not cross the second source path, sometimes they share the exact same path, and sometimes they only have one or two nodes in common. Making regular involuntary load balancing, AODV provides in this scenario better performance than OLSR.

The same phenomenon appears with WCETT-LBA. As expected, taking into account average values of routing traffic load, it makes efficient load balancing and outperforms OLSR and AODV in terms of delay, packet delivery ratio and system capacity (Fig. 5(b), 5(c) and (Fig. 5(a))).

Continuously choosing the best current path at each instant, LSOR keeps good performance on low traffic load situation. In addition since radio conditions vary quickly, LSOR also performs temporary load-balancing that helps to increase system capacity limit and reduces delay (Fig. 5(b) and (Fig. 5(a))). However, the top right path (i.e. mean best path (Fig. 3)), is often selected causing congestion when approaching 15-16 Mbps.

Taking the benefits of LSOR to LSI short and additionally to the BO short values, OBOR is able to reach WCETT-LBA performance using its lowest degree of knowledge (OBOR 1 (k = 1)). Indeed, a range of 1 hop, OBOR 1 could sometimes engage the flow in a potential good path in terms of throughput and traffic load. When progressing forward, it then discovers too lately that the rest of the path is heavily overloaded or experiences high multipath fading and it could have a lack of choice to find better path. However, if the refresh routing time is slightly increased, OBOR + 1 quickly sees that the selected path starts to be overloaded and the change of path reduces failure effects. This allows OBOR + 1 to provide results very close to LSOR 6 while requiring a widely less amount of data to collect (and consequently, easier to implement contrary to LSOR 6 ). With a range of 2 hops, OBOR 2 is able to avoid the majority of these cases. Results show that OBOR 2 clearly outperforms all other solutions in terms of packet delivery ratio (Fig. 5(c)) and system capacity (Fig. 5(a)) providing a low packet delay even with high traffic load (Fig. 5(b)). As in the previous scenario, the results in Fig. 5(a) show that the differences between the performance of OBOR 2 and OBOR 6 are not significant.

To summarize, as expected, algorithms without any load balancing and path adjustment are heavily outperformed by the others solutions. WCETT-LBA at low traffic load has interesting results because of low variation of router buffer occupancy, however with a high traffic load, average values are not sufficient enough leading to congestion. Like with LSOR, there is a huge difference between one and two hop(s) of knowledge for OBOR but full knowledge is not required. The solutions can be classified according to system capacity limit (Fig 5 E. Discussion about the overhead 1) Analytical estimation: It is possible to determine long term SNR (LSI avg ) values if the transmission power and either the Bit Error Rate (BER) or the Expected Transmission Count (ETX) are known. The short term throughput values (LSI short ) can be determined as well if enough transmissions are occurring on a link, which allows the implementation of OBOR. However, the time required to collect these measurements might be longer than the time during which they are relevant (because the channel conditions evolve quickly). Thus, they can be obsolete reducing the resulting performance of OBOR. To address this issue, other methods can be used such as studied by 3GPP and in literature concerning medium access/radio resource allocation [START_REF] Wong | Multiuser OFDM with adaptive subcarrier, bit, and power allocation[END_REF][START_REF] Viswanath | Opportunistic beamforming using dumb antennas[END_REF][START_REF] Gueguen | A fair opportunistic access scheme for multiuser OFDM wireless networks[END_REF]. Using channel model equations along with the measurement of received power while transmission occurs on a link yield to more reliable values compared to using a strategy based upon ETX or BER because it is more instantaneous. Furthermore, those more reliable measurements can be accomplished using data packets being transmitted over the channel, reducing the need for dedicated signaling. The only information that is additionally required is the transmission power of the receiver (that the sender can add to a packet). However, If we assume this value rarely changes, the resulting overhead can be neglected.

It is important to note that even though the overhead of short term LSI values and BO is small, it will become significant if the LSI short and BO short of each links are sent to each node of the topology. This is why OBOR is able to work with partial knowledge of LSI short and BO short values. The extra overhead required by OBOR compared to OLSR for different values of k is as follows:

• OBOR 1 =⇒ Each node only has knowledge of their links. There is no forwarding of LSI short values to neighbors so no overhead to consider. Each router uses power measurements recorded in received data packets. BO short values must still be forwarded, though. Designating N as the number of nodes in the topology and L as the number of links of a node, the node has to forward its data on L links to communicate with its neighbors. Assuming that every single node has L links and BO short values are updated every T seconds, the total forwarding cost (in packet) is L for one node every T ms. The global system overhead cost is consequently (L * N/50.10 -3 ) packet/s for OBOR 1 , L * N/25.10 -3 for OBOR + 1 and L * N/10.10 -3 for OBOR ++ 1 .

• OBOR 2 =⇒ The measured short term LSI and BO must be forwarded to each neighbor at one hop. Two cases are treated:

-It forwards the new measured LSI values at every detected variation (unsynchronized forwarding: upper bound).

When it detects a variation of short term LSI link, the node has to forward its data on L -1 links to communicate to its neighbors. Sent packets can add BO short information and the increased cost is inconsequential for OBOR 2 while it is doubled with OBOR + 2 and multiplied by 5 for OBOR ++ 2 . Assuming that every node is connected with L links and the short term LSI values variation frequency is 50 ms, during the signaling of these LSI short values, forwarding cost (in packet) is (L -1) * L for each node every 50 ms. Consequently, the global system overhead cost is ((L -1) * L * N/50.10 -3 ) packet/s for OBOR 2 , ((L -1) * L * N/25.10 -3 ) packet/s for OBOR + 2 , ((L -1) * L * N/10.10 -3 ) packet/s for OBOR ++ 2 .

-The short term LSI measurements forwarding to all links connecting a node are synchronized (synchronized forwarding: lower bound). The data will be collected with a minor delay but L -1 short term LSI measurements can be included in a same signaling packet meaning that we can divide the overhead by L-1. Consequently, the total system overhead cost can be decreased to (L * N/50.10 -3 ) packet/s for OBOR 2 , (L * N/25.10 -3 ) packet/s for OBOR + 2 , (L * N/10.10 -3 ) packet/s for OBOR ++ 2 .

• OBOR 3 =⇒ The measured short term LSI and BO values must be forwarded to each neighbor at two hops. Respecting the same law, we have to deal with two possibilities:

-Every single detection of variation, we forward the updated LSI values (unsynchronized forwarding: upper bound). As OBOR 2 , this packets will be sent to its L-1 direct neighbors, L times. Each connected node have to forward this data to its own neighbors once. Consequently, the total system overhead cost is increased and respectively for OBOR 3 , OBOR + 3 and OBOR ++ • OBOR k =⇒ The measured short term LSI and BO values must be forwarded to each neighbors at k-1 hops. Respecting the same law, we still have to deal with two possibilities:

-At every single variation detection, we forward updated LSI values (unsynchronized forwarding: upper bound). Total system overhead cost is heightened: ((L -1) (k-1) * L * N/T ) packet/s. -The short term LSI measurements forwarding to every link connecting a node are synchronized to be combined in only one single signaling packet (synchronized forwarding: lower bound). Total system overhead cost can be largely decreased to ((L -1) (k-2) * L * N/T ) packet/s. As aforementioned, OBOR 1 , OBOR 2 and OBOR + 1 do not require much overhead and can easily be considered. OBOR + 2 and OBOR 3 can also be considered, though they generate more overhead. Higher values of k can only be considered in topologies with lower connectivity (low L values). This is why we focus on OBOR 2 (having the same signaling cost than OBOR 1 when forwarding is synchronized) and OBOR + 2 in this paper. OBOR 2 and OBOR + 2 still widely outperform OLSR, AODV, WCETT-LBA and LSOR 6 .

2) Overhead comparison on one example: To greatly discern cost C in terms of overhead for every solution, we studied their amount of data signaling conditions in a grid topology with n = 3 and with a constant 50 Mbps traffic load T . In this context, L = 2.66 on average and N = 9. To create and keep updated routing tables with average LSI values, OLSR needs a precise signaling number (defined as S OLSR in the following). The cost is C = S OLSR for WCETT-LBA, OLSR, and LSOR 1 solutions. The cost is C = S OLSR + (L * N/50.10 -3 )packet/s for OBOR 1 protocol. Signaling packets of OBOR incorporate router ID, BO and LSI values. Their length can be evaluated as almost equal to 60 bytes. Overhead signaling for OBOR 1 consequently cost C = S OLSR + 230kbps. As previously explained in the last subsection, additional overhead cost to collect short term BO and LSI values is bounded by L * N/50.10 -3 and (L -1) * L * N/50.10 -3 signaling packets per second for OBOR 2 . So, the OBOR 2 total network overhead cost is bounded by S OLSR + 230kbps and S OLSR + 382kbps. For OBOR k complete (meaning total knowledge, thus OBOR 4 ), these values are bounded by 633kbps and 1.051 * 10 3 kbps (S OLSR is not required since mean LSI values are useless in this case). For AODV, a few signaling packet are sent during route selection by broadcasting and can be neglected if the connection lasts long enough. V. CONCLUSION Routing has always been a critical issue in multihop wireless networks. Multipath fading effect has been left behind in state-of-the-art solutions though it is a relevant wireless network particularity affecting every link's capacity. It makes it way harder for these protocols to permanently choose the best route with an optimal throughput value. OLSR exploits its routing table knowledge and keeps links value updated considering average LSI values. AODV selects a route by broadcasting packets (RREQ) and selects the path travelled by the first packets reaching destination. But in both cases, the chosen path does not change on the short term variation time scale which condemns them not to be optimal in terms of delay and throughput. We are persuaded that links' short term Signal to Noise Ratio values must be widely considered by the use of multipath fading variation knowledge. Previous works on LSOR protocol pointed out that taking into consideration this information is truly beneficial. Collecting these inputs have been proven as realistic in the access point radio resource management research domain (opportunistic scheduling) and grants a massive network performance improvement. The LSOR protocol can profit from decreasing delay in plentiful cases and rise throughput values by more than several tens of percent pushing back the system congestion. However, we demonstrated in this paper the limits of the LSOR algorithm that does not consider router buffer occupancy level in its management. This sometimes conducts to some links over-exploitation while several other links are under-exploited and this phenomenon particularly appears when network traffic load is high. This paper proposes to add the previous parameter in the path selection process. The new OBOR approach uses less signaling information than LSOR and succeeds in outperforming it. Packet delay is widely reduced thanks to an efficient load balancing while system capacity limit and packet delivery ratio are improved.

Fig. 1 :

 1 Fig. 1: The flowchart of the OBOR algorithm.

  (a) Paths chosen by OLSR and AODV at t = 0. (b) Router A: routing decision maker running LSOR when k = 2. The source chooses the next hop at t = 0. (c) Router B: routing decision maker running LSOR when k = 2. The second node chooses the next hop at t = (0+ ) ms. (d) Router A: routing decision maker running OBOR when k = 2 at t = 0. (e) Router C: routing decision maker running OBOR when k = 2 at t = (0 + ) ms. (f) Router D: routing decision maker running OBOR when k = 2 at t = (0 + ) ms. (g) OBOR when k = 2 at t = (50 + ) ms. OBOR's path has been adapted to new link throughput and router load.

Fig. 2 :

 2 Fig. 2: An example of the paths chosen by OLSR, AODV, LSOR and OBOR when k = 2.

Fig. 3 :

 3 Fig. 3: Performance evaluation topologies.

  (a) System limit capacity. (b) Mean packet delay. (c) System delivery ratio. (d) Mean energy consumption.

Fig. 4 :

 4 Fig. 4: Scenario 1 (single source).

  (a) System limit capacity. (b) Mean packet delay. (c) System delivery ratio. (d) Mean energy consumption.

Fig. 5 :

 5 Fig. 5: Scenario 2 (multi-sources).

3

  equal to: (L -1) 2 * L * N/50.10 -3 , (L -1) 2 * L * N/25.10 -3 , ((L -1) 2 * L * N/10.10 -3 ) packet/s. -The short term LSI measurements forwarding to every links connecting a node are synchronized to be combined in only one single signaling packet (synchronized forwarding: lower bound). Total system overhead cost can be widely decreased for OBOR 3 , OBOR + 3 and OBOR ++ 3 to: (L -1) * L * N/50.10 -3 , (L -1) * L * N/25.10 -3 and ((L -1) * L * N/10.10 -3 ) packet/s.

TABLE I :

 I 1 , OBOR 2 and OBOR 6 . For each k value, three RRF values are also tested: 50 ms, 25ms, 10ms denoted by OBOR k , OBOR + k , OBOR ++ k , respectively. Other simulation parameters are described in table I. Simulations parameters.

	Parameters	Value
	Node transmit power	P transmit = 0.1W (20 dBm) [30]
	Standard deviation of shadowing	σ = 8 dB
	Path-loss exponent	α = 3.5 (urban context)
	Target BER	E = 5 × 10 -5
	Thermal noise power density	N 0 = -174 dBm/Hz
	Simulation duration	20 × 10 3 s

  (a)): OLSR (10.5 Mbps), AODV (12 Mbps), WCETT-LBA & OBOR 1 & LSOR 6 (15.75 Mbps), OBOR + 1 (16 Mbps), OBOR ++

	Mbps), OBOR ++ 2	1 6 (18.7 Mbps), OBOR ++ & OBOR + 6	(16.25 Mbps), OBOR 2 (18.5 Mbps), OBOR + 2 & OBOR 6 (18.6 (19 Mbps). This represents a gain for OBOR 2 of 54 and 76 %
	respectively compared to AODV and OLSR.

TABLE II :

 II Global overhead cost estimation for the grid topology with n = 3.

	Solution	Cost from	Cost from short	Total overhead
		mean values	term values (kbps)	cost C (kbps)
	OLSR	S OLSR	0	S OLSR
	AODV	0	0	ε
	WCETT-LBA LSOR 4	S OLSR 0	0 [633, 1.051 * 10 3 ] S OLSR + [633, 1.051 * 10 3 ] S OLSR
	OBOR 1	S OLSR	230	S OLSR + 230
	OBOR 2 OBOR 4	S OLSR 0	[230, 382] [633, 1.051 * 10 3 ]	S OLSR + [230, 382] [633, 1.051 * 10 3 ]

Note that OLSR is hardly improvable by taking short term throughput values into consideration. To create accurate routing tables, OLSR has to converge and it seems hardly realistic with link values changing very fast over time. Even more, RFC 7181 defining OLSRv2[START_REF] Clausen | Rfc7181: The optimized link state routing protocol version 2[END_REF] sets signaling frame exchange timer to about one second which is much longer than multipath fading variation time. It makes OLSR unable to consider those values.

AODV floods the whole network with signaling RREQ packets until the first one reaches destination. It will establish the route that will regularly be the best in terms of throughput (if not overloaded) at this moment.