Denis Conan

Léon Lim

Chantal Taconet

Sophie Chabridon

Claire Lecocq Samovar

A multiscale approach for a distributed event-based Internet of Things

Keywords: Internet of Things, Multiscale distributed system, Distributed event-based system, Content-based routing, Localised scalability, Scoping, Multiscoping

The Internet of Things paradigm calls for exchanging data among dynamic and heterogeneous producer and consumer entities at unprecedented scales. The approach used in this paper to address IoT heterogeneity and scalability is through the modelling of multiple heterogeneous scales along dimensions of the application domain. Then, the concepts of scale and dimension of multiscalability are mapped to the concepts of scope and graph of scopes of distributed event-based systems, which have long been recognised as enabling scalable and flexible communication in a space-, time-and synchronisation-decoupled way. This multiscale approach for a distributed event-based Internet of Things enables the modelling of the decentralisation with human-centred edge computing solutions placing control at the edges of the IoT by leveraging localised scalability. Our implementation and experimentations with the MUDEBS framework show that multiscoping helps to drastically diminish the number of exchanged messages for both subscriptions and notifications.

I. INTRODUCTION

The Internet of Things (IoT) paradigm calls for exchanging data among dynamic and heterogeneous producer and consumer entities at unprecedented scales [START_REF] Atzori | The Internet of Things: A survey[END_REF], [START_REF] Bellavista | A Survey of Context Data Distribution for Mobile Ubiquitous Systems[END_REF]. The publish/subscribe communication model [START_REF] Eugster | The Many Faces of Publish/Subscribe[END_REF], supported by Distributed Event-Based Systems (DEBS) [START_REF] Hinze | Event-Based Applications and Enabling Technologies[END_REF], [START_REF] Oki | The information Bus: An Architecture for Extensible Distributed Systems[END_REF], has long been recognised as enabling scalable and flexible communication in highly distributed systems in a space-, timeand synchronisation-decoupled way. However, the dynamicity and heterogeneity characterising the IoT requires additional mechanisms. This paper addresses IoT heterogeneity and scalability through the modelling of multiple heterogeneous scales along dimensions of the application domain. This multiscale approach also enables full decentralisation with human-centred edge computing solutions [START_REF] Garcia Lopez | Edgecentric Computing: Vision and Challenges[END_REF] placing control at the edges of the IoT leveraging localised scalability [START_REF] Satyanarayanan | Pervasive Computing: Vision and Challenges[END_REF]. We discuss in the following our design choices for a content-based DEBS solution deployed on an overlay of brokers.

In a DEBS, a producer publishes notifications, possibly following an advertisement message describing a set of notifications it is willing to publish, whereas a consumer subscribes to a set of messages it is interested in. Although producers initiate the communication, they do not know any consumer. If a notification matches a subscription, it is delivered to the consumer. Considering the dynamicity and diversity of producers and consumers, IoT systems are open and it is questionable to rely on solutions based on subject-based filtering (also called topic-based filtering) in which subscribers specify explicitly the topic of interest (via a few words with meta-characters that match for instance several characters or words) in their subscriptions [START_REF] Castro | Scribe: a large-scale and decentralized application-level multicast infrastructure[END_REF], [START_REF] Oki | The information Bus: An Architecture for Extensible Distributed Systems[END_REF]. Instead, we adopt the full expressivity of content-based filters -i.e. they are constraints expressed on the whole content of notifications [START_REF] Carzaniga | Design and Evaluation of a Wide-area Event Notification Service[END_REF], [START_REF] Fidler | The PADRES Distributed Publish/Subscribe System[END_REF], [START_REF] Mühl | Generic Constraints for Content-Based Publish/Subscribe[END_REF]. In addition, in order to stay as open as possible, we prefer using semistructured data models à la XML [START_REF] Altınel | Efficient Filtering of XML Documents for Selective Dissemination of Information[END_REF], [START_REF] Chan | Efficient filtering of XML documents with XPath expressions[END_REF], [START_REF] Hou | Predicate-based Filtering of XPath Expressions[END_REF] rather than structured data models that organise notifications as records of pairs (attribute name,value). The main reason is to interoperate with approaches such as sensors as a service and with information processing approaches such as reasoning with ontologies where data may be structured with OWL 1 (e.g. SSN 2 ).

DEBS solutions are originally typically implemented as overlay networks of brokers [START_REF] Oki | The information Bus: An Architecture for Extensible Distributed Systems[END_REF]. The access broker of the consumer is responsible for installing the subscription filter on brokers of the overlay network so that notifications that match the subscription are routed towards the consumer. Next, broker-less epidemic solutions have been used to disseminate information with some filtering for decreasing the probability that they receive information of no interest [START_REF] Eugster | Epidemic information dissemination in distributed systems[END_REF]. The main issue with this approach is that, even when a peer knows that its neighbours are not interested in a given notification, it is difficult to state whether a given neighbour is critical to reach a consumer. To the best of our knowledge, filtering in brokerless solutions is topic-based (e.g. [START_REF] Esposito | A Publish/Subscribe Protocol for Event-Driven Communications in the Internet of Things[END_REF]).

More recently, DEBS solutions built over peer-to-peer (P2P) overlay networks have been proposed. As highlighted by [START_REF] Kermarrec | XL Peer-to-Peer Pub/Sub Systems[END_REF], P2P overlay infrastructures represent a promising infrastructure to implement large-scale content-based DEBS since they are characterised by self-organisation and are highly flexible with respect to communication topology changes. Basically, P2P-based DEBS rely on the assumption that peers may act both as clients and servers, solving intrinsically the scalability requirement, as the number of potential servers increases linearly with the size of the system. However, to the best of our knowledge, existing P2P-based DEBS solutions assume either subject-based filtering or content-based filtering with structured data models. In addition, in the context of the IoT with edge computing, hosts do not necessarily have the same capability and should not play the same role: for instance, some devices cannot communicate with each other due to NAT. Finally, by considering the P2P overlay infrastructure, the principle of locality may be violated since data are routed between peers regardless of their locality. For all of these reasons, we focus on DEBS solutions based on overlay networks of brokers and with a semi-structured data model.

