Fabrice Theoleyre

Fabrice Valois

MANET protocols are often evaluated through simulations, not in a real radio environment. We describe here the implementation and deployment of a complete testbed for hybrid networks, allowing a seamless integration of an ad-hoc network in the Internet. In particular, a self-organization protocol and the mobility management protocol benefiting from this organization were implemented. The performances demonstrate the feasibility and usefulness of this scheme. Besides, this testbed offers a detailed description of the requirements to constitute a wireless testbed and to test any protocol for ad hoc or hybrid networks.

Indoor experiments of self-organization and localization protocols for hybrid networks I. INTRODUCTION Mobile Ad Hoc Networks (MANET) are literally networks ready to work. All terminals can communicate with other nodes via wireless communications: MANET are spontaneous networks, without any fixed infrastructure. The network must function autonomously, without any human intervention: the self-configuration property is vital. In consequence, the nodes must collaborate to set up all network functions like routing. Because a source can be not in the radio range of the destination, intermediary nodes must relay the packets along a multihop path, each node being both router and client. Thus, a distributed routing algorithm must be proposed, computing efficient routes and dealing with network dynamicity. Ad-hoc networks connected to the Internet are often called hybrid networks, constituting multihop cellular networks. The most static nodes will surely forward the packets of the mobile nodes. In this paper, we focus our work on how to provide an efficient hybrid network, connected to the Internet, and test in one scenario the Internet access of a mobile node.

Recent works propose to self-organize the network via a virtual structure before its utilization. Such a self-organization is useful to give a macroscopic and stable view of the topology. Moreover, the introduced hierarchy allows to deploy more efficient protocols. Self-Organized Mobility Management protocol (SOMoM) [START_REF] Theoleyre | Mobility management in multihops wireless access networks[END_REF] proposes a routing scheme to interconnect seamlessly a MANET to the Internet thanks to a selforganization. Routing caches are distributed in the backbone, to create stable routes and to reduce the overhead: a selforganization seems promising.

The protocols for ad hoc networks are mainly evaluated through simulations, like SOMoM was. Simulations present several assets in terms of reproducibility, financial cost, deployment ease and flexibility. However, simulations simplify the radio environment: fading, shadowing, reflections or diffractions cannot be well modeled. A tradeoff between accuracy and execution speed is therefore required.

The contribution of this article is to present a performances evaluation of both a self-organization and a routing protocol for hybrid networks. The performances are measured in a real indoor radio environment, reflecting the expected performances of an operational hybrid network. Thus, this solution proposes the creation of a complete multihop cellular network. In a more general manner, this article details the complete network architecture and proposes consequently the description of a generic testbed, reusable to evaluate the performances of any protocol for hybrid networks. This approach could constitute the first step to set up an efficient wireless testbed for any research in this domain.

This work is organized as follows. Section II presents a panorama of existing testbeds for wireless networks. Section II-A gives a short overview of the protocol implemented here, and section III details the design and the implementation of our testbed. Results are given in section IV and a discussion about the issues of current testbeds in section V. Finally, section VI concludes this article and gives some perspectives.

II. RELATED WORK

[2] presents a pioneering work in the conception of a testbed for MANET, measuring the performances of DSR, mainly the delays and TCP throughput. The authors propose also a MAC filtering to set up any topology. Similarly, [START_REF] Kaba | Testbed on a desktop: strategies and techniques to support multi-hop manet routing protocol development[END_REF] proposes to deploy cables, shields and signal attenuators to control the signal propagation: the reproducibility is total. However, such a testbed cannot model a real-world environment, limiting the utilization to debugging. In [START_REF] Gray | Outdoor experimental comparison of four ad hoc routing algorithms[END_REF], AODV exhibits a 50% dropping rate in their outdoor environment, which is much lower than the performances obtained here. Recently, [START_REF] Bicket | Architecture and evaluation of an unplanned 802.11b mesh network[END_REF] presents a complete platform of 37 nodes. Approximatively 10% of the pairs of nodes do not find any route because of the lack of reliability of broadcasts. Recently, [START_REF] Kiess | A survey on real-world implementations of mobile ad-hoc networksnext term[END_REF] proposed a survey of the current testbeds used in the scientific community.

A. Overview of SOMoM

In [START_REF] Theoleyre | A virtual structure for mobility management in hybrid networks[END_REF], we introduced a self-organization based on a virtual backbone: some mobile nodes are elected to form a connected structure. The backbone consists in a tree structure, the Internet gateway being the root of this tree. Procedures allow to react to topology changes and to reconstruct locally the structure when it is broken. In particular, some control packets are periodically flooded in the backbone tree by the root to maintain the connectivity. In the future such packets will Fig. 1. General behavior of SOMoM integrate information about the Internet connection parameters (e.g. the IP subnet, the Foreign Agent address,etc.). However, a tree could present problems of robustness: only one radio link failure could potentially disconnect the structure. Consequently, the meshed backbone could be used instead of the tree structure: when a packet must be forwarded by the backbone, it is forwarded through all the radio links between backbone members, and not only through the radio links child→parent. The algorithms for construction and maintenance are proved to be self-stabilizing and highlight in particular properties of stability and robustness.

[1] presents a routing protocol based on this backbone: SOMoM. It creates a multihop cellular network (or hybrid network): it integrates an ad hoc bubble in a wired network. The backbone nodes form a distributed cache, and packets are forwarded through the backbone from or to the Internet gateway. The self-organization algorithms already maintain a tree structure (child→parent in the backbone). This allows to create a route toward the root of the backbone, i.e. the Internet gateway. This constitutes a gratuitous proactive route to the Internet, an upload route. Inversely, a localization process is initiated when the Internet gateway receives a packet to forward to the ad hoc area, if no route is present in the routing cache for this particular destination. A localization request is flooded but only through the backbone nodes: it reduces largely the overhead. Then, a download route is created distributively in the backbone. We adopted a crosslayer approach: the self-organization and routing protocols collaborate in order to flush obsolete information when the backbone topology must be changed. Since the backbone topology is more stable than the radio topology, this improves the routing cache stability. SOMoM increases the route stability and decreases the overhead. The SOMoM structure is depicted in figure 1.

III. DESIGN AND IMPLEMENTATION

A. Software: somomd

We chose to implement SOMoM in a Linux testbed because it is flexible and open-source. Moreover, Linux is extensively used in the scientific community and allows to share easily the different implementations. Additionally, we chose to implement the totality of the protocol in user space: the code is portable, with any Linux kernel, without modification. We implemented a daemon which constructs and maintains the virtual backbone, and the routing protocol SOMoM, described above. This daemon is fully operational: the self-organization is well-maintained and the localization protocol SOMoM functions perfectly. In the following, we detail some key points in our implementation available online [START_REF] Somomd | [END_REF]. a) Kernel / user space: Linux philosophy is to propose a restricted and stable kernel. Programs should be executed in a normal shell, not in kernel mode. However, this property is rarely observed by developers. Indeed, Ad-Hoc Support Library (ASL) [START_REF] Kawadia | System services for implementing ad-hoc routing: Architecture, implementation and experiences[END_REF] allows to implement ad hoc daemon in user space but contains itself kernel modules, for example to modify the routing table. [START_REF] Chakeres | AODV routing protocol implementation design[END_REF] presents 3 methods to implement a routing protocol in MANET. With the Netfilter method, some filters are applied when packets arrive. Some packets can be forwarded to a specific application when they are treated by the IP layer. Alternatively, the daemon could be implemented as a kernel module ( [START_REF] Klein-Berndt | Kernel AODV implementation[END_REF] is one example of such an implementation). Finally, a third method consists in listening frames in the MAC layer. If an ARP request is generated, it is intercepted and a route discovering is initiated (ARP is in this case mandatory). Kernel implementations seem for us intrusive and present several drawbacks (e.g. kernel instability, implementation changes when the kernel is upgraded). Our daemon is implemented integrally in userspace, and was tested with the kernels 2.6.14 and 2.6.12.

