Christian Grothoff
email: christian.grothoff@inria.fr

Design Requirements for Civil Internetworking Position paper

Early mistakes

Internet protocols need a general overhaul to make them suitable as the main communication infrastructure for a sustainable civil liberal society. When the US military created the Internet, the fundamental goal was to interconnect existing networks, which was a simple practical objective. What is more lasting were the second level goals in order of importance as elaborated by David Clark in [START_REF] Clark | The Design Philosophy of the DARPA Internet Protocols[END_REF]:

1. Internet communication must continue despite loss of networks or gateways 2. The Internet must support multiple types of communications service.

3. The Internet architecture must accommodate a variety of networks. [START_REF] Stallman | Free Software, Free Society: Selected Essays of Richard M. Stallman[END_REF]. The Internet architecture must permit distributed management of its resources.

5. The Internet architecture must be cost effective.

6. The Internet architecture must permit host attachment with a low level of effort.

7. The resources used in the internet (sic) architecture must be accountable.

We note that the only security-related goals relate to availability and usability. While some Internet architects were aware of encryption due to their proximity to the NSA, encryption was classified and thus could not even legally be included in the emerging Internet design that was deliberatly non-classified.

As a result of these 1970 design goals, the lack of data protection remains visible at all layers of the Internet architecture today. For example, the IP header from 1981, which is still in use today, unnecessarily leaks information about the sender address and the encapsulated transport protocol. Additionally, the checksums in TCP/IP are insufficient to provide authenticity, and it is difficult to prove ownership of a destination address.

With the emergence of e-commerce, a throughly broken cryptographic protocol called "secure sockets layer" (SSL) was introduced to provide a minimum of authenticity and confidentiality. The regulatory environment, rushed deployment and lack of understanding of cryptography by the designers resulted in a complex design that took the Internet community 20 years to sufficiently understand and thereby obsolete. The surviving complex cryptographic libraries remain a treasure trove for vulnerabilities.

Civil Needs for Private Communication

Today, the actual use and thus the social requirements for a global network differs widely from those goals of 1970. While the Internet remains suitable for military use, where the network equipment is operated by a command hierarchy and when necessary isolated from the rest of the world, the situation is less tenable for civil society.

Due to fundamental Internet design choices, Internet traffic can be misdirected, intercepted, censored and manipulated by hostile routers on the network. And indeed, the modern Internet has evolved exactly to the point where, as Matthew Green put it, "the network is hostile". Even if we consistently deployed authenticated encryption on the Internet, the network would still learn way too much. Authenticated encryption does not obfuscate sender and receiver, and also discloses the times, frequency and volume of the communication, which enables reverse engineering of the set of pages visited via traffic analysis. Thus, it is not enough to encrypt, we need to also protect the metadata.

Metadata is by definition data about data, and thus provides a higher level abstraction of the underlying data. Therefore, leaking metadata is not a cosmetic issue. As Michael Hayden, the former head of both NSA and CIA explained, the US government "kills based on metadata". The democide that has resulted from the NSA's application of statistics and machine learning to metadata leaked by information networks [START_REF] Eudes | Skynet, le programme ultra-secret de la NSA créé pour tuer[END_REF] is thus partially the responsibility of computer scientists, as we have failed to build and deploy systems that adequately protect this critical information.

Authenticated encryption is also of limited utility as long as we stick to centralised service providers operating on the "Big Data" business model. The NSA's PRISM program shows how the hunger for data by the spies is paralleled by the hunger for data by the advertising-based service providers, resulting in an unholy union. Privacy and data protection issues will continue as long as the dominant business model on the Internet is for service operators to collect and monetize client information.

Design Requirements for a GNU Network

Liberal society needs a network architecture that uses the anti-authoritarian decentralised peerto-peer paradigm and privacy-preserving cryptographic protocols. Civil networks need to be anti-authoritarian, as modern networks are a critical common used for virtually all civil, political and economic activity. Just like a liberal society cannot allow anyone including the government to exercise totalitarian control over roads, food, water or electricity, we similarly cannot allow GCHQ/NSA to achieve their stated goal of information dominance.

We propose to rearchitect the Internet and create the GNUnet, an evolution of the Internet with the fundamental goal of lessening the threat of networks supporting totalitarian control over the population. This includes both control over their networking and computing, as well as ensuring that the network protects privacy. To clarify this, we propose the following ten objectives for the design of the GNUnet, in this order:

1. The GNUnet must be implemented as free software, to ensure that citizens enjoy the four essential freedoms of free software [START_REF] Stallman | Free Software, Free Society: Selected Essays of Richard M. Stallman[END_REF].

2. The GNUnet must only disclose the minimal amount of information necessary, to second and especially third parties. Each user decides what information can be shared and with whom.

3. The GNUnet must be decentralised and survive Byzantine failures in any position in the network. Increased malicious participation may cause security and privacy assurances to deteriorate commensurate with the resources expended by the adversary.

4. The GNUnet must make it explicit to the user which entities must be trustworthy when establishing secured communications.

5. The GNUnet must use compartmentalization to isolate sensitive information against Byzantine failures even among layers of the implementation on the same device.

6. The GNUnet must be open and permit new systems to join.

7. The GNUnet must be self-organizing and not depend on administrators.

8. The GNUnet must support a diverse range of applications and devices.

9. The GNUnet must scale and be cost effective.

10. The GNUnet must provide incentives for participants to contribute more resources than they consume.

We note that many of Clark's original Internet design goals correspond to design goals the bottom of the priority list for the GNUnet: enabling host attachment, diversity of use, cost effectiveness and accountability remain important, but need to fall behind the need for data protection and Byzantine fault tolerance.

The objectives formulated for the GNUnet also go beyond the simple slogan of "privacy-bydesign" [START_REF] Cavoukian | Privacy by design[END_REF]. While objective ( 2) is enshrining data protection as a key goal, privacy-by-design only calls for respect for the user's privacy, while objectives (1) and ( 3) are more broadly protecting the user's autonomy. In contrast to privacy-by-design, for the GNUnet the use of proprietary software or centralized service providers is not acceptable, as they make citizens dependent on software vendors or service providers.

The last point hints at the importance of economic considerations for future network designs. In particular, it is crucial that we open opportunities for alternative business models that are not based on advertising and Big Data, for example by providing privacy-preserving micropayments. For this to happen, liberal financial regulation, that does not strangulate emerging privacypreserving payment systems, will be key. Only then we can hope to break up the unified front of the "Big Data" industry and "mass surveillance" spy agencies against citizens.


Ines Khoufi
email: ines.khoufi@inria.fr

Pascale Minet
email: pascale.minet@inria.fr

Mohamed-Amine Koulali
email: ma.koulali@ump.ma

Mohammed Erradi
email: erradi@ensias.ma

A Game Theory-Based Approach for Robots Deploying Wireless Sensor Nodes

Keywords: WSN, game theory, coverage, connectivity, points of interest, relay nodes, assisted deployment, robot tour, obstacles

Wireless Sensor Networks (WSNs) are deployed in many fields of application. Depending on the application requirements, sensor nodes can either be mobile and autonomous or static. In both cases, they are able to cooperate together in order to monitor a given area or some given Points of Interest (PoIs). Static sensor nodes need one or several agent(s) (humans or robots) to deploy them. In this paper, we focus on the deployment of static sensor nodes in an area containing obstacles, using two mobile robots. We want to minimize the time needed by the two robots to deploy all the sensor nodes and to return to their starting position. We require that each sensor node is placed at a PoI position, no PoI position is empty and no PoI position is occupied by more than one sensor node. The problem consists in determining the best strategy for each robot in order to meet these constraints. We adopt a game theory approach to solve this problem.

