Performance evaluation of routing protocols for MANETs with known connectivity patterns using evolving graphs

The assessment of routing protocols for mobile wireless networks is a difficult task, because of the networks` dynamic behavior and the absence of benchmarks. However, some of these networks, such as intermittent wireless sensors networks, periodic or cyclic networks, and some delay tolerant networks (DTNs), have more predictable dynamics, as the temporal variations in the network topology can be considered as deterministic, which may make them easier to study. Recently, a graph theoretic model-the evolving graphs-was proposed to help capture the dynamic behavior of such networks, in view of the construction of least cost routing and other algorithms. The algorithms and insights obtained through this model are theoretically very efficient and intriguing. However, there is no study about the use of such theoretical results into practical situations. Therefore, the objective of our work is to analyze the applicability of the evolving graph theory in the construction of efficient routing protocols in realistic scenarios. In this paper, we use the NS2 network simulator to first implement an evolving graph based routing protocol, and then to use it as a benchmark when comparing the four major ad hoc routing protocols (AODV, DSR, OLSR and DSDV). Interestingly, our experiments show that evolving graphs have the potential to be an effective and powerful tool in the development and analysis of algorithms for dynamic networks, with predictable dynamics at least. In order to make this model widely applicable, however, some practical issues still have to be addressed and incorporated into the model, like adaptive algorithms. We also discuss such issues in this paper, as a result of our experience.

An improved stochastic modeling of opportunistic routing in vehicular CPS

Vehicular Cyber-Physical System (VCPS) provides CPS services via exploring the sensing, computing and communication capabilities on vehicles. VCPS is deeply influenced by the performance of the underlying vehicular network with intermittent connections, which make existing routing solutions hardly to be applied directly. Epidemic routing, especially the one using random linear network coding, has been studied and proved as an efficient way in the consideration of delivery performance. Much pioneering work has tried to figure out how epidemic routing using network coding (ERNC) performs in VCPS, either by simulation or by analysis. However, none of them has been able to expose the potential of ERNC accurately. In this paper, we present a stochastic analytical framework to study the performance of ERNC in VCPS with intermittent connections. By novelly modeling ERNC in VCPS using a token-bucket model, our framework can provide a much more accurate results than any existing work on the unicast delivery performance analysis of ERNC in VCPS. The correctness of our analytical results has also been confirmed by our extensive simulations.

Opportunistic Data Gathering and Dissemination in Urban Scenarios

In the era of the Internet of Everything, a user with a handheld or wearable device equipped with sensing capability has become a producer as well as a consumer of information and services. The more powerful these devices get, the more likely it is that they will generate and share content locally, leading to the presence of distributed information sources and the diminishing role of centralized servers. As of current practice, we rely on infrastructure acting as an intermediary, providing access to the data. However, infrastructure-based connectivity might not always be available or the best alternative. Moreover, it is often the case where the data and the processes acting upon them are of local scopus. Answers to a query about a nearby object, an information source, a process, an experience, an ability, etc. could be answered locally without reliance on infrastructure-based platforms. The data might have temporal validity limited to or bounded to a geographical area and/or the social context where the user is immersed in. In this envisioned scenario users could interact locally without the need for a central authority, hence, the claim of an infrastructure-less, provider-less platform. The data is owned by the users and consulted locally as opposed to the current approach of making them available globally and stay on forever. From a technical viewpoint, this network resembles a Delay/Disruption Tolerant Network where consumers and producers might be spatially and temporally decoupled exchanging information with each other in an adhoc fashion. To this end, we propose some novel data gathering and dissemination strategies for use in urban-wide environments which do not rely on strict infrastructure mediation. While preserving the general aspects of our study and without loss of generality, we focus our attention toward practical applicative scenarios which help us capture the characteristics of opportunistic communication networks.

Information-centric communication in mobile and wireless networks

Information-centric networking (ICN) is a new communication paradigm that has been proposed to cope with drawbacks of host-based communication protocols, namely scalability and security. In this thesis, we base our work on Named Data Networking (NDN), which is a popular ICN architecture, and investigate NDN in the context of wireless and mobile ad hoc networks. In a first part, we focus on NDN efficiency (and potential improvements) in wireless environments by investigating NDN in wireless one-hop communication, i.e., without any routing protocols. A basic requirement to initiate informationcentric communication is the knowledge of existing and available content names. Therefore, we develop three opportunistic content discovery algorithms and evaluate them in diverse scenarios for different node densities and content distributions. After content names are known, requesters can retrieve content opportunistically from any neighbor node that provides the content. However, in case of short contact times to content sources, content retrieval may be disrupted. Therefore, we develop a requester application that keeps meta information of disrupted content retrievals and enables resume operations when a new content source has been found. Besides message efficiency, we also evaluate power consumption of information-centric broadcast and unicast communication. Based on our findings, we develop two mechanisms to increase efficiency of information-centric wireless one-hop communication. The first approach called Dynamic Unicast (DU) avoids broadcast communication whenever possible since broadcast transmissions result in more duplicate Data transmissions, lower data rates and higher energy consumption on mobile nodes, which are not interested in overheard Data, compared to unicast communication. Hence, DU uses broadcast communication only until a content source has been found and then retrieves content directly via unicast from the same source. The second approach called RC-NDN targets efficiency of wireless broadcast communication by reducing the number of duplicate Data transmissions. In particular, RC-NDN is a Data encoding scheme for content sources that increases diversity in wireless broadcast transmissions such that multiple concurrent requesters can profit from each others’ (overheard) message transmissions. If requesters and content sources are not in one-hop distance to each other, requests need to be forwarded via multi-hop routing. Therefore, in a second part of this thesis, we investigate information-centric wireless multi-hop communication. First, we consider multi-hop broadcast communication in the context of rather static community networks. We introduce the concept of preferred forwarders, which relay Interest messages slightly faster than non-preferred forwarders to reduce redundant duplicate message transmissions. While this approach works well in static networks, the performance may degrade in mobile networks if preferred forwarders may regularly move away. Thus, to enable routing in mobile ad hoc networks, we extend DU for multi-hop communication. Compared to one-hop communication, multi-hop DU requires efficient path update mechanisms (since multi-hop paths may expire quickly) and new forwarding strategies to maintain NDN benefits (request aggregation and caching) such that only a few messages need to be transmitted over the entire end-to-end path even in case of multiple concurrent requesters. To perform quick retransmission in case of collisions or other transmission errors, we implement and evaluate retransmission timers from related work and compare them to CCNTimer, which is a new algorithm that enables shorter content retrieval times in information-centric wireless multi-hop communication. Yet, in case of intermittent connectivity between requesters and content sources, multi-hop routing protocols may not work because they require continuous end-to-end paths. Therefore, we present agent-based content retrieval (ACR) for delay-tolerant networks. In ACR, requester nodes can delegate content retrieval to mobile agent nodes, which move closer to content sources, can retrieve content and return it to requesters. Thus, ACR exploits the mobility of agent nodes to retrieve content from remote locations. To enable delay-tolerant communication via agents, retrieved content needs to be stored persistently such that requesters can verify its authenticity via original publisher signatures. To achieve this, we develop a persistent caching concept that maintains received popular content in repositories and deletes unpopular content if free space is required. Since our persistent caching concept can complement regular short-term caching in the content store, it can also be used for network caching to store popular delay-tolerant content at edge routers (to reduce network traffic and improve network performance) while real-time traffic can still be maintained and served from the content store.

Sviluppo di un'applicazione di sincronizzazione file per reti challenged

Questa tesi si pone l'obiettivo di implementare in ambiente Linux un'applicazione di sincronizzazione, chiamata DTNbox, che permetta lo scambio di file tra due nodi di una rete classificabile come Delay-/Disruption-Tolerant Network (DTN), ossia una rete in cui a causa di ritardi, interruzioni, partizionamento, non sia possibile utilizzare l'usuale architettura di rete TCP/IP. E' evidente che i problemi menzionati rendono estremamente più complessa la sincronizzazione fra cartelle rispetto ad Internet, da cui le peculiarità di DTNbox rispetto ad altre applicazioni in rete visto che, ad esempio, non è possibile la sincronizzazione tramite un nodo centrale, come in Dropbox e similari, ma occorre basarsi su comunicazioni peer-to-peer. L'oggetto della mia tesi si è quindi sviluppato principalmente su tre direzioni: • Implementare, utilizzando il linguaggio di programmazione C, le funzionalità previste dal nuovo progetto per Linux • Integrarne e modificarne le parti ritenute carenti, man mano che i test parziali ne hanno mostrato la necessità • Testarne il suo corretto funzionamento Si è deciso pertanto di dare precedenza alla scrittura delle parti fondamentali del programma quali i moduli di controllo, la struttura e gestione del database e lo scambio di messaggi tra due nodi appartenenti ad una rete DTN per poter arrivare ad una prima versione funzionante del programma stesso, in modo che eventuali future tesi possano concentrarsi sullo sviluppo di una interfaccia grafica e sull'aggiunta di nuovi comandi e funzionalità accessorie. Il programma realizzato è stato poi testato su macchine virtuali grazie all'uso dello strumento Virtualbricks.

Impact of Mobility Constraints on Epidemic Broadcast in DTNs

In this paper, we investigate the effect of mobility constraints on epidemic broad-cast mechanisms in DTNs (Delay-Tolerant Networks). Major factors affecting epidemic broadcast performances are its forwarding algorithm and node mobility. The impact of forwarding algorithm and node mobility on epidemic broadcast mechanisms has been actively studied in the literature, but those studies use generally unconstrained mobility models. The objective of this paper is therefore to quantitatively investigate the effect of mobility constraints on epidemic broadcast mechanisms. We evaluate the performances of P-BCAST (PUSH-based BroadCast), SA-BCAST (Self-Adaptive BroadCast), and HP-BCAST (History-based P-BCAST) with a random waypoint mobility model with mobility constraints.

Energy Efficient GPS Acquisition with Sparse-GPS

Following rising demands in positioning with GPS, low-cost receivers are becoming widely available; but their energy demands are still too high. For energy efficient GPS sensing in delay-tolerant applications, the possibility of offloading a few milliseconds of raw signal samples and leveraging the greater processing power of the cloud for obtaining a position fix is being actively investigated. In an attempt to reduce the energy cost of this data offloading operation, we propose Sparse-GPS(1): a new computing framework for GPS acquisition via sparse approximation. Within the framework, GPS signals can be efficiently compressed by random ensembles. The sparse acquisition information, pertaining to the visible satellites that are embedded within these limited measurements, can subsequently be recovered by our proposed representation dictionary. By extensive empirical evaluations, we demonstrate the acquisition quality and energy gains of Sparse-GPS. We show that it is twice as energy efficient than offloading uncompressed data, and has 5-10 times lower energy costs than standalone GPS; with a median positioning accuracy of 40 m.

Sustainable IT and IT for sustainability

Energy and sustainability have become one of the most critical issues of our generation. While the abundant potential of renewable energy such as solar and wind provides a real opportunity for sustainability, their intermittency and uncertainty present a daunting operating challenge. This thesis aims to develop analytical models, deployable algorithms, and real systems to enable efficient integration of renewable energy into complex distributed systems with limited information.

The first thrust of the thesis is to make IT systems more sustainable by facilitating the integration of renewable energy into these systems. IT represents the fastest growing sectors in energy usage and greenhouse gas pollution. Over the last decade there are dramatic improvements in the energy efficiency of IT systems, but the efficiency improvements do not necessarily lead to reduction in energy consumption because more servers are demanded. Further, little effort has been put in making IT more sustainable, and most of the improvements are from improved "engineering" rather than improved "algorithms". In contrast, my work focuses on developing algorithms with rigorous theoretical analysis that improve the sustainability of IT. In particular, this thesis seeks to exploit the flexibilities of cloud workloads both (i) in time by scheduling delay-tolerant workloads and (ii) in space by routing requests to geographically diverse data centers. These opportunities allow data centers to adaptively respond to renewable availability, varying cooling efficiency, and fluctuating energy prices, while still meeting performance requirements. The design of the enabling algorithms is however very challenging because of limited information, non-smooth objective functions and the need for distributed control. Novel distributed algorithms are developed with theoretically provable guarantees to enable the "follow the renewables" routing. Moving from theory to practice, I helped HP design and implement industry's first Net-zero Energy Data Center.

The second thrust of this thesis is to use IT systems to improve the sustainability and efficiency of our energy infrastructure through data center demand response. The main challenges as we integrate more renewable sources to the existing power grid come from the fluctuation and unpredictability of renewable generation. Although energy storage and reserves can potentially solve the issues, they are very costly. One promising alternative is to make the cloud data centers demand responsive. The potential of such an approach is huge.

To realize this potential, we need adaptive and distributed control of cloud data centers and new electricity market designs for distributed electricity resources. My work is progressing in both directions. In particular, I have designed online algorithms with theoretically guaranteed performance for data center operators to deal with uncertainties under popular demand response programs. Based on local control rules of customers, I have further designed new pricing schemes for demand response to align the interests of customers, utility companies, and the society to improve social welfare.

车载容迟网络中一种基于真实轨迹的车辆移动模型

车辆移动模型的选择会严重影响车载容迟网络中关键技术的仿真研究结果.现有车辆移动模型大多属于合成移动模型,不符合真实环境.基于车辆真实移动轨迹建立车辆移动模型,考虑了道路拓扑选择、车辆速度控制、车辆初始位置选择以及路口转向选择等因素.在此基础上,进一步分析了模型对实际车辆行为模拟的接近程度、车辆的分布特性,以及基于该模型的网络连接特性.结果表明,提出的模型能够真实地逼近现实环境中车辆的实际行为.

基于web的遥操作系统时延分析

采用预测控制算法给出了一种带有时延补偿器的新的控制结构,分别在前向通道和反馈通道设计补偿器对网络时延进行补偿.实验结果表明:带有预测器及补偿器的新的控制结构可以改善系统的动态性能,并且能够保证系统在具有时延和数据丢失的环境下的稳定性.

网上协同工作中的等待时距知觉研究

A newly developed experimental model called simulation of real mission was used to explore law of time perception and user endurance for feedback delay under Network-Supported Co-operative Work. Some non-technological factors influencing time perception and user endurance (mission type、difficulty level、feedback method、partner type、gender and A type behavior pattern) were also examined. Results of the study showed that: (1) Under condition of waiting without feedback, mission type and difficulty level demonstrated significant main effects on judgment of waiting duration. People will wait more time to receive partner's feedback if he or she perceives that partner's task is difficult, and the longest waiting duration (LWD) in the mission of computation is longer than the LWD in the mission of proof searching. (2) Under condition of waiting with feedback, experimental data perfectly supported Vierordt's Law: short duration is underestimated, long duration is overestimated, only proper duration (2-6 second) can be estimated correctly. The proper duration will vary with the changing of difficulty levels of mission. More long the waiting duration is, more estimation error will be occurred. The type difference of partner has no significant effect on the law of time perception. (3) Under condition of waiting with feedback, non-technology factors can significantly effect user's endurance. When subjects were told their partner was human, mission type and difficulty level of mission could significantly effect user's endurance. When subjects were told their partner was computer, A type behavior pattern and difficulty level of mission could significantly effect user's endurance. The two-way interaction effect between A type behavior pattern and gender was detected.

Detour-Based Mobility Coordination in DTNs

Commonly, research work in routing for delay tolerant networks (DTN) assumes that node encounters are predestined, in the sense that they are the result of unknown, exogenous processes that control the mobility of these nodes. In this paper, we argue that for many applications such an assumption is too restrictive: while the spatio-temporal coordinates of the start and end points of a node's journey are determined by exogenous processes, the specific path that a node may take in space-time, and hence the set of nodes it may encounter could be controlled in such a way so as to improve the performance of DTN routing. To that end, we consider a setting in which each mobile node is governed by a schedule consisting of a ist of locations that the node must visit at particular times. Typically, such schedules exhibit some level of slack, which could be leveraged for DTN message delivery purposes. We define the Mobility Coordination Problem (MCP) for DTNs as follows: Given a set of nodes, each with its own schedule, and a set of messages to be exchanged between these nodes, devise a set of node encounters that minimize message delivery delays while satisfying all node schedules. The MCP for DTNs is general enough that it allows us to model and evaluate some of the existing DTN schemes, including data mules and message ferries. In this paper, we show that MCP for DTNs is NP-hard and propose two detour-based approaches to solve the problem. The first (DMD) is a centralized heuristic that leverages knowledge of the message workload to suggest specific detours to optimize message delivery. The second (DNE) is a distributed heuristic that is oblivious to the message workload, and which selects detours so as to maximize node encounters. We evaluate the performance of these detour-based approaches using extensive simulations based on synthetic workloads as well as real schedules obtained from taxi logs in a major metropolitan area. Our evaluation shows that our centralized, workload-aware DMD approach yields the best performance, in terms of message delay and delivery success ratio, and that our distributed, workload-oblivious DNE approach yields favorable performance when compared to approaches that require the use of data mules and message ferries.

Investigation of the M2/G2/1/ ∞, N Queue with Restricted Admission of Priority Customers and its Application to HSDPA Mobile Systems

This paper investigates a queuing system for QoS optimization of multimedia traffic consisting of aggregated streams with diverse QoS requirements transmitted to a mobile terminal over a common downlink shared channel. The queuing system, proposed for buffer management of aggregated single-user traffic in the base station of High-Speed Downlink Packet Access (HSDPA), allows for optimum loss/delay/jitter performance for end-user multimedia traffic with delay-tolerant non-real-time streams and partially loss tolerant real-time streams. In the queuing system, the real-time stream has non-preemptive priority in service but the number of the packets in the system is restricted by a constant. The non-real-time stream has no service priority but is allowed unlimited access to the system. Both types of packets arrive in the stationary Poisson flow. Service times follow general distribution depending on the packet type. Stability condition for the model is derived. Queue length distribution for both types of customers is calculated at arbitrary epochs and service completion epochs. Loss probability for priority packets is computed. Waiting time distribution in terms of Laplace-Stieltjes transform is obtained for both types of packets. Mean waiting time and jitter are computed. Numerical examples presented demonstrate the effectiveness of the queuing system for QoS optimization of buffered end-user multimedia traffic with aggregated real-time and non-real-time streams.

How much multiuser diversity is required over large-scale fading?

In multiuser diversity systems, the impact of large-scale fading on the total system performance such as link quality and system power has not been widely addressed. Considering large-scale fading, we propose an adaptive multiuser scheduling to minimize the total system power while reducing the effect of large-scale fading on the system bit error rate. The number of active users is adapted to every shadow variation, which varies slower than small-scale fading. We consider the two widely used multiuser systems (i.e., delay-tolerant, and delay-sensitive multiuser systems). Closed-form expressions for the bit error rate are derived. The selection procedure for the minimum number of users is introduced for guaranteed performance of the above multiuser systems. The impact of adaptive multiuser diversity gain on the system power and bit error rate is illustrated over large-scale fading channels by numerical results.

Classificação e previsão de cardiotocogramas usando algoritmos baseados em redes neuronais

Mestrado em Computação e Instrumentação Médica