J J Moreau
email: moreau@lmgc.univ-montp2.fr

FACING THE PLURALITY OF SOLUTIONS IN NONSMOOTH MECHANICS

SUMMARY

In the mechanics of systems involving dry frictional contacts it is known that the problem of evaluating at some instant the contact forces and the accelerations may admit a plurality of solutions. Starting from an elementary example of wedging one proposes, as a consistent way of handling information, to include the contact forces in the description of each state. This in fact is what popular time-stepping computation techniques do, as they make reference at each time-step to the constraint state calculated in the antecedent one (actually a way of treating Coulomb law incrementally). The Contact Dynamics technique optionally offers the alternative of discarding this information, exploring the consequent indeterminations and displaying the sets of solutions as clouds of dots. Examples arising from Granular Mechanics are presented. The so-called Painlevé paradox is commented. Finally, an explanation of the isostaticity of the equilibrium of a collection of frictionless round grains is proposed.

INTRODUCTION

However complex may be the phenomena which take place when two bodies touch each other, should sliding occur or not, the law of Coulomb provides an irreplaceable framework for approaching dry friction. In many industrial situations, the only quantitative information provided by technical documents about friction-affected devices is communicated in terms of Coulomb friction coefficients (with possible distinction between sticking and sliding values).

That the motions calculated from such a model frequently are mathematically nonsmooth reflects everyday observation: in the absence of lubrication, mechanisms may exhibit chattering motions, emit creaking noise, or jam.

Discussions have taken place for a long time about the fact that, in the dynamics of systems involving Coulomb friction, the initial value problem, i.e. the prediction of the motion consequent to an instant at which the positions and the velocities of the system elements are given, may have several solution or no solution at all. In the eyes of a 19th. century scientist like Painlevé, impressed by the theory of differential equations and Laplace's "determinism", this was an inacceptable defect, leading him to the point of rejecting the very concept of a contact force. The disquieting locution of "Painlevé's paradox" caused definite harm to mechanical science since engineers who had, from other parts, some reasons to be unsatisfied with the moderate quantitative precision of Coulomb law, tended to view this wording as a hint at some logical defect. The irrelevance of Painlevé's standpoint was already pointed at in his time [START_REF] Lecornu | Sur la loi de Coulomb[END_REF].

In our view, a physical model is nothing but a format, in the sense of data processing, in which one decides to record the available information concerning a certain physical situation, to treat this information and finally to communicate conclusions. Fundamentally, the information one may collect about the investigated situation is always incomplete, so the model through which this information is coded cannot be expected to generate exhaustive predictions. Also, as the system evolves, the validity limits of the model may come to be overrun.

ELEMENTARY EXAMPLE

The system shown on Fig. 1 is contained in a vertical plane. Two fixed walls slightly converge upward. A rigid rod, subject to gravity, is inserted between them, with Coulomb friction at the two contact points and abandoned at zero velocity. If the configuration angles have suitable values, compared with the friction angles at contact points, the problem of finding the consequent motion visibly has two solutions: either the rod loses contact and falls freely or it remains wedged.

The quadrilateral area filled with light gray is the intersection of the Coulomb cones drawn from the two contact points. The triangular part above AB intersects the vertical of the center of gravity G along a line segment. Any position of I on this segment corresponds to values of the contact forces R A and R B compatible with the no-sliding Coulomb condition and equilibrating the rod weight. But zero values for R A and R B are also compatible with the friction law, yielding a downward acceleration of G, hence the breaking of contact.

Intuitively, the outcome depends on the "intensity of wedging" of the rod. The natural measure of such a degree precisely consists of the values of contact forces and it turns out that, in the present case, knowing these forces allows one to predict the further motion unambiguouly. For more complicated systems, the numerical investigations presented in the sequel show that treating contact forces as part of the description of each state reduces ambiguity considerably. A deeper insight into the present situation could be expected from the use of a richer model than above. To this end, one may take into account a certain longitudinal elasticity of the rod. This involves the introduction of a "small" variable s, the rod elongation counted from some reference state. As long as contacts are effective, the value of s is geometrically related to the displacements of points A and B on the respective walls, still treated as indeformable. Given a law of longitudinal elasticity of the rod, a differential equation with the longitudinal components of R A and R B as endpoint data allows one to determine the stress distribution along AB. For simplicity, assume AB horizontal and all the applied forces vertical. Then this elastic analysis simply results in a monotone relationship between the variable s and the (opposite to each other) longitudinal components of R A and R B .

Such a model provides an understanding of the scenario of rod insertion and extraction. If, after contact is established, increasing upward forces are applied, the evolution (assumed quasistatic) consists in points A and B sliding upward. At every time, vectors R A and R B have lines of action imposed by Coulomb law in sliding regime. Thanks to the quasi-equilibrium equations of the rod, they may be calculated from the values of the applied forces.

If, at some instant, one decides to make the upward pushing forces decrease and eventually take downward direction, a new episode of motion begins, still assumed quasi-static. Points A and B remain fixed so that the elastic relationship, whatever it is, makes the longitudinal components of R A and R B keep the values they had at the instant of reversal. At every time, the values of R A and R B result from the values of the applied forces and the no-slide regime persists so long as these calculated vectors lie in the respective Coulomb cones. This allows one to determine the value that the resultant of the downward applied forces should eventually reach to produce detachment. This model has the merit of making understand the processes of insertion and extraction but, to the lay observer, it conveys no quantitatively tractable information in the absence of a measuring device for microdisplacements, commonly not at hand. Since the proper elasticity law of the rod turns out to be immaterial, one may expects that some model merely ignoring this elasticity could be able to reproduce the above scenario. In fact, the Contact Dynamics computation method has been found to yield numerically a response of contact forces to the pushing history which agrees with what precedes.

TIME-STEPPING COMPUTATION

A widespread method for the numerical simulation of multibody systems is derived from the techniques used in Molecular Dynamics, hence referred to as MD. It consists of approximating the impenetrability constraints, when two bodies come close to each other, by repulsion forces steeply dependent on the mutual positions. Friction forces are similarly approximated, yielding an evolution problem governed by differential equations smooth enough for being handled through standard integration methods. In this way, the interaction forces are connected with fictitious deformations passed from step to step, so that the numerical scheme complies with the proposition made in the foregoing of including these forces in the description of each state. The drawback of the method is that, for the sake of precision, very stiff repulsion laws are needed so that very short step-lengths have to be used in the integration of the differential equations, usually with artificial damping introduced to prevent numerical instability. These added features may alter significantly the behaviour of the investigated system.

Another approach entitled Contact Dynamics (abbr. CD) will be preferred here in view of its ability to explore also the plurality of solutions. It faces the essential nonsmoothness of the impenetrability constraints and of dry friction without resorting to any regularizing alteration of the model [START_REF] Moreau | Unilateral contact and dry friction in finite freedom dynamics[END_REF] (for a recent exposition, see [START_REF] Moreau | An introduction to unilateral dynamics[END_REF]). The dynamics of a system with n degrees of freedom is formulated in terms of two functions of a time-interval [0, T ] to R n , the position function t → q, and the velocity function t → u. In the simplest case, q equals the timeintegral of u; the kinematical relationship only becomes slightly more complicated when some members of u consist for instance in components of the spin vectors of rigid parts.

The geometric effect of non-interpenetrability is expressed by a finite set of inequalities f α (q) ≤ 0, with equality corresponding to contact. The leading feature of the CD approach is that these inequalities are actually handled at the velocity level: by astraining u(t) to belong for (almost) every t to a certain cone K(t, q), one secures inequalities to hold throughout [0, T ] provided they hold at initial instant.

In addition, some mechanical information about each contact should be available in terms of a contact law, i.e. a relationship connecting, for each α such that f α (q) = 0, the local kinematics with the contact force R α whose generalized components are noted r α ∈ R n . Coulomb law in particular may be written in such a form.

The equations of classical (smooth) Mechanics may be viewed as a differential equation, say du/dt = E(t, q, u, Σ r α ), governing the function u and involving the other unknown q as a t-dependent parameter. But in the present context, the nonsmoothness arising from contact unilaterality and dry friction is liable to entail discontinuities for the function u. The suitable mathematical framework is that of u being an R n -valued function of t with bounded variation, so that the differential equation of the classical case is replaced by a measure-differential equation MDE. This means that the derivative du/dt should then be understood as an R n -valued measure on [0, T ], with punctual atoms at the instants of possible collisions. Mechanical actions, in particular the unknown contact forces or contact percussions are also described through such measures.