DEBS for broad IoT face unprecedented scales in terms of the volume of exchanged data, number of participants and communication distance. As many brokers may be involved, a high quantity of messages may be exchanged when installing subscription filters and most importantly when routing numerous events from producers to consumers. In this work, we take benefit from the inherently heterogeneous nature of broad IoT systems to control and limit the amount of exchanged data. For example, when a consumer declares an interest in the transportation information concerning members of the group of UK supporters going to athletic competitions in Stade de France in the north of Paris, the brokers may deduce that some parts of the overlay network are not concerned. In other words, some sources of heterogeneity (e.g. geographical heterogeneity, group membership heterogeneity) may delimit visibility scopes [START_REF] Fiege | Publish-subscribe grows up: Support for management, visibility control, and heterogeneity[END_REF] for data distribution, with notifications being visible only in certain scopes. We therefore combine the concept of multiscale distributed systems [START_REF] Rottenberg | MuSCa: A Multiscale Characterization Framework for Complex Distributed Systems[END_REF] with visibility scopes to bring into play the concept of multiscoping in a distributed event-based IoT, and we extend the requirements of distributed routing accordingly.

The remaining sections of this paper are structured as follows. Section II describes the multiscale approach we propose, illustrated on a Smart city scenario. The corresponding multiscale characterisation (viewpoints, dimensions, and scales) is defined, the graph of scopes are then derived with the associated visibility filters. Section III describes the concept of multiscoping allowing to specify scopes and visibility filters along multiple dimensions. Section IV summarises the principles of distributed routing with multiscoping that we implemented in our open source MUDEBS framework. Section V puts multiscoping in action for purposes of experimenting its impact on message traffic. Section VI then discusses related works focusing on scoping approaches enforced by an overlay of brokers. Section VII concludes the paper and gives some further research directions.

II. MULTISCALE APPROACH

In order to master the complexity of routing and filtering notifications in the IoT, our approach builds on the concept of multiscale distributed systems [START_REF] Rottenberg | MuSCa: A Multiscale Characterization Framework for Complex Distributed Systems[END_REF] and implements it using multiscoping to control notification dissemination in a DEBS.

The word "multiscale" qualifies extremely diverse systems [START_REF] Blair | Emergent Middleware: Tackling the Interoperability Problem[END_REF], [START_REF] Franklin | Design Considerations for High Fan-in Systems: The HiFi Approach[END_REF], [START_REF] Kessis | DASIMA: A Flexible Management Middleware in Multi-Scale Contexts[END_REF], [START_REF] Rottenberg | MuSCa: A Multiscale Characterization Framework for Complex Distributed Systems[END_REF]. Following [START_REF] Rottenberg | MuSCa: A Multiscale Characterization Framework for Complex Distributed Systems[END_REF], we consider the heterogeneity aspect according to several viewpoints and for each viewpoint several dimensions. For instance, in the geographical viewpoint, one may consider the administrative area or the distance dimensions; in the user viewpoint, one may consider the membership dimension to gather users into groups. Thereupon, a distributed system is qualified as being multiscale when the projection of its entities are associated with different scales in at least one dimension. We match the system concept of scale to the DEBS concept of scope. Scopes are used for structuring publish/subscribe systems by putting the concept of visibility of notifications forward. Notification visibility limits the set of consumers that may get access to this notification. We take the definition presented in [START_REF] Fiege | Publish-subscribe grows up: Support for management, visibility control, and heterogeneity[END_REF]: "A scope is an abstraction that bundles a set of clients (producers and consumers) in that the visibility of notifications published by a producer is confined to the consumers belonging to the same scope as the producer; a scope can recursively be a member of other scopes".

Thereafter, we abstract the customisability of DEBS with multiscoping -i.e. filtering is impacted by the visibility of notifications that are analysed according to several dimensions of scopes. A client advertises or subscribes providing a filter that is tagged with a set of scopes, with at most one scope per dimension. A notification is visible to a client if it is visible in all the dimensions (cf. Section III).

In Section II-A, we motivate the approach with an illustrative scenario. In Section II-B, we detail the multiscale characterisation obtained for this scenario. Then, we present in Sections II-C and II-D the benefits of this characterisation to manage the graph of scopes and to control the routing of events.

A. Smart city illustrative scenario

In preparation of the possible Olympic games in Paris in a near future, the city of Paris and the region Île-de-France are setting up smart services for the million of users of the public transportation. The services are able to provide customised applications to each of its users based on privacy requirements, location, group membership, and public transportation events (incidents, opportunities, etc.).

The system should provide information sharing functionalities for groups of users. For instance, supporters of the United Kingdom team may wish to meet at Stade de France for the athletics competitions. On the way to Stade de France, the service proposes to share information such as the current location of each member of a group, their current means of transport (e.g., bus line, taxis, subway car, suburban trains), and forecast arrival time. The group may be joined on-demand and at any time.

The system should control the dissemination of notifications crossing administrative areas according to system performance measurements. In particular, if the monitoring system detects a sudden deterioration of latencies due to a burst of traffic in some parts of the overlay network of brokers, the system should be able to isolate the brokers of some scopes to limit the quantity of notifications that can span the entire network. This (visibility) filtering can take into account the execution context at border crossing brokers and classifying notifications based on additional information such as priority or provenance.

The system of public cars proposes a service to indicate all the parking places located at a walking distance from a user, but this information is of no interest out of a given quarter. For this purpose the system limits the broadcast of these events to the concerned quarters.

B. Multiscale characterisation

In order to obtain the relevant scopes for this scenario, we characterise the multiscale nature of the IoT system in construction using the MuSCa 3 software framework [START_REF] Rottenberg | MuSCa: A Multiscale Characterization Framework for Complex Distributed Systems[END_REF], which follows a model-driven engineering approach [START_REF] Schmidt | Guest editor's introduction: Model-driven engineering[END_REF]. The multiscale concepts, mainly viewpoints, dimensions and scales are defined in a meta-model. A specific editor guides the system designer to produce a multiscale characterisation and leads to a system-specific multiscale vocabulary -i.e. a model.

The left part of Figure 1 outlines the result of the multiscale characterisation for the illustrative scenario. The multiscale framework proposes pre-defined commonly-used viewpoints and dimensions and allows system designers to define new ones. We select the pre-existing user and geography viewpoints, and we add the public transportation viewpoint. Then, for each viewpoint, we choose the following dimensions of interest to characterise the system entities. For the geography viewpoint, we select the geographical area dimension, with the region, department, city, quarter, street, building scales. For the public transportation viewpoint, we define the transport organisation dimension that shows the organisation of the public transports into network companies organised into intercity, suburban, area, city and dedicated destination scales. The city scale of the transport organisation dimension exemplifies a situation in which a node can have several "parents", then leading to hierarchies of the form of trees, but also forests. Finally, for the user viewpoint, we design the membership dimension, with its hierarchical group scales.

