Optimization of smart city critical infrastructures: the case of communication network and transportation system

(1)

UNIVERSITÁ DIPISA

DOTTORATO DI RICERCA ININGEGNERIA DELL’INFORMAZIONE

O

PTIMIZATION OF SMART CITY CRITICAL

INFRASTRUCTURES

:

THE CASE OF COMMUNICATION

NETWORK AND TRANSPORTATION SYSTEM

DOCTORALTHESIS

Author

Elisabetta Biondi

Tutor (s)

Prof. Enzo Mingozzi, Dott. Ing. Andrea Passarella, Dott. Ing. Chiara Boldrini

Reviewer (s)

Prof. Marcelo Dias de Amorim, Dr. Daniele Puccinelli

The Coordinator of the PhD Program

Prof. Marco Luise

Pisa, November 2016 Cycle XXIX

(2)

(3)

(4)

(5)

Acknowledgements

I

would like to take the opportunity of thanking the people that have helped me. My special gratitude goes to my tutors Prof. Enzo Mingozzi, Dott. Andrea Passarella e Dott.sa Chiara Boldrini, and also to Dott. Marco Conti e Dott. Raffaele Bruno from the Institute of Informatics and Telematics (CNR) of Pisa. I owe them the most important part of my professional development as they acted as a guide and example. To have them at my side has been of immense importance and has spurred me on to learn more and more and to do my best. My appreciation of them goes beyond the work: their support helped me through difficult periods and taught me how it could contribute to making the work environment more pleasant and satisfactory.

I would like also to thank Antonino and Riccardo, who have been a fundamental and irreplaceable support, and the other boys in the laboratory, with whom I have spent years, especially Davide, Fabio, Massimiliano and Valerio.

Finally, I thank my parents, my sister and my two sets of grandparents: with these few words I am glad to be able to reciprocate in part the pride they fell towards me.

(6)

(7)

Ringraziamenti

V

ORREI cogliere questa occasione per ringraziare chi mi ha aiutato e mi è stato vicino in questo percorso. La mia più sentita gratitudine va ai miei tutors Prof. Enzo Mingozzi, Dott. Andrea Passarella e Dott.sa Chiara Boldrini, e anche a Dott. Marco Conti e Dott. Raffaele Bruno dell’Istituto di Informatica e Telematica (CNR) di Pisa. A loro devo la parte più importante della mia crescita professionale, della quale sono stati una guida e un esempio. Averli a fianco in questo percorso è stato prezioso e inestimabile, e mi ha spronato a imparare sempre di più e dare il meglio. Il mio apprezzamento verso di loro va anche oltre l’ambito professionale; la loro vicinan-za e il loro supporto mi hanno accompagnato anche nei momenti difficili e mi hanno insegnato quanto questo possa contribuire a rendere più fertile e piacevole l’ambiente di lavoro.

Vorrei ringraziare Antonino e Riccardo, che sono stati per me un sostegno fonda-mentale e insostituibile, e gli altri ragazzi del laboratorio con cui ho trascorso questi anni, in particolare Davide, Fabio, Massimiliano e Valerio.

Infine ringrazio i miei genitori, mia sorella e i tutti i miei nonni: con queste poche parole sono fiera di poter ricambiare in parte l’orgoglio che provano nei miei confronti.

(8)

(9)

Summary

U

RBAN population growth and technological advancements have stimulated

re-searchers to investigate innovative solutions that could improve the quality of life of people living in urban areas. All these research efforts strive towards a “smart city”, i.e., a city that exploits information technology to address its problems, that values its human capital, and in which citizens and stakeholders collaborate to boost economic development. A smart city can be seen as a system of systems, mean-ing that it can integrate and optimize different interdependent elements (transportation system, communication networks, energy grid, etc.). This can be achieved through the development of an ICT platform, the Smart City Operating System, that allows the monitoring and managing of the different infrastructures. A key component of the Smart City Operating System will be a set of optimization tools that could assist the manager of the smart cities infrastructures in the monitoring and management. Within this framework, the focus of my thesis is the definition of models and optimisation tools for two critical infrastructures of a smart city: the communication network and the transportation system.

The communication network of a smart city will move from the current fourth-generation (4G) systems to a new fourth-generation (5G) better equipped for addressing a huge demand for mobile data. The growth in mobile traffic is already an on-going trend but it is expected to explode with the capillary diffusion of the Internet of Things (a strategical asset for turning cities into smart cities). 5G networks aim at addressing the exponential growth in mobile traffic using a blend of different strategies, among which mobile data offloading is one of the most promising. One approach to mobile data offloading is to exploit device-to-device WiFi or Bluetooth communications between the users of the network to disseminate popular content without relying exclusively on the cellular infrastructure. Unfortunately, these device-to-device communications tend to consume a lot of battery, and this would discourage users from cooperating in the offloading process. For this reason, energy saving scheme are often implemented on the devices, to preserve their battery power and hence network lifetime. However, energy saving schemes have the net effect of reducing contact opportunities (because the network interface may be turned off when two users are in radio range) and thus

(10)

increasing message delay. With the aim of striking the right balance between energy saving and delay performances, in the first part of this thesis I discuss how to design a model that accurately describes how the measured contact process between users is modified by the duty cycle. Then, building upon the results obtained, I introduce a tool for optimizing the duty cycle in order to provide guarantees on message delay.

In the second part of this thesis, I consider smart transportation systems, with a spe-cific focus on the electric carsharing systems. Electric carsharing is considered now one of the key elements of a smart city, since it holds the promise of reducing both gas emissions and traffic congestion. Electric carsharing is typically station-based, i.e., cus-tomers are required to pick up and drop off vehicles at special locations called stations, which are also equipped with one or more charging poles. Since deploying the station infrastructure and running the service is costly for the carsharing operator, defining a set of tools for optimal deployment and operational efficiency becomes crucial to guar-antee the economic viability of such a system. First, I focus on station deployment, and introduce an optimization problem that allows minimizing the costs for the operator while at the same time maintaining a quality of service that is satisfactory to customers. Secondly, I investigate the opportunity offered by power sharing technologies (which allow multiple vehicles to share the same power), and I develop an optimal power shar-ing strategy that again takes into account both costs and customer satisfaction. Finally, since the impact of the electric carsharing system on the power distribution grid is ex-pected to be significant, I investigate the energy demands of electric carsharing under different deployment scenarios and charging technologies (including power sharing) in order to verify the effective sustainability of such a system for the power grid.

(11)

Sommario

N

EGLIultimi anni si è assistito ad una crescita demografica nelle aree urbane che,

