Evolutionary methods for self-organizing cooperation in peer-to-peer networks

The Peer-to-Peer network paradigm is drawing the attention of both final users and researchers for its features. P2P networks shift from the classic client-server approach to a high level of decentralization where there is no central control and all the nodes should be able not only to require services, but to provide them to other peers as well. While on one hand such high level of decentralization might lead to interesting properties like scalability and fault tolerance, on the other hand it implies many new problems to deal with. A key feature of many P2P systems is openness, meaning that everybody is potentially able to join a network with no need for subscription or payment systems. The combination of openness and lack of central control makes it feasible for a user to free-ride, that is to increase its own benefit by using services without allocating resources to satisfy other peers’ requests. One of the main goals when designing a P2P system is therefore to achieve cooperation between users. Given the nature of P2P systems based on simple local interactions of many peers having partial knowledge of the whole system, an interesting way to achieve desired properties on a system scale might consist in obtaining them as emergent properties of the many interactions occurring at local node level. Two methods are typically used to face the problem of cooperation in P2P networks: 1) engineering emergent properties when designing the protocol; 2) study the system as a game and apply Game Theory techniques, especially to find Nash Equilibria in the game and to reach them making the system stable against possible deviant behaviors. In this work we present an evolutionary framework to enforce cooperative behaviour in P2P networks that is alternative to both the methods mentioned above. Our approach is based on an evolutionary algorithm inspired by computational sociology and evolutionary game theory, consisting in having each peer periodically trying to copy another peer which is performing better. The proposed algorithms, called SLAC and SLACER, draw inspiration from tag systems originated in computational sociology, the main idea behind the algorithm consists in having low performance nodes copying high performance ones. The algorithm is run locally by every node and leads to an evolution of the network both from the topology and from the nodes’ strategy point of view. Initial tests with a simple Prisoners’ Dilemma application show how SLAC is able to bring the network to a state of high cooperation independently from the initial network conditions. Interesting results are obtained when studying the effect of cheating nodes on SLAC algorithm. In fact in some cases selfish nodes rationally exploiting the system for their own benefit can actually improve system performance from the cooperation formation point of view. The final step is to apply our results to more realistic scenarios. We put our efforts in studying and improving the BitTorrent protocol. BitTorrent was chosen not only for its popularity but because it has many points in common with SLAC and SLACER algorithms, ranging from the game theoretical inspiration (tit-for-tat-like mechanism) to the swarms topology. We discovered fairness, meant as ratio between uploaded and downloaded data, to be a weakness of the original BitTorrent protocol and we drew inspiration from the knowledge of cooperation formation and maintenance mechanism derived from the development and analysis of SLAC and SLACER, to improve fairness and tackle freeriding and cheating in BitTorrent. We produced an extension of BitTorrent called BitFair that has been evaluated through simulation and has shown the abilities of enforcing fairness and tackling free-riding and cheating nodes.

Adaptive multiscale biological signal processing

Biological processes are very complex mechanisms, most of them being accompanied by or manifested as signals that reflect their essential characteristics and qualities. The development of diagnostic techniques based on signal and image acquisition from the human body is commonly retained as one of the propelling factors in the advancements in medicine and biosciences recorded in the recent past. It is a fact that the instruments used for biological signal and image recording, like any other acquisition system, are affected by non-idealities which, by different degrees, negatively impact on the accuracy of the recording. This work discusses how it is possible to attenuate, and ideally to remove, these effects, with a particular attention toward ultrasound imaging and extracellular recordings. Original algorithms developed during the Ph.D. research activity will be examined and compared to ones in literature tackling the same problems; results will be drawn on the base of comparative tests on both synthetic and in-vivo acquisitions, evaluating standard metrics in the respective field of application. All the developed algorithms share an adaptive approach to signal analysis, meaning that their behavior is not dependent only on designer choices, but driven by input signal characteristics too. Performance comparisons following the state of the art concerning image quality assessment, contrast gain estimation and resolution gain quantification as well as visual inspection highlighted very good results featured by the proposed ultrasound image deconvolution and restoring algorithms: axial resolution up to 5 times better than algorithms in literature are possible. Concerning extracellular recordings, the results of the proposed denoising technique compared to other signal processing algorithms pointed out an improvement of the state of the art of almost 4 dB.

Sistemi riconfigurabili a basso consumo per applicazioni di monitoraggio distribuito