C. From the multiscale characterisation to the graph of scopes

In its centre, Figure 1 shows graphs of scopes for the chosen dimensions. The scopes are instances of the scales defined in the model. For instance, the Versailles scope is an instance of the City scale (model level) for the geographical area dimension. For each dimension, we translate the hierarchy of scale instances into a hierarchy of scopes: Each scope has superscopes (parent scopes) and subscopes (children scopes).

The right part of Figure 1 presents the distributed architecture of an overlay network of brokers settled by an administrator for a given infrastructure deployment. In each dimension, a broker "belongs" to zero, one or several scope areas (cf. Sections IV and V for the construction of the scope areas with the JoinScope action). For instance, in dimension d 2 , the Roissy area scope is managed by the brokers B 10 , B 11 , and B 13 . These scope areas are either built statically at deployment time or dynamically on demand when a client wants to produce or consume notifications in a scope that is 3 https://fusionforge.int-evry.fr/www/musca/ not already known by its access broker. Let us illustrate the dynamic extension of a scope area. When initially deployed, and since there is no client, the brokers are not aware of the groups of the membership dimension. And this is so even if the graph of scopes is fixed (i.e., the decomposition into subgroups is stable). Then, the overlay network of brokers managing the uk scope evolves: when a member of the group moves or connects to a broker that does not belong to the uk scope, the given broker joins the scope and the JoinScope action may lead to other brokers joining the scope to extend the scope area of the uk scope.

D. From scopes to filters

The scopes are used to limit the dissemination of notifications inside one or a restricted number of scope areas. This limitation is performed through the means of visibility filters associated with the edges of the graphs of scopes. Each edge of the graphs of scopes is associated with a content-based visibility filter to filter out outgoing notifications from the subscope to the superscope, plus another visibility filter for filtering out the incoming notifications from the superscope to the subscope. These filters are installed at border crossing brokers, precisely at those knowing both of the involved scopes. The visibility filters may be installed by 1) the administrator of the infrastructure for all the system services, or 2) system services from the point of view of the producers.

Firstly, visibility filters may be installed by system administrators. For instance, the administrator may install visibility filters at brokers B 9 and B 13 to control the traffic burst due to too numerous events produced during competitions at Stade de France and confine their dissemination to the Seine et marne scope. The filter may state by whatever means which ones come from official sources of information (or using many more resources, which notifications are potential duplicates), and filter out unofficial (and duplicate) notifications before forwarding them to the brokers of the Ile de france scope.

Secondly, visibility filters may be installed by system services. For instance, the group communication service can provide an option for producers to indicate whether their notifications should be kept in the scope of their production only (that information is included in every notification). The service can implement a content-based visibility filter that filters out outgoing notifications when the content of the notification indicates that the notification is declared as "producer-scope only". Finally, the service associates the visibility filter with the subscope-superscope relation of edges of the graph of scopes of the membership dimension so that they are installed at the border crossing brokers when the client joins a group. Clearly, these visibility filters target only scalability. They can be complemented with privacy management as proposed by MUDEBS with attribute-based access control [START_REF] Lim | Enhancing Context Data Distribution for the Internet of Things using QoC-awareness and Attribute-based Access Control[END_REF].

In addition, it is noticeable that if the data model of some of the notifications includes the production scope, clients can use this information in advertisement and subscription filters for that kind of notifications. For instance, assume that the notifications that serve to the announcement of newly freed parking places contain the scope of the producer in the geographical area dimension. Then, clients searching for parking places in their vicinity can specify in their subscription filter that the scope of the producer must match their quarter.

III. DEBS WITH MULTIPLE GRAPHS OF SCOPES

In this section, we give an overview of the underlying concepts of multiscoping that organises multiple graphs of scopes in MUDEBS 4 [START_REF] Lim | Distributed Event-Based System with Multiscoping for Multiscalability[END_REF], [START_REF]Poster: Concept of Multiscoping for Distributed Event-based Systems[END_REF].

A. Graph of scopes of a dimension

We complement the API of regular DEBS with the management of scopes. Before advertising or subscribing, system administrators "partition" the system into scopes by tagging brokers. This is done through the new JoinScope action. When clients submit an advertisement or a subscription, they can specify the scopes, at most one per dimension. Thus, their notifications are forwarded only in these scopes: This is the role of distributed routing to limit the dissemination (cf. Section IV).

As depicted in Figure 1, the edges of the graphs of scopes, one graph per dimension, are the scales (translated into scopes in a DEBS) plus the clients -i.e. a client advertising or subscribing "in" a scope is linked to the scope. The vertices define the partial order relationship "is subscope of" from 4 https://fusionforge.int-evry.fr/www/mudebs/index.html children scopes to parent scopes (noted ⊳, with its transitive closure * ⊳), and the inverse relation "is superscope of" (noted ⊲, with its transitive closure * ⊲). As shown in Figure 1, for the sake of convenience, we introduce the two specific scopes ⊥ (bottom) and ⊤ (top) such that the graph of scopes of a dimension contains at least ⊥ and ⊤, and such that ⊥ is a subscope of any other scope of the graph and ⊤ is a superscope of any other scope of the graph. By construction, the sets of scopes of different dimensions do not intersect, except for ⊥ and ⊤.

Edge directions in the graph indicate scope membership but notifications can travel in both directions. However, before "going through" a scope boundary, a notification must match a visibility filter established between the two scopes. Like forwarding filters 5 , visibility filters are content-based. The act of applying a visibility filter is called visibility matching. This way, virtually speaking, notifications are "passed along" from scope to scope by matching visibility filters.

The following rules determine the set of eligible direct subscopes and superscopes to which a notification is visible. Firstly, when published, a notification is made visible to the scopes the producer belongs to. This rule is applied recursively to make outgoing notifications visible to all further superscopes. Secondly, when an incoming notification is visible within a scope, it is visible to all its children. This rule is applied recursively to make notifications visible to further children. Consequently, outgoing notifications are visible to all the superscopes and to all the sibling scopes. A path of scopes that connects producer X to consumer Y is called a visibility path and is decomposed into two, possibly empty, parts: an upward part and a downward part such that