A time-stepping scheme is constructed by integrating both members of MDE on each interval of the time grid, say [t i , t f ], with t f = t i +h. Starting from the approximant u i of u(t i ) delivered by the antecedent step, the objective is to calculate an approximant u f of u(t f ). Concomitant unknown is the contact impulsion s = Σs α , i.e. the integral of Σr α over [t i , t f ]. The discretized MDE thus has to be complemented by some impulsional form of the contact laws, hopefully valid to connect each s α with some estimate U α of the local relative velocity of the contacting bodies. If one chooses as U α the value kinematically associated with the unknown u f , the resulting discretization scheme turns out to be of the implicit type. Whatever is the procedure additionally used to update the continous function q at the end of each step, such an implicit character secures numerical stability, allowing one to use considerably larger step-lengths than in MD methods. The price to pay is that the core of the calculation at each time-step consists of a highly nonlinear and nonsmooth problem.

Various techniques are available to solve the core problem [START_REF] Renouf | Gradient type algorithms for 2D/3D frictionless/frictional multicontact problems[END_REF], possibly parallelized [START_REF] Renouf | A parallel version of the non smooth contact dynamics algorithm applied to the simulation of granular media[END_REF]. The most commonly used is a nonlinear Gauss-Seidel procedure which suits well the present needs. It consists in reviewing the detected contacts cyclically again and again, solving for each of them a single-contact problem in which the other contact forces are treated as known and using the result to update interactions until some convergence criterium is met.

By connecting the contact impulsions s α with u f , the CD numerical scheme turns out to treat possible collisions as perfectly inelastic. An improvement, leading to a core problem of the same computational cost, consists in connecting each s α with some weighted mean of the initial and final values of U α (possibly using different weights for normal and tangential components). In the special case of a binary collision this trick is found equivalent to the introduction of some Newton restitution coefficients (for spherical grains, this has been fairly well validated by experiments in [START_REF] Foerster | Measurements of the collision properties of small spheres[END_REF]), but in general it offers the advantage of handling also multicontact systems with plausible results. Example: the rocking of a slender block on a horizontal ground [START_REF] Jean | Unilaterality and dry friction in the dynamics of rigid body collections[END_REF].

The CD numerical strategy may also be applied to collections of deformable bodies, discretized through finite elements [START_REF] Jean | Implementation of unilateral contact and dry friction in computer codes dealing with large deformation problems[END_REF].

Gauss-Seidel iterations have to be launched from some initial guess of the terms s α . This guess may consist of zero values but, in the case of dense collections of rigid bodies, one considerably accelerates convergence by starting from the values found for these impulsions at the antecedent step, for the contacts which were already active. If this is done, computation does comply with the proposition made in the foregoing of treating contact forces as state variables passed from step to step and very little indeterminacy is observed.

Of course such a way of passing some information about the past makes sense only in timestepping computation. At the level of theoretical formulation, what this numerical practice reflects is an incremental formulation of Coulomb law.

In contrast, given a time-step, if the information about antecedent contact forces is disregarded the Gauss-Seidel procedure allows one to explore the plurality of the solutions to the core problem. One possibility for this exploration is to execute a large number of runs of the cyclic iteration process, each time with initial guess drawn at random from some plausible range. Any solution then has a chance to be approached. Alternatively, one may launch all runs from zero initial guess while choosing at random, for each run, the ordering of the cyclic review of contacts. The limit of a run depends on this ordering. With κ contacts, the number of solutions attained in the latter way equals at most (κ -1)! which has been found sufficient to generate a significant outline of the solution set, as illustrated in Sect.4 below.

To determine whether a given position is an equilibrium, a single computation step is enough: starting with u i = 0, one checks whether u f = 0. The values found for the contact impulsions s α yield the respective contact forces as r α = s α /h.

AN EQUILIBRIUM

Fig. 2 presents a detail of a collection of N = 28 frictional circular bodies in equilibrium under gravity. The number of contact points being denoted by κ, the problem is to calculate the element r of R 2κ consisting of the components of the contact forces.

The 3N independent equations of equilibrium restrain r in an affine submanifold A of R 2κ with dimension 2κ-3N . Coulomb law requires of each contact force, say r α , to belong to an angular region C α of the corresponding two-dimensional factor subspace of R 2κ . This is equivalent to r belonging to a polyhedral cone C in R 2κ , the Cartesian product of regions C α . The set of equilibrium solutions thus equals the intersection A ∩ C, a convex hyperpolyhedron. Coming back to an individual contact, the set of the possible values of the associated contact force equals the Cartesian projection of A∩C onto the corresponding two-dimensional factor subspace. The two procedures described in the preceding Section are applied to their exploration.

For a specified contact point in the assembly, each run of the Gauss-Seidel algorithm allows one to draw a dot at the extremity of the computed contact force. By repetition, one obtains clouds outlining the investigated sets; of course, they are included in the angular regions imposed by Coulomb law.

For grain 1, simply supported by two underlying ones, clouds reduce to rectilinear segments parallel to the undetermined "wedging components" acting along AB and the situation is similar for grain 2. In contrast, grain 3 is involved in a more complicated pattern of interactions resulting in extended indetermination clouds.

A surprise is the appearance inside these clouds of some ghost images of edges and vertices of the high-dimensional polyhedron A ∩ C, not the same for both procedures.

For a similar collection of discs in equilibrium, an investigation of force indeterminacy in statistical spirit is reported in [START_REF] Unger | Force indeterminacy in the jammed state of hard disks[END_REF]. Periodic boundary conditions are applied, i.e. calculation is performed on disks with centers in the master band -a ≤ x < a. Disks in the vicinity of x = ±a may interact through contact with the images of other ones under translations (±2a, 0); if they come to exit the master band they are removed from computation while some images of them are entered instead.

Grain-to-grain friction: 0.3; ground friction: 0.5; restitution of possible collisions: 0.

Flow is not in stationary regime but, starting from rest, it accelerates as the effect of gravity. Some results of computation are displayed on Fig. 4 (11 computation steps after start) and Fig. 5 (121 steps after start) both produced by repeated runs of the Gauss-Seidel procedure at zero initial guess, each run using a reviewing order selected at random.

An extended cloud at the first instant, the indeterminacy figure becomes a simple line and, as time grows, eventually shrinks to the size of numerical incertainty. For instance, at t = 0.0444, the acceleration vector of some typical grain has a magnitude of about 520, while the indetermination range of its components is found to reduce to 0.007. We have no explanation to propose for such a decrease of indeterminacy as the flow gains speed. One might think of the number of contacts involved in calculation and of the proportion of sticking ones as determinant parameters. Actually, at the instant of Fig. 4, the number of contacts in the flow domain equals 556, among which 75% have zero sliding. At the instant of Fig. 5, the number of contacts equals 544, with 70% of zero sliding ones. At the instant of negligible indetermination referred to above, the number of contacts is still as hight as 506, with 57% of zero sliding ones.

PAINLEVE STATE AND FRICTIONAL PAROXYSM

In his criticism of the dry friction model, Painlevé invoked the very simple example of the motion of a rigid rod in a vertical plane, the extremity A of which slides with Coulomb friction on a fixed horizontal ground. Initial data consist of the angle θ of the rod with ground and of the velocity parameters (compatible with A remaining on ground). The problem of "incepting motion" is that of applying the equations of Dynamics in order to calculate the acceleration parameters at this instant. This is merely solving an algebraic system of linear equations and, if the friction coefficient is large enough, it turns out that, for a specific couple of values of θ and θ = dθ/dt, no solution exists because a certain determinant vanishes (this may also lead to indeterminacy if some other quantity vanishes).

Today, one is not surprised to see a model refusing certain values of the parameters. A more interesting issue was recently addressed: may an episode of regular motion lead to such a Painlevé state? The answer is found "yes" through the elementary reduction of the system of second order differential equations to a single first order equation in the variables θ, θ. The qualitative and numerical investigations of the integral lines reveal that the Painlevé state corresponds to some singular point in the (θ, θ)-plane. All the integral lines emanating from a certain basin in this plane terminate at this very point and (with the exception of one of them) the corresponding angular acceleration θ = θ(d θ/dθ) tends to ±∞. Consequently, the magnitude of the force exerted by the rod upon the ground tends to infinity; we propose to call that a frictional paroxysm. A detailed mathematical analysis [START_REF] Génot | New results on Painlevé paradoxes[END_REF] confirms these graphical findings.

What could the motion be after the paroxystic instant depends on the mechanical assumptions one accepts about the friction phenomenon when contact forces tend to infinity. This is somewhat similar to a collision and the locution "tangential shock" is sometimes used. A model yielding a one-parameter indeterminacy in the after-paroxysm velocities is developed in [START_REF] Moreau | Unilateral contact and dry friction in finite freedom dynamics[END_REF]; it is automatically handled by CD time-stepping.

A definition of the concept of solution and an existence theorem (uniqueness not asserted) covering this case may be found in [START_REF] Stewart | Convergence of a time-stepping scheme for rigid body dynamics and resolution of Painlevé's problem[END_REF].

STATICS OF FRICTIONLESS ROUND RIGID BODIES

