Distributed Routing and Charging Scheduling Optimization for Internet of Electric Vehicles

In this paper, we consider an Internet of Electric Vehicles (IoEV) powered by heterogeneous charging facilities in the transportation network. In particular, we take into account the state-of-the-art vehicle-to-grid (V2G) charging and renewable power generation technologies implemented in the charging stations, such that the charging stations differ from each other in their energy capacities, electricity prices, and service types (i.e., with or without V2G capability). In this case, each electric vehicle (EV) user needs to decide which path to take (i.e., the routing problem) and where and how much to charge/discharge its battery at the charging stations in the chosen path (i.e., the charging scheduling problem) such that its journey can be accomplished with the minimum monetary cost and time delay. From the system operator's perspective, we formulate a joint routing and charging scheduling optimization problem for an IoEV network, and show that the problem is NP-hard in general. To tackle the NP-hardness, we propose an approximate algorithm that can achieve affordable computational complexity in large-size IoEV networks. The proposed algorithm allows the routing and charging solution to be calculated in a distributed manner by the system operator and EV users, which can effectively reduce the computational complexity at the system operator and protect the EV users' privacy and autonomy. Besides, a proximal method is introduced to improve the convergence rate of the proposed algorithm. Extensive simulations using real world data show that the proposed distributed algorithm can achieve near-optimal performance with relatively low computational complexity in different system set-ups.

Routing and search on large scale networks

Dominique Florian Tschopp

In this thesis, we address two seemingly unrelated problems, namely routing in large wireless ad hoc networks and comparison based search in image databases. However, the underlying problem is in essence similar and we can use the same strategy to attack those two problems. In both cases, the intrinsic complexity of the problem is in some sense low, and we can exploit this fact to design efficient algorithms. A wireless ad hoc network is a communication network consisting of wireless devices such as for instance laptops or cell phones. The network does not have any fixed infrastructure, and hence nodes which cannot communicate directly over the wireless medium must use intermediate nodes as relays. This immediately raises the question of how to select the relay nodes. Ideally, one would like to find a path from the source to the destination which is as short as possible. The length of the found path, also called route, typically depends on how much signaling traffic is generated in order to establish the route. This is the fundamental trade-off that we will investigate in this thesis. As mentioned above, we try and exploit the fact that the communication network is intrinsically low-dimensional, or in other words has low complexity. We show that this is indeed the case for a large class of models and that we can design efficient algorithms for routing that use this property. Low dimensionality implies that we can well embed the network in a low-dimensional space, or build simple hierarchical decompositions of the network. We use both those techniques to design routing algorithms. Comparison based search in image databases is a new problem that can be defined as follows. Given a large database of images, can a human user retrieve an image which he has in mind, or at least an image similar to that image, without going sequentially through all images? More precisely, we ask whether we can search a database of images only by making comparisons between images. As a case in point, we ask whether we can find a query image q only by asking questions of the type "does image q look more like image A or image B"? The analogous to signaling traffic for wireless networks would here be the questions we can ask human users in a learning phase anterior to the search. In other words, we would like to ask as few questions as possible to pre-process and prepare the database, while guaranteeing a certain quality of the results obtained in the search phase. As the underlying image space is not necessarily metric, this raises new questions on how to search spaces for which only rank information can be obtained. The rank of A with respect to B is k, if A is B's kth nearest neighbor. In this setup, low-dimensionality is analogous to the homogeneity of the image space. As we will see, the homogeneity can be captured by properties of the rank relationships. In turn, homogeneous spaces can be well decomposed hierarchically using comparisons. Further, it allows us to design good hash functions. To design efficient algorithms for these two problems, we can apply the same techniques mutatis mutandis. In both cases, we relied on the intuition that the problem has a low intrinsic complexity, and that we can exploit this fact. Our results come in the form of simulation results and asymptotic bounds.

EPFL2010

Toward Ultrafast Charging of Electric Vehicles

Massimiliano Capezzali, Stefano Grioni, Hardi Hõimoja, Hans Björn Püttgen, Alfred Rufer, Michail Vasiladiotis