X * ⊳ K ∧ K * ⊲ Y .
For instance, as depicted in the graph of scopes of the public transportation dimension, notification n published in the Phébus Versailles scope is visible to the consumers in the Roissy area scope (because ph * ⊳ im ∧ im * ⊲ ro) but is not visible to the consumers in the SNCF-TGV scope (because im * ⊲ st ).

B. Visibility in several dimensions

In order to structure the overlay of network brokers according to several dimensions, we consider more than one graph of scopes. So, when submitting an advertisement or a subscription, a client provides a set of scopes, at most one per dimension. More precisely, Φ f is a set of scope paths, each scope path containing initially only one scope. When publishing, a producer indicates the identity of the advertisement filter f and the notification is tagged with Φ f . Therefore, each filter f is a triple (id f , r f , Φ f ), where id f is the identifier of the filter (noted f in brief), r f is the forwarding filter function of f and Φ f is a set of scope paths associated to f (one path per dimension).

We now denote X Φ X,f n Φ Y,f ′ Y the visibility of notification n produced by producer X and matching the forwarding filter of advertisement filter f to consumer Y that subscribes to subscription filter f ′ . Since it is not reasonable to let designers specify a scope for every dimension of the multiscale characterisation, we use the specific scope ⊥ in advertisements to indicate that ⊥ should be used for every dimension not explicitly stated in the advertisement. In other words, the producer is imposing no constraint on the routing of the notification for that dimension. Similarly, we use the specific scope ⊤ in subscriptions to indicate that ⊤ should be used for every dimension not explicitly stated in the subscription. In other words, the consumer wants to be notified regardless the scope of the notification for that dimension. Therefore, notification n published by client X through advertisement filter f is visible to client Y through subscription filter f ′ if and only if n is visible from X to Y in all the dimensions appearing in

Φ f ∪ Φ f ′ \ {(⊥), (⊤)}, with X being replaced by ⊥ when (s) / ∈ Φ f ∧(⊥) ∈ Φ f , and with Y being replaced by ⊤ when (s) / ∈ Φ f ′ ∧(⊤) ∈ Φ f ′ .
In conclusion, a distributed event-based system with multiscoping exhibits only traces satisfying the following requirements: (safety) (1) A client receives only notifications it is currently subscribed to; (2) A client receives only notifications that have been previously published by other clients and from which they are visible; (3) If the filter of the publication call does not belong to the active advertisements of the publishing client or if the notification does not match the filter specified in the publication call, the notification should not be delivered to any client; (4) A client receives a notification at most once; and (liveness) (5) A client eventually receives every notification that is visible to it and that matches some forwarding filters of its subscriptions.

In the next section, we complement the requirements with the distributed routing of notifications from producers to consumers.

IV. DISTRIBUTED ROUTING WITH MULTISCOPING

For the sake of simplicity, MUDEBS implements the simple routing approach with advertisements. Brokers broadcast the subscriptions in the overlay network of brokers and keep local the advertisements of their local clients. Techniques such as covering-based routing [START_REF] Carzaniga | Design and Evaluation of a Wide-area Event Notification Service[END_REF] could also be added to MUDEBS. We now describe how the flooding of subscriptions and the routing of notifications are constrained by scopes.

At first, administrators partition the system into scopes by tagging brokers through the JoinScope actions. More precisely, the role of administrators is to invoke JoinScope actions at specified brokers to project each scope graph onto the network of brokers in order to delimit scope "areas" and so that the membership relation superscope and subscope between scopes are preserved. Afterwards, a client can request for the membership to some scopes that its access broker is not aware of; the access broker then calls the corresponding JoinScope action. When the JoinScope action is called at broker B with the argument s ⊳ t, B updates its knowledge of the graph of scopes and sends a joinscope message to the neighbouring brokers that know t but do not know s so that (1) every future notification n tagged with scope s is forwarded to brokers in scope t if n matches the visibility filter of the relationship s ⊳ t, and (2) the reception of a notification n tagged with scope t is forwarded to B and then to the brokers of the scope "area" of scope s if n matches the visibility filter of the relationship t ⊲ s.

Visibility matching is a test that precedes any subscription or advertisement matching. Before forwarding a notification to a given destination D -i.e. a neighbouring broker or a local client-the receiving broker B verifies whether a visibility path associated with that notification can be built in the direction of D. The verification must be done not only according to the point of view of the producer for satisfying the constraints of the producer, but also according to the point of view of the consumer for satisfying the constraints of the consumer. Let Φ n be the set of scope paths associated with the notification, and Φ s be the set of scope paths associated with the subscription. From the point of view of the producer, a visibility path should exist for each dimension d in the set of dimensions associated with Φ n . Similarly, from the point of view of the consumer, a visibility path should exist for each dimension d in the set of dimensions associated with Φ s .

In a dimension, the routing of a notification follows a visibility path that is computed as the concatenation of the scope path of the notification and the scope path of the subscription as follows. At broker B, a scope path pp = (X, s 1 , s 2 , . . . , s h , . . . , s i , . . . , s j ) d in Φ n \ {(⊥), (⊤)} can be used to construct a visibility path vp = (X, s 1 , s 2 , . . . , s i , . . . , s j , . . . , s l-1 , s l , Y ) from X to Y if there exists a scope path sp = (Y, s l , s l-1 , . . . , s k , . . . , s j , . . . , s i ) d in Φ s \ {(⊥), (⊤)} such that s j+1 is an eligible next-hop scope of s j . In other words, there exists a suffix of pp that is a prefix of the reverse path 6 of sp such that the rule "eligible next-hop scope" can be applied. Figure 2 depicts the three allowed configurations a, b, and c, and the unallowed configurations d and e. pp is surrounded by a dashed line and sp is surrounded by a continuous line. In configurations a and b, (s i ...s j ) is in the upward part of vp and s j+1 is an eligible next-hop scope of s j . In the configurations c and d, (s i ...s j ) is in the downward part of vp and s j+1 is an eligible next-hop scope of s j . In the configurations d and e, (s i ...s j ) is in the downward part of vp, but s j+1 is not an eligible next-hop scope of s j . Therefore, the construction of vp with pp and sp in configurations a, b, and c is allowed, but is not allowed in configurations d, and e.

V. DEBS WITH MULTISCOPING IN ACTION