In contrast with the precedings we turn now to the statics of frictionless rigid body collections. Authors in [9][12] have asserted that, if a collection of spherical bodies (circular ones in 2D settings) contained in a fixed vessel is submitted to such external forces as gravity, then "generically" or "with probability 1", the configurations taken by this system at equilibrium are isostatic. In the traditional context of frictionless systems involving only equality constraints, discussing isostaticity or more generally assessing the degree of hyperstaticity of an equilibrium amounts to evaluate the dimensions of the kernels or ranges of some linear mappings. In the present unilateral setting, equilibria are not characterized by equalities but by complementarity conditions, so that the discussion does not reduce to evaluating dimensions anymore.

Repeated numerical simulations have confirmed the assertion, but we are not fully convinced by the arguments of the authors, so we suggest below a novel approach to the question.

First observe that, in the statics of a frictionless collection of n spherical balls, the relevant position parameters merely are the coordinates of the respective centers. Use as abstract parameter the element q of R N , N = 3n, consisting of all these Cartesian coordinates.

The geometric effect of the non-interpenetrability of the balls and of their confinement by the vessel (one may assumed it polyhedral for simplicity) is expressed by inequalities

f α (q) ≥ 0, α ∈ {1, . . . , ν}, (1)
with real functions f α convex and smooth. This defines in R N the feasible region Φ, equivalently the complement of the union of the smooth convex sets defined by replacing the ≥ symbols by <. The boundary Σ of Φ may thus be viewed as a "quilted" hypersurface constructed by piecing together some portions of the boundaries S α , α ∈ {1, . . . , ν} of ν smooth convex sets with nonempty interiors. The S α are smooth hypersurfaces which meet along hyperedges.

In particular, hyperedges of dimension zero constitute pits in Σ.

For every α ∈ A(q) = {α : f α (q) = 0}, the configuration q involves a contact, which imparts on the system some contact forces with generalized components r α ∈ R N . Through the standard machinery of Analytical Mechanics [START_REF] Moreau | Unilateral contact and dry friction in finite freedom dynamics[END_REF], the assumption that contact is frictionless and adhesionless is equivalently transformed into

∃ρ α ≥ 0 : r α = ρ α ∇f α (q) (2)
(if all balls have nonzero radii, one may check that all ∇f α (q) are nonzero element of R N ; furthermore no pair of them have a common direction).

Let the applied forces consist of the action of gravity upon the respective balls; their generalized components make a vector F ∈ R N , independant of q. Provided gravity doesn't lie in an unboundedness directions of the vessel, the system possesses equilibrium positions belonging to Σ and, in view of the above description of the feasible region, it is only in pits that such equilibria may be stable.

Let q, located in some pit of Σ, denote an equilibrium configuration under force F ; in view of (2) this means that -F equals a nonnegative combination of the elements ∇f α (q), α ∈ A. We claim that "generically" these elements make a base in R N , hence the expected uniqueness. We assert that generically no more than N of them can pass through a specified point and that the corresponding ∇f i evaluated at this point are linearly independent. Here is an intuitive explanation.

Let N of the above hypersurfaces pass through some point p 0 . Effecting if necessary some arbitrarily small alterations (e.g. altering some of the c i ), one may obtain that two of them intersect transversally along a regular manifold M N -1 containing a point p 1 arbitrarily close to p 0 . Again after a possible alteration, a third surface may be made to intersect M N -1 transversally along a manifold M N -2 containing a point p 2 close to the preceding ones. The procedure has to be repeated, finally yielding N hypersurfaces which intersect in the expected regular way at some isolated point p N close to p 0 . And it would be "exceptional" that another hypersurface of the collection pass through this point.

The essential issue is the meaning that one gives to the concept of genericity. A mathematical object depending on a parameter p ∈ R m will be said to possess some property P generically if P holds for every p in a subset of R m whose complement is viewed as an exceptional set. A choice has to be made about the class of sets to be considered as exceptional, similarly to what is done in the Theory of Transversality.

• One may declare exceptional the subsets of R m with zero Lebesgue measure. This choice opens the way to probabilistic statements by viewing p as a random variable. If the probability distribution of p admits a density relative to Lebesgue measure, an exceptional set then has probability zero. The reader willing to develop the argument in this direction may take inspi-ration from [START_REF] Spingarn | The generic nature of optimality conditions in nonnlinear programming[END_REF], a paper devoted to similar questions of genericity in nonlinear programming. The central analytic tool is Sard's theorem; it requires a high order of differentiability for the concerned functions, in fact secured in the present context.

• In a different approach, the property P will be declared generic if holds for every p in a dense open subset Ω of R m . In other words, if a point doesn't belong to Ω, an arbitray small displacement is enough to bring it into Ω and, since Ω is open, property P is then secured in a "stable" way. Actually, results in this line need a slightly more complicated construction: the exceptional sets shall be the Baire sets of first category (also called meagre sets).

Figure 1 :

 1 Figure 1: A rod inserted between convergent walls

Figure 2 :

 2 Figure 2: Contact force indeterminacy

Figure 3 :

 3 Figure 3: Dispersion of acceleration vectors at t = .00044

Figure 4 :

 4 Figure 4: Acceleration vector indeterminacy at t = .00044 Figure 5: Acceleration vector indeterminacy at t = .00484

Figure 6 :

 6 Figure 6: An illustration in R 3

Figure 6

 6 Figure 6 illustrates with N = 3 the proposed argumentation. After fixing ν real numbers c 1 , . . . , c ν , consider in R N the ν hypersurfaces f i = c i (here ν ≥ N ). We assert that generically no more than N of them can pass through a specified point and that the corresponding ∇f i evaluated at this point are linearly independent. Here is an intuitive explanation.


João Rodrigues
email: joao.rodrigues@dcc.fc.up.pt

Eduardo R B Marques

Joaquim Silva
email: joaquim.silva@dcc.fc.up.pt

Luís M B Lopes
email: lblopes@dcc.fc.up.pt

Fernando Silva

Video Dissemination in Untethered Edge-Clouds: a Case Study

We describe a case study application for untethered video dissemination using a hybrid edge-cloud architecture featuring Android devices, possibly organised in WiFi-Direct groups, and Raspberry Pibased cloudlets, structured in a mesh and also working as access points. The application was tested in the real-world scenario of a Portuguese volleyball league game. During the game, users of the application recorded videos and injected them in the edge-cloud. The cloudlet servers continuously synchronised their cached video contents over the mesh network, allowing users on different locations to share their videos, without resorting to any other network infrastructure. An analysis of the logs gathered during the experiment shows that such portable setups can easily disseminate videos to tens of users through the edge-cloud with low latencies. We observe that the edge cloud may be naturally resilient to faulty cloudlets or devices, taking advantage of video caching within devices and WiFi-Direct groups, and of device churn to opportunistically disseminate videos.

Introduction

Traditional mobile cloud computing focuses on moving processing and storage of data generated by mobile devices to centralised cloud datacenters. This offloading of computation and data benefits the users by decreasing battery consumption in the devices and allows them to access highly reliable infrastructure with seemingly unlimited computational and storage resources. However, due to the distance (both physical and logical) that separates a device at the edge of the network from the cloud, a major technical challenge prevails: how can mobile cloud computing provide applications with low-latency and/or high-bandwidth requirements? What if the infrastructure is unavailable or bandwidth limitations are part of the scenario, e.g., in the aftermath of natural disasters and in dense environments such as sports or music events?

To address these issues, new paradigms such as mobile edge-clouds [START_REF] Drolia | The Case for Mobile Edge-Clouds[END_REF] and cloudlets [START_REF] Satyanarayanan | The Case for VM-Based Cloudlets in Mobile Computing[END_REF] strategically combine traditional cloud infrastructure with the resources provided by devices and small servers near the edge, enabling proximityaware applications. In a mobile edge-cloud, for example, nearby devices work together to form a pool of computing resources with sustained operation under poor connectivity and access to crowd-sourced information which otherwise might be unavailable. Computational tasks are performed locally, i.e., there is no offloading of computation or data to a traditional cloud infrastructure. Cloudlets, on the other hand, bring processing and storage resources closer to the edge to support local offloading of tasks from devices or to serve as caches.

Content Distribution Networks (CDN) can significantly benefit from the aforementioned evolution in edge-cloud technology, e.g., in real world scenarios like sports or concert venues, or social gatherings like weddings, parties and graduation ceremonies. For example, there are apps that provide users within (and outside) sports venues with almost real-time statistics and multimedia contents like the number of kilometres a player has run or video replays for goals or interesting events [START_REF] Robb | HuaweiVoice: Agile Stadiums Bring Digital Content To Sports Fans[END_REF][START_REF] Yinzcam | [END_REF]. Video replays are downloaded from central servers to the mobile devices through the venue's WiFi or cellular infrastructure access points. If, however, the venue is crowded, the large number of requests can stress the infrastructure [START_REF] Erman | Understanding the Super-sized Traffic of the Super Bowl[END_REF][START_REF] Kapustka | State of the Stadium Technology Survey[END_REF]. In this context, edge-cloud based CDN can be used as a complement to the infrastructure by performing local video dissemination and caching, removing a significant load from the access points. In previous work [START_REF] Silva | Using Edge-Clouds to Reduce Load on Traditional WiFi Infrastructure and Improve Quality of Experience[END_REF] we showed that this is indeed possible, in a scenario in which a single (venue) server provides the video replays and the user's mobile devices organize themselves into mobile edge-clouds that cache and share those replays. We envision that users can be engaged through diverse incentives, for instance sweepstakes involving goods like team merchandise or game tickets.

