Emerging low power, embedded, wireless sensor devices are useful for wide range of applications, yet have very limited processing storage and especially energy resources. Sensor networks have a wide variety of applications in medical monitoring, environmental sensing and military surveillance. Due to the large number of sensor nodes that may be deployed and the required long system lifetimes, replacing the battery is not an option. Sensor systems must utilize the minimal possible energy while operating over a wide range of operating scenarios. The most of the efforts in the energy management in sensor networks have concentrated on minimizing energy consumption in the communication subsystem. Some researchers have also dealt with the issue of minimizing the energy in computing subsystem of a sensor network node. Some proposals using energy aware software have also been made. Relatively little work has been done on compiler controlled energy management in sensor networks. In this thesis, we present our investigations on how compiler techniques can be used to minimize CPU energy consumption in sensor network nodes. One effectively used energy management technique in general purpose processors, is dynamic voltage scaling. In this thesis we implement and evaluate a compiler assisted DVS algorithm and show its usefulness for a small sensor node processor. We were able to achieve an energy saving of 29% with a little performance slowdown. Scratchpad memories have been widely used for improving performance. In this thesis we show that if the scratchpad size for the system is chosen carefully, then large energy savings can be achieved by using a compiler assisted scratchpad allocation policy. With a small size of 512 byte scratchpad memory we were able to achieve 50% of energy savings. We also studied the behavior of dynamic voltage scaling in presence of scratchpad memory. Our results show that in presence of scratchpad memory less opportunities are found for applying dynamic voltage scaling techniques. The sensor network community lacks a comprehensive benchmark suite, for our study we also implemented a set of applications, representative of computational workload on sensor network nodes. The techniques studied in this thesis can easily be integrated with existing energy management techniques in sensor networks, yielding in additional energy savings.

Mobile Ad Hoc Networks (MANETs) are a class of infrastructure less network architecture which are formed by a collection of mobile nodes that communicate with each other using multi-hop wireless links. They eliminate the need for central management, hence each node must operate cooperatively to successfully maintain the network. Each node performs as a source, a sink and a router. Future applications of MANETs are expected to be based on all-IP architecture, carrying a multitude of real-time multimedia applications such as voice, video and data. It would be necessary for MANETs to have an efficient routing and quality of service (QoS) mechanism to support diverse applications. This thesis proposes a set of cooperative protocols that provide support for QoS routing. The first is the on-demand, Non-Disjoint Multiple Routes Discovery protocol (NDMRD). NDMRD allows the establishment of multiple paths with node non-disjoint between source and destination node. It returns to the source a collection of routes with the QoS parameters. The second part of the protocol is the Node State Monitoring protocol for the purpose of monitoring, acquisition, dissemination and accumulation of QoS route information. The third part of the protocol implements the QoS route selection based on a Genetic Algorithm. The GA is implemented online with predetermined initial population and weighted-sum fitness function which operates simultaneously on the node bandwidth, media access delay, end to end delay and the node connectivity index (NCI). The term node connectivity index is a numerical value designed to predict comparatively the longest time a node-pair might be connected wirelessly.

No description available.

Prostate cancer (PCa) is the most common non-skin malignancy of men in developed countries. In spite of treatment with curative intent up to 30-40% of patients have disease recurrence after treatment, resulting from any combination of lymphatic, hematogenous, or contiguous local spread. The concept of early detection of PCa offer benefits in terms of reduced mortality, but at the cost of over-diagnosis and overtreatment of indolent disease. This is largely due to the random nature of conventional biopsies, with a risk of missing significant cancer and randomly hitting indolent disease. In the present thesis, diagnostic performance of MRI DWI and 11C Acetate PET/CT lymph node staging of intermediate and high risk PCa, was investigated, and additionally, predictive factors of regional lymph node metastases were evaluated. Further, additional value of targeted biopsies to conventional biopsies, for detection of clinically significant PCa, was investigated. In paper one and two, 53 and 40 patients with predominantly high risk PCa underwent 11C Acetate PET/CT and 3T MRI DWI, respectively, for lymph node staging, before extended pelvic lymph node dissection (ePLND). The sensitivity and specificity for PET/CT was 38% and 96% respectively. The sensitivity and specificity for MRI DWI was 55% and 90% respectively. In paper three, 53 patients with newly diagnosed PCa were included. All patients underwent multi-parametric MRI, followed by two cognitive targeted biopsies. Five more clinically significant cancers were detected by adding targeted biopsies to conventional biopsies. In paper four the value of quantitative and qualitative MRI DWI and 11C Acetate PET/CT parameters, alone and in combination, in predicting regional lymph node metastases were examined. ADCmean in lymph nodes and T-stage on MRI were independent predictors of lymph node metastases in multiple logistic regression analysis. In conclusion the specificity of diffusion weighted MRI and 11C Acetate PET/CT for lymph node staging was high, although the sensitivity was low. Predictive factors of regional lymph node metastases could be retrieved from diffusion weighted MRI and 11C Acetate PET/CT. By combining targeted biopsies with conventional biopsies the detection rate of clinically significant PCa could be increased.