The term Ambient Intelligence (AmI) refers to a vision on the future of the information society where smart, electronic environment are sensitive and responsive to the presence of people and their activities (Context awareness). In an ambient intelligence world, devices work in concert to support people in carrying out their everyday life activities, tasks and rituals in an easy, natural way using information and intelligence that is hidden in the network connecting these devices. This promotes the creation of pervasive environments improving the quality of life of the occupants and enhancing the human experience. AmI stems from the convergence of three key technologies: ubiquitous computing, ubiquitous communication and natural interfaces. Ambient intelligent systems are heterogeneous and require an excellent cooperation between several hardware/software technologies and disciplines, including signal processing, networking and protocols, embedded systems, information management, and distributed algorithms. Since a large amount of fixed and mobile sensors embedded is deployed into the environment, the Wireless Sensor Networks is one of the most relevant enabling technologies for AmI. WSN are complex systems made up of a number of sensor nodes which can be deployed in a target area to sense physical phenomena and communicate with other nodes and base stations. These simple devices typically embed a low power computational unit (microcontrollers, FPGAs etc.), a wireless communication unit, one or more sensors and a some form of energy supply (either batteries or energy scavenger modules). WNS promises of revolutionizing the interactions between the real physical worlds and human beings. Low-cost, low-computational power, low energy consumption and small size are characteristics that must be taken into consideration when designing and dealing with WSNs. To fully exploit the potential of distributed sensing approaches, a set of challengesmust be addressed. Sensor nodes are inherently resource-constrained systems with very low power consumption and small size requirements which enables than to reduce the interference on the physical phenomena sensed and to allow easy and low-cost deployment. They have limited processing speed,storage capacity and communication bandwidth that must be efficiently used to increase the degree of local ”understanding” of the observed phenomena. A particular case of sensor nodes are video sensors. This topic holds strong interest for a wide range of contexts such as military, security, robotics and most recently consumer applications. Vision sensors are extremely effective for medium to long-range sensing because vision provides rich information to human operators. However, image sensors generate a huge amount of data, whichmust be heavily processed before it is transmitted due to the scarce bandwidth capability of radio interfaces. In particular, in video-surveillance, it has been shown that source-side compression is mandatory due to limited bandwidth and delay constraints. Moreover, there is an ample opportunity for performing higher-level processing functions, such as object recognition that has the potential to drastically reduce the required bandwidth (e.g. by transmitting compressed images only when something ‘interesting‘ is detected). The energy cost of image processing must however be carefully minimized. Imaging could play and plays an important role in sensing devices for ambient intelligence. Computer vision can for instance be used for recognising persons and objects and recognising behaviour such as illness and rioting. Having a wireless camera as a camera mote opens the way for distributed scene analysis. More eyes see more than one and a camera system that can observe a scene from multiple directions would be able to overcome occlusion problems and could describe objects in their true 3D appearance. In real-time, these approaches are a recently opened field of research. In this thesis we pay attention to the realities of hardware/software technologies and the design needed to realize systems for distributed monitoring, attempting to propose solutions on open issues and filling the gap between AmI scenarios and hardware reality. The physical implementation of an individual wireless node is constrained by three important metrics which are outlined below. Despite that the design of the sensor network and its sensor nodes is strictly application dependent, a number of constraints should almost always be considered. Among them: • Small form factor to reduce nodes intrusiveness. • Low power consumption to reduce battery size and to extend nodes lifetime. • Low cost for a widespread diffusion. These limitations typically result in the adoption of low power, low cost devices such as low powermicrocontrollers with few kilobytes of RAMand tenth of kilobytes of program memory with whomonly simple data processing algorithms can be implemented. However the overall computational power of the WNS can be very large since the network presents a high degree of parallelism that can be exploited through the adoption of ad-hoc techniques. Furthermore through the fusion of information from the dense mesh of sensors even complex phenomena can be monitored. In this dissertation we present our results in building several AmI applications suitable for a WSN implementation. The work can be divided into two main areas:Low Power Video Sensor Node and Video Processing Alghoritm and Multimodal Surveillance . Low Power Video Sensor Nodes and Video Processing Alghoritms In comparison to scalar sensors, such as temperature, pressure, humidity, velocity, and acceleration sensors, vision sensors generate much higher bandwidth data due to the two-dimensional nature of their pixel array. We have tackled all the constraints listed above and have proposed solutions to overcome the current WSNlimits for Video sensor node. We have designed and developed wireless video sensor nodes focusing on the small size and the flexibility of reuse in different applications. The video nodes target a different design point: the portability (on-board power supply, wireless communication), a scanty power budget (500mW),while still providing a prominent level of intelligence, namely sophisticated classification algorithmand high level of reconfigurability. We developed two different video sensor node: The device architecture of the first one is based on a low-cost low-power FPGA+microcontroller system-on-chip. The second one is based on ARM9 processor. Both systems designed within the above mentioned power envelope could operate in a continuous fashion with Li-Polymer battery pack and solar panel. Novel low power low cost video sensor nodes which, in contrast to sensors that just watch the world, are capable of comprehending the perceived information in order to interpret it locally, are presented. Featuring such intelligence, these nodes would be able to cope with such tasks as recognition of unattended bags in airports, persons carrying potentially dangerous objects, etc.,which normally require a human operator. Vision algorithms for object detection, acquisition like human detection with Support Vector Machine (SVM) classification and abandoned/removed object detection are implemented, described and illustrated on real world data. Multimodal surveillance: In several setup the use of wired video cameras may not be possible. For this reason building an energy efficient wireless vision network for monitoring and surveillance is one of the major efforts in the sensor network community. Energy efficiency for wireless smart camera networks is one of the major efforts in distributed monitoring and surveillance community. For this reason, building an energy efficient wireless vision network for monitoring and surveillance is one of the major efforts in the sensor network community. The Pyroelectric Infra-Red (PIR) sensors have been used to extend the lifetime of a solar-powered video sensor node by providing an energy level dependent trigger to the video camera and the wireless module. Such approach has shown to be able to extend node lifetime and possibly result in continuous operation of the node.Being low-cost, passive (thus low-power) and presenting a limited form factor, PIR sensors are well suited for WSN applications. Moreover techniques to have aggressive power management policies are essential for achieving long-termoperating on standalone distributed cameras needed to improve the power consumption. We have used an adaptive controller like Model Predictive Control (MPC) to help the system to improve the performances outperforming naive power management policies.