I. INTRODUCTION AND MOTIVATION

Many monitoring applications rely on Wireless Sensor Networks, WSNs, in various fields of application (e.g. predictive maintenance, industrial processes, environment, e-health, precision agriculture) to gather data on the environment monitored. Such WSNs need to satisfy coverage and connectivity requirements to ensure data gathering with a good quality of service. In this paper, we focus on the coverage of Points of Interest, (PoIs). These PoIs are sources of information that is of major importance for the monitoring process. As a consequence, a sensor node must be placed at the position of each PoI. However, this in itself is not sufficient, as the collected information must reach the sink to be analyzed. That is why connectivity of each PoI with the sink is necessary and to meet this requirement, additional relay nodes must be placed at appropriate locations.

The advantage of WSNs compared to wired networks is their ease of deployment. We can distinguish two types of WSNs depending on the type of wireless nodes:

• Those based on autonomous and mobile wireless nodes: in such a case a self-deployment algorithm is adopted where wireless nodes move to the positions that are computed. This computation, usually iterative, can be centralized to avoid expensive node oscillations. In a second step, wireless nodes move directly to their final positions. This computation can also be distributed to take advantage of the processing capability of each node to dynamically adapt to the real environment and wireless nodes move at each iteration. • Those based on static wireless nodes: in this case, mobile agents (robots or humans) are needed to place the wireless nodes at their final positions, which have been computed previously. This is termed an assisted deployment. In this paper, we focus on the deployment of wireless nodes assisted by robots. The deployment duration should be minimized in order to save the robot battery and in case of hostile environment, such as a post-disaster situation (e.g. fire, pollutant leak, radiation), to prolong its lifetime. Data sent from the PoIs and collected at the sink will allow us to assess damage, and the time needed for this damage assessment must be minimized. We again distinguish two cases:

• A single robot is used. The problem in this case is an optimization problem where the optimized tour of the robot has to be found. This is a variant of the Traveling Salesman Problem (TSP), where the changes of direction of the robot have to be taken into account in the tour duration as computed in Eq. 1 (see [START_REF] Khoufi | Optimized trajectory of a robot deploying wireless sensor nodes, Wireless Days[END_REF] for examples). • Several robots are available. The existence of several robots allow them to work in parallel. This reduces the workload assigned to each of them and hence minimizes the deployment duration as well as the time needed for damage assessment. In this paper we focus on two concurrent robots. The problem is considered as a game theory problem with the robots being two non-cooperative players. The goal is to identify the winning strategies for each robot. A strategy is the ordered set of PoIs visited by a robot. The payoff of each strategy must be computed in order to favor the coverage of each PoI by a single robot. Consequently, a robot will be penalized when either a PoI is not visited by a robot or when it is visited by both robots. In this non-cooperative game, each robot tends to choose the strategy maximizing its payoff.

To be more representative of a real environment, we have to take into account the existence of obstacles. An obstacle may block the robot path, and may prohibit (depending on its type) communication between neighboring nodes. A transparent obstacle has no impact on wireless communication, however an opaque obstacle prohibits wireless communication between 978-1-4799-5344-8/15/$31.00 c 2015 IEEE neighboring nodes which are not in the line of sight of each other making opaque obstacles more challenging than transparent ones. Thus, we have to deal with two problems caused by obstacles:

• Bypassing obstacles: a strategy is proposed in Section III-C to allow the robot to move from one PoI position to another while avoiding one or several obstacles. • Maintaining network connectivity: Opaque obstacles should also be taken into account when computing the positions of relay nodes. Two consecutive relay nodes may be at a distance less than or equal to their communication range, yet unable to communicate due to the presence of an opaque obstacle between them. In this case, additional relay nodes may be needed to ensure network connectivity.

II. STATE OF THE ART

In WSNs, a mobile robot can be used either to deploy/redeploy static sensor nodes or to collect data from sensor nodes already deployed. In [START_REF] Chang | Obstacle-Free Robot Deployment Algorithms for Wireless Sensor Networks[END_REF], the authors propose a solution using a mobile robot to ensure coverage of an area containing obstacles. This mobile robot is in charge of deploying the minimum number of sensor nodes along its trajectory such that neighboring nodes are at an optimal distance. The robot is assumed to know the dimensions of the area as well as the shapes obstacles and it deploys sensor nodes while exploring the whole area. Another problem in WSNs is to deploy sensor nodes in specific zones or points of interest. The PoI positions are predetermined, and the robot has to deploy a sensor node at each PoI. However, the order in which the robot visits the PoIs may have an impact on the distance covered or the duration of robot tour. In this context, the authors in [START_REF] Wang | Robot-Assisted Sensor Network Deployment and Data Collection[END_REF] refer to the traveling salesman problem with neighborhoods to find the minimum path in terms of distance traveled by the robot. The robot should visit each zone of interest only once and return to its starting position. To solve this problem, they propose an iterative algorithm where a non visited zone of interest is added at each iteration such that the distance added to robot tour is minimum. The authors propose the same algorithm for the robot to stop at some pause points in order to collect data from sensor nodes. thus, the robot tour is an ordered list of pause points. This tour should, on the one hand, allow the robot to communicate with every sensor node during the tour with a minimum number of pause points, and on the other hand, it should have the minimum length in terms of distance traveled. In a previous study [START_REF] Khoufi | Optimized trajectory of a robot deploying wireless sensor nodes, Wireless Days[END_REF], we proposed a Robot Deploying Sensor nodes problem (RDS) which aims to minimize the robot tour duration (i.e. the time spent by the robot to place its sensor nodes and return to its starting position). Unlike the TSP problem, which minimizes the distance traveled by the robot, our RDS problem takes into account the time the robot spends in changing direction. We solved this problem using optimization algorithms: a genetic algorithm and a 2-opt algorithm. We proposed a hybrid algorithm that combines both genetic and 2-opt algorithms and provides better results in terms of tour duration.

In this work we consider a game theory approach for robot assisted sensors deployment. Non cooperative game theory provides a mathematical framework for modeling, analyzing and predicting the outcome of strategic interactions involving interdependent rational players [START_REF] Basar | Dynamic non-cooperative game theory[END_REF]. In strategic decision taking, conflicts of interests arise and own decisions are no longer sufficient to ensure optimal payoff. Indeed, the outcome of the game will depend on the whole strategy profile (set of actions) of all the actors. Game theory has strong roots in economics, but has also been widely applied in several other fields such as political science [START_REF] Morrow | Game theory for political scientists[END_REF], biology [START_REF] Hammerstein | Game theory and evolutionary biology[END_REF], engineering and computer science [START_REF] Apt | Lectures in game theory for computer scientists[END_REF]. The past decade witnessed a surge in research effort to apply game theory in the context of modern communication systems [START_REF] Haykin | Cognitive radio: brain-empowered wireless communications[END_REF], [START_REF] Koskie | A nash game algorithm for sir-based power control in 3g wireless cdma networks[END_REF] and [START_REF] Alpcan | A power control game based on outage probabilities for multicell wireless data networks[END_REF]. Indeed, there has been an exponential growth of connected devices combined with an increase of their communication and computational capabilities. Game theory provides a formal framework for distributed decision while reducing the overhead of protocol design inherent to central authorities. Games in strategic form are well suited for the study of N player games with discrete action space. An important solution concept for such games is the Nash Equilibrium [START_REF] Nash | Equilibrium points in n-person games[END_REF]. A Nash equilibrium is a strategy profile to which all players have to commit. For instance, none of the players will have incentive to deviate from the Nash equilibrium to increase its payoff. The authors of [START_REF] Ai | Optimality and complexity of pure nash equilibria in the coverage game[END_REF] proposed a game-theoretic formulation for activity scheduling of sensors. The problem is to arrange the sensing schedule of sensors to maximize average area coverage. The considered game is proven to be a potential/congestion game with a pure Nash equilibrium. The problem of minimizing the probability of undetected intrusion, in environments with obstacles is considered in [START_REF] Kloder | Partial barrier coverage: Using game theory to optimize probability of undetected intrusion in polygonal environments[END_REF]. The problem is equivalent to partial barrier coverage formulated as a zero-sum game between the intruder and the deployment of the guards. The saddle point of the game (Equilibrium) is proven to exist for mixed strategies only.

