Hybrid Methods for Resource Allocation and Scheduling Problems in Deterministic and Stochastic Environments

This work presents exact, hybrid algorithms for mixed resource Allocation and Scheduling problems; in general terms, those consist into assigning over time finite capacity resources to a set of precedence connected activities. The proposed methods have broad applicability, but are mainly motivated by applications in the field of Embedded System Design. In particular, high-performance embedded computing recently witnessed the shift from single CPU platforms with application-specific accelerators to programmable Multi Processor Systems-on-Chip (MPSoCs). Those allow higher flexibility, real time performance and low energy consumption, but the programmer must be able to effectively exploit the platform parallelism. This raises interest in the development of algorithmic techniques to be embedded in CAD tools; in particular, given a specific application and platform, the objective if to perform optimal allocation of hardware resources and to compute an execution schedule. On this regard, since embedded systems tend to run the same set of applications for their entire lifetime, off-line, exact optimization approaches are particularly appealing. Quite surprisingly, the use of exact algorithms has not been well investigated so far; this is in part motivated by the complexity of integrated allocation and scheduling, setting tough challenges for ``pure'' combinatorial methods. The use of hybrid CP/OR approaches presents the opportunity to exploit mutual advantages of different methods, while compensating for their weaknesses. In this work, we consider in first instance an Allocation and Scheduling problem over the Cell BE processor by Sony, IBM and Toshiba; we propose three different solution methods, leveraging decomposition, cut generation and heuristic guided search. Next, we face Allocation and Scheduling of so-called Conditional Task Graphs, explicitly accounting for branches with outcome not known at design time; we extend the CP scheduling framework to effectively deal with the introduced stochastic elements. Finally, we address Allocation and Scheduling with uncertain, bounded execution times, via conflict based tree search; we introduce a simple and flexible time model to take into account duration variability and provide an efficient conflict detection method. The proposed approaches achieve good results on practical size problem, thus demonstrating the use of exact approaches for system design is feasible. Furthermore, the developed techniques bring significant contributions to combinatorial optimization methods.

Performance Analysis and Improvements for the Future Aeronautical Mobile Airport Communications System (AeroMACS)

This thesis deals with the development of the upcoming aeronautical mobile airport communications system (AeroMACS) system. We analyzed the performance of AeroMACS and we investigated potential solutions for enhancing its performance. Since the most critical results correspond to the channel scenario having less diversity1, we tackled this problem investigating potential solutions for increasing the diversity of the system and therefore improving its performance. We accounted different forms of diversity as space diversity and time diversity. More specifically, space (antenna and cooperative) diversity and time diversity are analyzed as countermeasures for the harsh fading conditions that are typical of airport environments. Among the analyzed techniques, two novel concepts are introduced, namely unequal diversity coding and flexible packet level codes. The proposed techniques have been analyzed on a novel airport channel model, derived from a measurement campaign at the airport of Munich (Germany). The introduced techniques largely improve the performance of the conventional AeroMACS link; representing thus appealing solutions for the long term evolution of the system.

The photosynthetic bacterial reaction center in native and artificial envirnoments: effects on light-induced electron transfer