The objective of scoping DEBS with one or multiple graphs of scopes is to limit the installation of subscription filters as well as the dissemination of notifications. In this section, we evaluate the impact of multiscoping on the overall message traffic with different topologies of overlay networks of brokers. The comparison is with "no scoping" and monoscoping -i.e. scoping with one graph of scopes.

The overall message traffic depends upon the way the projection of the graphs of scopes onto the overlay network of brokers is performed. Hence, we start with some rules for the projection of the graphs of scopes onto the graph of brokers before presenting the experiments.

A. Projection of the graphs of scopes onto the graph of brokers

The projection is specific to application domains, but we can provide indications of how it can be done. Administrators partition the system into scope areas by tagging brokers with the JoinScope action. Of course, when misused, this latter functionality may degrade the overall performance of the 6 sp is reversed because it has been built during the broadcasting of the subscription starting from the access broker Θ of the consumer, thus Θ being the first element of sp.

system. We propose the following rules of thumb for building the scope areas. Let G d = (V d , E d ) be a graph of scopes:

• Rule 1 : |E d | JoinScope actions are necessary.

• Rule 2 : The calls JoinScope(t ⊳ ⊤) are the first calls to perform. The choice of the brokers for these calls may have a great impact on performance. • Rule 3 : Consider the "root" t such that a call Join-Scope(t ⊳ ⊤) has already been executed at broker B m . Assume that there is a client C with a scope path such that

X = k 1 ⊳ k 2 . . . k i ⊳ k i+1 . . . k n-1 ⊳ k n = t,
and such that there exists a path of network links

(θ(X) = B 1 , B 2 , . . . B j , . . . B m ). Before calling JoinScope(k i ⊳ k i+1 ) at broker B j , a call JoinScope(k i+1 ⊳ k i+2
) at broker B j ′ with 1 j j ′ m should be performed. Rule 1 stems from the fact that a graph of scopes is projected onto the network of brokers by adding edges one after the other. Rule 2 is specified in order to consider the top-down construction so that the edges at the top level are built first. The use of Rule 3 in conjunction with Rule 2 preserves the superscope and subscope relationships between scopes.

B. Overlay topologies of brokers and graphs of scopes

We use the GT-ITM Tool [START_REF] Tool | Modeling Topology of Large Internetworks[END_REF] to generate three overlay topologies Net 16 , Net 52 and Net 100 composed of 16, 52, and 100 nodes, respectively. Figure 3 depicts for instance the topology used for 52 brokers. Each overlay topology has one transit domain built upon x = 4 nodes that form a ring. There are on average y = 3 connected graphs -i.e. stub domainsper transit node, without any extra transit-stub or stub-stub edges. Each stub domain has on average |Net i|-x y×x nodes, where i ∈ {16, 52, 100}. After the generation of the topology by GT-ITM, we adapt the connections between nodes inside each stub domain so that each stub domain contains a ring. For instance, in Figure 3, we identify the four transit nodes a-d. The transit node a is connected to three stub domains, where (a, a 1 ), (a, a 2 ) and (a, a 3 ) are transit-stub edges.

For all the topologies, there is one client per broker and the client plays both the roles of producer and consumer. Before advertising, subscribing, and publishing, each client obtains the set of scopes known by its access broker. For each combination of scopes, with at most one scope per dimension, the client advertises a filter with a forwarding filter that always returns true and with a visibility filter associated with the corresponding set of scope paths (at most one singleton scope path per dimension). Next, the client does the same with a call to subscribe. Finally, the client publishes one notification per advertisement filter.

If not stated otherwise, we assume that each graph of scopes is a hierarchy with 3 levels (without counting the levels corresponding to the clients and to the specific scopes ⊤ and ⊥). The projection of the graphs of scopes follows Rule 1 , Rule 2 and Rule 3 . In addition, let s 1 , s 2 , s 3 , s 4 and s 5 be five scopes such that s 1 = ⊤ is the root of the graph such that s 1 ⊲ s 2 ⊲ s 4 and s 1 ⊲ s 3 ⊲ s 5 : i) action JoinScope(s 1 ⊳ ⊤) is called at broker d in the transit domain, ii) action JoinScope(s 2 ⊳ s 1 ) is called at neighbouring broker c in the transit domain, iii) action JoinScope(s 4 ⊳ s 2 ) is called at stub domain node d 1 ((d 1 , d 2 ) is a transit-stub edge), iv) action JoinScope(s 3 ⊳ s 1 ) is called at the neighbouring broker a in the transit domain, and so on. When considering two or more graphs of scopes, we take the next transit node of c to be the broker at which action JoinScope(t 1 ⊳ ⊤) is called, where t 1 plays the same role as s 1 .

Finally, if not stated otherwise, all the visibility filters return true.

C. Dissemination of subscriptions

System administrators can control the calls to the JoinScope actions so that some parts of the overlay network of brokers have no knowledge of the scopes of a certain dimension (as exemplified in the third dimension of Figure 1). In the following, we call a subset of brokers that manages the scopes of a dimension a "partition". Scenario 1: Increasing the number of partitions. Every graph of scopes is projected onto a set of stub domains that are connected directly to the same transit node. We study in this scenario the intersection of partitions. Let D 1 , D 2 , and D 3 be the three dimensions considered. In experiment P 1 , no partition intersect: D 1 is present in broker d, and in stub domains of d 1 and d 2 ; D 2 is present in broker a, and in stub domains of a 1 , a 2 , and a 3 ; D 3 is present in broker c, and in stub domains of c 1 , c 2 , and c 3 . In experiment P 2 , the two partitions D 1 and D 2 intersect: they spread over the same brokers (a, d, and those of stub domains of a 1 , a 2 , a 3 , d 1 and d 2 ). In experiment P 3 , the three partitions intersect.

Metric. The following metric is computed: the average number of subscribe messages per call to Subscribe. For each experiment P 1 to P 3 , we compare the results with the case of no scoping -i.e. as if the clients specify ⊥ in their advertisements and ⊤ in their subscriptions.

Results. In Figure 4, we observe that in the three experiments P 1 , P 2 and P 3 , the number of messages exchanged is less than 56% compared to the case of no scoping. In addition, using multiscoping is efficient to drastically diminish the number of subscribe messages: a 22% of decrease when using a second dimension, and a 36% of decrease when using two additional dimensions. In the next section, we study the impact of the projection of the graphs of scopes onto the topology with the placement of clients.

D. Dissemination of notifications