In this paper, we explore a more extreme scenario. First, users can consume replays but they can also produce and inject them in the edge-clouds. Second, such clouds of devices can work totally offline, outside the venue's infrastructure, by sharing video replays among themselves and with another tier composed of modest cloudlet servers. The latter synchronize contents periodically allowing for injected videos to be disseminated to different areas of the venue more efficiently. Finally, we use churn, the natural movement of devices in the venue, to disseminate contents opportunistically. We implemented a CDN for the scenario, coupled with an Android app for video acquisition, dissemination and viewing. The software infrastructure was tested in a real world scenario during an official Portuguese volleyball league game. During the experiment, users of the application recorded small video replays of the game through their smartphones and injected them in their edge-cloud and in their local cloudlet servers. The latter synchronised with the other cloudlets in the mesh on a regular basis allowing users on opposite sides of the venue to access videos with different perspectives in almost real-time, and without resorting to any on-site or 3G/4G network.

The rest of the paper is organised as follows. Section 2 presents the scenario and the network architecture to support the "user generated replays" application. Section 3 delves into the implementation of the network tiers. Sections 4 describes the experiment and the results we obtained. Section 5 discusses related work. Section 6 presents concluding remarks and discusses future work.

Our interest on video dissemination in the context of edge-clouds stems from work in the Hyrax project 1 . The rationale for the latter is to explore a range of, potentially game-changing, crowd-sourcing middleware and applications that harness the collective resources of mobile devices and cloudlets at the edge of the network. Several case study applications were considered in the scope of the project, including caching and device-to-device techniques for video dissemination, distributed computer vision, and fully untethered communications infrastructure for emergency situations.

Previous work in a more restricted scenario, where contents were selected from a TV stream by administrators and published exclusively through central servers, showed that edge-clouds of mobile devices can successfully cache and disseminate a significant fraction of the video contents provided by servers, effectively removing up to 60% of the load from conventional access points [START_REF] Silva | Using Edge-Clouds to Reduce Load on Traditional WiFi Infrastructure and Improve Quality of Experience[END_REF]. We did this without resorting to rooting the devices or any otherwise intrusive operation that might render the client applications unfit for general public use. In this paper, we explore a more extreme scenario for sports venues (Figure 1) in which users can both consume and produce replays. When they produce a replay they publish it, with some metadata, in the edge-cloud. Also, these clouds of devices can now work totally offline, without the support of the venue's infrastructure. They do this with the help of a second network tier composed of modest cloudlet servers organised in a dynamic peer-to-peer mesh that synchronize their contents on-the-fly. Besides caching the videos published by devices, these servers also work as access points for devices and WiFi-Direct groups (WDGs) within a given spatial region. Finally, we use churn induced by the natural movement of devices in the venue to disseminate contents opportunistically, allowing devices to publish their videos to neighbouring edge-clouds as they enter them. Figure 2 shows the 2-tier architecture we used for this scenario. First, in tier 1, we have a mesh of cloudlet servers (in this case Raspberry Pi devices) that actively cache video contents published by tier-2 devices. They feature 2 wireless network interfaces: one to support the cloudlet mesh, the other to provide access points to tier 2 devices. The cloudlet servers actively synchronize their local video caches so that local videos can be accessed by devices under remote cloudlet servers. This is done on a best-effort basis, as no attempt is made to provide any strong form of consistency between the contents of the caches at each cloudlet server. In the absence of network errors (c.f. Section 4) the contents of these caches will progressively converge, i.e., eventual consistency will be attained [START_REF] Vogels | Eventually consistent[END_REF]. Mobile devices in tier 2 can form WDGs and use them to disseminate local contents, or they can connect directly to a cloudlet server. Each device also features a cache for holding the videos it generates and publishes plus the videos it downloads from other devices or cloudlet servers.

Implementation

We now describe the main implementation aspects of the infrastructure used in our case-study. We do so in terms of the hardware and software components for cloudlets and mobile devices, and the main algorithms used for video dissemination and edge cloud formation. The Raspberry has two USBattached D-Link DWA-172 WiFi cards with omnidirectional antennas, and runs the Raspbian 9.1 distribution with a Linux 4.9 kernel. One of the WiFi cards is setup in mesh mode using the BATMAN protocol2 over a 5 GHz band and a single channel (36) in all cloudlets with 20 MHz width. The other WiFi card is setup as an AP in the 2.4 GHz band using a distinct and non-overlapping 20 MHz channel per cloudlet (a choice of a 5 GHz band for the AP would limit connectivity by legacy AP clients). Two software services run in each cloudlet, a storage service and a synchronization service, as illustrated in Fig. 3b. Both services are supported by the local filesystem and a MongoDB database, used for storing video files and video metadata, respectively. The storage service, accessible via HTTP, deals with (upload and download) data transfers from mobile devices related to video files or corresponding metadata (video title, creation time, size, etc) and thumbnails (small images used by clients for video preview). The synchronization service is responsible for cloudlet announcement, discovery, and data transfers in the mesh network. Cloudlet announcement and discovery works dynamically over multicast UDP, allowing cloudlets to dynamically join or leave the mesh if necessary, and data transfers are made through TCP sockets. The algorithm in Figure 4 illustrates how a (possibly dynamic) set of cloudlets synchronize videos over time, using a best-effort active replication scheme that leads to eventual consistency among cloudlets in the absence of network failures. Each cloudlet periodically announces itself over multicast UDP with a hello message, allowing other cloudlets in the mesh to discover it. The hello message has an associated list of identifiers for available videos. As illustrated by the handle hello() procedure, receiving cloudlets determine which videos are not yet locally stored, and add the latter to a queue of pending videos to transfer. This queue is handled by a continuously running procedure, video sync(), such that each pending video entry is processed by downloading the corresponding metadata, thumbnail, and actual content, that are stored locally afterwards.

Android app. The Android app is illustrated in Fig. 5. The app works on non-rooted Android devices running at least Android version 5, thus making use of standard APIs in particular those for WiFi and WiFi-Direct networking. An app user may browse a list of videos (Fig. 5a) identified by their title, creation date, and duration, along with an image thumbnail. Upon selection, a video in this list can be viewed, downloading it first if this has not been done previously, since downloaded videos are stored persistently. The app also allows the reverse operation, i.e., recording a video and uploading it to the network (Fig. 5b). In implementation terms, the app is structured in terms of: a module that interfaces with the cloudlets' storage service via HTTP; a network manager that administers the dynamic role of the app/device in the network and; an additional module that deals with WDG data transfers via TCP/UDP. The app may connect to a standard WiFi AP, enabled by one the cloudlets in our scenario, or to a WiFi Direct group enabled by another device working as a "soft" AP, called the group owner (GO), that maintains the WDG and has (is able to maintain) a simultaneous a cloudlet/AP link. In standard operation, data flowing between non-GO members require a network hop through the GO, but Tunnelled Direct Link Setup (TDLS) may also be activated to enable (true) peer-topeer wireless links [START_REF] Rodrigues | Benchmarking Wireless Protocols for Feasibility in Supporting Crowdsourced Mobile Computing[END_REF].

The dynamics of network formation are discussed further below in this section. Focusing on group interactions for now, a WDG forms a mobile edge cloud where video download requests can be served from within the group, if the videos at stake are available in (i.e., were downloaded previously by) at least one of the members. When not, the GO's cloudlet fulfils the download onthe-fly, either directly, if the request originates at the GO, or with the GO acting as proxy between another group member and the cloudlet. All uploads by non-GO members are similarly routed on-the-fly from the GO to the cloudlet. When proxying file requests, the GO caches file, with the aim of improving resilience to churn in the group and the chance of one-hop transfers in the absence of TDLS links.