Aspekte der Modellbildung: Konzepte und Anwendung in der Atmungsphysiologie

Im ersten Teil 'Analyse der Grundlagen' der Dissertation 'Aspekte der Modellbildung: Konzepte und Anwendung in der Atmungsphysiologie' werden die Grundlagen zur Verfügung gestellt. Ausgehend von der Definition der modularer dynamischer Systeme im Kapitel 1 werden Grundbegriffe zu Modellen, Simulation und Modellentwicklung (Kapitel 2) dargelegt und schließlich folgt ein Kapitel über Netzmodelle. Im zweiten Teil wird 'der Prozess der Operationalisierung' untersucht. Im Kapitel 4 wird mit 'dem Koordinatensystem der Modellbildung' ein allgemeiner Lebenszyklus zur Modellbildung vorgestellt. Das Kapitel 5 zur 'Modellentwicklung' steht im Zentrum der Arbeit, wo eine generische Struktur für modulare Level-Raten-Modelle entwickelt wird. Das Kapitel endet mit einem Konzept zur Kalibrierung von Modellen, das auf Data Mining von Modelldaten basiert. Der Prozess der Operationalisierung endet mit der Validierung im sechsten Kapitel. 'Die Validierung am Beispiel der Atmungsphysiologie' im dritten Teil stellt die Anwendung der in beiden Teilen zuvor entwickelten Theorie dar. Zunächst wird das Projekt 'Evita-Weaning-System' vorgestellt, in dem die Arbeit entstanden ist. Ferner werden die notwendigen medizinischen Grundlagen der Atmungsphysiologie analysiert (Kapitel 7). Eine detaillierte Beschreibung des Modells der Atmungsphysiologie und der dabei entwickelten Algorithmen folgt im achten Kapitel. Die Arbeit schließt mit einem Kapitel zur Validierung des physiologischen Modells.

Troposphere Calibration Techniques for Deep Space Probe Tracking

