Dynamic Routing in Translucent WDM Optical Networks

Translucent WDM optical networks use sparse placement of regenerators to overcome the impairments and wavelength contention introduced by fully transparent networks, and achieve a performance close to fully opaque networks with much less cost. Our previous study proved the feasibility of translucent networks using sparse regeneration technique. We addressed the placement of regenerators based on static schemes allowing only fixed number of regenerators at fixed locations. This paper furthers the study by proposing a suite of dynamical routing schemes. Dynamic allocation, advertisement and discovery of regeneration resources are proposed to support sharing transmitters and receivers between regeneration and access functions. This study follows the current trend in optical networking industry by utilizing extension of IP control protocols. Dynamic routing algorithms, aware of current regeneration resources and link states, are designed to smartly route the connection requests under quality constraints. A hierarchical network model, supported by the MPLS-based control plane, is also proposed to provide scalability. Experiments show that network performance is improved without placement of extra regenerators.

SMAC multi-hop mesh routing protocol using IEEE 802.15.4

This paper discusses some aspects related to Wireless Sensor Networks over the IEEE 802.15.4 standard, and proposes, for the very first time, a mesh network topology with geographic routing integrated to the open Freescale protocol (SMAC - Simple Medium Access Control). For this is proposed the SMAC routing protocol. Before this work the SMAC protocol was suitable to perform one hop communications only. However, with the developed mechanisms, it is possible to use multi-hop communication. Performance results from the implemented protocol are presented and analyzed in order to define important requirements for wireless sensor networks, such as robustness, self-healing property and low latency. (c) 2011 Elsevier Ltd. All rights reserved.

Re-Os isotope and highly siderophile element systematics of the Parana continental flood basalts (Brazil)

Basalts of the Parana continental flood basalt (PCFB) province erupted through dominantly Proterozoic continental crust during the Cretaceous. In order to examine the mantle source(s) of this major flood basalt province, we studied Os, Sr, Nd, and Pb isotope systematics, and highly siderophile element (HSE) abundances in tholeiitic basalts that were carefully chosen to show the minimal effects of crustal contamination. These basalts define a precise Re-Os isochron with an age of 131.6 +/- 2.3 Ma and an initial Os-187/Os-188 of 0.1295 +/- 0.0018 (gamma Os-187 = +2.7 +/- 1.4). This initial Os isotopic composition is considerably more radiogenic than estimates of the contemporary Depleted Mantle (DM). The fact that the Re-Os data define a well constrained isochron with an age similar to Ar-40/Ar-39 age determinations, despite generally low Os concentrations, is consistent with closed-system behavior for the HSE. Neodymium, Sr, and Pb isotopic data suggest that the mantle source of the basalts had been variably hybridized by melts derived from enriched mantle components. To account for the combined Os, Nd, Sr, and Pb isotopic characteristics of these rocks, we propose that the primary melts formed from metasomatized asthenospheric mantle (represented by arc-mantle peridotite) that underwent mixing with two enriched components, EM-I and EM-II. The different enriched components are reflected in minor isotopic differences between basalts from southern and northern portions of the province. The Tristan da Cunha hotspot has been previously suggested to be the cause of the Parana continental flood basalt magmatism. However, present-day Tristan da Cunha lavas have much higher Os-187/Os-188 isotopic compositions than the source of the PCFB. These data, together with other isotopic and elemental data, preclude making a definitive linkage between the Tristan plume and the PCFB. (C) 2012 Elsevier B.V. All rights reserved.

Column generation for a multitrip vehicle routing problem with time windows, driver work hours, and heterogeneous fleet

This study addresses a vehicle routing problem with time windows, accessibility restrictions on customers, and a fleet that is heterogeneous with regard to capacity and average speed. A vehicle can performmultiple routes per day, all starting and ending at a single depot, and it is assigned to a single driverwhose totalwork hours are limited.Acolumn generation algorithmis proposed.The column generation pricing subproblem requires a specific elementary shortest path problem with resource constraints algorithm to address the possibility for each vehicle performingmultiple routes per day and to address the need to set the workday’s start time within the planning horizon. A constructive heuristic and a metaheuristic based on tabu search are also developed to find good solutions.

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.

Una rassegna di protocolli di routing per reti radio cognitive ad hoc

Questa tesi si propone di presentare e classificare per caratteristiche simili i protocolli di routing che ad oggi sono utilizzati nelle Cognitive Radio Ad Hoc Networks. Pertanto dapprima nel Capitolo 1 si introdurranno le radio cognitive con i concetti che sono alla base di questa tecnologia e le principali motivazioni che hanno portato alla loro nascita e poi al loro sviluppo. Nel Capitolo 2 si parlerà delle cognitive networks o meglio delle cognitive radio networks, e delle loro peculiarità. Nel terzo e nel quarto capitolo si affronteranno le CRAHNs e in particolare quali sono le sfide a cui devono far fronte i protocolli di routing che operano su di essa, partendo dall'esaminare quali sono le differenze che distinguono questa tipologia di rete da una classica rete wireless ad hoc con nodi in grado di muoversi nello spazio (una MANET). Infine nell'ultimo capitolo si cercherà di classificare i protocolli in base ad alcune loro caratteristiche, vedendo poi più nel dettaglio alcuni tra i protocolli più usati.

Enhanced Mixed Integer Programming Techniques and Routing Problems