b) Multi-threads: The daemon must monitor several tables (neighborhood table, routing table,. . . ) and flush obsolete information. The maintenance is based on triggers and timeouts. So, we chose a multi-threads implementation, each thread monitoring one type of information. Naturally, the implementation must take care of resource conflicts. c) Addressing: Each ad hoc node is configured with a static address with a 32 bits netmask (the network-netmask). Therefore, a route in the routing table corresponds to one single destination. All the nodes share a common logical private IP subnet of 24 bits, called the somom-netmask. The somom-netmask proves its usefulness for the Access Point for example. The AP must distinguish the ad hoc addresses and the Internet addresses. When the destination is known, a 32 bits route exists in the routing table: the packet is sent directly. On the contrary, if the AP has no route, it will verify that the destination IP address owns to the ad hoc area thanks to the somom-subnet (obtained from its IP address and the somom-netmask).

d) Routing table : The kernel routing table was designed for permanent and stable routes: a change is an exception. But ad-hoc routing protocols add and delete continuously the entries in the routing table, and handle timeouts. Hence, an internal routing table maintained by somomd dialogs with the kernel routing table and synchronizes its information (fig. 2). In this way, the kernel routing table is not modified, rendering the source code evolutive.

e) Protocol stack: The OSI model requires a strict independence of different layers so that layers interchangeability is facilitated. This independence allows flexibility but decreases performances: no information is shared. Moreover, an information mutualization allows to reduce the overhead. For example, DSR assumes the existence of an API which allows a notification of the MAC layer when an unicast packet is well The software architecture is described in figure 2. The daemon is executed above the network layer and uses an UDP socket to send control packets. However, the protocol needs information about all received IP packets. Thus, the daemon implements also a packet socket. This facility allows in Linux to capture all MAC frames (like a promiscuous IP mode). The program extracts IP packets, and information useful to update routing tables for example. Eventually, the packet is forwarded to the routing or self-organization threads if the packet is intended to the UDP port registered by SOMoM. In conclusion, when a packet is forwarded by a node, somomd can update on the fly its routing table.

In particular, each node can add an entry in its routing table for the source of each received packet when the source owns to the somom-subnet (computed from the IP address and the somom-netmask). In this way, a gratuitous inverse route is learned each time a packet is forwarded by a node.

f) Reactive behavior: The code was implemented in the user space. Each ad-hoc node has a default route pointing to its parent in the backbone. If a specific route with a 32 bits prefix corresponds, it will be used. Else, the packet is transmitted through the default route. Hop hop, the packet reaches the gateway if no route exists for this destination.

When the Access Point receives any packet to forward, it can extract the location of the destination thanks to the somomsubnet. If the destination is outside the ad hoc scope, the packet is forwarded through the wired link. If the destination is in the ad hoc area, two cases can occur. If a route (with a 32 bits prefix) exists, the packet is sent through this route. Else, the route toward a client node (a download route) must be learned reactively. The process uses the TUN facility offered by Linux. In the gateway, a route corresponding to the somom-subnet points to the TUN device, and this TUN device points itself to the somomd process. Moreover, when a packet is routed, the linux kernel chooses the route matching with the longest prefix. Hence, the default route is only used in the gateway when no other route exists. Somomd will receive this packet, buffer it in an internal queue, and send a route discovering. In conclusion, we did not modify at all the Linux Kernel.

For a route discovering, the AP sends a Route Request in multicast. All the backbone nodes which receive such a packet must forward it in multicast if the destination is not present in their neighborhood table. Else, a Route Reply is generated and transmitted through the default route. Hop by hop, the Route Reply is forwarded toward the gateway, and creates in each hop an entry in the routing cache. When the AP receives the Route Reply, somomd will extract the packets from the internal queue for the corresponding destination and just re-inject them in the normal routing process. The new route will be used. In conclusion, we keep the whole IP routing process without modification

B. Node equipment

The mesh network is constituted by 8 barebones (silent and small PCs). Each node is equiped with an hard disk to store an huge quantity of logs in order to extract performance results of the experimentations. Besides, all the static nodes have a wired NIC so that it can be monitored out-of-band, and so that the management traffic does not interfere with experiments. Only one mobile node is introduced in the experiments since to manage mobility during the experiments is a quite difficult task. Other mobile nodes will be introduced in the future to corroborate our current results. However, the radio topology can change because of temporary obstacles (closed door, person in the corridor. . . ). Consequently, even in a topology with only one mobile node, we can test many usual scenarios.

The nodes have all a IEEE 802.11 abg NIC, but we use the 2,4 GHz frequency so that any standard mobile node can be integrated in the hybrid network. Naturally, some tests have been also done with the 5 GHz frequency, and the obtained results corroborate the results exposed in the next section. However, they are not presented here because of lack of space.

In IEEE 802.11, the broadcast frames are always sent with the lowest available bitrate. Oppositely, unicast frames are sent with the bitrate as high as possible. Thus, the radio range of broadcast and unicast frames are different since the modulations differ. This could constitute a severe drawback: hellos being broadcasted, a node can choose to forward a packet to an unreachable neighbor. Besides, IEEE 802.11 presents performance anomaly when different bitrates are used [START_REF] Heusse | Performance anomaly of 802.11b[END_REF]. In conclusion, we chose to configure all the clients with a forced 1Mbps bitrate (6 Mbps with IEEE 802.11 a).

C. Testbed

8 nodes were deployed in the lab, constituting a multihop testbed (fig. 3). The topology is a trade-off to test both the network diameter and the network redundancy. One node (represented with a red square in the figure 3) acts as a gateway to the Internet. The gateway implements NAT functions to connect the ad-hoc area to the Internet, using netfiler. The testbed is full-operational and used for a multihop Internet connection in the lab.

A. Self-Organization

In a first time, we evaluated the impact of a topology change on the self-organization: the algorithms must quickly update their information and converge to a legal state. In particular, we measured the impact of the addition/deletion of a node. When a node is inserted in the network, the backbone topology is update in less than 1 second. So, we stressed the protocol in inserting simultaneously two nodes (A and B) to a network of 2 nodes (C and GW). The final network consists in a line A -B -C -GW . 2.6 seconds are necessary so that the new nodes determine if they must be backbone nodes or not (tab. I). Additionally, the backbone tree links are valid 0.6 seconds later. Finally, the self-organization structure updated all the information about parents, children in the backbone 4 seconds after the nodes insertion. We say that the backbone is in degraded-mode if the backbone mesh is connected but not the backbone tree (all radio links must be used, not a subset).

Step Then, we set up a squared network of 4 nodes and shutdown the backbone member neighbor of the gateway: the node 2 hops far from the gateway becomes disconnected, the backbone must be reconstructed, the other neighbor of the gateway must in particular become a backbone node. The disappearance is detected after 4.0 seconds, the timeout of an hello (tab. II). The reconnection step lasts on average 1.2 seconds (reconnection packets transmission,. . . ). Finally, the self-organization proves that it functions normally less than one second later. The whole reconnection procedures lasts on average 7 seconds. Naturally, this convergence time can be largely reduced if a more efficient disappearance detection is available (MAC layer notification, very frequent hellos. . . ). Other scenarios were studied (for example when 2 nodes disappear simultaneously) and present similar convergence time, but the details are not presented here because of lack of space.

Step Convergence time (in s) Disappearance detection 4.0 Valid backbone parent 6.2 Non degraded mode 7

TABLE II CONVERGENCE TIME WHEN A NODE DISAPPEARS

B. Ping

