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

HAL
open science

# Developing robust Iot to monitor smart spaces at scale

Francoise Sailhan

► To cite this version:

Francoise Sailhan. Developing robust Iot to monitor smart spaces at scale. Computer Science [cs]. Saclay, CNAM, 2021. tel-03175539

HAL Id: tel-03175539

https://cnam.hal.science/tel-03175539

Submitted on 20 Mar 2021

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

Public Domain
Mémoire présentée en vue de l'obtention de
l'habilitation à diriger des recherches
Université Paris-Saclay

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

Discipline : Informatique

Developing Robust IoT to
Monitor Smart Spaces at
Scale

Habilitation à diriger la recherche

PAR : Françoise Sailhan

Sous la direction de,

MEMBRES DU JURY:

**Rapporteur:** Julien BOURGEOIS, Prof. des Universités, Univ. de Franche Comté,

**Rapporteure:** Siobhán CLARKE, Prof. des Universités, Trinity College,

**Rapporteure:** Nathalie MITTON, Directrice de Recherche, Inria-Lille,

**Marraine:** Valérie ISSARNY, Directrice de Recherche, Inria-Paris,

**Examinatrice:** Nalini VENKATASUBRAMANIAN, University of California,

**Présidente:** Karine ZEITOUNI, Prof. des Universités, Université Paris-Saclay,

Date de soutenance : 14 janvier 2021
<figure><img src="image_3.png" /></figure>
# Contents

<table><thead><tr><th></th><th></th><th></th></tr></thead><tbody><tr><td>1</td><td>Introduction</td><td>1</td></tr><tr><td>1.1</td><td>Context and Related Opportunities</td><td>1</td></tr><tr><td>1.2</td><td>Challenges of designing and deploying an IoT system</td><td>2</td></tr><tr><td>1.3</td><td>Outline</td><td>3</td></tr><tr><td>2</td><td>Into the Wild - Intrusion Detection</td><td>7</td></tr><tr><td>2.1</td><td>Introduction</td><td>7</td></tr><tr><td>2.2</td><td>Signature-based Intrusion Detection in MANETs</td><td>9</td></tr><tr><td>2.2.1</td><td>Attacks Threatening the OLSR Protocol</td><td>9</td></tr><tr><td>2.2.2</td><td>Attack Detection</td><td>13</td></tr><tr><td>2.2.3</td><td>Trustworthiness Evaluation</td><td>15</td></tr><tr><td>2.2.4</td><td>Reducing the Cost of Investigations</td><td>18</td></tr><tr><td>2.3</td><td>Anomaly Detection</td><td>19</td></tr><tr><td>2.3.1</td><td>RFID System supporting access control</td><td>20</td></tr><tr><td>2.3.2</td><td>Anomaly Detector</td><td>21</td></tr><tr><td>2.4</td><td>Performance Evaluation</td><td>24</td></tr><tr><td>2.4.1</td><td>Signature-based Intrusion Detection</td><td>24</td></tr><tr><td>2.4.2</td><td>Trustworthiness and Confidence</td><td>27</td></tr><tr><td>2.5</td><td>Conclusion</td><td>28</td></tr><tr><td>3</td><td>Enhancing the Observation Quality through Calibration</td><td>31</td></tr><tr><td>3.1</td><td>Introduction</td><td>31</td></tr><tr><td>3.2</td><td>Planned Calibration of an IoT Infrastructure</td><td>33</td></tr><tr><td>3.2.1</td><td>Multi-Sensor Calibration Planning</td><td>34</td></tr><tr><td>3.2.2</td><td>Multi-Sensor Calibration Optimisation Problem</td><td>36</td></tr><tr><td>3.2.3</td><td>Solutions and Derived Algorithms</td><td>37</td></tr><tr><td>3.3</td><td>Robust Multi-Party calibration</td><td>40</td></tr><tr><td>3.3.1</td><td>Multivariate Linear Regression</td><td>41</td></tr><tr><td>3.3.2</td><td>Multi-hop, Multi-party Calibration</td><td>44</td></tr><tr><td>3.4</td><td>Evaluation</td><td>48</td></tr><tr><td>3.4.1</td><td>Planning the Calibration</td><td>48</td></tr><tr><td>3.4.2</td><td>Multi-Hop Multi-Party calibration</td><td>51</td></tr><tr><td>3.5</td><td>Conclusion</td><td>57</td></tr><tr><td>4</td><td>Leveraging Crowd sensors to support Context-aware and Cost-effective Crowd-sensing</td><td>63</td></tr><tr><td>4.1</td><td>Introduction</td><td>63</td></tr><tr><td>4.2</td><td>Context-Awareness sustaining a Collaborative Crowdsensing</td><td>65</td></tr><tr><td>4.2.1</td><td>Context Characterisation</td><td>66</td></tr><tr><td>4.2.2</td><td>Feature Selection</td><td>67</td></tr><tr><td>4.2.3</td><td>Classifier Initialisation</td><td>68</td></tr><tr><td>4.2.4</td><td>Online Personalising</td><td>69</td></tr><tr><td>4.3</td><td>Assessing the Crowdsensor Utilities</td><td>70</td></tr></tbody></table>
<table><tbody><tr><td>4.4</td><td>Opportunistic Aggregation and Interpolation</td><td>73</td></tr><tr><td>4.4.1</td><td>Spatio-temporal Interpolation</td><td>73</td></tr><tr><td>4.4.2</td><td>Opportunistic Aggregation</td><td>75</td></tr><tr><td>4.5</td><td>Performance Evaluation</td><td>76</td></tr><tr><td>4.5.1</td><td>User-centric Context Inference</td><td>76</td></tr><tr><td>4.5.2</td><td>Group-based Collaborative Crowdsensing</td><td>82</td></tr><tr><td>4.5.3</td><td>Interpolation and Aggregation</td><td>85</td></tr><tr><td>4.6</td><td>Conclusion</td><td>90</td></tr><tr><td>5</td><td>Information centric Networking</td><td>93</td></tr><tr><td>5.1</td><td>Context and Motivation</td><td>93</td></tr><tr><td>5.2</td><td>Group-based Publish-Subscribe System</td><td>95</td></tr><tr><td>5.2.1</td><td>Underlying Group Communication</td><td>95</td></tr><tr><td>5.2.2</td><td>Cluster-based Routing</td><td>96</td></tr><tr><td>5.3</td><td>Notification and Subscription Representation</td><td>97</td></tr><tr><td>5.3.1</td><td>Notification and Subscription Formats</td><td>97</td></tr><tr><td>5.3.2</td><td>Subscription Organisation - State of the Art</td><td>99</td></tr><tr><td>5.4</td><td>Enhanced Forwarding</td><td>100</td></tr><tr><td>5.4.1</td><td>Preventing Intermediate Routers From Performing Duplicate Searches</td><td>103</td></tr><tr><td>5.4.2</td><td>Prefiltering with an Index-based Subscription Repository</td><td>105</td></tr><tr><td>5.4.3</td><td>Synthesis</td><td>107</td></tr><tr><td>5.5</td><td>Folding Bloom Filters</td><td>108</td></tr><tr><td>5.5.1</td><td>Finding y-Smooth Numbers</td><td>109</td></tr><tr><td>5.5.2</td><td>On-Line Folding Strategy</td><td>113</td></tr><tr><td>5.5.3</td><td>Folding</td><td>114</td></tr><tr><td>5.6</td><td>Performance Evaluation</td><td>116</td></tr><tr><td>5.6.1</td><td>Event Notification System</td><td>116</td></tr><tr><td>5.6.2</td><td>Evaluation of the folding</td><td>119</td></tr><tr><td>5.7</td><td>Conclusion</td><td>123</td></tr><tr><td>6</td><td>Conclusion</td><td>125</td></tr><tr><td>6.1</td><td>Summary of Contributions</td><td>125</td></tr><tr><td>6.2</td><td>Perspectives</td><td>127</td></tr><tr><td colspan="2">Bibliographie</td><td>131</td></tr></tbody></table>
# Introduction

## 1.1 Context and Related Opportunities

The Internet of Things (IoT) has emerged as a distributed, self-healing and large-scale architecture composed of a variety of objects that monitor and affect their environment. This combination of sensing and actuation capabilities holds great promise as the enabler of a wide spectrum of applications, e.g., smart space (e.g., building surveillance and ecology-friendly control), emergency response and environmental monitoring. Instrumented with sensors, RFIDs and actuators, smart spaces (including the residents, employees) provide valuable information that serve supporting e.g., access control [66, 26], inform rescuers in case of emergency [137, 12, 56], provide assisted/enhanced living [179], ect.. In the area of environmental monitoring for example, large cities have made progress, in recent years, in monitoring and assessing the biological and ecological impacts of pollution to respond appropriately, from the political to the individual level. Cities have traditionally relied on sensing stations that gather observations (e.g., atmospheric conditions, noise levels, temperatures). Recently cities have also begun taking advantage of crowdsensing movement, wherein users (citizens, groups, communities) rely on the small and low-cost sensors embedded in –or connected to– their smartphones so as to help identify environmental problems. IoT-based applications build on a communication and computing infrastructure spanning different scales, from smartphones embedding or connecting to sensors (a.k.a. detectors) and actuators (e.g., electromechanical and/or software-based devices), enabling them to capture, measure, react and communicate with their environment, all the way to large-scale networks, capable of disseminating critical information from event sources to multiple recipients. At the network edge, some wireless networks (e.g., Device-to-Device and wireless sensor networks) with no specific underlying infrastructure in place, connect diverse Things hosting sensors and actuators (e.g., mobile phones, vehicles, smart clothing, motes). Interestingly, these networks mirror ad hoc networks — some of the nodes are battery powered and communicate via wireless connections, possibly involving intermediate/proxy-nodes and using multi-hop routing.

So far many specific, distributed, energy-/memory-/computationally-aware protocols, systems and applications have been proposed to enhance the collection and processing of the increasingly massive amount of available information in the IoT. However as the range of applications extends to the fields of industrial and mission-critical systems, additional assurance requirements related to accuracy, reliability and security must be considered. Accomplishing the challenging task of Developing Robust IoT therefore necessitates: (i) supporting accurate and resource-efficient sensing and actuation capabilities and (ii) providing efficient and reliable communication among Things/users across heterogeneous and volatile networks from the edge up to the cloud.
## 1.2 Challenges of designing and deploying an IoT system

While expectations are high for the wide applicability of IoT systems, the need to monitor phenomena at unprecedented scale is far from being a trivial concern especially considering that IoT applications must remain dependable under any circumstance (e.g., despite disruptions, harsh conditions or even attacks). IoT system applications are subject to a variety of faults/threats, spanning hardware, software and networking layers. Given that the IoT ecosystem is information-centric (i.e., Things generate a torrent of information delivered to many recipients that in turn must filter, customise, and process it on the fly), we are mostly concerned with the two following classes of impairments:

*   **Communication faults** - Any intentional or accidental attempt to disrupt the flow of information seriously jeopardises IoT systems. IoT systems are actually very difficult to insulate against communication faults due to the openness of the wireless communication medium, coupled with the cooperative nature of the network, which render protocols and related applications easy to compromise. In this regards, detecting any misuse or anomaly (i.e., deviations from the normal behaviour) that threatens the networking structure – from edge to core networks – is of critical importance. In this regard we began (i) investigating the detection of misuses and anomalies. Our attention was specifically directed at detecting attempts to disorganise the routing or disturb the data flow relaying. In addition we aimed at detecting anomalies corresponding to certain types of misbehaviour (e.g., unusual and potentially unauthorised access to some data, unexpected presence in a smart building).

*   **Information-related faults** - The collection of data of sufficient quality is a major challenge facing the IoT. Many sensors in use are low cost, mass produced and are made of off-the-shelf components and their relatively low accuracy challenges the relevance and accuracy of the collected sensory data. In addition, the exposure of the sensors to natural perturbations leads to questioning the accuracy of the observations. Correcting inadequate observations in order to derive proper conclusions is therefore of prime importance. Meanwhile, knowledge of the sensors' context is vitally important in order to discover whether the sensing devices are in a position that enables sensing, instead of interfering with it. In response to this challenge we propose to: (i) calibrate the inexpensive (and often inaccurate) sensors and (ii) fuse the information provided by multiple sensors so as to supply more accurate/reliable observations (as opposed to trying to improve the reliability of the individual devices involved).

While IoT enables environmental monitoring at an unprecedented scale (leveraging calibrated sensors and information fusion), it also involves significant communication, computation, and, therefore, financial costs due to the reliance on cloud infrastructures for processing the spatio-temporal data. The situation is actually worsen due to the fact that IoT systems require (i) a low-level control loop to support timely and situational-aware sensing and actuation and (ii) a higher-level control loop to infer a physical phenomenon as a whole, i.e., at macro scale and across time. As an illustration, knowledge of the level of ambient pollution (e.g., noise level, air quality) within a particular area helps citizens measure their own exposure to pollution. An extended control loop is also needed so that citizens, authorities and decision-makers can design adequate policies. As an alternative to the centralised gathering and analysis of crowdsensing observations through such a high-level control loop, we introduce a crowdsensing system that functions on a collaborative model, operating primarily at the very edge, i.e., empowering smartphones so as to enhance the quality of the data transferred to the cloud while
reducing the related communication cost and resource consumption. We adopt an information-
centric paradigm in which the information drives decision-making. To achieve this we build
upon a publish/subscribe system that supports a loosely-coupled communication towards/from
Things/users across heterogeneous and volatile networks in which data flows are governed by
both user interests and data content.

1.3 Outline

This document brings together a large portion of the research I have been conducting over a
period that spans 2005-2020. After completing my PhD in July 2005 at Inria on the subject of
service discovery in mobile ad hoc networks, my work has covered several topics at the heart
of what is today the (mobile) IoT, with an emphasis on the effective gathering of accurate
sensor data. However, I do not detail all of my work thus far; in particular, my industrial
research on network management [145, 15, 14, 48, 139, 142, 59, 80] and my work on sentiment
analysis [104, 103, 89] are deliberately omitted. This manuscript is instead specifically focused
on my research contributions to the design of robust distributed IoT systems supporting the
accurate monitoring of urban-scale phenomena, leveraging sensors and actuators embedded
in or connected to devices (e.g., smartphones or motes). The focus of this research is the
support of robust routing, observation gathering and processing and overcoming misbehaviour
or anomalies, while involving end-users as little as possible.

The core of the manuscript is structured around the following chapters, each covering a
specific theme of the aforementioned research.

**Chapter 2 – Into the Wild: Resource-Efficient Intrusion Detection for Secure IoT**

* **Publications**: [99, 6, 8, 7, 141, 146, 66, 22, 138, 126].

* **Supervision**: Mouhannad Alattar (PhD), Khaled Gari (Master student), Christophe Pitrey (Master student).

* Project on the topic: FP7 Securinet.

The starting point of my research concerns the detection of intrusions that threaten an
IoT system. This usually consists of diverse networks, ranging from *ad hoc* networks dealing
with mobile devices, highly constrained RFID (Radio Frequency Identification) systems and
also the core networks. In order to protect the networks against malicious activities, we ex-
plore two complementary approaches that relate to the detection of misuses and anomalies.
We introduce a misuse detection system [7, 146, 127], which is intended to detect an attack
based on a predefined attack signature (*i.e.*, a series of operations threatening security). Our
anomaly-based detection [66, 22] consists in establishing the “normal”<fnref n="1" /> behaviour of the system
to be protected and identifies an anomaly as a deviation between a given observation(s) and the
pre-established normal behaviour. With our misuse detector, our primary objective is to model
the general form of attacks and identify the related attack signatures. Our signature-based in-
trusion detector distinguishes itself with respect to the state of the art because it uses logs and
does not inspect the network traffic. Relevant logs are categorised and exchanged according to
their degree of importance. An additional issue is the cost associated with the acquisition and
processing of the logs. Our approach [99] to reducing related resource consumption is based on
probabilistically questioning neighbours and controlling the flow of logs gathered through the

<footnote n="1">1. Alternatively, the “abnormal” behaviour of the system can be expressed.</footnote>
use of statistical parameters. We further establish the trustworthiness [6] of the interrogated
node(s) and filter incorrect logs supplied by misbehaving ones. We then design an anomaly
detection system [66] that provides early warnings about anything out of the ordinary (e.g.,
zero-day attacks). Leveraging advanced machine learning techniques, our detector automati-
cally categorises (normal) activities without supervision.

**Chapter 3 – Enhancing the Observation Quality through Calibration**

• **Publications**: [148, 179].

• **Supervision on the topic**: O. Tavares-Nascimento (Master student).

• **Project**: MINES project in collaboration with UC Irvine.

Environmental monitoring represents a class of applications with an unprecedented benefit for the scientific community and society as well. Outfitting our physical space and people with low cost sensors can enable long-term data collection at scale, but poses the fundamental challenge of gathering high quality data from low-cost sensing devices. It is well-known that sensors are prone to faults, bias and sometimes drifts, which is unfortunate, given that the ability to report accurate and reliable data motivates the use of sensors. A typical approach to enhance the quality of the data and hence fully exploit the potential of sensors, is to calibrate sensors. Traditional calibration processes are carried in an environmentally controlled environment, i.e., typically using a stimuli and in a control chamber. But, calibration in the field is essential to ensure a proper operation of the sensing device, as aging, external conditions (such as solar radiation) and other factors (e.g., activity of the end user) affect sensor's measurements over time. To this end, we propose to carefully plan the sensors calibration and to send mobile units (e.g., trained personnel) equipped with high-quality (more expensive) and freshly-calibrated reference sensors to carry out calibration in the field. The proposed calibration solution is particularly well suited for the calibration of IoT infrastructures as it significantly reduces the cost associated to the upkeep of the sensors in place. Going one step further, we introduce an approach supporting the calibration of mobile crowdsensors without requiring the user involvement because they unlikely have the necessary expertise to do so in an accurate way. We thus introduce a collaborative and automatic calibration among nearby sensing smartphones while capitalising on the calibrated IoT infrastructure, whose sensors provide a bootstrapping calibration to the mobile crowdsensors that are passing by. This leads to the introduction of a novel macro-calibration problem where numerous devices calibrate without involving the end-users.

**Chapter 4 – On the Move Again: Leveraging Crowdsensors to Support Robust and Context-Aware Sensing**

• **Publications**: [52, 53, 51, 54].

• **Supervision on the topic**: Yifan Du (PhD).

The recent proliferation of human-carried mobile devices has given rise to a new class of IoT
applications, called mobile crowdsensing, which aims at outsourcing the collection of sensory
data to participating users. However the accuracy of the sensory data depends highly on the
expertise of the participants and their behaviour, which should not interfere with the sensing
of physical phenomena. At the same time, the involvement of many (possibly incentivised)
participants is financially challenging and demanding from the cloud perspective, while it does
not necessarily lead to a proportional increase of accuracy and spatio-temporal coverage. A
crowdsensing platform has to therefore correct, properly filter, and interpolate the contributed
information as much as possible, so as to deal with missing values and cancel out any possible
errors and omissions arising from faulty devices or inexperienced participants. In order to
address these issues, we introduce a context-aware [52, 53] and collaborative crowdsensing
approach that operates at the edge, where co-located crowd-sensors, operating in the same
context, group together [53] to share the workload in a cost- and quality-effective manner. In
particular, the most adequate crowdsensors are assigned the crowdsensing tasks, according to
the nodes' abilities (for instance a smartphone located in a pocket cannot adequately sense the
surrounding sound level). We then jointly distribute the processing of contributed data over the
crowdsensors: the collected data is aggregated and the partially observed physical phenomenon
is interpolated collaboratively, so as to offload the cloud and overcome any spatio-temporal
sparsity.

**Chapter 5 – Information-Centric Networking within the IoT**

* **Publications**: [82, 140, 147, 82]

* **Supervision on the topic**: Zaid Anwer, Donnacha Nylan (Master students).

* **Project**: European Madeira project, Ericsson Omega project.

Current IoT applications typically sense physical phenomena locally, and usually outsource
their authority over information to the cloud. The cloud infrastructure further distributes sen-
sory and control data to end-users and external services. Nonetheless, highly-constrained IoT
devices usually work more efficiently in a loosely-coupled environment without maintaining
end-to-end connectivity. We therefore adopt an information-centric networking approach [82]
and introduce a purposely-built content-based publish-subscribe system. This supports a high
demand by decoupling (in time and space) content consumers from data producers. As a result,
data producers, e.g., (crowd)sensors, may leverage this loose coupling to reduce their duty-cycle
and increase their battery life. Subscribers identify interesting content topics by stipulating the
attribute(s) of the content relevant to them. Such a content-based publish/subscribe system
improves the expressiveness of subscriptions, hence reducing the dissemination of irrelevant
notifications. On the downside, the subscription process comes with a sophisticated and hence
resource-consuming filtering and hop-wise forwarding. We improve scalability and expressive-
ness, although they are two conflicting goals, by supporting a lightweight filtering [147] and
distributed notification [143]. In particular, we propose a compact approximation of the sub-
scriptions [140] that speeds up the subscription lookup. We then introduce a self-organising,
cluster-based hierarchical structure, which ensures a strict control on the underlying structure
and enables the aggregation and correlation of notifications.
<figure><img src="image_4.png" /></figure>
# Into the Wild - Intrusion Detection

## 2.1 Introduction

The practical realisation of IoT involves the design and development of various subsystems (e.g., platforms, protocols and technologies) that identify, sense, actuate, communicate and process at different levels of sophistication. That said, IoT subsystems development is mainly profit-driven and constrained by a short time-to-market, which has historically led – and still leads – manufacturers to overlook security considerations. As a matter of fact, poorly designed IoT devices open the door to adversaries, who often exploit Things with little or no effort. Moreover, Things are easily accessible as they usually remain outside of properly protected and compartmentalised networks. The seriousness of the situation is well illustrated by an attack launched by IoT-specific malware called Mirai [2]. Dyn, a leading DNS provider in the United States, has been the target of one of the largest Denial of Service attacks ever launched on a myriad of vulnerable Things. The attack hampered name resolution and caused considerable collateral damage as users were unable to access websites. Given the Internet-wide deployment of IoT, any malicious manipulation may have a profound effect on the resilience of the entire Internet. It therefore becomes vitally important to track events occurring in today's IoT networks and to analyse them for potential signs of security breaches. Once an attack is detected, proper counter-measure mechanisms must be considered to prevent the attacker from causing widespread damage. One straightforward approach to securing the myriad Things is to redesign them, incorporating security agents within their structure. Such an approach would be neither affordable nor would it scale up to the massive amount of Things. This brings us to introduce an Intrusion Detection System (IDS) capable of detecting security threats within IoT environments without any design alterations.

