Optimization model for resource allocation of multiple applications in virtual sensor networks

The recent years have seen interesting growth in the arena of Wireless sensor networks (WSNs) which have become nowadays ubiquitous in several applications environments. Nevertheless, the classical design approach of WSNs is highly "vertical" with network deployments tightly customized on the needs of one or very few specific applications (one-application/one-network design approach). Hence, an increasing need towards efficient design of general purpose, easy-reconfigurable WSNs started recently attracting considerable attention in the research community. This view encompasses the creation of Virtual Sensor Networks (VSNs) in which multifold physical resources (sensor nodes, communication protocols, etc.) are virtually shared by multiple concurrent applications seamlessly. The VSNs’ vision essentially is represented in moving away from highly-customized, application-specific wireless sensor network deployment by opening up to the possibility of dynamically assigning general purpose physical resources to diverse stakeholder applications. In this context, in the present thesis, we propose a novel optimization framework to perform resource allocation in Virtual Sensor Networks where the physical network infrastructure is shared among several types of applications. The proposed framework aims to maximize the benefit from application deployment in the network, while accounting for the distinguishing characteristics and limitations of the wireless sensor environment (storage, processing power, bandwidth, tight energy consumption requirements). To reach our ambitious goal, this thesis will start off by concentrating on the design and analysis of a virtual sensor network where different kinds of applications and sensor nodes coexist and cooperate. Afterwards, several mathematical models are provided to address this optimization problem of maximizing the overall revenue out of the application deployment process while minimizing the cost related to activating sensor nodes considering the constraints regarding sensor nodes capabilities (memory, computation, energy) and network limitations (topology, shared bandwidth). On one hand, due to the complexity of the optimization problem, efficient heuristics and algorithms have also been introduced. On another hand, the resource allocation of multiple applications in VSN study has been tackled from two perspectives: a static one in which the set of applications is known in advance, and a dynamic one where the applications arrive dynamically. To this extent, we start off by analyzing the static case then we extend the proposed model to the dynamic case to cover the problem of dynamically addressing the deployment of new applications as they arrive to the network. The proposed models and algorithms are finally evaluated by considering realistic parameters for network topologies, sensor nodes and deployed applications to assess the efficiency of the different proposals. The obtained results show the potential performance gains provided in our work by sharing a general purpose wireless sensor network with respect to stand-alone vertical network deployments advocating the utility of Virtual Sensor Networks and their impact in terms of efficiency, cost reduction and flexibility.

Le reti di sensori radio hanno conosciuto negli ultimi anni uno sviluppo notevole sotto la spinta del nuovo paradigma dell’Internet degli Oggetti (Internet of Things). L’approccio progettuale classico delle reti di sensori é fortemente verticale con la realizzazione di reti strettamente personalizzate ed ottimizzate sulla base di una (o poche) applicazioni specifiche (approccio "una rete-un’applicazione"). Se da un lato tale approccio consente ottimizzazioni spinte sulla base delle esigenze di una singola applicazione, d’altra parte risulta scarsamente flessibile. In questa ottica, si inserisce l’esigenza di strumenti per il progetto e l’ottimizzazione di reti di sensori facilmente riconfigurabili, che stanno ricevendo notevole attenzione nella comunitá scientifica negli ultimi anni. In tali reti, anche note con il nome di reti di sensori virtuali (Virtual Sensor Networks), la risorse fisiche di rete (nodi sensore, protocolli di comunicazione) sono virtualmente condivise da molteplici applicazioni simultaneamente in maniera del tutto trasparente. La presente tesi propone modelli di ottimizzazione ed algoritmi per allocare le risorse in reti di sensori virtuali in cui l’infrastruttura di rete fisica é condivisa tra diversi tipi di applicazioni. L’approccio proposto tende a massimizzare il numero di applicazioni che possono essere supportate dalla rete, tenendo conto di vincoli mutuati dalle caratteristiche distintive delle reti di sensori radio come la banda di comunicazione disponibile, la potenza di calcolo disponibile, lo spazio di memorizzazione disponibile e l’interferenza tra comunicazioni concorrenti. Nella prima parte della tesi ci si concentra su un caso statico in cui l’insieme delle applicazioni che devono coesistere nella rete di sensori virtuale é noto a priori. Viene proposto un modello di ottimizzazione che massimizza il numero di applicazioni installate in rete tenendo conto della disponibilitá corrente di risorse in rete. Il modello do ottimizzazione é suc- cessivamente usato per valutare il guadagno dell’approccio a rete di sensore virtuale rispetto all’approccio classico di tipo verticale. Il modello di ottimizzazione per il caso statico é in seguito esteso nella seconda parte della tesi anche al caso dinamico in cui l’insieme delle applicazioni da supportare non é noto a priori, ma le singole applicazioni arrivano nel sistema secondo un processo casuale specifico. Dal momento che il problema affrontato é NP-difficile, sia nel caso statico che in quello dinamico, vengono infine proposti algoritmi efficienti per la sua soluzione che restituiscono soluzioni vicine all’ottimo in un tempo di calcolo limitato. I modelli di ottimizzazione e gli algoritmi proposti sono valutati su topologie di reti di sensori realistiche ed i risultati ottenuti dimostrano che l’approccio proposto di condividere risorse fisiche tra applicazioni multiple ed eterogenee presenta vantaggi rispetto all’approccio verticale in cui una rete di sensori é dedicata ad una singola applicazione.