Mixed integer programming is up today one of the most widely used techniques for dealing with hard optimization problems. On the one side, many practical optimization problems arising from real-world applications (such as, e.g., scheduling, project planning, transportation, telecommunications, economics and finance, timetabling, etc) can be easily and effectively formulated as Mixed Integer linear Programs (MIPs). On the other hand, 50 and more years of intensive research has dramatically improved on the capability of the current generation of MIP solvers to tackle hard problems in practice. However, many questions are still open and not fully understood, and the mixed integer programming community is still more than active in trying to answer some of these questions. As a consequence, a huge number of papers are continuously developed and new intriguing questions arise every year. When dealing with MIPs, we have to distinguish between two different scenarios. The first one happens when we are asked to handle a general MIP and we cannot assume any special structure for the given problem. In this case, a Linear Programming (LP) relaxation and some integrality requirements are all we have for tackling the problem, and we are ``forced" to use some general purpose techniques. The second one happens when mixed integer programming is used to address a somehow structured problem. In this context, polyhedral analysis and other theoretical and practical considerations are typically exploited to devise some special purpose techniques. This thesis tries to give some insights in both the above mentioned situations. The first part of the work is focused on general purpose cutting planes, which are probably the key ingredient behind the success of the current generation of MIP solvers. Chapter 1 presents a quick overview of the main ingredients of a branch-and-cut algorithm, while Chapter 2 recalls some results from the literature in the context of disjunctive cuts and their connections with Gomory mixed integer cuts. Chapter 3 presents a theoretical and computational investigation of disjunctive cuts. In particular, we analyze the connections between different normalization conditions (i.e., conditions to truncate the cone associated with disjunctive cutting planes) and other crucial aspects as cut rank, cut density and cut strength. We give a theoretical characterization of weak rays of the disjunctive cone that lead to dominated cuts, and propose a practical method to possibly strengthen those cuts arising from such weak extremal solution. Further, we point out how redundant constraints can affect the quality of the generated disjunctive cuts, and discuss possible ways to cope with them. Finally, Chapter 4 presents some preliminary ideas in the context of multiple-row cuts. Very recently, a series of papers have brought the attention to the possibility of generating cuts using more than one row of the simplex tableau at a time. Several interesting theoretical results have been presented in this direction, often revisiting and recalling other important results discovered more than 40 years ago. However, is not clear at all how these results can be exploited in practice. As stated, the chapter is a still work-in-progress and simply presents a possible way for generating two-row cuts from the simplex tableau arising from lattice-free triangles and some preliminary computational results. The second part of the thesis is instead focused on the heuristic and exact exploitation of integer programming techniques for hard combinatorial optimization problems in the context of routing applications. Chapters 5 and 6 present an integer linear programming local search algorithm for Vehicle Routing Problems (VRPs). The overall procedure follows a general destroy-and-repair paradigm (i.e., the current solution is first randomly destroyed and then repaired in the attempt of finding a new improved solution) where a class of exponential neighborhoods are iteratively explored by heuristically solving an integer programming formulation through a general purpose MIP solver. Chapters 7 and 8 deal with exact branch-and-cut methods. Chapter 7 presents an extended formulation for the Traveling Salesman Problem with Time Windows (TSPTW), a generalization of the well known TSP where each node must be visited within a given time window. The polyhedral approaches proposed for this problem in the literature typically follow the one which has been proven to be extremely effective in the classical TSP context. Here we present an overall (quite) general idea which is based on a relaxed discretization of time windows. Such an idea leads to a stronger formulation and to stronger valid inequalities which are then separated within the classical branch-and-cut framework. Finally, Chapter 8 addresses the branch-and-cut in the context of Generalized Minimum Spanning Tree Problems (GMSTPs) (i.e., a class of NP-hard generalizations of the classical minimum spanning tree problem). In this chapter, we show how some basic ideas (and, in particular, the usage of general purpose cutting planes) can be useful to improve on branch-and-cut methods proposed in the literature.

Dimensionamento di invasi per il controllo dei deflussi nei bacini urbanizzati

Urbanization is a continuing phenomenon in all the world. Grasslands, forests, etc. are being continually changed to residential, commercial and industrial complexes, roads and streets, and so on. One of the side effects of urbanization with which engineers and planners must deal with, is the increase of peak flows and volumes of runoff from rainfall events. As a result, the urban drainage and flood control systems must be designed to accommodate the peak flows from a variety of storms that may occur. Usually the peak flow, after development, is required not to exceed what would have occurred from the same storm under conditions existing prior to development. In order to do this it is necessary to design detention storage to hold back runoff and to release it downstream at controlled rates. In the first part of the work have been developed various simplified formulations that can be adopted for the design of stormwater detention facilities. In order to obtain a simplified hydrograph were adopted two approaches: the kinematic routing technique and the linear reservoir schematization. For the two approaches have been also obtained other two formulations depending if the IDF (intensity-duration-frequency) curve is described with two or three parameters. Other formulations have been developed taking into account if the outlet have a constant discharge or it depends on the water level in the pond. All these formulations can be easily applied when are known the characteristics of the drainage system and maximum discharge that these is in the outlet and has been defined a Return Period which characterize the IDF curve. In this way the volume of the detention pond can be calculated. In the second part of the work have been analyzed the design of detention ponds adopting continuous simulation models. The drainage systems adopted for the simulations, performed with SWMM5, are fictitious systems characterized by different sizes, and different shapes of the catchments and with a rainfall historical time series of 16 years recorded in Bologna. This approach suffers from the fact that continuous record of rainfall is often not available and when it is, the cost of such modelling can be very expensive, and that the majority of design practitioners are not prepared to use continuous long term modelling in the design of stormwater detention facilities. In the third part of the work have been analyzed statistical and stochastic methodologies in order to define the volume of the detention pond. In particular have been adopted the results of the long term simulation, performed with SWMM, to obtain the data to apply statistic and stochastic formulation. All these methodologies have been compared and correction coefficient have been proposed on the basis of the statistic and stochastic form. In this way engineers which have to design a detention pond can apply a simplified procedure appropriately corrected with the proposed coefficient.