Firstly, we measured the end-to-end delay according to the packet size (fig. 4) from each node to the gateway. We plotted the min/max/average delays. To evaluate the accuracy of the estimation, the errors were plotted for a list of 10 experiments. When the packet size increases, the delay also increases: the transmission requires more time since the radio bandwidth remains fixed. Moreover, the store-and-forward approach increases this effect: the packet must be integrally received before it can be forwarded. Besides, we can remark that average, minimum and maximum delays are very close: the jitter is reduced. Since the topology is in this part static, we compared the performances of SOMoM with static routing (tab. III). However, a few intermittent radio links impact the performances: routes should be reconfigured dynamically so that the network offers the best performances. We can note that the delay is almost the same with SOMoM and with a static routing whatever the pair in communication is. SOMoM, in spite of a dynamic route discovering, allows to obtain delays similar to a static route configuration. SOMoM presents an high flexibility to topology changes without any impact on the delay. In some cases, we can even note that SOMoM seems more efficient: the protocol adapts its route to the real quality of the radio links, discovering other routes when a radio link becomes weak. We can note that the node 5 which has only weak radio links presents the highest delay.

C. TCP throughput

Since TCP flows represent the most important part of the Internet traffic, we measured the reachable throughput with iperf (fig. 5) for flows of 8 seconds. We remarked that when a large data flow is forwarded, collisions are created between the different data and control packets. This behavior creates some route instabilities since for example hello packets are dropped and a node can consider erroneously that one of its neighbors is dead. A QoS mechanism for IEEE 802.11 would avoid such a behavior. A duration of 8 seconds presents a good trade-off. We can remark that the throughput increases when the packet size is longer. Indeed, some control frames (acks, backoffs. . . ) are required whatever the packet size is. Thus, a long packet size allows to reduce the bandwidth ratio used for control. Moreover, we can distinguish two flow types: the one hop flows offer the highest throughput, and multihop flows propose a lower throughput. However, 2 and 3 hops flows do not differ importantly. A multihop wireless Internet connection seems efficient. We measured the TCP throughput for every sourcedestination pairs (fig. 6). We can remark that the radio links present very different throughputs: one radio link (the bar of one hop flows) exhibits a throughput of 700 kbps while another one presents only a throughput of 100 kbps because of temporary obstacles. Besides, multihop connections present a lower throughput which is logical since the flow must be forwarded. However, the flows of 2, 3 or 4 hops present similar througputs. Thus, the throughput is quite scalable according to the route length. In other words, SOMoM discovers stable routes, without too frequent breaks.

D. UDP throughput

Then, we measured the maximum achievable throughput with a UDP flow. Since UDP is not reliable, we assume that a flow is achievable if more than 95% of the packets are delivered to the destination. We used here also the iperf tool to measure the UDP throughput. Since we obtained very similar results, the graphs are not reported here. We can just report that an optimal packet size exists to optimize the UDP throughput. When the packet size is large, collisions seem Throughput (in Kbps)

Route length (in hops) Fig. 6. TCP throughput according to the route length to occur frequently and decrease the global throughput. UDP seems to react less efficiently than TCP to collisions.

E. Route discovering latency

Finally, we measured the delay required to discover a new route from the gateway (tab. IV). For a route of 3 hops, 800 milliseconds are on average required for a ping (route request triggering, potential retransmissions, route reply reception, round trip of the ping). However, a route discovering occurs seldom: when the node initiates itself a communication, an inverse route is automatically created in the cache of the intermediary routers. Moreover, this delay is required only for the first packet of a flow, the route being subsequently dynamically maintained.

F. Mobile node

Then, we introduced a mobile node in the hybrid network. This node is moving from one extremity of the network to the Access Point (cf. map in figure 3). We measured the TCP throughput according to the displacement of the node. At the beginning, the mobile node is at the extremity of the network and the radio link is weak: this explains the fluctuating throughput. When the node stops, the throughput is more stable. When the node is changing its parent in the self-organization, the throughput decreases logically: routing reconfigurations are required, disturbing TCP. Finally, when the mobile node is neighbor of the Access Point, the throughput is maximal since it is a single hop flow. SOMoM reacts well to topology changes, updating continuously its knowledge.

V. CURRENT ISSUES IN TESTBEDS FOR HYBRID NETWORKS

This testbed constitutes a first step toward the improvement of protocols for ad-hoc and hybrid networks, and corroborates Fig. 7. TCP throughput of a mobile node the efficiency of protocols based on a self-organization. However, the experiments allowed to exhibit some key problems. Firstly, a real-world radio medium presents severe differences compared to simulations: radio links are heterogeneous, presenting different throughputs. Thus, an ad-hoc protocol must use a metric of link efficiency to improve the global performances, like in [START_REF] De Couto | Performance of multihop wireless networks: shortest path is not enough[END_REF]. Moreover, the timescale of route changes must be adjusted to the timescale of a radio link. For example, it is useless to change a route after 3 seconds if a radio link is changing every second. Besides, some radio links are instable, their radio range being not binary: some long links allow to deliver at most x% of the packets. If a hello is received, the radio link is considered valid although it presents a poor throughput. Thus, we modified SOMoM so that a radio link is considered valid if at least two consecutive hellos were received. Although the testbed is constituted by similar nodes, some unidirectional radio links can appear because of antenna orientation, bad connectors. . . . Hence, unidirectional and bidirectional links must be distinguished by the protocol (like SOMoM does). The environment highly influences the radio topology. In other words, the Unit Disk Graphs are a bad model of ad-hoc networks: two nodes can be near without having a radio link with each other. The dimensioning of a mesh network must in consequence carefully be conceived. Finally, tests are time-consuming. Automatized tools must be deployed and clocks must be synchronized. However, the control traffic for the measurements must avoid to disturb the experiments. Thus, a out-of-band management should be available (via wired connections, or different wireless NIC and radio channels)

Besides, we point out several key problematic properties of IEEE 802.11. They must be addressed to set up an efficient radio multihop network. IEEE 802.11 presents poor performances in an ad hoc network, under-estimating the bandwidth. A new MAC layer must consequently be proposed. Moreover, IEEE 802.11 does not offer priorities among flows. Thus, an heavy data flow will collide with control packets, disturbing the normal functions of a protocol, as mentioned above. Routes will be broken, creating instabilities in the throughputs Besides, IEEE 802.11 does not present the same rate in unicast and broadcast (as exhibited in these experiments and earlier in [START_REF] Lundgren | Coping with communication gray zones in ieee 802.11b based ad hoc networks[END_REF]). Thus, control packets sent in broadcast are transmitted farther. A node can consider a node neighbor although it is not able to send or receive a data packet in unicast

VI. CONCLUSION & FUTURE WORK

This article presented the deployment of a testbed to measure the performances of hybrid networks in a real environment. In particular, we implemented a self-organization protocol and the routing protocol benefiting from this scheme, SOMoM. We described the complete software architecture: this explanations represent a guide to implement protocols in a flexible manner in a Linux testbed. The integration of ad hoc networks in the Internet is fully operational, offering a spontaneous multihop extension of IEEE 802.11 networks. The performance evaluation demonstrates the relevance of a self-organization scheme and of SOMoM. Besides, we detail some specific issues of IEEE 802.11 in multihop radio testbeds, presenting problems of stability and QoS. A new MAC layer particularly adapted to multihop wireless networks must be proposed to optimize the performances.

As a future work, we plan to deal with multi-interfaces hosts: Bluetooth, WIFI, Ethernet interfaces must be seamlessly integrated, forming a wide ad-hoc network, offering a transparent connection to the Internet across multi technology links. Besides, more nodes must be introduced to test the scalability.

  For example, a node can have the IP address 192.168.1.15 with the network netmask 255.255.255.255 and the somom-netmask 255.255.255.0. Other ad-hoc nodes will be configured in the IP range 192.168.1.1-254.