In this paper, we focus on the deployment of static sensor nodes at specific positions (PoIs) using two robots that proceed in parallel in order to minimize the deployment duration. We require that each sensor node is placed at a PoI position, no PoI position is empty and no PoI position is occupied by more than one sensor node. The problem consists in determining the best strategy for each robot in order to meet these constraints. We adopt a game theory approach to solve this problem and find the best strategy for each robot. We consider a realistic area with some obstacles and show how to cope with these obstacles.

III. PROBLEM DEFINITION A. Goal

Our goal is to minimize the tours duration of two mobile robots in charge of deploying static sensor nodes in an environment with known obstacles. Each sensor node must be positioned at a Point of Interest (PoI). To maintain network connectivity, the robot will also deploy additional relay nodes during its tour, Then, each PoI will be able to communicate with the sink. The problem consists in determining the tours of the two robots that minimize the deployment duration while ensuring the coverage of each PoI by exactly one robot.

Figure 1 depicts the tour of two robots where each PoI is visited by exactly one robot and relay nodes are placed to ensure connectivity of each PoI with the sink. -The number, position and shape of the obstacles.

-The area considered.

• Each mobile robot is able to know its position and to move to a given position. • Both robots have the same linear speed ls and the same angular speed as. As an example, in the simulation reported in this paper, we take ls = 1m/s and as = 10/s. • Each robot R i has the capacity to carry C max,i sensor nodes.

• Each robot R i has the capacity to carry C relaymax,i relay nodes.

• Both robots have the same starting position, the sink denoted P 0 for simplicity, and should return to this position. • Let S i denote the set of strategies played by robot R i .

Any strategy s i played by R i is defined by the ordered set of PoIs visited by R i . • To cope with obstacles, a bypassing approach is adopted as explained in the nest section.

C. Deployment duration and obstacles

The deployment duration D i of robot R i depends not only on the time needed to travel a distance but also on the time needed to carry out changes in direction. Hence, we compute D i for any strategy s i as follows:

D i = j∈si d j,j+1 /ls+ j∈si a j-1,j,j+1 /as. (1)
Where j and j + 1 are two successive PoIs in s i . d j,j+1 is the distance between two successive PoIs in s i . a j-1,j,j+1 is the angle formed by the segments [j -1, j] and [j, j + 1] corresponding to three successive PoIs in s i . We notice however that the tour duration is the same when the robot visits the same nodes but in the reverse order.

If there exists an obstacle between the sensor node positions A and B, the direct path from A to B is made impossible as illustrated in Figure 2. We propose to define intermediate positions I i that allow the robot to reach B avoiding the obstacle. We replace the impossible direct path between A and B by a possible one that can be seen as a juxtaposition of segments I i I i+1 . The tour duration due to this path is computed as the sum of the duration due to any segment composing the path. Figure 2

IV. PROBLEM FORMALIZATION

We proceed in two steps. In the first step, we focus on the coverage problem: the goal is only to ensure the coverage of all PoIs while minimizing the tour duration of each robot. In other words, only one robot must place a sensor node at each PoI. In the second step, we are interested in both coverage and connectivity: each robot must, in addition, place relay nodes to ensure connectivity of each PoI with the sink.

A. Coverage problem

We can now model our coverage problem as a non cooperative game. A game is defined by the set of players, the set of strategies for each player and the set of payoffs corresponding to the strategies used by each player. In our case, the two players are the mobile robots. The action of each robot consists in selecting the next PoI to visit in its tour. Consequently the strategy s of a robot is an ordered set of PoIs visited by this robot. Let R 1 and R 2 denote our two robots. Let {P 1 , P 2 , .., P n } denote the set of n PoIs that should be monitored. Let P i (s i , s -i ) denote the payoff of player R i when it plays strategy s i while the other player plays strategy s -i . The payoff computation follows some rules:

• To incite robots to visit all PoIs exactly once, the payoff of a robot increases when the number of PoIs visited increases. However, the payoff of both robots becomes negative if some PoIs are visited by either no robot or both robots. • To minimize the tours duration of robots, the payoff of a robot increases for a given set of PoIs visited when the tour duration of the robot decreases.

Algorithm 1 shows how to calculate the payoff of one robot in charge of ensuring PoIs coverage. We use a weight factor α higher than D i to model positive outcome values.

Algorithm 1 Calculate P i (s i , s -i ) for Coverage problem if (N umber of P oIs visited by both Ri and R-i <> 0) then Pi(si,

s-i) = -1 else if ((Cmax,i + Cmax,-i) >= n) then if (N umber of P oIs visited by neither Ri nor R-i) <> 0) then Pi(si, s-i) = -1 else Pi(si, s-i) = α D i end if else if (N umber of P oIs visited by Ri < Cmax,i) then Pi(si, s-i) = -1 else Pi(si, s-i) = α D i end if end if end if
Consequently each player R i wants to maximize its payoff P i (s i , s -i ). Under the constraints:

• C i ≤ C max,i
, where C i is the number of sensor nodes carried by the robot R i .

B. Coverage and connectivity problem

In the coverage and connectivity problem, each robot places a relay node each time it travels a distance Dist. The coverage and connectivity problem differs from the coverage problem by an additional constraint on C relay,i the number of relay nodes placed by a robot R i . We must have:

• C relay,i ≤ C relaymax,i .
Strategies violating this constraint are eliminated. The payoff of any strategy is computed as given in Algorithm 1.

V. PROBLEM RESOLUTION Notice that in both games, the payoff computed for player R i depends not only on s i the strategy chosen by R i but also on the strategy s -i chosen by the other player R -i .

A strategy profile (s * i , s * -i ) is a Nash equilibrium if and only if no unilateral deviation of the strategy of a single player is profitable for that player. Hence, ∀i, ∀s i ∈ S i , P i (s * i , s * -i ) ≥ P i (s i , s * -i ). Nash proved the existence of at least one Nash equilibrium when mixed strategies are allowed in a game with a finite number of players and each player chooses among pure strategies.

Both problems are solved in a similar way:

• Determining all strategies for each player.

• Eliminating all strategies violating the constraints. The remaining strategies are the valid strategies of any player. • Computing the payoff for all the possible combinations of valid strategies for all players. • Computing the Nash equilibrium using the Gambit tool [START_REF]Gambit: a software tool for game theory[END_REF]. The number of strategies for robot R i visiting q PoIs with q ≤ min(C max,i , n) is: C q n * q! 2 . This is because the strategies {P j , P j+1 ...P j+m } and {P j+m ..., P j+1 , P j } have the same payoff. Hence the total number of valid strategies for robot R i is equal to:

q∈{1,Cmax,i} C q n * q! 2 .

A. Coverage problem

For any given strategy s -i , the strategy s i that maximizes P i (s i , s -i ) in the coverage problem consists of visiting only all the PoIs that are not visited by R -i , provided it meets the constraint C max,i and selecting the visit order that minimizes the deployment duration Di.

We first notice that if C max,i < n/2 for any i ∈ [START_REF] Khoufi | Optimized trajectory of a robot deploying wireless sensor nodes, Wireless Days[END_REF][START_REF] Chang | Obstacle-Free Robot Deployment Algorithms for Wireless Sensor Networks[END_REF], it is impossible to cover all the PoIs with two robots.

In any other case, we obtain a Nash equilibrium where each PoI is visited exactly once, ensuring the full coverage of all the PoIs without any redundancy.

In this section, we evaluate the tour duration of the two robots deploying sensor nodes in an area with and without obstacles. We start by computing the tour duration for various values of C max,i and C max,-i . The sum of C max,i and C max,-i should be higher than or equal to the number of PoIs to be covered. Then, we evaluate the duration of both tours in different configurations. These configurations are different in terms of the number and shape of the obstacles in the area considered.

1) Area without obstacles:

To evaluate the impact of the robot capacity to carry sensor nodes, we vary the values of C max,i and C max,-i .

When C max,1 is equal to C max,2 and their sum is equal to the number of PoIs (See Case 1 in Table I and Figure 3a)) the Nash equilibrium provides two robot tours that visit all PoIs exactly once. It may not be possible to find two robot tours with the same duration due to the position of the PoIs in the area considered. However, the ones computed are the best combination to minimize the tour duration of robots. In Figure 3b) and Figure 3c), we get the same Nash equilibrium, where the first robot visits C max,i PoIs and the second one visits the PoIs not visited by the first one. 2) Area with obstacles: In Figure 4a) and Figure 4b), we observe that the presence of obstacles modifies the trajectory of the robots. We obtain a Nash equilibrium for the two obstacle configurations, where each robot visits 50% of PoIs. To bypass the obstacle, each robot uses intermediate points.

For this reason, we notice that the tour duration is increased: 1071 in Configuration 1 Figure 4a) and 1077 in Configuration 2 Figure 4b) instead of 1056 as shown in Table II.

B. Coverage and connectivity problem

For any given strategy s -i , the strategy s i that maximizes P i (s i , s -i ) in the coverage and connectivity problem consists in visiting only all the PoIs that are not visited by R -i , provided it meets the constraints C max,i and C maxrelay,i , while selecting the visit order that minimizes the Deployment duration Di.

Notice that the robot places relay nodes along its trajectory such that two node-disjoint paths are established between each PoI and the sink. Then, a robust network connectivity is maintained. Fig. 5: C max,i = 3, C max,-i = 3 1) Area without obstacles: In this section, we assume that the robot is able to carry a limited number of relay nodes C maxrelay,i . In Figure 5, C maxrelay,i = 22. The two robot tours are different from the ones illustrated in Figure 4 where there is no constraint on the number of relay nodes. The two robot tours in Figure 4 provide a smaller deployment duration than those of Figure 5. However, they require a number of relay nodes higher than C maxrelay,i . Then, the result obtained in Figure 5 presents the better combination taking into account both the number of relay nodes and the deployment duration. 2) Area with obstacles: When obstacles exist the length of each tour may increase due to obstacle bypassing. Then, the value of C maxrelay,i may increase according to the obstacle configuration. We fix C maxrelay,i = 23 for Configuration 1 and C maxrelay,i = 24 for Configuration 2, respectively (see Table IV). We observe in Figure 6a) that the two robot tours are different from those in Figure 4a) due to the constraint on C maxrelay,i . However, in Configuration 2 (see Figures 4b) and6b)), the two robot tours do not change, whether we take into account the relay nodes or not. When we try to decrease C maxrelay,i to a value less than 24, we do not get any Nash equilibrium as all strategies are eliminated due to a violation of the C maxrelay,i constraints. VI. CONCLUSION In this paper we focused on the deployment of wireless sensor nodes by mobile robots. The goal is to ensure the coverage of PoIs and maintain connectivity of each PoI with the sink. To be closer to real conditions, we take into account the presence of obstacles. We want to find the trajectories of two mobile robots which satisfy the following constraints: all the PoIs are visited exactly once and the tour duration of the robots is minimized. Game theory is used to formalize this problem as a non-cooperative game with two players, to find the Nash equilibria for various configurations. We studied the impact of obstacles on the deployment duration. The robot tours may differ depending on whether obstacles are present or not. However, the Nash equilibrium obtained, provides the best combination of the two robot tours.

Fig. 1 :

 1 Fig. 1: Robot tours and relay node deployment in the presence of obstacles

  shows the two intermediate points I 1 and I 2 that are introduced in the path taken by the robot to reach B from A. The path A, I 1 , I 2 , B replaces the direct path A, B. Additional intermediate positions are introduced in the tour of the robot to bypass obstacles. The deployment duration takes into account these intermediate positions. Furthermore, additional relay nodes are needed to ensure connectivity in case of opaque obstacles. The positions of these relay nodes are also taken into account.

Fig. 2 :

 2 Fig. 2: Intermediate points between sensor node positions A and B

  a) Cmax,i = 3, Cmax,-i = 3. b) Cmax,i = 4, Cmax,-i = 2. c) Cmax,i = 4, Cmax,-i = 4.

Fig. 3 :

 3 Fig. 3: Best robot tours with different C max,i (No obstacles).

a) Cmax,i = 3 ,

 3 Cmax,-i = 3. b) Cmax,i = 3, Cmax,-i = 3.

Fig. 4 :

 4 Fig. 4: Impact of obstacles on the best robot tours.

  a) Cmax,i = 3, Cmax,-i = 3. b) Cmax,i = 3, Cmax,-i = 3.

Fig. 6 :

 6 Fig. 6: Impact of obstacles on the best robot tours with relay nodes placement.

TABLE I :

 I Impact of C max,i on the deployment duration.

TABLE II :

 II Impact of the presence of obstacles on the deployment duration.

TABLE III :

 III The deployment duration with relay nodes.

TABLE IV :

 IV The Deployment duration with relay nodes and obstacles.

ACKNOWLEDGMENT

This work has been partially funded by the Cluster Connexion project. For more details see http://www.clusterconnexion.fr/.

Special thanks to the members of the AWSN project for their cooperation, see http://hipercom.inria.fr/euromed/.


Adrià Arrufat

Pierrick Philippe

Olivier Déforges

Mode-dependent

Keywords: HEVC, transform coding, KLT, MDDT, rate-distortion optimised transforms

INTRODUCTION

Block-based transform coding is used in current lossy compression schemes, such as High Efficiency Video Coding (HEVC) [START_REF] Sullivan | Overview of the High Efficiency Video Coding standard[END_REF] to compact the signal energy. Despite being an important step in video coding, employed transforms are generic and not adapted to particular signal statistics: trigonometric transforms in the DCT family are still considered in state-of-the-art video standards such as HEVC.

Some research has been conducted in order to determine transforms better adapted to the different underlying varieties of video signal statistics. In this context the mode-dependent directional transform (MDDT) [START_REF] Ye | Improved H.264 intra coding based on bi-directional intra prediction, directional transform, and adaptive coefficient scanning[END_REF][START_REF] Yeo | Mode-dependent fast separable klt for blockbased intra coding[END_REF][START_REF] Saxena | Mode-dependent DCT/DST for intra prediction in video coding[END_REF] has been studied over the recent years. The idea behind the MDDT is to design transforms adapted to each intra prediction (IP) mode, which essentially implies the design of a Karhune-Loève transform (KLT) per prediction mode.