In the rest of the experiments, we do not "partition" the overlay network according to dimensions, but study the benefit of using visibility filters and of mixing several dimensions. The solution is evaluated with respect to i) the number of brokers, ii) the number of graphs of scopes, and iii) the level at which visibility filters always return false. We conduct the following series of experiments.

Scenario 2: Increasing the number of brokers and changing the level at which visibility filters return false. The size of the overlay network is successively increased by considering the three topologies Net 16 , Net 52 , and Net 100 . Only one graph of scopes is considered. We study the impact of the placement of visibility filters that return false: i) all the visibility filters return true, ii) all the visibility filters at level 1 (L1) return false (and only these filters), iii) all the visibility filters at level 2 (L2) return false (and only these filters), and iv) all the visibility filters at level 3 (L3) return false (and only these filters). The results are expressed using percentages: the experiment used as the reference is the "no scoping" one. Scenario 3: Increasing the number of dimensions and changing the level at which visibility filters return false. For a given topology, namely Net 52 , the number of dimensions is successively increased (1, 2 and 3 graphs of scopes).

Metrics. The following metrics are computed: the average number of notification messages per call to Publish, the average number of brokers involved per call to publish, and the average size of the routing table of brokers -i.e. entries with forwarding or visibility filter.

Results. In Figure 5, we observe that the number of notification messages with false visibility filters at L1 is the least important, and is the most important at L3. In experiment L3, the clients that are connected to brokers that are the borders of the topology are isolated. The clients that are connected to brokers that are situated in the transit domain, that are transit-stub domain nodes, etc. are linked through visibility paths. Therefore, isolating clients that are at the borders is meaningful as long as the number of clients that are "in the centre" is not high. Since there is one client per broker in all the experiments, the number of messages exchanged in L3 is the most important. In addition, the difference between L1 and L2, and L2 and L3 with the Net 16 topology are smaller than the ones with the Net 52 and Net 100 topologies. This is because the number of duplicate forwarding paths increases with the size of the network. In Figure 6, the same phenomenon can be observed. Nonetheless, the number of exchanged messages is less important: for example, the percentage is 91 in the experiment L3 with one dimensions and 84 in the experiment L3 with three dimensions. This results from the mixing of several dimensions, as already observed in Scenario 1 for the subscribe messages.

VI. RELATED WORKS

The concept of scope in [START_REF]Publish-subscribe grows up: Support for management, visibility control, and heterogeneity[END_REF] allows to organize a DEBS with a graph of scopes. This corresponds to what we can call monoscoping where only one scope graph is used at a time. [START_REF] Parzyjegla | Engineering Publish/Subscribe Systems and Event-Driven Applications[END_REF] defines "divisions" as different sets of scopes (finance, makerting, production...). Divisions are subsumed into a global graph such that each division is represented by a top-level scope that is a subscope of the root scope of the global graph. This scope hierarchy does not allow to distinguish divisions as clearly as we propose with the concept of dimension. In addition, the root scope is different from the virtual scope ⊤ in two ways: 1) the root scope is the superscope of only top-level scopes whereas ⊤ is a superscope of every scope, 2) the root scope is defined as the "authority" scope that has access to notifications published inside a division and forwards to another division whereas ⊤ is not considered as a central authority. Indeed, in our solution, ⊤ is specified in order to ease the use of multiscoping, not for a global control of the visibility between dimensions. In addition, we do not require advertisements and subscriptions to be tagged for every dimension, thus allowing interoperability with scope-agnostic applications.

With Self-Organizing Broker Overlay [START_REF] Baldoni | Efficient Publish/Subscribe Through a Self-Organizing Broker Overlay and its Application to SIENA[END_REF], the authors propose to dynamically reorganise the overlay topology by avoiding pure forwarders involved in the routing but having no clients. The principle is to have a connection between brokers that match similar events. Brokers therefore run a self-organising algorithm in order to measure the similarity of interest with another broker. The filtering is content-based and a structured data model is used. In the context of the IoT wih edge computing, we rather consider another organisation where brokers have different roles: e.g. border brokers versus inner brokers, or proximity brokers versus brokers in Cloudlets or in Clouds.

Similarly to [START_REF] Baldoni | Efficient Publish/Subscribe Through a Self-Organizing Broker Overlay and its Application to SIENA[END_REF], the authors of [START_REF] Kazemzadeh | Opportunistic Multipath Forwarding in Content-based Publish/Subscribe Overlays[END_REF] propose techniques for rewiring the broker overlay in order to avoid involving pure forwarder brokers. The solution introduces the notion of "subscription anchor" used to store subscription information in brokers' routing tables. From the perspective of a broker, an anchor for a subscription is a broker located up to ∆ hops closer to the issuing subscriber (the anchor of a local subscriber points to the broker itself). Then, the authors present the anchor placement algorithm to propagate subscriptionsi.e. to build the overlay. We can notice that, as highlighted by [START_REF] Barazzutti | StreamHub: A Massively Parallel Architecture for High-Performance Content-Based Publish/Subscribe[END_REF], a bad placement may result in a high number of messages being propagated between brokers. Some optimisations are proposed to address this problem: by connecting subscribers with similar subscriptions to the same brokers [START_REF] Cheung | Design and Evaluation of a Wide-area Event Notification Service[END_REF], or by linking publications and their expected subscribers to the same brokers [START_REF] Li | Community Clustering for Distributed Publish/Subscribe Systems[END_REF]. Again, we are in favor of a more distributed solution in which brokers are present for example to manage visibility filters.

VII. CONCLUSION

We advocate that the high potential of the Internet of Things can be reached only with applications built following fully decentralised software architectures enabling decoupled communication among dynamic and heterogeneous producers and consumers. Decoupling is required in time, space and synchronisation and should not be limited by physical constraints. Therefore such application software architectures should be deployed on highly distributed infrastructures like with edge computing and not on centralised systems such as clouds [START_REF] Garcia Lopez | Edgecentric Computing: Vision and Challenges[END_REF]. Distributed event-based systems are a good candidate for providing decoupled communication as required by the IoT. However, the unprecedented scales envisioned in the IoT call for additional features.