Fig. 2 .

 2 Fig. 2. Software architecture of the protocol

Fig. 3 .

 3 Fig. 3. Map of the testbed

Fig. 4 .

 4 Fig. 4. End-to-end delay according to the packet size

Fig. 5 .

 5 Fig. 5. TCP throughput according to the packet size


Fabrice Theoleyre

Rabih Tout

Fabrice Valois

New metrics to evaluate mobility models properties

Keywords: mobility models, characterization, metrics, taxonomy

Mobility models allow to mimic the behavior of mobile nodes when MANET performances are evaluated via simulations. Nevertheless, simulations results are strongly correlated with the mobility model. In this work, we introduce new metrics in order to characterize any mobility model. These metrics reflect the nodes distribution, the local topology changes, the repetitive behavior of a model,etc. They allow in consequence to characterize mobility models, and particularly to introduce a taxonomy based on objective and quantitative criteria. Using these metrics, we characterize some individual and one group mobility models.

I. INTRODUCTION

Mobile Ad Hoc Networks (MANET) are literally networks ready to work. All mobile terminals can communicate with other nodes via wireless communications. The network must function autonomously, without any human intervention. Many protocols were proposed to deal with these networks [START_REF] Chlamtac | Mobile ad hoc networking: imperatives and challenges[END_REF] and their performances were mainly evaluated through simulations. The perfect way to mimic the nodes mobility is to inject real movements in the simulation. In this way, we can efficiently evaluate the performances of one protocol in a given application. However, MANET are currently rarely deployed, and no MANET traces are available. Thus, many analytical mobility models were proposed in order to simulate the displacement of a node or of a group of nodes. Since ad hoc networks are promised to a large spectrum of utilization, many different mobility models exist in the literature ( [START_REF] Camp | A survey of mobility models for ad hoc networks research[END_REF] presents a detailed survey). Since these models are very different, they greatly impact the performance evaluation.

The main contribution of this work is the proposition of new metrics to discriminate and classify mobility models. We introduce metrics to evaluate the network dynamicity, the neighborhood persistence and the homogeneity of the network related to the mobility models by themselves. Consequently, we can propose an objective taxonomy of mobility models, based on quantitative metrics. These metrics can constitute a framework to determine the behavior of a new mobility model, and eventually to determine its redundancy with another mobility model. In the same way, from real MANET testbed and using these metrics we can identify the most suited analytical mobility model. It could be helpful to evaluate the performances through simulations. The reader can verify that these metrics are independent from any protocol. In particular, they do not integrate routing metrics since we want to characterize only mobility models which impact any upper layer, and not only the routing layer (services discovering, mobility management or the MAC layer for example). This work is organized as follows. Related works are introduced in II. Section III presents the metrics to classify and discriminate mobility models. In particular, new metrics characterizing the network dynamic and distribution are detailed. A performance evaluation is presented in section IV. Finally, section V concludes this work nd gives some perspectives.

II. RELATED WORK

The simulations represent the most common tool to evaluate the performances of new protocols in MANET. Thus, many mobility models were proposed to mimic the behavior of independent mobile nodes. [START_REF] Camp | A survey of mobility models for ad hoc networks research[END_REF] gives an overview of these models. We will present here a short overview of the main mobility models, and will give a taxonomy to classify all these models. We will verify the relevance of this taxonomy to discriminate different mobility models in the performance evaluation, in section IV.

A. Individual models

MANET are spontaneous networks: a node can freely enter in the network, and leave it at any time. Individual mobility models consider that all the nodes are independently mobile: in other words, a rule could be applied independently to each node to model its displacement. We chose to differentiate memory less and smooth models.

1) Memory less models: In memory less models, the direction and speed chosen by a node at the time t is completely independent from the previous values at the time t -∆(t). The random walk is a very simple model: a node chooses randomly a direction (between 0 and 2Π) and a speed (between V min and V max ). Then, it is moving during the duration t or the distance d. Then, the node chooses random new values (fig. 1(a)). According to [START_REF] Sanchez | Anejos: A java based simulator for adhoc networks[END_REF], this model was first introduced by Einstein in 1926.

The random waypoint is the largest used model: a node chooses a random destination (in the simulation area) and speed (between V min and V max ). When the node reaches this destination, the algorithm reiterates after a pause. This mobility model was first introduced to evaluate the performances of DSR [START_REF] Johnson | The dynamic source routing protocol for mobile ad hoc networks (DSR)[END_REF], a routing protocol for ad hoc networks (fig. 1(b)).

The random direction mobility model was proposed to overcome the problems of the random waypoint model, in order to distribute more uniformly the points in the simulation area. A node chooses a random speed (between V min and V max ) and direction (between 0 and 2Π) and changes these values only when it reaches the boundaries of the simulation area. Eventually, the node takes a pause time before moving (fig. 2(a)).

2) Smooth models: In the memory less models, the mobility pattern is very chaotic. Smooth models try to create a more realistic behavior. In the boundless mobility model [START_REF] Haas | A new routing protocol for reconfigurable wireless networks[END_REF], the position (x,y) and speed v at time t + ∆(t) are correlated with the speed and position at time t. More precisely, the speed (resp. direction) could change according to a small difference ∆(v) • ∆(t) (resp. ∆(Θ) • ∆(t)). The Gauss-Markov model [START_REF] Liang | Predictive distance-based mobility management for pcs networks[END_REF] is similar to the boundless mobility model since position and speed are time-correlated. However, the variations respect a gaussian distribution.

The markovian random path [START_REF] Chiang | Wireless networks multicasting[END_REF] proposes to use a markov chain to model the mobility: one chain for the horizontal displacement, and another chain for the vertical displacement. A transition matrix allows to configure the probability to change the directions when another value must be chosen.

Finally, the city section model [START_REF] Davies | Evaluating mobility models within an ad hoc network[END_REF] allows to model the mobility of a node in a urban environment. The node will uniquely move along some particular horizontal and vertical paths. Eventually, a different speed could be specified for each street.

B. Group models

Some articles try to model the mobility of groups of nodes. These models are widely based on the existence of reference points: one or several nodes are moving in a small area, surrounding a common reference point.

In the column model [START_REF] Sanchez | Anejos: A java based simulator for adhoc networks[END_REF], several reference points are defined, forming a column. This column is moving linearly according to the same individual mobility model: all the reference points keep on constituting a column. A node corresponds to each reference point. Eventually, a node can moves around its reference point according to a different mobility model (but it must stay close to this reference) (fig. 3(a)). This model is widely used to model the displacements in a battlefield. The nomadic community model [START_REF] Sanchez | [END_REF] follows a similar approach: each community is represented by a reference point (fig. 3(b)). The reference is moving according to a smooth individual mobility model. Then, all other nodes are moving according to the random waypoint model, in a small area surrounding this reference point. This could model well the displacement of a group of turists.

C. Properties

Several analysis were conducted to study the behavior of different mobility models. Since the random waypoint model is the most used model, it focused the efforts. [START_REF] Yoon | Random waypoint considered harmful[END_REF] proves that the average speed decreases constantly, mainly because the node can choose a null speed, and thus never reaches the destination, blocked in a static state. [START_REF] Navidi | Improving the accuracy of random waypoint simulations through steady-state initialization[END_REF] presents a method to accelerate the convergence of the random waypoint mobility model in re-injecting stationary values. [START_REF] Bettstetter | Properties of the random waypoint mobility model: epoch length, direction distribution, and cell change rate[END_REF] presents a stochastic study, proving in particular that the nodes are mainly present in the center of the simulation area.

III. METRICS TO CHARACTERIZE MOBILITY MODELS