In this paper, the MDDT concept is extended through the usage of a set of transforms adapted to each IP mode: for a given prediction mode, the encoder selects the best transform in the provided set. The design of multiple transforms and their implementation into HEVC have already been presented in our previous work [START_REF] Arrufat | Nonseparable mode dependent transforms for intra coding in HEVC[END_REF][START_REF] Arrufat | Ratedistortion optimised transform competition for intra coding in HEVC[END_REF], following two different approaches:

• In [START_REF] Arrufat | Nonseparable mode dependent transforms for intra coding in HEVC[END_REF], it is shown that a transform design method called rate-distortion optimised transform (RDOT) yields to better coding efficiency compared to the traditional KLT design. This method is used to design transforms adapted for each IP mode as in the MDDT system. The new generated transforms replace the default HEVC transforms on targeted block sizes.

• Work in [START_REF] Arrufat | Ratedistortion optimised transform competition for intra coding in HEVC[END_REF] follows a different approach; instead of designing one transform for each IP mode and replace the default transforms, it provides complementary transforms to HEVC core transforms that are shared amongst all prediction modes. The HEVC encoder selects the best performing transform in a rate-distortion optimisation (RDO) loop, along with the most adapted prediction mode and block size.

Both approaches suggest the use of non-separable transforms and bit-rate reductions of around 2% are reported using either technique: this improvement comes at the cost of significant increase in complexity and storage needs.

In this paper, a combination of both approaches is proposed. It is shown that an increase in performance can be achieved, while reducing the algorithmic complexity.

This paper is organised as follows. Section 2 introduces the design of separable and non-separable RDOTs. The combined approach is presented in section 3, where multiple transforms are provided for each IP mode. This approach is implemented in HEVC and the performance results are presented and discussed in section 4.

RATE-DISTORTION OPTIMISED TRANSFORMS

Sparse orthogonal transforms, or rate-distortion optimised transforms (RDOTs), were introduced in [START_REF] Sezer | Sparse orthonormal transforms for image compression[END_REF] by Sezer et al. and are explained more in detail in [START_REF] Sezer | Data-driven transform optimization for next generation multimedia applications[END_REF]. The RDOTs provide better compression gains than the KLT in the context of video coding as reported in [START_REF] Arrufat | Nonseparable mode dependent transforms for intra coding in HEVC[END_REF].

A RDOT is a transform A opt that minimises the following quantity:

A opt = arg min A ∑ ∀i min c i x i -A T c i 2 2 + λ c i 0 (1)
Where x i is a signal from a training set, i.e. a block of pixels reshaped into a N 2 × 1 vector, X i = A • x i are the transformed coefficients using the transform A and c i are the quantised transformed coefficients. A T is the inverse transform, since A is chosen orthonormal. The constraint in the cost function is the 0 norm of the coefficients, that is, the number of non-zero quantised transformed coefficients, also called the number of significant coefficients. The Lagrange multiplier λ of the constraint only depends on the quantisation accuracy applied to the coefficients, as proved in [START_REF] Sezer | Sparse orthonormal transforms for image compression[END_REF].

A solution to equation 1 can be found in two steps [START_REF] Sezer | Sparse orthonormal transforms for image compression[END_REF]. First, the optimal coefficients are obtained by hard-thresholding X i . Afterwards, the transform is updated given the hardthresholded coefficients c i and the x i . These two steps are repeated until convergence, with the design metric value being stable.

Although equation 1 outputs a non-separable transform, separable RDOTs can also be derived. In image coding, a two-dimensional separable transform is performed as:

X = A v • A h • x T T = A v • x • A T h (2)
Consequently, equation 1 is updated as:

A opt = arg min A ∑ ∀i min c i x i -A T v c i A h 2 2 + λ c i 0 (3)
In order to learn a transform set specific to each IP mode, residuals coming from every prediction mode are used separately. These residuals come from a video encoding performed with the HEVC reference software (HM) using a set of sequences different from the HEVC test set.

For each prediction mode, an initial random classification of the residuals into 1 + N groups is carried out. The first group is left to the HEVC core transforms and a RDOT is learnt on each remaining group. Based on the updated transforms, a reclassification of the residuals is performed using the design metric from equation 1. Those steps are iterated until the whole system becomes stable; the set of transforms is considered optimal then. See algorithm 1.

The use of separable and non-separable transforms

Non-separable transforms have frequently been discarded in favour of their separable counterparts in image and video coding. This is due to two reasons: the computational complexity and the storage requirements, which increase significantly when separable transforms are replaced with non-separable.

For non-separable transforms, the number of operations required for an N × N block is about N 4 , whereas for a separable transform is reduced to 2N 3 . This amount of operations can further be reduced for transforms exhibiting symmetries such as the DCT-like transforms.

The storage requirements differ notably, as well. Assuming each transform coefficient is stored using 2 bytes, to store

δ n = x -A T n c 2 + λ c 0 end n * = arg min n (δ n )
Class n * .append (x) end end Algorithm 1: Multiple transform design a non-separable transform, 2N 4 bytes are needed. For twodimensional separable transforms, 2 • 2N 2 + N 2 = 5N 2 are needed, instead. The second term in the separable transform equation represents the scanning pattern, which can be stored in one byte, such that the order of the coefficient is adapted to the context adaptive binary arithmetic coding (CABAC): the energy of the coded samples needs to be sorted in a descending order as in HEVC.

MODE-DEPENDENT TRANSFORM COMPETITION

The results from previous work in intra coding using modedependent transforms [START_REF] Arrufat | Nonseparable mode dependent transforms for intra coding in HEVC[END_REF] and transform competition [START_REF] Arrufat | Ratedistortion optimised transform competition for intra coding in HEVC[END_REF] independently encourage the combination of both, named modedependent transform competition (MDTC).

In order to validate the approach of using multiple transforms per IP mode, a first experiment has been carried out, where one additional transform is used to complement the HEVC core transforms. A flag has been used to indicate whether the additional transform has been chosen in the RDO loop.

The system extends HEVC for the 4 × 4 and 8 × 8 transform unit (TU) sizes. The encoder selects the best prediction mode / transform pair in the RDO loop: as such, there is a competition between the newly designed transforms and HEVC core transforms.

Results reported here use the coding configurations established by the Joint Collaborative Team on Video Coding (JCT-VC) standardisation group [START_REF] Bossen | Common test conditions and software reference configurations[END_REF]. They consist in encoding the sequences at four quantisation parameter (QP) points (22, 27, 32, 37) and computing the average bit-rate reduction [START_REF] Bjøntegaard | Calculation of average PSNR differences between RD-curves[END_REF]. The experiments have been carried out in all intra (AI) and random access (RA) configurations, even though transform competition is only available for those blocks coded using intra predictions.

Regarding the complexity, the systems tested in this paper present significant improvements over the previous one from [START_REF] Arrufat | Ratedistortion optimised transform competition for intra coding in HEVC[END_REF], which was 8 times more complex than the HEVC encoder. The current approach is only 2 times more complex.

Compression performance compared to HEVC is significantly better for both systems: they achieve a bit-rate reduction of 3.78% for the non-separable version, and 1.66% for the separable one.

Detailed results of this system are shown in table 1. As a reminder, non-separable systems from previous work achieved a bit-rate reduction of around 2% each one.