In the course of this chapter we focus on Intrusion Detection, with the aim of discovering whether or not the IoT ecosystem is functioning normally. Our scope covers the search for: (i) *misuses*, which correspond to some specific attacks that are already known and (ii) *anomalies*, which occur when an intruder's behaviour does not conform to the expected or legitimate behaviour. We introduce a *misuse detector* that exploits current knowledge about existing attacks in order to look for evidence/symptoms that signal an attack development. An *anomaly detector* further builds a reference model describing the usual behaviour of a given system and subsequently searches for any noticeable deviation from this model. Whilst essential to avert and control the risks associated with attacks, the general detection of misuses and anomalies that threaten the IoT at large is undeniably an ambitious project. Indeed, the wide range of attacks [163, 38] target different levels, covering hardware, networks, systems, and applications. It is moreover necessary to consider and handle: (i) The heterogeneity of Things, from highly resource-constrained Things (e.g., RFID tags and readers) to personal laptops and (ii) the various underlying organisations, from fully cooperative systems to individual Things.

To this end we cover two case studies, ranging from intrusion detection in Mobile Ad hoc NETwork (MANET) to anomaly detection in RFID-based access control systems. In both cases we consider the nature of the monitored system (network/computer/object and supplied
service) to determine intrinsic vulnerabilities and their corresponding attacks.

We begin with the problem of intrusion detection for the routing protocol in MANETs (§2.2). Our choice is motivated by the fact that a routing protocol supplies a critical network service and is therefore a prime target. Unlike existing systems that monitor packets passing through host [5, 168], our signature-based intrusion detector analyses logs to identify patterns of misuse. Thus, this approach does not necessitate modifying the implementation of the routing protocol, nor does it require inspection of the traffic. Our detector relies on the attack signatures that we pre-established. To this end, we have surveyed and modeled the attacks in a way that reflects the dependencies between their constituting tasks. In particular, we focused our attention on the intrusions threatening the OLSR routing protocol [39]. Based on the attack signatures, our detector discovers the attacks threatening the OLSR protocol. Whilst essential, intrusion detection faces two problems. First is the minimisation of computation overload and bandwidth usage associated with the investigation and intrusion detection processes. Second, the intrusion detection process involves open and spontaneous cooperation with other devices, which are generally unknown or barely known. It is very likely that malicious nodes intend to take advantage of this lack of mutual knowledge in order to disrupt the detection process. It is therefore indispensable to develop a cooperative intrusion detection system that: (i) regulates the amount of remote logs/evidences that are collected and (ii) assesses the trustworthiness of the devices involved in intrusion detection and weighs the contributed logs/evidences accordingly. Our strategy to reduce resource consumption Things on the development of a lightweight and distributed intrusion detection system that analyses logs as close as possible to the device that generated them. The intrusion detection system selects a subset of nearby nodes that are randomly and uniformly questioned. By leveraging the statistical approach (and in particular the confidence interval and confidence level), we reduce the resource consumption and regulate the gathering of evidence without compromising detection reliability. We then incorporate a mechanism for assessing trust and supporting informed decision making. Before considering evidences from another device, a node assesses the device's trustworthiness, which reflects the node's evaluation of its past activities and future intentions. Establishing a relationship of trust is a challenge, not only because it must be insusceptible to deception, but it must also be able to bypass attackers who adapt their behaviour, i.e., behave well and then misbehave in order to abuse the system. To this end we introduce an entropy-based trust system, which aims to objectively express an opinion on a device based on its actions and its recommendations from other nodes. This system capitalises on the notion of entropy, which allows it to establish the similarity between a personal opinion and the received recommendations while determining the extent to which a node's behaviour is legitimate.

Next, we explore a complementary approach that detects anomalies (§ 2.3), considering a
case study in which individuals are monitored using RFID tags. Our objective is to depict the
normal behaviour of the system and classify any deviation as an attack. We address the problem
of detecting anomalies in an RFID system, using unsupervised algorithm. Rather than relying
on a simple statistical method to detect any deviation from the normal activity, we select the
Kohonen's self-organising maps [92] as an advanced neural network architecture that permits
the user's profile to be built as an ordered representation of spatial proximity among vectors
of an unlabelled data set. The data provided by the RFID system is used to train a Kohonen
map which allows the definition of a region representing the normal behaviour of the observed
subjects. Based on the trained Kohonen map, any activity that does not match the defined
normal behaviour is identified as an anomaly; the main advantage is that there is no need
to pre-define the pattern of an intrusion. Kohonen's maps are also recognised for their ability
to automatically classify activities without supervision. Thus, our anomaly detection system
detects any spoofing attack wherein an adversary mimics an authentic tag or uses a robed tag
since such an intrusion will presumably deviate from normal usage.

## 2.2 Signature-based Intrusion Detection in MANETs

Securing *ad hoc* networks presents a challenge since these networks rely on an open medium of communication, are cooperative by nature and hence lack centralised security enforcement points (e.g., routers) from which preventive strategies are launched. While a wide variety of attacks [118] are aimed at disrupting *ad hoc* networks, routing protocols constitute a key target because: (i) devices operate as routers, which facilitates the manipulation of messages and more generally the compromising of the routing, and (ii) no security countermeasure is specified as a part of the published RFCs. In the following, we introduce an Intrusion Detection System (IDS) that monitors the attacks against routing protocols. We exemplify our IDS, focusing our attention on the attacks that threaten the Optimized Link State Routing protocol [39] (abbreviated as OLSR). We begin by detailing each attack (§ 2.2.1), relying on a model that captures the complexity and temporal dependencies between each of the constituting sub-tasks. We attempt to describe the general form of this attack so as to deal with slightly varying attacks. Based on these modelled attacks, we can further define the corresponding attack signatures (2.2.2).

### 2.2.1 Attacks Threatening the OLSR Protocol

We start with a brief introduction to the OLSR protocol.

**OLSR in a nutshell**

OLSR is proactive routing protocol designed to ensure that each terminal maintains an up-to-date picture of the network topology. A fundamental aspect is the Multipoint Relay (MPR): each terminal selects a subset of 1-hop neighbours whose task it is to forward control traffic to the whole network. OLSR attempts to select the minimum number*<sup>a</sup>* of MPRs that cover all the two-hop neighbours, so as to reduce the number of nodes re-transmitting control messages and thereby the resulting bandwidth usage. In practice, a node establishes the set of 1-hop neighbours that are further advertised*<sup>b</sup>* in a so-called *hello message*, which is sent periodically. A Topology Control message (TC) is then broadcast. Within the TC message, the MPR announces the set of neighbours that selected it as MPR. Thanks to these TC messages, any device can calculate the shortest path, in terms of number of hops, to any destination. This path is materialised by a sequence of MPRs. In addition, later versions of OLSR support the presence of nodes with multiple network interfaces that are declared in a message called a *Multiple Interface Declaration* (MID) message that is regularly broadcast by MPR. The functions we have laid out here form the core of OLSR though other extensions have been introduced (e.g., the interconnection to other routing domain thanks to OSPF protocol).

In the following we detail the attacks to the OLSR protocol, leveraging a model [4] that provides
the level of expressiveness needed to depict the actions constituting the attacks along with the

<footnote>a. Redundant MPR(s) can be selected to increase accessibility.</footnote>

<footnote>b. Instead, information coming from the link layer and typically provided by the IEEE 802.11 protocol, can be used to update the list of 1-hop neighbours.</footnote>
related consequences. We further enrich the model with temporal annotations (as visible in Table 2.1). Then we categorise attacks threatening the OLSR protocol according to actions undertaken against the following routing messages [121]:

* *Drop attack*: consists in dropping routing message(s).

* *Active forge attack*: proactively generates deceptive routing message(s).

* *Modify and forward attack*: modifies received routing message(s) before forwarding it.

<table><caption>Table 2.1 – Notations</caption><thead><tr><th colspan="4">Communication</th></tr></thead><tbody><tr><td>X &larr; Y</td><td>At time t, Y sends a message M received by X</td><td>&larr; Y</td><td>At time t, Y send a message M</td></tr><tr><td>X &ne; Y</td><td colspan="3">X does not receive a message M at time t</td></tr><tr><th colspan="4">Parameters</th></tr><tr><td>&Delta;t</td><td>Time period</td><td>NS<sub>X</sub></td><td>1-hop neighbour of X</td></tr><tr><td>sq</td><td>Sequence number</td><td>hc</td><td>Hop number</td></tr><tr><td>MPR<sub>X</sub></td><td>MPRs of X</td><td>Sel<sub>MPR<sub>X</sub></sub></td><td>MPR selector for X</td></tr><tr><th colspan="4">Messages</th></tr><tr><td>Hello</td><td>Hello message</td><td>TC</td><td>TC message</td></tr><tr><td>FM</td><td>Forwarded message</td><td>CM</td><td>Control message</td></tr></tbody></table>

## Drop attack

A Drop attack consists in suppressing a control message that should be normally<fnref n="1" /> relayed. A Drop attack is carried out by the MPRs, which forward control messages (i.e., TC, MID or HNA messages). Let us exemplify a drop attack: at time $t$, host $H$ sends a control message, which is intended to be forwarded. The message is received by an MPR $I$ that does not forward it during a time period that is greater than the maximum allowed period: $\Delta t$:

