the quantitative observations that mobile crowdsensing gathers. Characterising the context of crowdsensed observations has been extensively studied regarding the recognition of the user activity and more specifically the mobility condition (whether moving and with which mean) [122, 134]. On the other hand, inferring the sensing context with respect to the physical environment under scrutiny has received less attention, while related solutions focus on a single context element and do not account for the diversity of the contributing devices. Yet, it is essential to infer together the context elements that impact the crowdsensing, as they are all equally important. While considering a variety of eligible features, one should account for the variation in the availability of features across the contributing devices. Our approach addresses these requirement by being self-adaptive to the diversity of users (and devices). As a first step, we start from the characterisation of the crowdsensor context, spanning from the physical environment, user's activity and device capabilities. In particular, we provide a ranking over all the candidate features so as to compose the most significant feature set for each classification. Then, the user-centric classification on the user's device may be performed on any subset of the above set so as to account for the diversity of devices and related embedded sensors. The set may further be customised and freely recomposed, trading off energy efficiency and accuracy, to offer adaptiveness.

The sensing context must distinguish between in-pocket and out-pocket observations be-
cause the former leads to a quite significant deviation from the ground truth and are thus
not readily usable [43]. The same applies to both in-door versus out-door measurements as
well as under-ground versus upper-ground readings since aggregating them together to analyse
environmental phenomena obviously leads to unreliable results [83].

Overall, the major outcome of the group-based collaboration is:

* A context inference module for crowdsensor to provide explicit context information including both device attributes and user behaviours (§ 4.2.1).

* A context-based grouping to share position/internet and optimise the crowdsensing tasks, so as to decrease power consumption during registration and task assignments (§ 4.3).

* A context-based data aggregation/pre-processing module for crowdsensing groups in order to decrease the Internet traffic toward the cloud (§ 4.4.1).

4.2.1 Context Characterisation

The context of a crowdsensor serves assessing the relevance of its peering with nodes in the D2D communication range for the sake of enhanced efficiency, that is, the ability to improve the gathered knowledge prior to transferring it to the cloud in a way that reduces resource-consumption. In addition, determining how long the current context is going to last is critical to ensure that the benefit of the collaborative crowdsensing at the edge outperforms the overhead due to the group management/configuration. The context characterises the crowdsensor's collaboration profile, which subdivides into:

* PE (*Physical Environment*) defines the position of the embedded sensors, which influences the given observations of physical phenomena. It detects if the crowdsensor is: in/out-pocket, in/out-door and under/above-ground.

* UA (*User Activity*) refers to the mobility (walking, cycling, driving) or non-mobility (still) of the end-user. In order to support the activity recognition, we rely on the activity recognition module [57] implemented by the operating system.
* **DA** (*Device Attributes*) characterises the ability of the device to contribute to the various crowdsensing tasks. The attributes include the available networking and computing capabilities (*i.e.*, type of Internet access –e.g., WiFi–, (upload) bandwidth, remaining battery, CPU frequency, and memory size), the type of embedded sensors (*e.g.*, {"Temperature", "Light", "Pressure", "Humidity", "Sound level"}) together with the related power consumption and accuracy.

The user activity and devices attributes are obtained from the devices. In the following, our aim is focused on the characterisation of the physical environment and on the prediction of how long the current UA and PE are going to last. The classification of the sensing context of mobile "crowdsensors" has been the focus of various papers [131, 73, 77]. However, the existing work focuses on the inference of a single context element, while it is essential to accurately characterise the sensing context as a whole, that is, to identify whether a contributed observation is sensed with the device: in-pocket/out-pocket, in-door/out-door and under-ground/on-ground. Machine learning is an obvious candidate to systematise such a characterisation. Thus, starting from the sensors available on today's smartphones, we identify the features that best serve classifying each of the three elements of the sensing context. We then analyse the performance of candidate updatable learning algorithms to initialise the three resulting classifiers, taking into account their classification accuracy as well as their run-time and memory efficiency, from which we design the hierarchical inference system. In the mean time, we leverage online machine learning in a way similar to the inference of PE, to predict how long current UA and PE should last.

## 4.2.2 Feature Selection

In order to select the best feature set for each of the three classifications $M_{pocket}$, $M_{door}$ and $M_{ground}$, we use a data set of 20K which provides the supporting ground truth, using a Crosscall Trekker-X3 phone. The data set covers all the candidate features in all the scenarios to be classified, *i.e.*, in/out-pocket, in/out-door and under/on-ground; the amount of labelled data for each class is uniform. Among the data supplied by sensors, the candidate features are the following: proximity, temperature, light density, GPS accuracy, abstract RSSI level, GSM RSSI value, WiFi raw RSSI, light density, pressure, humidity. The most relevant features for each of our three classifications are defined based on their significance, which is defined by higher information gain and gain ratio, Gini and ReliefF while we set the required threshold value to 0.1 for both. The top three features for the $M_{pocket}$ classification (see Table 4.1) are proximity, temperature and light density. $M_{door}$ is relatively more complex (Table 4.2) with six candidate features (GPS accuracy, abstract RSSI level, GSM RSSI value, WiFi raw RSSI, light density, temperature) providing an information gain and a gain ratio above 0.1. Although the underground scenario (Table 4.3), which is considered as a sub-case of the in-door scenario, shares five of them with the latter and needs new features, *i.e.*, pressure and humidity. However, device models do not always support the sensing of the pressure and humidity, in which case other features remain decisive.

<table><caption>Table 4.1 – 3 Features classifying In-pocket/Out-pocket</caption><thead><tr><td>Feature/Metric</td><td>Info. gain</td><td>Gain ratio</td><td>Gini</td><td>χ<sup>2</sup></td><td>ReliefF</td></tr></thead><tbody><tr><td>Proximity</td><td>0.931</td><td>0.720</td><td>0.478</td><td>17776.819</td><td>0.329</td></tr><tr><td>Temperature</td><td>0.344</td><td>0.172</td><td>0.213</td><td>273.650</td><td>0.097</td></tr><tr><td>Light density</td><td>0.310</td><td>0.155</td><td>0.169</td><td>3758.434</td><td>0.034</td></tr></tbody></table>
<table><caption>Table 4.2 – 6 Features classifying In-door/Out-door</caption><thead><tr><th>Feature/Metric</th><th>Info. gain</th><th>Gain ratio</th><th>Gini</th><th>χ<sup>2</sup></th><th>ReliefF</th></tr></thead><tbody><tr><td>GPS accuracy</td><td>0.974</td><td>0.715</td><td>0.482</td><td>9085.097</td><td>0.996</td></tr><tr><td>Abstract RSSI level</td><td>0.794</td><td>0.493</td><td>0.416</td><td>15416.226</td><td>0.293</td></tr><tr><td>GSM RSSI value</td><td>0.738</td><td>0.370</td><td>0.384</td><td>11211.066</td><td>0.157</td></tr><tr><td>WiFi raw RSSI</td><td>0.320</td><td>0.180</td><td>0.148</td><td>437.694</td><td>0.133</td></tr><tr><td>Light density</td><td>0.255</td><td>0.127</td><td>0.157</td><td>5041.293</td><td>0.050</td></tr><tr><td>Temperature</td><td>0.228</td><td>0.114</td><td>0.125</td><td>50.212</td><td>0.070</td></tr></tbody></table>

<table><caption>Table 4.3 – 7 Features classifying Under-ground/On-ground</caption><thead><tr><th>Feature/Metric</th><th>Info. gain</th><th>Gain ratio</th><th>Gini</th><th>χ<sup>2</sup></th><th>ReliefF</th></tr></thead><tbody><tr><td>Abstract RSSI level</td><td>0.547</td><td>0.340</td><td>0.296</td><td>11586.949</td><td>0.250</td></tr><tr><td>GPS accuracy</td><td>0.434</td><td>0.318</td><td>0.222</td><td>4182.467</td><td>0.528</td></tr><tr><td>Temperature</td><td>0.485</td><td>0.243</td><td>0.255</td><td>1905.520</td><td>0.255</td></tr><tr><td>GSM RSSI value</td><td>0.463</td><td>0.232</td><td>0.262</td><td>8031.071</td><td>0.143</td></tr><tr><td>Pressure</td><td>0.376</td><td>0.188</td><td>0.202</td><td>6136.352</td><td>0.224</td></tr><tr><td>WiFi raw RSSI</td><td>0.181</td><td>0.170</td><td>0.086</td><td>5594.195</td><td>0.103</td></tr><tr><td>Humidity</td><td>0.276</td><td>0.138</td><td>0.142</td><td>2475.257</td><td>0.161</td></tr></tbody></table>

### 4.2.3 Classifier Initialisation

We further train the classifiers $M_{pocket}$, $M_{door}$ and $M_{ground}$ using their respective most significant features. Various algorithms are eligible for the classification problem [120] although fewer are updatable. We have specifically selected six candidate updatable algorithms: *Hoeffding Tree* (Very Fast Decision Tree), *IBk* (Instance Based K-nearest neighbours classifier), *KStar* (Instance-based Learner), *LWL* (Locally Weighted Learning), *updatable Naive Bayes*, and *SGD* (Stochastic Gradient Descent) [174].

Table 4.4 compares the selected algorithms according to the same four metrics for our three classifications: $M_{pocket}$, $M_{door}$ and $M_{ground}$. Our selection criteria is motivated by the size of the model on the (resource-constrained) mobile device, 10-fold Cross Validation Classification Accuracy (CVCA) that reflects the classification accuracy, i.e., the proportion of correctly classified examples, the Online Learning Run-time (OLSR) and the Inference Run-time (IR).

The result for $M_{pocket}$ in Table 4.4 shows that all the classifiers can provide a similar high CVCA of about 99%. However, a significant difference appears among the sterilised sizes: *IBk*, *KStar* and *LWL* are storing training instances inside the learning model, which makes the size of the classifier proportional to the size of the training dataset. Instead, *H TREE*, *NaiveBayes* and *SGD* require a much lower *Size*. *IBk* and *LWL* have an *OLR* greater than 3ms, while it is less than 1ms for the other four. *IBk*, *KStar* and *LWL* all have much longer *IR* than *H TREE*, *NaiveBayes* and *SGD*. A better cross validation result is discovered for $M_{door}$: All the algorithms provide the maximum classification accuracy in cross validation of 100%. However, although the dataset is unchanged compared to $M_{pocket}$, the serialized size of *IBk*, *KStar* and *LWL* increases due to the number of selected features. Besides, the *OLRs* do not change significantly, and are less than 1ms except for *IBk* and *LWL*. *IBk*, *KStar* and *LWL* still have a longer *IR* than the other three algorithms. Result for $M_{ground}$ shows that *LWL* and *NaiveBayes* give lower classification accuracy in cross validation than other algorithms, but still over 95%. The high storage cost remains for *IBk*, *KStar* and *LWL* as they require storing historical data. They further cost a much longer *IR* than the other three algorithms. As for *H TREE*, *NaiveBayes* and
SGD, both their OLR and IR remain below 1ms, with the negligible exception of the IR of NaiveBayes at 1.223. Overall, IBk, KStar and LWL show the highest space and time costs, and we discard them.

Finally, we select Hoeffding Tree, Naive Bayes and SGD as initial classifiers, as they show a fairly small space and time cost as well as the highest accuracy and lowest space/time costs.

<table><caption>Table 4.4 – Initial learning models.</caption><thead><tr><th>Metric/Model</th><th>H TREE</th><th>IBk</th><th>KStar</th><th>LWL</th><th>NaiveBayes</th><th>SGD</th></tr></thead><tbody><tr><td colspan="7" style="text-align:center; font-style:italic;">M<sub>pocket</sub></td></tr><tr><td>Size (kB)</td><td>16</td><td>1158</td><td>1157</td><td>1158</td><td>3</td><td>5</td></tr><tr><td>CVCA (%)</td><td>99.1538</td><td>99.469</td><td>99.350</td><td>99.149</td><td>98.999</td><td>99.180</td></tr><tr><td>OLR (ms)</td><td>0.020</td><td>3.809</td><td>0.081</td><td>4.344</td><td>0.012</td><td>0.123</td></tr><tr><td>IR (ms)</td><td>0.057</td><td>10.545</td><td>165.844</td><td>91.325</td><td>1.635</td><td>0.018</td></tr><tr><td colspan="7" style="text-align:center; font-style:italic;">M<sub>door</sub></td></tr><tr><td>Size (kB)</td><td>9</td><td>1612</td><td>1791</td><td>1764</td><td>4</td><td>6</td></tr><tr><td>CVCA (%)</td><td>100</td><td>100</td><td>100</td><td>100</td><td>100</td><td>100</td></tr><tr><td>OLR (ms)</td><td>0.036</td><td>5.150</td><td>0.062</td><td>5.813</td><td>0.011</td><td>0.172</td></tr><tr><td>IR (ms)</td><td>0.071</td><td>11.823</td><td>364.790</td><td>109.644</td><td>1.610</td><td>0.047</td></tr><tr><td colspan="7" style="text-align:center; font-style:italic;">M<sub>ground</sub></td></tr><tr><td>Size (kB)</td><td>13</td><td>1763</td><td>1763</td><td>1763</td><td>4</td><td>6</td></tr><tr><td>CVCA (%)</td><td>100</td><td>100</td><td>100</td><td>98.060</td><td>97.105</td><td>100</td></tr><tr><td>OLR (ms)</td><td>0.024</td><td>4.628</td><td>0.062</td><td>6.720</td><td>0.009</td><td>0.111</td></tr><tr><td>IR (ms)</td><td>0.061</td><td>15.160</td><td>238.916</td><td>128.149</td><td>1.223</td><td>0.018</td></tr></tbody></table>

In order to predict how long the current UA and PE are going to last, we leverage online machine learning in a way similar to the inference of PE: we predict the duration of the current UA (resp. PE) according to the current time and UA (resp. PE). The prediction of the UA/PE duration is a regression problem, rather than a classification. Many online learning algorithms may address the prediction model but fewer deal with regression. We have investigated three eligible algorithms: IBk (Instance Based k-nearest neighbour algorithm), KStar (an instance-based learner), and LWL (Locally Weighted Learning) [174]. We selected LWL as training algorithm because it provides the lowest RMSE and latency.

### 4.2.4 Online Personalising

The design rationale of our online learning solution is the following: The initially trained classifier is deployed on the participating devices at the time of the installation of the embedding crowdsensing middleware/application. While the inference of the sensing context is running on the device, feedback is requested from the user to assess the correctness of the inference result. The collected opportunistic feedback is then converted to a labelled training instance that updates the current learning model.

Through the online learning, the initial classifier gets personalised on various device models, according to diverse user behaviours and usage scenarios. In particular, the features that are not available locally become non-contributing to the related classifiers as they get updated. There is a well-known risk associated with online learning that is reaching a local optimum but not a global one as the classification accuracy may not be convex due to the continuous update. We address this limitation through opportunistic feedback where the user is given the opportunity to notify wrong context inferences.
Gathering feedback should be limited as much as possible to minimise the burden on the user, while still enhancing the accuracy of our three classifiers $M_{pocket}$, $M_{door}$ and $M_{ground}$ over time. We achieve the above by applying a hierarchical inference and update of the classifiers. While more detail about the hierarchical inference (along with the related Algorithm) can be found in [51], the design rational of the hierarchical follows from the predominant role of the in-pocket classifier over the two others and of the in-door classifier over the under-ground one when sensing the physical environment. Specifically, a crowdsensed measurement is relevant if out-pocket. Thus, the in-door/out-door detection is meaningful only when the device is out-pocket and ready for sensing. Further, the under-ground/on-ground case is a sub-scenario of the in-door situation. Similarly, requesting the user’s feedback is sensible only if the user is in the position to easily do so. Typically, requesting feedback when the device is in the pocket is too cumbersome for the user.

## 4.3 Assessing the Crowdsensor Utilities

We introduce a set of utility functions to evaluate the extent to which crowdsensors are eligible to carry out the various crowdsensing tasks. The following crowdsensing tasks must be implemented within any collaborative group: Coordinator (implementing the D2D network access point for the group and assigning the crowdsensing tasks to the connected crowdsensors, i.e., neighbours), Location provider (supplying geographical coordinates), Internet proxy (providing Internet access and thus transferring data to the cloud), Data aggregator (analysing together the collected data locally before sending to the cloud to, e.g., calibrate the sensors [149], analyse the data [165]), and, of course, Sensors. In practice, we rely on the following classical squashing function $f$ for the normalisation of the values used in the computation and comparison of the utilities:

$$f(x, k, x_0) = \frac{1}{1 + e^{k(x_0 - x)}}$$

where: the range of $f$ lays into (0, 1), $k$ is the logistic growth rate or steepness of the curve, and $x_0$ is the x-value of the midpoint of sigmoid, while $x$ is the variable to be normalised. The values of $k$ and $x_0$ are set according to the domain of the specific $x$. In the following, we denote $k_f$ and $x_f$ the values of $k$ and $x_0$ for a given function $f$, while the actual values of the various parameters have been set during the prototype evaluation. Next, we further define the utility functions for each crowdsensing tasks, relying on the squashing function that normalises the values (as defined in Table 4.5)

### Coordinator

- The selection of the coordinator is based on the following criteria:

* The number of neighbours $N_i$ has a significant impact on the overall performance because increasing the number of collaborators enables analysing more data locally and reducing the transfer of data to the cloud. In contrast, there is no benefit in creating groups with too few crowdsensors for which the minimum value $\delta$ depends on the application.

* The occurrences of collaboration $h_i$ between a crowdsensor $i$ and its neighbours is another relevant parameter as it reveals the relationship between crowdsensors materialised by the sharing of daily routines, habits, activities.

* The UA and PE (except pocket) $d_i$ of the crowdsensor should last sufficiently long.
<table><caption>Table 4.5 – Set of parameters used to measure the utility associated with a task</caption><thead><tr><th>Parameter</th><th>Function</th><th>Parameter(s)</th></tr></thead><tbody><tr><td>Sufficient number of neighbours</td><td>Δ<sub>i</sub> = f(max{0, |N<sub>i</sub>| - δ}, k<sub>Δ</sub>, x<sub>Δ</sub>)</td><td>N<sub>i</sub> : neighbours<br>δ: minimum value</td></tr><tr><td>Collaboration occurrences</td><td>h<sub>i</sub> = f(∑<sub>j∈N<sub>i</sub></sub> t<sub>collab</sub>(i,j) / |N<sub>i</sub>|, k<sub>h</sub>, x<sub>h</sub>)</td><td>t<sub>collab</sub>(i, j): number of times i collaborated with j</td></tr><tr><td>Context (i.e., UA, PE) durability</td><td>d<sub>i</sub> = f(min{dur(UA), dur(PE)}, k<sub>d</sub>, x<sub>d</sub>)</td><td>dur(UA), resp. dur(PE) predicted duration of the current UA, resp. PE</td></tr><tr><td>Remaining battery capacity</td><td>b<sub>i</sub> = f(bat<sub>i</sub>, k<sub>b</sub>, x<sub>b</sub>)</td><td>bat<sub>i</sub>: remaining battery</td></tr><tr><td>Accuracy versus power</td><td>l<sub>i</sub> = f(ACC<sub>l</sub>, k<sub>l</sub>, x<sub>l</sub>) - f(POW<sub>l</sub>, k<sub>l</sub>, x<sub>l</sub>)</td><td>ACC<sub>l</sub>: accuracy<br>POW: power</td></tr><tr><td>Upstream bandwidth versus power</td><td>n<sub>i</sub> = f(bw<sub>up</sub>, k<sub>n</sub>, x<sub>n</sub>) - f(POW<sub>net</sub>, k<sub>np</sub>, x<sub>np</sub>)</td><td>bw<sub>up</sub>: Bandwidth<br>POW<sub>net</sub>: power consumed for transmission</td></tr><tr><td>Accuracy vs power</td><td>d'<sub>i</sub> = f(dur(PE<sub>out</sub>), k<sub>d</sub>, x<sub>d</sub>)</td><td>dur(PE<sub>out</sub>): duration of the crowdsensor being out of the pocket</td></tr></tbody></table>

* The remaining battery capacity $b_i$ of the crowdsensor should obviously be taken into account.

Next, provided the weights $w_Δ$, $w_h$, $w_d$, $w_b$, all ∈ [0, 1], set for the above criteria, we define the utility $u_c(i)$ of the crowdsensor $i$ associated with acting as coordinator as the weighted sum of the above functions:

$$u_c(i) = w_Δ \cdot Δ_i + w_h \cdot h_i + w_d \cdot d_i + w_b \cdot b_i$$

## Location provider

On a smartphone, the location is either GPS- or network-based. While the GPS location brings higher accuracy out-door, it also comes with higher energy consumption and latency, compared to the network-based location. The utility function for crowdsensor $i$ of being a location provider is thus defined as $u_l(i)$, which accounts for the location service source<fnref n="1" />, location accuracy and remaining battery capacity:

$$u_l(i) = l_i + w_d \cdot d_i + w_b \cdot b_i$$

## Internet proxy

The Internet proxy transfers the (analysed) data provided by the group of crowdsensors to the cloud server. The service may be provided using either long range cellular or short range WiFi transmission, while we assume that a node supporting both networks will offer the WiFi based transmission by default. The utility function $u_p(i)$ for crowdsensor $i$ acting as Internet proxy then accounts for the Internet connection interface, up-link network bandwidth, and remaining battery capacity:

$$u_p(i) = n_i + w_d \cdot d_i + w_b \cdot b_i$$

<footnote n="1">1. Note that when the location service not operational, $l_i = -∞$.</footnote>
## Data aggregator

The data aggregator provides in charge the analysis of the sensing data collected locally. While lightweight data processing can be performed by the coordinator or by the proxy, complex data analysis may be delegated to a dedicated device that holds the necessary processing capabilities (spanning available memory, CPU frequency and remaining battery capacity). This results in the following definition for the supporting utility function $u_a(i)$:

$$u_a(i) = w_c[f(cpu_i, k_c, x_c) - f(pow_c, k_{cp}, x_{cp})] + w_r[f(mem_i, k_r, x_r) + w_d.d_i + w_b.b_i]$$