This simple experiment motivates the increase in the number of transforms in each IP mode to find out the amount of improvement that MDTC can provide. However, this increase of the number of transforms comes at a cost, notably in the storage and computational requirements: the results of this approach and the complexity requirements are discussed in the next section.

HIGH PERFORMANCE MDTC

This section presents the results of a system that combines mode-dependent transforms with an increased number of transforms for each prediction mode Transform competition has been enabled for the 35 IP modes only for the 4 × 4 and 8 × 8 TU sizes. For this updated system, 16 transforms for 4 × 4 blocks and 32 for 8 × 8 blocks are designed.

Transform usage is indicated using a basic signalling scheme conforming the signalling used in section 3: a flag is used to inform whether the default HEVC transform has been used. In a negative case, the selected transform is signalled using a fixed length codeword, 4 bits for the 4 × 4 TUs sizes and 5 bits for 8 × 8 sizes.

The performances obtained with this higher complexity MDTC scheme have increased significantly: for the AI configuration, on average 7.1% compression gains are obtained with the non-separable version compared to HEVC, 4.1% are reported for the separable version. These average results are consistent over all the tested resolutions, although the improvement is lower for the higher resolution (class A), since TU sizes of 16 ×16 and 32 ×32 are more often used and competition has not been introduced for them.

The RA performance is lower than the one obtained in AI, as the proposed improvement only affects the intra modes: inter coding has not been modified with the changes proposed in this publication. Despite that, the improvement is significant, as improving the intra predicted blocks also provides a better reference for inter-predicted blocks.

In order to compare the visual impact of the proposed system, the best performing sequence has been used. The fact of having a bit-rate reduction of 25% makes it easier to spot differences and possible visual artefacts. The QP point used for comparison is 37, because both sequences present a bit- As it can be observed in figure 2, this system, not only improves HEVC in textured and directional image regions, but also removes major coding artefacts.

A comparison between both systems in their separable and non-separable versions is presented in table 2. The number of transforms used affects, especially, the encoding time and the storage requirements, since more coding possibilities are explored. The augmented number of transforms highly increases the number of operations needed to find the best combination of block size, prediction mode and transform. Due to the increment of operations needed to find the best combination of block size, prediction mode and the augmented number of transforms, the separability has almost no impact on the encoding time. However, on the decoder side, using non-separable transforms comes at a high expense, around 30% can be observed, whereas complexity increases of about 5% when using separable transforms. Storage seems unreasonable when using a high number of transforms or non-separable transforms.

Figure 3 highlights the interest of increasing the number of additional transforms in each IP. The number of 8 × 8 transforms has been progressively increased and coding performance improve systematically. Better compression gains could be obtained by a further increase of the number of transforms. However, the complexity leads to unrealistic systems,

CONCLUSIONS

This paper combines two approaches that provide extended competition for improved video coding: different transforms are designed per prediction mode to better adapt to the video signal statistics. The design of the transforms is based on a method based on previous work, and the level of performance obtained here demonstrates the validity of this method. Two distinct systems were presented which report significant improvement over the state-of-the-art HEVC codec. Up to 7% of improvement is reported for the higher complexity configuration. Since the storage and algorithmic requirements for this system seem unrealistic, two alternative Fig. 3: Improvements over HEVC when the number of 8 × 8 transforms increases systems, using separable transforms, provide viable points in terms of ROM and complexity, they accommodate different trade-offs, for those systems 4% of compression improvement is provided for the higher complexity systems, 1.6% for the simpler coding scheme. It has also been shown that different levels of performances can be achieved, depending on the complexity level. As a result, further work will address the complexity aspects: the storage requirements and the encoding complexity will be decreased as they represent the major drawbacks for the current designs.

  input : Residuals x from a given intra prediction mode output: Set of N RDOTs A n Initial random classification into 1 + N classes while !convergence do for n = 1 to N do Learn a RDOT on Class n using equation 1 end foreach block x do for n = 0 to N do

Fig. 1 :Fig. 2 :

 12 Fig. 1: BD-rate savings for BasketballDrill: -25.06%

Table 1 :

 1 Compression gains for the different proposed MDTC configurations

						4 × 4: 1+1 -8 × 8: 1+1		4 × 4: 1+16 -8 × 8: 1+32
					Y BD-rate (N-Sep)	Y BD-rate (Sep)	Y BD-rate (N-Sep)	Y BD-rate (Sep)
			Sequence	AI	RA	AI	RA	AI	RA	AI	RA
			NebutaFestival	-0.52% -0.04%	-0.34% -0.05%	-1.15%	-0.13%	-1.06% -0.08%
	Class A		PeopleOnStreet	-2.76% -1.16%	-1.40% -0.48%	-5.65%	-2.27%	-4.21% -1.49%
	(2560 × 1600)	SteamLocTrain	-0.46% -0.36%	-0.36%	0.33%	-0.68%	0.03%	-0.60%	0.23%
			Traffic	-3.07% -1.68%	-1.68% -1.25%	-6.06%	-5.12%	-4.52% -3.73%
			BasketballDrive	-3.15% -1.76%	-1.17% -0.35%	-5.52%	-2.36%	-3.22% -0.72%
	Class B (1920 × 1080)	BQTerrace Cactus Kimono1	-5.11% -2.83% -3.76% -2.42% -1.06% -0.50%	-1.80% -1.08% -1.95% -1.15% -10.92% -9.22% -0.46% -0.25% -1.80%	-4.93% -7.68% -1.18%	-4.70% -2.65% -5.22% -3.08% -1.10% -0.79%
			ParkScene	-2.20% -1.50%	-1.68% -1.09%	-5.27%	-3.69%	-4.61% -3.22%
			BasketballDrill	-12.83% -7.06%	-2.09% -1.32% -25.06% -14.80%	-5.92% -3.53%
	Class C		BQMall	-3.27% -1.91%	-2.04% -1.20%	-6.21%	-3.64%	-4.79% -2.79%
	(832 × 480)		PartyScene	-3.31% -2.29%	-2.18% -1.40%	-6.19%	-4.30%	-4.88% -3.21%
			RaceHorses	-3.99% -2.16%	-1.71% -0.70%	-6.75%	-3.24%	-4.25% -1.59%
			BasketballPass	-3.71% -1.97%	-1.68% -0.82%	-6.15%	-3.14%	-3.91% -1.82%
	Class D		BlowingBubbles	-4.21% -2.35%	-1.96% -1.21%	-6.73%	-3.95%	-4.30% -2.69%
	(416 × 240)		BQSquare	-3.72% -2.00%	-2.26% -1.21%	-6.12%	-3.61%	-4.58% -2.74%
			RaceHorses	-4.61% -2.03%	-1.57% -0.58%	-7.13%	-3.20%	-3.85% -1.54%
	Class E (1280 × 720)		FourPeople Johnny KristenAndSara	-3.42% -3.27% -2.96% -2.86% -3.49% -3.26%	-1.83% -1.94% -1.29% -1.61% -1.34% -1.75%	-6.15% -6.73% -6.12%	-3.14% -3.95% -3.61%	-4.56% -5.18% -3.34% -4.16% -3.82% -4.47%
	Class F (various resolutions)		BasketDrillText ChinaSpeed SlideEditing SlideShow	-11.01% -6.31% -2.87% -1.58% -1.82% -1.97% -3.49% -2.96%	-2.37% -1.51% -21.14% -13.15% -2.02% -1.22% -4.86% -3.03% -2.04% -2.18% -3.67% -4.06% -2.53% -2.32% -6.03% -5.91%	-6.24% -3.71% -4.25% -2.71% -4.80% -5.05% -5.66% -5.61%
	All sequences	Overall	-3.78% -2.36% -1.66% -1.10%	-7.10%	-4.67% -4.10% -2.76%
			4 × 4: 1+1	4 × 4: 1+16
			8 × 8: 1+1	8 × 8: 1+32
			Sep	N-Sep	Sep	N-Sep
	Y BD-rate -1.66% -3.78% -4.10% -7.10%
	Enc. Time		×2	×2	×10	×10
	Dec. Time		+3%	+30%	+5%	+30%
	Storage	27 kB	298 kB 788 kB	9 MB