This paper instantiates the semantically rich localised scalability concept [START_REF] Satyanarayanan | Pervasive Computing: Vision and Challenges[END_REF] through a multiscale approach where multiple dimensions of multiple viewpoints may be modelled. Communication may then take place among geographically close entities, entities sharing common interests or entities with any kind of application-defined relationship without having to know each other in a direct way. A multiscale characterisation step allows to specify a graph of multiple scopes providing multiscoping and limiting event dissemination to some parts of the IoT. We propose an implementation of multiscoping in the MUDEBS framework that relies on content-based filtering with a semi-structured data model and we measure its performance gain on event dissemination. First experiments on micro-benchmarks show that multiscoping is efficient to drastically diminish the number of subscribe messages (a decrease of 45%, 67% and 81% when using 1, 2 and 3 dimensions).

Future research directions concern the enforcement of quality of service where our multiscale approach enables flexible and locality-aware QoS management as well as multilevel QoS management [START_REF] Bellavista | Quality of Service in Wide Scale Publish-Subscribe Systems[END_REF]. We are also investigating highavailability solutions such as in [START_REF] Salehi | Highly-available contentbased publish/subscribe via gossiping[END_REF]. We promote a flexible approach in which the brokers self-reorganise to arrange redundant communication paths.

Fig. 1 :

 1 Fig. 1: Multiscale characterisation and DEBS with multiscoping: dimensions, scales, and scopes

Fig. 2 :

 2 Fig. 2: Construction of a visibility path during routing

Fig. 3 :

 3 Fig. 3: Topology of the overlay of brokers Net 52

Fig. 4 :Fig. 5 :Fig. 6 :

 456 Fig. 4: Number of subscribe messages per call to Subscribe, three graphs of scopes, Net 52 .

https://www.w3.org/OWL

http://www.w3.org/2005/Incubator/ssn/XGR-ssn-20110628/

This is the routing filter in classical DEBS without scoping that serves to forward a notification to a destination neighbouring broker or connected client.


Fátima Castro-Jul

Denis Conan

Sophie Chabridon

Rebeca P Díaz Redondo
email: rebeca@det.uvigo.es

Ana Fernández Vilas

Chantal Taconet

Rebeca P Díaz

Combining fog architectures and distributed event-based systems for mobile sensor location certification

Keywords: participatory sensing, smart city, internet of things

come   L'archive ouverte pluridisciplinaire

Introduction

The Smart City paradigm envisions a city where information technologies enhance citizens quality of life by improving urban services. The Internet of Things (IoT) plays a major role in building smart cities since it enables the interconnection of different devices, vehicles or any kind of objects. Additionally, Distributed Event-based Systems (DEBS) [START_REF] Eugster | The Many Faces of Publish/Subscribe[END_REF] have become a popular interaction paradigm for IoT-based smart city services [START_REF] Antonic | A mobile crowdsensing ecosystem enabled by a cloud-based publish/subscribe middleware[END_REF]. These systems support event filtering and producer mobility. The former is essential in large-scale urban sensing, due to the tremendous quantity of data produced. The latter is a promising alternative to building a costly fixed sensing and communication infrastructure to cover the whole city.

Location is one of the main criteria to categorize and filter urban events. Providing spatial context in event distribution allows consumers to subscribe only to their geographical areas of interest. Moreover, even when the event is not location-dependent, receiving information on the producers' whereabouts increases trust in the event content. Implementing location evaluation mechanisms is a non-trivial task in cloud architectures. However, it becomes simpler when part of the data processing is moved to the edges of the network, using a fog architecture.

Fog computing is a promising yet still unexploited possibility to build urban DEBS that provide sensor location certification. To analyze their potential, we have designed three architectures based on fog computing that combine proximity and cloud communication. Our contribution is targeted at providing proximity-based location verification on the edges of the network while employing an architecture that enables communication over a wide-spread area. The aim is to support the quality assessment of publications by relying on proximitybased communication. Thus, we leverage our previous works on quality of context information in DEBS [START_REF] Lim | Enhancing Context Data Distribution for the Internet of Things using QoC-awareness and Attribute-based Access Control[END_REF] and on distributed proximity-based collaboration with peer devices [START_REF] Castro-Jul | Have you also seen that? collaborative alert assessment in ad hoc participatory sensing[END_REF].

This paper is structured as follows. First, we present an overview of related work (Section 2). Then, we detail our proposal (Sections 3 and 4). Finally, we conclude and present our ongoing work in Section 5.

Related Work

The importance of mobile event producers has considerably grown over the last ten years, due to the emergence of participatory sensing [START_REF] Burke | Participatory sensing[END_REF] and mobile crowdsensing systems [START_REF] Ganti | Mobile crowdsensing: current state and future challenges[END_REF][START_REF] Guo | From participatory sensing to mobile crowd sensing[END_REF]. These systems rely on collaborative data gathering and can be implemented using different architectures. When data is collected in a centralized manner, a cloud entity is in charge of receiving all the sensor readings and analyzing them. In this case, a blind confidence is placed in the locations claimed by data producers. In order to enhance trust in the provided location, a possible solution is to switch to a proximity-based totally ad hoc network that ensures producers' communication directly with consumers in their very area [START_REF] Castro-Jul | Have you also seen that? collaborative alert assessment in ad hoc participatory sensing[END_REF]. This is a good solution for small and densely populated urban areas but it becomes expensive when producers and their subscribed consumers are far away from each other. An alternative is to migrate part of the data processing from the cloud to the edges of the network, using a fog computing architecture. Fog computing [START_REF] Bonomi | Fog computing and its role in the internet of things[END_REF] has become a useful paradigm for IoT architectures since it provides heterogeneity and fast mobility support [START_REF] Yannuzzi | Key ingredients in an iot recipe: Fog computing, cloud computing, and more fog computing[END_REF], low latency and scalability [START_REF] Hong | Mobile fog: A programming model for large-scale applications on the internet of things[END_REF]. [START_REF] Munir | IFCIoT: Integrated Fog Cloud IoT Architectural Paradigm for Future Internet of Things[END_REF] targets better localized accuracy through location-based customization but does not verify the trustworthiness of location information. To the best of our knowledge, the potential of fog architectures to support location certification schemes has remained unexploited.

DEBS with location certification support

Our DEBS is targeted at participatory sensing scenarios with high producer mobility and periodic publications of sensed data. We can think of, for instance, a participatory noise measurement system that relies on citizens smartphones. Using a DEBS architecture, event distribution is not limited to the close producer's neighborhood but extends outside the city boundaries and beyond. Consumers subscribe by providing filters that specify the publications they are interested in. Publications are routed from producers to consumers by an overlay network of brokers.