A number of attempts have been made to facilitate agricultural trade liberalisation over the last decades. In spite of these efforts, trade liberalisation of agricultural and food processed goods has been modest. It is argued that this lack of trade liberalisation is explained by the existence of governments that are politically biased in the sense that they place anti-trade policies in order to favour powerful sectors in the economy. While there exists some evidence supporting this argument, it is difficult to assess how these biases influence agricultural trade patterns because existing quantitative modelling approaches do not normally consider simultaneously key aspects that characterise the food industry such as intra-industry trade and the existence of intermediaries in the supply chain with significant market power, among others. The objective of this thesis is to offer an alternative theoretical model that has the potential to accommodate these key aspects and corresponds to an international trade network model that extends the framework developed by Goyal and Joshi (2006). The model was solved by means of simulations and the results revealed that policy biased indeed can prevent trade liberalisation of agricultural and food processed goods. However, other factors that apparently have not been reported so far and that are related to the market power exercised by intermediaries were identified. They correspond to the position of a country in the trade network (i.e. a country occupying a central position in the network is less likely to support trade liberalisation independently of any policy bias), the possibility that global free trade is an unlikely outcome, and the possibility that the world is trapped in an inefficient international trade network. The results also revealed that the adoption of compensatory lump sum payments across countries (i.e. inter-node transfers) or across sectors within a country (i.e. intra-node transfers) could be used a potential tools to achieve global free trade in agriculture as they can compensate losers from trade by gainers achieving, as a consequence, Pareto improving outcomes.

Cette thèse se centre sur les discordances dans l’ellipse périphérique (RNR) et propose une analyse basée sur l’identité de lexème entre le matériel manquant et le matériel périphérique. Les analyses précédentes accordent de l’importance au syncrétisme, ou identité phonologique (Pullum & Zwicky (1986)). Dans cette thèse, nous contestons cette hypothèse. Nous avons analysé 5 types de discordance dans l’ellipse périphérique: discordances de polarité, de possessifs, de prépositions, de voix et de formes verbales. Nos études de corpus sur Internet, sur Frtenten 2012 (1.6 milliard de mots) (Baroni et al. (2009)) et sur le English Web 2013 (19 milliard mots) montrent l’existence des discordances dans l’ellipse périphérique en français et en anglais. Les discordances sont assez nombreuses même dans des écrits soignés. Dans tous les cas, les discordances sont résolues par la forme qui correspond au second conjoint. Les résultats des expériences de jugements d’acceptabilité et de mouvements oculaires permettent d’intégrer les discordances dans la grammaire. Les résultats sont compatibles avec les analyses qui postulent l’identité sémantique entre le matériel manquant et l’antécédent pour l’ellipse. Nous proposons une analyse formelle en HPSG.Nous comparons les résultats obtenus avec les cas de coordination lexicale. Nous montrons que l’accord de proximité s’applique (Villavicencio et al. (2005)) et nous proposons une analyse HPSG pour la coordination de verbes et de prépositions. / This thesis focuses on mismatches in peripheral ellipsis (RNR) and proposes an analysis based on lexeme identity between the missing material and the peripheral material. Previous analyses put emphasis on syncretism, or phonological identity (Pullum & Zwicky (1986)). In this thesis, we challenge this hypothesis. We analyzed 5 types of mismatches in peripheral ellipsis: polarity mismatch, possessive mismatch, voice mismatch and verbal form mismatch. Our corpus studies on the Internet, on Frtenten 2012 (1.6 billion words) (Baroni et al. (2009)) and on English Web 2013 (19 billion words) shows the existence of mismatches in peripheral ellipsis in French and English. Mismatches are quite numerous even in careful writings. In all cases, the mismatches are resolved by the form that corresponds to the second conjunct. The results of acceptability judgment tests and eye tracking experiments allow the integration of these mismatches into the grammar. The results are compatible with analyses postulating semantic identity between the missing material and the antecedent for ellipsis. We formalize peripheral ellipsis with mismatch within HPSG.We finally compare our results with lexical coordination. We show that it obeys closest conjunct agreement (Villavicencio et al (2005)) and propose a HPSG analysis for coordination of verbs and prepositions.