assieme al repentino proliferarsi di nuove tecnologie ha favorito la ricerca di soluzioni innovative volte ad aumentare la qualità della vita nelle città. L’o-biettivo è quello di sviluppare una smart-city, vale a dire una città in grado di sfruttare le tecnologie che risiedono in essa per risolvere i problemi relativi ai servizi offerti, va-lorizzare il capitale umano e promuovere una collaborazione tra i cittadini e le imprese. Una smart city può essere vista come un sistema di sistemi (system of systems), che ottimizza e coordina i diversi elementi interdipendenti, quali sistemi di trasporto, reti di comunicazioni, reti energetiche etc. Per rendere possibile tutto ciò, è fondamentale lo sviluppo di un vero e proprio sistema operativo della smart city, che permetta di monito-rare e dunque gestire le varie infrastrutture. Pertanto, l’elemento chiave di tale sistema operativo risiede nello sviluppo di strumenti di ottimizzazione per supportare interventi di monitoraggio e gestione. Il tema centrale della mia tesi si colloca in questo contesto e si è focalizzato nella definizione di modelli di ottimizzazione per due infrastrutture critiche di una smart city: le reti di comunicazione ed il sistema di trasporto.

Le reti di comunicazioni delle smart cities saranno reti di quinta generazioni (5G), pensate per gestire quantità di traffico dati enormemente maggiore rispetto alle attuali reti di quarta generazione (4G). Attualmente la crescita del traffico dati diretto verso le reti mobili è in continua crescita ed è destinato ad esplodere con la diffusione capillare dell’Internet of Things (IoT), fondamentale per lo sviluppo delle smart cities. Grazie all’uso delle reti 5G sarà possibile far fronte al problema della crescita esponenziale del traffico dati da/verso dispositivi mobili. In particolare, uno degli strumenti più promet-tenti delle reti 5G è il mobile data offloading, che permette di scaricare il traffico dalla rete cellulare verso un’altra rete complementare. Il modo più comune di implementare l’offloading è l’utilizzo delle comunicazioni device-to device (D2D) tramite interfaccia WiFi e Bluetooth dei dispositivi mobili presenti in rete. Esso infatti consente di far reperire i contenuti richiesti riducendo l’occupazione della banda della rete cellulare. Purtroppo in questo tipo di comunicazioni si deve far fronte al problema del consumo energetico dei dispositivi e, a tale scopo, su di essi sono spesso implementati dei mec-canismi di risparmio energetico che consentono di preservare la batteria. Ovviamente,

(12)

visto che in genere tali schemi agiscono sui tempi di accensione e spegnimento delle interfacce D2D, ne consegue la diminuzione delle opportunità di contatto e quindi un incremento nel ritardo di ricezione di un messaggio. La prima parte della mia tesi è stata volta a trovare il giusto bilanciamento tra il delay dei messaggi ed il risparmio energetico dei dispositivi. In particolare, in primo luogo ho costruito dei modelli che valutano accuratamente come i contatti tra i vari utenti variano al variare del duty cycle. In seguito, partendo da tale modello, ho fornito uno strumento capace di ottimizzare il duty cycle riuscendo a garantire un ritardo di arrivo dei messaggi fissato a priori.

La seconda parte della tesi si è focalizzata sui trasporti di tipo smart, in particolare sul carsharing elettrico. Attualmente il carsharing con vetture elettriche è considerato uno dei più promettenti tipi di trasporto per smart cities, in quanto ha il duplice effetto di diminuire fenomeni di congestione del traffico stradale e di contribuire alla riduzio-ne dell’emissioriduzio-ne dei gas di scarico. L’implementazioriduzio-ne tipica di tale sistema è quella basata sulle stazioni (station-based), ossia in cui i veicoli si trovano parcheggiati in sta-zioni appositamente dislocate all’interno della città. Per accedere al servizio, gli utenti sono obbligati a recarsi alle stazioni per poter prendere un veicolo oppure lasciarlo alla fine dell’utilizzo. Il posizionamento e la manutenzione dell’infrastruttura delle stazio-ni rappresentano un notevole costo per l’operatore e pertanto è fondamentale costruire strumenti di ottimizzazione per la dislocazione delle stazioni e la fruizione del servizio che rendano il sistema economicamente sostenibile per l’operatore. Per questo, prima di tutto la mia attività di ricerca in questo ambito si è concentrata sul problema del po-sizionamento delle stazioni. A tal fine ho formulato un problema di ottimizzazione con l’obiettivo di minimizzare i costi dell’operatore garantendo allo stesso tempo una qua-lità del servizio soddisfacente per gli utilizzatori. Successivamente, ho studiato alcune possibilità fornite delle strategie di power sharing, che consentono ai veicoli di condivi-dere la stessa potenza di carica alle stazioni. Sulla base di ciò ho definito un problema di ottimizzazione sulle operazioni di ricarica tenendo ancora una volta in considerazio-ne sia i costi dell’operatore che il grado di soddisfazioconsiderazio-ne dell’utente. Inficonsiderazio-ne, partendo dall’osservazione che sistema di carsharing elettrico impatta significativamente sulla distribuzione delle rete elettrica, ho analizzato l’effettiva sostenibilità di tale sistema da parte dei fornitori di energia esaminando richieste energetiche di varie tecnologie in diversi scenari di riferimento.

(13)

Summary of PhD Achievements

Research Activity

My research activity has been aimed at defining a set of optimisation tools for two crit-ical infrastructures of a smart city: the network infrastructure, with a focus on oppor-tunistic networks, and the transport infrastructure, with a focus on electric carsharing. My key contributions are summarised below.

• Assuming that a power saving scheme is implemented in the opportunistic net-work, I have derived and validated two models for characterising the measured contact process (i.e., the contact process after duty cycling has been factored in) between pairs of nodes. These models are very general: they have closed-form solutions for exponential and Pareto contact processes (two popular assumptions in the literature), and they can be solved numerically for general distributions of contact and intercontact times. This activity is discussed in Chapter 2.

• Exploiting one of the above models for the contact process, I have studied how to optimise the duty cycle in order to guarantee, with probability p, that the delay of messages in the opportunistic network remains below a threshold z, assuming that intercontact times are exponentially distributed. This model allows to strike the right balance between energy saving and quality of service provided to the user. This activity is presented in Chapter 3.

• I have addressed the problem of how to optimally deploy the stations of a station-based car sharing system. In the proposed model, the optimal capacity of stations is obtained describing the station as an M/M/1/K queue, while the optimal cov-erage is achieved through a set covering problem. A greedy approximation algo-rithm is also discussed. The extensive validation demonstrates that the proposed solution significantly reduces the costs for station deployment, while at the same time not impacting the quality of service provided to the users, when compared against three benchmark approaches. This activity is illustrated in Chapter 4. • I have proposed an efficient optimized charging methodology for electric

(14)

into account customer satisfaction. I have formulated the recharging problem as a two-step optimization problem, considering a realistic energy pricing scheme, and I have evaluated this solution using real traces of parking times in a French station-based car sharing system. The validation shows that significant cost sav-ings can be achieved without impacting customer satisfaction and also reducing the strain on the grid with respect to a baseline approach. This activity is discussed in Chapter 5.

• I have analysed the energy demands of the car sharing system under different de-ployment scenarios and charging technologies, including power sharing. Finally, to test how well our model can be applied to the real world I have leveraged on a data-driven evaluation methodology based upon the travel demands of an exist-ing car sharexist-ing operator. The most important results of this study is that power sharing technologies can be used without negatively affecting the state-of-charge of departing vehicles and ensuring a significant reduction in infrastructure invest-ments. This activity is presented in Chapter 6.