Our goal is to improve publication quality by increasing trust on the publication's source location. As a result, we focus our attention on producers' mobility, and for the sake of simplicity we assume the broker and consumer structure to be fixed. A producer is connected to at most one broker, namely its access broker. When producers move, they may disconnect and reconnect to a different broker.

Location information may be included in every publication: it consists of an explicit representation using coordinates, or of the identifier of a specific area or neighborhood. When the location can be verified, the publication is enriched with a location certificate. The location is added by the producer and may be verified either by the producer or the broker but it is always the broker, assumed to be trustworthy, that decides whether to provide the certificate (Algorithm 1). Consumers choose whether they ask the DEBS to filter out uncertified location.

Algorithm 1 : at broker B, handle a publication

1: procedure HandlePublication(Producer X, Publication n) 2:
if B is the access broker of X then 3:

locOk ← VerifyLocation(n)
// verify location information included in n 4:

if locOk then

5:

ProvideLocationCertificate(n) // add to n a location certificate

6:

Forward n to interested neighbor brokers and local consumers

A publication is certified if the location claim has been verified. The verification consists in assessing the location information using either extra information provided by the producer to support the location claim or the collaboration of other peers in the area. In both cases, the verification relies on proximitybased communication. Proximity-based communication connects devices that are placed closely, at a distance from each other that allows them to be reached using a wireless short-range communication technology, such as Bluetooth or ad hoc WiFi. If a producer that claims to be in a certain area cannot be reached by other devices known to be there, we can conclude that it is not providing its actual location. Following these principles, we foresee three different DEBS architectures supporting location verification and detailed in Section 4.

Fog-based architectures

In traditional DEBS cloud architectures, clients (producers and consumers) are connected through an overlay of brokers that are hosted in a cloud. An access broker may serve clients from different locations (Figure 1.a). It has no knowledge about the clients' location and no way to verify whether they are claiming false locations. As an alternative, we introduce three different fog architectures for a DEBS with location verification support. The different combinations of cloud and short-range communication determine how the location verification process is performed. This architecture considers two levels of brokers: border brokers that are in the vicinity (e.g., B1, B5 in Figure 1.b) and inner brokers that are hosted in the cloud (e.g., B2, B3, B4). Border brokers are placed all over the city covering different areas; they are fixed, thus being assigned an immutable location. Clients in the same area are connected to the same access broker using a short-range transmission technology that ensures the veracity of the clients' location. As a result, location verification is straightforward. The access broker will certify the location of every publication whose location attribute coincides with the broker location (Algorithm 2).

A mobile producer may have to disconnect temporary. Publications created by disconnected producers are stored in a local queue, to be issued to the new access broker when reconnecting. If the location is different from the new access broker's location, they are distributed but not considered for location certification because a broker can not certify a location different from its own. Algorithm 2 Verify location information (Fixed brokers architecture)

1: procedure VerifyLocation(Publication n) 2:
return (location included in n "equals" access broker's location)

Assigned brokers architecture

Even though a hybrid architecture is a cheaper alternative to deploying a purely fixed sensor network architecture, its cost is still high. As a result, we have designed a second architecture, which still exploits location verification through proximity-based communication but gives up the requirements for a fixed infrastructure. By considering location-based network partitions, we maximize the probability of having all the clients in an area connected to the same broker (Fig-ure 1.c). Thus, they can still be in charge of producers' location verification even though they cannot communicate with them using a short-range transmission technology. Producers obtain the IP address of their access brokers by providing their location to a discovery service. Producers include in their publications a set of other producers in the area with whom they have established a short-range communication link and who are connected to the same broker (neigh). If nearly all1 of the producers included in the set are registered as local producers of the same access broker, the location is confirmed (Algorithm 3). Producers claiming a false location are not able to provide a valid set of neighbors.

Algorithm 3 Verify location information (Assigned brokers architecture)

1: procedure VerifyLocationInformation(Publication n) 2:
return (location included in n "equals" access broker's location ∧ "most of" the producers ∈ neigh are local producers)

Neighbor-based architecture

Unlike the two previous architectures, brokers are not assigned to specific areas and location verification takes place between peer neighbor producers. Producers can be connected to any access broker, which may be different from the one their close neighbors are connected to (Figure 1.d). By exchanging shortrange messages, they are always aware of who their neighbors are. When a producer is going to send a publication, it triggers a consensus process between its neighbors. In this process, neighbor producers propose location values and decide on one of them, which will be included in the publication. Since we are dealing with a dynamic scenario where it may be difficult to decide due to variations in the number of neighbors, we consider abortable consensus [START_REF] Guerraoui | Introduction to Reliable Distributed Programming[END_REF][START_REF] Chen | Abortable Consensus and Its Application to Probabilistic Atomic Broadcast[END_REF]: the result of the consensus is either a location value or aborted . If no location value can be reached by consensus, the producer includes its own proposed location value in the notification. Then, the publication sent to the broker includes, in addition to the location, an indication about the consensus result (successf ul or aborted). The broker does not take part in the verification process and certifies every publication that includes an indication of successful consensus (Algorithm 4). Remark that changing the access broker does not necessarily imply a change of producers' location and does not invalidate a location certification. We are currently working on the evaluation of the architectures. We plan to employ network simulations based on pedestrian traces generated in real urban maps. The assessment will be focused on the appropriate location verification and on the ability to handle producer's mobility in highly dynamic urban scenarios.

Fig. 1 :

 1 Fig. 1: Fog-based architectures 4.1 Fixed brokers architecture

Algorithm 4

 4 Verify location information (Neighbor-based architecture)1: procedure VerifyLocationInformation(Publication n) 2:return (indication of consensus in n equals successful)5 Conclusion and Ongoing WorkThis paper presents three different fog architectures, targeted at location certification support in DEBS for IoT urban services. They combine cloud and proximity-based communication, which enables them to provide first-hand location verification.

To tolerate disconnections and overlapping

Acknowledgments This work is funded by: the European Regional Development Fund (ERDF) and the Galician Regional Government under agreement for funding the Atlantic Research Center for Information and Communication Technologies (At-lantTIC), the Spanish Ministry of Economy and Competitiveness under the National Science Program (TEC2014-54335-C4-3-R) and a predoctoral grant financed by the Galician Regional Government (Consellería de Cultura, Educación e Ordenación Universitaria) and the European Social Fund.