In this thesis, we consider wireless ad hoc and sensor networks where energy matters. Indeed, sensor nodes are characterized by a small size, a low cost, an advanced communication technology, but also a limited amount of energy. This energy can be very expensive, difficult or even impossible to renew. Energy efficient strategies are required in such networks to maximize network lifetime. We distinguish four categories of strategies: 1. Energy efficient routing, 2. Node activity scheduling, 3. Topology control by tuning node transmission power and 4. Reduction of the volume of information transferred. Our contribution deals with energy efficient routing and node activity scheduling. For energy efficient routing, the idea consists in reducing the energy spent in the transmission of a packet from its source to its destination, while avoiding nodes with low residual energy. The solution we propose, called EOLSR, is based on the link state OLSR routing protocol. We show by simulation that this solution outperforms the solution that selects routes minimizing the end-to-end energy consumption, as well as the solution that builds routes based on node residual energy. We then show how we can improve the benefit of energy efficient routing using cross layering. Informa- tion provided by the MAC layer improves the reactivity of the routing protocol and the robustness of routes. Moreover, taking into account the specificities of some applications like data gathering allows the routing protocol to reduce its overhead by maintaining routes only to the sink nodes. Concerning node activity scheduling, since the sleep state is the least power consuming state, our aim is to schedule node state between sleeping and active to minimize energy consumption while ensuring network and application functionalities. We propose a solution, called SERENA, based on node coloring. The idea is to assign a color to each node, while using a small number of colors and ensuring that two nodes with the same color can transmit without interfering. This color is mapped into a slot in which the node can transmit its messages. Consequently, each node is awake during its slot and the slots granted to its one-hop neighbors. It sleeps the remaining time. We show how this algorithm can adapt to different application requirements: broadcast, immediate acknowledgement of unicast transmissions... The impact of each additional requirement is evaluated by simulation. An originality of this work lies in taking into account real wireless propagation conditions. Color conflicts are then possible. A cross-layering approach with the MAC layer is used to solve these conflicts. We also show how cross-layering with the application layer can improve the coloring per- formance for data gathering applications. This work has been done for the ANR OCARI project whose aim is to design and implement a wireless sensor network for applications in harsh environments such as power plants and war- ships. The network layer including SERENA and EOLSR has been specified and is now under implementation.