Ground-based Earth troposphere calibration systems play an important role in planetary exploration, especially to carry out radio science experiments aimed at the estimation of planetary gravity fields. In these experiments, the main observable is the spacecraft (S/C) range rate, measured from the Doppler shift of an electromagnetic wave transmitted from ground, received by the spacecraft and coherently retransmitted back to ground. If the solar corona and interplanetary plasma noise is already removed from Doppler data, the Earth troposphere remains one of the main error sources in tracking observables. Current Earth media calibration systems at NASA’s Deep Space Network (DSN) stations are based upon a combination of weather data and multidirectional, dual frequency GPS measurements acquired at each station complex. In order to support Cassini’s cruise radio science experiments, a new generation of media calibration systems were developed, driven by the need to achieve the goal of an end-to-end Allan deviation of the radio link in the order of 3×〖10〗^(-15) at 1000 s integration time. The future ESA’s Bepi Colombo mission to Mercury carries scientific instrumentation for radio science experiments (a Ka-band transponder and a three-axis accelerometer) which, in combination with the S/C telecommunication system (a X/X/Ka transponder) will provide the most advanced tracking system ever flown on an interplanetary probe. Current error budget for MORE (Mercury Orbiter Radioscience Experiment) allows the residual uncalibrated troposphere to contribute with a value of 8×〖10〗^(-15) to the two-way Allan deviation at 1000 s integration time. The current standard ESA/ESTRACK calibration system is based on a combination of surface meteorological measurements and mathematical algorithms, capable to reconstruct the Earth troposphere path delay, leaving an uncalibrated component of about 1-2% of the total delay. In order to satisfy the stringent MORE requirements, the short time-scale variations of the Earth troposphere water vapor content must be calibrated at ESA deep space antennas (DSA) with more precise and stable instruments (microwave radiometers). In parallel to this high performance instruments, ESA ground stations should be upgraded to media calibration systems at least capable to calibrate both troposphere path delay components (dry and wet) at sub-centimetre level, in order to reduce S/C navigation uncertainties. The natural choice is to provide a continuous troposphere calibration by processing GNSS data acquired at each complex by dual frequency receivers already installed for station location purposes. The work presented here outlines the troposphere calibration technique to support both Deep Space probe navigation and radio science experiments. After an introduction to deep space tracking techniques, observables and error sources, in Chapter 2 the troposphere path delay is widely investigated, reporting the estimation techniques and the state of the art of the ESA and NASA troposphere calibrations. Chapter 3 deals with an analysis of the status and the performances of the NASA Advanced Media Calibration (AMC) system referred to the Cassini data analysis. Chapter 4 describes the current release of a developed GNSS software (S/W) to estimate the troposphere calibration to be used for ESA S/C navigation purposes. During the development phase of the S/W a test campaign has been undertaken in order to evaluate the S/W performances. A description of the campaign and the main results are reported in Chapter 5. Chapter 6 presents a preliminary analysis of microwave radiometers to be used to support radio science experiments. The analysis has been carried out considering radiometric measurements of the ESA/ESTEC instruments installed in Cabauw (NL) and compared with the requirements of MORE. Finally, Chapter 7 summarizes the results obtained and defines some key technical aspects to be evaluated and taken into account for the development phase of future instrumentation.

An evolutionary approach to the design of experiments for combinatorial optimization with an application to enzyme engineering

In a large number of problems the high dimensionality of the search space, the vast number of variables and the economical constrains limit the ability of classical techniques to reach the optimum of a function, known or unknown. In this thesis we investigate the possibility to combine approaches from advanced statistics and optimization algorithms in such a way to better explore the combinatorial search space and to increase the performance of the approaches. To this purpose we propose two methods: (i) Model Based Ant Colony Design and (ii) Naïve Bayes Ant Colony Optimization. We test the performance of the two proposed solutions on a simulation study and we apply the novel techniques on an appplication in the field of Enzyme Engineering and Design.

Synthese und Selbstorganisation von Perylendiimid-Oligonucleotid-Konjugaten