Many mobility models were already and keep on being proposed. Our goal is here to focus on how to discriminate different mobility models. These quantitative and objective metrics will allow to discriminate mobility models and eventually to verify the relevance and originality of a newly proposed model. Routing is a main application in MANET. Consequently, [START_REF] Ng | Impact of group mobility on ad hoc networks routing protocols[END_REF] chose to focus on routing efficiency metrics like the delivery ratio. However, these metrics are not directly related to the mobility model and should be, according to us, improved.

A. Existing metrics

We distinguish two types of existing metrics: the metric computed for each node according only to its own properties, and the metrics related to the interaction between different nodes.

1) Individual metrics: We can model the ad hoc network with a graph: a vertex corresponds to each node and there exists an edge between two vertices if the corresponding nodes can communicate with each other. Usually, we use the notation G(V,E): G is the graph with the set of vertices V and the set of edges E. If we consider only bidirectional communications, we can measure the degree of each node, i.e. the number of edges: it represents the number of radio neighbors (like [START_REF] Uehara | Impact of mobility metrics on routing protocols for mobile ad hoc networks[END_REF]), impacting on the overhead for example. If the graph is asymmetrical, we can distinguish the inner and outer degree.

Besides, we can directly extract values like the direction, the absolute speed and the position of each node.

2) Complex metrics: More complex metrics are useful to extract the common behavior of the network. [START_REF] Gerharz | Link stability in mobile wireless ad hoc networks[END_REF] measures the link duration, i.e. the average time before a radio link is broken. Eventually, thanks to this metric, we can compute the average duration of a path in the network (the probability of a path break being the product of each individual probability). If the ad hoc network is used for routing, this metric can reflect directly the reliability of a given route. [START_REF] Bai | IMPORTANT: a framework to systematically analyze the impact of mobility on performance of routing protocols for adhoc networks[END_REF] proposes to estimate the correlation of the speed of a node for different time t and t + ∆(t), called the degree of temporal dependence. This reflects the smoothness of a mobility model. The degree of temporal dependence is the product of the cosine formed by the angle of both directions with the ratio of both absolute speeds. More formally, let v(a) and v(b) the speed vectors of the same nodes at different instants (without lake of genericity, let v(a) < v(b) ). The degree of temporal dependence is:

v(a) • v(b) v(a) • v(b) • v(t + ∆(a) v(b)
This formula is also useful to describe the correlation between the speed of two different nodes, metric called the degree of spatial dependence.

B. New metrics

However, these metrics are not reflecting well all the mobility models properties. In particular, the network dynamicity is not completely represented. Indeed, [START_REF] Bettstetter | Properties of the random waypoint mobility model: epoch length, direction distribution, and cell change rate[END_REF] demonstrates for example the non-uniform distribution of the nodes in the simulation area with the random waypoint mobility model. However, none of these metrics could express such a property. Consequently, we introduce here new metrics to fully characterize the behavior of a mobility model.

1) network diameter: If we model a MANET with a graph, we can measure the graph diameter, i.e. the maximum distance in hops between two nodes. More formally, let lg(a, b) be the minimum number of edges required to find a connected path between a and b.

Then, diameter = max{lg(a, b)} ∀(a,b)∈V 2
The network diameter is representative of the average length of the paths of the network. Thus, a mobility model which creates a low diameter will for example improve routing performances, minimizing interferences. In particular, we can verify that the network diameter represents a stable value, not changing importantly when the nodes are moving.

The reader can remark that, although this metric can reflect routing performances, it is related only to the mobility model by itself, independent from any particular protocol.

2) neighborhood instability: The stability of the neighborhood impacts several protocols. For example, when a node offers a service to its neighbors, an important neighborhood instability will decrease the reliability. We estimate the neighborhood instability as the number of radio link apparition and disappearance. It is normalized by the total number of radio links.

It is important to monitor the distribution of the neighborhood instability: with an high probability, a few nodes, very mobile, will know an important instability whereas other nodes, more statical will have an acceptable instability. In particular, a smooth model will tend to limit the neighborhood instability. On the contrary, a memory less will introduce high variations.

3) nodes distribution: We propose to measure the geographical nodes distribution. We represent graphically the node density in some small surface areas. This allows to have a snapshot of the nodes distribution. In particular, we can verify that the distribution is homogeneous, and not concentrated around the center of the simulation area, like with the random waypoint model.

More precisely, we cut the network in a regular grid of side c. Then, we count the number of nodes lying in each case. This number gives a color level to represent graphically the density in this particular cell. This tool will give us the opportunity to verify that a mobility model does not present side effects. This also allows to differentiate heterogeneous and homogeneous models, i.e. models were the nodes are concentrated on restricted areas.

4) repetitive behavior:

A realistic movement pattern is often repetitive. For example, a person will go working during the morning and come back home after his work. It could be interesting to extract a quantitative metric, related to the property of a node to exhibit the same movement after a given time.

To evaluate the repetitive behavior of a mobility model, we measure the average ratio of time during which a node is located inside the transmission range area of its initial position (cf. fig. 4). An important value of the repetitive metric means that the mobility model exhibits an important repetitive behavior. It could be the case if the direction and speed remain unchanged, or if the node is mobile only around a short distance from the initial position. [START_REF] Watts | Collective dynamics of smallworld networks[END_REF] to measure the small-world graph property of a node. We propose to re-use this metric to discriminate mobility models. The clustering coefficient is the ratio of the radio links among neighbors and the number of neighbors.

More formally, let N (u) be the set of neighbors of the node u. The clustering coefficient is defined as:

v∈N (u) |{x ∈ N (v)}| N (u)
This clustering coefficient is related to the network redundancy. Indeed, when a node presents an high clustering coefficient, this means that its neighbors have many radio links with each other. Thus, this node is redundant: a route can, with an high probability, pass through its neighbors without a path length increase.

IV. MOBILITY MODELS CHARACTERIZATION

In this section, we present a set of simulation results allowing to discriminate and classify different mobility models.

A. Methodology

We use the OPNET Modeler tool in order to simulate the MANET. We implemented six individual and one group mobility models: the random way point, random walk, random direction, boundless, Gauss-Markov, restricted random way point and the nomadic community (cf. [START_REF] Camp | A survey of mobility models for ad hoc networks research[END_REF]). We measured the metrics (in particular the five new metrics described above) presented in the section III. We run a set of at least 10 simulations for each result presented here. Moreover, the 95% confidence interval is systematically reported.

B. Results

We mainly investigated the neighborhood behavior (chaotic or stable), the link duration, the repetitive behaviors of the mobility models, and the nodes distribution in the simulation area. The results are deeply explained, giving ideas to introduce an objective taxonomy. By default, we assume a simulation area of 1000*1000m and a simulation time of 1000 seconds. The radio range is assumed to be equal to 100m.