The Steiner Tree problem has appeared in the Karp's list of the first 21 NP-hard problems and is well known as one of the most fundamental problems in Network Design area. We study the Node-Weighted version of the Prize Collecting Steiner Tree problem. In this problem, we are given a simple graph with a cost and penalty value associated with each node. Our goal is to find a subtree T of the graph minimizing the cost of the nodes in T plus penalty of the nodes not in T. By a reduction from set cover problem it can be easily shown that the problem cannot be approximated in polynomial time within factor of (1-o(1))ln n unless NP has quasi-polynomial time algorithms, where n is the number of vertices of the graph. Moss and Rabani claimed an O(log n)-approximation algorithm for the problem using a Primal-Dual approach in their STOC'01 paper \cite{moss2001}. We show that their algorithm is incorrect by providing a counter example in which there is an O(n) gap between the dual solution constructed by their algorithm and the optimal solution. Further, evidence is given that their algorithm probably does not have a simple fix. We propose a new algorithm which is more involved and introduces novel ideas in primal dual approach for network design problems. Also, our algorithm is a Lagrangian Multiplier Preserving algorithm and we show how this property can be utilized to design an O(log n)-approximation algorithm for the Node-Weighted Quota Steiner Tree problem using the Lagrangian Relaxation method. We also show an application of the Node Weighted Quota Steiner Tree problem in designing algorithm with better approximation factor for Technology Diffusion problem, a problem proposed by Goldberg and Liu in \cite{goldberg2012} (SODA 2013). In Technology Diffusion, we are given a graph G and a threshold θ(v) associated with each vertex v and we are seeking a set of initial nodes called the seed set. Technology Diffusion is a dynamic process defined over time in which each vertex is either active or inactive. The vertices in the seed set are initially activated and each other vertex v gets activated whenever there are at least θ(v) active nodes connected to v through other active nodes. The Technology Diffusion problem asks to find the minimum seed set activating all nodes. Goldberg and Liu gave an O(rllog n)-approximation algorithm for the problem where r and l are the diameter of G and the number of distinct threshold values, respectively. We improve the approximation factor to O(min{r,l}log n) by establishing a close connection between the problem and the Node Weighted Quota Steiner Tree problem.

With the advent of the modern technological age, a plethora of electronic tools and devices are available in numbers as never before. While beneficial and ex-ceedingly useful, these electronic devices require users to operate them. When designing systems capable of observing and acting upon an environment, the number of devices can become unmanageable. Previously, middleware sys-tems were designed for large-scale computational systems. However, by apply-ing similar concepts and distributing logic to autonomous agents residing on the devices, a new paradigm in distributed systems research on lightweight de-vices is conceivable. Therefore, this research focuses upon the development of a lightweight middleware that can reside on small devices enabling the capabil-ity for these devices to act autonomously. In this research, analyses determined the most advantageous methods for solving this problem. Defining a set of requirements for the necessary middle-ware as well as assumptions for the environment and system in which it would operate achieved a proper research focus. By utilizing concepts already in ex-istence such as peer-to-peer networking and distributed hash tables, devices in this system could communicate effectively and efficiently. Furthermore, creat-ing custom algorithms for communicating with other devices, and collaborating on task assignments achieved an approach to solving the consensus problem in real time. The resulting middleware solution allowed a demonstration to prove the effi-cacy. Using three devices capable of observing the environment and acting up-on it, two tests highlighted the capabilities of the consensus-finding mechanism as well as the ability of the devices to respond to changes in the environment autonomously.

This thesis studies advection modeling for heat transfer and fluid flow problems using a new Non--Inverted Skew Upwind Scheme (called NISUS). Variants of the new scheme are formulated and developed with 8-noded hexahedral elements using the Finite Element Method (FEM)and rectangular elements based on a Finite Volume Method (FVM). A new method of mass weighting to predict convective fluxes of each scalar from the nodal point values is developed. Due to an explicit representation in terms of nodal variables, local inversion of the upwind coefficient matrix is not needed. Also, this thesis evaluates two variants of the new scheme (i.e., 3-node / 3-point and 4-node / 8-point formulations) within a 3--D FEM and a third variant within a 2--D FVM. The 3--D FEM variants are applied to a variety of test problems involving the transport of a scalar variable, while the 2--D FVM variant is applied to fluid flow problems including natural convection in an enclosure and micro--channel flow simulations. The promising performance of NISUS, as compared with exact and previous solutions, is demonstrated both in terms of accuracy and stability. Furthermore, a new data storage format called Compressed Banded Data (CBD) is developed for sparse banded matrices generated by the control volume finite element method (CVFEM). The platform of the new CBD structure permits dynamic switching between various solvers, without any procedural change in the implementation of existing simulation software. The performance of different Krylov techniques with an ILU(0) preconditioner is observed and compared in three test problems with a direct solver. / October 2006