Apart from GO caching, and unlike in the cloudlet tier, video replication otherwise occurs passively in the group, i.e., videos are copied between members only when necessary due to an explicit download request by a user. Alternatively, an active replication could imply higher overhead in terms of network bandwidth and inherent battery consumption, but, on the other hand, also potentially lead to faster video dissemination, or reduce user wait-time without much impact in bandwidth if users tends to watch a high share of a limited pool of videos (e.g., the curated video setting of our previous work [START_REF] Silva | Using Edge-Clouds to Reduce Load on Traditional WiFi Infrastructure and Improve Quality of Experience[END_REF]). In the algorithm, state transitions are parameterised by a device threshold T op and a probability P op probability pairs, where op may refer to group creation, disposal, joining, or leaving. The threshold parameters impose limits as follows: min. devices visible in the AP network to create a group (T c ); min. devices in a group before the GO considers disposal (T d ); max. devices that a group may hold, inhibiting other devices to join (T j ) and; min. devices in a group before a group peer considers leaving (T l ). The probabilities govern the likelihood of transitions, provided all other conditions are enabled for an operation. The transition predicates (e.g. ShouldCreateGroup() for group creation) may also account for runtime conditions in the device and/or the network. Overall, the parameterisation scheme allows for flexible tuning according to the scenario of interest.

The concrete parameters for the game scenario are shown above the listing of Fig. 6, and result from an empirical calibration we did through some preliminary tests at the game venue. They reflect the concerns of not creating WDGs too aggressively (P c = 0.5, T c = 3), trying to maintain them active (P d = 0.5, T d = 1) and stable (P l = T l = 0) for relatively long, and encouraging devices to join groups and have groups of reasonable size (P j = 0.7, T j = 5). Together with this parameterisation, the evaluation of group creation, embedded in the implementation of ShouldCreateGroup(), feeds on battery and AP signal strength values broadcasted by devices (when connected to a cloudlet) to implement a simple heuristic: a device becomes GO only if it has the highest value of all (batteryLevel + signalStrength)/2 measures known for all devices; the scheme limits the chance that two devices connected to the same cloudlet become GO almost simultaneously. Other transition predicates could also easily be refined to account for runtime conditions, e.g., the battery level of a device while acting as GO in ShouldDisposeGroup() in order to avoid battery depletion (that occurs at a faster rate for GOs, given their role as soft APs), or the signal strength measured for the serving GO to decide leaving a group in ShouldLeaveGroup().

The experiment

Setup. We conducted our real-world experiment during a game of the Portuguese volleyball league between S. C. Espinho and Vitória S. C., that took place on December 1st, 2017, at the Nave Desportiva de Espinho sports venue 3 . We recruited several student volunteers to watch the game and use the video dissemination app, using Google Nexus 9 tablets running Android 6.0 that we provided. Additionally, some audience members and S. C. Espinho staff were also engaged to participate using their own smartphones. In total, 18 users/devices participated in the experiment.

For the experiment, the peer-to-peer mesh formed between the cloudlets was static in size and fully connected. At the venue, we had three cloudlets installed as shown in Figure 1, identified as C1, C2, and C3 in this section. Smartphones and tablets from the volunteers, sitting in the game stands or moving through them, formed tier-2. Before the experiment, we disabled the use of TDLS over WiFi-Direct, as we found that the Android app had stability problems; hence the app used only plain WiFi and WiFi-Direct. Additionally, GPS signal strength/precision was too poor inside the (indoors) sports venue for obtaining good location/mobility logs, hence we instructed volunteers not to activate GPS in the devices.

The experiment began at approximately 16:30, 30 minutes before the game started, and ended just after the game was over at approximately 19:15. During this period, the following types of events were logged for the Android app and cloudlet instance: video data transfers in terms of source, destination, time interval, length of data; network formation events for WiFi-Direct group creation or disposal, and; connection establishment/detachment between devices and cloudlets or WiFi-Direct GOs. Event data was stored locally for the cloudlets and devices, and also pushed from devices to cloudlets in short data transfers. When the experiment was over, we collected and merged all the logs for analysis.

3 https://goo.gl/maps/cUainSqtD962 Overview of user behaviour. Over the course of the experiment, the volunteers recorded and uploaded 165 videos to the edge cloud, and also performed a total of 660 video downloads. Apart from these successful operations, there were 39 transfer errors, corresponding to approximately 4% of total video transfers. Figure 7 shows a timeline of operations per device. The colors show, for any given instant, whether a device was connected directly to a cloudlet AP or to a WDG, or if they formed a WDG (acted as GO). For each device timeline, upload and download completions are respectively marked with arrows and dots. As shown, the behaviour observed from device to device can be quite heterogeneous in terms of connectivity and user operations. Some devices connected to a cloudlet AP and remained in that state for most if not all of the game (e.g., [START_REF] Liu | Secure sharing and searching for real-time video data in mobile cloud[END_REF][START_REF] Mollah | Secure data sharing and searching at the edge of cloud-assisted internet of things[END_REF][START_REF] Robb | HuaweiVoice: Agile Stadiums Bring Digital Content To Sports Fans[END_REF][START_REF] Rodrigues | Benchmarking Wireless Protocols for Feasibility in Supporting Crowdsourced Mobile Computing[END_REF], others roamed between different cloudlet APs [START_REF] Andreev | Cellular traffic offloading onto network-assisted device-to-device connections[END_REF][START_REF] Erman | Understanding the Super-sized Traffic of the Super Bowl[END_REF][START_REF] Helgason | A mobile peer-to-peer system for opportunistic content-centric networking[END_REF][START_REF] Koukoumidis | Pocket cloudlets[END_REF][START_REF] Lu | An Analysis and Comparison of CDN-P2P-hybrid Content Delivery System and Model[END_REF], two devices formed WDGs for most of the game (8 and 10), and, finally, a portion of devices was connected to a WDG for significant time [START_REF] Cerqueira | Towards a persistent publish/subscribe system for networks of mobile devices[END_REF][START_REF] Nordström | Haggle: Opportunistic mobile content sharing using search[END_REF][START_REF] Rodrigues | Towards a Middleware for Mobile Edge-cloud Applications[END_REF][START_REF] Satyanarayanan | The Case for VM-Based Cloudlets in Mobile Computing[END_REF]. Regarding video transfers, some devices were quite active in terms of uploads (10 and 18), downloads (7 and 16), or both (4 and 8), while others had little or no activity [START_REF] Liu | Secure sharing and searching for real-time video data in mobile cloud[END_REF][START_REF] Mollah | Secure data sharing and searching at the edge of cloud-assisted internet of things[END_REF][START_REF] Robb | HuaweiVoice: Agile Stadiums Bring Digital Content To Sports Fans[END_REF][START_REF] Rodrigues | Benchmarking Wireless Protocols for Feasibility in Supporting Crowdsourced Mobile Computing[END_REF].

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        6
Connectivity. Figure 8 depicts stacked graphs for the number of users over time in terms of connection type (8a) and serving cloudlet (Fig. 8b).

First, we can observe that the share of devices that formed WDGs (GO) or connected to them (Group) was roughly balanced with the number of devices that merely connected to cloudlet APs. Over time, 7.6 (49%) devices on average participated in WDGs, 2.5 as group owners (16%) and 5.1 (33%) connected to these groups, whilst 7.9 (51%) devices connected to a cloudlet AP only. The results are less balanced for the serving cloudlet, through direct connection or transitively through a GO: over time 9. 1.3 by C2, and 3.2 by C3. To explain this, a precise analysis would require accurate user location/mobility data (as mentioned earlier, we were constrained by GPS signal reception) but we attribute this to two facts we observed on-site:

(1) users typically installed and turned on the app at a working desk located very near C1, therefore likelier to keep the connection to it longer, and;

(2) as suggested by the numbers, there were in fact a higher concentration of users near C1, where most of the game fans concentrated.

Uploads and downloads. Figure 9 depicts video transfers in terms of active downloads (9a) and uploads (9b) over 1-minute intervals, as stacked graphs. Downloads are distinguished in terms of the following types of transfers: cloudletto-device (C2D), when involving devices that are not part of a WDG; cloudletto-group transfers (C2G), for downloads that originated in a WDG but could not be served by it; and device-to-device (D2D), for videos that were requested and served within a WDG. On average, 3.4 C2D (42%), 2.6 C2G (33%), and 2.0 (25%) D2D downloads were active per minute. The C2D share (42%) is slightly less than the share of devices that were not involved in groups over time (51%, as mentioned earlier), whilst the D2D/C2G ratio of 43% corresponds to the proportion of downloads issued and served within the same WDG. Regarding uploads, device-to-cloudlet (D2C) and group-to-cloudlet (G2C) are shown, along with the correlated video transfers in the mesh (using Algorithm 4 presented earlier). On average, there were 2.5 (1.1 D2C and 1.4 G2C) active uploads and 3.1 mesh transfers active per minute. Note that per each upload, there should be 2 corresponding mesh transfers (we use 3 cloudlets), hence close to 5.0 mesh transfers would be expectable instead. Upon log inspection, we verified that the mesh synchronization got stuck for cloudlet C1 early in the experiment due to a software glitch. Thus, videos originating at devices served by C2 and C3 were not replicated through the mesh onto C1, although cloudlets C2 to C3 functioned properly and were able to pull videos from C1 during the entire experiment. Looking into this issue further, Figure 10 shows a global plot for the number of distinct videos stored in all 3 cloudlets over time (on top), plus three other plots comparing the number of videos stored per each cloudlet (Ci) vs. the number of (also distinct) videos stored in the devices served by that cloudlet (Ai). The global plot clearly indicates that, at around 17:15, C1 started to lag behind C2 and C3. Inspecting the plot for C1, a surprising finding is that the number of videos in devices served by it (A1) did not stop growing, however. In fact, it converged very closely to the set of videos stored in C2 or C3. The behavior of C1 is not observed for C2 and C3 which synchronised over the mesh properly, apart from a temporary glitch in C2 between 17:00 and 17:30, and where the number of videos in served devices was actually much lower than those stored by the cloudlets (owing up to the lower number of users/download requests). The finding for C1 is explained by the combined effects of device churn and video caching: the loss of videos through faulty synchronization at the mesh tier was compensated by devices that eventually got under the scope of C1 and brought most of the missing videos with them. We did not anticipate (the technical glitch or) this possibility, hence C1 was not updated with those videos, but clearly the potential of opportunistic churndriven synchronization exists and should be seized upon. for a video was roughly 14.5 MB, and more than 75% were smaller than 25 MB. To put this in perspective, in spite of some larger videos (the largest one had 144 MB), even with low bandwidth, say 500 KB/s, a video transfer typically took less than 1 minute.