1) Neighborhood dynamic: The performances of mobile ad hoc networks are linked to the persistence of the neighborhood. For instance, the more the neighborhood of a node is stable, the more routing protocols are efficient: the network is more stable and the routes break less often. Figure 5 illustrates the impact of the network cardinality on the neighborhood stability. There are 3 kinds of mobility models: i) the smoothest models are the random direction and a group model (nomadic community). For a group model, it is clear that the neighborhood is stable because the main neighorhood of a node is restricted to the group. For the random direction, this result may appear more surprising but it is due to the bound effect: when a bound is reached, a node waits a time and then, changes of direction and go to another bound. If the pause time is important, the nodes have an high probability to be on the simulation area boundaries, stabilizing the topology. ii) The second part of mobility models exhibit a chaotic behavior: the neighborhood is not stable. This is the case for the random walk, the Gauss-Markov, etc. iii) Finally, the random way point and the restricted way point exhibit a compromise behavior. In conclusion, if we fix the parameters of a given routing protocol, ir performances will be, with an high probability, better with the random waypoint than with the random walk mobility model. And the results may be better if a random direction is used. Clearly, the results of a performance evaluation of a routing protocol are greatly impacted by the mobility model. It is more a miscroscopic point of view. In fact, as it is shown on figure 7 the link duration is not impacted by the network cardinality for all the mobility models. Indeed, when the number of nodes increases, more radio links appear, increasing the absolute changes in the neighborhood. However, the mean duration of a particular radio links remains unchanged since the displacement does not change either. But the link duration decreases drastically when the speed increases (figure 8). Indeed, when the speed increases, two nodes which are not moving in the same direction will quickly break their common radio link. Consequently, the link duration decreases drastically when the absolute speed increases. For example, this means that a services discovering protocol must re-trigger a new discovering very oftenly when the speed increases. 3) Repetitive behavior: In the repetitive behavior metric, we want to investigate if the mobility models lead to a repetitive behavior of node (figure 9). Thanks to the repetitive metric, we want to explore the reproctibility property of a given mobility model: does a node has an high probability to move according to a repetitive displacement pattern. It means, considering the initial position of a node and a service area around this initial position, during the simulation, what is the ratio of time during which a node stays around this initial service area? The boundless appears the less repetitive: this result will be confirmed by the next parameter (the probability of density is uniform with this mobility model, as shown below). The most repetitive model is the random walk model: a node has an high probability to stay around its initial position, limiting the displacements. The nomadic community model is quite an exception: a group of nodes will stay around the leader. The others mobility models present a very close repetitive property. The Markov mobility model (and also the Boundless, not represented here due to the lack of place) is the most uniform mobility model (fig. 10(a)): a node has no privileged location in the simulation area. On the contrary, the random waypoint (fig. 10(b)) exhibits a centralized behavior in the center of the simulation area: clearly, this will lead to important density in the center of the simulation area, creating an heterogeneous network.

Figures 11(a) and 11(b) illustrate the nodes distribution in the case of the random direction mobility model and the random walk, respectively. These two models appear homogenous in terms of nodes distribution over the simulation area. The simulation area boundaries represent a particular case for the random direction mobility model: a node must implement a pause when it reaches the simulation borders. However, if the pause time is null, the mobility model presents an uniform distribution. MANET protocols are often evaluated through simulations, requiring mobility models which mimic the real movements of each node. Since MANET are promised to a wide spectrum of utilizations, many mobility models were proposed in the literature, presenting different behaviors. In particular, the performance evaluation of a MANET protocol will be widely impacted by the model. We proposed here five new metrics to discriminate them, introducing an objective and quantitative taxonomy. This characterization allows to understand deeply the behavior of some mobility models. Moreover, this framework allows to extract the most relevant mobility model for a particular application. In this way, the performances evaluation via simulations will be the most relevant as possible.

As a future work, we want to explore some new additional metrics to characterize dynamical graph properties to complete this framework. Moreover, we would like to validate this approach: we plan to set up an experimental MANET in order to collect statistics about the displacement of users. Then, we should obtain the mobility model most suitable to mimic this application, thanks to the metrics presented in this article. Finally, it could be relevant to propose new mobility models when no mobility model presents some expected characteristics (for example an important link duration with an high absolute mobility and an important clustering density).

Fig. 1 .

 1 Fig. 1. Mobility patterns of the random waypoint and random walk models

Fig. 2 .

 2 Fig. 2. Mobility pattern of the random direction and boundless models

Fig. 3 .

 3 Fig. 3. Mobility pattern of the different group mobility models

Fig. 4 .

 4 Fig. 4. Repetitive metric 5) clustering coefficient: The clustering coefficient was firstly introduced by Watts & Strogatz[START_REF] Watts | Collective dynamics of smallworld networks[END_REF] to measure the small-world graph property of a node. We propose to re-use

Fig. 5 .

 5 Fig. 5. Neighborhood stability: influence of network cardinality

Fig. 6 .

 6 Fig. 6. Neighborhood stability: influence of node's speed

Fig. 7 .

 7 Fig. 7. Link duration: influence of network cardinality

Fig. 8 .

 8 Fig. 8. Link duration: influence of node's speed

Fig. 9 .

 9 Fig. 9. Repetition: impact of the mobility 4) Nodes distribution: Finally, we studied the distribution of a nodes in the simulation area. In particular, we verified that the mobility models do not present side effects. The figures (10(a), 10(b), 11(a), 11(b)) illustrate this property. When a case of the grid is red, this means that the probability of density for this particular case is important.

  Fig. 10. Gauss-Markov and Random Way Point nodes distribution

Fig. 11 .

 11 Fig. 11. Random Walk and Random Direction nodes distribution


Cezar Mbiethieu
email: mbiethieucezar@gmail.com

Norbert Tsopze

Engelbert Mephu-Nguifo

CovSegNet: An Automated COVID-19 lesion segmentation from CT scans using Deep Learning Techniques

Keywords: COVID-19, CT scans, Deep Learning, U-net, SubSampling, Attention mechanism

The coronavirus disease (COVID-19) pandemic has led to a devastating effect on the global public health. Computed Tomography (CT) is an effective tool in the screening of COVID-19. It is of great importance to rapidly and accurately segment COVID-19 lesions from CT images to help diagnostic and patient monitoring. In this paper, we propose a U-net based segmentation network using attention mechanism. As not all the features extracted from the encoders are useful for segmentation, we propose to incorporate an efficient attention mechanism, to an U-Net architecture to re-weight the feature representation channel-wise to capture rich contextual relationships for better features representation while maintaining a better time complexity. In addition, a novel subsampling techniques for CNN is introduced to significantly increase the amount of information kept by feature maps through subsampling layers and we finally use a focal Tversky loss to deal with small lesion segmentation. The experiment results, evaluated on a COVID-19 CT scans segmentation dataset where 3250 CT slices are available, demonstrate the proposed method can achieve an accurate and rapid segmentation on COVID-19 segmentation. The method takes only a fraction of second to segment a single CT slice.

I INTRODUCTION

The COVID-19 pandemic caused by the virus named SARS-CoV-2 identified in 2019, has been spread all over the world and has caused a devastating effect on the global public health. Researches have shown that the coronavirus is spread through droplets and virus particles released in the air when an infected person breathes, talks, laughs, sings, coughs or sneezes. The traditional method used to diagnose and evaluate the disease is named real-time polymerase chain reaction (RT-PCR) which assays the sputum; it has a high specificity, but is time consuming, laborious and has been reported for high false negative rates Liang [START_REF] Liang | Handbook of covid-19 prevention and treatment[END_REF]. Chest Computed tomography (CT) and Chest X-ray are two imaging approaches used to detect certain characteristics manifestations in the lung infected by COVID-19. CT is more sensitive, especially for early stage of infection. Chest CT is considered as a low-cost, accurate and efficient method diagnostic tool for early screening and diagnosis of COVID-19. It can be used to evaluate how severely the lungs are affected, and how the patients disease is evolving, which is helpful in making treatment decisions. The evaluation of localization and geometric features of infection area could provide adequate information of disease progress and help doctors make better treatment.

One of the most widely used method to segment region of interest(ROI) in medical images is a deep learning system called U-net presented by Ronneberger, Fischer, and Brox [START_REF] Ronneberger | U-Net: Convolutional Networks for Biomedical Image Segmentation[END_REF] which has an architecture in "U" form based on encoder -decoder that captures low level and high level resolution features at the encoder phase and combines with the semantic features extracted at the decoder phase using skip connections. However, the features captured from the encoder part are not all useful for the segmentation task. Therefore, it is necessary to find an effective way to fuse features of the encoder and that of the decoder; we focus on the extraction of the most informative features for segmentation. Recently, incorporation of channel attention into convolution blocks has attracted a lot of interests, showing great potential in performance improvement of deep CNNs which extract the most informative features for segmentation. Some of the representative methods include squeeze-and-excitation networks (SENet) of Hu, Shen, and Sun [START_REF] Hu | Squeeze-and-Excitation Networks[END_REF] and it variants, which learns channel attention for each convolution block, bringing clear performance gain for various deep CNN architectures. Although these methods have achieved higher accuracy, more often, they bring higher model complexity and suffer from heavier computation burden due to complex architecture. Through the deep analysis of different types of layers in a deep learning architectures, we discovered that we usually skip some important features which could significantly increase the amount of information kept by the feature maps, therefore improving the models accuracy.

