Distributed Optimization and Data Recovery for Wireless Networking

My research activity focused on the field of heterogeneous wireless networks and has been particularly inspired by the problem of sensing a city-wide environment through a large scale, partially distributed, mobile and low cost network (possibly composed of mobile phones or similar user’s equipment). In my PhD thesis I have been guided by the grand vision of a two tier architecture which integrates existing cellular systems with different types of distributed networks (these could be mixtures of ad hoc, sensor networks and soon). In fact, a fully distributed infrastructure alone would be inappropriate when the network is very large in size and highly populated (e.g., urban area networks). In such a case, the network organization itself would be energy draining and probably impractical. On the other hand, a cellular system alone does not have the flexibility and the instruments to get a fine grained view of all the data generated within such a network. This envisioned scenario, besides featuring a number of mobile phones, also consists of a mixture of embedded devices, which are expected to have on-board radio and sensing capabilities. Nowadays technology makes us more and more able to control the environment we are in through motion sensors, GPS, health care devices, microphones and video-cameras. Wireless Sensor Networks (WSNs), for instance, are infrastructures made of small devices (nodes) equipped with “intelligent sensors” able to sense their surroundings for, e.g., light, temperature, humidity and/or pollution. Therefore, mobile phones as well as other network elements, including base stations, routers and access points hosting diverse wireless and wired technologies, can cooperate to accomplish a common task like the detection of a fire or the monitoring of a physical phenomenon. Exploiting the fact that cell phones are becoming a communication hub in our daily life, we can foresee the integration of standard cellular systems with overlayed distributed networks such as WSNs. The ultimate goal of this is to “connect” everything has some communication capability, possibly providing self-configurability and self-adaptability of the network. We note that current cellular networks already implement some of these features: user positions, to a certain extent, can be tracked already and services can be provided based on contextual information. As a matter of fact, we are depicting a Delay Tolerant Network (DTN) scenario, where heterogeneous, sparse and/or mobile wireless networks communicate with each other, but where, due to the inherent nature of the infrastructure itself, no continuous connectivity can be assumed. The above grand vision entails quite a few challenges, and during my research activity I have been focusing on the following ones: 1) the design of reconstruction algorithms that from a subset of the data (i.e., from the collection of the sensor readings from a small fraction of nodes) are able to reconstruct with high accuracy the data monitored over the entire sensor field (these algorithms allow for scalability of the system as they decrease the number of data packets to collect for a given accuracy goal); 2) the design of cooperative networking protocols, where cooperation is utilized to reach a common goal such as the detection of a fire or/and to increase the network performance in terms of optimization of given performance metrics, e.g., energy consumption, delivery time, delivery probability. Concerning the first point, my study explores the capabilities of Compressive Sensing (CS), a technique that has been proved to be very effective for the compression and recovery of correlated signals, with the objective of designing and implementing a system for the efficient acquisition of large data sets in distributed (sensor) networks. The goal of this system is to reconstruct large signals through the collection of the smallest number of samples that will keep the reconstruction quality above a minimum target level. The steps of my research activity can be summarized as follows: 1.a) assess the applicability and potential benefits of CS in networking applications; 1.b) provide a sound theoretical justification of the effectiveness of CS recovery when coupled with Principal Component Analysis (PCA) along with a characterization of the optimality of the reconstruction process as a function of the statistics of the input signal; 1.c) design an algorithm for signal reconstruction based on CS and validating the proposed method through Matlab simulations as well as real signal traces. For the second point, my work has been centered around distributed optimization methods whose objective is that of optimizing network wide (global) performance metrics. In detail, in the investigated scenario nodes collaborate to minimize the sum of local objective functions, which in general depend on global variables such as the network protocol parameters or actions taken by all the nodes in the network. In the case where the local objective functions are convex, it is possible to adopt a framework that relies on local subgradient methods and consensus algorithms to average the information from each node, while granting convergence towards global optimal solutions. However, existing convergence results for this framework can only be applied in the case of synchronous operations of the nodes and mobility models without memory. My research addresses and solves these issues, and its fundamental steps were: 2.a) the extension of the convergence results to the optimal solution for a more general class of mobility models; 2.b) the application of distributed sub-gradient methods under asynchronous operations; 2.c) the presentation of a possible networking scenario to validate the analysis, showing the effectiveness of the considered distributed optimization technique. The outcomes of my research are useful tools for the optimization of practical network protocols and provide recommendations for the design of the integrated communication and sensing system that we have envisioned above.Durante la mia attività di ricerca mi sono concentrato sullo studio di problematiche relative alle reti wireless eterogenee, ispirandomi in particolare ad uno scenario di monitoraggio urbano realizzato per mezzo di una rete di comunicazione estesa su vasta scala, parzialmente distribuita, mobile e a basso costo (possibilmente composta da telefoni cellulari o simili). Nella mia tesi di dottorato, dunque, sono stato guidato dalla visione globale di una architettura a due livelli, che permettesse l’integrazione dei sistemi cellulari esistenti con varie tipologie di reti distribuite (quali, ad esempio, le reti ad hoc o di sensori). Infatti, una infrastruttura completamente distribuita sarebbe inappropriata nel caso di una rete di grandi dimensioni e composta da numerosi dispositivi (si pensi, ad esempio, a reti su scala urbana). In questo caso, l’organizzazione stessa dell’infrastruttura di comunicazione risulterebbe assai dispendiosa in termini energetici e probabilmente impraticabile. D’altro canto, il solo sistema cellulare non possiede la flessibilità e gli strumenti per sfruttare la granularità di informazione prodotta dai dati generati in una tale rete. Nello scenario considerato, oltre alla presenza di un certo numero di cellulari mobili, e implicita anche l’esistenza di dispositivi (embedded devices) di varia natura, capaci di comunicare tra loro e con gli altri elementi della rete, e che ci si aspetta possano anche “misurare” l’ambiente circostante. Al giorno d’oggi, infatti, la tecnologia ci rende sempre più capaci di controllare la realtà quotidiana attraverso sensori di movimento, GPS, strumentazioni per il monitoraggio medico, microfoni e video-camere. Le reti di sensori (Wireless Sensor Networks, WSN), ad esempio, sono infrastrutture costituite da piccoli dispositivi (nodi) dotati di “sensori intelligenti” capaci di misurare l’ambiente circostante in termini di luminosità, temperatura, umidità , inquinamento e/o altro. Perciò, e possibile pensare che i telefoni cellulari, così come altri elementi di rete (incluse le base station, i router e gli access point su cui si basano diverse tecnologie cablate e non), possano cooperare per realizzare un obiettivo comune come l’individuazione di un incendio o il monitoraggio di un fenomeno fisico. Osservando il fatto che i telefoni cellulari sono sempre piu al centro delle comunicazioni quotidiane, è possibile prevedere l’integrazione dei sistemi cellulari standard con reti distribuite aggiuntive come le WSN. Lo scopo ultimo sarebbe quello di “connettere” qualsiasi cosa in grado di comunicare, trasmettendo e ricevendo dell’informazione, e possibilmente dotare tale rete di meccanismi autonomi di configurazione e adattamento. Si noti che le reti cellulari odierne già implementano alcune di queste caratteristiche: sulla base di informazioni contestuali, infatti, è oggigiorno possibile determinare la posizione di un utente con una certa accuratezza e fornirgli determinati servizi. Di fatto, si sta considerando una infrastruttura di rete che può essere classificata come una Delay Tolerant Network (DTN). In questo tipo di infrastruttura, reti wireless eterogenee, sparse e/o mobili, comunicano tra loro, ma tale comunicazione non puo essere assunta continua a causa della natura stessa della reti interagenti. La visione generale di cui sopra porta con s'é numerose problematiche, e durante la mia attività di ricerca mi sono concentrato in particolare sulle seguenti due: 1) la progettazione di algoritmi di ricostruzione che a partire da un sottoinsieme di dati (ossia, dalla raccolta parziale delle letture dei nodi che costituiscono l’intera rete) sono in grado di ricostruire con elevata accuratezza l’intero segnale misurato (tali algoritmi rendono il sistema scalabile, dal momento che permettono di ridurre il numero di pacchetti dati da raccogliere, fissato un certo livello di accuratezza che si vuole garantire sulla rappresentazione del segnale da monitorare); 2) la progettazione di protocolli di rete cooperativi, dove la cooperazione è utilizzata per raggiungere un obiettivo comune come l’individuazione di un incendio e/o l’aumento delle prestazioni della rete in termini di metriche quali il consumo energetico, la latenza, la probabilità di consegna. Per quanto riguarda il primo punto, il mio studio indaga le potenzialità di Compressive Sensing (CS), una tecnica molto efficace per l’acquisizione e il recupero di segnali correlati, con l’obiettivo di progettare e implementare un sistema per la raccolta efficiente di elevate quantità di dati da reti (di sensori) distribuite. Tale sistema ha l’obiettivo di ricostruire segnali di grandi dimensioni, raccogliendo il minor numero di campioni necessario al recupero del segnale di interesse entro un fissato livello minimo di qualità . I passi della mia attività di ricerca possono essere riassunti come segue: 1.a) valutazione dell’applicabilità dei benefici potenziali di CS in applicazioni di reti; 1.b) giustificazione dell’efficacia del recupero del segnale tramite CS, quando quest’ultimo è utilizzato in sinergia con la tecnica dell’analisi alle componenti principali (Principal Component Analysis, PCA) e caratterizzazione dell’ottimalità del meccanismo di ricostruzione in funzione della statistica del segnale di ingresso; 1.c) progettazione di un algoritmo per la ricostruzione di segnali basato su CS, e successiva validazione del metodo proposto per mezzo di simulazioni (Matlab) e utilizzando tracce reali. A proposito del secondo punto, invece, il mio lavoro si è focalizzato sullo studio di metodi distribuiti il cui obiettivo è quello di ottimizzare una metrica globale, nel senso delle prestazioni dell’intera rete di interesse. Nel dettaglio, nello scenario considerato vi sono più nodi che collaborano per minimizzare la somma di funzioni obiettivo locali, che in generale dipendono da variabili globali quali parametri protocollari o decisioni prese dai nodi stessi. Nel caso in cui le funzioni obiettivo locali siano convesse, è possibile utilizzare una tecnica che si basa sul metodo del subgradiente e algoritmi di consenso per mediare l’informazione proveniente da ogni nodo, e che garantisce la convergenza verso una soluzione di ottimo globale. In letteratura si trovano risultati di convergenza per tale tecnica che considerano solo il caso di operazioni sincrone tra nodi e modelli di mobilità senza memoria. La mia ricerca si è occupata di estendere tali risultati ad un contesto piu ampio. I passi fondamentali del mio lavoro sono stati: 2.a) estensione dei risultati di convergenza all’ottimo per una classe piu generale di modelli di mobilità (con memoria); 2.b) applicazione del metodo del subgradiente nel caso di operazioni asincrone tra nodi; 2.c) presentazione di un possibile scenario di applicazione di rete per validare l’analisi svolta e mostrare l’efficacia della tecnica di ottimizzazione distribuita considerata. I risultati della mia ricerca si sono rivelati strumenti utili per l’ottimizzazione pratica di protocolli di rete e permettono di formulare raccomandazioni per la progettazione del complesso sistema integrato discusso sopra