The activities discussed in Chapters 2-3 have been carried out in the framework of the EU FP7 project MOTO (http://www.fp7-moto.eu/). These activities have produced one paper currently under submission to an international journal, two articles accepted at international conferences (one has received the Best Short Paper Award at the 17th ACM International MSWiM 2014 Conference), and three technical re-ports. For the two conference papers, I was also the presenter at the conference. The activities discussed in Chapters 4-6 are part of the EU H2020 project ESPRIT (http://www.esprit-transport-system.eu/), currently ongoing. These activities have generated three articles accepted at international conferences (one has received the Best Student’s Paper Award at the IEEE 2nd International Forum on Re-search and Technologies for Society and Industry, RTSI) and one technical report. For two of the conference papers, I was also the presenter at the conference.

Furthermore, during my Ph.D. studies I served as Publicity Chair for the following international workshops:

• ACM CHANTS 2016 (11th Workshop on Challenged Networks co-located with ACM MobiCom 2016), October 2016, New York, USA.

• IEEE AOC 2015 (9th IEE WoWMoM Workshop on Autonomic and Opportunistic Communications), June 2015, Boston, Massachusetts, USA.

• ACM CHANTS 2014 (9th Workshop on Challenged Networks co-located with ACM Mobicom 2014), September 2014, Maui, Hawaii, USA.

Publications

International Journals

[J1] Biondi, E., Boldrini, C., Passarella, A. & Conti, M. (2016, September). What you lose when you snooze: intercontact times and power-saving mode in opportunistic networks. Under submission to ACM Transactions on Modeling and Performance Evaluation of Computing Systems (TOMPECS).

(15)

International Conferences/Workshops with Peer Review

[C1] Biondi, E., Boldrini, C., & Bruno, R. (2016, Nevember). Optimal Deployment of Stations for a Car Sharing System with Stochastic Demands: a Queueing The-oretical Perspective. In Proceedings of IEEE Intelligent Transportation Systems Conference. (pp. 1-7).

[C2] Biondi, E., Boldrini, C., & Bruno, R. (2016, September). The Impact of Regulated Electric Fleets on the Power Grid: the Car Sharing Case. In Proceedings of IEEE 2nd International Forum on Research and Technologies for Society and Industry (RTSI 2016). (pp. 1-6). Winner of the Best Student’s Paper Award

[C3] Biondi, E., Boldrini, C., & Bruno, R. (2016, April). Optimal Charging of Electric Vehicle Fleets for a Car Sharing System with Power Sharing. In Proceedings of IEEE Energycon 2016. (pp. 1-6).

[C4] Biondi, E., Boldrini, C., Passarella, A., & Conti, M. (2014, September). Duty cycling in opportunistic networks: the effect on intercontact times. In Proceedings of the 17th ACM international conference on Modeling, analysis and simulation of wireless and mobile systems. (pp. 197-201). ACM. Winner of the Best Short Paper Award

[C5] Biondi, E., Boldrini, C., Passarella, A., & Conti, M. (2014, May). Optimal duty cycling in mobile opportunistic networks with end-to-end delay guarantees. In European Wireless 2014; 20th European Wireless Conference; Proceedings of (pp. 1-6). VDE.

Others

[O1] Biondi, E., Boldrini, C., & Bruno, R. (2016, February). Optimal Charging of Electric Vehicle Fleets for a Car Sharing System with Power Sharing. Technical Report IIT TR-13-2015.

[O2] Biondi, E., Boldrini, C., Passarella, A. & Conti, M. (2015, October). Optimal energy vs. delay trade off in opportunistic networks. Technical Report IIT TR-13-2015.

[O3] Biondi, E., Boldrini, C., Passarella, A. & Conti, M. (2015, September). What you lose when you snooze: intercontact times and power-saving mode in opportunistic networks. Technical Report IIT TR-12-2015.

[O4] Biondi, E., Boldrini, C., Passarella, A. & Conti, M. (2014, October). Optimal duty cycling in mobile opportunistic networks with end-to-end delay guarantees. Technical Report IIT TR-13-2014.

[O5] Biondi, E., Boldrini, C., Passarella, A. & Conti, M. (2013, December). Duty cycling in opportunistic networks: intercontact times and energy-delay tradeoff. Technical Report IIT TR-22/2013.

(16)

(17)

Part I

(22)

(23)

CHAPTER

1

Introduction

Imagine a city with no traffic jams, because sensors capture real-time data on the roads and guide drivers to optimal routes, where other sensors can quickly alert the police to crime, where people can go jogging without breathing smog or can take a relaxing walk without the stressful noises of cars, buses, etc. Nowadays, this is only a dream, but this is what a smart city promises to deliver. The concept of a smart city has at-tracted a lot of attention in recent years, with its envisioning a city built around the citizens and more liveable than today’s cities. This vision is particularly appealing be-cause of the many shortcomings of modern cities: problems like traffic jams, delays in public transport, pollution, criminality, crowding, noise, etc., are familiar to many of us. All these problems can severely impact not only the quality of life of people but also their health: an increase in many mental diseases, like stress and anxiety disorders, has been measured in people living in urban areas [75]. Things are even worse in more densely populated areas, where the number of citizens puts services under strain. Un-fortunately, the population in cities is only expected to grow more and more. Today, for the first time in history, there are more people living in cities than in rural areas [39], and by 2050, the world will be one-third rural (34 per cent) and two-thirds urban (66 per cent), roughly the reverse of the global rural-urban population distribution of the mid-twentieth century (Figure 1.1).

The research on smart cities aims to bridge the gap between the dream city and our real-life modern cities. At its core, a smart city is a new, intelligent city that en-hances the quality of life of its inhabitants using technology to improve the efficiency of services. In particular, information and communication technology (ICT) plays a fundamental role, as it represents the key instrument for monitoring, understanding, and planning a city, possibly in real time. As Townsend puts it [89], a “smart city is a digital upgrade to our built legacy”. There are several driving forces behind a smart

(24)

Figure 1.1: Urban and rural population of the world, 1950–2050 [3].

city, and the literature does not always address them consistently. As suggested in [67], we can identify three main elements that characterize a smart city:

• Technological element A smart city is one using “smart” technologies, seen as the key enablers for many services like city administration, education, healthcare, public safety, real estate, transportation, and utilities. Technology includes smart grids, innovative transport systems and traffic regulation systems.

• Human resource element A smart city is one with smart people, thus education is seen as the key enabler for urban growth. Human capital and human resources are the driving forces of city development.

• Governance element A smart city is one of smart collaboration, where interac-tion between citizens and stakeholders can create “innovainterac-tion hubs” for boosting economic development.

In other terms, the infrastructure, the human element, and the governance are the three pillars of a smart city, as is well illustrated in Figure 1.2 (provided by IBM Intelligent Operations Centre). The definition that best captures the sense of interaction among these three elements is provided by Caragliu et al. in [28]:

We believe a city to be smart when investments in human and social capital and traditional (transport) and modern (ICT) communication infrastructure fuel sustainable economic growth and a high quality of life, with a wise management of natural resources, through participatory governance.

Each of these three pillars is composed of many subsystems. However, injecting intelligence into each city subsystem, one by one - transportation, energy, education,

(25)

Figure 1.2: IBM Intelligent Operations Centre’s view of Smart City (http://www.ibm.com/ smarterplanet/us/en/smarter_cities/overview/).

health care, buildings, physical infrastructure, food, water, public safety, etc. - is not enough to make a city become a smarter city. Using an appropriate metaphor found in [71], a smart city is like a large organic system, where none of its parts operates in isolation. For this reason, sharing information and knowledge, connections, and collaborations are the key features which allow us to monitor and operate decisions to achieve a new level of effectiveness and efficiency. This idea leads to the concept of system of systems[72], that denotes the capability of integrating several concurrent and distributed systems into a large-scale complex system that offers more functionality and performance than simply the sum of them. A smart city has to be a system of systems in the sense that it integrates and optimizes a set of interdependent subsystems.

Figure 1.3: The horizontal ICT platform Smart City Operating System

In order to achieve the above goal, a concept recently investigated in the literature is that of a Smart City Operating System (see Figure 1.3), which is able to correlate

(26)

the different subsystems (transportation system, communication networks, energy grid, education system, physical infrastructure, water system, public safety system, etc.), provide global information to the city government for taking decisions, and then actu-alizing them through direct action on the various subsystems. A conventional operating system manages the physical resources of a computer in a uniform way mediating their use by many services and applications. In a similar way, a Smart City Operating System would collect data from many physical infrastructures of a smart city, understand their status, make these data available to any type of smart city services and applications, and mediate access to them. Therefore, such a platform will allow us to simultane-ously organize all the elements of a smart city in a horizontal way, enabling the share the knowledge and access to all of them in real time. This will represent a significant advantage with respect to vertically integrated solutions, where infrastructures are mon-itored and managed only for the specific (set of) application(s) they were installed to support. For example, knowing the cellular traffic flowing through the LTE infrastruc-ture and having access to citizens’ mobility, in case of overload, some mechanisms of traffic offloading of the cellular network can be activated, that can take advantage of, and thus can be optimized for, citizens’ mobility. Similarly, monitoring the mobility of electric vehicles and correlating it with the load profile of the power grid can enable optimized recharging strategies for a better use of energy power.

From the above discussion, it follows that an essential element of a Smart City Op-erating System will be a set of optimization tools that could assist the manager of the infrastructure in dynamically configuring it based on the conditions of the infrastruc-ture itself, and how it is used. It is exactly on this crucial building block of a smart city that my research activity has focused. Specifically, the aim of my research has been the design of optimization tools for assisting the management of two critical in-frastructures, the cellular and the transportation network. For these inin-frastructures, I have dealt with energy-efficient and operational-efficient optimisations of physical re-sources. In Sections 1.1 and 1.2 below, I will introduce the research problems I faced and my contributions on these two topics.

1.1

Communication Networks in Smart Cities

In modern cities there is already a vast underworld of computers and software, some-times clearly visible, like the smartphones in our pockets, somesome-times lurking behind a traffic light or a surveillance camera. All these devices are already generating exabytes of mobile traffic [57], and this trend is only expected to grow with the full blooming of the Internet of Things (IoT) and M2M communications, which will be an integral part of any smart city and a key instrument for monitoring and understanding the city in real time. With all these devices sprouting up everywhere and communicating with each other, a huge demand for mobile traffic will be generated, with a foreseen 11-fold increase only in the next couple of years [57]. Current 4G networks are not suited to address such data demand, but a collapse of communication networks would mean shutting down the central nervous system of the smart city. Hence, smart cities need a new kind of communication network, typically referred to as 5G network.

Research efforts on 5G networks aim at addressing the exponential growth in mo-bile traffic using a blend of different strategies, from network densification [11] to the

(27)

(a) WiFi offloading (b) Opportunistic offloading

Figure 1.4: The two main types of mobile data offloading: (a) AP-based offloading; (b) Opportunistic offloading

exploitation of heterogeneous wireless technologies. Mobile data offloading is one of the most promising techniques in the latter category, and its has recently attracted a lot of interest from the research community. It consists in transferring data from a con-gested cellular network to a complementary wireless network [80]. There are two main approaches in mobile data offloading (see Figure 1.4). The first one adopts WiFi Ac-cess Points (AP), which serve the traffic in their own covering range diverting it from the cellular network. The advantage is that often AP’s connection speed and through-put are better than those of the cellular network. However, with this approach, only devices in the AP coverage can be served, and thus node mobility is constrained. Fur-thermore, this solution cannot be applied everywhere, but only in areas where an AP infrastructure is already deployed. The other possibility is called mobile opportunistic traffic offloading, and here the complementary network used to offload the traffic is not infrastructured, but uses direct communications between nodes (device-to-device com-munication or D2D). With this paradigm, popular contents are sent through the cellular network only to a few users, who then spread these contents to the other interested people nearby using opportunistic networking.

The concept of opportunistic networks stems from the idea of exploiting the wide-spread availability of smart, handheld devices for extending the possibility of commu-nication between users. In this sense, mobility becomes an opportunity for spread-ing contents around the network. In particular, an opportunistic network exploits the movements of network nodes, and delivers messages according to the store-carry-and-forward paradigm (see Figure 1.5): nodes, that can be smartphones or sensors, carry messages while they move and forward them to other nodes in radio contact, until mes-sages reach their final destination. For this reason, communication between nodes is not constrained to a limited zone, since the source and destination do not need to be in direct radio contact. By their very nature, opportunistic networks are suitable for delay-tolerant communications, wherein the communicating end parties do not need to receive messages by a strict deadline. Luckily, this is typically the case for several of the most popular applications such as web browsing, social networking (Twitter, Face-book), and news aggregator applications. As messages follow multi-hop paths across the nodes of the network, their delay is the result of the delay accumulated at each hop along the forwarding path. Therefore, the time (intercontact time) between consecutive encounters of a pair of nodes is the main elementary component of the overall delay.

(28)

For this reason, in networks where intercontact times are large, the delay experienced by messages will be large, and vice versa.

Figure 1.5: Store-carry-and-forward paradigm in opportunistic networks: messages arrive at their destination between several pairwise exchanges

Opportunistic networks are based on device-to-device communications, but D2D is supported by technologies that were not optimized for that purpose. Because of this, D2D communications suffer from many shortcomings on off-the-shelf devices, with their energy requirements being particularly critical. This is true both for ad hoc WiFi and Bluetooth [46]. This can greatly affect the applicability of opportunistic protocols, because clearly no user will participate in an opportunistic network if they have to pay the price of consuming their battery devices in a few hours. Due to the energy issues of the available ad hoc communication technologies, several schemes for energy saving have been implemented. The most practical and popular ones consist in reducing the scanning frequency of Bluetooth or turning off the WiFi interface. Such strategies are typically referred to as duty cycling, since they make nodes alternate between a low-power state (in which they cannot communicate) and a high-low-power state. With duty cycling policies, devices can exchange messages only when they are in one-hop radio range and both in active mode. As a natural consequence forwarding opportunities are reduced, because all contact opportunities which happen when one of the two de-vices is in power saving mode are missed. The net effect can be observed looking at the measured intercontact time, that is defined as the time between two consecutively detected contact events (after duty cycle): with respect to the “original” intercontact times (i.e., those without any duty cycling policy) they are obviously longer. To the extent that end-to-end delay of messages depends on measured intercontact times, it is of paramount importance to understand how they are affected by power saving tech-niques, which may effectively reduce the number of usable contacts. In general, also the contact time, defined as the duration of a contact, is modified by the duty cycle, because a contact is interrupted whenever one of the two nodes becomes inactive after entering the low-power state. The contact duration observed after the duty cycle is fac-tored in is called measured contact time, and, in general, it provides information about transmission capacity, as messages are exchanged during contact periods: the shorter the contact duration, the fewer the data that can be transmitted.

(29)

has been largely ignored in the related literature. My contribution in this area1 _goes in the direction of filling this gap. First, we study how the measured contact process is modified by the duty cycle. To this aim, we derive the distribution of the measured contact and intercontact times. The mathematical expressions that we find are valid for general distributions of contact and intercontact times, and can be solved numerically. In addition, for two of the most popular distributions for contact and intercontact times considered in the literature (exponential and Pareto), we are also able to obtain the results in a closed form. This closed form is then used to extensively validate the proposed model starting from real traces of contact and intercontact times available in the literature. The model can be used for both deterministic and stochastic duty cycling policies. Using this model, we derive several interesting results about the properties of measured contact and intercontact times with duty cycling: their distribution, how their coefficient of variation changes depending on the duty cycle value, how the duty cycling affects the capacity and delay of an opportunistic network. The applicability of these results is broad, ranging from performance models for opportunistic networks that factor in the duty cycling effect, to the optimisation of the duty cycle to meet a certain target performance. This model for the measured contact process, which has been previously described and validated in [17, 19], will be presented in Chapter 2.

Building upon the results on the measured contact process, my other contribution in this area aims at optimising the value of the duty cycle in order to provide probabilis-tic guarantees on the delay experienced by messages. Denoting with ∆ the fraction of time nodes spend in the active state of the duty cycle, the probability distribution rep-resenting the delay of messages exchanged between a tagged node pair can be seen as a function of ∆. Using this distribution, we can derive what is the probability that the delay is smaller than a target delay threshold z. This probability will be a function of ∆ as well. Thus, denoting with p the probabilistic guarantee that we want to achieve, op-timising the duty cycle means finding the smallest ∆ such that message delay remains under the threshold z with probability p. We have obtained closed-form approximate solutions. For the sake of example, a typical result is illustrated in Figure 1.6, where we can see how the optimal duty cycle varies with the threshold z of the delay, for two fixed target probability p = 0.4 and p = 0.8. The model allows us to tune the duty cycle taking into consideration the maximum delay we want to achieve. For example, considering the probability p = 0.8, if we want a maximum delay z = 250s, we have to set the duty cycle equal to 1, which means that device interfaces are always active and thus any energy saving mechanism is not activated. Instead, if we can be more flexible in terms of the delay, we can choose a threshold level z = 380s that can be obtained with a duty cycle equal to 0.8, and that allows the saving of 20% of battery lifetime.This model for finding the optimal duty cycle value of an opportunistic networks is presented in Chapter 3. It had been previously described and validated in [18].

1.2

Transportation System in Smart Cities

While ICT systems and communication networks are a recent addition to the urban landscape, the transportation system has always been one of its essential elements. Personal mobility has been acknowledged as a basic human need and has always been 1_{All the work presented in this Section has been carried out in the framework of the EU FP7 MOTO project (http://www.} fp7-moto.eu/).

(30)

Figure 1.6: Optimal duty cycle for two fixed target probability p = 0.4 and p = 0.8 varying the target delay. This is a case obtained with exponential delay

a crucial element of human history. Personal mobility has reached its peak flexibility with the advent of private cars, which have allowed greater access to jobs, goods, and services, giving us the freedom to go where we want, when we want, and carrying the things that we need. The price to pay for this diffuse, personalized flexibility is a common experience of everyone: traffic, pollution, accidents, acres of land dedicated to roads and parking spaces. According to Eurostat statistics, transport is responsible for around a quarter of all greenhouse gas emissions in Europe2_{, and demographic} projections and economic structures make it likely that the demand for transport – and thus its volume – will continue to grow in the coming decades 3_{. To reduce CO}

2 emissions from the transportation sector, policy makers are pushing for more efficient vehicles, alternative fuels [7], as well as alternative solutions to car ownership.

Vehicle improvement has been directed at building lighter and smaller vehicles, in-creasing powertrain efficiency, and, above all, introducing alternative technologies such as hybrid or electric vehicles. Electric vehicles (EVs), in particular, are now considered a strategic asset in the transition to a low-carbon and more sustainable transport sys-tem [97]. However, private electric cars maybe be greener than gasoline cars, but still share many of the same inefficiencies. For example [9, 43], a private vehicle, regardless of its propulsion, is used on average only 5% of its available time (72 minutes per 24 hrs) and with a typical occupancy rate of 1.3 passengers representing 20% of the total capacity. When not idly parked, private vehicles, again regardless of their propulsion, increase city congestion. Several studies have been directed at envisaging a better uti-lization of the road infrastructure (for example [63]), but even if a better utiuti-lization of the resources would be beneficial, road capacity would not be able to satisfy all the increasing demand.

2_{Greenhouse gas emission statistics from Eurostat Statistic Explained http://ec.europa.eu/eurostat/} statistics-explained/index.php/Greenhouse_gas_emission_statistics

3_{Climate change - driving forces from Eurostat Statistic Explained} http://ec.europa.eu/eurostat/statistics-explained/index.php/Climate_change_-_driving_forces

(31)

Reduced congestion and improved vehicle utilization can only be achieve by de-parting from the traditional car ownership model. Public transport has always been promoted as the best alternative to private cars. However, public transport can only achieve the convenience and reliability that customers require only in densely popu-lated areas. And even in these areas, public transport may not be flexible enough to cover all customer needs (e.g., journeys in the evening or late at night, journey during which customers need to carry heavy items with them, etc.). At the moment, the gap between private and public transport seems to be wide and most citizens do not consider public transport to be a real alternative to car ownership [87].

Carsharing was born in Zürich, Switzerland, in 1948 [54], but it is not until the 2000s that it has seen its full realization and explosion, mainly due to the widespread availability of Internet connectivity (first at home, then on smartphones) and the more flexible carsharing options that have started to be offered around that time. Carsharing perfectly lies at the intersection between smart cities and the new sharing economy: car access is decoupled from car ownership [25], people do not own a car, they simply rent it from the carsharing operator when they need it, typically for short-range trips. The carsharing operator takes the burden of caring for the car off the customers: it pays for vehicle maintenance, repair, insurance coverage, parking and charging costs. In additional, in several cities shared cars have access to reserved parking spaces, which is a huge bonus in densely populated area (e.g., Paris), where finding parking space can be a nightmare. In cities where carsharing services are running, positive effects have already been measured [60, 66, 82]: carsharing members use cars less, increase the utilization of public transport or bicycles, and in some cases they even shed their private car (or refrain from buying a second one for their family). Carsharing can also act as last-kilometer solution for connecting people with public transport hubs, hence becoming a feeder to traditional public transit [84].

The research efforts towards greener vehicles and those towards smarter transporta-tion systems merge into electric carsharing systems, which hold the promise of be-ing an integral part of the future smart transportation systems [85]. Today, the most widespread carsharing form is free-floating carsharing, which allows its members to pick up and drop off cars at any available parking space within the operating area. Examples are Car2go, DriveNow, and Enjoy. However, free-floating is not the best so-lution for electric carsharing, since EVs need an efficient and well-deployed recharging infrastructure that is currently a mirage for most cities. For example, in March 2016 the free-floating operator Car2go decided to replace its electric fleet in San Diego, US, with gas-powered cars due to the lack of charging stations in the city4. The other type of car-sharing is station-based carcar-sharing, where several stations are displaced across the city and customers have to go there to pick up and drop off shared cars. With station-based car sharing, some flexibility is traded off for operational efficiency: cars can be easily recharged [44], and overall better guarantees on car availability and parking spaces can be offered.

My research activity in this area has focused on the optimization of the deployment and operations of an electric station-based car sharing system. Despite its huge poten-tial, in fact, several problems relating to its operations and infrastructure deployment

4 http://www.sandiegouniontribune.com/news/2016/mar/16/car-share-car2go-fleet-gas-electric/

(32)

have not yet been fully considered, and represent open issues that have to be addressed. The key point to bear in mind when dealing with planning and managing such a sys-tem is the huge operator investment for infrastructure deployment. The viability for a station-based carsharing system, in fact, is possible only if all strategical operations (as for example planning and charging) take into account the operator’s costs and try to minimise them as much as possible. The correct balance is given by the quality of service provided to the customers: investments can be reduced only until they do not affect the perceived quality of the carsharing service. Thus, my goal is to strike the right balance between operator savings and consumer satisfaction (in terms of quality of service).

When deploying a new carsharing system, the first and costlier problem is station deployment. On the one hand, the carsharing operator would like to have as fewer sta-tions as possible. On the other hand, the carsharing members are not willing walk more than a few hundreds of meters for picking up their cars, and expect to find an available car whenever they need one. My first contribution to this area of research has been the definition of a minimum-cost optimization problem that can provide probabilistic guarantees on finding both an available car and an available parking space. To do this, I built a model using insights from queuing theory, thanks to which I was able to model the stochastic demand for cars and parking spaces at stations. Please note that taking into account the uncertainty of demand for cars and parking spaces is a key point for the planning operation. In fact, existing planning models always refer to determinis-tic demands, but, since there are strong interdependencies between travel demands and parking and car availability, this assumption does not address the problem satisfactorily. The minimum-cost optimization problem has been test with a real trace of more than 100,000 pickup and drop-off events at a free-floating carsharing service in the Nether-lands, which are used to model the input demand of the carsharing system. The most important result obtained is that the proposed model significantly reduces operator in-vestment, and at the same time the obtained deployment is able to preserve the quality of service provided to users with respect to three benchmark approaches. This model, previously defined and evaluated in [16], will be presented in Chapter 4.

Besides station placement and dimensioning, how (and when) shared vehicles are recharged is a key strategy for curbing the operator’s costs. Recent advancements in recharging technology now offer the possibility of using one charging station to recharge several EVs. This goes under the name of power sharing. In Figure 1.7, there are two main examples of power sharing. In the first one, stations are equipped with many charging ports, that can be plugged into as many EVs. The second type of power sharing is supported by a new generation of stackable vehicles that are able to share power when connected in a train, so that they can be simultaneously charged. These vehicles are currently under development within the EU H2020 project ES-PRIT (http://www.esprit-transport-system.eu/), in which framework my research activities in this area have been carried out. ESPRIT cars can increase the carsharing operators’ revenues by reducing the cost of installation (only one charg-ing supply equipment to serve multiple parkcharg-ing spaces), while supportcharg-ing, due to their small size, the growing demand for charging spots. Despite its many advantages, man-aging power sharing operations can be complex: the power available at stations has to be split among the vehicles connected at the station, whose parking durations may

(33)

(a) (b)

Figure 1.7: The two main types of power sharing: (a) a charging station with ports for distributing power to multiple EVs;(b) ESPRIT vehicles: stackable EVs that can share power when connected in train

be short and which, due to a high vehicle turnover, may need frequent recharges. To the best of my knowledge, there are no previous studies on recharging strategies that use power sharing technology. To fill this gap, I have focused on an optimized charging strategy that minimizes recharging costs when power sharing is used and also takes into account customer satisfaction. I have formulated the recharging problem as a two-step optimization problem, considering a realistic energy pricing scheme, and I have eval-uated this solution using real traces of parking times in a large-scale station-based car sharing system. We show that significant cost savings can be achieved without impact-ing customer satisfaction (i.e., vehicles have enough energy to complete their trips) and also reducing the strain on the grid with respect to a baseline approach. In Chapter 5 the model and the contribution of this part of my research will be presented. This work has been previously described and validated in [14].

My third research contribution in this area takes a different perspective on the car-sharing system. Specifically, it focuses on the impact of the presence of a regulated fleet of shared electric cars on the power distribution grid. This impact is expected to be significant and very different from that of privately-owned EVs due to: the differ-ent mobility patterns (e.g., higher vehicle utilisation, shorter parking times), and the dependence of charging opportunities on the specific layout of the carsharing station infrastructure. However, these issues are not sufficiently investigated in the research literature. To fill this gap, I have analysed the energy demands of the car sharing sys-tem under different deployment scenarios and charging technologies, including power sharing. Finally, to test how well the model can be applied to the real world, I have again leveraged on a data-driven evaluation methodology based upon the travel de-mands of a real-life car sharing operator. The key finding is that, although there are peak and off-peak periods during the day, power demands are generally low and thus easily manageable by the power grid. In Chapter 6 the main contributions of this part of my research will be discussed. This work have been previously described and validated in [13].

(34)

(35)

Part II

Communication Network in Smart

Cities: Energy Saving in Opportunistic

(36)

(37)

CHAPTER

2

How duty cycling impacts on the contact process

in opportunistic networks

2.1

Introduction

In opportunistic networks, messages arrive to their final destination through consecu-tive pairwise exchanges between users that are in radio range of each other [35]. As such, unlike MANETs, opportunistic networks do not assume a continuous end-to-end path between source and destination, and paths are built dynamically and incremen-tally by intermediate nodes when new contacts (i.e., new forwarding opportunities) arise. While originally studied as a standalone solution, opportunistic networks are now being exploited in synergy with the cellular infrastructure in mobile data offload-ing scenarios [80] (as discussed in Chapter 1), as well as in other applications, such as an enabling technology for the Internet of Things [95] or in sinergy with cloud infras-tructure when available [96].

User mobility, and especially user encounters, is the key enabler of opportunistic communications. Unfortunately, ad hoc communications tend to be very energy hun-gry [46] and no user will be willing to participate in an opportunistic network if they risk to see their battery drained in a few hours. However, there are very few contri-butions that study how power saving mechanisms impact on the contacts that can be exploited to relay messages. These power saving mechanisms range from completely turning off devices periodically or, more commonly, to tuning the frequency at which the network interface is used (e.g., reducing neighbour discovery activities). We gener-ically refer to all these strategies as duty cycling. With duty cycling, messages can be exchanged only when two nodes are in one-hop radio range and they are both in the active state of the duty cycle. So, power saving may reduce forwarding opportunities, because contacts are missed when at least one of the devices is in a low-energy state.

(38)

Since some contacts may be missed, the measured intercontact times, defined as the time interval between two consecutive detected encounters between the same pair of nodes, is, in general, larger than the original intercontacts (i.e., those defined exclu-sively by the nodes mobility process) and this may clearly affect the delay experienced by messages. The measured contacts (i.e., the length of a contact while the two nodes are in radio range and active) may also be affected, if one of the two nodes becomes inactive during a contact. Owing to the extent at which, in principle, measured contacts and intercontact times may affect the performance of opportunistic networks, we argue that it is essential to better understand how they are characterised and how they depend on the duty cycling policy in use. Unfortunately, the effects of duty cycling on the measured pairwise contact process have been largely ignored in the literature.

The goal of this work is to characterise the distribution of the measured contact and intercontact times, starting from a given distribution of original contact and intercon-tact times, and a duty cycling scheme. To this aim, the contribution of this chapter is threefold. First, in Section 2.3, assuming that contact duration is negligible, we derive a mathematical model of the measured intercontact times between nodes. For general distributions of the original intercontact times we derive mathematical expressions that can be solved numerically to obtain the first two moments of the measured intercontact times. We can thus approximate any distribution of the measured intercontact times using hyper- or hypo- exponential approximations [86]. Under the two most popular intercontact time distributions considered in the literature, exponential and Pareto, the closed forms of the first two moments admit analytic solutions, making the model even more flexible. As a second contribution, in Section 2.4 we extend the above model to include the effects of non-negligible contact duration, again under any distribution of contact and intercontact times, thus making the model as general as possible. We ex-tensively validate this model using as input the distribution of contact and intercontact times obtained from traces of real user mobility. Finally, in Section 2.5 we show that the results obtained assuming a deterministic duty cycling (as described in Section 2.2.2), actually provide a very good characterisation also when stochastic duty cycling is used. Focusing on a tagged node pair, the key findings presented in this chapter are the fol-lowing:

• The measured contact time ˜C cannot be longer than the duration of the active state of the duty cycle, hence the data transfer capacity of the opportunistic network is generally reduced, even significantly. However, if the duty cycling policy is such that nodes refrain from entering the low-power state when they detect a contact, the measured contact duration (hence the capacity) may be only minimally af-fected by the duty cycle.

• When contact duration C is negligible, if the original intercontact times S are ex-ponential with rate λ, the measured intercontact times ˜S are exponential with rate λ∆, where ∆ is the percentage of time nodes keep the wireless interface active (duty cycling parameter). Instead, if the original intercontact times S are Pareto with exponent α, the measured intercontact times ˜S do not feature a well-known distribution but they decay as a Pareto random variable with the same exponent α. This implies that all the properties (e.g., the delay convergence [24, 29]) that depend on the shape of the tail of the Pareto distribution of intercontact times are

(39)

not affected by duty cycling.

• The duty cycle can affect measured intercontact times in such a way that low-variability (i.e., with coefficient of variation smaller than one) original intercontact times can turn into highly variable measured intercontact times (and vice versa), thus potentially altering the convergence of the expected delay.

• A stochastic duty cycling can be approximated with a deterministic duty cycling for which the length of the active and inactive intervals corresponds to the average length of the same intervals in the stochastic duty cycling. This means that our results about ˜C and ˜S hold for a very large class of duty cycling policies.

To the best of our knowledge, as discussed in Section 2.6, this work represents the first comprehensive analysis of how the measured contact process is altered by power saving techniques.

2.2

Preliminaries

In this section we introduce the duty cycling process that we take as reference and we describe how the contacts between users can be modelled.

2.2.1 The duty cycling process

We use duty cycling in a general sense, meaning any power saving mechanism that hinders the possibility of a continuous scan of the devices in the neighbourhood. We assume that nodes alternate between the ON and OFF states. In the ON state, nodes are able to detect contacts with other devices. In the OFF state (which may correspond to a low-power state or simply to a state in which devices are switched off) contacts with other devices are missed. Using this generalisation, we are able to abstract from the specific wireless technology used for pairwise communications.

Duty cycling policies can be deterministic or stochastic, depending on how the length of their ON and OFF states is chosen (fixed, in the former case, varying ac-cording to some known probability distribution in the latter). In the literature also non-stationary duty cycling policies can be found, in which the length of ON and OFF states depends on some properties of the network (or a node’s neighborhood) at time t. All these approaches are discussed in Section 2.6. We base our model on the deterministic duty cycling case (which requires a coarse synchronisation between devices), then we later prove in Section 2.5 how this model captures the average behaviour of the stochas-tic case (which does not require synchronisation) as well. Finally, we also discuss how the model captures some notable cases of non-stationary duty cycling policies.

In the following, we assume that the duty cycle process and the real contact process are independent and, considering a tagged node pair, we denote with τ the length of the time interval in which both nodes are ON, and with T the period of the duty cycle. Thus, T − τ corresponds to the duration of the OFF interval and ∆ = _Tτ is the duty cycle parameter. In general, the ON interval can start anywhere within T but here, without loss of generality, we assume it starts at the beginning of interval T . In addition,

(40)

considering a generic detected contact, we count duty cycle periods from the first one where the contact is detected. Hence, ON intervals will be of type [iT, τ + iT ), with i ≥ 0 and OFF intervals of type [τ + iT, (i + 1)T ), with i ≥ 0 (Figure 2.1). In the following, ON and OFF intervals will be denoted with ION and IOF F, respectively. Hence, the set of all ON (OFF) intervals is given byS∞

n=0I ON n ( S∞ n=0I OF F n ). Focusing on a tagged node pair, we can represent how the duty cycle function evolves with time as d(t) = 1 if t mod T ∈ [0, τ )

0 otherwise . When d(t) = 1, both nodes are ON, thus their contacts, if any, are detected.

d(t))

t))

t

! " #

$

_%

% & $

&

'%

'% & $

!"#$%!$&'()*#+

Figure 2.1: ON and OFF intervals in our model.

Reference values for τ and T depend also on practical aspects. A result derived in [91] shows that, for frequencies of switching between ON and OFF states beyond 1/100s−1, energy consumption on smartphones drastically increases, making the dis-covery process not energy efficient. Thus, for the purpose of this chapter, we will consider values of T around 100s and will experiment with different values of τ when evaluating the proposed models. This is also the reason why in the chapter we do not consider duty cycling schemes switching the wireless interfaces at a much finer granu-larity, in the order of milliseconds or less.

2.2.2 The contact process

Similarly to the related literature [23,77], we assume that, from the mobility standpoint, node pairs are independent.This assumption is necessary to make analytical models tractable. Previous works in the related literature [77] have shown that the results ob-tained exploiting this assumption are accurate in predicting the behaviour of a real sys-tem (in which contacts are generally not independent). From the modelling standpoint, the contact process of each node pair (u, w) can be approximated as an alternating re-newalprocess [38]. In this case, the node pair alternates between the CONTACT state in which the two nodes are in radio range, and a state in which they are not (Figure 2.2). The time interval between the beginning and the end of the i-th contact is denoted as C_i(u,w). The time interval between the end of a contact and the beginning of the next one corresponds to the intercontact time and it is denoted as S_i(u,w). Hence, the alter-nating renewal process corresponds to the independent sequence of random variables {C_i(u,w), S_i(u,w)}, with i ≥ 1, which is an approximation of the real contact process as C_i(u,w) and S_i(u,w) can be dependent for a fixed i but must be independent for different i. Note that assuming independence of consecutive contact and intercontact times is also customary in the literature. Since in the following we focus on a tagged node pair, for the sake of clarity we hereafter drop superscript (u, w) from our notation. Please note,

(41)

however, that the contact process we consider is heterogeneous, i.e., the distribution of Ciand Sican be different for different pairs of nodes. Exploiting this notation, we have that the time Xi at which the i-th contact begins is

Pi

j=1Sj+ Pi−1

j=0Cj, ∀i ≥ 1, while the time Yiat which it ends is given byPi_j=1Sj+Pi_j=0Cj, ∀i ≥ 1.

t

(₎ *₊ (₊ *_, (_, *_- (_- ,"#$%!$&'()*#+

,"#$%!$&(#-+

.₊ /₊ ._, /_, ._- /

-Figure 2.2: The alternate-renewal contact process

For the reader’s convenience we summarise the notation used throughout this chapter in Table 2.1.

2.3

Measured intercontact times when contact duration is negligible

We now discuss how the measured contact process depends on the contact process described in Section 2.2.2. We start analysing the case where the contact durations are negligible with respect to the duty cycling period. In real traces, this is often a reasonable approximation, given that a significant part of observed distributions is con-centrated on contact durations of a few seconds. Under this assumption, the alternating renewal process of Figure 2.2 becomes a simple renewal process [38] where Si are the renewal intervals. We later relax this assumption in Section 2.4.

Recall that the effect of duty cycling on contacts is that some contacts between nodes may be lost. So, we first study in Section 2.3.1 what are the characteristics of the process of measured contacts and how it can be modelled. The main outcome of this section is that the measured intercontact time can be obtained as the sum of N (with N stochastic) real intercontact times, assuming that the PDF of S has certain properties that can simplify our derivations. Building upon these results, in Section 2.3.2 we com-pute the PMF of N and then in Section 2.3.3 we finally derive the measured intercontact times ˜Si.

2.3.1 Problem setting

Let us denote with ˜Sj the time between the (j − 1)-th and the j-th detected contact (corresponding to the j-th measured intercontact time) and assume that at time ˜Xj−1 a contact has been detected, as shown in Figure 2.3. For convenience of notation, in Figure 2.3 and in the following, the sequence number of the duty cycling interval in which the i-th contact takes place is denoted with ni, while the sequence number of the ON interval in which the j-th detected contact takes places is denoted with ˜nj.

Then, the measured intercontact time ˜Sj is the time from ˜Xj−1 until the next de-tected contact at ˜Xj, which can be obtained by adding up the intercontact times Si

(42)

Table 2.1: Notation Symbol Definition

τ length of the ON interval T period of duty cycle

∆ τ

T, duty cycle parameter

ION

n n-th ON interval [nT, nT + τ ]

IOF F

n n-th OF F interval [nT + τ, (n + 1)T ]

Xi time when the i-th contact begins

Yi time when the i-th contact ends

Ci i-th contact time, i.e. time interval between the beginning and the end of the i-th

contact

Si i-th intercontact time, i.e. time interval between the end of the (i − 1)-th contact and

the beginning of the next one ˜

Xi time when the i-th detected contact begins

˜

Yi time when the i-th detected contact ends

˜

Ci i-th measured contact time, i.e. time interval between the beginning and the end of

the i-th detected contact ˜

Si i-th measured intercontact time, i.e. time interval between the end of the (i − 1)-th

detected contact and the beginning of the next one ˜

Nj number of contact events between the (j − 1)-th and the j-th detected contact

ZON _{displacement of a detected contact within an ON interval}

ZOF F _{displacement of a detected contact within an OFF interval}

λ rate of the intercontact time distribution, when it behaves as an exponential µ rate of the contact time distribution, when it behaves as an exponential

(α, b) rate and scale respectively of the intercontact time distribution, when it behaves as a Pareto

pON

s , pONe probability of a contact beginning or ending in an ON interval

pOF F

s , pOF Fe probability of a contact beginning or ending in an OFF interval

H number of ON intervals spanned by a measured contact time

Chit _{duration of a contact assuming that it is detected, i.e. when it overlaps an ON interval}

Cshort _{duration of a contact assuming that it is fully contained in an ON interval}

Cres _{duration of a contact assuming that it starts in an OFF and ends in the following ON}

interval

Cmiss duration of a contact assuming that it does not overlap with any ON interval R duration of the intersection between a contact and the OFF interval

0123

233 t

45₆₇₊% 4567+6 +% & $

*

₊

*

,

*

-

*

8

*9

₆

.:

₆₇₊

.:

₆

Optimization of smart city critical infrastructures: the case of communication network and transportation system

O

PTIMIZATION OF SMART CITY CRITICAL

INFRASTRUCTURES

:

THE CASE OF COMMUNICATION

NETWORK AND TRANSPORTATION SYSTEM

Acknowledgements

I

Ringraziamenti

V

Summary

U

Sommario

N

Summary of PhD Achievements

Contents

Part I

CHAPTER

1

Introduction

1.1

1.2

Part II

Communication Network in Smart

Cities: Energy Saving in Opportunistic

CHAPTER

2

How duty cycling impacts on the contact process

in opportunistic networks

2.1

2.2

d(t))

t))

t

$

%

% & $

&

'%

'%

'%

'% & $

2.3

0123

233

t

*

*

*

*

*9

.:

.:

_%