where: cpu_i is the CPU frequency, pow_c is the power consumption of the CPU, mem_i is the available memory, and coefficients w_c, w_r are the weights set for the metrics.

## Sensors

The utility of a crowdsensor to carry out the sensing task depends on the accuracy of the contributed observations and their power consumption. In particular, a crowdsensor within a pocket/bag is ignored, which we filter out using the duration of the crowdsensor being out of the pocket (as defined by the $PE_{out}$ value of PE):

which leads to the following utility function, $u_s(i) \in (-1, 1 + w_d)$:

$$u_s(i) = d'_i[f(acc_i^s, k_a, x_a) - f(pow_i^s, k_{sp}, x_{sp}) + w_d.d_i]$$

where: $acc_i^s$ (resp. $pow_i^s$) is the accuracy (resp. power consumption) of the sensor of type s on crowdsensor i.

## Utility-based Grouping

Provided the utility functions, the grouping algorithm leverages the communication and discovery protocols implemented at the link layer by state of the art D2D communication technologies. Without loss of generality, our grouping algorithm builds upon the WiFi Direct technology [9]. In a nutshell, WiFi Direct establishes a D2D opportunistic network through the discovery of peer nodes followed by the election of the node acting as the network's access point according to the criteria provided by the upper layer (i.e., in our case, the coordinator utility value provided by the middleware). Furthermore, the grouping algorithm runs on every node i, either on-demand or on a periodic basis according to the network's dynamics. Once a group is created, the arrival/departure of nodes is detected at the link layer by the underlying D2D protocol. This enables two approaches to the reconfiguration of the group: (i) on a periodic basis, or (ii) on-demand upon the detection of the departure/arrival of a group member. The latter performs very well and induces almost no cost when very few topology changes occur and when the context evolves slowly. On the other hand, it may lead to a unnecessarily high traffic and constant reassignment in a highly dynamic environment. Keeping in mind that, in practice, users are still most of the time (and hence evolving in the same context), by default we adopt an on-demand approach (based on context change). Nevertheless, the middleware switches to periodic re-assignment when the context gets highly dynamic. Subsequently, our work focuses on a distributed interpolation and aggregation approach running on the crowdsensors to achieve both higher sensing quality and efficiency.
## 4.4 Opportunistic Aggregation and Interpolation

A mobile crowdsensing application dealing with urban pollution monitoring (e.g., noise, air quality, water quality, etc.) needs to sense, pre-process, interpolate, then aggregate and relay measurements in a P2P way so as to favour computation at the edge and thereby limit the resource and financial costs associated with the use of the cloud infrastructure. Concretely, we attempt to support a fully distributed, collaborative approach to crowdsensing, in which crowdsensors further interpolate data, and aggregate their respective contributions to the observations of the phenomenon in a collaborative way. The intent is to overcome the spatio-temporal sparsity and to limit—or even avoid— the use of a centralised infrastructure server. There are many interpolation methods for inferring spatio-temporal phenomena; the smartphone is becoming increasingly powerful to perform such advanced tasks. However, the collaboration [170, 46, 177] primarily deals with handling the relay of data, while deployed static edge servers are in charge of the distributed data aggregation. Our approach leverages the advantage of the former and overcomes the disadvantage of the latter: it implements an opportunistic data relay and analysis on the move, across the crowdsensors.

In particular, our solution supports the repeated monitoring of a physical phenomenon over (a possibly large) area over a given time period $\mathcal{D}$ using the contributions of the $m$ crowdsensors. The data that each crowdsensor collects is represented as a concise 3-dimensional tensor where the first two dimensions refer to the spatial space and the third one to the temporal domain. In particular, we discretise the target region into a $I \times J$ area, which contains equally spaced grid points. We also discretise $\mathcal{D}$ into $K$ time slots of equal duration.

We denote $\mathcal{Y}_s \in \mathbb{R}^{I \times J \times K}$ the tensor that crowdsensor $s$ ($1 \le s \le m$) maintains and that is such that entry $y(x) \in \mathbb{R}$ at position $x := (i, j, k) \in \mathbb{R}^3$ is the average of the measurements collected by $s$ over the area indexed by $(i, j)$ during the time interval indexed by $k$. In other words, any crowdsensor $s$ contributes a tensor $\mathcal{Y}_s$ that provides a sparse/incomplete observation of the physical phenomenon according to $s$ behaviour. The middleware then allows the opportunistic combination of the various tensors $\mathcal{Y}_s$ ($1 \le s \le m$) using interpolation and aggregation so as to compute an overall $\mathcal{Y}$.

The periodic process runs on every participating crowdsensor to compute $\mathcal{Y}$. The process iterates over time windows of duration $\mathcal{D}$. Within a given time window $T_{+\mathcal{D}}$, the process runs in parallel: (i) the collection of the measurements provided by the embedded sensors to update the tensor $\mathcal{Y}_s(T_{+\mathcal{D}})$ of the current time window, and (ii) the opportunistic aggregation of the local tensor of the previous time window $T$ with the ones of peers as they meet (see detail in § 4.4.2). At the end of the time window, GPR-based spatio-temporal interpolation is applied on the associated local tensor to recover missing values (see detail in § 4.4.1). We highlight that the interpolation is run locally, only once and prior to the aggregation process run over the next time window because: (i) the number of occurrences must be minimised due to the high cost of the interpolation computation, and (ii) the local interpolated tensor allows assessing the quality of the local measurements against the ones of the peers that the node meets, which the aggregation process leverages. Finally, at the end of the current time window $T_{+\mathcal{D}}$, the node ultimately sends its local tensor to the cloud, unless it got aggregated and relayed by another peer.

### 4.4.1 Spatio-temporal Interpolation

Given a sparse tensor $\mathcal{Y}_s$ resulting from the averaging of the local measurements collected at $s$ over time duration $\mathcal{D}$, interpolation allows completing the tensor by estimating missing
observations. The dense tensor $\hat{\mathcal{Y}}_s$ denotes the resulting (denser) tensor. The quality of the estimation can be established based on the approximation error (i.e., residual) at point $x$, that is: $e(x) := |y(x) - \hat{y}(x)|$ where we recall that the function $y: \mathbb{R}^3 \to \mathbb{R}$ maps an arbitrary point $x := (i, j, k)$ to its observation value $y(x)$. The overall residual is then given by $\mathcal{E} = \|\mathcal{Y} - \hat{\mathcal{Y}}\|$.

Let $\Omega$ be the set of observation points collected by a given crowdsensor. The boolean mask tensor $\mathcal{M} \in \mathbb{B}^{I \times J \times K}$ is defined such that $m(x) = 1$ if there is a corresponding value within $\Omega$, and $m(x) = 0$ otherwise. Thus, $\mathcal{M} * \mathcal{Y}$ provides the actual observations (i.e., ground truth as sensed). When estimating $\hat{\mathcal{Y}}$ based on a sparse tensor $\mathcal{Y}$ with mask $\mathcal{M}$, we seek to minimise the following loss function, which is associated with the approximation $\hat{\mathcal{Y}}$:

$$J(\mathcal{Y}, \hat{\mathcal{Y}}) := \frac{1}{2} \sum_{x \in \Omega} e(x)^2 = \frac{1}{2} \|\mathcal{M} * (\hat{\mathcal{Y}} - \mathcal{Y})\|^2$$

where: $\| \cdot \|$ denotes the Euclidean norm of a tensor, and $*$ represents the element-wise multiplication.

We leverage Gaussian Process Regression (GPR) [132] to compute $\hat{\mathcal{Y}}$ out of $\mathcal{Y}$. That is, we assume that $y$ follows a Gaussian Process (Gaussian distribution over functions), i.e.:

$$y(x) \sim \mathcal{GP}(\mu(x), k(x, x'))$$

where: $\mu(x) = \mathbb{E}[y(x)]$ refers to the mean function, and $k(x, x')$ is the covariance matrix, i.e., the kernel of the GPR, which verifies $k(x, x') = \mathbb{E}[(y(x) - \mu(x))(y(x') - \mu(x'))]$.

The covariance function is a crucial ingredient of GPR as it encodes the notion of similarity between two nearby data points $x$ and $x'$ on the basis that observations that are close to each other (in both time and space) are likely to have higher correlation. Various families of covariance functions exist (see [132] for an overview), including, e.g., squared exponential, polynomial, and Matérn class. In our case, the Matérn class [110] induced the lowest error and runtime compared to alternative functions.

We assume that the observation $y$ is noisy, which is more realistic. We therefore consider a regression that aims at establishing $y = y(x) + \epsilon$ where: the function $y(x)$ follows a Gaussian Process, i.e., $y(x) \sim \mathcal{GP}(\mu, k)$, and the noise is additive, independent, and corresponds to an identically distributed Gaussian noise: $\epsilon \sim \mathcal{N}(0, \sigma_e^2)$. Furthermore, given $n$ observed values $Y = [y_1, \cdots, y_n]^\top$ obtained at the location points $X = [x_1, \cdots, x_n]^\top$, the joint distribution of $[y(x_1), \cdots, y(x_n)]^\top$ follows a Gaussian distribution:

$$[y(x_1), \cdots, y(x_n)]^\top \sim \mathcal{N}(\mu, K)$$

where: $\mu = [\mu(x_1), \cdots, \mu(x_n)]^\top$ refers to the mean vector, and $K$ is a $n \times n$ covariance matrix with $K_{ij} = k(x_i, x_j)$.

Our interpolation aims at inferring $Y^* = y(X^*)$, which includes $m$ unobserved points stored in the tensor $X^* = [x_1^*, \cdots, x_m^*]^\top$.

The inferred tensor $Y^*$ follows a Gaussian distribution:

$$p(Y^*|X^*, X, Y) = \mathcal{N}(\hat{\mu}, \hat{\sigma}^2 + \sigma_e^2 \mathcal{I})$$

With a mean and variance of $Y^*$ respectively estimated as:

$$\hat{\mu} = \mathcal{K}(X, X^*)^\top [\mathcal{K}(X, X) + \sigma_e^2 \mathcal{I}]^{-1} Y$$

$$\hat{\sigma}^2 = \mathcal{K}(X^*, X^*) - \mathcal{K}(X, X^*)^\top [\mathcal{K}(X, X) + \sigma_e^2 \mathcal{I}]^{-1} \mathcal{K}(X, X^*)$$
Once the GPR model is trained, the mean value $\hat{\mu}$ and variance $\hat{\sigma}$ of any given point $x$ are inferred. In addition, the complete approximation tensor $\hat{\mathcal{Y}}$ is provided along with the variance tensor $\hat{\Sigma}^2 \in \mathbb{R}^{I \times J \times K}$, in which each element $\hat{\sigma}^2$ provides the variance of the corresponding $\hat{\mu}$, namely $\hat{y}(x)$. Note that GPR is computationally demanding as the training scales in $O(n^3)$ with $n$ being the number of observations. Thus, applying such a regression over the overall dataset at the cloud incurs significant computation and financial costs. As an alternative, the middleware distributes the training and inference load over the crowdsensors in an opportunistic way.

### 4.4.2 Opportunistic Aggregation

The design of the middleware is such that it favours the occurrences of aggregation among the crowdsensors over the ones of the cloud for the sake of lowering the overall computation and communication costs at the cloud, while maintaining the same data quality. To achieve this, our middleware implements an opportunistic aggregation approach. Upon a meeting (involving a shared 2D communication range) of two crowdsensors $s$ and $s'$, the middleware selects one of the two to aggregate their respective tensors $\hat{\mathcal{Y}}_s$ and $\hat{\mathcal{Y}}_{s'}$. Assuming the selected node is $s$, then $\hat{\mathcal{Y}}_s$ is updated as the aggregation of $\hat{\mathcal{Y}}_s$ and $\hat{\mathcal{Y}}_{s'}$, and $\hat{\mathcal{Y}}_{s'}$ is set to the null tensor. Then, $s$ relays $\hat{\mathcal{Y}}_s$ till it meets another crowdsensor or till the current time window $T_{+D}$ expires in which case $s$ sends the tensor to the cloud.

The crowdsensor that is the best suited to act as the relay node is the one that will meet the highest number of nodes in the future and thus minimises the occurrences of $A_c$. We consider that the respective inference quality of the tensors somehow hints on the probability of encountering other crowdsensors in the future. Evaluation further shows that it is a relevant criterion. Precisely, we use the inference quality as defined by the following loss function:

$$D(\hat{\mathcal{Y}}_s, \hat{\mathcal{Y}}_{s'}) := \frac{\| (\mathcal{M}_{s'} * \neg \mathcal{M}_s) * (\hat{\mathcal{Y}}_{s'} - \hat{\mathcal{Y}}_s) \|^2}{2 \| \mathcal{M}_{s'} * \neg \mathcal{M}_s \|^2}$$

where $\neg$ corresponds to the NOT Boolean operation and $\mathcal{M}_s$ and $\mathcal{M}_{s'}$ correspond to the mask tensors of $s$ and $s'$.

The crowdsensor with the lowest loss function performs the actual aggregation. In the following, we describe the aggregation function that crowdsensor $s$ runs provided the tensor $\mathcal{Y}_{s'}$ from $s'$, to compute the new tensor $\mathcal{Y}_{ss'}$. The aggregation function (see Eq. 4.2) sums the following:

* the sensor measurements that are only provided by $s$ omitting the interpolated measurements of $s'$: $\mathcal{Y}_s * (\mathcal{M}_s * \neg \mathcal{M}_{s'})$,

* the sensor measurements provided by $s'$ omitting the ones of $s'$ that are interpolated: $\mathcal{Y}_{s'} * (\mathcal{M}_{s'} * \neg \mathcal{M}_s)$,

* the actual sensor measurements provided by both $s$ and $s'$, which are averaged together: $\frac{n_s \mathcal{Y}_s + n_{s'} \mathcal{Y}_{s'}}{n_s + n_{s'}} * (\mathcal{M}_s * \mathcal{M}_{s'})$ with $m$ (resp. $n$) measurements denoting the amount of measurements collected by crowdsensor $s$ (resp. $s'$). Note that the above merged average is built upon a simple algebraic expression of addition that works well to fuse the measurements provided by, e.g., temperature sensor. Such a merged average should be tailored to deal with observations that do not follow an algebraic expression. This is, e.g., the case when merging the average sound level provided by mobile crowdsensors, which is the focus of the experiments.

* The two values resulting from interpolation, which are aggregated using the Generalised Product-of-Expert of GPR, as detailed below.
Overall, the aggregation function performed by crowdsensor s, provided the tensor $\mathcal{Y}_{s'}$ from $s'$, to compute the new tensor $\mathcal{Y}_{ss'}$, is the following:

$$ \mathcal{Y}_{ss'} = \mathcal{Y}_s * (\mathcal{M}_s * \neg \mathcal{M}_{s'}) + \mathcal{Y}_{s'} * (\mathcal{M}_{s'} * \neg \mathcal{M}_s) + \frac{n_s \mathcal{Y}_s + n_{s'} \mathcal{Y}_{s'}}{n_s + n_{s'}} * (\mathcal{M}_s * \mathcal{M}_{s'}) \quad (4.1) $$

$$ + (\beta_s \mathcal{Y}_s / \Sigma_s^2 + \beta_{s'} \mathcal{Y}_{s'} / \Sigma_{s'}^2) / (\beta_s \Sigma_s^{-2} + \beta_{s'} \Sigma_{s'}^{-2}) * (\neg \mathcal{M}_s * \neg \mathcal{M}_{s'}) \quad (4.2) $$

**Generalised Product-of-Expert** is a method that allows combining predicted results that have been inferred by several experts (e.g., sensor measurements and interpolation). In particular, it enables weighting the respective importance of the experts according to the reliability of their prediction. The aggregation of multiple GPR inferences is a generalised product-of-expert, which accounts for multiple inference distributions $p_s$ of an arbitrary point $x^*$. According to [33], it combines many Gaussian distributions with mean $\hat{\mu}_s(x^*)$ and variance $\hat{\sigma}_s^2(x^*)$ from any crowdsensor $s$, and it is defined based on:

$$ \hat{\mu}(x^*) = \hat{\sigma}^2(x^*) \sum_{s=1}^{m} \beta_s(x^*) \hat{\sigma}_s^{-2}(x^*) \hat{\mu}_s(x^*) $$

$$ \hat{\sigma}^2(x^*) = [\sum_{s=1}^{m} \beta_s(x^*) \hat{\sigma}_s^{-2}(x^*)]^{-1} $$

with a weighting parameter $\beta_s$ that allows tuning the relative importance of a crowdsensor $s$ according to the reliability of its prediction. Regarding the value of $\beta$, we distinguish whether the aggregation is performed at the cloud or at a crowdsensor. In the former case, the cloud considers all the incoming data as equivalent; thereby, $\beta_s = \beta_{s'} = 1$. On the other hand, the opportunistic aggregation on the move is asymmetric, as captured by the loss function $D$. Our evaluation shows that assigning a greater $\beta$ to the crowdsensor acting as the merge base (i.e., resulting in the least loss) leads to a higher aggregation accuracy.

# 4.5 Performance Evaluation

## 4.5.1 User-centric Context Inference

Our primary aim is to evaluate the accuracy of the proposed classifications and the amount of feedback required for personalization. In order to select the most efficient machine learning algorithm for the classifications, we assess candidate algorithms using both negative and positive feedback. The final solution relies on the Hoeffding Tree and uses only negative feedback hierarchically so as to keep the amount of feedback to a minimum and limit the burden put on the end user. The initial classifier is trained once on a computer and then deployed on the smartphones where it evolves.

We evaluate our updatable approach relying on the training dataset $DATASET_1$ (see Section 4.2.2), and a new testing dataset $DATASET_2$.
*DATASET*₂: Similarly to *DATASET*₁, *DATASET*₂ contains 20k instances, each embedding three labels representing the ground truth, and covers all the relevant scenarios (i.e., in/out-pocket, in/out-door and under/on-ground) uniformly. Differently to *DATASET*₁, the environment sensors, including temperature, humidity, pressure are not available on the contributing device Xiaomi Redmi Note 4, and the available sensors are from a distinct manufacturer. In addition, the user can switch off the WiFi module. Furthermore, the data gathered for *DATASET*₁ and *DATASET*₂ correspond to two different physical environments as they were collected in two different city areas and at different time period (i.e., different months).

The simulation-based experiments reported in the two next sections are run multiple times and break down into the following three steps:

1. The initial classifier, which is generated from batch training using *DATASET*₁ is imported and assessed against the entire *DATASET*₂ to provide an initial classification accuracy for *M*<sub>pocket</sub>, *M*<sub>door</sub> and *M*<sub>ground</sub> respectively.

2. The opportunism is simulated by randomly selecting 30 instances from *DATASET*₂. The 30 instances are classified sequentially using their corresponding feature vector. Then, the feedback is simulated: the inference result is compared to the ground truth label in the instance. If the classification is correct, the instance represents a positive feedback. Otherwise, it represents a negative feedback.

3. The simulated feedback is used to update the classifier. Once a classifier is updated, it is evaluated on the entire *DATASET*₂ again to provide a new classification accuracy. Thus, every feedback iteration has a corresponding classification accuracy.

*DATASET*₂ is shuffled in each run. Therefore the opportunistic feedback are randomised. The baseline is the initial classification accuracy performed by the initial classifier on *DATASET*₂ before any update.

## Assessing the online learning algorithms and the type of feedback

Since our objective is to update the classifier for a particular user, it is important to (i) investigate the amount of feedback required to achieve a high inference accuracy and (ii) identify the algorithm providing the highest accuracy with the least feedback. For *M*<sub>pocket</sub>, *M*<sub>door</sub> and *M*<sub>ground</sub>, we evaluate the three algorithms Hoeffding Tree, Naive Bayes and SGD, as selected in Section 4.2.3. For each learning algorithm in each classifier *M*, the λ parameter is configured constantly as 10 to boost the online learning process.

We have run the experiment 100 times and in each run, the volume of feedback reaching the highest accuracy along with the classification accuracy itself are recorded. Note that in this experiment, the inference and update are not hierarchical, which means that the update for each *M* is independent of each other.

Figure 4.1 shows the classification accuracy for the three algorithms over the three classifications, when both positive and negative feedback are requested from the user. We observe that the algorithms have different performance across the classifications. For *M*<sub>pocket</sub>, the accuracy of Naive Bayes does not increase at all with the volume of feedback, while both Hoeffding Tree and SGD can increase their accuracy after few feedback, and Hoeffding Tree requires less feedback to reach the highest accuracy. For *M*<sub>door</sub>, Naive Bayes shows both lower initial classification accuracy and updated classification accuracy than the other two. Hoeffding Tree is
<figure><img src="image_52.png" /><figcaption>Figure 4.1 – Maximum classification accuracy according to the amount of user feedback (positive & negative)</figcaption></figure>

more likely to improve the classification accuracy, although SGD may increase the accuracy with less feedback. For *M*<sub>ground</sub>, SGD does not show improvement on accuracy, while in most cases Hoeffding Tree provides higher accuracy than Naive Bayes after gathering feedback.

<figure><img src="image_53.png" /><figcaption>Figure 4.2 – Maximum classification accuracy according to the amount of user feedback (only negative)</figcaption></figure>

The experiments suggest that more positive feedback will be collected than negative feedback if the initial classification accuracy is above 50% and even more if the accuracy keeps increasing. Therefore, the negative feedback is always less requested, and thus the user is less prompted. Figure 4.2 analyses the maximum classification accuracy achieved when collecting only negative feedback. For all the algorithms, we observe that we can reach the highest classification accuracy with less than 15 negative feedback (half of positive and negative feedback). In more detail, for *M*<sub>packet</sub>, Hoeffding Tree reaches the highest accuracy instantly after one negative feedback, Naive Bayes does not change the accuracy at all and SGD requires more feedback to achieve the highest accuracy. For *M*<sub>door</sub>, a similar phenomenon is observed: in most cases, Naive Bayes keeps the accuracy unchanged while both Hoeffding Tree and SGD increase the accuracy following negative feedback. For *M*<sub>ground</sub>, SGD still does not provide any improvement on the classification accuracy, and in most cases, Hoeffding Tree provides a higher accuracy than Naive Bayes after receiving negative feedback. The result has shown that using only negative feedback can reduce the amount of feedback requests. Meanwhile, the increased classification accuracy has the same range as using both positive and negative feedback.

Overall, the Hoeffding Tree[81] is considered as the best candidate and used for the evaluation of the hierarchical inference and update approach detailed next. Also, we consider only negative feedback in our hierarchical approach. Note that the total number of feedback required needs be accumulated here, e.g. 15 for each and 45 in total, because the three classifiers are
updated individually using a single instance and three labels are requested every time.

## Hierarchical feedback

Instead of requesting feedback for every classifiers on each instance, the hierarchical and negative feedback is provided to one of the three classifier. Our hierarchical approach is evaluated on *DATASET*₂, assessing the classification accuracy according to the amount of negative feedback. We performed 500 experimental runs.

<figure><img src="image_54.png" /><figcaption>(a) Accuracy is better 99% of the time for $M_{pocket}$</figcaption></figure>

<figure><img src="image_55.png" /><figcaption>(b) Accuracy is better 86% of the time for $M_{door}$</figcaption></figure>

<figure><img src="image_56.png" /><figcaption>(c) Accuracy is better 71% of the time for $M_{ground}$</figcaption></figure>

Figure 4.3 – Improvement of the binary H TREE classification accuracy according to the number of (hierarchical and negative) feedback with $\lambda = 10$

Figure 4.3 provides the classification accuracy according to the amount of (negative and hierarchical) feedback. Among the 13 (negative and hierarchical) feedback, at most 9 feedback are related to $M_{pocket}$, 12 to $M_{door}$ and 13 to $M_{ground}$. The classification accuracy gets better 99%, 86% and 71% of the time for $M_{pocket}$, $M_{door}$ and $M_{ground}$, respectively. In such a case, the mean classification accuracy for $M_{pocket}$ and $M_{ground}$ is quite high and much better comparing to the initial accuracy, while the mean enhanced accuracy for $M_{door}$ is quite high, but is closer to the initial accuracy. While the accuracy in $M_{pocket}$ remains stable, the classification accuracy for $M_{door}$ and $M_{ground}$ increases and then decreases a little before reaching maximum 91% and 90%, respectively. We undertook additional experiments that are not plotted here. These experiments showed that when the parameter $\lambda$ is larger, the accuracy is more often better, but the runtime cost is also higher. For instance, with $\lambda = 15$, the accuracy is better 100%, 88% and 71% of the time for $M_{pocket}$, $M_{door}$ and $M_{ground}$, respectively. Overall, requesting only negative feedback reduces the amount of feedback requested from the end user while the hierarchical approach requires even less feedback. Indeed, 13 (negative and hierarchical) feedback are requested rather than 90 (negative and positive, non hierarchical) feedback, or 45 (negative only, non hierarchical) feedback.

We perform 500 experiments so as to evaluate our hierarchical approach using the $F_1$ score, which is a measure of a test's accuracy considering both the precision and the recall of the test. The best (resp. worst) value attained by $F_1$ score is 1 (resp. 0). Precisely, the initial classifier trained with $DATASET_1$ is evaluated by simulating negative feedback, leveraging $DATASET_2$.

Figure 4.5 provides the $F_1$ score according to the number of (negative and hierarchical) feedback. Among the 15 (negative and hierarchical) feedback, at most 4 feedback are related to $M_{pocket}$, 12 to $M_{door}$ and 15 to $M_{ground}$. The $F_1$ score gets an enhancement 100%, 90% and 71% of the time for $M_{pocket}$, $M_{door}$ and $M_{ground}$, respectively. The enhancement of $F_1$ score is most significant for $M_{pocket}$ and least significant for $M_{door}$. Overall, 8 hierarchical feedback can provide high $F_1$ scores for all the three classifiers.
<figure><img src="image_57.png" /><figcaption>(a) $F_1$ score is better 100% of the time for $M_{pocket}$</figcaption></figure>

<figure><img src="image_58.png" /><figcaption>(b) $F_1$ score is better 90% of the time for $M_{door}$</figcaption></figure>

<figure><img src="image_59.png" /><figcaption>(c) $F_1$ score is better 71% of the time for $M_{ground}$</figcaption></figure>

Figure 4.4 – Improvement of the binary H TREE $F_1$ score according to the number of (hierarchical and negative) feedback with $\lambda = 10$

Hierarchical classifiers versus multi-class classifier

We can infer the context by either performing a single multi-class classification or by using three
binary hierarchical classifications. The multi-class classifier distinguishes 8 classes as combina-
tion of in/out-pocket in/out-door and under/on-ground. To compare the multi-class classifier
with our hierarchical classifiers solution, we perform 100 experiments (because many more up-
dates are needed compared to the hierarchical way), using the same settings as in Section 4.5.1.

<figure><img src="image_60.png" /><figcaption>(a) Multi-class H TREE classification accuracy according to the amount of (negative) feedback</figcaption></figure>

<figure><img src="image_61.png" /><figcaption>(b) Single multi-class H TREE versus hierarchical binary class H TREE</figcaption></figure>

Figure 4.5 – Improvement Multi-class H TREE classification accuracy and Runtime for single multi-class H TREE versus hierarchical binary class, with $\lambda = 10$

As illustrated in Figure 4.5a, the initial and enhanced classification accuracy of a multi-class
classifier is much lower (around 2 times lower) compared to the ones of hierarchical classifiers
(Figure 4.3). The enhanced accuracy is on average always lower than 45%. Besides, the multi-
class classifier requires more feedback over all experiments (28 feedback are required over 30
feedback). Another drawback of the multi-class classifier is that the user has to select among 7
options as a feedback rather than answering "yes or no" to a simple and specific question.

Meanwhile, we performed 500 experiments to compare in Figure 4.5b the inference and
update runtime of multi-class classifier and hierarchical classifiers. Our hierarchical solution is
characterised by a much lower update runtime (median, mean and majority) compared to multi-
class classifier. For inference, hierarchical classifiers induce a slightly lower runtime comparing
to the multi-class classifier because the hierarchical classifiers do not run all classifications every
time.

Overall, the advantages of using a hierarchical classifiers (rather than a multi-class classifier)
are many fold: (1) Using a classifier for each context element ensures that the classification
accuracy remains high for each of them. (2) Each classifier relies on the vector of the most
relevant features, resulting in a reduced inference and update runtime. (3) A classifier can
easily be added/removed/replaced when a new context element needs to be managed for the
benefit of the upper layer crowdsensing-based application. (4) Our hierarchical classification
limits the number of classifications that is triggered, e.g., the in-/out-door context is assessed
only if the device is outside the pocket. (5) The user feedback required for the personalisation
of the hierarchical classifiers is simple and reduced.

Power consumption and accuracy

<figure><img src="image_62.png" /><figcaption>Figure 4.6 – Classification accuracy and power consumption</figcaption></figure>

Figure 4.6a presents the power consumption of the environmental sensors embedded in the Crosscall Trekker-X3 phone and of the networking modules<fnref n="2" />, which together serve to gather the features. We observe that the light, temperature, pressure and humidity sensors are not power-consuming, contrary to GPS module, proximity sensor and WiFi component. In the following, we concentrate on evaluating the impact of disabling these three power-consuming features. We already considered the impact caused by the unavailability of environmental sensors in *DATASET*₂.

DATASET₃: This dataset contains a training dataset (20k instances) and a testing dataset (20k instances): a Samsung Galaxy S4 GT-i9505 smart phone is used to collect DATASET₃ for the initial classifier and a modified version *DATASET*₃' is used for evaluation. In *DATASET*₃', the proximity sensor, the GPS module and the WiFi component are disabled on the device, thus the three features from them are unavailable.

Again, we simulated the hierarchical inference and update by 500 experimental runs. Figure 4.6b presents the classification accuracy for *M*<sub>pocket</sub>, *M*<sub>door</sub> and *M*<sub>ground</sub>, when all the features are available, and when the GPS module, proximity sensor and WiFi component are disabled.

<footnote n="2">2. https://source.android.comdevices/tech/power/values.html</footnote>
When the GPS module, proximity sensor and WiFi component are disabled, the classification accuracy diminishes to respectively 50%, 40% and 20%. After getting feedback, the mean classification accuracy increases by 10%, 8% and 1% respectively, while the maximum classification accuracy after feedback reaches 74%, 99% and 98% respectively. Overall, our approach personalises the classifiers and deals with the disabled power-consuming features according to user preference.

Our implementation requires 100MB of memory on a Nokia X6 Android 9 smartphone (Qualcomm Snapdragon 636) and leads to an increase of 5% of the CPU. The inference and update of contexts necessitates around 3MB of memory and an increase of 5% of the CPU. We evaluate the computation runtime of the entire inference and update phases. The inference runtime is on average 0.2ms, 0.1ms and 0.1ms for $M_{pocket}$, $M_{door}$ and $M_{ground}$, respectively, while the runtime necessary to update the model is 7.3ms, 7.5ms and 10.0ms on average (with $\lambda = 10$).

### 4.5.2 Group-based Collaborative Crowdsensing

We evaluate the performance of our approach, assessing: (i) the impact on the power consumption of the device running the *BeTogether* middleware in the background, and (ii) the potential benefit of the collaborative crowdsensing at the edge from the standpoint of data quality and communication cost based on a one-year dataset obtained from the Ambiciti application for urban pollution monitoring. We note that due to privacy and commercial concerns, the Ambiciti company shared the data with us within the framework of a collaboration agreement while data cannot be released openly.

#### Power consumption

<table><caption>Table 4.6 – Active power of components for Nexus 5X</caption><thead><tr><td>WiFi TX</td><td>WiFi Scan</td><td>Cellular TX</td><td>Light Sensor</td><td>GPS RX</td></tr></thead><tbody><tr><td>173 mA</td><td>2 mA</td><td>186 mA</td><td>0.2 mA</td><td>60 mA</td></tr></tbody></table>

We estimate theoretically the power consumption on a single crowdsensor; Table 4.6 shows the power of the main components used in our crowdsensing middleware. The reference values are for the Google Nexus 5X smartphone, as provided by the Android OS (https://source.android.com/devices/tech/power/values) according to the power profile provided by the manufacturer. Herein, we select the light sensor, which involves a power consumption comparable to that of most sensors [52, 96]. Note that the power consumption associated with the transmission depends on the transmission duration, which increases linearly with the packet size. We assume that cellular and WiFi Direct communications have the same transmission speed.

Figure 4.7 shows the power consumption of a crowdsensor working individually at various sensing and upload frequencies. The upload is the most energy-demanding and the energy consumption can be reduced by lowering the upload frequency. As a comparison, Figure 4.8 provides the power consumption of the various nodes contributing to collaborative crowdsensing with regards to a high sensing frequency (every 1 minute) and upload frequency (every 10 minutes) for the individual case. Results show that the proxy always consumes the most energy due to the cellular transmission that takes place with the cloud, followed by the coordinator that communicates with the nearby devices to distribute the tasks. Other group participants
<figure><img src="image_63.png" /><figcaption>Figure 4.7 – Varying individual crowdsensing frequencies & Power consumption</figcaption></figure>

<figure><img src="image_64.png" /><figcaption>Figure 4.8 – Collaborative crowdsensing & Power consumption</figcaption></figure>

<figure><img src="image_65.png" /><figcaption>Figure 4.9 – Distribution of the still duration</figcaption></figure>

consume much less energy compared to the individual case, even-though this consumption includes the cost related to discovery and D2D transmission to the coordinator.

## Dataset-driven evaluation

**Dataset** We leverage a dataset produced by the Ambiciti (formerly called SoundCity) cloud-based crowdsensing application available on Google Play since 2015 and on Apple AppStore since 2016 (see http://ambiciti.io). Ambiciti monitors the noise pollution using the smartphone's microphone [167]. Our dataset contains 946,573 observations gathered both indoors and outdoors in Paris over the year 2017 from 550 crowdsensors, where the average uploading duty cycle is around 5 minutes. Each observation provides: the uploading time-stamp, the location and (anonymized) ID of the contributing device, the noise level and its measurement bias, a description of the user activity (still, on foot, on a bicycle, in a vehicle, unknown), and whether the device is in/out-pocket (based on proximity). With 550 crowdsensors for the all of Paris, the dataset is sparse. Hence, it does not provide the most suitable case for opportunistic collaboration at the edge. Still, this allows us to assess the effectiveness of *BeTogether*, even with a sparse deployment.

<figure><img src="image_66.png" /><figcaption>Figure 4.10 – Comparison of grouping strategies</figcaption></figure>

<figure><img src="image_67.png" /><figcaption>Figure 4.11 – Distribution of group properties</figcaption></figure>

<figure><img src="image_68.png" /></figure>

<figure><img src="image_69.png" /><figcaption>Figure 4.12 – Lifetimes of collaborative groups</figcaption></figure>

**Analyzing the crowdsensor behavior** We first analyse the stability of the crowdsensors' context, as used for the configuration of groups, where we only consider the User Activity (UA). Indeed, the Physical Environment (PE) value is limited to the in-pocket case in the dataset, which only influences the sensor utility $u_s(i)$. The context is assessed daily. Starting with the initial location *l* of any crowdsensor *i* within the dataset, we consider that *i* changes group when
it reaches another location *l*′ that is more than the D2D range away from *l*, and repeatedly so
with *l*′ as the new reference location.

Figure 4.9 then shows the distribution of the duration of the crowdsensor staying within the above estimated group for all the crowdsensors of our dataset according to the device’s location: it varies from 10 minutes to 60 minutes where we recall that we set D<sub>min</sub> = 5 minutes as the minimum duration of the group. Hence, many crowdsensors remain at the same location long enough to group.

Figure 4.10 further compares the three following grouping strategies in terms of the average number of messages sent per crowdsensor daily so as to discover nearby crowdsensors: *periodic* (after every upload) that is the approach found in related work, *on-demand* (detected by WiFi Direct), and *context-aware* that accounts for the crowdsensors’ activities. In average, the amount of traffic generated by the on-demand strategy is 80.810% lower than the periodic approach, and the one of our context-aware grouping is 21.844% lower than the on-demand approach.

<figure><img src="image_70.png" /><figcaption>Figure 4.13 – Impact on collected data quality</figcaption></figure>

<figure><img src="image_71.png" /><figcaption>Figure 4.14 – Impact on uploaded data traffics</figcaption></figure>

<figure><img src="image_72.png" /><figcaption>Figure 4.15 – Impact on overall battery consumption</figcaption></figure>

**Analyzing the efficiency gain of grouping** In order to find the clusters of crowdsensors that are within D2D range (at 10m (re-scaled) away) from each other, we rely on the DBSCAN algorithm [58], which handles clusters that are arbitrarily shaped and that are of varying density. According to our parameter $\delta = 4$, that configures groups of size 5 and more, Figure 4.11 shows the distribution of the resulting group sizes in our dataset, with 79% of the groups being immobile.

Figure 4.12 further compares the average duration of the identified groups depending on whether the context is accounted for or not. Interestingly, results show that even in real life scenarios (including both immobile and mobile groups, not considering only still grouping as in Figure 4.9), our context-aware grouping finds groups of longer duration, which is up to 3.256 times of non context-aware grouping. As groups grow, the difference between a context-aware and non-context-aware approaches lowers because the likelihood of grouping co-located nodes having the same context gets higher. A decrease of lifetime is observed for groups of 12 members and more, which is partly due to the sparsity of our dataset and also the higher probability of members moving away from the group.

Although the crowdsensing data of our dataset is very sparse in time and space, the context-aware collaborative crowdsensing at the edge still brings benefit in terms of data quality and global resource consumption. It is especially efficient as the size of the group grows. Figure 4.13 shows that the *context-aware* collaborative approach delivers the best data quality: the collected measurement bias is reduced by up to 615% (resp. 407%) compared to an individual (resp. non-context-aware collaborative) crowdsensing approach. This is because of the selective sensing of *BeTogether* within each group, leading to the collection of the most accurate observations rather
than a simple average of the observations (non-context-aware collaborative crowdsensing) or than all the raw data (individual crowdsensing).

As shown in Figure 4.14, the amount of data that a collaborative and context-aware approach uploads to the cloud is reduced by up to 197% compared to both the individual and (non-context-aware) collaborative crowdsensing approach. There are two reasons for this: first, collaborative crowdsensing uploads only the aggregated data (i.e., concatenated hash tables) via the group proxy rather than uploading the raw data supplied by each crowdsensor (individual crowdsensing). Second, our context-aware collaboration also filters out the data that are of low-quality and that are collected in-pocket, which reduces the amount of data aggregated and uploaded to the cloud.

Finally, Figure 4.15 focuses on the power consumed per hour, which is associated with both WiFi Direct transmission (assuming that all the tasks are distributed) and cellular transmission: the power is reduced by up to 181% (resp. 183%) compared to individual (resp. non-context-aware collaborative) crowdsensing approach. Overall, these results show that the collaboration achieves a better data quality at a lower sensing and transmission cost when the group is larger because the tasks can be assigned to more devices, resulting in less task duplication and better context-aware filtering and aggregation.

### 4.5.3 Interpolation and Aggregation

In the following evaluation, the experiments are run either on a DELL Precision 7520 workstation - § 4.5.3 as a centralised server and § 4.4 for simulation, or on Android smartphones - § 4.5.3 as end-device testbed.

#### Accuracy metrics

We use the *Mean Absolute Percentage Error* (MAPE) and *Root Mean Square Error* (RMSE) to evaluate the accuracy of the interpolated and aggregated tensors. Given the observation data tensor $\mathcal{Y}$, the approximation data tensor $\hat{\mathcal{Y}}$ and the ground truth mask tensor $\mathcal{M}$ (indexing useful values), MAPE is defined as:

$$MAPE(\mathcal{Y}, \hat{\mathcal{Y}}, \mathcal{M}) := \frac{100\%}{\|\mathcal{M}\|^2} \sum \frac{\mathcal{M} * |\mathcal{Y} - \hat{\mathcal{Y}}|}{\mathcal{M} * \mathcal{Y}}$$

While RMSE is defined as:

$$RMSE(\mathcal{Y}, \hat{\mathcal{Y}}, \mathcal{M}) := \sqrt{\frac{\|\mathcal{M} * (\mathcal{Y} - \hat{\mathcal{Y}})\|^2}{\|\mathcal{M}\|^2}}$$

To compute MAPE and RMSE, we run 100 training rounds followed by tests. At each round, both training and evaluation sets are randomly shuffled, where: For the interpolation, 70% of the dataset is used for training (i.e., as actual observations to complete the tensor) and 30% to test (i.e., to assess the estimated values against the ground truth). For aggregation, the entire approximation tensor is used for the evaluation.

#### Interpolation evaluation

Figures 4.16 and 4.17 compare the robustness of the three inference strategies that are commonly used to interpolate physical phenomena: Ordinary kriging with Gaussian variogram model (OK-Gaussian), CP decomposition with Alternating Least Square (CP-ALS), and Gaussian Process
<figure><img src="image_73.png" /><figcaption>Figure 4.16 – Interpolation accuracy - MAPE</figcaption></figure>

<figure><img src="image_74.png" /><figcaption>Figure 4.17 – Interpolation accuracy - RMSE</figcaption></figure>

<figure><img src="image_75.png" /><figcaption>Figure 4.18 – Interpolation response time</figcaption></figure>

Regression with Matern kernel (GPR-Matern). The interpolation is performed at the same PC (without involving any aggregation), using the dataset from which we selected on the day during which the largest amount of crowdsensing data were collected. The same experiments were run using the whole dataset and the same trends were observed. In the figures, the box corresponds to the interquartile range, the orange line is the median and the green triangle is the mean. At first sight, OK-Gaussian seems to be accurate and hence promising, given the low MAPE and low RMSE interquartile range and median. However, some wrong inferences lead to abnormal values as illustrated by high MAPE and RMSE mean values of 16% and 47, respectively. Similarly but to a lower extent, CP-ALS shows some abnormal RMSE. Instead, GPR-Matern provides both an accurate and robust inference: stable MAPE and RMSE without outliers —hence characterised by the lowest variance— is observed.

Figure 4.18 shows the response time of the three interpolation approaches. We run the experiments over the 365 days of our dataset, where the number of observations varies everyday. The response time of CP-ALS ($R = 1$) is constant in $O(RIJK)$ regardless of the number of available observations since the computation applies on the entire fixed-size tensor. Both OK-Gaussian and GPR-Matern have a time complexity in $O(n^3)$ with $n$ being the number of observations used to fit the model. The response time of GPR-Matern is lower than OK-Gaussian, and below CP-ALS when the number of observations is less than 2800. Note that in our dataset, the number of observations collected by crowdsensors daily remains lower than 1500. Overall, GPR-Matern is the most efficient in terms of accuracy and robustness, while its response time is also relatively lower.

We further evaluated the efficiency of the three interpolation methods in terms of memory consumption. GPR-Matern consumes the least memory: around 3.114MB, with a variance of 1.718. While the memory consumption associated with CP-ALS (resp. OK-Gaussian) is of 3.258MB with a variance of 0.422 (resp. 4.644MB with a variance of 1.437). Note that the memory consumption is stable and does not depend on the number of observations since our approach always uses a fixed-size tensor that is filled with zeros in the absence of observations.

Focusing on GPR, we assessed the accuracy (Figures 4.19 and 4.20) and associated response time (Figure 4.21) of the following kernels: constant, RBF, rational quadratic, and Matérn. The rational quadratic and Matérn kernels are the most accurate, while the former slightly outperforms the latter. However, the response time of the quadratic kernel is twice as much as that of the Matérn kernel. We therefore consider only GPR with Matérn kernel in our solution.

## Aggregation simulation-based evaluation

The distributed aggregation encompasses several tasks: each crowdsensor converts the sensing data into a tensor, interpolates and potentially merges the tensors when meeting another.
<figure><img src="image_76.png" /><figcaption>Figure 4.19 – Kernel accuracy
- MAPE</figcaption></figure>

<figure><img src="image_77.png" /><figcaption>Figure 4.20 – Kernel accuracy
- RMSE</figcaption></figure>

<figure><img src="image_78.png" /><figcaption>Figure 4.21 – Kernel response
time</figcaption></figure>

We assess the performance of the following distributed aggregation methods using our 1-year dataset:

* **Iterative aggregation** is a theoretical and sequential case in which the aggregation starts at the first crowdsensor that aggregates its tensor with the next crowdsensor and the aggregation process repeats with the following crowdsensors until the last crowdsensor is reached. This is the ideal case for which we ignore the actual locations of the crowdsensor.

* **Stochastic aggregation** represents the real-life scenario: an aggregation occurs when at least two crowdsensors meet as detected using the location and time proximity in the dataset. The aggregation process thus depends on the mobility of the contributing users. Upon a meeting, the merge base is selected randomly and $\beta = \beta' = 1$ for the generalised product-of-expert. Ultimately, all data are uploaded to and merged at the cloud, either directly or via a relay depending on the peer meetings.

* **Opportunistic aggregation** is similar to the above stochastic aggregation with the exception of the selection of the merge base and the chosen $\beta$ values. Here, we set $\beta_s = 1.3$ and $\beta_{s'} = 0.7$ for crowdsensor $s$ with lower $D$ and crowdsensor $s'$ with higher $D$ respectively.

The above methods are further compared to the cloud-centric solution where the cloud server (DELL workstation in our experiment) collects the sensing data and performs the interpolation based on the whole dataset.

<figure><img src="image_79.png" /><figcaption>Figure 4.22 – Aggregation accuracy - MAPE</figcaption></figure>

<figure><img src="image_80.png" /><figcaption>Figure 4.23 – Aggregation accuracy - RMSE</figcaption></figure>

<figure><img src="image_81.png" /><figcaption>Figure 4.24 – Impact of $\beta$ setting - MAPE</figcaption></figure>

Figures 4.22 and 4.23 provide the MAPE and RMSE of the three above distributed aggregation approaches and of the centralized one. As expected, the centralized approach provides the most accurate inference: The MAPE mean equals 8.5% and the MAPE median is 8.1%;
the RMSE mean equals 10.8 and the RMSE median is 10.6. The accuracy of the distributed aggregations are quite similar, with a MAPE of around 12.5% with a median of 12.5% and a RMSE mean of 15.6 with a median of 15.8. In particular, our opportunistic aggregation is comparable to the centralised approach (e.g., the MAPE accuracy difference is 4% lower than the centralised approach). It has mean and median MAPE of 12.0%; a RMSE mean of 15.0 and a RMSE median of 15.2. Overall, our approach is characterised by very slight decrease of the accuracy compared to centralised aggregation.

<figure><img src="image_82.png" /><figcaption>Figure 4.25 – Impact of $\beta$ setting - RMSE</figcaption></figure>

<figure><img src="image_83.png" /><figcaption>Figure 4.26 – Simulation response time</figcaption></figure>

<figure><img src="image_84.png" /><figcaption>Figure 4.27 – Cloud server response time</figcaption></figure>

Figures 4.24 and 4.25 compare different weighting configurations ($\beta_s, \beta_{s'}$) for crowdsensor $s$ and $s'$. For three of the pairs, we manually set their values depending on the loss function $D$, i.e. the lower loss has a higher weight. For the fourth one, we set $\beta_s = 2\frac{n_s}{n_s+n_{s'}}$ using the ratio depending on the history number of aggregations $n$. The results show that assigning a higher weight to the crowdsensor with the lower loss function slightly increases the overall accuracy aggregated at the cloud.

Figure 4.26 shows the response time associated with the entire procedure including data pre-processing, interpolation and aggregation, with the simulation being run on the server. We observe that the centralised aggregation response time is lower than the accumulated response time of the distributed aggregation schemes. However, in the distributed approach, the cloud does not perform any interpolation, thus the centralised interpolation requiring a high response time is eliminated. As illustrated in Figure 4.27, the response time associated with the aggregation at the cloud server significantly increases when the number of crowdsensors gets high. Instead, when the interpolation and aggregation are mainly performed by crowdsensors, the cloud response time is almost negligible regardless of the number of crowdsensors. In addition, the storage requirement is minimised on cloud because the data tensor size is always unchanged when aggregating new incoming data.

<figure><img src="image_85.png" /><figcaption>Figure 4.28 – Directly uploaded messages</figcaption></figure>

<figure><img src="image_86.png" /><figcaption>Figure 4.29 – P2P forwarded messages</figcaption></figure>

<figure><img src="image_87.png" /><figcaption>Figure 4.30 – On-device response time</figcaption></figure>
Figures 4.28 and 4.29 compare the amount of traffic uploaded to the cloud and relayed among the crowdsensors. The traffic is evaluated in terms of the number of actual aggregations. As expected, distributed aggregation reduces the amount of traffic uploaded to the cloud and hence the cellular network occupancy is kept to a minimum. In particular, our opportunistic aggregation drastically reduces the cloud uploading by 54.2% compared to the stochastic aggregation. A portion of the traffic sent to cloud is replaced by the traffic forwarding among crowdsensors; there are more aggregations and thus more P2P messages generated when the number of crowdsensors increases. This result also validates our estimation that crowdsensors with better inference quality tend to have more meetings and thus relay opportunities.

Aggregation testbed-based evaluation

Using Android smartphones, we empirically assess the performance associated with the proto-
type in terms of response time and energy consumption. We conduct the experiment using our
1-year dataset as data input.

<figure><img src="image_88.png" /><figcaption>Figure 4.31 – Energy con-
sumed</figcaption></figure>

<figure><img src="image_89.png" /><figcaption>Figure 4.32 – Energy con-
sumed by network</figcaption></figure>

<figure><img src="image_90.png" /><figcaption>Figure 4.33 – Cloud monthly financial cost</figcaption></figure>

Figure 4.30 shows the interpolation response time depending on the number of observa-
tions, and the aggregation response time depending on the number of aggregations, where the
experiment is run on a SAMSUNG GALAXY S7 smartphone. Note that the figure shows no
more than 500 entries, which is in practice a very high number of observations collected by
a crowdsensor daily. As expected, interpolation is computationally intensive compared to ag-
gregation, whose response time is comparatively negligible: the interpolation takes a couple of
minutes when the number of observations is greater than 500, while the aggregation takes less
than 100 seconds for a number of aggregations below 500 and for a number of observations
per crowdsensor varying from 1 to 500. When we consider 500 observations, the interpolation
consumes the most energy with 88mAh, and the aggregation consumes only 2mAh. Figure 4.31
shows the energy consumed by a smartphone that implements our opportunistic aggregation
when the P2P meeting frequency varies: the more frequent is the aggregation, the more energy
is consumed. Recall that each crowdsensor executes the interpolation only once and it can be
piggyback, e.g., executed when the smartphone is charged during night. Nevertheless, in prac-
tice, the related energy consumption gets limited because the crowdsensor usually has already
relayed/aggregated its data before meeting ≈ 10 crowdsensors for a single day.

In order to evaluate the power consumption due to communication, we rely on the power
profile of a LG NEXUS 5X smartphone provided by the manufacturer. Assuming a constant
bandwidth, the WiFi transmission consumes 1.72mAh while the cellular transmission consumes
1.85mAh power. We estimate the energy consumption associated with all crowdsensors. Figure
4.32 shows the energy consumption associated with the local P2P traffic as well as the cellular
Internet traffic. The energy is reduced by replacing uploads with P2P relays. When the P2P
bandwidth is higher than the cellular bandwidth (e.g., two times in figure), the advantage is more significant. Furthermore, the local P2P traffic is not only less costly in terms of energy aspect but also in terms of budget.

## Impact on the financial cost

We estimate the financial cost associated with our crowdsensing system, using the Google Cloud Platform (GCP, https://cloud.google.com/products/) as an example of cloud platform. GCP provides the following key services: *Cloud IoT Core* is responsible for connecting the cloud to the IoT devices and establishing a two-ways communication. Upon the reception of a packet, the *Cloud Pub/Sub* service creates and delivers an event notification to *Cloud Functions* that implements basic operations (e.g., average, maximum, minimum) needed to pre-process the data. *BigQuery* is used to temporarily store the pre-processed data during the aggregation and interpolation. *Compute Engine* runs a virtual machine that performs the advanced computation (e.g., interpolation and aggregation). *Cloud Bigtable* is a NoSQL database that stores the resulting aggregated and interpolated sensing data.

The use of each of the above services is priced: for a detailed description, one may refer to https://cloud.google.com/pricing/list. In a nutshell, the price depends on the amount of network traffic received/sent, the amount of storage needed, and the load associated with the computation (e.g., number of pre-processing functions invoked and response time associated with the interpolation and aggregation). Figure 4.33 shows the monthly financial cost associated with running different crowdsensing in GCP, assuming that each crowdsensor sends a 2MB packet everyday. The cost associated with the centralised approach increases linearly because the number of uploads and the computation involved to interpolate the phenomena are both high. Instead, the costs of the stochastic and opportunistic approaches remain low because communication toward the cloud is reduced and only lightweight aggregation is performed at the cloud. Our opportunistic aggregation outperforms the stochastic approach because we further reduce the computing load on the cloud.

## 4.6 Conclusion

One of the major benefits of crowdsensing is the possibility to monitor environmental phenomena at an urban scale, simply leveraging the abundance and capacity of people's smartphones. However, as the number of contributors grows, the increasing number of observations that the crowdsensing systems must process gets challenging: the high network and financial cost associated to a cloud-centric system hinders the widespread deployment of crowdsensing, and the high computational cost due to the large amount of data makes the modelling of the environmental phenomenon intractable.

We tackle the above issues by exploiting the increasing computing capacity of today's smartphones, that is, we enforce a collaboration strategy at the edge so as to enhance the quality of the data transferred to the cloud while reducing the related communication cost and resource consumption. For this purpose, we introduce a set of utility functions that assess to which extent a device should carry out a given crowdsensing task, while achieving a trade-off between the benefit for all (for the whole group) and the related cost for the device.

Furthermore, we distribute the interpolation and aggregation associated with the sensing data at the powerful end devices. To do so, we introduce a middleware that runs on the smartphone to capture complex and potentially non-linear relationships among the collected observations across both space and time by relying on Gaussian Process Regression and 3D tensors.
Then, the resulting tensors are opportunistically combined together following a stochastic pro-
cess based on the physical encounters of people. Rather than applying a naive combination
(e.g., averaging) of the tensors that would actually degrade the quality of the sensing data, our
solution performs a Product-of-Expert on the inference. The benefit our approach is threefold:
(i) a selected crowdsensor (i.e., expert) may independently establish a very precise interpolation
of the regions covered by a crowdsensor group; (ii) the aggregation resulting from the Product-
of-Experts is sharper than any of the individual tensor and renders much more tractable the
establishment of the overall tensor; and (iii) the computation achieved on the device is energy-
efficient. Indeed, the evaluation using simulation and prototype implementation, together with
a real-world dataset shows that our approach significantly reduces the transmission to, and the
computing resource consumed on, the infrastructure server, without compromising the overall
data accuracy.
<figure><img src="image_91.png" /></figure>
# Information centric Networking

## 5.1 Context and Motivation

IoT is an ever growing ecosystem in which the *Things* (e.g., smartphones, sensors, actuators, RFIDs, just to name a few) continuously exchange some data streams with other interested *Things*, applications and users spread across the Internet. IoT is an event driven ecosystem in the sense that reactions (e.g., actuations, decisions) are triggered after an event or a series of events is captured by the event producer (e.g., a sensor). Events correspond to some changes in the state (e.g., a temperature increase, an excessive sound level) or simply an update. Relying on event notification permits to minimise the need of integration among *Things* and applications. As a result, *Things* are easily deployed and operate independently, as needed.

The IoT presents a number of challenges, especially in regard to routing and aggregation of a continuous flow of information that is exchanged among things. Thus, our attempt is to support an efficient communication between Things/users across heterogeneous networks by adopting an information-centric philosophy that heralds a new communication style, in which the data flow is governed by both the Things/users interests and the data content. More specifically, we build upon the publish/subscribe paradigm in which event producers send notifications to subscribers who have previously expressed their interests. The degree of expressiveness, which permits the users to describe their interest, is of critical importance and greatly differs from one publish/subscribe system to another. This leads to the categorisation of these systems into the two following classes: Topic- versus content-based publish/subscribe systems.

With topic-based pub/sub systems [179, 180, 184, 182], a subscriber identifies a topic of interest (i.e., a keyword) and is thereby endowed with a low level of expressiveness. Each individual topic can be viewed, and thereby abstracted, as a separate channel /pipe, which is further mapped to a interested group of subscribers towards whom a notification is forwarded. Partitioning the topic space - and thereby the event space - into sub-topics leads to the creation of separate groups in which subscribing is equivalent to becoming a group member, with one group defined per (sub)topic. Due to the simplicity and ease of use of topic-strings, topic-based pub/sub systems became widely employed as part of enterprise and message-oriented middlewares [158, 159, 109, 40] and are now the cornerstone of modern stream analytic pipelines [71, 153]. Still, despite their effectiveness topic-base pub/sub systems suffer from a lack of expressiveness, meaning that that many irrelevant notifications are disseminated.

*Content-based publish/subscribe systems* overcome the limitations of topic-based publish/subscribe system by improving the expressiveness of subscriptions. A subscription is composed of a set of filters (e.g., "String function = temperature sensing", "String unit = Celsius", "Integer priority > 1") that are further used to match event notifications. Thus a subscriber can easily combine several filters applying to notification attributes [34, 155, 13, 84, 124]. However this expressive subscription process comes with a more sophisticated and fine-grained filtering, which increases the broker workload. Indeed, the proposed filtering algorithms (§5.2) scale poorly (i.e., sublinearly) with an increase of the event notification size (i.e., number of attributes) and the
<figure><img src="image_92.png" /><figcaption>Figure 5.1 – Overview of the routing structure over which routers propagate the subscriptions and event notifications</figcaption></figure>

subscription size (*i.e.*, number of filters), not to mention the volume of event notifications. Thus many of the approaches to scale the Publish/Subscribe system share the overheads of subscription management (matching, update) and event filtering among distributed routers. Whilst a variety of distributed notification systems have been proposed, a significant portion [34, 16] assume a pre-established organisation, which is not a realistic model for large-scale and geographically distributed networks.

Within this work we focus our attention on content-based publish/subscribe systems. Our aim is to render our content-based publish/subscribe system accessible by/from any *Things* over a wide-area network while overcoming some of the limitations of distributed content-based publish/subscribe systems, including: (i) the lack of robustness and flexibility [70], and (ii) the computing-gluttony associated with the fine-grained filtering. Our primary concern is hence to define – from design to the implementation – an effective strategy for dynamically organising the delivery of event notifications so that it scales and tolerates failures. Another key goal is to lighten the filtering process that takes place during the event notification delivery, without compromising the expressiveness of the subscriptions and the fine-grained nature of the filtering.

The publish/subscribe system we propose is non-centralised so as to avoid using a central access point that may become a bottleneck. The system self-organises in a cluster-based hierarchical structure that self-adjusts upon link/device failures and device arrival and departure while ensuring strict control over the underlying structure. Conceptually, cluster heads serve as routers (Figure 5.1) and forward event notifications (as well as (un)subscriptions) to the next routers, towards their final destination(s). The advantage of a hierarchical structure is threefold. First, the cluster-based structure enables a short and situation-aware control loop, in which cluster members (a.k.a *Things*) can individually adapt and react in real-time to local events. Second, the hierarchical structure supports the aggregation [115], subsumption [85] and correlation of event notifications and hence alleviates the traffic load. Higher-level decisions can also be made on the basis of a macro-view/ state through an extended and hierarchical control loop.

The key activity of a router is to convey the event notifications and the related (un)subscriptions. In order to filter event notifications and (un)subscriptions (§ 5.3) the router maintains a repository containing the received subscriptions. It is noteworthy that most routers get unnecessarily overloaded because they perform the same filtering task *i.e.*, each router goes through the repository looking for the same subscription(s) (*a.k.a.* filter(s) to apply) as its neighbours. In order to alleviate the filtering process we introduce (§ 5.4) a new, compact way of representing filters that must be applied and that form a subscription. We rely on the Bloom filter [25], which corresponds to a compact approximation supporting probabilistic membership queries. Bloom filters intuitively introduce small space overheads when stored and conveyed due to their compact nature. In addition, Bloom filters save a substantial amount of time performing
the membership test that takes place during the notification/(un)subscription forwarding. The probabilistic nature of the Bloom filter means that false positives may eventually occur while there are no false negatives.

This constitutes a classical trade-off between space (i.e., storage and communication), time (i.e., computation) and accuracy (false positives): increasing the performance of one of the three factors is done at the expense of the others. We formalise the problem of approximating and summarising the subscription filters into Bloom filters as an optimisation problem (§ 5.5). In particular we determine the degree of approximation desired and thereby a suitable size of Bloom filter so that the probabilities of false positive/negative always remains negligible. We further introduce a lossy compression algorithm that conveniently compresses the Bloom filter when needed. As a complement, we aim at improving the search algorithm that is used by a router looking for the applicable subscription(s)/filter(s) to filter the incoming notification. As shown during our evaluation (§ 5.6), the space cost associated with the indexing, is compensated by the gain in terms of responsiveness achieved when forwarding event notifications and (un)subscriptions. Scalability and expressiveness are two conflicting goals that a content-based publish/subscribe faces: the more expressive the subscription, the more overloaded the router is by the forwarding process.

## 5.2 Group-based Publish-Subscribe System

We adopt an event communication model that derives from the well-known asynchronous publish/subscribe paradigm in which consumers express their demands to producers during a subscription process and producers transfer to subscribers the description of any event that has been triggered locally. From a communication standpoint, our distributed event notification system exchanges notifications and control messages (i.e., (un)subscriptions) between producers and subscribers through a collection of intermediate routers that host our notification service. The key objective pursued by any router lies in forwarding a notification to a router only if there exists a consumer interested in receiving it. For the purpose of selectively forwarding notifications, each router holds a repository that includes the received subscription along with a list of the routers, which forwarded it. Indeed, a neighbouring router constitutes the potential candidate towards which the corresponding notifications are forwarded. Intermediate routers are organised into a cluster-based structure (also called an overlay) in which each cluster leader (a.k.a, router) keeps the information concerning: (i) the cluster members under its responsibility and (ii) its connections with other cluster leaders. Such a cluster-based structure facilitates the aggregation and the correlation of notifications and as a result of this significantly reduces bandwidth usage.

### 5.2.1 Underlying Group Communication

In order to dynamically manage the delivery structure to react upon any network failure, we rely on the Nice protocol [17], which is an application-level protocol originally developed to support video streaming over the Internet. The Nice protocol creates a self-organised, cluster-based hierarchy of $n_l$ layers ($n_l=\log(n_n)$), with $n_n$ designating the number of nodes that are expected to join the group, in which each layer is composed of a set of bounded-size clusters controlled by a cluster head. The reason for setting bounds on the number of layers and on the cluster size is twofold. First, it ensures a control overhead of about $\log(n_n)$ at each node. Second, it bounds the length of the path used for delivering notifications, and thereby the related delay ($o(\log(n_n))$). In practice, to warrant a loop-free structure, each node belongs to the lowest layer
<figure><img src="image_93.png" /></figure>

(a) Arrival of a new node *N*: *N* contacts the RP and the closest cluster-heads of each layers so as to join the closest cluster at layer 0

<figure><img src="image_94.png" /></figure>

(b) Message Routing: G and then H send an identical subscription to their cluster-head B. G's subscription is disseminated across the cluster-based structure. Later on, I generates a notification, which matches G's and H's subscription and is forwarded to G and H.

Figure 5.2 – Routers organised into a cluster-based structure through which messages are transmitted

$(L_0)$ and only the leader of a cluster located in a layer $L_i$ belongs to the upper layer $L_{i+1}$. A node keeps information restricted to its cluster(s) and each member periodically sends a *keep-alive* message. Thus, a cluster leader may passively detect a node failure and initiate a cluster merge/split if the cluster size differs significantly from the desired bound. The Nice protocol relies on a Rendezvous Point that provides bootstrapping information to any new node that joins the cluster-based structure. The addition of a new node *N* to the structure is handled as follows (Figure 5.2a): *N* contacts the Rendezvous Point (RP), which provides bootstrapping information relating to (i) the group configuration (e.g. the identity of the root *R*, number of layers, the cluster's bounded-size) and (ii) the event system configuration (e.g. the number of hash functions, hashing algorithm in use). Next, with the bootstrapping information given by *RP*, *N* selects the closest cluster head (*B*) and refines progressively its selection at each layer so as to ultimately join the closest cluster in layer $L_0$ (i.e., *H*'s cluster in Figure 5.2a). Once created, the resulting delivery structure is used to propagate messages generated by the publish/subscribe system.

### 5.2.2 Cluster-based Routing

The main challenge related to routing over the cluster-based structure stems from the need to minimise the traffic and the computational load of routers. This calls for:

1. Duplicating messages as close as possible to their respective consumers, while filtering notifications as close as possible to event producers.

2. Minimising the number of control messages that are propagated.

3. Minimising the processing load induced by filtering notifications.

In the following, we describe to which extent our routing strategy meets the above commitments.

**Subscription Routing.** In order to propagate less subscriptions, a router determines if a subscription should be forwarded or not, and if so, towards which neighbouring router(s). To clarify this decision making we consider two consumers, *G* and *H* (Figure 5.2b), which declare their interests in receiving notifications for event *e*. Let us assume that *G* first sends a subscription to its neighbouring routers *B* and *H* and that shortly after *H* sends an identical
subscription to its neighbouring routers *B* and *G*. Upon receiving *G*'s subscription, *B* forwards it to its upper-layer router *R* and its sibling *A*. Following, *G*'s subscription is forwarded to all the remaining routers: *R* sends *G*'s subscription to *E* and *F* while *A* forwards *G*'s subscription to *C* and *D*.

Later, upon receiving *H*'s subscription, *B* does not propagate it to *R* and *G*, because there is no need for *B* to propagate a subscription for a notification that it has already previously received. Herein *H*'s subscription is not propagated because an identical subscription ( *G*'s subscription) was already propagated. The same propagation process would apply if *H*'s subscription were covered by *G*'s subscription since this would mean that the events that match *G*'s subscription(s) also match *H*'s subscription. Subscription is routed as follows: if the subscription is ascendant<fnref n="1" />, then that subscription is forwarded<fnref n="2" /> to the upper-level router. Conversely, if the incoming subscription corresponds to a descendant message or has been issued by a clustermate, then that subscription is forwarded to all lower-level routers. The unsubscription routing is similar to the subscription routing: a router forwards an unsubscription only if the related subscription was previously forwarded to that router.

Event Notification Routing

Figure 5.2b illustrates our presentation on notification routing: an event producer *I* generates a notification *e* in which two consumers are interested (*G* and *H*). *I* then sends a notification *e* to its cluster head *C*, which propagates it to *A* since a subscription that matches *e* was previously issued by *A*. Following, *A* propagates the event notification to *B*, which in turn propagates it to *G* and *H*. Overall, the event notification is not propagated to all the routers: any router that receives the notification selects the router(s) towards which the notification should be propagated. The selection process consists in first matching the notification against the subscription summary and then in extracting the list of neighbouring routers that should forward the matching subscriptions. The propagation of the notification over the delivery structure formed by the router is the same to the one carried to disseminate (un-)subscriptions.

**5.3 Notification and Subscription Representation**

The effectiveness of the routing depends on the structure used to represent notifications, (un)subscriptions (§5.3.1 and §5.3.2) and on the structure used to organise all subscriptions (§5.4).

**5.3.1 Notification and Subscription Formats**

An event notification (or simply a notification) is composed of a set of $n_e$ attributes that are typed and that describe the event (Figure 5.3a); each attribute $\alpha_i$ (with $1 \le i \le n_e$) consists of a type as well as a name-value pair: $\alpha_i = (type_{\alpha_i}, name_{\alpha_i}, value_{\alpha_i})$. An attribute type belongs to a predefined set of primitive types( e.g., string, integer or date). Figure 5.3a illustrates a notification issued by a network-monitoring application that informs about a directory service being stopped.

<footnote n="1">1. An *ascendant subscription* is conveyed to an upper-level router.</footnote>

<footnote n="2">2. If we consider an edge router belonging to layer $L_0$ (resp. $L_M$), the subscription is not forwarded to a lower (resp. upper) layer.</footnote>
<figure><img src="image_95.png" /><figcaption>(a) A notification is generated by a monitoring application. The notification is composed of a set of attributes.</figcaption></figure>

<caption>(b) Four different subscriptions. Each subscription is made of a set/conjunction of filters; each filter is characterised by a type, name, operator and value.</caption>

Figure 5.3 – Notification and subscription

A subscription refers to a conjunction<fnref n="3" /> of $n_a$ filters ($f_1, \cdots, f_j, \cdots, f_{n_a}$) where each filter $f_j$ designates a consumer's interest for a particular event. Each filter $f_j$ is characterised by a type, a name, a predicate operator (e.g. $=$, $<$, substring) and a value. We say that an attribute $\alpha_i = (type_{\alpha_i}, name_{\alpha_i}, value_{\alpha_i})$ is covered by a filter $f_j = (type_{f_j}, name_{f_j}, operator_{f_j}, value_{f_j})$ iff $type_{\alpha_i} = type_{f_j}$ and $name_{\alpha_i} = name_{f_j}$ and $operator_{f_j}(value_{\alpha_i}, value_{f_j}) = true$. The notation $f_j \subset \alpha_i$ means that the filter $f_j$ matches / is covered by the attribute $\alpha_i$. More generally, an event notification $e = (\alpha_1, \cdots, \alpha_{n_e})$ matches a subscription $a = (f_1, \cdots, f_{n_a})$ if the subscription matches all the filters constituting the subscription: $a \subset n$. Among the four subscriptions in Figure 5.3b, only the second subscription matches the notification of Figure 5.3a.

Similarly, a subscription $a'$ is covered by a subscription $a$ ($a' \subset a$) if all the filters constituting $a'$ are covered by those of $a$. This also implies that any event notification matching $a$ also matches $a'$: $\forall e/a' \subset e \Rightarrow a \subset e$. Note that the covering relations are:

* reflexive: $a \subset a$ is always met.

* anti-symmetric: if $a \subset a'$ and $a' \subset a$ then $a = a'$.

* transitive: if $a \subset a'$ and $a' \subset a''$ then $a \subset a''$.

The establishment of a covering relationship constitutes a resource-consuming process that reiterates upon the receipt of a (un)subscription or of an event notification. In both cases a router attempts to discover if there exists (at least one) subscription $s$ that covers the (un)subscription $s'$ or that matches the event notification $e$. To this end, the router should go through all $n'_s$ filters of the (un)subscription or all the $n_e$ attributes of the notification $e$ so

<footnote n="3">3. A disjunction is obtained using several subscriptions.</footnote>
as to assess if the attributes are covered by or match the filters constituting the subscription *s*. This results in $O(n_s \cdot n_{s'})$ or $O(n_e \cdot n_a)$ comparisons if the attributes and filters are not ordered, and in $O(\min(n_e, n_s))$ (resp. $O(\min(n_s, n_{s'})|$ comparisons if they are ordered. Overall, the handling of a new (un)subscription or event notification is laborious with content-based pub/sub systems while topic-based publish/subscribe systems filter events and handle (un)subscriptions in $O(1)$ when the subscriptions are stored in hash tables.

## 5.3.2 Subscription Organisation - State of the Art

Few solutions [112, 125, 34, 24, 85, 32] thus far address reorganisation of subscriptions so as to improve the notification filtering and the (un)subscription process. All propose to organise the subscriptions into a single data structure, which corresponds to a list, a partially ordered set (or poset), a R-tree, a B$^+$-tree or a binary decision diagram. As detailed in the following, performance associated with notification filtering or with the establishment of a new (un)subscription covering varies depending on the data structure:

* **List** [112, 125] - In a list containing *n* subscriptions, the establishment of the covering relationship with an (un)subscription *s*′ is costly: the covering is established in $O(n \cdot n_s \cdot n_{s'})$ if subscriptions are not ordered and in $O(\log(n) \cdot \min(n_s, n_{s'}))$ if ordered. The filtering of an incoming event notification *e* takes $O(n \cdot n_e \cdot n_s)$ when subscriptions are not ordered and $O(\log(n) \cdot \min(n_e, n_s))$ if subscriptions are ordered. With a list, the subscriptions are stored one by one. The alternative structures described below, combine the filters that form the subscription into a single data structure, which is organised in different ways.

* **Poset** [34] (see Figure 5.5 on page 103) exploits the covering relations of a set of filters by applying a partial order on the set of subscriptions. Thus, any subscription at the upper level covers its descendant (Figure 5.6a). In practice, a poset corresponds to a direct acyclic graph whose size has an information-theoric lower bound of $n_p^2/4 + O(n_p)$ [113] and a (worst case) space complexity of $O(n_p^2)$ [34] with $n_p$ defining the number of elements stored in the poset. Adding/removing a subscription or filtering an event notification necessitates the lookup of subscription(s), which is done [34] by traversing the poset following a breadth-first order and starting from the root. This lookup has a worst case complexity of $n_p$, though in practice it may be lower. This results in a subscription process done in $O(n_p^2)$, an unsubscription process of $O(n_p^3)$, and a notification matching of $O(n_p)$. The two following data structure (R-tree and B$^+$-tree) also exploit the covering relationship.

* **R-tree** [24] has been traditionally used to support spatial queries. An R-tree is a tree in which each internal node has between *m* and *M* children. A node refers to the smallest poly-space rectangle (a.k.a set of filters) that encloses all the rectangles of its subtree (a.k.a covers all its descendants). A range query is answered thought a top-down traversal, starting at the root and recursively following the subtree of each matching child. The height of an R-tree containing $n_r$ nodes is $\lceil \log_M(n_r) \rceil - 1$ with $n_r$ corresponding to the number of nodes. However, there is no acceptable guarantee, given that more than one sub tree under a node may need to be visited. In the worst case, the lookup with an R-tree is as expensive as a naive sequential scan.

* B$^+$-tree is an ordered tree wherein all the intervals (all the filters) are stored and sorted at leaf level for fast traversing. A B$^+$-tree is designed to have a fairly high number of children for each internal node so that the height of the tree remains relatively small.
After insertion and deletion, a B$^+$-tree may thus require balancing. In a tree of size *n*, performing a range query with *k* elements occurring within the range requires O(log\_b*n*+k) operations.

*   **Binary Diagram** [32] structure represents a generic data structure used to represent the Boolean functions constituting a filter. A binary decision diagram may be represented as a DAG with a unique root, in which the internal nodes correspond to the Boolean functions. Thus, there are exactly two outgoing edges, labelled 0 or 1, for each inner node. With the binary decision diagram, an arbitrarily complex Boolean expression of *n* variables can be straightforwardly evaluated, by simply descending the DAG in *n* steps according to the values of the *n* Boolean functions. In counterpart, the size of the tree may exponentially grow with the number of functions.

Overall, the list, poset, R-tree, B$^+$-tree and the binary decision diagram all place a high load on routers and lead to a lower throughput and higher end-to-end latency.

## Overload Reduction

The cost incurred by a lookup may be reduced by keeping the number of nodes in the data structure to a minimum, thereby ensuring a faster traversal. This can be achieved in three ways: (i) reordering the data structure, (ii) merging the overlapping filters [111, 41, 24] or (iii) exploiting the fact [162] that there is no need to store the (new) subscription(s) that are already covered by other subscription(s). A (re)ordering of the nodes may lead to a smaller data structure and hence may reduce the (worst) time complexity. Still, an optimal re-ordering leading to a canonical form is known as an NP-hard problem. While a poset reordering was suggested in [111], complicated heuristics have been devised in the literature on the subject to either avoid the exponential growth of binary diagrams or of balanced R-trees. In particular, the binary tree can be organised in regards to the frequency of attributes and the variable dependencies (the analysis being an O(n²) process). In such a case, frequent attributes are positioned near the root. The R-tree can be balanced by splitting an overflowing node during the joining process. Both a linear and an enhanced quadratic method in *M* and in the number of dimensions have been proposed. Going one step further, the filters that overlap can be merged together [111, 41] so as to reduce the depth and width of the data structure.

## 5.4 Enhanced Forwarding

Forwarding a notification or a (un)subscription is a common and resource-consuming process for a router as it entails the two following tasks:

*   Searching for the subscriptions that (i) match the incoming notification, or (ii) cover the incoming (un)subscription. As seen in Section 5.3.2 the matching of the notification and the establishment of the coverage both imply going through the router's subscriptions and are organised in several ways (list [112, 125], R- or B$^+$-tree [24] or binary decision tree [32] and poset [34]). With a list, the search consists of reviewing the subscriptions one by one; with the remaining structures, the router traverses the structure, following the children that match/cover. The sequential reviewing and the traversal of the structure both involve an elementary operation that consists in either matching the notification attribute against a subscription filter or establishing the covering relationship between two filters.
* The two elementary operations are relatively complex. As an illustration, matching the attribute `String priority = 3` against the filter `Integer priority > 2` requires verifying that both have (i) the same type (`String`), (ii) the same name (`priority`) and (iii) that the value taken by the attribute (3) is indeed > 2. These elementary operations (i.e., matching and establishment of a covering relationship) are repeated until any subscription that matches/covers is discovered.

It is worth stressing that each router traversed by a notification/(un)subscription often unnecessarily looks for the same subscription(s) and thereby performs a duplicate search. In order to avoid any unnecessary duplication of the search while making it easier to search when necessary our approach is threefold:

* We include in the notifications (resp. (un)subscriptions to be conveyed) the subscription filters that need to be applied to filter the notification (resp. cover the incoming (un)subscriptions). Based on these embedded filters, any intermediate router gains fast access to the subscription(s) that match(es)/cover(s) the incoming subscriptions/notifications without searching for it/them.

* We summarise/approximate the subscription filters using a Bloom filter, which is useful for several purposes (§ 5.4). First, handling a summary (i.e., a Bloom filter) – in lieu of a full subscription filter – speeds up the filtering of event notifications and the establishment of a covering relationship between subscriptions. Second, rather than including in the notification/(un)subscription all the subscription filters that match/cover the notification/(un)subscription, a router adds a compact set made of the related Bloom filters. Third, Bloom filters can be easily aggregated. This means that a set of Bloom filters that are added to the notification/(un)subscription can be easily aggregated into a single and comparatively smaller Bloom filter. Based on the set of Bloom filters (or the aggregated Bloom filter) a router forwards the notification/(un)subscription to the next router without searching for the subscription(s) that match(es)/cover(s) the incoming notification/(un)subscription (§ 5.4.1).

* We index subscriptions (§ 5.4.2) so as to enhance the search for a matching/covering subscription; the index is similar to a book index that allows anyone to quickly find the chapter of interest, without sequentially going through the book. In our case, the index corresponds to a hash table, which allows us to easily find the subscriptions covering the incoming notifications/(un)subscriptions.

## Subscription and notification summarising

In order to accelerate matching notifications against subscription filters, we propose to represent each filter (and also each subscription) in a compact form by using Bloom filters. A short introduction on Bloom filters is provided in the following section.
## The Bloom Filter in a nutshell

Bloom filters are commonly used first to represent a set in a compact manner and subsequently to test the membership of an element. A Bloom filter [25] is a bit vector of size *m*, denoted $B = b(1), \dots, b(m)$, which is initialised to 0 (i.e., $\forall i \in [1, m], b(i) = 0$).

**Updating a Bloom filter** - To add an element *e* to the Bloom filter, *k* hash functions $h_1, \dots, h_k$ are used. Each hash function is applied to the element and the *k* bits at the positions designated by $h_1(e) \text{ mod}(m), \dots, h_k(e) \text{ mod}(m)$ are set to 1. Assuming that the hash time is $O(1)$ then the time spent adding an element is $O(k)$.

**Testing the membership of an element** - Testing whether an *e* element belongs to the set encoded in a Bloom filter is very similar to adding an element. The *e* is hashed, which gives the values $h_1(e) \text{ mod}(m), \dots, h_k(e) \text{ mod}(m)$. In a Bloom filter, if a bit at said positions is 0 then the element is not stored in the Bloom filter. Otherwise (if none of the bits are at 0), the element is considered to be contained in the Bloom filter, knowing that a false positive may occur but no false negative can occur. The time required to test the membership of an element is $O(k)$.

**Delete an element** - An element cannot be removed from a Bloom filter simply by resetting the *k* bits to 0. To solve this problem, counting Bloom filters have been introduced [60]. The idea is to replace the bit vector forming the Bloom filter with a *u* bit counter vector. A counting Bloom filter corresponds to a vector of *m* counters. Each time an element is added, the counters at $h_1(e) \text{ mod}(m), \dots, h_k(e) \text{ mod}(m) \text{ mod}(m)$ are incremented. Thus, an *e* element can be deleted by decreasing the *k* counters located at the positions $h_1(e) \text{ mod}(m), \dots, h_k(e) \text{ mod}(m)$. A counting Bloom filter supports deletion of data in $O(k)$. However, the use of counters implies an increased use of storage space and the possibility of false negatives.

## Encoding of subscription filters as Bloom filter

A subscription is composed of a set of *p* filters. Each subscription filter, denoted $f_j$ (with $1 \le j \le p$), composing the subscription is hashed<fnref n="4" /> using *k* hash functions and stored in a Bloom filter.

In order to limit their space footprint, there are two options for representing the Bloom filter depending on the number of elements (i.e., filters) to be stored: as a bit vector (as is the case with traditional Bloom filters) if the number of elements is low or as a list of hashes. Since a set of Bloom filters can be easily aggregated, a subscription can therefore be summarised into a single Bloom filter (Figure 5.6b). In order to summarise a set of filters, denoted $f_1, \dots, f_j, \dots f_p$, into a Bloom filter $b_f$, we apply a bitwise OR on the corresponding Bloom filters: $b_f = b_{f_1} \text{ OR } \dots \text{ OR } b_{f_j} \text{ OR } \dots \text{ OR } b_{f_p}$. If the Bloom filter is encoded as a list of hashes, the resulting Bloom filter is encoded as: $b_f = b_{f_1}, \dots, b_{f_p}$.

## Bloom-filter based repository

Each router keeps the received subscriptions in a dedicated repository, which may be organised as:

* A list of subscriptions in which each subscription is stored along with the corresponding Bloom filter that summarises the subscription. Assuming that $n_f$ filters compose a sub-

<footnote n="4">4. Each field composing the filter can be hashed independently or more simply the entire filter can be hashed.</footnote>
<figure><img src="image_96.png" /><figcaption>Figure 5.4 – An event notification matches the first subscription and does not match the second subscription</figcaption></figure>

<figure><img src="image_97.png" /><figcaption>Figure 5.5 – Subscriptions repository organised as a poset. In the poset, each node refers to a set of filters stored along with the related Bloom filter, which is encoded as a bit vector.</figcaption></figure>

scription, the space overhead associated with a Bloom filter that is encoded as a vector of bits (or a list of hashes) is $-\frac{k n_f}{\ln(1-\rho^+)} k n_f$.

* A tree or a poset (Figure 5.5): each node of the tree/poset corresponds to one or several filter(s) that are also summarised into a single Bloom filter. Assuming that $n_f$ filters are present, the space overhead with a Bloom filter for each node is $-\frac{k n_f}{\ln(1-\rho^+)}$ for a Bloom filter encoded as a vector of bits ($k n_f$ for list of hashes).

Based on its subscription repository enriched with Bloom filters, routers forward the received notifications/(un)subscriptions to the interested recipients.

### 5.4.1 Preventing Intermediate Routers From Performing Duplicate Searches

Our goal is to prevent any router through which a notification/(un)subscription passes from individually performing the same treatment. The design rationale is that the first router that receives a notification/(un)subscription searches for the covering subscriptions and indicates in the outgoing notification/(un)subscription the filters that should be applied to the notification/(un)subscription. In order to illustrate this process we consider the scenario of Figure 5.2b: a device *I* emits the event notification that is forwarded by the routers *C*, *A* and *B* to the two subscribers *G* and *H*. The search proceeds as follows:

1. The first router that receives the notification – *C* in our example – searches for the subscription(s) that cover(s) the incoming notification/subscription and determines to which neighbouring router(s) propagate the notification/subscription.
2. Then the first router adds to the outgoing notification any indications about the location of the subscription (i.e., how to access the subscription), which allows the next routers to quickly find the subscription(s) without searching for the subscription(s). The type of indication varies depending on the underlying structure adopted to store the subscriptions. With a list of subscriptions the indication consists of the ordered list of subscriptions that match (or resp. cover) the incoming notification (resp. subscription). Note that this ordered list of filters is expressed as a compact set of Bloom filters. In the case of a binary-decision-/R-tree or poset, the path(s) to follow to get the matching subscription(s) must be added. This path materialises by an ordered list of filters that are aggregated into a Bloom filter.

3. The subsequent routers (i.e., A and B) rely on the provided indications (i.e., the list of ordered subscriptions/filters) to extract the related subscription(s) and to forward notification/(un)subscription to the appropriate router(s).

Overall, the above outlined approach eases (and even prevents) the search for subscriptions by intermediary routers. An intermediate router that receives a (un)subscription/ notification containing Bloom filters proceeds by extracting each Bloom filter. If the repository is organised as a list of subscriptions, the router checks if the filter equals a Bloom filter of the repository, which requires $O(k \times n_f)$ comparisons per Bloom filter. If the repository is organised as a tree or poset the router goes through the structure following the path expressed in the provided Bloom filter, which requires $O(k \times n_p)$ comparisons with a path going through $n_p$ filters.

Overall, the representation of subscriptions as Bloom filters speeds up the matching of a notification against a subscription. Nonetheless false positives may occur. In such a case, a router assumes that an incoming subscription/notification is covered/matches (while this is not the case) and unnecessarily forwards the notification/(un)subscription. The probability of a false positive differs depending on the representation of the Bloom filter.

* *Probability of false positives with a Bloom filter corresponding to a list of hashes* - Knowing that the probable occurrence of a false positive when an filter is compared to a filter is equal to $(1 - \frac{1}{N})^k$, we can therefore infer that the probability of a false positive $p(E)$ occurring when $n_f$ filters are compared to $n_e$ attributes is:

$$p(E) = C_{n_f}^{n_f} (1 - \frac{1}{N})^k \qquad (5.1)$$

* *Probability of false positive with a Bloom filter expressed as a vector of bits* - We will use a balls-and-urns construct to model the handling of a Bloom filter. A Bloom filter (i.e., a vector of bit) is modelled as $m$ urns. We distinguish the repository subscriptions and incoming subscription using different colours: an incoming subscription is modelled as a set of bright balls and a subscription of the repository as set of back balls. The addition of $n_f$ filters in a Bloom filter is equivalent to throwing $k \times n_f$ bright balls into $m$ urns (with $m$ corresponding to the size of the Bloom filter). We define an urn as shiny if it contains at least one shiny ball. Adding $n_f$ filters to a Bloom filter corresponds to randomly throwing $n_f \times k$ black balls into $m$ urns. A false positive occurs if a subscription of the repository does not correspond to an incoming subscription even thought the $n_f \times k$ black balls have been thrown into bright urns. Using conditional probabilities and applying the law of total probability we infer that the $p(E)$ probability of a false positive occurring is:

$$p(E) = \sum_{r=1}^{m} \left[ \sum_{i=1}^{m} p(E/E_i/E_r)p(E_i) \right] p(E_r) \qquad (5.2)$$
with $p(E/E_i/E_j)$ denoting the probability that $r$ black balls are thrown in $i$ bright urns, $p(E_i)$ corresponding to the probability that $i$ urns are bright, and $p(E_r)$ the probability that $r$ urns are black. For a given $i$ and given $r$, we observe that $p(E/E_i/E_r)$ is:

$$p(E/E_i/E_r) = \left(\frac{i}{m}\right)^r \qquad (5.3)$$

In addition, the probability $p(E_i)$ that $i$ urns are bright corresponds to the quotient between:

- The number of surjections from a set containing $k \times n_f$ elements to a set of $i$ elements [79]. This number is equal to $i!.St(k \times n_f, i)$, with $St$ symbolising Stirling's number.

- The number of functions of $k \times n_f$ elements in a set of size $m$, which corresponds to $m^{k \times n_f}$.

So:

$$p(E_i) = \frac{1}{m^{k \times n_f}} \sum_{j=0}^{i} (-1)^j C_i^j j^{k \times n_f} \qquad (5.4)$$

Likewise, $p(E_r) = \frac{1}{m^{k \times n_f}} \sum_{s=0}^{r} (-1)^s C_r^s s^{k \times n_f}$. We conclude that:

$$p(E) = \frac{1}{m^{k^2 \times n_f \times n_f}} \sum_{r=1}^{m} \sum_{s=0}^{r} (-1)^s C_r^s s^{k \times n_f} \sum_{i=1}^{m} \frac{i^r}{m^r} \sum_{j=0}^{i} (-1)^j C_i^j j^{k \times n_f} \qquad (5.5)$$

Based on Formulas 5.2 and 5.5, the number of hash functions is set according to the number of filters contained in the subscription/path, so that the probability of a false positive remains below a given threshold.

### 5.4.2 Prefiltering with an Index-based Subscription Repository

The efficiency associated with the event/subscription forwarding depends of various aspects. With a repository containing a list of subscriptions, key factor is the number of subscriptions stored in the repository. With tree or poset, the depth and the width of the tree/poset are two key factors. Usually, the root tends to have many children. Visiting all the children of the root – which we call horizontal crossing – is laborious and very frequent. Note: if there is no subscription filter that matches, all the children of the root are visited. In order to: (i) speed up the subscription search (especially the horizontal crossing) and (ii) avoid starting a subscription search when no subscription filter match, we propose to: (i) rely on hash tables that speedup the horizontal crossing (ii) introduce a prefiltering process that avoid searching for some covering subscriptions while no subscription covers.

#### Index-based Structure

We propose to index the subscriptions, leveraging hash table. With a list of subscriptions, we propose to replace the list by a hash table. Thus, subscriptions are located with a key (as detailed in the following paragraph), without searching for the subscription. In the case of a poset or tree, the first level of nodes are also organised in a hash table. Similarly, subsequent level may also be accessed using a hash table, i.e., the children of a given node are easily
organised in hash table. Thus, upon the reception of a new subscription, it becomes easier to localise the subscription in the hash table. In the case of a (ordered) list, subscriptions are located according to a specific criterion, rather than searching for the subscription sequentially or by dichotomy (if the list is ordered). In the case of a poset (Figure 5.6a) or tree, it allows the router to quickly find the first level nodes. Similarly, subsequent levels can be accessed using a hash table.

Prefiltering

Notifications are prefiltered using a counting Bloom filter stored in each router, which encom-
passes all the subscriptions, i.e., that aggregates all the Bloom filters stored by a router. As a
result, a router avoid starting an unnecessary lookup. Moreover, several counting Bloom filter
may also summarise all the filters accessible through the nodes of the poset/tree. Using these
counting Bloom filters avoid starting a search from these nodes whereas there is no matching
subscriptions.

<figure><img src="image_98.png" /><figcaption>Figure 5.6 – Subscriptions organised in poset and Bloom filter associated with a filter.</figcaption></figure>

In the following, we briefly describe the way subscriptions are indexed and added to the
router repository so that incoming notifications can be filtered.

Generating an index

We hash the names of each filter $f_i$ constituting the subscription. A particular index designated by the key $min(h(f_i.name))$ is selected and used to store the subscription. We use the minimum value to define the position where the subscription is stored, knowing that more advanced techniques could be used to perform load balancing. In order to minimise the number of subscriptions that are stored, a subscription is only added if there is no other subscription propagated by the neighbouring router that covers this subscription. The identity of the neighbouring router is stored along with the subscription so that later notifications can be redirected to it.
## Adding a subscription

Adding a subscription to the repository consists of extracting each filter and hashing the filter name so as to generate a set of keys. If the repository is organised as a list of subscriptions, then, the subscription is simply added in the cell of the hash table, which is designated by the lowest index. If the repository is organised as a tree/poset, each cell given by a key is inspected. If all the concerned cells are empty, then the subscription is simply added in the cell identified by the lowest key. Otherwise, if one cell is not empty, then there is potentially an overlapping subscription. In such a case, the covering relationship is recursively established: the covering relationship with the filter(s) composing the node is studied and the traversal continues with the matching child(ren) (if any) so as to find the proper cell wherein is ultimately added the subscription.

## Looking for the subscription(s) that match(es)

Upon the reception of an event notification, the router pre-filters the notification. If the notification is not pre-filtered, then the router hashes the name of the attributes that form the subscription and inspects the location identified by the hashes so as to find the filter(s) (and possibly the subscription) that match. With a poset/tree, this process is recursively iterated so as to find the matching subscription.

### 5.4.3 Synthesis

We have proposed an event notification system that distinguishes itself in the use of Bloom filters that improve the lookup process, thereby introducing significant performance gain (in terms of delay and computational load). Subscription is encoded as a concise Bloom filter that is further conveyed along with the subscription (resp. notification) so as to speed up the routing by avoiding the sequential comparison of each subscription constraint (resp. each notification attribute). In addition, counting Bloom filters are used to summarise the subscriptions and avoid searching for potential subscriptions that are not existing anyway.

In the following we go one step further and focus our attention on the problem of assigning an adequate size to Bloom filters. This is critical since dealing with:

* undersized Bloom filters induces a poor accuracy (i.e., a high false positive rate with Bloom filters and false negative rate only for the counting Bloom filters).

* oversized Bloom Filters lead to a waste of bandwidth/storage usage with no gain in terms of accuracy.

Thus, the Bloom filter size should be modulated (i.e., increased or decreased) when the number of items stored in a Bloom filter substantially varies.

To cope with an undersized Bloom filter, a straightforward solution lies in adding another Bloom filter in which new items are inserted. To deal with oversized Bloom filter, a naive (but widely practiced) approach lies in recomputing another Bloom filter with the most suitable size. This is impractical because it involves a significant computation cost since all the elements must be added to the new Bloom filter.

In the following, we continue our analysis of our event notification system by focusing our attention on the compression of Bloom filter, which is a critical factor since an oversized Bloom Filter results in significant bandwidth/storage usage with no gain in accuracy. To this end we introduce a lossy compression algorithm, which consists in folding the Bloom filter, so as
to require less space for storage or transmission. Note that this approach can be applied to
counting Bloom filter. The proposed compression takes advantage of the fact that Bloom filters
contain more information than necessary.

5.5 Folding Bloom Filters

Folding a Bloom filter is beneficial in the two following circumstances:

1. the Bloom filter stored in memory should be folded because it was initially over-sized. This situation frequently occurs because it is difficult to find a suitable size for a Bloom filter since one must estimate in advance the amount of data that will be stored. Thus, a conservative approach based on over-sizing Bloom filters, which is often adopted.

2. A large Bloom filter needs to be transmitted and must first be folded so as to keep bandwidth usage and communication delay to a minimum.

In order to deal with both cases, we introduce a lossy compression algorithm, which performs
the folding of the Bloom filter and hence optimises the bandwidth/storage usage by reducing
the Bloom filter's size.

In the following, we exemplify the folding of a Bloom filter with the following Bloom filter
of 20 bits: 10010 11111 11101 11000. The halving of the Bloom filter consists of applying a OR
on the two portions of the Bloom filter: 10010 11111 OR 11101 11000. The resulting Bloom
filter of size 10 is 10000 11000. With a counting Bloom filter, the folding is done by adding
the corresponding counters, using the maximum in case of overflow. It is worst-emphasising
that with a Bloom filter of size 20, there exists several possible folding. Instead, a Bloom filter
containing 5 bits/counters cannot be folded<fnref n="5" />. Let us understand the reason why by considering
a Bloom filter of size 20. A Bloom filter of size 20 can be folded in 7 ways because there are
7 ways of factorising the original size of the Bloom filter: 20 = 2.10 = 2.2.5 = 2.5.2 = 4.5 =
5.4 = 5.2.2 = 10.2. Remark that 5 and 2 are primes while 20, 10 and 4 are some composite
numbers, *i.e.*, they can be expressed as a product of primes. Their composite nature implies
that a Bloom filter with a size of 20, 10 or 4 can be folded while a Bloom filter with a size equal
to 5, cannot be folded because 5 is a prime. Overall, selecting a proper size for the Bloom filter
is critical so as to guarantee that many different folding may be applied later. Then, among the
possible choice(s), our goal is then to determine which is the best folding to apply at run time.
In the following, we explore to which extend the folding may be achieved and we break the
two related optimization problems into the off-line sizing of the Bloom filters and their on-line
folding:

* Off-line sizing of the Bloom filters (§ 5.5.1) - The sizing of a Bloom filter depends on the number of elements that are expected to be added and the required false positive rate. We will show that the ability to fold a Bloom filter is related to the size of the Bloom filter. We will investigate this relationship by introducing the mathematical background on number theory as well as providing a mathematical and practical formulation for finding the optimal Bloom filter size. Although we will show that this size should be ideally a highly composite number (i.e., a positive number that has a larger number of divisors than any number smaller than itself), practical considerations will lead us to formulate the problem of finding a Bloom filter size as equivalent to finding a *y*-smooth-number, i.e., a positive number whose prime factors are little primes (i.e., $\le y$). Once the size is set, the filter is created and may be compressed whenever needed by folding it.

<footnote n="5">5. We purposely exclude a bloom filter of size 1 that only reflects that the encoded set is empty or not empty</footnote>
* *On-line folding* can be modulated (§ 5.5.2) based on the amount of data actually stored in the Bloom filter and the admissible false positive rate. The folding (§ 5.5.3) can be viewed as a simple form of lossy compression that reduces the size of the Bloom filter and hence requires less space for storage or transmission. The lossy nature of the compression implies that the original Bloom filter cannot be reconstructed from the folded Bloom filter.

## 5.5.1 Finding y-Smooth Numbers

Number theory comes into play here because the determining the precise sizing of Bloom filters is critical to our approach. So before moving on with the planning of the Bloom filter size, let us first introduce some basic notions and background on number theory and more specifically on smooth numbers.

### Digression on Number Theory

Any number $m \in \mathbb{N}^*$ can be expressed in a unique way as a product of primes:

$$m = \prod_{j=1}^{\infty} (p_j)^{\gamma_j} = \prod_{j=1}^{a} (p_j)^{\gamma_j} \qquad (5.6)$$

with $p_j \in \mathbb{N}$, $(i, \gamma_j) \in \mathbb{N}^2$, $a = \max\{i \in \mathbb{N} | \gamma_i > 0\}$ and $\forall i < j, p_i < p_j$. Contrary to a prime number, a *composite number* has divisor(s) apart from itself and one. Keeping in mind that we aim at finding numbers that have a high number of divisors, we naturally exclude primes and focus our attention on highly composite numbers. A *highly composite number* (resp. a *largely composite number*) [129] is a number that has a larger number of divisors (resp. a larger or equal number of divisors) than any number less than itself and is herein the best (resp. good) candidate. Unfortunately, even though largely composite numbers are more crowded than highly composite numbers, both remain rare. To illustrate: 34 highly composite numbers and 87 largely composite numbers are $\le 332640$; example values are provided in Table 5.1. More formally [116], the number of highly composite and largely composite numbers less than $x$, denoted $\Psi(x)$, is subject to $\Psi(x) \ll \ln(x)^b$ with $b$ being constant and respectively to $\exp(\log^c(x)) \le \Psi(x) \le \exp(\log^d(x))$ with $c$ and $d$ constant, for any large $x$. Studying the decomposition of the largely and highly composite numbers given in Table 5.2, we can hypothesise that a number suitable for our purposes would be composed of little primes, because this reflects the ability to fold a Bloom filter and thus to smoothly reduce the Bloom filter size. This suggests considering using a *smooth number*, which is a number with only small prime factors [100]. Technically, a positive integer is said to be *y-smooth* if it holds no prime factor exceeding $y$ (i.e., any constituting prime factors $\le y$). These numbers are fairly numerous. Theorem 5.5.1, whose detailed proof can be found in [78], gives a sense of the density of the smooth numbers that belong to an interval $[1, x]$ by showing that the proportion of *y-smooth* numbers up to $x$ that have only small primes (i.e., $y \le x^{1/u}$) tends to a non-zero limit which is denoted $\rho(u)$.

**Theorem 5.5.1** Let $S(x, y)$ be the set of $y$-smooth up to $x$ and $\Psi(x, y)$ denote its cardinality. Given $y = x^{1/u}$ ($\forall u \ge 1$), this number tends to a non-zero limit as $x \to \infty$. This limit is denoted $\rho(u)$ and the cardinality satisfies [45]:

$$\Psi(x, y) \sim x \rho(u) \quad \text{as} \quad x \to \infty \qquad (5.7)$$
with $\rho$ defined as:

* $\rho(u) = \frac{1}{u} \int_{u-1}^{u} \rho(t) dt, \forall u > 1$, and,

* $\rho(u) = 1$ for the initial condition $0 \le u \le 1$.

A closed form of $\rho$ to express $\Psi(x, y)$ has been established in [72]:

$$ \Psi(x, y) = \frac{1}{\pi(y)} \prod_{p \le y} \left( \frac{\log x}{\log p} \right) \left( 1 + O \left( \frac{y^2}{\log x \log y} \right) \right) \quad (5.8) $$

Although this theorem gives the global distribution of y-smooth numbers over a range $[0, x)$ - the values of the function $\rho$ used in Expression 5.7 are provided in [72] (page 288) - the density of the smooth numbers is represented by the average gap in the sequence of two smooth numbers, denoted $n_i$ and $n_{i+1}$ with $n_i < n_{i+1}$, is about:

$$ \approx \frac{n_i}{(\log n_i)^{\pi(y)}} \quad \text{with } c_2(y) \le \pi(y) \le c_1(y) \quad (5.9) $$

Based on Equations 5.8-5.9, we observe that y-smooth numbers are quite numerous. This implies that they constitute a good solution for our folding problem.

<table><caption>Table 5.1 – Largely Composite Numbers (extracted from the annotations provided as part as [129] from the table handwritten by S. Ramanujan). Highly composite numbers are identified by *</caption><tr><td>*1</td><td>*2</td><td>*3</td><td>*4</td><td>*6</td><td>8</td><td>10</td><td>*12</td><td>18</td></tr><tr><td>20</td><td>*24</td><td>30</td><td>*36</td><td>*48</td><td>*60</td><td>72</td><td>84</td><td>90</td></tr><tr><td>96</td><td>108</td><td>*120</td><td>168</td><td>*180</td><td>*240</td><td>336</td><td>*360</td><td>420</td></tr><tr><td>480</td><td>504</td><td>540</td><td>600</td><td>630</td><td>660</td><td>672</td><td>*720</td><td>*840</td></tr><tr><td>1080</td><td>*1260</td><td>1440</td><td>*1680</td><td>2160</td><td>2520</td><td>3360</td><td>3780</td><td>3960</td></tr><tr><td>4200</td><td>4320</td><td>4620</td><td>4680</td><td>*5040</td><td>*7560</td><td>9240</td><td>*10080</td><td>12600</td></tr></table>

<table><caption>Table 5.2 – Decomposition of Highly and Largely Composite Numbers</caption><tr><td>*2</td><td>3</td><td>*4 = 2<sup>2</sup></td><td>6 = 2 * 3</td><td>8 = 2<sup>3</sup></td><td>10</td></tr><tr><td>*12 = 2<sup>2</sup>.3</td><td>18 = 2.3<sup>2</sup></td><td>20 = 2<sup>2</sup>.5</td><td>24 = 2<sup>3</sup>.3</td><td>30 = 2.3.5</td><td>36 = 2<sup>2</sup>.3</td></tr><tr><td>48 = 2<sup>4</sup>.3</td><td>*60 = 2<sup>2</sup>.3.5</td><td>72 = 2<sup>3</sup>.3<sup>2</sup></td><td>84 = 2<sup>2</sup>.3.7</td><td>90 = 2.3<sup>2</sup>.5</td><td>96 = 2<sup>5</sup>.3</td></tr><tr><td>108 = 2<sup>2</sup>.3<sup>3</sup></td><td>*120 = 2<sup>3</sup>.3.5</td><td>168 = 2<sup>3</sup>.7</td><td>180 = 2<sup>2</sup>.3.7</td><td>240 = 2<sup>4</sup>.3.5</td><td>336 = 2<sup>4</sup>.3.7</td></tr></table>

Based on a Bloom filter size, denoted $x$, which is provided as input by the application depending on its need, the objective is to find a y-smooth, denoted $m$, that is near the given size $x$ and that offers a large number of possible folding. In practice, we isolate a short interval $[x, x + z]$ near $x$ and find a smooth number in this interval. Note that $z$ should be selected based on Expression 5.9 so that the interval $[x, x + z]$ contains at least one smooth number. Then, all the numbers $x, x + 1, ...x + z$ should be enumerated and the divisibility with small primes (i.e., with all the primes $\le y$) tested for each. Assuming that $x$ is fairly large, $y$ relatively very small and $z$ sufficient to find at least one smooth number, excessive calculation
<figure><img src="image_99.png" /><figcaption>Figure 5.7 – Find primes up to z=10. Primes are 2, 3, 5, 7 because these numbers are not crossed.</figcaption></figure>

<figure><img src="image_100.png" /><figcaption>Figure 5.8 – Find the y-smooth numbers up to z=10 with y=3. The y-smooth numbers are 4, 6, 8, 9 because they hold at least two crosses.</figcaption></figure>

would still be required given that $O(\sqrt{x})$ trials are expected to factorise each $x$. However, the cost related to the factorisation of consecutive integers $x, \dots, x+z$ can be alleviated by relying on the well-known sieve of Eratosthenes. Although we may consider more recent algorithms (e.g., the elliptic curve factoring [95]), the sieve of Eratosthenes is sufficiently fast for the Bloom filters sizes that are needed in practice.

To apply the sieve, one first writes down all the numbers from 1 to $z$ and crosses out all the multiples of 2, 3, 5 and so on, until all multiple of primes not exceeding $\sqrt{z}$ have been crossed out. The remaining numbers are the primes.

Similarly, finding the y-smooth numbers that are $\le x$ can be done (as pointed out in [128]) by crossing out all the numbers that are powers of a prime $\le y$ (Figure 5.8). One then counts the number of crossed-out powers for each number. If that count is sufficient, the number is a smooth number.

We will need to adopt a slightly modified formulation of the problem to generate y-smooth numbers given that we are interested in finding the y-smooth numbers that pertain to the interval $[x, x + z]$ rather than to the interval $[1, z]$. This interval encompasses the potential candidates among which the size of the Bloom filter can be selected.

For this purpose we proceed as follows (see Algorithm 3 for the details):

1. *Initialisation*:

* We start with an array of bits $w$ of length $z$ and initialise each array location to 0 (lines 1-2).

* We assume that the primes that are $\le y$ (excluding 1) are known; these primes are easily generated given that $y$ is by construction small (i.e., $y \ll x$). Let us denote by $\mathcal{P}_y$ this
predetermined set and by $\pi(y)$ the number of primes in this set.

2. Consider successively all the primes $p_i \le y$, and for each perform the following actions:

* Find the starting point, i.e., the smallest number in the interval, which can be divided by $p_i$ and cross-out all the multiple of $p_i$ until all are crossed (line 12), i.e., cross $x + s$, $x + s + p_i$, $x + s + 2 p_i$, $x + s + 3 p_i$ ..., until all multiples of $p_i$ within $[x, x+z]$ are crossed. Note that such a crossing-out has to be performed not only for $p_i = p_i^1$ but also (whenever possible) for $p_i^2$ (double crossing-out), $p_i^3$ (triple crossing-out) etc, which leads to the following step:

* Perform the same action (whenever possible) for $p_i^2, p_i^3, p_i^4$... until all the crossing-out ends. More precisely, this requires shifting the starting point to $x + s + p_i^j$ and crossing out $x + s + p_i^j, x + s + 2 p_i^j, x + s + 3 p_i^j, x + s + 4 p_i^j$, ..., until all multiples of $p_i^j$ within $x, x+z$ are crossed out (line 12).

3. Finally, we attempt to enumerate the y-smooth numbers, i.e., all the numbers $m$ of $[x, x+z]$ that hold a sufficient number of crosses.

**Require:** $x \in \mathbb{N}^*, y \in \mathbb{N}^*, z \in \mathbb{N}^*, z > x, \mathcal{P}_y$

1: **for** $i = 0$ to $z$ **do**

2: $w[i] = 0$ {initialise the array $w$ used to record the sum of the primes powers}

3: **end for**

4: **for** $p_i \in \mathcal{P}_y$ **do**

5: $j \leftarrow 1$

6: $start_{p_i^j} \leftarrow (p_i - (\frac{x-p_i}{2}) \mod p_i) \mod p_i$ {find the starting point so that $p_i^j|x + i$}

7: **while** $start_{p_i^j} \le z$ **do**

8: **for** $k \leftarrow 0$ to $\lfloor \frac{z-start_{p_i^j}}{p_i^j} \rfloor$ **do**

9: $w[i + k \cdot p_i^j] \leftarrow \log(p_i)$ {cross the multiple $k \cdot p_i^j$}

10: **end for**

11: $start_{p_i^j} \leftarrow start_{p_i^j} \cdot p_i$

12: $j \leftarrow j + 1$

13: **end while**

14: **end for**

15: **if** $w[i] \ge \log(x)$ **then**

16: SmoothNumbers = SmoothNumbers $\cap x + i$ {x + i is a y-smooth number}

17: **end if**

**Algorithm 3: Looking for Smooth Numbers**

*Complexity analysis* - Let us investigate the time and space complexity of the algorithm.

* *Initialisation:* the initialisation of an array whose length is $z$, requires $\sim z$ steps and, according to the Prime Number Theorem, the space allocated to store the primes is $O(\pi(y)) \approx \frac{y}{\ln(y)}$.

* *Crossing:* the time devoted to multiple crossings-out splits into the research of the starting point $start_{p_i}$ and then the crossing operation starting from $start_{p_i}$. For all $p_i$ the time for finding the starting point $start_{p_i}^j$ is $\approx \pi(y) \approx \frac{y}{\log(y)}$. In the following, we first consider the
time devoted to the first crossing (step 2.a) and then generalise our analysis to the $j^{th}$ crossing (step 2.b), with $j \ge 1$. The first crossing lies in enumerating all the multiples of $p_i$, with $p_i \le y$. This operation is the one achieved by the sieve of Eratosthenes implemented in the usual way [117], the execution time being $\Theta(z \log \log y)$. More precisely, $\frac{z}{p_i}$ crossing operations are performed for a given $p_i$. Assuming that $y \le z$, we henceforth obtain that for all $p_i$ there are $\sum_{1 \le p_i \le y} \frac{z}{p_i} \approx z \log \log y$ crosses.

The general case consists of crossing all multiples of $p_i^j$, with $j \ge 1$. For a given prime $p_i$ subject to $p_i^j \le z$, the $j^{th}$ operation consists of crossing the multiples of $p_i^j$, leading to $\frac{z}{p_i^j}$ crosses. All $p_i$ subject to $p_i^j \le z$ hence involve $\sum_{1 \le p_i \le y} \frac{z}{p_i^j}$ crossing with $j \ge 2$. Overall, the time $\phi(x, z, y)$ needed for all crossing operations satisfies:

$$ \phi(x, z, y) = \sum_{p_i=1}^{y} \sum_{j=1}^{\log_{p_i}(z)} \frac{z}{p_i^j} $$

Let us find the upper-bound of $\phi$:

$$ \phi(x, z, y) = \sum_{p_i=1}^{\min(y,z)} \frac{z}{p_i} + \sum_{p_i=1}^{\min(y,z^{1/2})} \frac{z}{p_i^2} + \sum_{p_i=1}^{\min(y,z^{1/3})} \frac{z}{p_i^3} + \dots \le \sum_{p_i=1}^{p_i=y \le z} \frac{z}{p_i} + \sum_{p_i=1}^{\min(y,z^{1/2})} \frac{z}{p_i^2} (1 + \frac{1}{p} + \frac{1}{p^2} + \dots + \frac{1}{p^{\log_2(x+z)-2}}) = \sum_{p_i=1}^{\min(y,z)} \frac{z}{p_i} + z \sum_{p_i=1}^{\min(y,z^{1/2})} \frac{1-p_i^{\log(x+z)-1}}{p_i(p_i-1)} \le z (\log \log y + O(1)) $$

* **Enumerating y-smooth Number** - Finding all the smooth number in $[x,x+z]$ requires an $O(z)$ time execution.

Overall, the space required is $z + \pi(y)$ and the computation time is $\pi(y) + z (\log \log y + O(1))$. Note that a logarithm formulation of the problem is used in the provided algorithm so as to limit the space requirement involved in storing the crosses for any of the investigated $z$ and for representing the $\pi(y)$ primes. It also privileges addition over multiplication by representing a composite number in its logarithmic formulation as the following sum: $\log m = \sum_{j=1}^{a} \gamma_j \log(p_j)$ rather than as the product $m = \prod_{j=1}^{a} p_j^{\gamma_j}$.

Among the resulting candidates, one y-smooth number, denoted $m$, is selected; the smooth number should be selected to ensure that the Bloom filter is highly foldable, which yields to the following canonical factorisation of $m$:

$$ m = \prod_{j=1}^{a} (p_j)^{\gamma_j} \quad \text{with } p_i \le y. \qquad (5.10) $$

Thus the operational Bloom filter can be subsequently folded when necessary.

## 5.5.2 On-Line Folding Strategy

The goal is to determine the optimal folding to apply at run time, keeping in mind that the goal remains to meet the required false positives rate $\rho^+$ (and the required false negatives rate $\rho^-$ for the counting Bloom filter).

We express this on-line folding strategy as the following optimisation problem. Given that $m_t$ is the actual size of the Bloom filter, $n_t$ the number of elements stored and $k$ the number of hash functions, our goal is to find the minimal size of the resulting folded filter $m_{t+1}$ that still meets the required false positive rate $\rho^+$ and false negative rate $\rho^-$, subject to $m_{t+1}$ dividing
$m_t$ (which is denoted $m_{t+1}|m_t$). We assume that the number of hash functions is set once, preferably to its optimal value, minimising the false positives rate and is given by $k = \frac{m_0}{n_0} \ln(2)$, with $m_0$ referring to the initial size of the Bloom filter which is about $\frac{-n_0 \ln(\rho^+)}{(\ln(2))^2}$ and $n_0$ denoting the number of items that is expected to be added to the filter. We find that the $m_{t+1}$ that still meets the false positives rate satisfies:

$$m_{t+1} \geq \frac{-n_0 m_t \ln(1 - (\rho^+)^{1/k})}{n_{t+1} f_0 \dots f_t \ln(2)} \quad (5.11)$$

Given that our goal is also to find $m_{t+1}$ that divides $m_t$, the above expressed goal can be refined as finding all the combinations of $p_i^{\gamma_i}$ which produce $m_{t+1}$ and selecting one combination. For instance, as suggested in the following algorithm, the minimal $m_{t+1}$ that matches Equation 5.11 can be used.

Recall that with $m_t = \prod_{j \in S_t} p_j^{\gamma_j}$ the exhaustive enumeration of any folding is characterised by a worst case computing time that is exponential in $\sum_{j \in S_t} \gamma_j$ because the maximum number$^6$ of distinct products $m_t$ obtainable is $2^{\sum \gamma_j}$. The storage required is $\sum_{j \in S_t} \gamma_j$ in the worst case. But if some combinations of folding are equivalent (i.e., have the same product) and are henceforth not computed and not stored, the number of possible folding becomes in the order of $\sum_{j=0}^{q_t-1} \binom{q_t}{j}$ with $q_t = \sum_{j \in S_t} \gamma_j$. Then if the overall set of folding which is computed for $m_0$ is ordered (the duplicates being pruned), the computational cost related to finding $m_{t+1}$ can be reduced to the order of $(\log(\sum_{j=0}^{q_t-1} C_q^j))$ with a worst case of $O(\sum_{j \in S_0} \gamma_j)$. Once the size of the Bloom filter is fixed, the Bloom filter can be folded.

### 5.5.3 Folding

The folding of a Bloom filter consists in first dividing the Bloom filter into segments of size $m'$, which are denoted $s_1, \dots, s_{m/m'}$. Next, these segments are combined to create a folded Bloom filter which is expressed as $s_1 \oplus \dots \oplus s_{m/m'}$, with the folding operator $\oplus$ defined as a combination corresponding to an or logic for a Bloom filter and an addition for a counting Bloom filter with. Precisely, with a Bloom filter (resp. counting Bloom Filter) the folding corresponds to applying a bitwise or on (resp. summing$^7$) the segments.

The Bloom filter is expressed as follows:

$$B' = \left( \bigoplus_{l=0}^{p_l-1} b(1+l m') \atop \dots \atop \bigoplus_{l=0}^{p_l-1} b(i+l m') \atop \dots \atop \bigoplus_{l=0}^{p_l-1} b(m_{t+1}+l m') \right) \quad \text{with} \quad B = \left( \begin{array}{c} b(1) \\ \dots \\ b(i) \\ \dots \\ b(m) \end{array} \right)$$

This folding corresponds to a lossy compression that leads to the establishment of a Bloom filter whose size is less than or equal to that of the filter before folding. Given that a Bloom filter is a vector of size $m$ whose constituent elements are counters whose values go from $\{0 \dots 2^u - 1\}$,

<footnote n="6">6. This number is in fact achieved for some $m_t$.</footnote>

<footnote n="7">7. if a sum exceeds the maximum value $2^u - 1$, the counter is set to $2^u - 1$</footnote>
we have proved that the folding function $\varphi: \{0 \cdots 2^u - 1\}^m \to \{0 \cdots 2^u - 1\}^{m'}$ satisfies the following properties:

1. **Compression with loss** - $\varphi$ maps a set of cardinality $m$ to a set of cardinality $m'$ such that $m'$ divides $m$ for any $m', m \in \mathbb{N}^*$.

Note: a Bloom filter $B_m$ is indexed by its size $m$ and a folding $\varphi_{p_l}$ by the folding ratio $p_l \in \mathbb{N}^*$; this ratio can be expressed as the following quotient: $p_l = m/m$.

2. **Invariance** - The folding always provides the same result and the operations corresponding to the addition of elements, the membership test and the deletion of an element in the case of a Bloom filter, are all performed on a folded Bloom filter the same as they would be on an unfolded filter. The membership test, which is denoted $\omega$, is performed on a folded filter $\varphi_{p_l}(B_m)$ as it would be on a filter of size $m' = m/p_l$ with $\omega_k(\varphi_{p_l}(B_m)) = \omega_k((B'_m))$.

3. **Commutativity** - A sequential folding, denoted $o$, corresponding to two folds $\varphi_{p_l}$ and $\varphi_{p_r}$ is commutative: $\varphi_{p_l} o \varphi_{p_r} = \varphi_{p_r} o \varphi_{p_l}$

4. **Associativity** - sequential folding is associative: $\varphi_{p_l} o (\varphi_{p_r} : o \varphi_{p_v}) = (\varphi_{p_r} o \varphi_{p_l}) o \varphi_{p_v}$

5. **Efficiency** - Any $\varphi$ folding of a Bloom filter $B_m \in \{0 \cdots 2^u - 1\}^m$, $\varphi(B)$ can be done in a polynomial time.

Verifying that the folding satisfies Condition 1 is straightforward. Condition 2 mainly relates to the capacity to query the membership of an element and to add or delete this element in a folded Bloom filter. In the following we concentrate on proving that Condition 2 applies to the membership test. The proof for the addition and deletion, which can be deduced from this equation, will be left to the reader. Recall that the membership query proceeds as follows: the element $e$ is hashed with the $k$ hash functions and if all the $k$ investigated bits are set to 1, $e$ is said to be stored. Thus Condition 2 holds if, for all $k$, $b(h_k(e) \text{ mod } m) \le b'(h_k(e) \text{ mod } m')$. Given that $b'(h_k(e) \text{ mod } m') = \bigoplus_{l=0}^{p_l-1} b(h_k(e) \text{ mod } m' + l m') \ge b(h_k(e) \text{ mod } m)$ it follows that Condition 2 is satisfied and that the resulting probability of false positives $\rho^+$, on the folded (counting) Bloom filter $B$ containing $n$ elements, using $k$ hash functions satisfies: $\rho^+ = (1 - (1 - \frac{1}{m'})^{kn})^k \approx (1 - e^{\frac{kn}{m'}})$. For Conditions 3 and 4, we consider a folding method that is sequentially performed.

**Lemma** - The sequential folding $\varphi_{p_l}$ and $\varphi_{p_r}$ satisfies:

$$ \varphi_{p_l} o \varphi_{p_r} = \varphi_{p_r} p_l \qquad (5.12) $$

*Proof:* Given a Bloom filter $B$, we can prove that:

$$ \varphi_{p_l} o \varphi_{p_r}(B) = \varphi_{p_l p_r}(B) $$

The successive folding of $B$ leading to $B'$ and the subsequent folding of $B'$ resulting in $B''$ can be expressed as:

$$ \forall i \in [1, m''], b''(i) = \varphi_{p_l} o \varphi_{p_r}(b(i)) = \varphi_{p_l}(b'(i)) $$

with: $\forall i \in [1, m'], b'(i) = \bigoplus_{r=0}^{p_r-1} b(i + r \cdot m')$.
Thus, $\forall i \in [1, m'']$, $b''(i)$ can be expressed as:

$$ 
\begin{aligned}
b''(i) &= \bigoplus_{l=0}^{p_l-1} \bigoplus_{r=0}^{p_r-1} b(i + l \cdot m'' + r \cdot m') \\
&= \bigoplus_{l=0}^{p_l-1} \bigoplus_{r=0}^{p_r-1} b(i + l \cdot \frac{m}{p_l p_r} + r \cdot \frac{m}{p_r})
\end{aligned}
$$

A one-time-composite folding of B that leads to $B''$ is performed as follows:

$$ 
\begin{aligned}
\forall i \in [1, m''], b''(i) &= \phi_{p_r p_l}(b(i)) \\
&= \bigoplus_{j=0}^{p_r p_l - 1} b(i + j \cdot m'') \\
&= \bigoplus_{j=0}^{p_r p_l - 1} b(i + j \cdot \frac{m}{p_r p_l})
\end{aligned}
$$

Thus, $\phi_{p_l}(b) = \phi_{p_r}(b)$ given $l \in [0, p_l]$, $r \in [0, p_r]$, and, $j = l + rp_l$ $\square$.

The above lemma means that the Bloom filters resulting of a sequential folding $\phi_{p_r} \circ \phi_{p_l}$ is identical to a single folding $(\phi_{p_r} \circ \phi_{p_l})$. Based on this lemma, the proof of conditions 3 and 4 can be established as:

$$ \phi_{p_r} \circ \phi_{p_l}(B_t) = \phi_{p_l} \circ \phi_{p_r}(B_t) = \phi_{p_r} \circ \phi_{p_l}(B_t) = \phi_{p_l} \circ \phi_{p_r}(B_t). \text{ Thus, } \phi_{p_l} \circ \phi_{p_r} = \phi_{p_r} \circ \phi_{p_l} \square $$

$$ \text{In addition, } \phi_{p_l} \circ (\phi_{p_r} \circ \phi_{p_v}) = \phi_{p_r} \circ \phi_{p_l} \circ \phi_{p_v} = (\phi_{p_r} \circ \phi_{p_l}) \circ \phi_{p_v} $$

$$ \text{Thus, } \phi_{p_l} \circ (\phi_{p_r} \circ \phi_{p_v}) = \phi_{p_l} \circ (\phi_{p_r} \circ \phi_{p_v}) \square $$

The commutative and associative properties of the folding imply that the order of the folding does not matter. More generally, given the folded Bloom filter B, it is impossible to guess whether the Bloom filter went through a one-time or sequential folding; the folding pathway cannot be inspected given the resulting Bloom filter. Although the sequential folding $\phi_{p_r} \circ \phi_{p_l}$ and a one-time folding $\phi_{p_r} \circ \phi_{p_l}$ provide the same result, the cost in terms of time resulting from a sequential folding is greater than the cost of a one-time folding. Indeed (as defined in Condition 5), the computation cost associated with the folding is $O(m)$: it depends on the size of B even if this cost can be reduced if the folding is parallelised. But, the cost of a sequential folding is $O(m(1 + \frac{1}{p_l}))$ with $p_l$ defining the second folding ratio.

# 5.6 Performance Evaluation

Our next step is to assess the performance of our event notification system 5.6.1 via the folding of Bloom filters 5.6.2.

## 5.6.1 Event Notification System

In order to reveal the scaling properties of our event notification system, we distinguish the corresponding control traffic induced by the management of the cluster-based structure (Figures 5.9a and 5.9b) and by the dissemination of the event notifications and (un)subscriptions. For this purpose we use a constant load of 3 events/s per publisher. The distribution of subscriptions and notifications follow a zipf law<fnref n="8" />; the probability of occurrence of the $i^{th}$ subscription/notification is given by $\frac{1}{i^\alpha}$. We will then aggregate the results obtained from several runs over a period of 20 minutes. As illustrated in Figures 5.9a and 5.9b, the group size has a low impact on the amount of control traffic; the bandwidth usage being indifferent to the group size, highlighting the benefits of maintaining membership information restricted to a cluster. When we consider the traffic associated with the event notification and (un)subscription routing (Figure 5.9c), we

<footnote n="8">8. Zipf distribution has been observed by stock quote providers [172].</footnote>
<figure><img src="image_101.png" /><figcaption>Figure 5.9 – Bandwidth usage associated with our notification system.</figcaption></figure>

can see that the volume of subscriptions and notifications decreases as their similarities (i.e., popularity ranking given by *alpha*) increases. This reveals the combined effect of (i) leveraging the subscription covering and (ii) the aggregation and filtering capabilities made possible thanks to our cluster-based routing.

<figure><img src="image_102.png" /><figcaption>Figure 5.10 – Adding a subscription organised in poset and tree.</figcaption></figure>

Following this we will measure the respective performances of, in term of latency, the main stages constituting the subscription and notification processes, *i.e.*, the addition of a subscription into a router repository and the filtering of an event notification. These results are then compared with the poset-based repository promoted by Siena [34], using the delay as an accurate indicator of the processing overhead incurred within each of the above stages. In order to test the impact of a complex subscriptions and notifications scanning, we further vary the subscription size (number of constraints) and notifications (number of attributes).

## Subscription Insertion

We measure the latency associated with adding a subscription into a repository by considering both our approach (Figure 5.10a) and the Siena approach (Figure 5.10b), with regards to a varying number of (i) subscriptions in the repository ([1, 200]) and of (ii) subscription filters ([1,20]). Results show that Siena performs better than our approach for a number of subscription constraints inferior to 5. To illustrate: if we consider 5 constraints per subscription filter, we observe in our approach an average time ratio per subscription of 0.35 and an upper limit of 283ms and a corresponding ratio of 0.44 and maximum of 369ms with Siena. This reflects the computing cost of indexing and summarising the new subscription. However our approach
outperforms Siena when the number of constraints per subscription is greater than 5 because the indexing and summarising costs are compensated by the significant gain induced by the research covering the new subscription. Indeed, if we consider 10 and 20 constraints per subscription filter respectively, we measure a lower latency (425ms and 499ms compared to 430ms and 761ms obtained with Siena) and slower ascending rate (0.495 and 0.5925 with our approach compared to the 0.525 and 0.87 experienced with Siena). Note that this difference, in terms of ascending rate and maximum latency, increases when we consider an increased repository size (i.e., number of subscriptions summarised), demonstrating that our event filtering system performs better in large-scale networks.

A similar trend is observed in Figure 5.11a. The delay incurred by our approach and Siena increases in a linear way, our system performing better when the number of subscriptions reaches a certain threshold (from 5 up to 7 filters per subscription) whose value depends of the value of *m*. As expected, the latency induced by the insertion of a subscription into the repository depends of the repository size. However such impact remains limited and is easily minimised by adequately configuring our event notification system and in particular the Bloom filters' sizes (§ 5.6.2).

<figure><img src="image_103.png" /><figcaption>(a) Adding a subscription into a router repository.</figcaption></figure>

## Notification Filtering

Next we compare the performances of the event notification filtering process in our solution (Figure 5.12) and Siena (Figure 5.13), considering varying repository sizes (Figures 5.12a and 5.13a), varying subscription sizes (Figures 5.12b and 5.13b) and varying notification sizes (Figures 5.12c and 5.13c). In all of the above cases we observe that the minima, maxima and ascending slope obtained by our approach are always inferior to those of Siena. If we look at Figures 5.12a and 5.13a, the difference is mostly due to the combined effect of using a summary and an index-based structure that allows the acceleration of the retrieval of the subscription(s) matching an incoming notification. The linear increase of the delay in Figures 5.12b and 5.13b is attributed to the sequential comparison of each subscription filter against each notification attribute; the lower rate of increase exhibited by our solution is due to the compact digest used to summarise the subscription.

Finally, in Figures 5.12c and 5.13c, we measure delay as a function of repository size ([1,200]) and subscription similarity (given by the ratio of covered attributes shared by the subscriptions which are stored in the router repositories). The delay decrease experienced by both our approach and Siena when considering an ascending similarity, is due to a reduced number of
<figure><img src="image_104.png" /><figcaption>(a) \#constraints=10.</figcaption></figure>

<figure><img src="image_105.png" /><figcaption>(b) \#constraints=10.</figcaption></figure>

<figure><img src="image_106.png" /><figcaption>(c) \#constraints=10 and \#attributes=10.</figcaption></figure>

<figure><img src="image_107.png" /><figcaption>(a) \#constraints=10.</figcaption></figure>

<figure><img src="image_108.png" /><figcaption>(b) \#constraints=10.</figcaption></figure>

<figure><img src="image_109.png" /><figcaption>(c) \#constraints=10, \#attributes=10.</figcaption></figure>

<caption>Figure 5.13 – Notification Matching with Siena.</caption>

matching.

We further supplement this filtering analysis with an evaluation of the traffic generated by
the event system.

**5.6.2 Evaluation of the folding**

Our objective is to empirically evaluate the effectiveness of the sizing (§5.6.2) and folding
(§5.6.2) of Bloom filters. The results presented hereafter, are averaged over at least 100 runs
and were obtained using a laptop with an Intel(R) Core(TM) 2 duo P8600 CPU of 2,40Ghz
and a cache size of 2 MB.

Off-line Planning

Our primary goal is to (i) investigate the ability to select a Bloom filter size that permits
many different foldings and (ii) analyse the related computing cost evaluated in terms of delay.
To this end, we explore the properties of smooth numbers, including their density and their
composition. Guided by our application, we limit the range of numbers that are investigated
to the practically relevant cases in which the size of the Bloom filters is determined so that the
probability of false positives is low. In our experiments, we first start by considering a range
of false positives rates that is low and narrow (see Figure 5.14). We then reduce the range (see
Figures 5.15 and 5.16) and show that there remain enough smooth numbers to pick the best
Bloom filter size. In addition, we investigate to what extent this reduction affects the composite
nature of the *y*-smooth numbers. Figure 5.14.a highlights the properties of *y*-smooth numbers by
<figure><img src="image_110.png" /><figcaption>(a) y-Smooth Numbers with an optimal $k = 4, y = 23$.</figcaption></figure>

<caption>(b) Power of the primes constituting the y-smooth numbers, $y = 23$.</caption>

<caption>(c) Amount of y-smooth numbers.</caption>

Figure 5.14 – Effectiveness of the Planning, considering $n = 1000, 3 \cdot 10^{-2} \le \rho^+ \le 5 \cdot 10^{-2}$.

<figure><img src="image_111.png" /></figure>

Figure 5.15 – Scalability of the Planning, setting $n = 1000, 3 \cdot 10^{-6} \le \rho^+ \le 5 \cdot 10^{-6}$.

<figure><img src="image_112.png" /></figure>

Figure 5.16 – Scalability of the Planning, considering $3 \cdot 10^{-8} \le \rho^+ \le 5 \cdot 10^{-8}, y = 23$.
<figure><img src="image_113.png" /><figcaption>Figure 5.17 – Folding a Bloom filter, $y=23$, $6247 \le m \le 7433$.</figcaption></figure>

plotting the y-smooth numbers as a function of the primes $p \le y$ that compose them and their respective powers. The Figure also provides a quantitative support for observing the density of the smooth numbers: 11.86% of the numbers are y-smooth numbers. This is more than sufficient for the selection of a satisfactory Bloom filter size. Furthermore, the density remains stable: for instance, only 9 numbers need to be explored before finding one 23-smooth number and only 101 before finding ten 23-smooth numbers. It is also visible that the smallest primes are mostly present in the composition of the smooth numbers. They⁹ are typically compensated by larger powers: this is illustrated in Figure 5.14.b where power is plotted as a function of the prime. This means that the Bloom filter can be folded many times and in a smooth fashion. In Figure 5.14.c a saturation of the amount of y-smooth numbers is observed when increasing y. At a certain point it is unnecessary to continue increasing y because the time to search for y-smooth numbers grows significantly (Figure 5.14.c) whereas the quantity of smooth numbers grows only slightly.

By restricting the range of the false positives rate from $\rho^+ \in [3.10^{-4}, 5.10^{-4}]$ in Fig. 5.15 to $\rho^+ \in [3.10^{-8}, 5.10^{-8}]$ in Fig. 5.16, we see that the amount of smooth numbers naturally decreases as the investigated range narrows. However the amount of smooth numbers remains significant (Fig. 5.16c): if the number of hash functions $k$ is smaller than the optimal number of hash functions $k = 4$ (see Figures 5.15.a and 5.15.b), the amount of y-smooth numbers is comparatively much greater. This illustrates the trade-off made between time ($k$) and space ($m$): an attempt to improve the performance of one is done at the expense of the other. Nevertheless, as demonstrated in Figure 5.16.c, a sufficient amount of y-smooth numbers is still available even considering a worst case, i.e., a very narrow range of false positives rates. It can also be observed that the quantity of smooth numbers is proportional to the number of elements $n$ that are added to the Bloom filters, because the amount smooth numbers within an interval $[m_1, m_2]$ is proportional to the number of items $n$ to be added. Indeed, $m_1 - m_2 = \frac{n}{\ln(2)^2} \ln(\frac{\rho_1^+}{\rho_2^+})$ with $\rho_1^+$ and $\rho_2^+$ denoting the false positives rate corresponding to $m_1$ and $m_2$, respectively. In the following experiments we study the folding of a range¹⁰ of sizes for a Bloom filter, which is given by [6247,7433].
<figure><img src="image_114.png" /><figcaption>(a) Foldability of a (counting) Bloom filter, $m/m' \le 100$.</figcaption></figure>

<figure><img src="image_115.png" /><figcaption>(b) Delay for a Bloom filter.</figcaption></figure>

<figure><img src="image_116.png" /><figcaption>(c) Compression ratio of a Bloom filter.</figcaption></figure>

Figure 5.18 – Folding and Compression and Decompression of a Bloom filter, $6247 \le m \le 7433$.

On-Line Folding

In order to evaluate the performance of our lossy-compression we compare the computation cost, measured in terms of execution time, to the space economy, expressed as a compression ratio (and corresponding to the original size of the Bloom filter divided by its folded size). We also compare the cost and space economy of our lossy compression against the popular compression format Zlib<sup>11</sup>[44] that creates a zip file. Our goal is to give the cost/gain associated with the folding relative to the Zlib compression even though the two compression methods are somehow not comparable because our folding-based lossy compression is specific to Bloom filters, while Zlib provides a lossless compression for general classes of data including *e.g.*, text. We use MurmurHash<sup>12</sup>, a non-cryptographic hash function which is typically used for hash-based lookup. We consider the delay associated with the folding of a Bloom filter (Figure 5.17.a) and of a counting Bloom filter (Figure 5.17.b). This delay is expressed as a function of the size of the Bloom filter (*m*) and of the folding ratio *m*/*m*'. The Bloom filter and the counting Bloom filter both exhibit the same behaviour during folding. The easily discernible lines are related to the repetitive combinations of the same primes: the lower *y*, the higher the repetition. Although it is less observable in lower folding ratios (Figure 5.18.a), an in depth analysis showed us that this behaviour remains unchanged regardless of the folding ratio. Returning to Figures 5.17.a and 5.17.b, the latency, as expected increases as a function of the Bloom filter size (recall that the theoretical cost is $O(um/f)$, with $u = 1$ for a pure Bloom filter) even though the quantitative cost is several times higher in average for a counting Bloom filter. This points out the price to paid for handling counters rather than bits. The arithmetic addition required to fold a counting Bloom filter is particularly costly compared to the bitwise OR used with Bloom filter. Considering the lossless compression of a Bloom filter (Figure 5.18.c) shows us that the compression ratio expressed as a function of the number of elements *n* in the Bloom filter decreases drastically and stabilises as the Bloom filter is populated. Meanwhile the delay related to the lossless compression remains stable (Figure 5.18.b) and lower than the folding delay (Figure 5.17), but the two delays are still comparable for a given folding ratio. Nonetheless, the ratio *m*/*m*' is greater with the folding than with the lossless compression. Specifically (see Figure 5.18.c), the highest compression ratio is obtained with an empty Bloom

<footnote n="9">9. Similarly, a high prime is compensated by either few small primes and/or smaller powers.</footnote>

<footnote n="10">10. This range is the one used in Figure 5.14.</footnote>

<footnote n="11">11. http://www.zlib.net/</footnote>

<footnote n="12">12. https://sites.google.com/site/murmurhash/</footnote>
filter (i.e., a vector of entirely set to 0) whereas the lowest ratio stands for the highest<fnref n="13" /> value of $n$ (here, 1000). The monotonic decrease and the small compression ratio reflects the difficulty of compressing random data (i.e., a Bloom filter wherein some bits are randomly set to 1) and the practical advantage of a folding-based lossy-compression.

## 5.7 Conclusion

The IoT is characterised by a large number of *Things* scattered around the world that need to exchange messages over the Internet. The provision of a reliable and timely means of communication over a wide area network is still a critical and problematic issue. We have addressed this issue through the introduction of an event notification system that supports a lightweight content-based filtering and that relies on a self-configuring grouping service that dynamically organises the event delivery structure. Our content-based event notification system supports a scalable group communication and novel lightweight event filtering scheme that keeps the load on routers to a minimum. Our event notification system is automatically deployed without requiring human intervention and is fault-tolerant as it adapts dynamically to any permanent or transient network failure.

It is worth stressing that the routers traversed by a notification/(un)subscription dedicate significant time and effort to search the matching subscriptions while the search is often the same for all the routers. If one router – ideally, the first router receiving the notification/(un)subscription – can indicate how to access the subscriptions, then subsequent routers do not have to repeat the same time-consuming subscription search. In order to support such an approach without congesting the network and routers, we represent the subscription as highly compact Bloom filters. In this way it is possible to effectively filter event notifications. In addition, we propose a hash-based indexing structure that allows subscriptions to be quickly retrieved, possibly based on the provided indications.

Still, finding the correct Bloom filter size is challenging, because the quantity of data must be estimated in advance to ensure that the required false positive rate is always respected. In general practice this leads to a situation in which the Bloom filter is oversized. In order to overcome this issue we propose – and further evaluate the performance of – a lossy compression system that consists of folding the Bloom filter. We show that the foldability depends on the the exact size of the Bloom filter, thereby establishing an interesting link between number theory and Bloom filters. More precisely, we propose to select a $y$-smooth number due to their high density and ease of production, which derives from their simple multiplicative structure. We show that selecting $y$-smooth numbers is advantageous since they allow a large number of possible folding combinations. We then present an algorithm based on a sieve of Eratosthenes, which is efficient with regards to the envisaged sizes of Bloom filters. Once properly sized, the Bloom filter can be folded very efficiently so that the false positive/negative rate is always met. We further analyse the ease of selecting a size for Bloom filters that allows a large number of folds and evaluate the associated costs. This led us to empirically explore the properties of $y$-smooth numbers, their density and composition.

Overall, Bloom filter folding is advantageous in two application scenarios. The first assumes a Bloom filter stored in memory, which needs to be folded; this is advantageous, for example, if the Bloom filter was initially over-sized. The second scenario, and the main motivation for our work, deals with the transmission of a Bloom filter, which should be folded prior to transmission

<footnote n="13">13. Although a highly populated Bloom filter would exhibit a high compression ratio, it would be subject to an unacceptable false positives rate.</footnote>
in order to minimise bandwidth usage and communication delay. After appropriate sizing, the remaining problem in both scenarios is the determination of the applied folding rate in order to achieve the required false positive/negative rate. Ultimately this folding and filtering problem is a classic compromise between time (computation) and space (storage and communication): increasing the performance of one is inevitably to the detriment of the other.
Conclusion

The forward-thinking academic John Culkin remarked that “we become what we behold. We shape our tools and then our tools shape us.” The truth behind this observation written in 1967, has perhaps never been more obvious than it is today. We are witnessing a unique stage in mankind’s technological history and just as technology evolves – and continues to evolve – so do we too change with it. From this perspective, the IoT has greatly increased our intercon- nectedness and thereby our understanding of the physical world around us. The shift towards widespread use mobile, consumer-centric smartphones is making our immersion with comput- ing into a permanent, and somehow dependant, state by permeating practically all aspects of our daily lives. The real and the virtual have remained relatively dissociated since the dawn of information technology, but are nowadays becoming increasingly intertwined.

Shaped by the Internet of Things, my own research journey is anchored in these last decades, anticipated by Mark Weiser (1988), which has predicted a world in which "technology recedes into the background of our lives." Since then, the IoT ecosystem has been successfully applied to enhance our interconnection with physical spaces. Due to its ubiquity, the IoT might well aspire to become the lingua franca of a newly emerging generation of people long immersed in an IoT-landscape. However the path leading towards ubiquitous computing raises some challenges and significant research efforts remain to be invested as tribute to the discrepancy in the quality of data and services contributed by the Things.

6.1 Summary of Contributions

In an increasingly interconnected IoT where Things freely exchange data and offer services that are accessible through open and poorly secured interfaces, the IoT raises some concerns related to reliability, faithfulness and accuracy. In the last mile, IoT networks are predominately driven by – and built upon – wireless networks (Near Field Communication or slightly longer WiFi or Bluetooth-enabled technologies) that: (i) allow greater access to outsiders that exploit vulnerabilities and may cause significant damage, and (ii) make it easier for insiders to avoid identification. Monitoring the behaviour of things and the network is necessary in order to spot intrusions, coming from either inside or outside the network. Intrusions manifest in the forms of: (i) attack behaviour which differs to that of a normal user, or as (ii) a sequence of actions undertaken by the attacker that characterises the attack pattern. We have covered both forms of attacks and explored signature-based and anomaly detection, focusing on the communication and computing infrastructures that span different scales from the MANETs composed of per- sonal laptops equipping mobile users to RFIDs tags that are highly miniaturised. Unlike mobile laptops that may undertake advanced analytics, RFID tags are passive and unintelligent; these features imply their inability to monitor and understand their environment. In each case, we have considered the nature of the monitored system (network/computer/object and supplied service) and tailored the detection system accordingly. To secure MANETs, we have introduced a distributed signature-based Intrusion Detection System (IDS) intended to monitor the attacks against the OLSR routing protocol. We noted that the device has a limited observability and
that the partial network view, which is gained thanks to other peers, is questionable in terms
of reliability. To address this issue we have devised an entropy-based trust system that deals
with uncertainties and incompleteness involved in trust relationships, leveraging a statistical
gathering approach that gracefully and incrementally gathers observations without sacrificing
detection accuracy. As a complement we have explored anomaly detection to identify any devi-
ations from normal behaviour. Relying on Kohonen maps, which constitute an efficient way for
automatically categorising, our IDS further compares the tagged behaviour against the normal
user's behaviour as expressed in the user's profile.

A lack of security is not the only flaw in the IoT. The loss of data quality is a highly debated issue within the academic and practitioner communities who often deal with the unintentional corruption of sensed data. A conflict between end-users' expectations over the data and the reliability of data gleaned from low-cost or DIY sensing devices is often present. Sensor calibration in the field is essential to overcoming this issue as it: (i) ensures a proper operation of the sensing devices, and (ii) deals with varying external conditions (e.g., solar radiation, freezing) and other factors (e.g., activity of the end user) that affect the measurements over time. Sensor calibration has received surprisingly little attention from researchers. We have thus proposed a holistic approach to reduce the cost associated with calibration in smart spaces at scale, from the fixed Things that make up the IoT infrastructure to the mobile Things that people carry. We have developed a plan for the calibration of a large number of often inaccurate sensors in a smart space using high-integrity reference sensors that are mobile, so as to maintain an adequate sensing accuracy while minimising the required effort from the mobile calibrators. We have in turn generalised the automated calibration to the multi-party case to sustain a macro-calibration. In particular we have conceived a distributed, opportunistic macro-calibration system that leverages the presence of the nearby crowdsensors that monitor the same physical phenomenon, which we have shown improves the accuracy of the performance sensing application. Such an approach to calibration is particularly well suited to mobile crowdsensing scenarios in which the crowd senses and meets in public places.

Opportunistic crowdsensing shows a great potential to monitor the physical environment in a cost-effective and dynamic way by empowering people to contribute as part of their daily life. As such, crowdsensing is gradually becoming a cost-effective complement to fixed wireless sensor networks. The major emerging challenge currently facing mobile crowdsensing is related to the gathering and processing of an ever-increasing amount of data collected across time and space, with the intention of making the best sense of it so as to provide citizens and communities with relevant value-added information. In practice, people's mobility makes the crowdsensing contribution unevenly distributed over space and time, thus requiring the post-processing of sensing data on the cloud. As the number of contributors grows, the increasing number of observations that the crowdsensing platform must process becomes challenging: the high network and financial cost associated with a cloud-centric system hinders the widespread use of crowdsensing and the high computational cost required makes the modelling of the environmental phenomenon intractable. Given the growing volume of data involved to cover urban-scale areas, restraining the increasing operational cost of the cloud-assisted infrastructure and keeping to a minimum the resource consumed by the hand-held devices are a prerequisite. We have addressed this issue by exploiting the ever-increasing computing capacity of smartphones by evenly distribute the collection, interpolation and aggregation associated with the sensing data to powerful end devices. To this end we have introduced a crowdsensing middleware, which supports a novel in-network collaboration strategy that enhances the quality of the data before their transfer to the cloud, while reducing the related communication cost and resource consumption. The middleware tailors a set of utility functions that assess to what extent a device should carry out
a given crowdsensing task while achieving a trade-off between the benefit for all (aka for the
group) and the related cost for the device. Rather than applying a naive combination (e.g., aver-
aging) of the data collected by the crowdsensors that would actually degrade the quality of the
sensing data, our middleware performs an advanced inference. A Crowdsensor may establish a
very precise interpolation of the regions it covers. Individual interpolations are then aggregated
on the cloud, which renders the overall interpolation on the cloud much more tractable.

We observe a paradigm shift towards "edgeness" and information-centric networking that supports an early edge decision-making. In this perspective we have proposed a content-based publish/subscribe system that supports flexible and scalable messaging among Things (e.g., sensors and actuators) and applications, delivering information across the wide range network to interested consumers as the amount of IoT devices increases and spreads geographically. We have built a cluster-based and hierarchical delivery structure that scales and tolerates failures while achieving both low latency and efficient use of resources. In the delivery structure, routers (a.k.a cluster heads) dedicate significant effort to filter and forward the messages (i.e., event notifications and (un)subscriptions). To reduce the routers loads we have proposed to help routers by including in the message the filters that need to be applied. In order to support such an approach without congesting the network, we have compacted filters. As a result, the flow of event notifications produced by any Thing can be filtered and distributed to provide situation-awareness and trigger actions accordingly.

In this manuscript I have presented a snapshot of my research as it stands today, keep-
ing in mind that the development of a robust and resilient IoT remains a daunting task and
many improvements are needed. From hardware to middleware, data collection to analysis and
decision-making, actual practice to guiding theory, much works lies ahead in the creation of an
efficient, resilient and ultimately life-enhancing IoT.

**6.2 Perspectives**

Conveying and processing the massive amount of data that is produced by the IoT – and in
particular by crowdsensing applications – has become a major issue in terms of the management
and operation of the underlying applications and networks. Conventional cloud computing
systems and current communication architectures must be adapted and optimised to efficiently
process the very large volumes of data generated by the IoT, which will continue to grow in
time and space.

Further solutions and related optimisations need to be designed – acknowledging that some
services can be moved close to smartphones and that much of the data can be stored or even
analysed and filtered at an early stage to limit the amount of data transferred. Data, services and
underlying infrastructure must also be secured in a complementary fashion. I intend to address
these issues by exploring several research directions, ranging from the design of collaborative
and distributed systems capable of supporting crowdsensing applications that operate on a
large scale to the development of a secure environment for these applications.

Towards Virtual(ised) Crowdsensing

The data supplied by sensing applications, including mobile crowdsensing apps, contain insights
about the physical and social environment and concerns user's activities and situation. Our past
work has shown us that contributed data are often unusable unless first compared, fused, con-
textualised, enriched, classified *ect*. Somehow, sensors are not intended to operate individually;
they should not be considered as an autonomous pieces of hardwares and softwares capable of
monitoring a physical or social phenomenon on their own. Sensors are heterogeneous and oper-
ate at different scales spanning the nano, personal, and urban. Yet they are domain-specific and
task-oriented: the mass of information they produce is specific to a sensor model, dedicated to
a particular use(r), and mostly tailored to a given application with little or no possibility of use
with other applications. To overcome this limitation we must abstract the set of physical sen-
sors along with the operations performed on them to increase the data usability. The aim is to
define and support virtual sensors that supply measurements that are not directly available by
combining the measurements provided by a group of heterogeneous sensors. This also involves
broadening the types of context we may thus characterise and integrating other sources of infor-
mation of a social (social networks) or environmental (such as open street maps) nature. From
this perspective it is crucial to define new methods of cooperation between physical and virtual
sensors capable of performing complex and virtual tasks sustaining the enrichment, analysis,
fusion, interpretation and transformation of data provided by both virtual and physical sen-
sors, including other sources of relevant information. During the synthesis and comparison of
the sensed information, the context/situation dependence and multi-dimensional nature of the
sensed data cause a non-stationarity, which is not adequately addressed by conventional least
square regression and derived interpolation methods. Rather than breaking down the data,
using for instance multiple regressions to deal with the multi-dimensionality of the context, we
propose an exploration of weighted regression [29] and moving weighted windows over the data,
thereby estimating groups of coefficient values that fit the samples. This method first selects
a bandwidth for an isotropic spatial weights kernel, typically a Gaussian kernel with a fixed
bandwidth chosen by leave-one-out cross-validation. The choice of the bandwidth [28] is very
demanding and requires investigation, as regressions must be fitted at each step.

Mobile and edge computing

Delivering seamless connectivity and communication to mobile users and ensuring sufficient quality of service despite the mobility of users/things remains a vast area of research, of which only certain challenges have been solved thus far. Our approach to improving communication reliability relies on exploiting multiple access networks that should be further adapted to deal with the dynamic aspects induced by mobility. As far as the mobile IoT is concerned, intelligent and opportunistic clustering helps to structure the network architecture; "intelligent gateway placement" techniques are prerequisites to enabling a smooth connection. Still there is a need to establish the most suitable path based on dynamic network properties (such as link quality) so as to convey packets to (mobile) gateways, taking into account the Braess paradox that often occurs as certain gateways act as vortexes. Supporting algorithms lead to an overuse of certain paths and therefore severe congestion, e.g., with video [27]. Rather than merely selecting the optimal path our approach will aim at distributing/splitting the information using game theory. Although theory and algorithms for game have been extensively studied, a majority of the approaches [86] assumes that players are aware of the overall game state and previous moves before playing. This not realistic with IoT: Things (a.k.a players) have a limited observability and do share a consistent knowledge on their previous or ongoing actions. Incomplete knowledge introduces uncertainty that needs to be modelled [161], a critical issue that we address by finding an equilibrium without necessarily needing information regarding the presence of other data streams, the strategies implemented, or the paths taken by others. In addition, content fragmentation, network coding, joint and adaptive routing are all needed to effectively exploit the diversity of access paths while taking into account factors such as content specifics, user priorities and reliability.
On securing virtualised infrastructures

Networks are made up of virtualised infrastructures – ranging from cloud computing to NFV systems – that are constantly evolving and, as a result, highly complex and thus subject to vulnerabilities. Their dependability/security is contingent on our skill at detecting these vulnerabilities and in turn updating virtualised systems as soon as new threats are discovered. To this end it is necessary to understand how the attacker compromises the system, what vulnerabilities they exploit, what actions they undertake, and where vulnerabilities are located at the system level. Detecting and combating attacks in real time for virtualised infrastructures is tricky due to their modular structure, elasticity, rapid evolution (materialised by frequent upgrades), and containerization as isolated components comparable to black boxes.

While classification techniques are becoming popular to resolve problems related to anomaly
detection [50], assuming the availability of a sufficiently large, diverse and labelled data set for
a virtualised infrastructures is unrealistic. With this regards, unsupervised learning has to be
privileged and new statistical profiling techniques using dynamic/multiple regressions need to
be devised. Importantly, the model need to be pre-trained to properly reconstruct multivariate
time series, using e.g., stacked denoising auto-encoders [20]. This causes significant challenges
due to the anomalies' variability and the need for designing adapted or dedicated models. Several
sources of information should be collected and correlated in order to derive features, keeping
in mind that the relationships between them are highly complex while taking into account
real-time requirements. Rules must define the abnormal or normal character of a behaviour by
comparing predicted and real behaviours. The simplest approach to setting a threshold based
on (Euclidean) distance is likely to lead to many false positives, especially with noisy data.
It is therefore crucial to design new methods based on statistical and probabilistic profiling
approaches while also defining concrete policies to be applied to containers in order to create a
line of defence that can be applied on a large scale and on the fly.
<figure><img src="image_117.png" /></figure>