Video transfer analysis.

The transfer speeds are shown for uploads (green), downloads (blue) and mesh synchronization (red). For uploads, we distinguish between direct deviceto-cloudlet (D2C) transfers, and uploads mediated through a GO (D2Go2C), with median values of approximately 1 MB/s and 600 KB/s, respectively. The symmetric values for downloads, C2D and C2GO2D, are higher as expected (downlink speed is higher as usual): 2.6 and 1.1 MB/s. As for downloads made within a WDG, we distinguish transfers from GO to another group member (Go2D) and between non-GO members (D2D), with median values of 1.4 MB/s and 600 KB/s, respectively. D2D transfers are slower, as they require data to be routed through the GO and the inherent up-link bandwidth limitation (the values are similar to the D2Go2C case). TDLS links, disabled for stability reasons, should allow much higher values for D2D transfers (as we have achieved in [START_REF] Rodrigues | Benchmarking Wireless Protocols for Feasibility in Supporting Crowdsourced Mobile Computing[END_REF][START_REF] Silva | Using Edge-Clouds to Reduce Load on Traditional WiFi Infrastructure and Improve Quality of Experience[END_REF]). Finally, the median value for mesh transfers was 1.6 MB/s. WDG analysis. We now analyse the behavior of the two WDGs that were active for most of the experiment, those enabled by devices 8 and 10 in Figure 7. In comparison, the other 5 WDGs that were formed during the experiment all lasted less than 1 hour. Figure 12 depicts the behavior of the 2 groups in terms of member count (including the GO), the number of videos in the GO, the number distinct videos stored in all members, and the number of total videos stored by the group (including duplicates). The first group was clearly more active, with 4.46 members on average and a peak value of more than 300 videos, 122 of which were distinct (74% of all 165 videos in the system). Two other significant traits are that: (1) the GO videos, that are permanently available while the group lasts, grows monotonically over time and stores/caches more than half (52%) of these videos, and; (2) there is a high ratio of replication of videos (1.9), meaning that devices tended to download a high portion of the same videos. This results in resilience to churn: the group's video pool (the set of distinct videos) does not decrease significantly when a member departs, while there are much higher variations in total video count. The second group marks a contrast to the first one, given that it had far few members (1.9), a smaller video pool on average, and low levels of GO caching (27%) and replication (1.1).

Related work

CDNs are usually materialised by large datacenters spread throughout the globe, emerged with the objective of improving the distribution of content to endusers by providing high data availability, reduced latency and increased network bandwidth. The potential of hybrid CDN-P2P architectures is well acknowledged by large CDN providers, e.g., see [START_REF] Lu | An Analysis and Comparison of CDN-P2P-hybrid Content Delivery System and Model[END_REF]. Some architectures combine servers and P2P (Internet) links [START_REF] Ghareeb | P2PWeb: A Client/Server and P2P Hybrid Architecture for Content Delivery Over Internet[END_REF][START_REF] Wang | AMES-Cloud: A framework of adaptive mobile video streaming and efficient social video sharing in the clouds[END_REF], but do not directly account for proximity to end users. Cloudlets, on the other hand, are lightweight servers deployed at the edge of the network, e.g., as part of hybrid CDN-P2P architectures [START_REF] Yin | Design and deployment of a hybrid CDN-P2P system for live video streaming: experiences with LiveSky[END_REF], as relays to perform video processing before uploading data to the central cloud [START_REF] Simoens | Scalable crowd-sourcing of video from mobile devices[END_REF], or to deliver geo-based multi-player content and interaction [START_REF] Wang | ENORM: A framework for edge node resource management[END_REF]. Mobile devices themselves can be used effectively as CDN caches in the network, even without resorting to D2D links [START_REF] Koukoumidis | Pocket cloudlets[END_REF].

D2D communications enabled at the level of cellular networks is envisioned as the main enabler for traffic offloading/proximity-aware CDN [START_REF] Andreev | Cellular traffic offloading onto network-assisted device-to-device connections[END_REF]. While this promise is not fulfilled at scale, WiFi/Bluetooth-based communications are the prevalent means. For instance, Haggle [START_REF] Nordström | Haggle: Opportunistic mobile content sharing using search[END_REF] is an opportunistic content-sharing system that employs WiFi and Bluetooth links and store-and-forward techniques to cope with network disruption and churn, and Kwon et al. [START_REF] Kwon | Scalable video streaming relay for smart mobile devices in wireless networks[END_REF] make use of WiFi-Direct groups for improved video streaming by letting the GO act as relay/cache between the cellular infrastructure and other group members. There are other non-standard techniques that require "rooted" device extensions to work, e.g., Helgason et al. [START_REF] Helgason | A mobile peer-to-peer system for opportunistic content-centric networking[END_REF] present a middleware for mobile applications that disseminate contents opportunistically over WiFi ad-hoc one-hop links without further infrastructural support, and Microcast [START_REF] Keller | Microcast: Cooperative video streaming on smartphones[END_REF] uses D2D WiFi/Bluetooth communication in conjunction with 3G/4G to improve the performance of video streaming, but making use of overhearing techniques for WiFi.

The hybrid architecture of this paper combines cloudlets and D2D communication, and is naturally extensible to the consideration of a centralised cloud layer. In addition to the video dissemination scenario considered here (in sequence to [START_REF] Silva | Using Edge-Clouds to Reduce Load on Traditional WiFi Infrastructure and Improve Quality of Experience[END_REF], discussed earlier in the paper), another Hyrax project case-study concerns photo sharing for temporary networks formed at social gatherings, making use of the Thyme system [START_REF] Cerqueira | Towards a persistent publish/subscribe system for networks of mobile devices[END_REF]. Thyme is a time-aware publish-subscribe CDN service, in which devices are logically organised into geographical hash-tables for content discovery and retrieval. For these and other Hyrax applications and services, a general-purpose middleware [START_REF] Rodrigues | Towards a Middleware for Mobile Edge-cloud Applications[END_REF] is being developed, providing the abstraction of an overlay network formed from heterogeneous (WiFi, WiFi-Direct, Bluetooth) D2D links, and that is adaptive to intermittent communication and device churn.

Conclusions and future work

We presented an untethered hybrid edge-cloud to support video dissemination at sporting events, validated experimentally in the real world setting of a Portuguese league volleyball game. The edge-cloud was composed of mobile devices, possibly organised in WDGs, that produce and consume videos, and a mesh of three Raspberry Pi cloudlets that cache and disseminate the videos produced by the devices. The experiment showed that the edge cloud was sufficiently robust to provide videos to tens of users with low latencies. Moreover, the multiple caching levels-at devices, WiFi-Direct groups and cloudlets-made it resilient to device or cloudlet failures. In particular, we illustrated that an unexpected long-term fault by one the cloudlets could be compensated through the combined effects of caching and churn for opportunistic content sharing. The role of the WDGs was specially relevant in this overall picture. They significantly offloaded traffic from the mesh infrastructure, by involving 49% of devices on average and serving 43% of the downloads issued by devices in such groups. Moreover, as illustrated for the most active group in the experiment, caching not only provides resilience to churn (when devices leave the group) but in fact seize upon it (when devices enter) to accumulate videos over time in a group.