Table 2 :

 2 Performance and complexity summary especially for the encoding time and storage requirements.


Nadia Boufares
email: nediya.boufares@gmail.com

Ines Khoufi
email: ines.khoufi@inria.fr

Pascale Minet
email: pascale.minet@inria.fr

Leila Saidane
email: leila.saidane@ensi.rnu.tn

3D Surface Covering with Virtual Forces

The deployment of Wireless Sensor Network (WSNs) is widely used in monitoring applications. Depending on the entity to be monitored, sensor nodes are deployed in a twodimension (2D) area or a three-dimension (3D) area. In addition, sensor nodes can be deployed either in a distributed way or their positions are precomputed by a central entity and they are placed at their positions using mobile robots. In this paper, we are interested in the deployment of WSN in a 3D-surface using autonomous and mobile nodes. Our goal is to ensure full 3Dsurface coverage and maintain network connectivity. To reach our goal we propose 3D-DVFA-SC, a distributed deployment algorithm based on virtual forces strategy to move sensor nodes. Simulation results show that 3D-DVFA-SC provides a very good coverage rate while maintaining network connectivity.

I. CONTEXT AND MOTIVATION

Wireless sensor networks (WSNs) are deployed in an area of interest in order to monitor physical or environmental conditions, such as temperature, sound, pressure, etc. To perform the monitoring task, two main issues should be considered: area coverage and network connectivity. The area to be monitored is fully covered if each event occurring in this area can be detected by at least one sensor node. Network connectivity is maintained if there is at least one path between each sensor node and a central entity called sink. Then, each detected event can be reported to the sink.

WSNs are used in many monitoring applications such that military battlefields, environment disaster, home automation, industrial monitoring. These applications differ by, on the one hand, the entity to be monitored that can be a 2D or a 3D area, Points of Interest (PoIs) or barrier and, on the other hand, the coverage and connectivity requirements. The coverage of the entity to be monitored can be full or partial and network connectivity can be either temporary or permanent. To meet the application requirements, a deployment algorithm is needed to determine the appropriate sensor node positions. The deployment algorithm can be centralized, the central entity in charge of computing the deployment must collect the current positions of all sensor nodes. Then, a human or mobile robot will be in charge of placing a sensor node at each computed position. Otherwise, the deployment algorithm is distributed when sensor nodes are mobile and autonomous, and able to exchange information to reach their final position progressively.

In our study, we focus on distributed deployment algorithms where sensor nodes are able to cooperate in order to determine their appropriate positions that meet required coverage and connectivity. Autonomous and mobile sensor nodes can be used to cover a 2D area or 3D area. In 3D, we have to distinguish volume covering from surface covering: in the first case, the entity to cover is the whole volume as depicted in Figure 1a, whereas in the second case, sensor nodes should be placed only on the surface considered. This surface may have different variations as depicted in Figure 1b. In this work we are interested in ensuring full coverage of a 3D surface.

In 3D space, the area to cover can be either a polyhedron, see for instance Figure 1a, or a surface that is not flat (e.g. a mountain) like this illustrated in Figure 1b. When the area to cover is a polyhedron, a sensor node can be located at any position inside the polyhedron. However, when the target to cover is a 3D surface, the sensor nodes should follow the shape of this surface. This problem is also called 3D surface covering. Recent studies [START_REF] Zhao | Surface coverage in wireless sensor networks[END_REF] reveal that sensor deployment on 3D surface is totally different from deployments in a 2D plane or a 3D volume. It tackles new challenges such as how to handle variations in the shape of the 3D surface. Some applications require a 3D surface covering, such as snow tracking in a mountainous area or forest fire detection. Thus, existing solutions developed for 2D planar or 3D volumetric deployment are no longer valid for applications requiring 3D surface covering. For instance, a 2D deployment applied to 3D surface may lead to coverage holes.

That is why we propose to design a 3D distributed deployment algorithm whose aim is to deploy sensor nodes in the 3D surface area in order to ensure full coverage and maintain network connectivity.

This paper is organized as follows: In section II, we give an overview of the state of the art. Section III describes in details our 3D distributed virtual forces algorithm. Section IV deals with the performance evaluation of our algorithm. Finally, we conclude in Section V.

II. RELATED WORK

In the literature, several strategies for the deployment of wireless nodes are proposed to determine the appropriate node positions. We distinguish three main deployment strategies [START_REF] Khoufi | Survey of deployment algorithms in wireless sensor networks: coverage and connectivity issues and challenges[END_REF]: grid-based strategy, computational based strategy and virtual forces-based strategy. These strategies are proposed to monitor 2D area, however, they can be extended to monitor 3D area (e.g. volume or surface).

If the grid based strategy is adopted, sensor node positions can be either at cell centers or cell vertex. In the case of monitoring an area with irregular borders, some positions that do not belong to the grid should be added to avoid coverage holes near these borders. The authors in [START_REF] Alam | Coverage and connectivity in three-dimensional networks[END_REF] proved that the truncated octahedron cells is the best tessellation to ensure the coverage of a volume using the minimum number of sensor nodes. Sensor nodes positions are the truncated octahedron centers. In order to maintain network connectivity, the communication range R must be at least 1.7889 times the sensing range r.

The computation geometry strategy is generally based on Voronoi diagram or Delaunay triangulation to determine sensor nodes positions. This strategy has a high cost of computation since a global knowledge of the area is required. The authors in [START_REF] Jin | Optimal surface deployment problem in wireless sensor networks[END_REF] focus on finding the optimal deployment on 3D surfaces whose goal is to achieve the highest overall sensing quality. They showed that the optimal deployment can be determined based on a special type of Voronoi diagram which is called Centroidal Voronoi tessellation. They proposed algorithms able to support different 3D surfaces. However, sensor nodes area static and their positions are computed by a central entity. Then, these algorithms are not scalable.Another study in [START_REF] Li | Autonomous deployment for load balancing-surface coverage in sensor networks[END_REF] is also based on Voronoi diagram to ensure 2D or 3D k-coverage (i.e. an area is covered by at least k sensor nodes). The authors proposed an autonomous deployment for load balancing k-surface coverage called APOLLO. This algorithm allows sensor nodes to move and achieve k-coverage, while minimizing the maximum sensing range required by the nodes.

The virtual forces strategy is based on attractive or repulsive forces to move sensor nodes based on a predefined target distance D th that should be maintained between neighbors. Then, if the distance between two sensor nodes is less than D th , a repulsive force is exerted. If this distance is greater than D th , an attractive force is exerted. Otherwise, the force is null. Then sensor node will move according to the resultant of these forces. Virtual forces strategy allows sensor nodes to compute their positions autonomously. The 3D version of the virtual forces is used in both [START_REF] Li | Deploying three-dimensional mobile sensor networks based on virtual forces algorithm[END_REF], [START_REF] Miao | 3d self-deployment algorithm in mobile wireless sensor networks[END_REF] and [START_REF] Boufares | Three dimensional mobile wireless sensor networks redeployment based on virtual forces[END_REF], to ensure full coverage of 3D area (volume) and maintain network connectivity. The benefit of these algorithms is due to the simple principle of the virtual force strategy: sensor nodes are able to spread in the whole area and reach rapidly the final deployment.