The paper is devoted to the problems arising from the ultrafast (≤ 10 min) charging of an electric vehicle (EV). An ultrafast charging station (UFCS) must provide high power output with minimal influence on the electricity transmission system, which can only be achieved by the application of energy storage acting as an additional buffer between the vehicle and the grid. Besides storage, interfaces between a fast charging station and the outside environment (vehicle, utility grid) must be designed to fulfil a set of requirements. The main challenge is to be found within the specification of parameters for the design of future energy supply systems, providing for fast charging of the vehicle batteries while avoiding solicitations of the local distribution system which exceed its instantaneous power capabilities. The possible impact of an UFCS on the power distribution system is analysed with the stochastic approach, based on the utilisation of such a station. The general aspects of highly variable load profile clearly include the use of energy storage means that must be specified regarding both the energy storage and the instant power capabilities. Different technologies are analysed in terms of performances and costs. In conclusion, one of the important problems facing electric vehicles is the possibility of short-time charging, both as seen from the EV battery itself as well as from the local supply system. In this context, large load variations as seen from the local power system, at multiple levels, must be carefully assessed with special attention to feasible load changes at the coupling points. By addressing these technical issues as well as the financial constraints, the research aims at providing viable solution for broad ultrafast charging systems integration into the power distribution infrastructure.

2012

Artificial immune system for the Internet

Slavisa Sarafijanovic

We investigate the usability of the Artificial Immune Systems (AIS) approach for solving selected problems in computer networks. Artificial immune systems are created by using the concepts and algorithms inspired by the theory of how the Human Immune System (HIS) works. We consider two applications: detection of routing misbehavior in mobile ad hoc networks, and email spam filtering. In mobile ad hoc networks the multi-hop connectivity is provided by the collaboration of independent nodes. The nodes follow a common protocol in order to build their routing tables and forward the packets of other nodes. As there is no central control, some nodes may defect to follow the common protocol, which would have a negative impact on the overall connectivity in the network. We build an AIS for the detection of routing misbehavior by directly mapping the standard concepts and algorithms used for explaining how the HIS works. The implementation and evaluation in a simulator shows that the AIS mimics well most of the effects observed in the HIS, e.g. the faster secondary reaction to the already encountered misbehavior. However, its effectiveness and practical usability are very constrained, because some particularities of the problem cannot be accounted for by the approach, and because of the computational constrains (reported also in AIS literature) of the used negative selection algorithm. For the spam filtering problem, we apply the AIS concepts and algorithms much more selectively and in a less standard way, and we obtain much better results. We build the AIS for antispam on top of a standard technique for digest-based collaborative email spam filtering. We notice un advantageous and underemphasized technological difference between AISs and the HIS, and we exploit this difference to incorporate the negative selection in an innovative and computationally efficient way. We also improve the representation of the email digests used by the standard collaborative spam filtering scheme. We show that this new representation and the negative selection, when used together, improve significantly the filtering performance of the standard scheme on top of which we build our AIS. Our complete AIS for antispam integrates various innate and adaptive AIS mechanisms, including the mentioned specific use of the negative selection and the use of innate signalling mechanisms (PAMP and danger signals). In this way the AIS takes into account users' profiles, implicit or explicit feedback from the users, and the bulkiness of spam. We show by simulations that the overall AIS is very good both in detecting spam and in avoiding misdetection of good emails. Interestingly, both the innate and adaptive mechanisms prove to be crucial for achieving the good overall performance. We develop and test (within a simulator) our AIS for collaborative spam filtering in the case of email communications. The solution however seems to be well applicable to other types of Internet communications: Internet telephony, chat/sms, forum, news, blog, or web. In all these cases, the aim is to allow the wanted communications (content) and prevent those unwanted from reaching the end users and occupying their time and communication resources. The filtering problems, faced or likely to be faced in the near future by these applications, have or are likely to have the settings similar to those that we have in the email case: need for openness to unknown senders (creators of content, initiators of the communication), bulkiness in receiving spam (many recipients are usually affected by the same spam content), tolerance of the system to a small damage (to small amounts of unfiltered spam), possibility to implicitly or explicitly and in a cheap way obtain a feedback from the recipients about the damage (about spam that they receive), need for strong tolerance to wanted (non-spam) content. Our experiments with the email spam filtering show that our AIS, i.e. the way how we build it, is well fitted to such problem settings.

EPFL2008