For future work we focus on several aspects. Some natural extensions can be considered to our hybrid architecture, such as the addition of a centralised cloud layer [START_REF] Silva | Using Edge-Clouds to Reduce Load on Traditional WiFi Infrastructure and Improve Quality of Experience[END_REF], and the use of 3G/4G networks in combination with WiFi and D2D communication. In the presence of a centralised cloud layer, a curation mechanism can be implemented such that administrative users filter the appropriate videos for dissemination and certify their provenance for security assurances (e.g., using digital signatures for videos). More generally, the paramount aspects of security and privacy, outside the scope of this paper, may be dealt with by several mechanisms in a mobile edge cloud setting at the level of devices and/or cloudlets, e.g., see [START_REF] Liu | Secure sharing and searching for real-time video data in mobile cloud[END_REF][START_REF] Mollah | Secure data sharing and searching at the edge of cloud-assisted internet of things[END_REF][START_REF] Tan | Chips: Content-based heuristics for improving photo privacy for smartphones[END_REF]. Another line of work concerns the simulation of our scenario, to help us understand the behavior of the network at scale over the parameter space, and calibrate experiments in more principled manner, for instance regarding the strategies for network formation, video caching and replication, patterns for user mobility and video sharing, and choice of communication technologies. These future developments may consider other scenarios in crowded venues (e.g., music halls, museums) or in communication-deprived environments (e.g., disaster settings, remote locations) [START_REF] Rodrigues | Towards a Middleware for Mobile Edge-cloud Applications[END_REF].

Fig. 1 :

 1 Fig. 1: Snapshot of the game S.C. Espinho vs Vitória S.C., our case study.

Fig. 2 :

 2 Fig. 2: The 2-tier network architecture.

Fig. 3 :

 3 Fig. 3: Cloudlet setup.

Fig. 4 :

 4 Fig. 4: Cloudlet synchronization algorithm.

  (a) Video browsing. (b) Video capture.

Fig. 5 :

 5 Fig. 5: Android app.

Fig. 7 :

 7 Fig. 7: Timeline of operations per device.

  8 devices were served by C1 on average,

Fig. 8 :

 8 Fig. 8: Connectivity over time.

Fig. 9 :

 9 Fig. 9: Video transfers over time.

Fig. 10 :

 10 Fig. 10: Video storage analysis.

Figure 11

 11 characterises video lengths (11a) and transfer speeds per category (11b), in terms of quartiles, minimum and maximum values. The median size

Fig. 11 :

 11 Fig. 11: Video transfers -size and speed.

Fig. 12 :

 12 Fig. 12: Analysis of two Wifi-Direct groups.

http://www.hyrax.dcc.fc.up.pt

https://www.open-mesh.org/projects/open-mesh/wiki

Acknowledgements

This work has been sponsored by projects HYRAX (CMUP-ERI/FIA/0048/2013), funded by FCT, and SMILES (NORTE-01-0145-FEDER-000020), funded by NORTE 2020, under PORTUGAL 2020, and through the ERDF fund. We wish to thank Nuno Vitó and Bernardo Viterbo from S. C. Espinho, José Gouveia and Quirino Gomes from C. M. Espinho, and Francisco Carvalho from Vitória S. C. for their precious support.


Raad Bin Tareaf
email: raad.bintareaf@hpi.uni-potsdam.de

Philipp Berger
email: philipp.berger@hpi.uni-potsdam.de

Patrick Hennig
email: patrick.hennig@hpi.uni-potsdam.de

Christoph Meinel
email: christoph.meinel@hpi.uni-potsdam.de

Malicious Behaviour Identification In Online Social Networks

Keywords: Online Social Networks, Twitter, Anomaly Detection, Authorship Authentication

This paper outlines work on the detection of anomalous behaviour in Online Social Networks (OSNs). We present various automated techniques for identifying a 'prodigious' segment within a tweet, and consider tweets which are unusual because of writing style, posting sequence, or engagement level. We evaluate the mechanism by running extensive experiments over large artificially constructed tweets corpus, crawled to include randomly interpolated and abnormal Tweets. In order to successfully identify anomalies in a tweet, we aggregate more than 21 features to characterize users' behavioural pattern. Using these features with each of our methods, we examine the effect of the total number of tweets on our ability to detect an anomaly, allowing segments of size 50 tweets 100 tweets and 200 tweets. We show indispensable improvements over a baseline in all circumstances for each method, and identify the method variant which performs persistently better than others.

Introduction

Online Social Networks (OSNs) present convenient platforms for users to participate, interact, and collaborate in online manner. While users' relish the openness and amenity of social media, various malicious unethical activities and actions can be performed by individuals or communities to manipulate thought process of OSN users' to fulfil their own agenda. Therefore, it is extremely critical to detect these unusual activities as accurately and quickly as possible to prevent potential attacks and disasters. Such malicious behaviour needs to be controlled and its consequences should be reduced.

Social media platforms acts as a medium for communication for getting an overview of trends and current situation in various domains and locations. For instance, [START_REF] Bin Tareaf | Identifying Audience Attributes: Predicting Age, Gender and Personality for Enhanced Article Writing[END_REF] proposed a system which helps bloggers creates an effective articles by identifying so-called non annotated audience attributes (age, gender and personality traits) for potential blogs posts, while [START_REF] Boutyline | The social structure of political echo chambers: Variation in ideological homophily in online networks[END_REF] introduced a system that is competent in predicting political ideology and homophily between online individuals by analyzing their twitter profiles contents. Among this potentiality, social media evolves into an interesting target for criminal [START_REF] Stringhini | Detecting spammers on social networks[END_REF]. As fake accounts can be easily recognized and reported [START_REF] Egele | Compa: Detecting compromised accounts on social networks[END_REF], the attackers tend to hack into real existing accounts and compromise profiles content. Thus, provides criminals wide range of contacts and connections to spread their tragedy, with a potentially high success rate of penetration, because those contacts have already trusted relationship with the compromised profile. In 2016, more than 600,000 Facebook profiles are compromised every day [START_REF] Andra | 10 alarming cyber security facts that threaten your data[END_REF] By taking over legitimate accounts, the attacker can easily exploit this trust relation to serve his own intentions.

Consequently, Attackers can disseminate their malicious messages or propagate fake information to a large users base. Nevertheless, detecting compromised accounts is much harder than detecting fake accounts. In comparison, a compromised account is genuine until it is successfully attacked. This yields two main benefits for attackers. First, they can misuse the existing trust between the profile owner and their contacts. Secondly, a compromised account confers normal behaviour, thus, it may not be blocked or deleted promptly by the operators.

Related Works

Social networking platforms have become a very attractive target for hackers and intruders. For instance, one could spam users with malicious messages and consequently spread harmful messages. Gianluca Stringhini [START_REF] Stringhini | Detecting spammers on social networks[END_REF] analysed the activities of spammers by proposing a new method called honey profiles, this act as a trap to detect and counteract at unauthorized use of information systems.

Another framework for authorship identification of online-messages was proposed by [START_REF] Zheng | A framework for authorship identification of online messages: Writing-style features and classification techniques[END_REF]. The framework was examined with online-newsgroup messages in English and Chinese language. In addition, a tool called COMPA [START_REF] Egele | Compa: Detecting compromised accounts on social networks[END_REF] uses a feature set of meta information about the single post such as time, language and location. However, the text itself was not analysed nor considered in their proposed model. [START_REF] Brocardo | Authorship verification for short messages using stylometry[END_REF] analysed message segments of 500 characters. They introduced a combination of supervised learning technique with n-gram analysis to verify an author of a specific text. Since posts in social networks are usually very short and often have a limited length of characters, [START_REF] Schwartz | Authorship attribution of micro-messages[END_REF] focused on authorship attribution of micro-messages, particularly on tweets. They introduced the concept of an authors unique signature, specifying the features that are unique for a certain user.

Our approach focuses on capturing malicious activities by extracting all user activities within Twitter profiles. Consequently, We developed machine learning algorithm to extract 21 unique feature to be able to detect malicious behaviours and reveal compromised accounts to their owners.

Implementation

Dataset Acquisition

We examined two existing datasets, the Followthehashtag1 dataset and the myPersonality2 . Nevertheless, none of them matched our specified preferences (100 tweet as a minimum per user). Eventually, we decided to gather our own dataset as an exemplary samples from Twitter platform.

Crawled Twitter Dataset : A new dataset [START_REF] Bin Tareaf | Tweets Dataset -Top 20 most followed users in Twitter social platform[END_REF] was gathered by crawling Twitters REST API using the Python Tweepy library 3 . The new dataset contains the tweets of the 20 most popular twitter users (with the most followers) 4 whereby re-tweets are neglected. Consequently, the dataset contains a mix of relatively structured tweets, written in a formal and informative style, and completely unstructured tweets written in a colloquial style.

In total, the dataset contains 52,542 tweets with an average number of 2627.1 tweets per user. The time difference between the first and the last crawled tweet is 1,287 days (about 3.5 years) on average; half a year for CNN Breaking News account and up to 7 years for Twitter official account. Consequently, the dataset contains user accounts with 0.13 tweets per day (YouTube) up to 1.13 tweets per day, while the rest accounts have in average 0.5 tweets per day. Considering these statistics, the crawled dataset comprises of a well-suited mix of diverse posting behaviours.