In this paper, we focus on 3D surface coverage. We assume that the 3D surface may be unknown or hostile and sensor nodes are mobile. We adopt the virtual forces strategy to spread over the whole 3D surface (i.g. mountains). The goal is to ensure full 3D surface coverage and maintain network connectivity.

III. OUR CONTRIBUTION : 3D-DVFA-SC

To deploy sensor nodes in 3D-surface, we propose 3D-DVFA-SC algorithm: 3D Distributed Virtual Forces Algorithm for Surface Covering. 3D-DVFA-SC is a distributed algorithm based on the virtual forces strategy to spread sensor nodes in the whole 3D-surface while maintaining network connectivity. The aim of the virtual forces is to maintain the same target distance between neighboring nodes. This target distance is called D th , Distance threshold.

A. Models and Assumptions

In this paper we adopt the following assumptions in order to cover the whole 3D surface:

• Each sensor node is mobile and autonomous.

• Each sensor node can determine its own position from global positioning system (GPS).

• The binary sensing model is adopted as the sensing model, which means the probability of detecting the target is 1 if this one is within the sensor's sensing range, and 0 otherwise. • The sensing range and communication range of any sensor node are modeled by two spheres of radius r and R respectively (see Figure 2). • The entity to monitor is a 3D surface, see Figure 1b.

• The 3D surface exerts a gravitational attraction on sensor nodes, see Figure 3. This gravitational attraction maintains each sensor node on the surface. This attraction combined with the resultant of the virtual forces gives a force tangent to the surface. The 3D-DVFA-SC algorithm proceeds in iterations. At each iteration, each node broadcasts a Hello message. In the Hello message, each node sends its position and the node it hears in order to perform the neighborhood discovery. Then, each sensor node is able to determine its 1-hop neighbors and 2hop neighbors. It is then able to compute its new position according to the forces exerted on itself by its 1-hop and 2hop neighbors.

(x j -x i ) 2 + (y j -y i ) 2 + (z j -z i ) 2 .
The force exerted by sensor s j on sensor s i is • an attractive force if d ij > D th and is given by:

F ij = K a • (d ij -D th ) • (x j -x i , y j -y i , z j -z i ) d ij
• a repulsive force, if d ij < D th and is equal to

F ij = K r • (D th -d ij ) • (x i -x j , y i -y j , z i -z j ) d ij • null otherwise, (d ij = D th )
Hence, the resultant force F i on s i is computed as the sum of these forces exerted by its 1-hop and 2-hop neighbors:

F i = j F ij
Since the sensor node should follow the 3D surface considered, node s i will move according to the resultant force and the gravitational attraction of the 3D surface.

Notice that Ka and Kr are the attractive coefficient and the repulsive coefficient of the virtual forces strategy, respectively. To favor the convergence of the algorithm the Kr coefficient should be much higher than the Ka.

To improve efficiency of the algorithm, the distance traveled by each sensor node at each iteration is limited by Distmax.

IV. PERFORMANCE EVALUATION

A. Simulation Parameters

To evaluate performances of our 3D-DVFA-SC algorithm, we implemented it in the Network Simulator NS3 version 3.20. Table I illustrates the simulation parameters used to evaluate the 3D-DVFA-SC algorithm.

The values of Ka and Kr are tuned by series of simulations. The 3D surface considered is depicted in Figure 4. Its equation is given by:

z = 80 * exp((-(x -50) 2 -(y -50) 2 )/600) (1)
We evaluate 3D-DVFA-SC using two initial configurations: • Random configuration, when sensor nodes are randomly scattered in the whole 3D-surface (mountain) by an aircraft (see Figure 5a). • Bottom of the mountain configuration, when sensor nodes are placed randomly at the bottom of the mountain (see Figure 5b). To evaluate 3D-DVFA-SC, we performed 20 simulations for each configuration.

B. Simulation Results

1) Coverage rate: We evaluate the coverage as a function of time for both configurations. To compute the coverage of a 3D-surface, we build a virtual grid of unit cells and we project each cell center on the 3D-surface. Each cell center projected is considered covered if it is at a distance less than or equal to the sensing range of at least one sensor node. Figure 7 shows the coverage rate obtained by both configurations. When sensor nodes are randomly deployed in the whole 3D-surface, the coverage rate reaches 100% at time 1000s. However, when sensor nodes are initially at the bottom of the mountain, the coverage rate at the end of the simulation is 90%. This is due to the shape of the mountain. Sensor nodes needs much time to reach the top of the mountain when they are initially deployed at the bottom. However, the very good results obtained by using the initial random configuration in short time can be explained by the fact that when sensor nodes are scattered in the whole area, the coverage rate is initially good and it is improved by 3D-DVFA-SC algorithm. The 3D-DVFA-SC enable sensor nodes to heal coverage holes when the initial configuration is random and to maintain network connectivity. Final deployment is illustrated in Figure 6. Figure 6a shows that full 3D-surface coverage is ensured and Figure 6b shows that network connectivity is maintained by the 3D-DVFA-SC algorithm. Notice that, in our study, we take into account the opaque shape of the mountain. Then, neighboring sensor nodes (i.e. where sensor nodes are at a distance less than or equal to the communication range) may not be able to communicate since the line of sight between them cross the mountain. In such a case, the connectivity is maintained only between neighboring sensor nodes whose line of sight does not intersect the 3D-surface and whose distance is less than or equal to R.

2) Distance traveled: We evaluate the total distance traveled by nodes as a function of time for both configurations. Figure 8 shows the accumulative distance traveled by nodes In this paper, we proposed 3D-DVFA-SC, a distributed deployment based on virtual forces to ensure full 3D-surface coverage and maintain network connectivity. We evaluated 3D-DVFA-SC using two different initial configurations. Wen 3D-DVFA-SC algorithm is executed with the initial random configuration, 100% coverage rate is reached. However, when sensor nodes are initially at the bottom of the mountain, the coverage rate is slightly smaller than with the other configuration. We also evaluated the total distance traveled by nodes. Simulation results show that sensor nodes still moving even when full 3D-surface coverage is reached.

  a Polyhedron. b 3D surface.

Fig. 1 :

 1 Fig. 1: 3D area.

Fig. 2 :

 2 Fig. 2: Sensing and communication ranges modeled by spheres

Fig. 3 :

 3 Fig. 3: Gravitational attraction on the sensor node

Fig. 4 :

 4 Fig.4: 3D surface corresponding to Equation1.

a

  Random configuration b Sensors are at the bottom of the mountain.

Fig. 5 :

 5 Fig. 5: Initial configurations.

Fig. 6 :

 6 Fig. 6: Final deployment.

Fig. 7 :Fig. 8 :

 78 Fig. 7: Coverage as a function of time

TABLE I :

 I Simulation parameters

	Toplogy
	Sensor nodes	300
	3D surface considered	Equation 1
	MAC Layer
	Protocol	IEEE 802.11b
	Throughput	2 Mb/s
	Transmission range R	15 m
	Sensing range r	9m
	Simulation
	Simulation time	2500s
	3D-DVFA
	Ka	0.004
	Kr	0.25
	Hello period	2.4s
	D th	10m
	Distmax	4