In this thesis we focussed on the characterization of the reaction center (RC) protein purified from the photosynthetic bacterium Rhodobacter sphaeroides. In particular, we discussed the effects of native and artificial environment on the light-induced electron transfer processes. The native environment consist of the inner antenna LH1 complex that copurifies with the RC forming the so called core complex, and the lipid phase tightly associated with it. In parallel, we analyzed the role of saccharidic glassy matrices on the interplay between electron transfer processes and internal protein dynamics. As a different artificial matrix, we incorporated the RC protein in a layer-by-layer structure with a twofold aim: to check the behaviour of the protein in such an unusual environment and to test the response of the system to herbicides. By examining the RC in its native environment, we found that the light-induced charge separated state P+QB - is markedly stabilized (by about 40 meV) in the core complex as compared to the RC-only system over a physiological pH range. We also verified that, as compared to the average composition of the membrane, the core complex copurifies with a tightly bound lipid complement of about 90 phospholipid molecules per RC, which is strongly enriched in cardiolipin. In parallel, a large ubiquinone pool was found in association with the core complex, giving rise to a quinone concentration about ten times larger than the average one in the membrane. Moreover, this quinone pool is fully functional, i.e. it is promptly available at the QB site during multiple turnover excitation of the RC. The latter two observations suggest important heterogeneities and anisotropies in the native membranes which can in principle account for the stabilization of the charge separated state in the core complex. The thermodynamic and kinetic parameters obtained in the RC-LH1 complex are very close to those measured in intact membranes, indicating that the electron transfer properties of the RC in vivo are essentially determined by its local environment. The studies performed by incorporating the RC into saccharidic matrices evidenced the relevance of solvent-protein interactions and dynamical coupling in determining the kinetics of electron transfer processes. The usual approach when studying the interplay between internal motions and protein function consists in freezing the degrees of freedom of the protein at cryogenic temperature. We proved that the “trehalose approach” offers distinct advantages with respect to this traditional methodology. We showed, in fact, that the RC conformational dynamics, coupled to specific electron transfer processes, can be modulated by varying the hydration level of the trehalose matrix at room temperature, thus allowing to disentangle solvent from temperature effects. The comparison between different saccharidic matrices has revealed that the structural and dynamical protein-matrix coupling depends strongly upon the sugar. The analyses performed in RCs embedded in polyelectrolyte multilayers (PEM) structures have shown that the electron transfer from QA - to QB, a conformationally gated process extremely sensitive to the RC environment, can be strongly modulated by the hydration level of the matrix, confirming analogous results obtained for this electron transfer reaction in sugar matrices. We found that PEM-RCs are a very stable system, particularly suitable to study the thermodynamics and kinetics of herbicide binding to the QB site. These features make PEM-RC structures quite promising in the development of herbicide biosensors. The studies discussed in the present thesis have shown that, although the effects on electron transfer induced by the native and artificial environments tested are markedly different, they can be described on the basis of a common kinetic model which takes into account the static conformational heterogeneity of the RC and the interconversion between conformational substates. Interestingly, the same distribution of rate constants (i.e. a Gamma distribution function) can describe charge recombination processes in solutions of purified RC, in RC-LH1 complexes, in wet and dry RC-PEM structures and in glassy saccharidic matrices over a wide range of hydration levels. In conclusion, the results obtained for RCs in different physico-chemical environments emphasize the relevance of the structure/dynamics solvent/protein coupling in determining the energetics and the kinetics of electron transfer processes in a membrane protein complex.

Management and routing algorithms for ad-hoc and sensor networks

Large scale wireless adhoc networks of computers, sensors, PDAs etc. (i.e. nodes) are revolutionizing connectivity and leading to a paradigm shift from centralized systems to highly distributed and dynamic environments. An example of adhoc networks are sensor networks, which are usually composed by small units able to sense and transmit to a sink elementary data which are successively processed by an external machine. Recent improvements in the memory and computational power of sensors, together with the reduction of energy consumptions, are rapidly changing the potential of such systems, moving the attention towards datacentric sensor networks. A plethora of routing and data management algorithms have been proposed for the network path discovery ranging from broadcasting/floodingbased approaches to those using global positioning systems (GPS). We studied WGrid, a novel decentralized infrastructure that organizes wireless devices in an adhoc manner, where each node has one or more virtual coordinates through which both message routing and data management occur without reliance on either flooding/broadcasting operations or GPS. The resulting adhoc network does not suffer from the deadend problem, which happens in geographicbased routing when a node is unable to locate a neighbor closer to the destination than itself. WGrid allow multidimensional data management capability since nodes' virtual coordinates can act as a distributed database without needing neither special implementation or reorganization. Any kind of data (both single and multidimensional) can be distributed, stored and managed. We will show how a location service can be easily implemented so that any search is reduced to a simple query, like for any other data type. WGrid has then been extended by adopting a replication methodology. We called the resulting algorithm WRGrid. Just like WGrid, WRGrid acts as a distributed database without needing neither special implementation nor reorganization and any kind of data can be distributed, stored and managed. We have evaluated the benefits of replication on data management, finding out, from experimental results, that it can halve the average number of hops in the network. The direct consequence of this fact are a significant improvement on energy consumption and a workload balancing among sensors (number of messages routed by each node). Finally, thanks to the replications, whose number can be arbitrarily chosen, the resulting sensor network can face sensors disconnections/connections, due to failures of sensors, without data loss. Another extension to {WGrid} is {W*Grid} which extends it by strongly improving network recovery performance from link and/or device failures that may happen due to crashes or battery exhaustion of devices or to temporary obstacles. W*Grid guarantees, by construction, at least two disjoint paths between each couple of nodes. This implies that the recovery in W*Grid occurs without broadcasting transmissions and guaranteeing robustness while drastically reducing the energy consumption. An extensive number of simulations shows the efficiency, robustness and traffic road of resulting networks under several scenarios of device density and of number of coordinates. Performance analysis have been compared to existent algorithms in order to validate the results.