Im Rahmen dieser Arbeit wurde eine Methode entwickelt, Perylendiimidfarbstoffe mit Oligonucleotiden in der Lösung zu verknüpfen. Das Ziel der Arbeit war die nicht-kovalente Synthese von Perylendiimid-DNA- und Protein- supramolekularen Strukturen. Dabei werden die molekularen Erkennungseigenschaften von DNA und Proteinen zunutze gemacht. Insgesamt drei Themenbereiche wurden dabei betrachtet: 1. Synthese und Hybridisierung von symmetrischen und asymmetrischen Perylendiimid-bis(oligonucleotid)-konjugaten für die Bildung supramolekularer Strukturen, 2. Erzeugung von Oberflächenstrukturen auf der Basis von Streptavidin-Perylendiimid-Komplexen, 3. Synthese wasserlöslicher Rylenfarbstoffe für Anwendungen in biologischen Systemen. Zur Synthese und Hybridisierung von Perylendiimid-Oligonucleotid-Konjugaten wurde eine neue Idee verfolgt und erfolgreich realisiert. Dabei handelt es sich um die Synthese von Perylendiimid-DNA-Polymeren durch nicht-kovalente Bindungen. Die Basis des entwickelten Konzepts ist die Ausnutzung der Erkennungseigenschaften der DNA, um Perylendiimidmoleküle in eine lineare Makrostruktur zu organisieren, was sonst nur durch komplizierte chemische Polymersynthese zugänglich wäre. Die Selbstorganisation von zwei komplementären Perylendiimid-bis(oligonucleotid)-konjugaten (PODN1 und PODN2), die an der 5`-Position verknüpft sind, führte zu einem linearen Perylendiimid-DNA-Polymer in der Form von …ABABABAB…., das mit Hilfe von Gelelektrophorese charakterisiert wurde. Eindrucksvoll war auch die erfolgreiche Kopplung des hydrophoben Perylendiimids mit zwei unterschiedlichen Oligonucleotidsequenzen in der Lösung, um asymmetrische Perylendiimid-bis(oligonucleotid)-konjugate zu synthetisieren. Mit solchen asymmetrischen Konjugaten konnte die programmierbare Selbstorganisation der Perylendiimid-Oligonucleotide zu einer definierten Polymerstruktur realisiert werden. Die Synthese von PDI-(biotin)2 wurde vorgestellt. Durch die spezifische Erkennungseigenschaft zwischen Biotin und Streptavidin ist es möglich, eine Oberflächenstruktur zu bilden. Die Immobilisierungsexperimente zeigten, dass das PDI (biotin)2 Streptavidin erkennen und binden kann. Dabei konnte eine multischichtige Nanostruktur (5 Doppelschichten) auf einer Goldoberfläche.

Verso una sociologia della sostenibilità: il caso delle Città in Transizione. Prospettive e limiti di un percorso bottom-up

Oggetto di indagine del lavoro è il movimento ambientalista e culturale delle Città in Transizione che rappresentano esperimenti di ri-localizzazione delle risorse volte a preparare le comunità (paesi, città, quartieri) ad affrontare la duplice sfida del cambiamento climatico e del picco del petrolio. A partire dal Regno Unito, la rete delle Transition Towns si è in pochi anni estesa significativamente e conta oggi più di mille iniziative. L’indagine di tale movimento ha richiesto in prima battuta di focalizzare l’attenzione sul campo disciplinare della sociologia dell’ambiente. L’attenzione si è concentrata sul percorso di riconoscimento che ha reso la sociologia dell’ambiente una branca autonoma e sul percorso teorico-concettuale che ha caratterizzato la profonda spaccatura paradigmatica proposta da Catton e Dunlap, che hanno introdotto nel dibattito sociologico il Nuovo Paradigma Ecologico, prendendo le distanze dalla tradizionale visione antropocentrica della sociologia classica. Vengono poi presentate due delle più influenti prospettive teoriche della disciplina, quella del Treadmill of Production e la più attuale teoria della modernizzazione ecologica. La visione che viene adottata nel lavoro di tesi è quella proposta da Spaargaren, fautore della teoria della modernizzazione ecologica, secondo il quale la sociologia dell’ambiente può essere collocata in uno spazio intermedio che sta tra le scienze ambientali e la sociologia generale, evidenziando una vocazione interdisciplinare richiamata anche dal dibattito odierno sulla sostenibilità. Ma le evidenze empiriche progressivamente scaturite dallo studio di questo movimento che si autodefinisce culturale ed ambientalista hanno richiesto una cornice teorica più ampia, quella della modernità riflessiva e della società del rischio, in grado di fornire categorie concettuali spendibili nella descrizione dei problemi ambientali e nell’indagine del mutamento socio-culturale e dei suoi attori. I riferimenti empirici dello studio sono tre specifiche realtà locali in Transizione: York in Transition per il Regno Unito, Monteveglio (Bo) e Scandiano (Re) in Transizione per l’Italia.

Untersuchungen zum Austausch von Stickstoffdioxid (NO 2) zwischen Pflanzen und Atmosphäre

Der Austausch der NO2-Konzentration zwischen der Atmosphäre und verschiedenen Bäumen (Betula pendula, Fagus sylvatica, Quercus robur, Quercus ilex und Pinus sylvestris) wurde mit einer Dynamischen Küvette gemessen. Die NO2-Konzentrationen wurden mit einem CLD 780 TR Analysator in Verbindung mit einem PLC 762 gemessen. Die experimentellen Untersuchungen wurden im Dunkeln und unter zwei Lichtintensitäts-Niveaus (PAR, 450 und 900 µmol m-2 s-1) und sechs verschiedene NO2-Konzentrationen zwischen 0 - 5.0 ppb durchgeführt. Der stomatäre Einfluss wurde unter Einsatz des Hormons Abscisinsäure untersucht. Die Umgebungsparameter (Lufttemperatur und Luftfeuchtigkeit) wurden konstant gehalten. Die Daten zeigten klar und deutlich den dominanten Einfluss der jeweiligen Baumspezies auf die NO2-Konzentrationen innerhalb der Küvette. Die Ergebnisse dieser Arbeit belegen bei allen Spezies eine lineare Abhängigkeit der NO2-Austauschrate mit der NO2-Umgebungskozentration und mit der stomatären Leitfähigkeit. Das Vorhandensein eines Kompensationspunkt wird nicht bestätigt.

A numerical methodology for the multi-objective optimization of the DI Diesel engine combustion

DI Diesel engine are widely used both for industrial and automotive applications due to their durability and fuel economy. Nonetheless, increasing environmental concerns force that type of engine to comply with increasingly demanding emission limits, so that, it has become mandatory to develop a robust design methodology of the DI Diesel combustion system focused on reduction of soot and NOx simultaneously while maintaining a reasonable fuel economy. In recent years, genetic algorithms and CFD three-dimensional combustion simulations have been successfully applied to that kind of problem. However, combining GAs optimization with actual CFD three-dimensional combustion simulations can be too onerous since a large number of calculations is usually needed for the genetic algorithm to converge, resulting in a high computational cost and, thus, limiting the suitability of this method for industrial processes. In order to make the optimization process less time-consuming, CFD simulations can be more conveniently used to generate a training set for the learning process of an artificial neural network which, once correctly trained, can be used to forecast the engine outputs as a function of the design parameters during a GA optimization performing a so-called virtual optimization. In the current work, a numerical methodology for the multi-objective virtual optimization of the combustion of an automotive DI Diesel engine, which relies on artificial neural networks and genetic algorithms, was developed.

Discrete Event Systems based Design Patterns for Diagnosability Analysis of Automated Manufacturing Systems

The main goal of this thesis is to facilitate the process of industrial automated systems development applying formal methods to ensure the reliability of systems. A new formulation of distributed diagnosability problem in terms of Discrete Event Systems theory and automata framework is presented, which is then used to enforce the desired property of the system, rather then just verifying it. This approach tackles the state explosion problem with modeling patterns and new algorithms, aimed for verification of diagnosability property in the context of the distributed diagnosability problem. The concepts are validated with a newly developed software tool.

Target Tracking in UWB Multistatic Radars

Detection, localization and tracking of non-collaborative objects moving inside an area is of great interest to many surveillance applications. An ultra- wideband (UWB) multistatic radar is considered as a good infrastructure for such anti-intruder systems, due to the high range resolution provided by the UWB impulse-radio and the spatial diversity achieved with a multistatic configuration. Detection of targets, which are typically human beings, is a challenging task due to reflections from unwanted objects in the area, shadowing, antenna cross-talks, low transmit power, and the blind zones arised from intrinsic peculiarities of UWB multistatic radars. Hence, we propose more effective detection, localization, as well as clutter removal techniques for these systems. However, the majority of the thesis effort is devoted to the tracking phase, which is an essential part for improving the localization accuracy, predicting the target position and filling out the missed detections. Since UWB radars are not linear Gaussian systems, the widely used tracking filters, such as the Kalman filter, are not expected to provide a satisfactory performance. Thus, we propose the Bayesian filter as an appropriate candidate for UWB radars. In particular, we develop tracking algorithms based on particle filtering, which is the most common approximation of Bayesian filtering, for both single and multiple target scenarios. Also, we propose some effective detection and tracking algorithms based on image processing tools. We evaluate the performance of our proposed approaches by numerical simulations. Moreover, we provide experimental results by channel measurements for tracking a person walking in an indoor area, with the presence of a significant clutter. We discuss the existing practical issues and address them by proposing more robust algorithms.

On arc-routing problems

Das Basisproblem von Arc-Routing Problemen mit mehreren Fahrzeugen ist das Capacitated Arc-Routing Problem (CARP). Praktische Anwendungen des CARP sind z.B. in den Bereichen Müllabfuhr und Briefzustellung zu finden. Das Ziel ist es, einen kostenminimalen Tourenplan zu berechnen, bei dem alle erforderlichen Kanten bedient werden und gleichzeitig die Fahrzeugkapazität eingehalten wird. In der vorliegenden Arbeit wird ein Cut-First Branch-and-Price Second Verfahren entwickelt. In der ersten Phase werden Schnittebenen generiert, die dem Master Problem in der zweiten Phase hinzugefügt werden. Das Subproblem ist ein kürzeste Wege Problem mit Ressourcen und wird gelöst um neue Spalten für das Master Problem zu liefern. Ganzzahlige CARP Lösungen werden durch ein neues hierarchisches Branching-Schema garantiert. Umfassende Rechenstudien zeigen die Effektivität dieses Algorithmus. Kombinierte Standort- und Arc-Routing Probleme ermöglichen eine realistischere Modellierung von Zustellvarianten bei der Briefzustellung. In dieser Arbeit werden jeweils zwei mathematische Modelle für Park and Loop und Park and Loop with Curbline vorgestellt. Die Modelle für das jeweilige Problem unterscheiden sich darin, wie zulässige Transfer Routen modelliert werden. Während der erste Modelltyp Subtour-Eliminationsbedingungen verwendet, werden bei dem zweiten Modelltyp Flussvariablen und Flusserhaltungsbedingungen eingesetzt. Die Rechenstudie zeigt, dass ein MIP-Solver den zweiten Modelltyp oft in kürzerer Rechenzeit lösen kann oder bei Erreichen des Zeitlimits bessere Zielfunktionswerte liefert.

Solving the logically constrained multiple choice multiple knapsack problem: A real case

In questa tesi viene analizzato un problema di ottimizzazione proposto da alcuni esercizi commerciali che hanno la necessita` di selezionare e disporre i propri ar- ticoli in negozio. Il problema nasce dall’esigenza di massimizzare il profitto com- plessivo atteso dei prodotti in esposizione, trovando per ognuno una locazione sugli scaffali. I prodotti sono suddivisi in dipartimenti, dai quali solo un ele- mento deve essere selezionato ed esposto. In oltre si prevede la possibilita` di esprimere vincoli sulla locazione e compatibilita` dei prodotti. Il problema risul- tante `e una generalizzazione dei gia` noti Multiple-Choice Knapsack Problem e Multiple Knapsack Problem. Dopo una ricerca esaustiva in letteratura si `e ev- into che questo problema non `e ancora stato studiato. Si `e quindi provveduto a formalizzare il problema mediante un modello di programmazione lineare intera. Si propone un algoritmo esatto per la risoluzione del problema basato su column generation e branch and price. Sono stati formulati quattro modelli differenti per la risoluzione del pricing problem su cui si basa il column generation, per individuare quale sia il piu` efficiente. Tre dei quattro modelli proposti hanno performance comparabili, mentre l’ultimo si `e rivelato piu` inefficiente. Dai risul- tati ottenuti si evince che il metodo risolutivo proposto `e adatto a istanze di dimensione medio-bassa.

Computation of discrete cosine transform using Clenshaw's recurence formula

Clenshaw’s recurrenee formula is used to derive recursive algorithms for the discrete cosine transform @CT) and the inverse discrete cosine transform (IDCT). The recursive DCT algorithm presented here requires one fewer delay element per coefficient and one fewer multiply operation per coeflident compared with two recently proposed methods. Clenshaw’s recurrence formula provides a unified development for the recursive DCT and IDCT algorithms. The M v e al gorithms apply to arbitrary lengtb algorithms and are appropriate for VLSI implementation.