Features Selection

A) Text-specific features Since writing style is a broad field to analyse, [START_REF] Zheng | A framework for authorship identification of online messages: Writing-style features and classification techniques[END_REF] suggests to break it down in four types: lexical, syntactic, structural and content-specific feature styles. These styles depend for example on the gender or the educational background of the person [START_REF] Koppel | Automatically categorizing written texts by author gender[END_REF] [START_REF] De | Mining e-mail content for author identification forensics[END_REF]. Therefore, We applied the following features to analyse the writing style:

-Lexical character features: LCR features are extracted from users posts considering the: amount of characters, amount of ASCII characters, amount of ASCII upper-case characters, amount of ASCII lower-case characters, amount of digits, amount of white spaces and amount of special characters.

-Lexical word features: LWF features are extracted from users posts considering the: amount of words, amount of short words, average words length, average sentence length of characters, average sentence length of words and the amount of unique words.

-Syntactic features: are extracted by considering the usage of punctuations and the frequency of all used punctuations.

-Structural features: are extracted by analyzing the total number of lines and total number of sentences within a user posts. B) N-grams: For our approach, we selected two types of n-gram [START_REF] Brocardo | Authorship verification for short messages using stylometry[END_REF] features which are Word n-grams and Character n-grams.

C) Post-specific features On one hand, each user follows a specific pattern in posting behaviour [START_REF] Corney | Gender-preferential text mining of e-mail discourse[END_REF]. On the other hand, there is a reactional pattern to a user's posts by his/her followers [START_REF] Egele | Compa: Detecting compromised accounts on social networks[END_REF]. By analysing these two patterns, anomalies in posts can be recognized. For our approach we decided to analyse the amount of shares for posts, the amount of likes for posts as well as the time stamps for each of the post-specific features.

All extracted features are scaled using the Python sklearn.preprocessing package5 to obtain a Gaussian distribution with zero mean and unit variance. This standardization is necessary to prevent a learning algorithm's objective function from being dominated by some single features and, thus, make the estimator unable to learn from other features correctly.

Training and Prediction

Training algorithm We implemented an algorithm which is based on a legitimate assumption that the oldest 100 tweets are actually posted by the user. In most scenarios, this assumption holds since the probability that an account was compromised increases with the time. The longer a faked post exists, the more likely users will detect it manually, either because of the reactions of friends or by themselves while checking their profile. Moreover, an account with a little amount of tweets (100 or less) usually has a few audience. Therefore, such an account is less interesting to get compromised by attackers and the probability that one of these first tweets is a compromised is relatively low. An analysis of different initial training set sizes is presented in the evaluation section.

The proposed solution starts by increasing the number of training samples incrementally utilizing interactive machine learning approach. In the beginning, the classifier is trained with the initial and oldest 100 posts of a user timeline as positive samples. The generated model is then used to predict classes for the remaining posts which are sorted by publishing time starting with the oldest one. The algorithm breaks down the predictions into cohesive batches of posts with the same predicted class. If the first batch is predicted as legitimate posts, the existing model is trained with these posts as positive samples. If the batch is predicted as malicious, posts will be added to a list of suspicious posts and the model is trained with the next batch as positive samples. In both cases, all samples in the list of suspicious posts are classified again with the updated model. If the class of a post has changed, then it will be removed from the negative list. Consequently, the next iteration starts with classifying the remaining posts whose batches are not examined before. This process is repeated until there are no remaining posts. The algorithm then returns the full list of the suspicious tweets.

Figure 1 Model Refinement Given the detected suspicious posts, the user who runs the algorithm can select those ones which are actually written by him/her. The marked tweets are used as labelled samples for an additional training process turning the actual classification errors into a chance to refine the generated model on fly. The existing classifier is fitted with the samples using a higher weight than in the initial training. The list of suspicious posts is then updated using the improved model.

Classifier Selection

The goal of this implementation is to procreate an architecture which does not depend heavily on a specific learning algorithm. This makes it easy to switch classifier type and compare the performance of differ-ent algorithms. In this work, we considered four classification algorithms whose evaluation results are compared in Section 4.2 .

Evaluation

Evaluation method

In online social networks domain, there is no superior evaluation criteria available to follow within the task of malicious behaviour identification. Therefore, we followed the concept of evaluation that is proposed by [START_REF] Guthrie | Unsupervised anomaly detection[END_REF] [START_REF] Guthrie | An unsupervised approach for the detection of outliers in corpora[END_REF]. The crawled tweets are grouped by the author and sorted by publishing time starting with the oldest one. Afterwards, the data is partitioned into a training set and a validation set as described below. Since our training approach is iterative, the boundary between trained and tested status are updated in each iteration. The first 100 tweets of a chosen author are used as positive sample for the training set. Additionally, a randomly sampled subset (500 tweets) of the tweets of ten other users is used as negative sample. To evaluate the performance of our developed training algorithm, the 400 next tweets of the chosen author are added. Validation set: As introduced above, the 400 next tweets of the chosen user are added and they are acting as part of the training set but likewise are used for testing in the sense of determining if our developed training algorithm correctly recognizes these tweets during the incremental training. Moreover, a randomly sampled subset of the tweets for the remaining nine other users (disjoint with tweets used for the training set) is inserted into the validation set whereby the temporal order of all tweets is maintained.

Classifier performance

In order to evaluate the performance of the proposed model, we used the accuracy, precision, recall metrics and we plotted the final f-score harmony measurement for each classifier on each feature category, as shown in table 1. When a bigger initial training set is given as shown in figure 2, the recall improves significantly whereas the precision slightly decreases. Considering that the precision is more important for our stated problem and that the possibility of containing already compromised tweets raises when using a bigger initial training set size (which are then considered to be a user's posts by the algorithm), a size above 100 tweets is not well-suited as initial training set size.

Conclusion and Future Work

We presented our work of automating the process of identifying malicious behaviour in online social networks. Specifically, Twitter social platform. We extracted 21 unique features from user profiles and trained our model accordingly to characterize users' behavioural pattern and specify compromised accounts. Given a Twitter account, the proposed system can detect suspicious posts based on anomalies in user's profile and state whether the account was compromised before or not. Our novel combined features (text-specific features, n-grams feature and post-specific features) confirms that utilizing the power of machine learning classifiers can accurately detect deviations in user's posts and alert when profile behaviour is violated.

With our proposed approach, we improved the performance for specific classifiers and feature subsets by 9% (One-Class SVM) to 13% (Perceptron) while slightly lost some precision. The strength of our feature set combination is that post-specific (meta) features are considered in the experiments. In future work, our results could be improved significantly if more post-specific features, such as the geolocation are available in the dataset. The Supplementary material associated with this research is publicly available for interested researchers.

  demonstrates the training algorithm for an exemplary user's timeline. In each iteration, a batch of tweets is added to the positive training samples and both classifier and predictions are updated for the remaining tweets. As it demonstrated in the figure, the new batch of tweets is framed by a solid line while the dotted box contains all positive training samples. Each column shows the state at the of the corresponding iteration after selecting the new batch of training samples which depends on the updated predictions of the previous iteration.

Fig. 1 .

 1 Fig. 1. First three iterations of the training algorithm conducted on exemplary tweets. T and F refer to the True or False predicted classes.

  Training set: Since two out of the four classifiers: Perceptron, Decision Tree, One-Class SVM and Isolation Forest are binary classification techniques, the initial training set consists of two separate sets: positive and negative samples. Being one-class classification techniques, the SVM and the IsolationForest classifier take only the positive samples as input and neglect the negative examples.

a 1 :

 1 Text-specific, b 2: N-grams, c 3: Post-specific, d (1&2): combination of Textspecific and N-grams, e (1&3): combination of Text-specific and Post-specific,

Fig. 2 .

 2 Fig. 2. Comparison of the precision and recall for different initial training set size using Decision Tree classifier.

Table 1 .

 1 Precision and F-score values for various classifiers options over different feature subsets.

		Precision
	Classifier	(1) a (2) b (3) c (1&2) d (1&3) e All Features F-measure
	Perceptron	0.78 0.82 0.24	0.81	0.77	0.83	0.70
	Decision Tree	0.65 0.79 0.56	0.75	0.65	0.73	0.76
	One-Class SVM 0.74 0.72 0.50	0.80	0.73	0.85	0.61
	Isolation Forest 0.54 0.51 0.52	0.53	0.54	0.53	0.72

http://followthehashtag.com/datasets/

http://mypersonality.org/wiki/doku.php?id=download_databases

http://www.tweepy.org/

http://twittercounter.com/pages/100

http://scikit-learn.org/stable/modules/preprocessing.html

Acknowledgement

We would also like to show our gratitude to our master students (Henriette Dinger, Dominic Sauer , Soeren Oldag and Sebastian Kliem -Hasso Plattner Institute) who provided insight and expertise that greatly assisted the research during our research seminar.