$$ 
\begin{array}{c}
I \leftarrow^{FM_t} H, \leftarrow^{FM_{t'}} I, |t' - t| > \Delta t \\
\Downarrow \\
I \in \mathcal{I}
\end{array} 
\qquad (2.1) $$

There are few variants of drop attacks: a malicious MPR may either delete all the incoming control messages (black hole) or a portion of them (grey hole) depending on e.g., the source, the destination or the message type. Attack is detectable by comparing the rate of packets received with that re-transmitted, considering each message type individually. Rather than deleting messages, an alternative behaviour consists in modifying the routing messages prior to forwarding it.

<footnote n="1">1. Deletion shall exclude the withdraw of some packets, which are empty, expired, duplicated or badly formatted.</footnote>
Active forge attack

An active forge attack proactively generates misleading routing messages. The best-known example of this kind of attack is probably the Denial Of Service attack (DOS), where a massive amount of control messages are forged to saturate the communication medium (see Expression (2.2)). The attack is usually conducted in a distributed manner with the participation of several devices. The scope of a DOS is either local (i.e., targeting 1-hop neighbours) or global in which case messages are broadcast over multiple hops. While a local attack cannot be prevented, it is recommended to delay and limit the forward of control messages to circumvent a global attack.

$$
\begin{equation}
\left.
\begin{array}{l}
\stackrel{CM_t}{\leftarrow} I, \stackrel{CM'_t}{\leftarrow} I, |t' - t| < \nabla t \\
\Downarrow \\
I \in \mathcal{I}
\end{array}
\right\}
\tag{2.2}
\end{equation}
$$

A DOS attack is highly visible and is hence typically conducted along with a masquerade in which the attacks switch their identity. The insertion of falsified messages also falls under the category of active forge attacks. Typically the falsification concerns the list of adjacent links that are advertised in hello messages. Similarly, the information about network interfaces in the MID and HNA messages may be modified. In the first case (Expression (2.3)), I forges a *hello* message, which declares a list of 1-hop and symmetric<fnref n="2" /> neighbors $NS'_I$ that differs from the real set $NS_I$.

$$
\begin{equation}
\left.
\begin{array}{l}
S \leftarrow \stackrel{\text{hello}(NS'_I)t}{\leftarrow} I, NS'_I \neq NS_I \\
\Downarrow \\
I \in \mathcal{I}
\end{array}
\right\}
\tag{2.3}
\end{equation}
$$

In particular, the basis of an attack aiming at falsifying the state of the links lies in:

* Publishing the presence of a symmetric 1-hop node that does not actually exist (Expression (2.4)). This allows the intruder to be selected as MPR. Indeed, if *I* advertises a non-existing node *N* (*N* ∉ *N*, with *N* defining the set of nodes composing the OLSR network<fnref n="3" />), *I* ensures that no other (well-behaving) MPR claims being a 1-hop symmetric neighbour of *N*. *I* is hence selected as an MPR. In addition, the connectivity of *I* is also artificially increased (*Card*(NS'₁\(NS'₁ ∩ N)) > 0).

$$
\begin{equation}
\left.
\begin{array}{l}
\displaystyle \leftarrow \stackrel{\text{hello}(NS_S)_t}{\leftarrow} S, S \leftarrow \stackrel{\text{hello}(NS'_I)_t}{\leftarrow} I, |t' - t| < \Delta t, \\
\exists N \in NS'_I \exists: N \notin \mathcal{N} \cap NS_I \\
\Downarrow \\
I \in \mathcal{I}, \\
\exists I' \in \mathcal{I} \cap NS_S \exists: I' \in \text{MPR}_S, \\
\text{Card}(NS'_I \setminus (NS'_I \cap \mathcal{N})) > 0.
\end{array}
\right\}
\tag{2.4}
\end{equation}
$$

* Publishing an existing node *s* is a 1-hop neighbour, when it is not the case. This claim disrupts the routing and artificially increases the connectivity of *I* i.e., *Card*((NS'₁\*NS_I)∩

<footnote n="2">2. A symmetric 1-hop neighbor, hereafter simply referenced as neighbor, corresponds to an adjacent node with which communication is bidirectional.</footnote>

<footnote n="3">3. According to the OLSR RFC [39], messages can be flooded into the entire network (with a maximum network diameter defined by the message Time To Live field, or flooding can be limited to nodes within a diameter (defined in terms of number of hops) from the originator of the message. For the sake of clarity, let be $\mathcal{N}$ represent the network in both case.</footnote>
$\mathcal{N}) > 0.$

$$
\begin{align*}
& \xleftarrow{\text{hello}(NS_S)_t} S, S \xleftarrow{\text{hello}(NS'_I)_{t'}} I, |t' - t| < \Delta t, \\
& \exists X \in NS'_I \cap \mathcal{N} \ni: X \notin NS_I \\
& \Downarrow \\
& I \in \mathcal{I}, \\
& \text{Card}((NS'_I \setminus NS_I) \cap \mathcal{N}) > 0, \\
& \exists A \in \mathcal{N} \setminus \mathcal{I} \ni: A \in NS_S \land X \in NS_A \\
& \Downarrow \\
& \exists I' \in \mathcal{I} \ni: I' \in \text{MPR}_S.
\end{align*}
\tag{2.5}
$$

If no other (well-behaving) MPR covers $S (\not\exists A \in \mathcal{N} \setminus \mathcal{I} \ni: A \in NS_S \land X \in NS_A)$, then at least one misbehaving node is selected as a MPR of $S (\exists I' \in \mathcal{I} \ni: I' \in \text{MPR}_S)$. Such insertion typically characterises an attempt to create a blackhole: $I$ introduces a novel path toward $M$ that whenever selected provisions the blackhole.

* omitting a symmetric 1-hop neighbour $P$ as a means of isolating the latter. As a matter of fact, omitting to advertise the presence of $P$ ($\exists P \in NS_I \ni: P \notin NS'_I$) artificially decreases the connectivity of both $P$ and $I$ ($NS_I \not\subseteq NS'_I$).

$$
\begin{align}
& \xleftarrow{\text{hello}(NS_S)_t} S, S \xleftarrow{\text{hello}(NS'_I)_{t'}} I, |t' - t| < \Delta t, \nonumber \\
& \exists P \in NS_I \ni: P \notin NS'_I \nonumber \\
& \Downarrow \nonumber \\
& I \in \mathcal{I}, \nonumber \\
& \exists I' \in \mathcal{I} \cap NS_S, NS_I \not\subseteq NS'_I. \tag{2.6}
\end{align}
$$

The falsification of the adjacency links may pervert the overall local topology, which is per-
ceived by a node and may influence MPR selection. The attack is potentially coupled with
a modification of the willingness field [3]. I may prevent (resp. ensure) its selection as MPR
by setting willingness field to the value *will_never* (resp. *will_always*). The MPR selection
is altered either by falsifying the topological information or the willingness attribute. Overall,
the aforementioned forge attack may contaminate the OLSR network ; interconnected routing
domains are impacted<fnref n="4" /> if a compromised gateway forge falsified routing messages. In such a
case the gateway publishes some nodes or some networks that do not exist or exist but are un-
reachable. In addition, the gateway may also omit to advertise some existing nodes or networks.
This attack is quite similar to a link spoofing attack, which is why we will not detail it here.
Another way of carrying an attack lies in altering the control messages that are disseminated.

Modify and forward attack

This attack consists in capturing a victim’s control message, modifying and then relaying it.
Any packet field may be modified, including e.g., the MPR set in TC message, the interface
configuration in MID message and routing information injected in HNA message. The attack
also involves replaying the packet several times or forwarding it later (possibly to a different
location) so that routing tables are updated based on outdated information. Interestingly,

<footnote n="4">4. Symmetrically, false routes can be imported into the OLSR domain.</footnote>
attacks may be carried out by multiple nodes. Let us illustrate this case by considering a pair of intruders (Expression 2.7).

$$ 
\begin{array}{l}
I_1 \leftarrow \underset{enc}{\overset{CM(S)_t}{CM(S)_t}} S, I_2 \leftarrow \underset{enc}{\overset{CM(S)}{CM(S)}} I_1, \underset{enc}{\overset{CM(S)_{t'}}{CM(S)_{t'}}} I_2, \\
\nabla t \le |t' - t| < \Delta t \qquad (2.7) \\
\Downarrow \\
X \in NS_Y
\end{array}
$$

One intruder, $I_1$, records control message from one region while another intruder, $I_2$, modifies and forwards the message to another region. To do this, $I_1$ may transmit the message to $I_2$ using a different interface than that of the ad hoc network. Alternatively, $I_1$ may create an encrypted tunnel through which encrypted control messages pass. At the other end of the tunnel, $I_2$ replays incoming messages. The attack creates a wormhole whose length corresponds to the distance separating the two intruders. In order to remain invisible, $I_2$ may masquerade; the source of the relayed control message can be either $I_1$ – thus $I_2$ remains invisible – or another node, say $S$ – thus both $I_1$ and $I_2$ remain invisible. In order to circumvent the attack, nodes should check if the data transfer is done in time.

Another possible attack is to hijack sequence numbers so that the destination deletes the message that would otherwise have been used. In practice, an intruder $I$ increases<fnref n="5" /> (resp. decreases) the value taken by the sequence number so that the destination assumes that $I$ advertises most recent (resp. obsolete) routes and ignores the next (resp. current) control message. Note that if the packet conveying the sequence number is forged then we are dealing with an active forge.

The attacks we have just mentioned can be composed and conducted independently or cooperatively, possibly coupled with a masquerade. Thus devising an intrusion detection system capable of tracking these attacks along with their perpetrators is not a trivial task because the slightest deviation from one attack may make it undetectable.

### 2.2.2 Attack Detection

The attacks targeting the OLSR protocol follow some well-defined patterns that can be modelled with attack signatures. In the following, we propose an intrusion detection system that aims at monitoring the operation of the OLSR protocol, looking for series of events that match the codified signatures so as to counter security threat. Our IDS is non-invasive: it collects audit data (i.e., logs) generated by the OLSR protocol. Traces correspond to a sequence of chronological events that characterise the evolution of all the internal activities of the protocol (e.g., packet reception or MPR selection). Additional security reports and logs on the system state are easily integrated and correlated. In addition, our IDS does not require any amendment to the OLSR protocol, which generates separate individual log files. The first step of the online intrusion detection process lies in collecting and pre-processing logs to extract relevant events and avoid matching an attack signature against a large dataset. Events are then classified into the following four categories that reflect the degree of evolution – and hence the seriousness – of the attack:

* Initial event group: contains the events that lead to the initiation of an extensive investigation.

<footnote n="5">5. A sequence number reaching its maximum is reset.</footnote>
* Suspicious-evidence-group: encompasses the events leading to the qualification of a node as possibly malicious.

* Confirmed-evidence-group: comprises the event confirming the attack occurrence.

* Cancel-evidence-group: includes events that eliminate all suspicion.

Based on a compact set of categorised events, our signature-based IDS supports a fast pattern matching that ensures that incidents are promptly addressed. Additionally, the evolution of a long term attack can be easily tracked. Once filtered and analysed, logs are matched against predefined intrusion signatures. A signature can be viewed as an ordered sequence of events that characterises a suspicious activity. The procedure can be expensive in terms of memory and bandwidth usage as it may require the collection of evidence from other nodes in order to correlate them. Thus, an investigation needs to be initiated if a sufficient degree of suspicion exists. Before delving into the operation of the above evidence groups, let us first exemplify the proposed intrusion detection system with the link spoofing attack we purposely developed.

## Signature of a Link Spoofing Attack

Central to the notion of misuse detection is the definition of the attack signature. We are interested in establishing the signature of an attack that tampers adjacent links. A first step towards that goal lies in describing the specific<fnref n="6" /> attack relying on the model introduced in [4], which we enrich with temporal annotations so as to support the expressiveness necessary to establish the relationship between actions constituting the attack and the resulting consequences. In order to perform a link spoofing attack, an intruder, denoted $I$, forges a hello message, which declares the list of 1-hop neighbours whose link is bidirectional, denoted $NS'_I$ and which differs from the correct one, denoted $NS_I$.

$$ S \leftarrow \begin{array}{l} hello(NS'_I)_t \\ I, NS'_I \neq NS_I \\ \downarrow \\ I \in \mathcal{I} \end{array} \qquad (2.8) $$

In order to ascertain the occurrence of such an attack, one should determine whether $NS'_I$ differs from $NS_I$. There are three variants of falsification (see §2.2.1):

1. Declaring a non-existent node as a symmetric 1-hop neighbour of $I$ (or of another node) so that $I$ (or another node) is selected as MPR.

2. Claiming that an existing node as a 1-hop symmetric neighbour even though the node is distant or is an asymmetric 1-hop neighbour.

3. Omitting a 1-hop symmetric neighbour artificially decreases the connectivity of the omitted node.

The detection of the link spoofing attack described above necessarily requires a continuous investigation that aims at confronting each node's vision (which includes the set of 1-hop and 2-hops neighbours). Unfortunately this involves a continuous confrontation and hence is not viable. We therefore take a different approach, noting that inflecting the MPR selection is one

<footnote n="6">6. Interested reader may refer to [8] for a detailed modelling of all the attacks threatening OLSR and a description of the related signatures.</footnote>
attack goal and thereby an attack indicator. Our approach thus consists of looking for changes (or an absence of changes) in the MPR selection and in the MPR coverage. As a complement, a MPR behaving inappropriately (*e.g.*, suppressing, falsifying, failing to adequately relay control messages or defining itself as a MPR without having been selected as such) is also an interesting aspect. Events (extracted from the logs) that reveal such (possibly inappropriate) behaviour are tagged as evidence announcing an attack occurrence and are categorised as an "initial event group" (as defined in §2.2.2). In such a case, an in-depth investigation is triggered to collect information concerning the 1-hop and 2-hops neighbourhood.

### Collaborative Investigation
An in depth investigation consists in verifying that the MPR coverage is adequately advertised. For this purpose, 2-hops neighbours are questioned with the aim of determining if the suspicious MPR is indeed a symmetric 1-hop neighbour and is susceptible of being a MPR. The corresponding request is sent out, avoiding the suspect as much as possible. Based on the returned answers, the attack diagnosis takes place using the signature described above. If all the interrogated nodes provide information that conforms to that of the suspected MPR, the behaviour of the MPR is defined as appropriate. If instead one or more nodes provide information that differs from the MPR information, this may indicate that an attack is taking place. Two special cases in particular may pose problems:

* Some or all of the responses are missing due to *e.g.*, some packet collisions or some disconnections of the queried nodes. In such a situation, the diagnosis is biased as it is only based on a portion of the evidence.

* Answers are contradictory. For instance, a malicious node may non-legibly accuse a well-behaving MPR or may certify the good behaviour of a malicious MPR. A legitimate node may also have a different vision due to *e.g.*, the node mobility or to slightly inconsistent routing table.

In order to prevent misbehaving nodes from foiling the intrusion detection, we propose to evaluate the trustworthiness of the node(s) that provide second-hand observations (see § 2.2.3). The objective is to favour the observations provided by trustworthy nodes while being detrimental to misbehaving nodes. In addition we leverage a statistical parameter, namely the confidence interval, to control the evidence-gathering and determine to what extent additional evidence is needed to make an informed judgement (§ 2.2.4).

### 2.2.3 Trustworthiness Evaluation

In the presence of malicious nodes, supporting a reliable intrusion detection strategy is challenging because attackers will try to conceal the attack by providing false observations. While essential, trust establishment in a distributed and resource-constraint MANET is much more difficult than in traditional wired networks as there is no certification authorities nor trusted third parties; as opposed to traditional centralised approaches, trust management in MANETs should handle uncertainty and incompleteness of trust evidences.

In the years 2010, a great majority of existing work on distributed intrusion detection assumes that any participating node is trustworthy and faithfully reports intrusion attempts [63]. Alternatively, Duma et al. [55] introduce a trust-aware engine that correlates intrusion alerts. Nonetheless, the proposed trust model does address highly distributed intrusion detection. Meanwhile, much research has been conducted on modelling and quantifying trust [87]. Trust and reputation are usually utilised to prevent packets from being routed through misbehaving
nodes [151, 175]. In this work, we develop a robust trust management model that specifically
copes with distributed intrusion detection. Our trust system evaluates node trustworthiness
based on personal experience and on the recommendations formulated by others. We propose a
distributed and entropy-based trust system in which trust relationships are primarily built with
neighbours, based on local observations and on mutually exchanged evidence. Trust is evaluated
depending on the similarities between received evidence and local evidence. Each time a node
provides a similar (resp. dissimilar) evidence of intrusion, its trustworthiness increases (resp.
decreases). Recommendations from neighbours are also necessary to derive indirect trust values.
A fundamental challenge is then to define a suitable means by which to represent trust and
synthesise the set of opinions that are provided by others into a unique aggregated value. To
this end, we first define the notion of trust and introduce some axioms that describe the basic
rules for establishing trust. Then, based on these axioms, we develop techniques to calculate
trust values.

Trust Definition

A trust relationship established between node *A* concerning node *I*, represents the extent to which *A* thinks that *I* behaves adequately. Trust is established before a misbehaving action takes place and as such can be viewed as a belief, i.e., level of likelihood with which a node is expected to perform a particular action. Trust is characterised by the following properties:

* Trust is subjective. For instance, the trust that two nodes grant to a third node may differ.

* Trust has a dynamic nature and usually varies over time. The trust value is a discrete real number.

* Trust is an action – and context– dependent function: an entity may be trustworthy for performing one task (e.g., forwarding packets) but not for another one (e.g., detecting attacks).

* Trust is asymmetric and not transitive. Trust is not necessarily mutual and the fact that *A* trusts *B* and *B* trusts *C* does not imply that *A* trusts *C*,

Building trust requires a quantitative analysis of the nodes behaviours based on the history of their previous activities and interactions. Thus, trust can be assessed by a measure of uncertainty, and as such trust values can be estimated based on entropy. In the following we introduce the rules (axioms) to follow for calculating trust values based on observations and also through a third party (concatenation propagation) and through recommendations from multiple nodes (multipath propagation).

Trust Establishment

The following five axioms are used to establish trust relationships accordingly, leverage previous
interactions and consider recommendations:

*   **Axiom 1 - Measuring trust based on entropy:** An activity that is beneficial to others (e.g., packet relaying) increases the confidence in the node that performs it. Conversely, a malicious activity decreases this confidence. A piece of evidence that concerns a node *I* and is established by a node *A*, is denoted $e_j^{A,I}$. Such evidence contains all the observations necessary to evaluate the trust and calculate a value that reflects the confidence associated
with the evidence. The confidence associated with the evidence is not absolute but the opinion of the specific node instead. In order to increase the readability of the manuscript, the trust value is referred as an evidence value. The evidence (a.k.a confidence value) takes a positive value (resp. a negative value) if the related behaviour is beneficial (resp. malicious). The trust is a real number in [-1,1]. When the trust value is -1 the node is not trusted and if trust value is +1 the node is trusted. We define the entropy-based trust value as follows:

$$T^{A,I}(e_j^{A,I}) = -e_j^{A,I} \log_2(e_j^{A,I}) - (1 - e_j^{A,I}) \log_2(1 - e_j^{A,I}) \quad (2.9)$$

* **Axiom 2 - Danger:** the degree of danger should be taken into account when assigning a trust value. To do so, a factor $\alpha_j$ weights the evidence $e_j^{A,I}$.

* **Axiom 3 - Freshness:** Newer activities should be prioritised over older ones. In practice, an omission factor $\beta$ privileges fresh evidences rather than older ones. A node A calculates the trust of a node I based on n evidence denoted $e_1^{A,I}, \dots, e_i^{A,I}, \dots, e_n^{A,I}$, which concerns I and that have been collected during $\Delta t$:

$$T_{\Delta t}^{A,I} = \sum_{j=0}^{n} \alpha_j e_j^{A,I} + \beta T_{\Delta t-1}^{A,I} \quad (2.10)$$

Note that in absence of evidence, the trust value is periodically updated as follows to ensure node redemption: $T_{\Delta t}^{A,I} = \beta T_{\Delta t-1}^{A,I}$

* **Axiom 4: Recommendation of a third party:** First-hand evidence that is obtained by the node itself is preferred to second-hand evidences, which are comparatively more controversial. Nonetheless, when the observations obtained by A are not sufficient, additional (less reliable) evidence provided by other nodes is gleaned (see § 2.2.4). In this case A considers the recommendations of the third parties but the uncertainty increases. Node A establishes the trust value associated with a node I based on the recommendation of a third party S as follows:

$$Ts_{\Delta t}^{A,I} = R_{\Delta t}^{A,S} T_{\Delta t}^{S,I} \quad (2.11)$$

Thus node A relies on the evidence $T_{\Delta t}^{S,I}$ provided by S. Given that node S may lie, A lowers the resulting trust value using $R_{\Delta t}^{A,S}$.

Note that the computation of the trust value (Eq. 2.11) reflects the probability that I will perform an attack. Let $p_S$ denote the probability that S makes a correct recommendation and $p_{I/B=0}$ the probability that I will perform an attack if B lies. This probability can be expressed as :

$$p_{ASI} = p_S p_{I/S=1} + (1 - p_S) p_{I/S=1} \quad (2.12)$$

Unfortunately A ignores the value of $p_S$ and $p_{I/S=1}$. Leveraging our distributed trust model, A evaluates the probability $p(AS)$ that A observes the behaviour of S and A makes a recommendation on S. In addition, A estimates $p(SI)$ the probability that S observes the behaviour of I and that S makes a correct recommendation on S. Finally, A computes the value of $p_{ASI}$:

$$p_{ASI} = p(AS) p(SI) + (1 - p(AS)) (1 - p(SI)) \quad (2.13)$$

* **Axiom 5- Concatenating multiple recommendations:** The recommendations of
several nodes may be considered together in order to establish a trust value. Recommendations are concatenated into a trust value that should not be artificially amplified. Thus, when several nodes, denoted $S_1, S_2, \dots, S_m$, generate recommendations, A computes an aggregated trustworthiness about I as follows:

$$ Tm_{\Delta t}^{A,I} = \sum_{i=1}^{m} w_i R_{\Delta t}^{A,S_i} T_{\Delta t}^{S_i,I} \qquad (2.14) $$

with $w_i = \frac{1}{\sum_{j=0}^{m} R_{A,S_j}^{\Delta t}}$ serving as an averaging factor. Once established, trust is then used to prevent malicious nodes from interfering with intrusion detection.

### Trust Establishment in the presence of a link spoofing attack

In the following, we detail the computation of the trust value considering a link spoofing attack: In order for Node A to establish whether I is carrying a link spoofing attack A interrogates the neighbours of the suspected node I. The interrogated neighbours either do or do not corroborate the information provided by the suspect, in which case the answer includes the fields $r^{S_i,I}$ that either takes the value 1, if the link established by I is correct, or the value -1 otherwise. The answers from each interrogated neighbour $S_i$ (with $i \in [1, m]$) are weighted with the trust level $T_{A,S_i}$ that the investigator A places in the neighbour $S_i$ as well as taking into account a weighting factor $w_i$:

$$ Detect_{\Delta t}^{A,I} = \sum_{i=1}^{m} w_i T_{A,S_i} R_i^{S_i,I} \qquad (2.15) $$

with $w_i = \frac{1}{\sum_{j=0}^{m} T_{A,S_j}}$. Ultimately, a fake link attack is detected if $Detect_{\Delta t}^{A,I}$ is close to 1.

### 2.2.4 Reducing the Cost of Investigations

Intrusion detection is a resource-consuming process that needs to last because an attack against a routing protocol is typically persistent and continuous (i.e., attack repeats itself over time). Thus intrusion detection leads to the collection of a massive amount of logs and evidence. In a dense network, the number of collected evidence becomes colossal. In order to reduce the corresponding bandwidth usage and thereby lighten the intrusion detection process, we propose to randomly and uniformly request the nearby nodes into collaborative investigation (i.e., the 2 hop neighbours of the MPR). As a result, fewer nodes are less frequently contacted compared to the deterministic approach introduced above. We employ confidence interval and confidence level as means for regulating (either reducing or increasing) the evidence-gathering while ensuring a satisfactory level of detection reliability.

#### Confidence interval and confidence level

The confidence interval represents a statistical uncertainty associated with the estimation of a population parameter (e.g., proportion, mean, median) [156]. The confidence interval is associated with confidence level, which corresponds to the likelihood that the true parameter belongs to the interval.

In our case, based on a partial set of evidence, denoted $e_1, \dots, e_n$, we establish an interval in which the mean, computed using the entire set of evidence, has a high probability of belonging to. In practice, based on a confidence level fixed by the investigator, the true mean $\bar{m}$ has a certain probability of being contained in the confidence interval $[\bar{m}_e - \epsilon, \bar{m}_e + \epsilon]$ with $\epsilon$
reflecting the allowed margin of error that is defined by the end user. The sampling error $\epsilon$ decreases as the sample size increases. According to the central limit theorem introduced by Pierre Simon Laplace [135], the sampling distribution of the mean follows a t-distribution [157] when the sample size is small and a normal distribution when the sample size becomes large [11], regardless of the population form. With a normal distribution, the margin of error $\epsilon$ is expressed as a function of the standard deviation $\sigma$ and the standard density $z$:

$$ \epsilon = z \frac{\sigma}{\sqrt{n}} \qquad (2.16) $$

With a t-distribution, the margin of error $\epsilon$ is expressed as a function of the standard deviation $\sigma$ and the standard density $z$:

$$ \epsilon = z \frac{\sigma}{\sqrt{df}} \qquad (2.17) $$

with $df$ corresponding to the degree of freedom. Note that there are many potential t distributions, whose forms are determined by their degrees of freedom. Nonetheless, when estimating the mean, $df = n - 1$. The standard deviation is then calculated as follows:

$$ \sigma = \sqrt{\frac{\sum_{i=0}^{n} (\bar{m}_i - e_i^{A,S_i})^2}{n - 1}} \qquad (2.18) $$

The overall estimation of the confidence interval of a population mean proceeds as follows:

* Gather a few pieces evidence (a.k.a samples).

* Compute the sample mean and standard deviations.

* If the sample size is large (resp. small), select the $z_{\alpha/2}$ (resp. $t_{\alpha/2}$) from the normal distribution (resp. the t-distribution),

* Compute the sampling error $\epsilon$ and the confidence interval as $[\bar{m}_e - \epsilon, \bar{m}_e + \epsilon]$.

The computation of the confidence level and interval during the diagnostic permits our Ids to: (i) regulate the number of gathered and processed evidences while maintaining the required detection accuracy and (ii) measure to what extent the diagnosis is reliable, especially in the presence of inconsistent evidences.

At best, the confidence level is high and the confidence interval is narrow. If an attack<fnref n="7" /> is taking place, evidence will be collected with less but sufficient regularity. In practice, the IDS follows a stepwise process that reduces the volume of evidences to collect. Instead, if the confidence level is low and the confidence interval is wide, additional evidence should be collected to establish a representative diagnostic. Note that collecting more evidences conveniently increases the confidence level but not necessarily narrow the confidence interval: a controversy is established but cannot be prevented.

## 2.3 Anomaly Detection

We propose an anomaly detection, whose aim is to find any behaviour that does not conform to the expected behaviour. We begin by modelling the normal behaviour of the target and define an anomaly as any observed behaviour that does not conform to the normal/baseline model. A

<footnote n="7">7. In absence of detected attack, investigation ends.</footnote>
key challenge to searching for an anomaly lies in identifying which data are dissimilar to the rest
of the data set, since an individual piece of data can be considered as anomalous with respect
to the the larger whole. As an illustration, an anomaly may refer to credit card transaction
characterised by a very high amount of expense compared to the usual range of expenditure. A
contextual anomaly corresponds to a data instance that is anomalous only in a specific context.
A collective anomaly comprises a collection of instances; the individual instances are not by
themselves defined as anomalies but their concomitant occurrences, as a collection, is abnormal.
A Denial Of Service illustrates such an anomaly: individual events are not anomalies when they
occur sporadically over a large time frame.

In order to detect individual, context-dependant and collective anomalies, we investigate
the feasibility of applying machine learning techniques and in particular unsupervised learning,
considering an application that controls the access of users [138, 126]. To this ends, users are
provided active RFID tags which are used to monitor the user's location. Given this specific
use case, anomalies are primarily detected based on spatial-temporal features rather than oper-
ational ones. Rather than relying on a simple statistical method, we select an advanced neural
network architecture permitting the construction of the user's profile automatically *i.e.*, with-
out involving users or experts. Note that such automatic training permits the easy addition
of (operational) features without modifying the core implementation. Based on an advanced
Kohonen's map, our detection system detects any spoofing/cloning attack wherein an adversary
mimics an authentic tag and any usage of a robed tag since these intrusions, by assumption,
will deviate from normal user's normal activity.

2.3.1 RFID System supporting access control

We propose an anomaly detection model that deals with an access control application in which
users working within a building are equipped with RFID tags which are used to monitor the
user’s location. The application records the user’s profile including the series of Cartesian co-
ordinates of that user so as to detect any intruder in the building.

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

Our access control application [138, 126] consists of three main components:

* An RFID tag (Figure 2.1a)– a silicon microchip attached to an antennae and possibly enriched with additional functionalities, e.g., sensing, storage, encryption – that outfits the users.

* An RFID reader (Figure 2.1b) –a transceiver communicating with tags via radio frequency and typically containing internal storage and processing capabilities (so as to perform tasks on behalf of the tag), which is deployed within the building,

* A back-end database connected to the reader, which collects the information related to the physically tagged persons.
The above components are naturally subject to a broad range of threats [123], due to the networked nature of RFID, their poor physical security as well as their insufficient resilience against physical manipulation.

### Security Flaws

A particularly common issue is related to the fact that RFID tags may be permanently or temporally disabled. Possible ways of rendering a tag inoperable involve: (i) destroying the tag, (ii) disabling the tag using the so-called kill command, (iii) covering the tag with an aluminium shield that serves as a Faraday Cage, and (iv) preventing tags from communicating with readers by generating an electromagnetic signal in the same range as the reader so as to cause jamming. In order to safeguard RFID systems against low-tech attacks that (permanently or temporarily) disable tags, additional countermeasures can be used such as increased physical security through guards and cameras.

Another type of attack lies in *cloning* and *spoofing* an RFID tag. *Cloning* consists in replicating the legitimate tag, which is reasonably easy given the wide availability of writable and re-programmable tags. With a *spoofing* attack an adversary impersonates a valid RFID tag to gain privileges. Spoofing requires a certain expertise; the attacker must (i) understand the involved protocols, and (ii) gain access to the secrets (e.g., keys) used during the authentication. Nonetheless if the RFID communication is unauthenticated, attackers may easily counterfeit the identity of a legitimate reader so as to elicit sensitive information or modify data on RFID tags.

The wireless nature of RFID makes eavesdropping one of the most serious threats. By eavesdropping an attacker records communications (tag-to-reader and reader-to-tag) between legitimate RFID tags and readers. The feasibility of this attack depends in particular on the distance of the attacker from the legitimate RFID devices. For instance, the clandestine scanning of the tag may take place wherever the read range permits it to do so. Such scanning remains undetected (recall that a tag responds to the reader interrogation without alerting its owner). In addition, once a reader powers a tag another reader may monitor the resulting tag emission without putting a signal out itself, i.e., it eavesdrops within the detection range. A misbehaving reader that harvests information from a well-behaving tag is the starting point of privacy concerns, especially when the tag's serial numbers are combined with personal data. Considering the fact that a significant portion of RFID tags employ user-writeable memory, an adversary can exploit this to modify or delete valuable information.

Generally speaking, the level of sophistication of RFID tags and readers depends on their relative financial cost, which may impair their ability to provide advanced encryption and authentication functions. This requires providing intrusion detection. In order to meet this requirement we propose an anomaly detection system that identifies three types of attacks: stolen, cloned and spoofed tags.

### 2.3.2 Anomaly Detector

Rather than simply relying on the simple statistical method, we select the Kohonen's self-organising maps [92] as an advanced neural network architecture that can build the users' profiles as an ordered representation of spatial proximity among vectors of an unlabelled data set. The justification for this choice is twofold: (i) Kohonen's maps automatically categorise the inputs provided during the training phase without supervision, and (ii) they allow easy enrichment of the user profile, i.e., without necessitating substantial implementation changes. Consequently, based on an advanced Kohonen's map, our detection system identifies a spoofing
attack wherein an adversary mimics an authentic tag and any usage of a robed tag because
these intrusions, by assumption, deviate from the normal usage of the users.

The primary challenge in anomaly detection lies in defining normal versus abnormal be-
haviour. An advantage of self-organising maps is that they can learn to discriminate between
normal and abnormal based on examples (i.e., training samples) and therefore requiring no ex-
plicit definition of these behaviours by the user. Our anomaly detection system is based on the
Kohonen map [92], a neural network that distinguishes itself by its unsupervised learning. An-
other convenient aspect is related to the fact that this map reduces the dimensions of the input
data from a (potentially) high dimension into 2- or 3-dimensional space (here 2-dimensional)
therefore allowing an easy visualisation and instinctive interpretation of the results.

The visible part of a Kohonen’s map consists of neurons initially arranged in a grid. Each neuron is associated with a weight vector that visually corresponds to the neuron position in the grid. The training consists in moving the neurons; this movement is based on attraction strength determined by neighbourhood function. This neighbourhood function conveniently preserves the topological properties of the input space and serves as a regularisation factor that smooths the functional mapping. The low dimensionality of Kohonen Maps renders them useful for visualisation. The neighbourhood function serves ordering the map by pulling units close together in the map space toward each other. The resulting trained map reflects a mapping from a higher-dimensional input space to a lower-dimensional map space. The self-organised map serves partitioning the input space into convex regions of activity that are characterised with the following property. Every point in the space is closer to the centroid of its region than to the centroid of any other region. In the map, the centroids of the regions are defined by the weight vectors.

As detailed in the following, anomaly detection identifies activities that vary from an es-
tablished pattern, following three main steps: (i) pre-processing the gathered data, (ii) creating
a knowledge model made up of the (previously) monitored activities, and (iii) subsequently
categorising the various activities relying on Kohonen maps.

Raw Data Pre-processing

The output of the RFID system corresponds to the trajectory of any subject sampled at dis-
crete time intervals t₁, ..., tₖ, ..., tₘ with *m* defining the trajectory length. Any observation
is expressed as a set of *m* *n*-dimensional real vectors *x* = (*x*(*t*₁), ..., *x*(*t*ₖ), ..., *x*(*t*ₘ)). A
trajectory is hence composed of spatial-temporal records, each record being primarily com-
posed of a geographical location in a 3D plan and a temporal attribute, *i.e.*, a timestamp.
In addition to the above, extra pieces of information may be added or inferred from the
spatio-temporal records. For instance, they relate to the maximum speed, (estimated) at-
traction point, direction, movement pattern (*e.g.*, loop, u-turn) and the average or standard
deviation of the aforementioned parameters. Data provided by the RFID system are further
filtered and normalised so as to fall in a specific [0, 1] range. In practice, filtered samples
are expressed as a vectors set in which each vector *x* = (*x*(*t*₁), ..., *x*(*t*ₖ), ..., *x*(*t*ₘ)) ∈ R<sup>*m*</sup>
are collected at *t*₁, ..., *t*ₖ, ..., *t*ₘ. Each activity *x*(*t*ₖ), is defined as an *n*-dimensional
vector *x*<sup>*T*</sup>(*t*ₖ) = (*x*₁(*t*ₖ), ..., *x*ᵢ(*t*ₖ), ..., *x*ₙ(*t*ₖ)), which once normalised is denoted *x*<sup>*T*</sup>(*t*ₖ) =
(*x*'<sub>₁</sub>(*t*ₖ), ..., *x*'<sub>ᵢ</sub>(*t*ₖ), ..., *x*'<sub>n</sub>(*t*ₖ)) with *x*'<sub>*i*</sub> =
frac[*x*ᵢ(*t*ₖ)]
arg max[*x*<sub>j</sub>∈[1,*n*](*x*ᵢⱼ(*t*ₖ))}.
Relying on these filtering and nor-
malisation processes, work-less samples are removed and each filtered sample is of equal footing
and can hence be exploited during the training phase in order to create a Kohonen map.
## Training phase

A training phase is needed in order to generate a map. The resulting Kohonen map $w_1, \dots, w_s$ of size $s$ corresponds to a topological 2-dimensional array of neurons originally initialised with random values. This map is intended to categorise the normalised samples $x'(t_k)$ (with $1 \le k \le m$) provided as input. Each input vector $x'(t_k)$ is therefore compared with each neuron forming the Kohonen map and the distance between the input vector and neuron is computed and the closest neuron is selected as the winner. The topological structure of the Kohonen map is then updated: neurons that are topologically close to the winner move towards it. Consequently the resulting Kohonen map reflects a categorisation (clustering) of the samples. More specifically, considering a measure whose norm is noted $||$, the distance between an input vector $x'(t_k)$ and the synaptic vector of each neuron $w_i(t_k)$ of the map is computed and the winner $g(x'(t_k))$ selected according to the following law:

$$g(x'(t_k)) = \operatorname*{argmin}_{i \in [1, s]} \|x'(t_k), w_i(t_k)\|. \qquad (2.19)$$

Afterwards the neurons that are topologically close to the identified neuron move in the direction of the winner. To achieve this the neuron $w_i$ is updated as follows:

$$w_i(t_{k+1} = w_i(t_k) + \pi_{i,g(x'(t_k))(t_k)} \eta(t_k) x'(t_k) - w_i(t_k) \qquad (2.20)$$

with $(i, j, k) \in [1, s]^2 \times [1, m]$, $\eta(t_k)$ defining an adaptation factor that controls the degree of change imposed to the neuron's vector, and $\pi_{i,g(x'(t_k))(t_k)}$ a neighbouring function centred around the winner $g(x'(t_k))$.

The basic idea is that the adaptation factor $\eta(t_k)$ decreases monotonically as the learning phase progresses so as to guarantee a convergence of the weighted neuron's vector towards a stable state [98]. To this end $\eta(t_k) = \eta_0 \exp(t_k/t_m)$. Similarly, the neighbouring function $\pi_{i,g(x'(t_k))(t_k)}$ decreases as $t$ evolves until the winning neuron is the only neuron that has its weight significantly updated. For this purpose $\pi_{i,g(x'(t_k))(t_k)}$ is defined as a symmetric function following a Gaussian form with a standard deviation $\sigma$ decaying exponentially with time:

$$\pi_{i,g(x'(t_k))(t_k)} = \exp\left(\frac{\|(x'(t_k), w_i)\|}{2\sigma^2(t_k)}\right) \qquad (2.21)$$

and,

$$\sigma(t_k) = \sigma_0 \exp\left(\frac{-t_k \log(\sigma_0)}{t_m}\right) \qquad (2.22)$$

Kohonen algorithm is applicable to large data set given that: (i) the computational complexity scales linearly with the number of samples $m$, and (ii) limited memory is necessary to record the set of training vectors $x'(t_1), \dots, x'(t_k), \dots, x'(t_m)$ and the Kohonen map $w_1, \dots, w_s$. As a 2D-grid a Kohonen map is of great help in visualising and inspecting the user behaviour recalling that the structure of Kohonen map reflects the structure of the original training samples. By employing the trained Kohonen map, which reflects the normal activity of a subject, any deviation from that normal activity can be easily detected and identified as an anomaly.

## Decision Making

If the distance between the observed and normal behaviour is greater than a given threshold, then the observed behaviour is intuitively defined as anomalous. Given our use case - RFID-
enabled control access system attempting to analyse the user location - we distinguish two
sources of potential anomalies: the user's position and its trajectory. A position is said to be
anomalous if it does not belong to any of the classification defined during the training, i.e., if
it does not pertain to any of the clusters centred on the winning neurons defined as part of the
training phase. By extension we define a trajectory as anomalous if a large percentage of the
user's positions are anomalous, i.e., if the pre-processed observations do not pertain to any of
the clusters centred around the winning neurons g(x'(t_k)) and delimited by the radius defined
as the maximum distance separating the winning node g(x'(t_k)) from its neighbouring neurons
(i.e., the neurons that belong to Dg(x'(t_k))). By extension, a trajectory o'(t), ..., o'(t + p) is
anomalous if the ratio of anomalous positions exceeds a given threshold defined by β(r).

The computational complexity related to detecting a position and then its trajectory scales linearly to the number of winning vectors $g(x'(t_k))$ (bounded by $m$). In addition to the memory allocated to the training phase, little additional memory (essentially just the index $i$ of the winning neurons and their established radii) is used during the anomaly detection.

Identifying trajectories that exhibit irregular or even suspicious traits is crucial in many
applications including access control and intrusion detection. In such scenarios, unsupervised
learning is the most advantageous model when learning from many regular data instances,
as the algorithm thoroughly approximates the underlying distribution and produces a concise
model of normality. As a consequence, unsupervised learning method are often used to detect
anomalies.

**2.4 Performance Evaluation**

In the following section we evaluate performances associated with the intrusion detection system (§ 2.4.1) and the trust system (§ 2.4.2).

**2.4.1 Signature-based Intrusion Detection**

In order to evaluate the performance of our intrusion detection system (§2.2) we simulate a
mobile *ad hoc* network using the Ns3 network simulator<fnref n="8" /> [133] and we virtualise each device
using LxC<fnref n="9" /> [23]. The MANET area is defined by a squared area of *S* = 310 × 310 m² and
is comprised of *N* = 30 devices split into 25 well-behaving devices and 5 intruders, the latter
of whom repeatedly launch the implemented link spoofing attack<fnref n="10" />. Devices move randomly,
following a randomly chosen direction, at a given speed that is the same for all the devices.
When a device hits the network boundaries it rebounds following a reflexive angle. Nodes use
the OLSR protocol, communicating via IEEE 802.11a with transmissions that have a range of
90m. Data traffic is further simulated using the *V4PingHelper* application of NS3; the nodes
exchanges 56 bytes ICMP echo requests to one another and wait for 1s before sending it again.

During our experiments we evaluate the performance of our IDS in terms of:

* The number of intrusions that are successfully detected.

* The number of false positives that occur when a legitimate node is wrongly designated as an intruder.

<footnote n="8">8. http://www.nsnam.org</footnote>

<footnote n="9">9. http://lxc.sourceforge.net</footnote>

<footnote n="10">10. In our experiments, the number of successful intrusions varies between 15 and 33, according to the specificity of the simulated network.</footnote>
<figure><img src="image_6.png" /><figcaption>Figure 2.2 – Performances of our intrusion detection system depending on the Network Density.</figcaption></figure>

* Detection overhead, referring to the memory usage and network traffic that are generated by our IDS.

Using these performance criteria, we consider the impacts of the network density (Figure 2.2) and the device mobility (Figure 2.3). The network density corresponds to the average number of neighbours, which is defined in [75] as $\frac{N \times \pi \times T_x^2}{S}$.

## Impact of the density

At first glance, the rate of intrusions that are detected is conveniently high (Figure 2.2-a) and the false positive rate remains low (Figure 2.2-b). Specifically, the detection rate increases slightly from 93.5% to a maximum of 96.3% when the density varies from 6 to 8 neighbours because the attack is seen by a larger number of neighbours. Then a slow decrease is observed when density is above 8. The decline is caused by a higher number of collisions that partially prevent the collection of evidence and slows down intrusion detection. Still the detection rate always remains greater than 80%. As visible in Figure 2.2-b, the percentage of false positives is on average always under 5.9%. Further analysis reveal that many false positives occur due to the lack of synchronisation among nodes: some links are valid (i.e., existing) for some nodes and expired (i.e., absent) for others. To address this problem, the period during which links are considered valid should be slightly lengthened, as in [164]. While memory usage (Figure 2.2-c) gently fluctuates between 17.6MB and 22.2MB, the traffic generated by our intrusion
detection system (Figure 2.2-d) is almost negligible. Overall, there is clearly a good trade-off
between detection accuracy and resource consumption (i.e., computing and bandwidth usage)
associated with the distributed detection. When the density is high, our intrusion detection
system is confronted with a typical limitation of a constrained network: the traffic volume –
most of which stems from the routing protocol and the application – is too high and cannot
be supported by the network. In this situation, MANET can no longer fulfil its mission and
intrusions are hardly discerned.

<figure><img src="image_7.png" /><figcaption>Figure 2.3 – Performance associated with our intrusion detection System, considering a varying Mobility given a network density of 8 neighbours.</figcaption></figure>

Impact of mobility

From the standpoint of intrusion detection, mobility is the biggest challenge. When node mo-
bility increases, the intrusion detection rate decreases (Figure 2.3-a) and false positive rate
(Figure (2.3-b) falls due to the constantly changing topology. However a high detection rate
remains (e.g., about 70.7% with a moving speed of 8m/s, i.e., around 28.7 kilometers/hour
equivalent to 17.89 miles/hour). The memory usage (Figure 2.3-c) rises steadily from 17.6MB
to 26.5MB, which is a reasonable figure even for resource-limited devices. Traffic remains very
low compared to the OLSR. Overall, our evaluation shows that the intrusion detection system
is characterised by a high detection rate and a low false positive rate even under harsh con-
ditions. While the traffic overhead is negligible compared to OLSR, the fairly small memory
usage means that the intrusion detection can be undertaken by resource-limited devices.
<figure><img src="image_8.png" /><figcaption>Figure 2.4 – Trust values computed by the attacked node.</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>Figure 2.5 – Confidence associated with attack assessment.</figcaption></figure>

### 2.4.2 Trustworthiness and Confidence

In the following, we consider a network of 15 nodes, including 10 well-behaving nodes, 4 colluding nodes providing incorrect observations, and one attacker performing a link spoofing attack against a well-behaving node. The link spoofing attack engages (Figure 2.4a) and then ceases (Figure 2.4b). During the attack (Figure 2.4a), trust values of misbehaving nodes rapidly decrease regardless of their initial values and once the attack stops (Figure 2.4b), their trust values increase very slowly. This reflects the defensive nature of our trust system: it takes a lot of time to regain lost confidence while it is very easy to lose. During the attack and after, the increase of the trust associated with well-behaving is slow, especially for the well-behaved nodes that nonetheless had a small original trust value.

Rather than questioning all the neighbours, the IDS randomly selects some of the neighbours that are interrogated. The diagnostic result (Figure 2.5-b) is quickly established. As expected, the confidence interval gets narrower (Figure 2.5-a) over time because more evidence are collected and the sampling error (Figure 2.6-b) drastically decreases. When the sampling error and the confidence interval are both below a certain threshold, it is recommended to reduce the collection of evidence, to avoid unnecessarily overloading the network (Figure 2.6).

As long as liars constitute a minority (i.e., less than 50% of the nodes), trust is correctly assessed (Figure 2.6): as an illustration, attack is detected while 43.2% of the devices are lying. Attack assessment takes longer when the amount of liars increases because the trust values of the liars diminish dramatically in the last rounds. Regardless of the percentage of liars, the diagnostic result converges to -0.8.
<figure><img src="image_10.png" /><figcaption>Figure 2.6 – Bandwidth usage and impact of liars.</figcaption></figure>

## 2.5 Conclusion

In an increasingly interconnected world, an attack can be launched and massively spread from any device. Intrusion Detection Systems (IDS) hence play a crucial role on account of their ability to protect every device in a networked system including equipment, hardware and software, by forming a digital perimeter that partially or fully guards a network. We have approached the problem of intrusion detection in several contexts, spanning the routing in an ad hoc network to an RFID-based application controlling access. We adapted the IDS organisation to the contexts, leveraging an extremely distributed structure to deal with an infrastructure-less ad hoc network, and relying on a remote and centralised IDS with highly-contained RFIDs and an infrastructure-based IT network. We first introduced a misuse intrusion detection in which attack signatures were manually crafted in advance. We proposed an unusual approach to detect intrusions in a network, which consists in relying on the logs generated by the OLSR protocol. Logs give insight into the protocol's state and on the device view concerning the network topology, without requiring a change in implementation. After modeling the attacks and designing the corresponding attack signatures we turned our attention to network monitoring, as intrusion detection comes with awareness and continuous vigilance requirements. While monitoring is necessary, the constant surveillance of a network implies a prohibitive bandwidth consumption whereas the continuous flow of information should be regulated. To this end, we have proposed a statistical approach by leveraging the confidence level and confidence interval in order to fine-tune the evidence gathering process without sacrificing detection accuracy. In open and infrastructure-less MANETs we must also deal with the lack of faithfulness and non-corruptibility of information provided by other peers. Thus we introduced an information-theoretic trust system that evaluates trust based on previous interactions and considers recommendations given by others in order to increase the robustness of the IDS. Overall, our experiments highlighted that a signature-based intrusion detection system is suitable for tracking attacks, and in particular those targeting routing protocols in MANETs; a high detection rate and a low false positives rate are imperative. Nonetheless, anticipating the attacks and envisioning any possible inappropriate behaviours is not always practicable. In such a case, anomaly detection systems adequately complement signature-based IDS. Following, we introduced an anomaly detection system that identifies deviations from normal behaviour. First, subjects are equipped with RFID tags in order to be constantly located and monitored then, a user's profile is built, relying on Kohonen maps, which constitute an efficient method for automatically categorising and further comparing the tagged behaviour against the normal user's behaviour (as expressed in the user's profile). Our experiments [66] showed that unsupervised
machine learning used in combination with the functionality of an IDS forms a robust defence against possible attacks by predicting them based on past events. Even a simple Kohonen map, trained based on normal data, detects anomalous features that the system is exposed to. In the course of our research we observed that Kohonen maps may deal with multiple users. More features could easily be integrated leveraging vectorisation techniques. As long as the intrusion contaminates only a fraction of the training set and generates sufficiently distinct vectors, a map remains dominated by normal activity.
<figure><img src="image_11.png" /></figure>
# Enhancing the Observation Quality through Calibration

## 3.1 Introduction

In the light of the ever expanding importance of IoT, a noticeable trend is to promote the adoption of IoT technologies, to support the sustainable development of urban spaces, thus realising the so-called vision of smart spaces and smart cities. In particular, IoT technologies contribute to the improvement of the services the city delivers and thereby respond to a number of environmental challenges generated by the city itself (e.g., pollution) or caused by natural phenomena (e.g., global warming). With this in prospect, various research projects, including those in which I was involved in [1, 64, 144], primarily rely on IoT infrastructures to manage and optimise some services, the oversight of public spaces (e.g., campus, building, parking), environmental and pollution monitoring, surveillance for disaster preparedness and efficient first responses, as well as the preservation of cultural heritage. The delivering of problem-solving services requires the joint effort and engagement of a wide range of persons, communities, organisations and stakeholders. This also demands a(n) (r)evolution of the relationship between the participants. These needs led to the development of the crowdsensing movement wherein users (citizens, groups, communities) engage in some collaborative data collection, analysis and decision making. In practice, citizens rely on the small and low-cost sensors embedded in –or connected to– their smartphones so as to e.g., help identifying environmental problems, alert about an imminent danger, collaboratively monitor road traffic, or trace the evolution of an epidemic.

Together, IoT-based sensing and mobile crowdsensing gather some observations at a fine grain, based on the fixed things of the urban infrastructure and on the mobile devices that people carry. On the one hand, stationary sensors (e.g., weather stations, cameras) relay their (a priori) high-quality measurements to data sinks that redirect the resulting traffic towards the cloud (e.g., a back-end server typically owned by some public organisations) – this is the typical setting involving a secured wireless sensor network connected to a wired infrastructure. On the other hand, mobile smartphones opportunistically publish their data to a (crowdsensing) server according to the connectivity allowed by their data plan. Leveraging both (mobile) individually-owned and (primarily fixed) organisation-owned sensors, smart cities may henceforth oversee a physical phenomenon at a large-scale. The resulting breed of multi-purpose applications (w.r.t apps), has shifted and keeps shifting the urban areas towards environmental, social and sustainable paths.

Nonetheless, such a vision comes with a fair share of challenges. The financial cost associated to the maintenance of the IoT infrastructure is high; limited budgets lead to a partial instrumentation of the public space. The spatio-temporal coverage problem is typically addressed by leveraging mobile crowdsensors that conveniently fill the gap thanks to the mobility of the participants. Moreover, leveraging crowdsensing is a double-edged sword as crowdsensing is highly
constrained by the choice of the sensing hardware: off-the-shelf sensors/actuators outfit or are connected to the smartphones. In respect to this, the prevalence of low-cost and multi-purpose crowdsensing platforms conducts to discrepancy in the quality of observations.

To overcome this issue, a classical approach consists in calibrating sensors. Yet, we shall not solely count on the manufacturers to do so for several reasons: (i) manufacturers calibrate sensors within laboratories, under a specific range of conditions, using a controlled stimuli serving as ground-truth data; (ii) in many cases, sensors are delivered uncalibrated and are shipped along with a data-sheet that briefly sketches some generic calibration values; (iii) multi-purpose sensing devices (e.g., smartphones) are not accompanied with a data-sheet nor even a mention to the manufacturer, version or brand of the sensors/actuators.

Obviously, any non calibrated sensors, whether mobile or static, need to be calibrated. In addition, calibration in the field is essential to ensure a proper operation of the sensing device, as aging, external conditions (such as solar radiation) and other factors (e.g., activity of the end user) affect sensoring the measurements over time.

In situ calibration is essential to preserve data quality, yet challenging, for several reasons. Firstly, sensors are usually scattered over large areas and operate across long periods of time. Thus, they shall be checked and calibrated on a regular basis to preserve the measurements' quality. Secondly, massive amounts of sensors need to calibrate. The required calibration entails a significant upkeep of the sensors. A team of dedicated technicians needs to conduct the necessary parameterisations and the related manipulations in the field. This *modus operandi* is particularly well suited for the calibration of the IoT infrastructure. The situation is more problematic with mobile crowdsensing because participants do not hold the required expertise.

While essential, yet challenging, the calibration of (crow)sensors in the field has received little attention. All the proposed solutions [173, 171, 160, 114, 76, 31, 152, 107] perform a pairwise calibration: the measurements of the calibrated device then serve calibrating the non-calibrated device. This calibration applies with static and mobile sensors. Within a dense but very small-scale Wireless Sensor Network (WSN), the inaccurate readings of an uncalibrated sensor can be compensated using the measurements provided by a nearby (calibrated) sensor [173, 171, 160]. Such calibration eliminates the need for calibrating each sensor individually through the iterative and automatic calibration of sensor pairs. However, the calibration approach requires a dense deployment and is unpractical with large-scale deployments. With mobile sensing, a calibration process happens when a mobile sensing device meets another sensing device, either in a planned manner [114] or opportunistically [76, 31, 152, 107], depending on whether the mobile user is intentionally guided. In [114], a single mobile user, which is guided, is featured with a high-fidelity sensor, so that user calibrates static sensors. The problem then lies in finding the shortest path that the mobile user follows. With mobile calibration, it is assumed that two sensors that move freely, may opportunistically meet. In such an occurrence, the two devices sense the same phenomenon if their relative distance is inferior to a given threshold [76, 31, 152] or if they belong to the same spatial area [107], which is defined by, e.g., a cell. The sequence of meetings/calibrations constitutes a so-called calibration path. The best calibration path is further assessed using the model of pairwise rendezvous introduced in [31], which represents the meetings as a matrix where a non-zero edge represents a pairwise calibration. Based on this matrix, the shortest calibration path starting at a high fidelity sensor, is selected.

In contrast to the above efforts, we take a more holistic approach to cost-effective calibration in smart spaces at scale. Our objective is to enable the effective calibration of the connected nodes, from the fixed Things that make up the IoT infrastructure to the mobile Things that people carry. To overcome such an issue, our approach is two-fold:

* We propose (§3.2) to send mobile units (e.g., trained personnel) equipped with high-
quality (more expensive) and freshly-calibrated reference sensors so as to carry out cal-
ibration in the field. One can thus generate “sufficiently accurate” knowledge over time
through the frequent calibration of the sensors in the field; however, this might result
in increased maintenance costs! Careful planning of the calibration process is therefore
essential for the cost-effective monitoring of the smart spaces – this is increasingly im-
portant as the number and size of smart spaces grow. We address cost-accuracy issues
that arise in the deployment of affordable IoT systems, with the aim of developing 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, such that (a) the deployment and oper-
ational costs for calibration are minimised, while (b) maintaining a sufficient observation
accuracy from the sensor measurements. We take into consideration the presence of het-
erogeneous sensor types with varying calibration characteristics. We then program the
calibration with respect to an observed phenomenon so as to maintain an adequate sens-
ing accuracy while minimising the required effort from the mobile calibrators. We exploit
the locality of IoT infrastructure in place – we leverage the fact that a static sensor may
calibrate another nearby static sensor and thereby foster the automatic calibration of a
small-scale wireless sensor network. Our proposed approach is application-aware and is
able to take into account diverse sensing needs (sensor type, sensing accuracy) presented
by the context at hand.

Going one step further, we capitalise on the IoT-based infrastructure whose sensors may opportunistically serve as *reference* to provide a bootstrapping calibration to the mobile crowdsensors that are passing by.

*   Afterwards, we propose a distributed opportunistic calibration system (§3.3) that compensates the crowdsensor errors while alleviating the need for visiting each crowsensor to manually (re-)calibrate. Precisely, the distributed calibration system opportunistically leverages the presence of the nearby crowdsensors that monitor the same phenomenon. All the (macro-)calibration approaches introduced so far, operate either in an opportunistic or planned manner, and perform a pairwise calibration when two sensors are closeby, or meet. Instead, our solution leverages all the calibrated crowdsensors in the relevant sensing range in order to implement a multi-party calibration, which –we show– improves the performance of the calibration in terms of the resulting sensing accuracy. Our calibration system hence generalises the automated calibration to the multi-party case. Following the opportunistic calibration of crowdsensors as they meet, we introduce a *multi-hop, multi-party calibration* algorithm that is such that the history of the calibrated crowdsensors is used to assess the *best calibration hyperpath*, which is the one that minimises the accumulated calibration error. Such an opportunist calibration approach is particularly well suited to mobile crowdsensing scenarios wherein the crowd senses and meets in public place. Last but not the least,

Once calibrated, the sensors, - static and mobile – are operational and the collection of the
observations across time and space can begin.

**3.2 Planned Calibration of an IoT Infrastructure**

Note: This work results from a collaboration with the Distributed Systems Middleware (DSM) Group, under Professor Nalini Venkatasubramanian of the Department of Information & Computer Science at the University of California Irvine.
<figure><img src="image_12.png" /><figcaption>Figure 3.1 – Calibration planning over a long maintenance period.</figcaption></figure>

Cost-effectively planning the on-site calibration of IoT devices helps in the sustainable long term operation of deployments. Our aim is to develop a plan (Figure 3.1) for the calibration of a large number of inexpensive sensors in a smart space using high-integrity reference sensors that are mobile, such that (a) the deployment and operational costs for calibration are minimised while (b) maintaining a sufficient observation accuracy from the sensor measurements over a given – possibly long – maintenance period T. More realistically, given the knowledge of a sensor’s degradation characteristics, we program its calibration with respect to an observed phenomenon so as to maintain an adequate sensing accuracy while minimising the required effort from the mobile calibrators.

With that goal in mind, (i) we firstly partition the space to form calibration *spots* by exploiting the locality of in-situ sensors; a sensor can calibrate other sensors of the same type at the same spot. (ii) Subsequently, we carry out multiple iterations of calibration during the given maintenance period *T*. Our challenge lies in determining the number of iterations and the time at which each iteration should be executed. Furthermore, at each iteration we determine: the sensors to be calibrated, the number of mobile calibrators needed, and the paths taken by each mobile calibrator. The sensor calibration is then carried out accordingly over the least number of Ω *iterations* so that the overall cost over *T* is kept to a minimum and ensures that all the sensors always comply with the *data accuracy requirements*.

We formalise the above (Section 3.2.1) as a long-term multi-sensor calibration planning problem, which we solve using a two-phase iterative solution (Section 3.2.2) and a family of heuristic methods to enable the cost-effective planning of multi-sensor calibration in large smart spaces and over longer time periods (Section 3.2.3).

## 3.2.1 Multi-Sensor Calibration Planning

A **mobile calibrator** (or simply a *calibrator*) $m_i$ is a person who carries some sensors and visits the field to calibrate the deployed low-cost sensors. Sensor calibration takes place when a calibrator $m_i$ visits a node $n_j$ and stays at the spot for long enough to calibrate a sensor $n_{j,k}$.

A **node** $n_j$, $j=1, 2, ..., N$, corresponds to a IoT device that embeds one or several types of low-cost **sensors**. A **sensor type** $s_k$, $k=1, 2, ..., K$, refers to the capability of detecting a certain type of phenomenon (e.g., temperature, gas concentration), which usually requires a specific kind (or combination) of low-cost sensor(s). Afterwards, we denote an individual sensor
by $n_{j,k}$, and we introduce the binary **sensor presence** matrix $\mathbf{Q}_{N \times K}$ to characterise the set of available sensors so that $Q_{j,k}=1$ (resp. 0) if sensor type $s_k$ is present (resp. absent) on node $n_j$.

## Calibration-Related Terms

Each sensor type $s_k$ is associated with a **calibration time** $\tau_k$ that ranges from a few seconds to several minutes, depending on the phenomenon detected by the type of sensor and the calibration complexity. We associate each sensor type $s_k$ with a **calibration period** $T_k$, which characterises the maximum duration, during which the sensors remain valid (i.e., the measurements have sufficient accuracy) once calibrated. The period depends on the usage scenario and may be learned from empirical studies.

During the operation, each individual sensor $n_{j,k}$ is associated with a **time to next calibration** (TTNC) $F_{j,k}$, which indicates how soon the sensor needs to be (re-)calibrated. The TTNC matrix $\mathbf{F}_{N \times K}$ then represents the TTNCs of all the sensors. $\mathbf{F}$ is a function of time, where each $F_{j,k}$ decreases between iterations and is reset to $T_k$ when $n_{j,k}$ is calibrated. We further denote $\mathbf{F}[\omega_-]$ (resp. $\mathbf{F}[\omega_+]$), the matrix TTNC immediately before (resp. after) the iteration $\omega$. Note that $\mathbf{F}$ is non-negative, i.e., $F_{j,k}[\omega_+] \ge 0, \forall (j, k), \omega \in \mathbf{N}_+$. If node $n_j$ does not hold a sensor of type $s_k$, the corresponding TTNC is infinite.

A **sensor selection** is a collection of sensors (selected for calibration) represented by a binary matrix $\Gamma_{N \times K}[\omega]$, where $\Gamma_{j,k} \le Q_{j,k}$. If sensor $n_{j,k}$ is selected for calibration at iteration $\omega$ (i.e., $\Gamma_{j,k}[\omega]=1$), then, at the end of this iteration, its TTNC is reset to its calibration period $T_k$, i.e., $F_{j,k}[\omega_+]=T_k$; otherwise, its TTNC stays unchanged (during iteration $\omega$):

$$ \mathbf{F}[\omega_+] = \Gamma[\omega] \circ \mathbf{T}_N + (1 - \Gamma[\omega]) \circ \mathbf{F}[\omega_-] \quad (3.1) $$

Where $\mathbf{T}_N$ is the nodal calibration period matrix that consists of $N$ identical rows of $[T_1, T_2, \dots, T_K]$; “o” is the element-wise multiplication of matrices. Also, special needs and unexpected changes could be easily addressed by altering the TTNC matrix. Hence, the **time to next iteration** (TTNI) after $\omega$ is the minimum TTNC of all the sensors, i.e., $t_{\omega+1}-t_{\omega}=\min \mathbf{F}[\omega_+]$; thus, the TTNC matrix immediately before the next iteration is $\mathbf{F}[(\omega+1)_-]=\mathbf{F}[\omega_+]-\min \mathbf{F}[\omega_+]$.

## Smart-Space-Related Terms

Given the node locations $\mathbf{D}$, we can derive the **spot selection** vector $\mathbf{h}_L$ from the sensor selection $\Gamma$. A spot is selected for iteration $\omega$ if any sensor on any node deployed at that spot is selected in $\Gamma[\omega]$ i.e.,

$$ h_l[\omega] = \bigvee_{j=1}^{N} \bigvee_{k=1}^{K} \Gamma_{j,k}[\omega] \cdot D_{j,l} \quad (3.2) $$

In each iteration, the **path** of a calibrator is an ordered sequence that starts from the depot and visits a set of non-repeating selected spots. It can be represented as a binary matrix $\mathbf{W}_{L \times L}$, where $W_{l_1,l_2}=1$ if the calibrator visits spot $\nu_{l_2}$ immediately after visiting $\nu_{l_1}$; or 0 otherwise. The path of calibrator $m_i$ in iteration $\omega$ is denoted $\mathbf{W}_i[\omega]$. Each selected spot is visited exactly once by one calibrator:

$$ \sum_{i=1}^{M} \sum_{l=1}^{L} W_{l,l_0,i}[\omega] = h_{l_0}, \quad l_0 = 2, 3, \dots, L \quad (3.3) $$
### 3.2.2 Multi-Sensor Calibration Optimisation Problem

We now introduce the **multi-sensor calibration planning** problem to minimise the **average cost** of operation over the maintenance period $T$. The operation cost of any iteration $\omega$, denoted $C[\omega]$ incurs three following types of costs:

* The iteration overhead $C_{it}$ is the cost related to the preparation, equipment, and the transport to the deployment.

* The calibration cost $C_c$ reflects the time and effort required to conduct sensor calibration while staying at the spots. $C_c[\omega]=\sum_i C_{c,i}[\omega]$.

* The movement cost $C_w$ is associated with the travel time of the calibrators while moving between spots. $C_w[\omega]=\sum_i C_{w,i}[\omega]$.

The **total operation cost** is the weighted sum of:

$$C[\omega] = \mu_0 \cdot C_{it} + \mu_c \cdot C_c[\omega] + \mu_w \cdot C_w[\omega] \quad (3.4)$$

The **calibration cost** $C_c$ reflects the time and effort it takes to conduct sensor calibration while staying at the spots. The cost $C_{c,i}[\omega]$ of a specific calibrator $m_i$ in iteration $\omega$ is computed based on a given selection of sensors $\Gamma[\omega]$. We further assume that the calibration that happens at the same spot is done in parallel. Thus, the **calibration time** that $m_i$ spends at spot $v_l$ equals the maximum $\tau_k$ of all selected sensors at that spot (i.e., $\Gamma_{j,k}=1$ and $D_{j,l}=1$). Then $C_{c,i}[\omega]$ equals the sum of the calibration times at all the spots assigned to $m_i$:

$$C_{c,i}[\omega] = \sum_{l=1}^{L} \left( \max_{j,k} \left( D_{j,l} \cdot \Gamma_{j,k}[\omega] \cdot \tau_k \right) \cdot \sum_{l'=1}^{L} W_{l,l',i}[\omega] \right) \quad (3.5)$$

The **movement time** $C_{w,i}[\omega]$ of a single calibrator $m_i$ in iteration $\omega$ can be computed from the map $G$ and the calibrator's path $W_i[\omega]$. It equals the sum of the weights on the edges between all the consecutive pairs of spots visited by the calibrator:

$$C_{w,i}[\omega] = \sum_{l_1=1}^{L} \sum_{l_2=1}^{L} \left( W_{l_1,l_2,i}[\omega] \cdot G_{l_1,l_2} \right) \quad (3.6)$$

#### Problem formulation of the multi-sensor calibration planning

Our **multi-sensor calibration planning** problem, which aims at minimising the **average cost** of operation over the maintenance period, is formulated as follows: Given the time span $T$, the map $G$, the location matrix $D$ and the sensor presence matrix $Q$ of all the nodes, the calibration time $\tau_k$ and the calibration period $T_k$ of all the sensor types, and the initial TTNC matrix $F[1_\cdot]$; find the total number of iterations $\Omega$, and for each iteration $\omega=1, 2, ..., \Omega$, find the time $t_\omega$ it takes place, the sensor selection $\Gamma[\omega]$, and the number and the paths of calibrations
`{W[ω]}`; such that the **average cost** of all iterations over the time span T is minimised:

$$ \min \frac{1}{T} \cdot \sum_{\omega=1}^{\Omega} C(\Gamma[\omega], \{W[\omega]\}) \qquad (3.7) $$

s.t. $t_1 = 0$

$\Gamma_{j,k}[\omega] \in \{0, 1\}, \forall \omega, \forall j, \forall k$

$W_{l_1, l_2, i}[\omega] \in \{0, 1\}, \forall \omega, \forall i, \forall (l_1, l_2)$

$F_{j,k}[\omega_-] \ge 0, \forall \omega, \forall j, \forall k$

$F_{j,k}[\omega_+] > 0, \forall \omega, \forall j, \forall k$

$\Gamma_{j,k}[\omega] \le Q_{j,k}, \forall \omega, \forall j, \forall k$

$F[\omega_+] = \Gamma[\omega] \circ T_N + (1 - \Gamma[\omega]) \circ F[\omega_-], \forall \omega$

$F[(\omega+1)_-] = F[\omega_+]-\min F[\omega_+], \forall \omega$

$t_{\omega+1} = t_{\omega} + \min F[\omega_+], \forall \omega$

$$ t_{\Omega} + \min F[\Omega_+] \ge T \qquad (3.8) $$

$$ h_l[\omega] = \bigvee_{j=1}^{N} \bigvee_{k=1}^{K} \Gamma_{j,k}[\omega] \cdot D_{j,l}, \quad \forall \omega, \forall l \qquad (3.9) $$

$$ \sum_{i=1}^{M} \sum_{l=1}^{L} W_{i,l_0,i}[\omega] = h_{l_0}, \quad l_0=2, 3, \dots, L, \forall \omega \qquad (3.10) $$

$$ C_i(\Gamma[\omega], \mathbf{W}_i[\omega]) \le \hat{c}, \quad \forall \omega, \forall i \qquad (3.11) $$

`{W[ω]}` are valid path(s): constraints in 3.2.3 apply.

where $C[\omega]$ is representative of the total cost of iteration $\omega$ given by Equation (3.4), which depends on the sensor selection $\Gamma$ and the calibrators' paths `{W[ω]}`, i.e., $C[\omega] = C(\Gamma[\omega], \{W[\omega]\})$; obviously, it also depends on problem inputs (i.e., $\mathbf{G}$, $\mathbf{D}$, $\mathbf{Q}$, etc.) which are hidden for cleaner expressions. The unnumbered constraints relate to the definition of sensor selection and TTNC. Constraint (3.8) says the iterations need to cover the entire time span of $T$; (3.9) and (3.10) make sure all the spots with selected sensors in $\Gamma$ are visited in $\{W\}$; (3.11) says no calibrator should work for longer than $\hat{c}$ in any iteration. Additional constraints ensure that $\{W\}$ are valid path(s).

The sensor calibration planning problem is NP-hard. It tries to minimise the total cost of all iterations while the choices of early iterations can affect and limit the choices of latter ones. Moreover, the cost of each iteration $C[\omega]$ involves a movement time $C_w[\omega]$, which also needs to be minimised, and thus requires an optimisation on the paths of the calibrators, which is a variant of the Multiple Travelling Salesman Problem (mTSP) that is known to be NP-hard.

### 3.2.3 Solutions and Derived Algorithms

Our formulation suggests we find $\Gamma[\omega]$ (sensor selection) and a path plan $\{W[\omega]\}$ (path plan) simultaneously for all iterations. However, if we know which spots the calibrators need to visit, we can optimise the paths to visit them accordingly. Hence, we attempt a two-phase local optimisation on the **single-iteration average cost**, $C[\omega]/(t_{\omega+1}-t_{\omega})$, where we decouple the optimisation of $\Gamma[\omega]$ and $\{W[\omega]\}$. Accordingly, for each iteration we have a **sensor selection planning** phase and a **multi-path planning phase**. In the selection planning phase, given the initial TTNC matrix $F[\omega_-]$, we optimise the sensor selection $\Gamma$, from which we derive the set of selected spots $H$, which is then used in the path planning phase to decide the number of
calibrators and the optimal path(s) to visit the selected spots.

## Sensor Selection Planning Algorithms

Leveraging the discrete nature of TTNC and the definition of TTNI (time to next iteration), we propose the TTNI-driven local optimisation algorithm. The intuition behind this algorithm is to exhaust the possible values of TTNI (i.e., $t_{\omega+1}-t_{\omega}$) and find the “cheapest” one to fulfil. The procedure of the TTNI-driven local optimisation involves the following steps: (1) Determine **all the possible values of TTNI** that could result from any possible sensor selection in this iteration. The minimum TTNI candidate is $\min\{F_{j,k}[\omega_-] | Q_{j,k}=1 \land F_{j,k}[\omega_-]>0\}$, selecting only the sensors that need immediate calibration. The maximum TTNI candidate is $\min T_k$, selecting **all sensors**. All values in $\mathbf{F}[\omega_-]$ between them become TTNI candidates. In the worst case, the number of TTNI candidates is $O(N \cdot K)$ (2). For each TTNI candidate $T_{\text{cand}}$, tentatively assume it to be the desired TTNI and create the minimum selection of sensors to meet the TTNI, i.e., let $\Gamma_{j,k}=1$ if $Q_{j,k}=1$ and $F_{j,k}[\omega_-]<T_{\text{cand}}$; then add all the sensors that are co-located with the selected sensors and that do not induce extra time for calibration, because their calibration is done in parallel, if it takes a shorter time). Generating $\Gamma$ from $T_{\text{cand}}$ takes $O(N \cdot K+N \cdot L)$ time. Compute the single-iteration average cost from $\Gamma$. (3) Select the TTNI candidate that gives the minimum average cost, and its corresponding $\Gamma$ is the output of the algorithm. The worst-case running time excluding the time used to compute or estimate the movement time, is $O(N^2 \cdot K^2+N^2 \cdot K \cdot L)$.

If during step (2) we are able to compute the optimal paths of calibrators, we will compute the best cost evaluation for each selection and find the local optima.

## Multiple-Path Planning Algorithms

The objective of the multi-path planning problem is to generate a set of paths {$\mathbf{W}[\omega]$} of minimum cost (i.e., movement time $C_w[\omega]$) for the selected spots yielded by the sensor selection $\Gamma[\omega]$. It is a variant of the classic mTSP or VRP: we determine the number of calibrators based on the demand instead of having the number $m$ of travellers given, as in mTSP. Also, evaluating the calibrator workload constraint involves the movement time of individual calibrators, which adds to the complexity of solutions. Hence, we derive the following mixed-integer-programming (MIP) formulation of the multi-path planning problem based on a flow-based three-index MIP formulation of mTSP [19], adding appropriate modifications to match our assumptions and constraints: Given a map $\mathbf{G}$, the location of the nodes $\mathbf{D}$, the sensor selection $\Gamma$, and the calibration time $\tau_k, \forall k$; find $\mathbf{W}_{L \times L \times M}$ and helper variables $\mathbf{U}_{L \times M}$ to

$$ \min \sum_{l_1=1}^{L} \sum_{l_2=1}^{L} \left( G_{l_1,l_2} \cdot \sum_{i=1}^{M} W_{l_1,l_2,i} \right) \qquad (3.12) $$

$$ \text{s.t.} \quad W_{l_1,l_2,i} \in \{0,1\}, \quad \forall i, \forall (l_1, l_2) $$

$$ W_{l,l,i} = 0, \quad \forall l=2, 3, \dots, L, \forall i $$

$$ \sum_{l_2=1}^{L} W_{1,l_2,i} = 1, \quad \forall i $$

$$ \sum_{l_1=1}^{L} W_{1,l,i} - \sum_{l_2=1}^{L} W_{l,2,i} = 0, \quad \forall i, \forall l $$

$$ \sum_{l_1=1}^{L} \sum_{i=1}^{L} W_{l_1,l_2,i} = h_l, \quad \forall l_2 \qquad (3.13) $$

$$ u_{l,i} \ge 2, \quad \forall i, \forall l $$

$$ (3.14) $$
$$ u_{l_1,i} - u_{l_1,i} + 1 - (L-1) \cdot (1 - W_{l_1,l_2,i}) \le 0, \forall i, \forall (l_1, l_2) \\ \sum_{l_1=1}^{L} \sum_{l_2=1}^{L} W_{l_1,l_2,i} \cdot (G_{l_1,l_2} + \Upsilon_{l_2}) \le \hat{c}, \forall i \qquad (3.15) $$

Where $W_{l_1,l_2,i}=1$ if calibrator $m_i$ visits spot $\nu_{l_2}$ immediately after spot $\nu_{l_1}$; or 0 otherwise. $M$ is the maximum number of calibrators; assuming we always have enough calibrators, $L$ would be an effective upper bound of $M$ to be used in solvers. The unnumbered constraints are related to the construction of multiple paths. Constraint (3.13) makes sure all selected spots are visited by exactly one calibrator; (3.15) enforces the maximum workload of calibrators, where $\Upsilon_l$ is the total calibration time spent at spot $\nu_l$, i.e., $\Upsilon_l[\omega] = \max_{j,k}(D_{j,l} \cdot \Gamma_{j,k}[\omega] \cdot \tau_k)$.

However, the problem is NP-hard; the number of independent variables and the number of constraints in this MIP formulation are both in the order of $O(L^3)$, resulting in a huge solution space. It is hard for any MIP solver to optimally solve the problem in a reasonable amount of time [19]. In practice, we tried two widely used solvers: GLPK (GNU Linear Programming Kit, open-source – https://www.gnu.org/software/glpk/) and Gurobi (commercial software – http://www.gurobi.com/). None of the two solved the problem in less than 48 hours for $L \ge 15$. To solve the problem at a larger scale, we propose two heuristics: a greedy algorithm derived from the nearest neighbour heuristic of traditional TSP, and an improved genetic algorithm (GA) based on the one proposed by Sedighpour, et al. [154] for mTSP. For a clean design of the algorithms, after the completion of the sensor selection planning phase, the planning framework computes the set of selected spots $H$ and the calibration time $\beta$ at these spots from the sensor selection matrix $\Gamma$.

## Nearest-Neighbor-Based Greedy Heuristic

The nearest neighbor algorithm for TSP starts with a tour containing only one spot. At each step, it determines the next spot to visit as the one that is closest to the last visited spot, and loops until all the spots are visited. Inspired by this straightforward TSP algorithm, we derive that our greedy algorithm (see Algorithm 1) for the multi-path planning problem, works as follows: (1) Start with a set of empty paths (i.e., all the calibrators stay at the depot) and the set of all selected spots $H$. (2) At each step, for each unvisited spot, pick the spot-calibrator pair that induces the least additional movement time. (3) Loop until all the spots are visited. Note: Our actual implementation of this algorithm caches the movement and calibration time associated with each calibrator to reduce redundant computation, so the worst-case running time of this algorithm is $O(L^3)$.

## Improved Genetic Algorithm (GA)

We design our genetic algorithm (GA) based on the mTSP GA solution of [154]. Features are added to address the peculiarities of our MPP formulation, i.e., the variable number of calibrators, the workload constraint, and the map (i.e., a directed-graph).

A **chromosome** is an integer vector that is made of two parts: a permutation of all the selected spots (1st half) and an assignment mapping the spots to mobile calibrators (2nd half). If the number of selected spots is $|H|=L'$, a chromosome's length will be of $2L'$. The assignment (2nd half) is represented by the number of spots visited by each calibrator, so these integers should all be in range $[0, L']$ and sum up to $L'$. For example, chromosome $[2, 4, 5, 6, 3, 2, 3, 0, 0, 0]$ means $L'=5$ and that $m_1$ will visit spots $\nu_2, \nu_4$, and $m_2$ will visit $\nu_5, \nu_6, \nu_3$. The **fitness** is the negative of the total movement time of all the mobile calibrators, and the **selection** is done by a standard scaled-fitness proportional selection.
The **initial population** is composed of randomly generated individuals. The permutation is performed by a uniformly random permutation generator, and the assignment is done by uniformly and randomly picking an integer and subtracting it from the total number of selected spots until none is left. The **crossover** is done by applying a standard “order crossover” on the first half of the chromosome.

Because of the variable number of mobile calibrators, we design three helper functions that apply to chromosomes: (a) **compress**: shift all zeros in the assignment section to the end and non-zeros values to the beginning; (b) **split**: check if any assignment ($\ge$2 spots) leads to an overloaded calibrator, randomly split it into two calibrators, and loop until none is found; (c) **merge**: check if there exists a pair of assignments that can be merged into one without overloading the calibrator; then merge the first pair found. Among the three, **compress** and **split** are applied to every newly-generated chromosome during population initialisation, mutation, and crossover, while **merge** is applied as one type of mutation.

Apart from “merge”, there are three other types of **mutation**: (a) two-point swap, (b) segment reversal, and (c) 3-opt local optimisation. Every time a mutation is triggered, we randomly pick one of the four types of mutation functions. (a) and (b) are straightforward. 2-opt is a commonly used local optimisation for TSP on undirected graphs, but an odd numbered opt is required for digraphs to avoid reversing any segment, which makes it faster to compute the new movement time.

Finally, the tunable parameters such as the population size, elite-keeping size, and the termination conditions are assigned by the framework according to the problem size (i.e., $L'$).

Overall, we have presented a collaborative and distributed calibration solution that enhances the quality of the gathered observations. We frame multi-sensor calibration planning as an optimisation problem where we propose a two-phase iterative local optimisation approach to determine (a) how many calibration iterations are necessary, (b) which sensors should be calibrated at each of these iterations, and (c) the number of mobile calibrators that are required (as well as their respective calibration paths). Such an effective deployment and maintenance of the IoT infrastructure within a metropolitan area fosters the long term gathering of meaningful observations. In addition, calibrated IoT infrastructure can in turn serve as a high-quality reference to opportunistically calibrate some mobile sensors that monitor the same phenomenon and that are engaged to sense at a larger scale.

## 3.3 Robust Multi-Party calibration

The distributed collaborative calibration requires rendezvous, although infrequent, with reference sensor(s) belonging to the IoT infrastructure, for the calibration of the mobile crowdsensors. An overriding requirement is to minimise the involvement of end-users, who usually do not hold the required expertise. The calibration system shall require no specific knowledge or manual configuration – end-users do not need to place themselves under ideal conditions. End-users engaged in the crowdsensing, are simply required to install a mobile app – implementing the calibration and the crowdsensing together– on the smartphones at their disposal.

Our solution leverages robust regression so as to discard the measurements that are of too low quality for being meaningful. We further introduce a multi-party calibration system, which exploits the spatial dimension of the problem which –we show– improves the performance of the calibration in terms of the resulting sensing accuracy. Several sensors that are separated in space, may track better the physical phenomenon and should therefore be involved into a multi-party calibration of higher-quality. In particular, we say that there is a *multi-party calibration rendezvous* between a non-calibrated smartphone *i* and *m* calibrated smartphones
(1 ≤ m ≤ n − 1) in the case of both spatial and temporal proximity over a time period. That is, if the following conditions are met:

• The m reference – or previously calibrated– sensors are in communication range with i during the overall calibration period { t$_{1}$, ..., t$_{p}$ } .

• The m reference sensors are in a shared sensing range with i , i.e.,, the distance between i and any reference sensor j ∈ { 1 , · · · , m } is less than the maximum calibration distance d$_{max}$ , which is defined based on the measured physical phenomenon and environment being considered.

During the multi-party rendezvous, the uncalibrated sensor i attempts to calibrate using the calibrated measurements provided by the m nearby sensors. The objective lies in determining a calibration function, which describes the relationship between the non-calibrated measurements and the calibrated one(s) and thereby enables correcting the measurements of the non-calibrated sensor(s). As presented in literature, for many sensors, there is close to linear dependence between the measurements produced by the sensor and the sensed phenomenon ( e.g. , see [105, 30]). Accordingly, it is assumed that a sensor i can be provided with the relevant calibration coefficients/parameters for the linear function, which returns the calibrated measurements ˆ y$_{i}$ given the sensor measurements ˆ y$_{i}$ at time t . In the same way, the measurements of a non- calibrated sensor have a linear dependence with those of some calibrated sensors, as illustrated in Figure 3.3 with the specific example of noise sensing using the smartphones’ microphones. In this case, any reading y$_{i}$ ( t ) of the uncalibrated sensors (at time t ) can be expressed as the following function: y$_{i}$ ( t ) = β$_{0}$ + β$_{1}$x$_{1}$ ( t ) + β$_{2}$x$_{2}$ ( t ) with x$_{1}$ ( t ) and x$_{2}$ ( t ) corresponding to the reading of two calibrated sensors. Once calibrated, the sensor i can in turn, be used to calibrate others. Such a dynamic calibration, which is also known as blind calibration , allows calibrating sensors under their deployment conditions and without involving the end-user.

To the best of our knowledge, this is the first calibration system that generalises the au- tomated calibration to the multi-party case. Following the opportunistic calibration of sensors as they meet, we introduce a multi-hop, multi-party calibration algorithm that is such that the history of the calibrated sensors is used to assess the best calibration hyperpath , which is the one that minimises the accumulated calibration error. Figure 3.2a depicts the pairwise and multi-hop case supported in literature [76, 31, 152], which is based on a sequence of pairwise cal- ibration rendezvous with the initial calibration starting with the Reference sensor. Figure 3.2b then introduces the general case of multi-hop, multiparty calibration, in which a succession of pairwise or multi-party calibrations may take place. In practice, our sensor calibration aims at assessing the sensor’s bias compared to the measurements of reference (or previously calibrated) sensor(s) that happen to be in the relevant communication and sensing range. Overall, the cal- ibration system is unobtrusive in that it requires no configuration or handling once started. Furthermore, the system does not require a parsimonious and dense deployment, making it practically relevant to various urban scenarios.

3.3.1 Multivariate Linear Regression

Given the multi-party calibration rendezvous of the sensor i with m smartphones, the multi- variate linear regression computes the calibration coefficients/parameters for i based on the calibrated measurements provided by the m mobile sensors. In particular, the uncalibrated (raw) measurement of the sensor i is defined as the following linear function:

$$
Y_i = XB + \mathcal{E}_i \tag{3.16}
$$
<figure><img src="image_13.png" /><figcaption>(a) Multi-hop pairwise calibration: Sensor 2 first calibrates with the reference sensor 3. Then, sensor 1 may calibrate with calibrated sensor 2.</figcaption></figure>

<figure><img src="image_14.png" /><figcaption>(b) Multi-hop pairwise followed by multiparty calibration: Sensors 2 and 6 apply pairwise calibration. Then, multiparty calibration occurs for sensor 5.</figcaption></figure>

<caption>Figure 3.2 – Pairwise versus multi-party calibration.</caption>

$Y_i$ is a p-dimensional vector (i.e., $Y_i = (y_i(t_1), \dots, y_i(t_p))^T$) with T denoting the transpose of the vector; $X$ is a $p \times (m+1)$ that includes the calibrated measurements of the m sensors ($j \in \{1, \dots, m\}$); $B$ is a $(m+1)$-dimensional vector (i.e., $B = (\beta_0, \dots, \beta_m)^T$) that represents the unknown (and fixed) regression coefficients; and and $\mathcal{E}_i$ is a p-dimensional vector (i.e., $\mathcal{E}_i = (\varepsilon_i(t_1), \dots, \varepsilon_i(t_p))^T$), which refers to the residual noise. The model assumes that $\mathcal{E}_i$ is a normally distributed random variable with 0 mean and a constant standard deviation $\sigma$ that is unknown [49]. Given the above, we want to find the regression coefficients $B$ of $\hat{Y}_i$:

$$ \hat{Y}_i = XB \qquad (3.17) $$

We apply the method of the least square, which minimises the sum of the squared differences between the actual values $y_i$ (resp. $Y_i$) and the regression values $\hat{y}_i$ (resp. $\hat{Y}_i$), using the linear regression of Equation 3.16. Formally, the estimate of the regression coefficient denoted $B = (\beta_0, \dots, \beta_m)^T$ is computed such that $\sum_{t=t_1}^{t_p} (y_i(t) - \hat{y}_i(t))^2$ is minimised. This sum of the squared differences is minimised analytically by setting: $B = (X^T X)^{-1} X^T Y_i$. It follows that the fitted value $\hat{Y}$ verifies:

$$ \hat{Y}_i = XB = X(X^T X)^{-1}X^T Y_i \qquad (3.18) $$

Thus, the minimised residual error is given by:

$$ \mathcal{E}_i = Y_i - \hat{Y}_i = (I - H)Y_i = (I - X(X^T X)^{-1}X^T)Y_i \qquad (3.19) $$

where $I$ is a $m \times m$ identity matrix.

The above simple multivariate regression is particularly well suited to establish a relationship between the measurements of sensor $i$ and those of provided by the smartphones that are encountered during a multi-party calibration rendezvous. Nonetheless, the validity of the simple multivariate regression is compromised if some measurements contain outlier(s). With sensors, outliers are commonly observed.

## Removing Outliers using Robust Regression

Rather than minimising the sum of the squared residuals $\sum_{t=t_1}^{t_p} \varepsilon_i(t)^2$ as it is the case with simple regressions, the robust regression minimises the median of squared residuals computed for the entire data set [136]. This median-based estimator resists the effect of nearly 50% of the data contaminated by outliers. Afterwards, we remove outliers using the robust regression algorithm presented in [136], which iterates on the following steps: Randomly select few samples; Fit the model to these few samples using multivariate regression; Evaluate the quality of the fit on the remaining points using the median, which is a well known robust estimator. Ultimately, the
<figure><img src="image_15.png" /><figcaption>Figure 3.3 – *Simple versus robust linear regression:* Sound Level (dB(A)) of an uncalibrated Crosscall Trekker-X3 expressed as a function of the sound level sensed with two calibrated Asus Nexus 7.</figcaption></figure>

subset that is characterised by the best fit is kept. Ideally, the above procedure should repeat
for all possible sub samples of size *q*, for which there are $C_p^q$ possible combinations. In practice,
one should select a certain number of random subsamples, such that the probability that at
least one of the *q* subsamples is good, is almost 1. A subsample is said to be "good" if it contains
up to a fraction *f* of bad observations. The probability that at least one of the *q* subsamples
is good, assuming that *p/Q* is large, is 1 - (1 - (1 - *f*)^q)^p By setting a probability of almost 1,
the value of *q* can be determined based on the given values of *p* and *f*. Finally, the model is
re-fitted to all the data that are sufficiently close to the model and the data that are not close
enough (*i.e.*, the outliers) are removed.

Using such a robust regression, the calibration coefficients of an uncalibrated smartphone
*i* are estimated based on the possibly faulty readings *X*₁, ..., *X*ₘ provided by *m* sensors that
are met during the multi-party rendezvous.

Assessing the Relevance of a Calibration Rendezvous

Given a set *M* of *m* devices meeting with *i*, the multi-party calibration requires determining the best subset *K* of *k* (*k* ≤ *m*) devices to calibrate with, *i.e.*, the subset of devices with which to exchange measurements so as to enhance the accuracy of *i*'s measurements while minimising the resulting resource consumption. Figure 3.4 illustrates the representative cases that arise where *Y* (resp. *X*₁, *X*₂) depicts the variance of the samples from device *i* (resp. 1, 2):

* If two nearby devices, 1 and 2, supply almost the same samples (Fig. 3.4a), the calibration of the device *i* does not require the readings of 1 and 2; using the samples of one of the two is sufficient.

* Contrariwise, when two devices provide uncorrelated samples (Fig. 3.4b), each separate device makes a unique contribution to the calibration of *i* and should be considered during the calibration.

Overall, the best subset *K* should include the nearby devices that: (i) are both calibrated and (ii) both contribute sufficiently to the calibration of *i* by supplying some samples that are mostly non-redundant. We rely on (semi-)partial correlation [49] to estimate the unique contribution
<figure><img src="image_16.png" /><figcaption>(a) $X_1$ and $X_2$ are highly correlated. (b) $X_1$ and $X_2$ are uncorrelated. (c) $X_1$ and $X_2$ are correlated.</figcaption></figure>

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

<figure><img src="image_18.png" /><figcaption></figcaption></figure>

Figure 3.4 – Device *i* meets two calibrated devices 1 and 2. Device *i* collects samples locally, whose variance is *Y* and determines if it can calibrate using the samples of 1 and 2 (with variance denoted $X_1$ and $X_2$). The figure depicts the relationship between the 3 variables *Y*, $X_1$ and $X_2$. In 3.4c: *a* is the variance specific to the samples of *i*; *b* (resp. *d*) is the part of *Y* variance uniquely influenced by $X_1$ (resp. $X_2$); *e* is the part of $X_1$ variance uniquely influenced by $X_2$; *c* is the part of *Y* variance influenced by both $X_1$ and $X_2$.

of each device to the calibration of *i*. Consider the case depicted in Figure 3.4c, the area *a* represents the variance specific to *Y*, while the area *b* + *c* + *d* (i.e., the area of *Y* intersecting with $X_1$ and $X_2$) represents the overlap of *Y* with $X_1$ and $X_2$. We may further decompose the variance *Y* with respect to $X_1$ and $X_2$. The area *b* (resp. *d*) is the part of the *Y* variance uniquely influenced by $X_1$ (resp. $X_2$); it is represented by the squared semi-partial correlation coefficient, denoted $r_{X_1}$ (resp. $r_{X_2}$), which reflects the correlation between *Y* and $X_1$ while $X_2$ has been partialed out (i.e., the effect of $X_2$ has been removed from $X_1$ but not from *Y*). The semi-partial correlation of $X_1$ with *Y*, which can be simply denoted $sr_{X_1}$, corresponds to the correlation $r_{X_1 \setminus X_2 Y}$ between $X_1$ and *Y*, removing the effect of $X_2$ from $X_1$, but not from *Y*:

$$sr_{X_1} = r_{X_1 \setminus X_2 Y} = \frac{r_{X_1 Y} - r_{X_1 X_2} r_{X_2 Y}}{\sqrt{1 - r_{X_1 X_2}^2}} \quad (3.20)$$

Following, we use the semi-partial correlation to characterise the specific effect that each calibrated device of *M* may have on the calibration of *i* so as to exclude any device *j* that contributes measurements that are not sufficient/unique (i.e., with $sr_{X_j} \le \epsilon$). We apply a stepwise process, wherein the devices having the lowest semi-partial regression are removed first. Semi-partial correlations are further used in a stepwise regression procedure, where the device (rather than the end-user) determines which variables (i.e., device) should be considered in the final regression. We note that, in a forward stepwise regression, the calibrated device that would add the largest semi-partial correlation is added next (provided it is statistically significant).

### 3.3.2 Multi-hop, Multi-party Calibration

We now consider the history of the sensors’ calibrations to assess the relevance of a given multi-party rendezvous. Indeed, we must compare the quality of the calibration parameters computed in the current rendezvous to the quality of the previous calibrations, if any.

#### Formalising the History of Multi-party Calibrations using Hypergraphs

Formally, we represent the history of multi-party calibrations using a weighted, directed hypergraph (Figure 3.5a). A *directed hypergraph* is a pair $H = (V, E)$, where *V* denotes the finite
<figure><img src="image_19.png" /><figcaption>(a) Hypergraph example. *Node r* abstracting all the *reference nodes*, to which they each connect, is added to the hypergraph.</figcaption></figure>

<caption>(b) Hyperedge between node *i* and *m* nodes.</caption>

<caption>Figure 3.5 – Hypergraph encoding the multi-party calibration history.</caption>

set of nodes (*i.e.*, sensors/smartphones) and $\mathbb{E}$ the finite set of directed hyperedges. A *directed hyperedge* $E_j \in \mathbb{E}$ is an ordered pair $E_j = (T, D)$ of two (possibly empty) disjoint subsets $T, D \subset V$, where $T$ is the *tail* –noted $tail(E_j)$– and $D$ is the *head* –noted $head(E_j)$– of the hyperedge. As an illustration, the *hyperedge* $E_j = (\{i\}, \{1, \dots, m\})$ represents in Figure 3.5b the multi-party rendezvous between node $i$ and $m$ nodes; the cardinality of the tail is 1 (*i.e.*, $|tail(E_j)| = 1$) while the cardinality of the head is $m$ ($|head(E_j)| = m$, with $m \ge 1$). The directed hyperedge is further weighted such that each of the inner-edges between $i$ and one of the $m$ nodes provides the properties of the calibration (including regression) established by $i$ using the readings provided by the calibrated node(s). Thus, $V^2 \mapsto \mathbb{R}^q$ denotes the set of all the inner-edges such that the weight of any $i, j \in V^2$ is defined as a $q$-dimensional vector that specifies:

* The characteristics of the meeting, which includes, e.g., the time period during which the calibration is taking place;

* The properties of the calibration for sensor *i*, which is established based on the readings provided by sensor *j*. This includes $\hat{y}_i$ as well as the parameters that determine the quality of the regression, including the variance-covariance matrix (as previously defined) and the regression error.

Consider the hypergraph that is locally maintained by a participant node *i* involved in some rendezvous, *i.e.*, the hypergraph at *i* represents the history of past rendezvous together with the rendezvous that are currently eligible for the calibration of *i*. The *m* nodes in the sensing range of *i* similarly maintain their hypergraph of calibration rendezvous. The various nodes may then exchange their respective hypergraphs, which allows each one of them to compute the *shortest hyperpath* that minimises their own calibration error (*i.e.*, as estimated by the regression qualities that weight the inner edges). Consider the example of Figure 3.5a, in which there are two hyperedges from node 8 to reference nodes 3 and 7: (i) From 8 to 3 through $E_1$, $E_2$, and $E_3$, and (ii) From 8 to 7 through $E_1$, $E_2$, and $E_4$. We simplify the problem of establishing the hyperpath of minimum weight from *i* to a set of *reference nodes* (*i.e.*, highly accurate, high-quality sensors), denoted *R*, by transforming it into the problem of finding a hyperpath of minimal weight from *i* to a single node *r*. This is done by adding a new *consolidated node* *r* to the hypergraph and connecting each end reference node to node *r* with a *< 0 >*-weighted hyperedge.

Following, given a directed and weighted hypergraph $H = (V, \mathbb{E})$ and the nodes $i$ and $r$ of $V$, we say that there is an *hyperpath* from $i$ to $r$ shall one of the following conditions be met:

1. $i = r$, in which case, the hyperpath is empty.
2. There is a hyperedge ($\{i\}, K$) $\in \mathbb{E}$ such that $\forall k \in K \subset V$, there is a hyperpath from $k$ to $r$.

Condition 2 signifies that a node $i$ can calibrate using the surrounding sensors in $K$ if and only if the sensors in $K$ are also calibrated (i.e., there is a hyperpath from each of them to $r$). Overall, considering the set of eligible hyperpaths, $H_{i,r} = (V_{i,r}, \mathbb{E}_{i,r})$, from $i$, according to the set of nodes in the sensing and communication ranges of $i$, the goal of node $i$, which attempts to calibrate, is to find the calibration hyperpath (from $i$ to $r$) –and thus the associated hypergraph– that minimises the accumulated weight, which is:

$$P: \min_{\mathbb{E}_{i,r} \subseteq \mathbb{E}} \sum_{E_j \in \mathbb{E}_{i,r}} w(E_j)h(E_j) \quad (3.21)$$

where $w(E_j)$ specifies the sum of the weights of the inner edges of an hyperedge $E_j$, and $h(E_j) = 1$ if the hyperpath goes through the edge $E_j$ and $h(E_j) = 0$ otherwise.

## Finding the Shortest Hyperpath

Using the local hypergraph, any sensor $i$ may independently compute the shortest hyperpath (in terms of the edge weights) towards the "consolidated end reference" sensor $r$, for which we introduce Algorithm 2:

1. The initialisation (lines 2-4) is as follows: the hyperpath from $i$ to any node is set to empty; the distance to the source is set to 0 and to all the other nodes to infinite; and the set of nodes that need to be visited, denoted $Q$, is set to $V$.

2. Then, all the nodes are visited (line 5), starting with $i$ as the current node (i.e., $u = i$). In the consecutive rounds, the current node refers to the closest node, i.e., the closest node that is reachable by an outgoing hyperedge (line 6).

3. The set of nodes that can be reached from the current node through any outgoing hyperedge $E_j$ is determined (line 7):

* First, we treat the pairwise rendezvous (lines 8-14), which is characterised by a hyperedge $E_j$ having a head of cardinality 1. If a shorter path passing through $E_j$ is found, the distance from $i$ to the newly connected node $v$ is updated considering the minimal distance, and the hyperpath to $v$ is updated accordingly.

* Then, we treat the multi-party rendezvous (lines 15-25) with a hyperedge $E_j$ with $|head(E_j)| > 1$, which has not been visited so far (i.e., $E_j \notin E$). We establish the shortest hyperpath from each node $v$ participating to the rendezvous (for each $v \in head(E_j)$). We check if each node $v$ is already calibrated, i.e., if there exists a hyperpath for each node $v$ to $r$ (i.e., $H_{v,r} \neq \emptyset$) or if node $r$ is reached. In such a case, if the hyperpath going through each $v$ is the shortest one (so far), this hyperpath is established as the shortest one.

4. After having visited any node of the hypergraph, the shortest hyperpath established so far (if any) is returned.

The algorithm runs in $O(\log \frac{V^{E_u}+V}{(V-E_p)(V-E_p)})$ time, assuming that there are $V$ nodes in the hypergraph (including the consolidated node $r$ that has been added) and that there are $E$ hyperedges with: $E_u$ hyperedges reflecting each a single party meeting, and $E_p$ hyperedges
designating multi-party meetings (i.e., $E = E_u + E_p$). More precisely, the main loop of the algorithm extracts one node that has not been visited. All these –unvisited yet– nodes are stored in a min heap of size $V$ which contains the node identification along with the distance to $i$. So, the extraction of the closest node $v$ not yet visited (as performed in line 6) takes $O(\log V)$. The next step consists in checking all the outgoing (single-party and then multi-party) hyperedges of $v$. First, we consider any single-party hyperedge and we store the shortest distance to the node $v$ accessible through this hyperedge. If that node is not yet visited, we add it to the list of unvisited node $Q$; given that at most $V$ nodes are not yet visited, we have a total cost of at most $O(V \log V)$. On the other hand, if the node $v$ is already in $Q$, its priority may be increased considering the shortest distance to $i$, leading to a cost of $O(E_u \log V)$. Therefore, so far, the total run time is $O(V \log V + E_u \log V)$, which is $O(E_u \log V)$ because $V$ is $O(E_u)$ assuming a connected hypergraph. In addition, we consider the analyses of $E_p$ multi-party rendezvous. For each of them, there are at most $V$ hyperpaths established using a hypergraph containing at most $V - 1$ nodes and $E_p - 1 + E_u$, leading to the overall time complexity:

$$ 
\begin{aligned}
E_u \log V + \sum_{i=1}^{E_p} V^i \log(V-i) &\sim E_u \log V + \log \prod_{i=1}^{E_p} (V-i)^{V^i} = E_u \log V + V \sum_{i=V}^{V-E_p} \log i! = \\
E_u \log V + V \sum_{i=1}^{V-E_p} \log i! - V \sum_{i=1}^{V-1} \log i! &< E_u \log V + V \log V - (V - E_p) \log(V - E_p) = \\
&\qquad \log \frac{V^{E_u+V}}{(V-E_p)^{(V-E_p)}}
\end{aligned}
$$

## The multi-hop, multi-party calibration in practice

Summarising the multi-hop, multi-party calibration, any mobile $i$ participating in the collaborative calibration periodically runs the following process:

1. Sensor $i$ detects the presence of the nearby sensing device(s), i.e., the devices in the shared sensing range.

2. Sensor $i$ and the surrounding devices exchange their respective hypergraphs and any node updates its hypergraph (see Algorithm 2).

3. In the presence of any eligible rendezvous, $i$ exchanges its sensing measurements (i.e., time series) in a synchronised manner so as to establish the linear relationship between the measurements of the nearby sensors and the raw measurements obtained locally.

4. The best calibration path is determined, the calibration function is set and the hypergraph is updated accordingly.

The calibration function is a linear function from the actually measured values to the calibrated values. Let the expected calibrated measurements of sensor $i$ be $\tilde{Y}_i$. In order to calibrate the actual measurements $Y_i = (y_i(t_1), \dots, y_i(t_p))^T$, it is required to apply the reversion of the linear relationship for: $Y_i \mapsto \tilde{Y}_i$ simply by replacing the reference values with $\tilde{Y}_i$ and replacing the regressed values $\hat{Y}_i$ with $Y_i$, in Equation (3.17), where $\hat{Y}_i$ eliminates the residual noise error while maintaining the linear relationship from reference to actual measurements. Thus, the calibration function is:

$$ \tilde{y}_i(t) = \frac{y_i(t) - \beta_0}{\sum_{j=1}^{k} \beta_j} \qquad (3.22) $$

where the index $j$ indicates a vertex from the $k$ reference vertices. The multi-hop allows a recursive loop for the calibration process from the reference vertices to all uncalibrated vertices.
<figure><img src="image_20.png" /></figure>

(a) *Mapping of a space:* Spots (green markers) are placed; nodes (red markers) compose a spot and communicate via wireless links (blue lines).

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

(b) *Visualising a pairwise calibration:* On the top, the noise level collected by the two sensors. Below, sound level of the uncalibrated device is expressed as a function of the calibrated device; simple regression line (pink line) and robust regression line (blue line) are traced.

<caption>Figure 3.6 – Prototype GUI.</caption>

## 3.4 Evaluation

In order to assess our calibration solutions, we prototyped a calibration planner as well as the multi-party and the multi-hop calibrator. The calibration planer implements the planing algorithms (§ 3.2.3) and is accompanied with a service (Figure 3.6a) that serves to visualise 3-dimensional maps, place on the maps, the spots that should be visited along with the nodes and the related sensors, and besides provide navigation guidance to the mobile calibrators. In addition, we have implemented an opportunistic calibration system as an Android Application Package (APK). Figure 3.6b illustrates the GUI of the application, which plots the measurements and the regression line. The system is intended to enable pervasive calibration in a fully decentralised way, and thus does not require any central authority. While our approach supports the automated calibration of diverse sensor types, we have focused on noise sensing for our prototype and experiment.

Hereinafter, we evaluate the performance of our proposed multi-sensor calibration planner (§ 3.4.1) and of our mobile calibration system (§3.4.2).

### 3.4.1 Planning the Calibration

We evaluate the performance of our proposed multi-sensor calibration planner, considering the IoT structure, which is deployed at UC Irvine [21, 101] within a smart instrumented building for everyday monitoring and for emergency responses. In particular, we consider the multi-sensor platforms (called SCALE boxes) consisting of a Raspberry-Pi-based multi-sensor box interfaced with a wide range of sensor types (gas, light, air quality, temperature, seismic, camera, etc.). We conduct a series of evaluations using three sets of input data. The first two ones involve
<figure><img src="image_22.png" /><figcaption>(a) Average cost vs. number of nodes.</figcaption></figure>

<figure><img src="image_23.png" /><figcaption>(b) Avg. move. time (s) per iter. vs. numb. of nodes.</figcaption></figure>

<figure><img src="image_24.png" /><figcaption>(c) Mean running time (sec) vs. number of nodes.</figcaption></figure>

<figure><img src="image_25.png" /><figcaption>(a) Average cost vs. numb. of sensors N; sensor presence $\Sigma \mathbf{Q}/(N \cdot K)=0.5$.</figcaption></figure>

<figure><img src="image_26.png" /><figcaption>(b) Average movement time (sec) per iteration vs. N; $\Sigma \mathbf{Q}/(N \cdot K)=0.5$.</figcaption></figure>

<figure><img src="image_27.png" /><figcaption>(c) Average cost vs. number of sensors $\Sigma \mathbf{Q}; N=100$.</figcaption></figure>

<figure><img src="image_28.png" /><figcaption>(a) Average cost vs. number of sensors; normal scenario.</figcaption></figure>

<figure><img src="image_29.png" /><figcaption>(b) Mean interval (day) between iterations vs. number of sensors; normal condition.</figcaption></figure>

<figure><img src="image_30.png" /><figcaption>(c) Average cost vs. number of sensors; emergency condition.</figcaption></figure>

<caption>Figure 3.9 – Impact of the number of sensors on the sensor selection in an indoor environment containing 100 nodes.</caption>

the instrumented building at UC Irvine: we consider the actual deployment and we generate additional spots (with sensors and nodes) using a similar pattern. We also synthesised the third data set that relates to an outdoor urban environment in which sensors are placed to monitor noise and air quality. The parameters are summarised in Table 3.1.

In the following, we compare our sensor selection with two naïve sensor selection strategies that aim at “always selecting *all* sensors” (regardless of their TTNC) and “only selecting the *minimal* set of sensors” (*i.e.*, those we must calibrate because their TTNC reaches 0). In addition, we also investigate two simple selection strategies. The former consists in selecting all sensors that are co-located with the sensors that form the minimal set (“*local*”). The latter
<figure><img src="image_31.png" /><figcaption>(a) Movement time vs. number of spots.</figcaption></figure>

<figure><img src="image_32.png" /><figcaption>(b) Number of calibrators vs. number of spots.</figcaption></figure>

<figure><img src="image_33.png" /><figcaption>(c) Running time (sec) vs. number of spots.</figcaption></figure>

Figure 3.10 – Scalability of the multi-path planning solvers and proposed heuristic algorithms.

consists in only selecting the sensors that can automatically calibrate with each other without human intervention and that henceforth do not induce additional calibration time (“local bounded”). For multi-path planning, we evaluate the performance of two MIP solvers (GLPK and Gurobi), our two path planning heuristics (NN-based greedy and GA), and a naïve strategy that sends one calibrator to each spot and that should give the highest cost. The algorithm running time is evaluated on the OpenLab cluster of Dept. Computer Science at UCI, where each computing node has 2x Quad-core Intel Xeon 3.0GHz CPU E5450 CPUs.

## Indoor vs. Outdoor Results:

In an indoor environment (Figure 3.7), our algorithm (TTNI-driven sensor selection and GA-based multi-path planning) always results in a lower average cost for *N* ranging from 5 to 200. Compared to the naïve sensor selection strategies, such as “selecting all sensors” and “selecting the minimal set of sensors” (still considering GA-based multi-path planning), our algorithm combination provides up-to 30% improvement in the long-term average cost. Note that even though our algorithm does not always end up with the lowest cost per iteration (Figure 3.7b), it makes a fair trade-off between the cost and the time (between iterations). Figure 3.7c shows that the time spent to select sensors is short – less than 1 sec for a reasonably complex building incorporating 200 nodes and 60 spots. The same trend also applies in the outdoor environment (Figure 3.8), where the distances between spots are significantly longer (Table 3.1). As the spatial span of the setup grows, the difference among the algorithms becomes more dramatic (note the different y-scale in Figures 3.7a, 3.7b and 3.9a, 3.9b). Certain naïve approaches are very sensitive to this change (Figure 3.9b, “minimal” and “local bounded”), while our algorithm shows stable performance in both settings.

## Normal vs. Emergency Condition Results:

Having demonstrated the effectiveness of our algorithm in indoor and outdoor settings, we further study the performance of our approach in an emergency scenario where the calibration requirements of certain sensor types are increased (Figures 3.10a and 3.10c, note the difference in y-scale). When calibration is required more frequently for some sensors, the naïve/simple approaches suffer from a big increase in average cost, especially when the sensors are deployed densely ($\Sigma Q/(N \cdot K) > 0.5$), while the performance of our algorithm and “local bounded” are less affected. We also notice that unlike the simpler approaches (“local bounded” or “minimal”), our TTNI-driven sensor selection algorithm avoids the desynchronisation of the periodical calibrations, while the “local bounded” strategy does so with a small number of sensors (Figure 3.10b).
Scalability Results for the Multi-Path Planning

Figure 3.10 compares the performance of multi-path planning algorithms for the number of spots $L \le 12$: GA provides close-to-optimal solutions but takes 8–10 sec for $L=12$ (20–60 sec for $L=60$); the greedy heuristic is much faster (approx. 0.5 sec for $L=60$), which makes it suitable as an estimator during the sensor selection planning. GLPK and Gurobi (i.e., the MIP solvers) could not terminate within 48 hours for $L \ge 15$ so we aborted.

3.4.2 Multi-Hop Multi-Party calibration

We evaluate the performance of the proposed multi-hop, multi-party calibration using the
Android app implementation. We specifically run the application on the following Android
devices: 1 Samsung Galaxy S5, 2 Asus Google Nexus 7, 1 Crosscall Trekker-X3, and 1 Huawei
P9 Lite. So as to assess, the performance/quality of the multi-party calibration, we compare
the noise measurements using the mobile phones, with the ones of a professional SLM -*Sound
Level Meter* (SVAN 971 from SVANTEK) that meets the IEC61672 international standard.
This SLM takes 10 samples per second; each sample corresponds to an average of the sound
level power that is sensed during 100ms, on which an A-weighting is applied. Although our
calibration app enables adapting the duration of the calibration and the sampling rate, we use
the setting of the SLM in the following evaluation: 10 samples are registered per second and
the calibration is performed simultaneously with the sound level meter. Figure 3.11 illustrates
some of the undertaken evaluation experiments that we detail hereinafter.

<figure><img src="image_34.png" /><figcaption>(a) Indoor calibration: Three phones perform a multi-party calibration, while another one plays music.</figcaption></figure>

<figure><img src="image_35.png" /><figcaption>(b) *Underground calibration:* Three persons speak in a quiet parking. All are holding their devices next to a wall, while the person in the middle additionally holds a SLM that serves as ground truth.</figcaption></figure>

<figure><img src="image_36.png" /><figcaption>(c) *Outdoor calibration:* Three people meet at a bus station, in a bi-directional street that is relatively noisy.</figcaption></figure>

<caption>Figure 3.11 – Experiments.</caption>

Our evaluation assesses the quality of the regression, and hence of the calibration, accord-
ingly to the following parameters:

- The *variance of the regressand, Var(Y)* – Measures the dispersion of the regression.

* The coefficient of determination [42], R² – Quantifies the goodness of fit of the regression plane, i.e., the amount of variability in the data set that is explained by the regression. The closer R² is to 1 (resp. 0), the greater (resp. lower) the degree of association between Y and the X.
* The adjusted *R*² - Evaluates the goodness of fit and penalises the use of additional variables. The adjusted *R*² increases only if new variables improve the regression more than it would be expected by chance. It remains less or equal to *R*² but it can also be negative.

* The standard deviation of the residual noise, εᵢ.

* The difference/bias between the measurements provided by a calibrated device and the ones of the SLM.

We use *box plots* to depict the above parameters when reporting the evaluation results (e.g., see Figure 3.12): the *triangle* denotes the mean, the *line* inside the box indicates the median, the *lines on edge* reflect the range of values, and the *rectangle* corresponds to the Interquartile Range (IQR).

In order to evaluate the multi-hop, multi-party calibration, we consider the following scenarios:

1. Comparison between the simple and robust regression (§ 3.4.2).

2. Comparison between univariate (pairwise) and multivariate (multi-party) regression (§ 3.4.2).

3. Comparison of multi-hop, pairwise with multi-hop, multi-party calibration (§ 3.4.2).

4. Evaluating the impact of the environment (in-door vs out-door) on multi-party calibration (§ 3.4.2).

The first three scenarios involve in-door calibration within a room (see Figure 3.11a), while the fourth also considers the underground and out-door cases (see Figures 3.11b and 3.11c). In most of the experiments, the devices were less than 1 meter away from each other, except when we consider the impact of the following sensing conditions: distance, obstacle and in-/out-pocket.

## Simple versus Robust Regression

We compare the simple vs robust regression using an uncalibrated device (the Crosscall Trekker-X3) and two devices (the 2 Asus Google Nexus 7) that were previously calibrated with the SLM, and that exchange the noise level they collected during 10s. The experiments were run in-door, 100 times.

Figure 3.12a (resp. 3.12b) compares the robust regression with the simple regression considering the variance of the regressand (resp. the standard deviation of the regression residuals). As shown, the robust regression provides a lower regressand variance in terms of mean and median. In particular, the average value of the variance corresponds to 11.984 with the simple regression and 5.529 with the robust regression. In fact, the robust regression reduces the influence of outliers, which leads to a lower regressand variance and thereby to a more accurate regression. Also, the regression residuals (Figure 3.12b) produced by a robust regression is characterised by a weaker standard deviation: the average value of this standard deviation is equal to 1.531 dB(A) for the simple regression and 0.915 dB(A) for the robust regression. Meanwhile, the IQR of the standard deviation exhibited by the robust regression, i.e., [0.402dB(A), 1.336dB(A)], is much lower, compared to the one provided by the simple regression, i.e., [1.019dB(A), 2.017dB(A)].

In order to evaluate the computational overhead and accuracy of the robust regression, we use the same three devices and we run series of calibrations characterised by various sampling durations; we execute 20 times each of these series.
<figure><img src="image_37.png" /><figcaption>(a) The regressand variance for simple vs robust multivariate regressions.</figcaption></figure>

<figure><img src="image_38.png" /><figcaption>(b) Standard deviation of the residual for simple vs robust multivariate regressions.</figcaption></figure>

<figure><img src="image_39.png" /><figcaption>(a) Duration induced by the establishment of a multivariate regression according to the sampling duration.</figcaption></figure>

<figure><img src="image_40.png" /><figcaption>(b) Adjusted $R^2$ attained from a robust multivariate regression according to the sampling duration.</figcaption></figure>

<caption>Figure 3.13 – Impact of the sampling duration on the performance of multivariate regression.</caption>

The robust regression induces a significant computational overhead (see Figure 3.13a) because many regressions are established and further compared so as to ultimately select the regression that best fits. As an illustration, the simple (resp. robust) regression takes around 7.159 ms (resp. 969.561 ms) when taking 100 sound samples; with 600 samples, the robust regression lasts for around 2035.791 milliseconds. However, this is to be balanced with the resulting adjusted $R^2$ of the robust regression (Figure 3.13b), which increases and reaches a maximum for a recording duration of 40s and then decreases. This shows that there is no need for unnecessarily increasing unnecessarily the calibration duration.

In what follows, we consider only the robust regression.

## Univariate versus Multivariate Regression

We used the same three devices as above to conduct one-to-one and one-to-two regressions, 100 times each. Figure 3.14a (resp. 3.14b) evaluates and compares the accuracy of the (robust) univariate vs multivariate regression in terms of $R^2$ (resp. adjusted $R^2$). The multivariate regression always has higher $R^2$ and adjusted $R^2$ compared to the univariate case. As an illustration, an univariate regression (resp. bivariate regression) generates an average and adjusted
<figure><img src="image_41.png" /><figcaption>Figure 3.14 – Univariate versus robust multivariate regression.</figcaption></figure>

$R^2$ of 0.335 – 0.343 as raw– (resp. 0.504 – 0.516 as raw). We observe the same trend with the interquartile range. When the number of calibrated devices increases, both the $R^2$ and adjusted $R^2$ also increase. This suggests that the multivariate regression provides a better fitting than the –state of the art– univariate approach.

<figure><img src="image_42.png" /><figcaption>Figure 3.15 – Pairwise *vs* multi-party calibration.</figcaption></figure>

We now compare the pairwise (univariate regression) with the multi-party calibration (multivariate regression), using 40s, instead of 10s, measurements. We further confronted the noise measurements provided by the newly calibrated smartphone with the ones provided by the SLM over a duration of 100 seconds. Figure 3.15a shows that after a multi-party calibration, the bias between the measurements provided by the device that gets calibrated and the two calibrated devices is drastically reduced. And, quite noteworthy, Figure 3.15b shows that the difference between the measurements provided by the newly calibrated device and the SLM decreases as the number of calibrated devices participating to a calibration rendezvous increases. Overall, the multi-party calibration is more accurate.
<figure><img src="image_43.png" /><figcaption>Figure 3.16 – Multi-hop, multi-party calibration scenarios.</figcaption></figure>

<figure><img src="image_44.png" /><figcaption>Figure 3.17 – Indoor multi-hop multi-party calibration.</figcaption></figure>

Multi-hop, Multi-Party Calibration

We now investigate a multi-hop, multi-party calibration that takes place during 30s in an
indoor environment (see Figure 3.16). In the scenario, Device 4 is the only device that has been
calibrated with an end reference node (i.e., the SLM). Device 1 has three options to calibrate:
(1) with Device 2 (top Figure 3.16a), (2) with Device 3 (bottom Figure 3.16a), (3) with both
Devices 2 and 3 (Figure 3.16b). That is, there are three potential hyperpaths (§ 3.3.2): two
correspond to some consecutive pairwise calibrations (i.e., 1 → 2 → 4 → reference, and
1 → 3 → 4 → reference) and one refers to the sequence of both multi-party and pairwise
calibrations (i.e., 1 → {2, 3} → 4 → reference). Figure 3.17a depicts the measurements of
Device 1 before calibration and after calibration for each of the 3 cases; the figure also provides
the measurements of the SLM. Each of these hyperpaths (calibrations) is characterised by a
specific accuracy, which can be assessed by comparing the measurements provided by the SLM
with the ones from Device 1. Figure 3.17b shows that the bias between the measurements
provided by Device 1 and the SLM decreases from 1 → 2 → 4 → reference and 1 → 3 → 4 →
reference to 1 → {2, 3} → 4 → reference. The difference between the two former hyperpaths
is not significant while the third hyperpath is characterised by a lower bias to the SLM. Table 3.2
considers additional metrics for weighting the hyperedges (i.e., the mean residual R² and the
residuals σ). In such a case, the shortest hyperpath is the one having either the highest R², or
the lowest mean residual and the lowest σ (residuals).
In order to evaluate the execution time of the multi-hop, multi-party calibration, we generate a large-scale and random hypergraph. In this hypergraph, each hyperedge is characterised by a head whose cardinality is chosen randomly. In addition, the hypergraph is created so that there exists a hyperpath between the source of the hypergraph and the consolidated node. Figures 3.18a and 3.18b analyse the time needed to compute the shortest hyperpath from the source to the consolidated node. In particular, the time taken to compute the shortest hyperpath (Figure 3.18b) increases linearly with the number of hyperpaths because the length of the hyperpath increases proportionally. Meanwhile, the time taken to compute the shortest path is proportional to the size of the multi-party calibration group.

<figure><img src="image_45.png" /><figcaption>(a) Time induced by computing the shortest hyperpath between the source and the consolidated node with an hypergraph including 500 nodes and 3 end reference nodes.</figcaption></figure>

<figure><img src="image_46.png" /><figcaption>(b) Time induced by computing the shortest hyperpath between the source and the consolidated node with an hypergraph with 3 end reference nodes and meetings involving at most 3 nodes.</figcaption></figure>

<caption>Figure 3.18 – Scalability analysis.</caption>

## Impact of the Sensing Conditions

<figure><img src="image_47.png" /><figcaption>(a) Bias observed in an indoor environment.</figcaption></figure>

<figure><img src="image_48.png" /><figcaption>(b) Bias observed in a street characterised by a high traffic.</figcaption></figure>

<caption>Figure 3.19 – Controlled calibration using pink noise vs blind calibration using ambient noise.</caption>

We conclude the evaluation with the study of the impact of the sensing environment on the multi-party calibration. We first compare the calibration that is performed in a laboratory using pink noise with the one performed in an indoor/outdoor environment using ambient noise. We consider the calibration accuracy defined by the bias observed between the sound levels provided
by a SLM and the one given by a newly calibrated device. Figure 3.19a (resp. 3.19b) provides the accuracy in the indoor (resp. outdoor) case. We note that when the calibration is performed in the same environment, the blind and lab calibrations have almost the same accuracy. When the calibrations are performed in different environments, the difference between a blind and a lab calibration remains under acceptable limits (i.e., $\le 1dB(A)$).

<figure><img src="image_49.png" /><figcaption>(a) Impact of the distance: The uncalibrated smartphone is placed near a person that speaks and in the middle of the two calibrated smartphones.</figcaption></figure>

<figure><img src="image_50.png" /><figcaption>(b) Impact of obstacles: The uncalibrated smartphone is placed at a wall corner and 2 calibrated smartphones are placed on the two corner sides, near two persons speaking.</figcaption></figure>

<figure><img src="image_51.png" /><figcaption>(c) Impact of a smartphone placed in a pocket: The uncalibrated smartphone calibrates with two calibrated smartphones (one in the pocket and the other out-of pocket).</figcaption></figure>

Figure 3.20 – Impact of the calibration conditions.

Finally, we investigate the impact that different operational conditions may have on the calibration, while performing the study in a quiet indoor environment. We specifically consider the impact of: the distance between the devices involved in the calibration rendezvous, the presence of an obstacle, and the presence of a device in a pocket. As expected, the calibration is more accurate (Figure 3.20a) when the devices are very close to each other because they are exposed to the same sound. For instance, the mean residuals after calibration are 1.973, 2.460 and 3.546 dBA for 0, 5 and 10-meter distances, respectively. In general, such a trend is not always observed given that the audio signal can reverberate on obstacles or can be obstructed by obstacles (Figure 3.20b). Even though, the multi-party calibration plays an essential role to mitigate the impact of the obstacle, the residual noise can be used to determine whether the calibration should be effective or abandoned. We end this evaluation by looking at the impact that a smartphone located in a pocket may have (Figure 3.20c). The uncalibrated device favors the smartphone outside the pocket by giving it a high $\beta$ value compared to the one given to the device in the pocket, therefore showing the robustness of the multi-party calibration. This is thanks to the fact that measurements in different context have low correlation.

## 3.5 Conclusion

We are witnessing the emergence of some infrastructure-based and crowd-driven applications opening up previously unprecedented ways of linking the human with the physical world. Our increased interconnection with the physical world also holds the promise of an enhanced environmental and social sustainability built upon a better understanding about, and act upon, the physical environment. While expectations are high, monitoring a phenomena at an unprecedented scale is challenging, especially considering that applications must provide the expected meaningful data in any circumstances, regardless of e.g., disturbances, harsh conditions. We are
addressing this challenge through the calibration of the IoT nodes, from the fixed Things that
make up the IoT infrastructure to the mobile Things that people carry. Cost-effectively plan-
ning the on-site calibration of IoT infrastructure helps in the sustainable long term operation
of deployment and in the enhancement of the quality for the gathered observations. We frame
multi-sensor calibration planning as an optimisation problem where we propose a two-phase
iterative local optimization approach to determine (a) how many calibration iterations are nec-
essary, (b) which sensors should be calibrated at each of these iterations, and (c) the number of
mobile calibrators that are required (as well as their respective calibration paths), such that the
average cost of all iterations is minimised and under the constraint that the calibrators should
not be overloaded. The proposed two-phase iterative local optimisation approach first creates a
selection of sensors for each iteration, and introduces new methods (mTSP variants, heuristics)
to compute a set of paths for the calibrators based on the selection. Our evaluation shows
that the proposed algorithms solve the calibration planning problem effectively compared to
naïve/simple solutions. Such calibration solution constitutes a pragmatic approach to support
the full-fledged deployment and flexible maintenance of an IoT network infrastructure that is
not always uniformly and continuously available. In order to accommodate budget constraints
without sacrificing the coverage of the phenomenon of interest, we aim at exploiting all available
sensing modalities –fixed as much as mobile– for increased sensing coverage.

Mobile crowdsensing is becoming one of the most promising paradigm supporting social sensing, as it allows to significantly decrease the infrastructure costs and to supply fine-grained information about the phenomenon of interest. In counterpart, the prevalence of low-cost sensors and the presence of human in the sensing loop brings into the picture new research challenges, most of which are yet to be understood and addressed. smartphone sensors are not typically of the same fidelity as task-specific sensors (e.g., a noise pollution monitor vs. smartphone microphone). As a matter of fact, the control of the sensing process is delegated to people that lack of expertise and experience. Inadvertent or erroneous handling of the phone (e.g., phone acting as a noise sensor located in the pocket) may adversely influence the quality of the data, irrespective of the willingness of the participants.

This leads us to introduce a novel macro-calibration problem where numerous devices need
to calibrate without involving the end-users. To tackle this new problem, we introduce an oppor-
tunistic macro calibration system that leverages the high density of smartphones in the urban
environment to support a seamless and multi-party calibration. Our multi-party calibration
system coordinates multiple surrounding smartphones and leverages multivariate and robust
linear regression to handle outliers. We have implemented and experimented our solution. Our
prototyped system contributes to enhancing the accuracy of mobile phone sensing. In particu-
lar, our evaluation shows that a multi-party regression is characterised by an accuracy that is
always higher, and, in the worst case, equal to the accuracy of a pairwise regression. During our
experiments, we investigated the actual impact of faulty measurements that potentially lead
to incorrect calibration, i.e., outliers and non relevant measurements obtained by some phone
operating within another sensing context (such as those provided by a calibrated phone in a
pocket). As presented, our approach leverages robust regression, which systematically discards
outliers. In addition, our evaluation shows that our approach allows distinguishing the actual
sensing contexts (e.g., measurements taken with the phone(s) in the pocket), which explains
by the lack of correlation between the related measurements. Consequently, the phone in the
pocket is assigned a negligible weight or is even ignored. Even though the impact of these
recognisable faulty measurements remains insignificant, the fact remains that some incorrect
calibration parameters or measurements that have been (intentionally or unintentionally) al-
tered may impair a multi-hop calibration. In practice, the regression minimises the squared
distance between the measurements of the uncalibrated and calibrated nodes, which compensates for small discrepancies among the (miscalibrated and well-calibrated) measurements. In general, we argue that the multi-party calibration allows for a more precise characterization of the relationship between crowdsensors than would a pairwise calibration.

Once calibrated – static as much as mobile – sensors provide some observations that are expressed with regards to a common reference system. Their interpretation of the observation depends on the conditions under which they are made. For example, if we are interested in a temperature sensor, knowing whether the sun is hitting is crucial. Same applies with noise observation, previous analysis [83, 165] of the noise observations collected from the opportunistic crowdsensing application Ambiciti (formerly SoundCity) showed that less than 5% of the collected data were of sufficient quality to be considered for use in the mapping of urban noise pollution.
function solveMPPGreedy (G, $\hat{c}$, H, $\beta$);

**Input** : G – Map; $\hat{c}$ – Maximum workload;

H – Set of selected spots;

$\beta$ – Vector of calibration time at selected spots.

**Output:** {W} – Set of paths.

Initialize pathSet ← [];

while H is not empty do

minInc ← +∞; minSp ← minPath ← null;

for each path in pathSet; last ← path[-1] do

oldTime ← getMoveTime (path) + Σ$_{l}$∈path $\beta_l$;

for each sp in H do

dCw ← G last, sp] + G sp, 1] − G last, 1] ;

if oldTime + dCw + $\beta_{sp}$ ≤ $\hat{c}$ then

if dCw < minInc then

minInc ← dCw ;

minSp ← sp; minPath ← path;

end

end

end

end

if minInc is finite then minPath.append (minSp);

else

for each sp in H do

if (dCw ← G [1, sp] + G [sp, 1]) < minInc then

minInc ← dCw; minSp ← sp;

end

end

newPath ← [minSp]; pathSet.add (newPath);

end

H.del (minSp);

end

return {W} ← convertPathVecToMatrix (pathSet);

**Algorithm 1:** Nearest-neighbor-based greedy algorithm for the multi-path planning problem.
**Input:** *i*: source node

*r*: consolidated reference node

*H*<sub>*i*</sub>: hyperpath from *i*

**Output:** SH<sub>*i*,r*</sub>: shortest hyperpath from *i* to *r*

begin

$H_{i,v} \leftarrow \emptyset$ for all $v \in V$

$|H_{i,i}| \leftarrow 0, |H_{i,v}| \leftarrow \infty$ for all $v \in V \setminus i$

$Q \leftarrow V$

while $Q \neq \emptyset$ do

$u \leftarrow u'$ subject to $\min_{u' \in Q} |H_{i,u'}|$

forall $E_j \in E$ so that $u = tail(E_j)$ do

if $|head(E_j)| = 1$ then

$v \leftarrow head(E_j)$

if $|H_{i,u}| + w(E_j) < |H_{i,v}|$ then

$|H_{i,v}| \leftarrow |H_{i,u}| + w(E_j)$

$H_{i,v} \leftarrow H_{i,u} \cup \{v\}, E_j$

end

end

if $|head(E_j)| > 1$ then

forall $v \in head(E_j)$ do

$|H_{v,r} \leftarrow SHPath(v, E \setminus E_j \setminus H_{i,u}, r)$

end

if $(H_{v,r} \neq \emptyset \; || \; v = r)$ for all $v \in head(E_j)$ then

if $|H_{i,u}| + w(E_j) + \sum_{v \in head(E_j)} |H_{v,r}| < |H_{i,r}|$ then

$|H_{i,r}| \leftarrow |H_{i,u}| + w(E_j) + \sum_{v \in head(E_j)} |H_{v,r}|$

$SH_{i,r} \leftarrow H_{i,u} \cup E_j \cup H_{v,r}$

end

end

end

end

end

if $|H_{i,r}| < |SH_{i,r}|$ then

$SH_{i,r} \leftarrow H_{i,r}$

end

return SH<sub>*i*,r*</sub>

end

**Algorithm 2:** SHPath(*i*, *H*, *r*) - Shortest Hyperpath from *i* to *r* in hypergraph *H*
<table><caption>Table 3.1 – Experimental setup for the performance evaluation.</caption><thead><tr><th colspan="2">Input Data</th><th colspan="2">Indoor</th><th>Outdoor</th></tr><tr><th></th><th></th><th>Normal</th><th>Emergency</th><th></th></tr></thead><tbody><tr><td rowspan="2">Map</td><td>L Num. of Spots</td><td colspan="2">60</td><td>63</td></tr><tr><td>G Pairwise Dist.<sup>a</sup></td><td colspan="2">≤53 sec</td><td>≤73 min</td></tr><tr><td rowspan="3">Sensor</td><td>K Num. of Types</td><td colspan="2">10</td><td>8</td></tr><tr><td>τ Calib. Time</td><td colspan="2">1–30 min</td><td>0.25–1 min</td></tr><tr><td>T Calib. Period</td><td>14–91 d</td><td>7–91 d</td><td>28–123 d</td></tr><tr><td rowspan="2">Nodes</td><td>N Num. of Nodes</td><td colspan="3">100 (varies if independent variable)</td></tr><tr><td>Sensor Presence</td><td colspan="3">100 (varies if independent variable)</td></tr><tr><td rowspan="3">User Req.</td><td>ĉ Max. Workload</td><td colspan="2">2 hours</td><td>4 hours</td></tr><tr><td>μ Coefficients</td><td colspan="2">C<sub>it</sub>=10000, μ<sub>0</sub>=1, μ<sub>w</sub>=5, μ<sub>c</sub>=1</td><td></td></tr><tr><td>T Maintenance P.</td><td colspan="3">360 days</td></tr></tbody></table>

<table><caption>Table 3.2 – Hyperpath weighting</caption><thead><tr><th>Weight/Edges</th><th>(1, 2)</th><th>(1, 3)</th><th>(1, {2,3})</th><th>(2, 4)</th><th>(3, 4)</th></tr></thead><tbody><tr><td>Adjusted R<sup>2</sup></td><td>0.564</td><td>0.529</td><td>0.570</td><td>0.511</td><td>0.444</td></tr><tr><td>Mean of the residuals</td><td>2.504</td><td>2.515</td><td>2.478</td><td>3.5e-14</td><td>1.9e-14</td></tr><tr><td>σ(residuals)</td><td>1.079</td><td>1.073</td><td>0.786</td><td>2.515</td><td>2.645</td></tr></tbody></table>
# Leveraging Crowdensors to support Context-aware and cost-effective Crowdsensing

## 4.1 Introduction

Crowdsensing is becoming one of the most promising paradigms supporting the vision of social sensing: citizens may contribute valuable spatio-temporal observations using the low-cost, yet powerful, sensors embedded in their smartphones/tablets, with the GPS for positioning and the Internet access for uploading. As opposed to mere physical equipment that only senses the environment and transfers data, crowdsensor should be treated as "social sensor".

There is a wide range of users' engagements to sensing tasks [94, 65], which depend on how the smartphones' owners contribute observations [94, 65], which may be either: (i) pro-actively, aka *participatory crowdsensing* [74, 90]; or (ii) passively in the background, aka *opportunistic crowdsensing* [37, 102]. *Participatory crowdsensing* allows covering a specific area while maximising the number of tasks that each participant may achieve [91] through careful path planning. On the other hand, *opportunistic crowdsensing* makes it easy to collect a massive amount of observations across time and space. Indeed, there is no burden put on the end-users. The human presence in the sensing loop brings into the picture new research challenges, most of which are yet to be understood and addressed. With participatory sensing, the massive collection of data often necessitates the participants' long term commitments, which are very hard to achieve in practice, mainly due to the practical problem of "hiring" motivated volunteers. Participants lack the technical skills required to set-up and maintain sensors. Participatory sensing is critiqued as a top-down approach allowing non-experts to participate in scientific progress. In other words, participatory sensing is perceived as being closer to a participatory push [62] as opposed to a "form of science developed and enacted by citizens themselves". On the other hand, the opportunistically-collected observations often cover the urban space and time unevenly, due to the mobility of citizens throughout the city. In addition, previous analysis [83, 165] on the noise observations collected from the opportunistic crowdsensing application Ambiciti (formerly SoundCity), showed that less than 5% of the collected data were of sufficient quality to be considered for use in the mapping of urban noise pollution.

Our approach to support the democratisation of environmental crowdsensing, lies in supporting an opportunistic and collaborative crowdsensing. State-of-the-art opportunistic crowdsensing systems address the aforementioned shortcoming – namely the uneven coverage of the urban space and the low-quality of the collected observation – through the centralised analysis – spanning filtering, aggregation and interpolation– of the contributed observations on cloud/edge infrastructure servers [93, 108, 69, 68, 166]. The implemented centralisation then severely limits the adoption of crowdsensing for environmental monitoring due the resulting resource cost and threat to privacy. Instead, our approach is to allow a fully distributed, collaborative approach
to crowdsensing: Crowd sensors interpolate data, and aggregate their respective contributions to the observations of the phenomenon in a collaborative way, so as to overcome the spatio-temporal sparsity and to limit –or even avoid– the use of a centralised infrastructure server. We support a distributed solution to the problem of collection, interpolation and aggregation on the Move, which builds upon the two following trends to support crowdsensing-based environmental monitoring at scale:

(i) We view crowdsensors as "social sensors" that often encounter each other during crowd-sensing campaigns or as part of their owners' daily routine. When the crowdsensing is opportunistic, participants follow their daily routine without being directly involved in the sensing task [37]. Thus, at the micro level, behavioural signatures (i.e., routines) as well as recurrent meeting patterns reflect the underlying relational dynamics of organisations or communities to which the user is affiliated [97]. Participatory crowdsensing campaigns bring groups of people together to meet, exchange information and share their findings [10], with the aim of improving the quality of the data collected for better impact on the ground [18]. Compared to the opportunistic crowdsensing, participants in participatory campaigns meet more often and contribute finer scale measurements but cover smaller areas [169]. In both cases, the end-users are more likely to share their information, especially in short meetings, as the risk of losing their anonymity is lower [88].

(ii) The control of the sensing process is delegated to people, who may choose to deliver (or not) relevant information depending on their context as well as their personal constraints, such as financial budget, time, smartphone battery, available network bandwidth. Other factors may also influence the quality of submitted sensing measurements. In particular, smartphone sensors are not typically of the same fidelity as task-specific sensors (e.g., a noise pollution monitor vs. smartphone microphone). Besides, inadvertent erroneous handling of the phone (e.g., phone acting as a noise sensor located in the pocket) coupled with the lack of experience in performing the sensing task (e.g. blurry photo captured by mistake) may adversely influence the quality of the data, irrespective of the willingness of the participants.

(iii) The collaborative and ubiquitous processing of crowdsensor observations improves the overall efficiency of the system in terms of resource consumption [176], regarding both the infrastructure and contributing devices. It also allows end users to collaborate and share knowledge effortlessly and with little or no cost. In particular, D2D collaboration enhances mobile edge computing by enabling the sharing of heterogeneous computing and communication resources between powerful mobile end-devices [36].

The design rationale of our crowdsensing solution directly derives from the social nature and in particular from the location-, context- and time-dependence of the crowd sensors: co-located crowd sensors contribute related observations [96], and may thus collaborate toward improving the provided contributions and avoiding unnecessary duplication of work. More precisely, the crowdsensing tasks that need to be performed at the edge encompass: environment sensing, location provisioning, data processing, and uploading to the cloud. Then, while the replication of physical sensing within a group potentially allows for the gathering of more accurate knowledge, any of the other tasks only need to be performed by the most cost-effective group member(s). The fact that people tend to group [43, 150] as part of their daily activity, follow a daily/weekly routine [61, 47], and are most of the time still [83] further supports such a edge-based collaborative strategy to opportunistic crowdsensing.
Beyond the user's mobility which is relevant to initiate the collaboration with the nearby crowdsensors, to know whether the smartphone is in-/out-pocket, in-/out-door and under-/on-ground is particularly important because the smartphone/sensing device needs to be in a position that enables – yet does not interfere with – sensing the physical characteristics of the surrounding. The sensing context must distinguish between in-pocket and out-pocket observations because the former lead to a quite significant deviation from the ground truth and are thus not readily usable [130]. The same applies to in-door versus out-door – as much as under-ground and on-ground – measurements since aggregating them together to analyse environmental phenomena obviously leads to unreliable results [106]. The context information allows keeping more observations -and even correcting them- for aggregating environmental knowledge, rather than filtering out drastically the crowdsensed data. We qualify as "context" the combination of these criteria. Our aim is to create dynamic context-aware collaborative groups of crowdsensors, which are such that the peers within any given group: (i) Stay together for a long-enough time period so as to prevent constant changes and unnecessary grouping re-configuration; (ii) Operate within the same physical environment (e.g., in-door vs out-door) and hence sense related physical phenomena; and (iii) Perform the same activity so that they behave alike –e.g., it is preferable that all the crowdsensors that collaborate either move together or are still. Then, upon the creation of a group, the middleware distributes the crowdsensing tasks to the most adequate group members according to the nodes’ abilities –e.g., a smartphone located in the pocket cannot adequately sense the surrounding sound level. Overall, our approach fosters opportunistic collection of the observations that puts minimum burden on the end-users, while increasing the accuracy and resource-efficiency of the crowdsensing system.

Still, a major issue is to cope with the absence of observations due to the uneven distribution of the crowdsensors and the resulting spatio-temporal sparsity of crowdsensors in some specific areas. Concretely, our solution also allows a fully distributed, collaborative approach to support the interpolation of data and aggregation of the respective contributions to the observations of the phenomenon, so as 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, and the smartphone is becoming increasingly powerful to perform such advanced tasks. At the same time, P2P wireless ad hoc network technology (e.g., WiFi Direct) enables the discovery of nearby mobile devices and the exchange of data between peers, making the collaboration possible [54]. Some crowdsensing systems already exploit the P2P collaboration of crowdsensors as they meet [170, 46, 177]. However, the collaboration 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 – spanning the interpolation and aggregation – on the move, across the crowdsensors.

## 4.2 Context-Awareness sustaining a Collaborative Crowdsensing

A major challenge is to cope with the dynamics and heterogeneity of the crowdsensors: the user activity, the resources available on the device, and the position of the sensors/smartphones are all criteria that characterise the crowdsensor's contribution to the upper layer application. We qualify as *context* the combination of these criteria.

The accurate monitoring of the physical environment through crowdsensing requires the contextualisation of the contributed observations because the context impacts the quality of