To address the above issues, we focus our research on finding a method which will establish a tradeoff between a better performance and a low model complexity cost. In this paper, we propose CovSegNet (Covid-19 Segmentation Network), a deep learning based segmentation system made with improved convolution and pooling layers to significantly increase the amount of information kept by the feature maps; we also proposed to used an improved channel attention mechanism which reduces the complexity of the segmentation models while maintaining their accuracy to segment the covid-19 lesions. We revisit the existing layers in deep architectures which perform subsampling and the existing attention mechanism in order to tackle their limitations in medical image segmentation. Our contributions include:

1. The proposition of a novel subsampling technique in encoder-decoder models to significantly increase the amount of information kept by the feature maps. 2. We propose a novel attention mechanism based Deep CNN architecture to segment COVID-19 CT scans. 3. We built a new U-net based architecture which integrates our proposed subsampling and attention mechanism in the classical skip connection, and also we replace the classical subsampling by our proposed lighter subsampling module. The rest of this paper is organized as follows. In section 2, we provide an overview of the segmentation models and some related literature using attention mechanism. Section 3 represents our proposed CovSegNet. Section 4 will describe the dataset and the experiments to demonstrate the potential power of our proposed method. Finally, we will present the conclusion in section 5.

II RELATED WORK

Most cutting-edge segmentation algorithms are based on deep learning approaches, which are algorithms that feature powerful fitting capacity and require no laborious preprocessing on input data. For example, U-Net of Ronneberger, Fischer, and Brox [START_REF] Ronneberger | U-Net: Convolutional Networks for Biomedical Image Segmentation[END_REF] and its variants were used to segment lung tissues in chest CT scans. However, those models suffer from the fact that, not all the features extracted from the encoder are useful for segmentation task at hand. Thus, attention mechanisms guide the model to emphasize the most salient features, avoiding useless features that are not beneficial.

With the development of deep neural networks, attention mechanism has been widely used in diverse application domains. It is a module added at the top of a convolution layer in order to guide the model to emphasize the most salient features, avoiding useless feature that are not beneficial for the given task. Related algorithms typically refine feature maps in spatial dimension, channel dimension or both. To focus on the most informative features for segmentation using U-Net, researchers proposed to insert attention module in the skip connection of U-net. For example, Oktay et al. [START_REF] Oktay | Attention U-Net: Learning Where to Look for the Pancreas[END_REF] proposed attention gate modules (AG) that are incorporated into the skip connections of the encoder-decoder network, using the information of the decoder feature to better guide information to the encoder feature. Hu, Shen, and Sun [START_REF] Hu | Squeeze-and-Excitation Networks[END_REF] introduced a Squeezeand-Excitation module, where global average pooling is performed on input features to produce channel-wise attention which highlight useful channels and that outperforms the methods in ILSVRC 2017 image classification. Roy, Navab, and Wachinger [START_REF] Roy | Concurrent Spatial and Channel 'Squeeze & Excitation' in Fully Convolutional Networks[END_REF] introduced to use both spatial and channel block (scSE), which concurrently recalibrates the feature representations spatially and channel-wise, and then combines them to obtain the final feature representation. Some of the above mentioned methods have been adjusted to segment COVID-19 infections. Zhou, Canu, and Ruan [START_REF] Zhou | Automatic COVID-19 CT segmentation using U-Net integrated spatial and channel attention mechanism[END_REF] segmented COVID-19 from CT to help diagnostic and patient monitoring while incorporating spatial and channel attention mechanism to U-Net architecture to capture rich contextual relationships for better feature representation. Li et al. [START_REF] Li | Using Artificial Intelligence to Detect COVID-19 and Community-acquired Pneumonia Based on Pulmonary CT: Evaluation of the Diagnostic Accuracy[END_REF] developed a COVID-19 detection neural network (COVNet) to extract visual features from volumetric chest CT exams for distinguishing COVID-19 from Community Acquired Pneumonia (CAP).

III METHOD

In this section, we will explain in detail the proposed CovSegNet.

Overview of CovSegNet architecture

The figure 1 shows the general architecture of the network, which is basically the U-net architecture with additional blocks including the attention mechanism module which replaces the classical skip connection. The traditional subsampling blocks (convolutional layers with stride, pooling layers) are replaced by their corresponding multisampling blocks. In figure 1, Multi_conv2 represents the improved version of 2D convolution layer with stride of 2 and a kernel of size k=3; Multisample Maxpooling is the improved version of maxpooling layer; EATT is the attention mechanism block.

Novel Subsampling technique: Multisampling

Deep learning architectures employ subsampling techniques to scale down spatial dimension lengths of the feature maps in order to increase the global receptive field of neurons in proceeding layers. Some subsampling layers include: pooling layers, convolution layers with stride, dropout, normalization. The spatial resolution r t of a feature map after passing through a CNN layer is: r t = r t-1 /k d where r t-1 is the resolution of the feature map before the subsampling layer is applied, k is the stride length, and d is the dimensionality of the CNN (1D, 2D or 3D) . A two dimensions convolution layer (2D CNN) with a stride length of 2 reduces spatial resolution by a ratio of 4, bottlenecking the capacity of proceeding feature maps. By implementing the following subsampling strategy, we preserve the benefits of traditional subsampling layers while generating a more informative forward pass producing higher-resolution feature maps, better gradient updates for deep layers during training. We increase the number of samples taken from feature maps at subsampling layers and therefore preserve more information for late layers in the network. In the above figure 2(a), with the traditional subsampling, the feature map is divided into k × k sampling windows, then a convolution or pooling operation is lined up with the top left element of the window and the result is a single 2 × 2 feature window. Our idea is not to limit to lining up the convolution or pooling operation only to the top left element, but we have k 2 possibilities (representing all the elements of the k ×k window) of subsampling. One can decide to choose n samples of the k 2 , generalizing the spatial resolution of the feature map r t to higher dimension: r t = n. r t-1 k d . In figure 2(b), we show an example of 2D subsampling with kernel size of 2x2 where our choice of samples is made on the top left and bottom right element of the window. A 2x2x2 size feature map is then generated with n = 2. The multisampling is applied to all the subsampling layers and the output of the final convolution layer is made of many different submaps giving room to the post processing operations to generate feature vector (3D convolution can be used to combine features across the submap dimension).

Attention mechanism module

Description

The channel attention block of Hu, Shen, and Sun [START_REF] Hu | Squeeze-and-Excitation Networks[END_REF] (Squeeze Excitation block named SENET) is performed through Equation 1 below which shows that there is a dimensionality reduction which can reduce the model complexity, but it destroys the direct correspondence between channels and its weights. Equation 1 first projects channel features into a low-dimensional space and then maps them back, making correspondence between channel and its weight to be indirect.

z ′ = W 1 (δ(W 2 z)) (1)
with W 1 ∈ R C×C/r , W 2 ∈ R C/r×C being weights of two fully-connected layers and the ReLU operator δ(.). Wang [START_REF] Wang | ECA-Net: Efficient Channel Attention for Deep Convolutional Neural Networks[END_REF] demonstrates that avoiding dimensionality reduction helps to learn effective channel attention.

Inspired by Wang [START_REF] Wang | ECA-Net: Efficient Channel Attention for Deep Convolutional Neural Networks[END_REF], we propose to solve the above problem by avoiding the dimensionality reduction. The idea is to consider the following: Z = δ(W y) where W is a matrix with C × C parameters allowing to model cross-channel (C channels) interaction which is proven to be beneficial to learn channel attention, each row i of the matrix models the relation between the channel i and the remaining C-1 channels . Proceeding as such requires mass of parameters (C × C) leading to high model complexity, especially when the number of channel C is large.

An efficient and effective method to cross-channel interaction consists of modelling the relation between the channel i and its k neighbors, making an abstraction with other channels. This can be done by equation 2 proposed by Wang [START_REF] Wang | ECA-Net: Efficient Channel Attention for Deep Convolutional Neural Networks[END_REF]:

w = δ(C1D k (y)), (2)
where C1D indicates 1D convolution and k is the kernel size of the convolution.

The equation 2 is graphically represented by figure 3 named efficient attention mechanism (EATT) module, which only involves k parameters. The objective of the EATT module is to approximately capture local cross-channel interaction, the coverage of the interaction k can be determined automatically. A high value of k also increases the model complexity. After aggregating convolution features using global average pooling without dimensionality reduction, EATT module first performs 1D convolution then followed by a Sigmoid function to learn channel attention. Our EATT module is applied in U-net by replacing the skip connection by the EATT module as it is done by Hu, Shen, and Sun [START_REF] Hu | Squeeze-and-Excitation Networks[END_REF]. The architecture of our proposed attention module is shown in Figure 3.

IV EXPERIMENTATIONS

Dataset

We used a publicly available COVID-19 CT scans dataset published by Jun et al. [START_REF] Jun | Towards Efficient COVID-19 CT Annotation: A Benchmark for Lung and Infection Segmentation[END_REF], which contains 20 labeled COVID-19 CT lung scans volume ( with 3520 slices of 630x630 gray scale

Implementation details

In the medical community, the Dice Score Coefficient (DSC) is the most widespread metric to measure the overlap ratio of the segmented region and the ground truth, and it is widely used to evaluate segmentation performance. The Focal Tversky Loss function (FTL) addresses the limitation of Dice loss (DL) that penalizes false positive (FP) and false negative (FN) equally, which results in segmentation maps with high precision but low recall especially true and disadvantageous in the case of COVID-19 lesions which have small regions of interests. To this end, we used FTL to train the network to help segment the small COVID-19 regions.

The models are optimized with the Adam optimizer with learning rate of 5e-4 and batch size of 8. The models are trained until they cannot achieve further improvement and we use Early stopping strategy of size 15 to avoid model overfitting. The evaluation metrics used to validate the effectiveness of the proposed method are Dice similarity coefficient, Precision and Recall.

The execution is been done on a GPU Tesla P100-PCIE machine, with a memory size of 16GB.

The number of output channel is respectively 32, 64, 128, 256, and 512 at each level of the downsampling phase. We compared the performance of the proposed network with two publicly available models namely spatial -channel attention gate U-Net (scAG-U-net) Khanh, Dao, Ho, Yang, Baek, Lee, Kim, and Yoo [START_REF] Khanh | Enhancing U-Net with Spatial-Channel Attention Gate for Abnormal Tissue Segmentation in Medical Imaging[END_REF] and spatial-channel squeeze-excitation U-net (scSE-U-net) Roy, Navab, and Wachinger [START_REF] Roy | Concurrent Spatial and Channel 'Squeeze & Excitation' in Fully Convolutional Networks[END_REF] executed on the same computing platform. The evaluation metrics include both efficiency (i.e., network parameters, floating point operations per second and training speed) and effectiveness(Dice loss, recall and precision). Table 1 presents the evaluation metrics of different algorithms (our proposal and some state of art algorithms). The results presented in Table 2 show that the computer resources needed to execute CoviSegNet is lower than the the state-of-the-art counterpart.

Quantitative analysis

Detailed comparison among different models in our experiments is shown in Table 1. Our proposed model outperforms scSE-U-net and scAG-U-net in terms of training time, Dice, recall and precision metrics. As these models are identical in model encoder, it appears that the proposed attention mechanism contributes very well in lesion segmentation. The utilization of attention mechanism helps to accurately detect and segment infected tissues and ignore non infected tissues. The number of false positive is reduced, increasing the rate of the recall. The CovSegNet captures both the large and tiny visual structures which is useful to segment infection lesion with different size. It is noted that the number of parameters of our proposed model is lower than that of others attention U-net models presented in this work. More to that the computation cost is considerably reduced due to lower number of operations. The CovSegNet executed without the proposed subsampling techniques is fastest in terms of training time because of it low number of operations, but it is less accurate comparing to CovSegNet+Novel subsampling, which shows the efficiency of the novel subsampling techniques used in efficient features extractor.

Qualitative analysis

From the visualization of our results in Figure 5, we notice that our model outperforms other models. The models scSE-U-net and scAG-U-net provide good results but there are limited in segmenting lesions with non-smooth borders. Our proposed method is sensitive to non-smooth and tiny lesions as shown in Figure 4. Additionally, others methods tend to provide some segments which don't exist in the ground truth image.

VI CONCLUSION

We have presented in this paper, a novel segmentation network CovSegNet to efficiently segment COVID-19 lesions. The multisampling technique and the EATT module can easily be integrated into the popular U-Net architectures while minimizing the computational cost and increasing the performance of the model. By taking advantage of the information of the encoder and decoder features, our proposed attention mechanism captures efficient information about the location and the shape of the lesion. Experiments results show that the proposed method improves the segmentation results while reducing the model parameters and computation cost. We limited our study to the channel attention mechanism while expecting further works to be carried on the spatial attention mechanism that will allow to focus on the salient region that are beneficial to find the location of the object and determine the target structure of the of the object.

Figure 1 :

 1 Figure 1: Architecture of the proposed network. A CT slice is taken as input and the COVID-19 infected region is displayed as output

Figure 2 :

 2 Figure 2: Subsampling strategies

Figure 3 :

 3 Figure 3: Efficient attention mechanism

Figure 5 :

 5 Figure 5: Representative results from our dataset using different U-Net architectures.

Table 1 :

 1 Quantitative analysis of infection regions on our dataset. scAG-U-net refers to the model

	CoviSegNet +	90.73 ± 0.06 96.91± 0.02	95.90± 0.04
	Subsampling

proposed in Khanh, Dao, Ho, Yang, Baek, Lee, Kim, and Yoo

[START_REF] Khanh | Enhancing U-Net with Spatial-Channel Attention Gate for Abnormal Tissue Segmentation in Medical Imaging[END_REF]

and scSE-U-net is the model proposed in Roy, Navab, and Wachinger [4] Model Dice Recall Precision scAG-U-net 90.67 ± 0.06 96.54 ± 0.022 94.86 ± 0.05 scSE-U-net 90.55 ± 0.07 96.83 ± 0.02 94.97 ± 0.05 CoviSegNet 90.57 ± 0.06 96.03 ± 0.02 95.02 ± 0.04 image) of patients diagnosed with COVID-19 as well as segmentations of lungs and infections made by experts. Left lung, right lung, and infections are labeled by two radiologists and verified by an experienced radiologist. Each slice has it corresponding infection mask.

Table 2 :

 2 Comparison of different attention methods on Covid-19 in terms of network parameters (Param.), floating point operations per second (FLOPs), training speed (per second)

	Model	Time #Param. #FLOPS
	scAG-U-net	56.47 8.65M 16.47 G
	scSE-U-net	47.48 8.98M 16.44 G
	CoviSegNet	42.49 8.63M 16.43 G
	CoviSegNet +	43.82 8.63M 16.42 G
	Subsampling
	V EXPERIMENT RESULTS

A ANNEX 1

See Figure 4.