Range Assignment for Biconnectivity and k-Edge Connectivity in Wireless Ad Hoc Networks

Depending on whether bidirectional links or unidirectional links are used for communications, the network topology under a given range assignment is either an undirected graph referred to as the bidirectional topology, or a directed graph referred to as the unidirectional topology. The Min-Power Bidirectional (resp., Unidirectional) k-Node Connectivity problem seeks a range assignment of minimum total power subject to the constraint that the produced bidirectional (resp. unidirectional) topology is k-vertex connected. Similarly, the Min-Power Bidirectional (resp., Unidirectional) k-Edge Connectivity problem seeks a range assignment of minimum total power subject to the constraint the produced bidirectional (resp., unidirectional) topology is k-edge connected. The Min-Power Bidirectional Biconnectivity problem and the Min-Power Bidirectional Edge-Biconnectivity problem have been studied by Lloyd et al. [23]. They show that range assignment based the approximation algorithm of Khuller and Raghavachari [18], which we refer to as Algorithm KR, has an approximation ratio of at most 2(2 – 2/n)(2 + 1/n) for Min-Power Bidirectional Biconnectivity, and range assignment based on the approximation algorithm of Khuller and Vishkin [19], which we refer to as Algorithm KV, has an approximation ratio of at most 8(1 – 1/n) for Min-Power Bidirectional Edge-Biconnectivity. In this paper, we first establish the NP-hardness of Min-Power Bidirectional (Edge-) Biconnectivity. Then we show that Algorithm KR has an approximation ratio of at most 4 for both Min-Power Bidirectional Biconnectivity and Min-Power Unidirectional Biconnectivity, and Algorithm KV has an approximation ratio of at most 2k for both Min-Power Bidirectional k-Edge Connectivity and Min-Power Unidirectional k-Edge Connectivity. We also propose a new simple constant-approximation algorithm for both Min-Power Bidirectional Biconnectivity and Min-Power Unidirectional Biconnectivity. This new algorithm applies only to Euclidean instances, but is best suited for distributed implementation. A preliminary version of this work appeared in the proceedings of the 2nd International Conference on AD-HOC Network and Wireless (Adhoc-Now 2003). Research performed in part while visiting the Max-Plank-Institut fur Informatik. Gruia Calinescu is an Assistant Professor of Computer Science at the Illinois Institute of Technology since 2000. He held postdoc or visiting researcher positions at DIMACS, University of Waterloo, and Max-Plank Institut fur Informatik. Gruia has a Diploma from University of Bucharest and a Ph.D. from Georgia Insitute of Technology. His research interests are in the area of algorithms. Peng-Jun Wan has joined the Computer Science Department at Illinois Institute of Technology in 1997 and has been an Associate Professor since 2004. He received his Ph.D. in Computer Science from University of Minnesota in 1997, M.S. in Operations Research and Control Theory from Chinese Academy of Science in 1993, and B.S. in Applied Mathematics from Tsinghua University in 1990. His research interests include optical networks and wireless networks.     

Synthesis of probabilistic models for quality-of-service software engineering

An increasingly used method for the engineering of software systems with strict quality-of-service (QoS) requirements involves the synthesis and verification of probabilistic models for many alternative architectures and instantiations of system parameters. Using manual trial-and-error or simple heuristics for this task often produces suboptimal models, while the exhaustive synthesis of all possible models is typically intractable. The EvoChecker search-based software engineering approach presented in our paper addresses these limitations by employing evolutionary algorithms to automate the model synthesis process and to significantly improve its outcome. EvoChecker can be used to synthesise the Pareto-optimal set of probabilistic models associated with the QoS requirements of a system under design, and to support the selection of a suitable system architecture and configuration. EvoChecker can also be used at runtime, to drive the efficient reconfiguration of a self-adaptive software system. We evaluate EvoChecker on several variants of three systems from different application domains, and show its effectiveness and applicability.     

The uncertainty interaction problem in self-adaptive systems

Software and Systems Modeling - The problem of mitigating uncertainty in self-adaptation has driven much of the research proposed in the area of software engineering for self-adaptive systems in...     

Microwave-Assisted Batch Extraction of Polyphenols from Sea Buckthorn Leaves

Extraction of polyphenols from sea buckthorn leaves using microwave-assisted extraction (MAE) is described. The influence of different parameters on the extraction process (reactor type, stirring rate, extraction time, temperature, ethanol/water ratio) was studied. The polyphenolic extracts were analyzed in order to determine the total phenolic content (TPC) either by the Folin–Ciocalteu method or by differential pulse voltammetry (DPV), and the concentration of the main polyphenolic compounds by high-performance liquid chromatography (HPLC). The specific microwave energy was also determined. MAE resulted in a shorter extraction time (7.5 versus 30 min for the conventional method). The best results for MAE were obtained at a temperature of 90°C, using a solvent/plant ratio of 20/1 and 50% ethanol in the extraction solvent. The highest values of antioxidant capacity were obtained for polyphenolic extracts resulted from microwave extraction.     

Interference-aware broadcast scheduling in wireless networks

In this paper, we study the Interference-Aware Broadcast Scheduling problem, where all nodes in the Euclidean plane have a transmission range and an interference range equal to r and α r for α ? 1, respectively. Minimizing latency is known to be NP-Hard even when α = 1. The network radius D, the maximum graph distance from the source to any node, is also known to be a lower bound.We formulate the problem as integer programs (IP) and optimally solve moderate-size instances. We also propose six variations of heuristics, which require no pre-processing of inputs, based on the number of receivers gained by each additional simultaneous transmitting node. The experimental results show that the best heuristics give solutions that exceed the optimal solutions by only 13–20%. Further, an O(αD) schedule is proven to exist yielding an O(α) approximation algorithm.     

SO2 and NOx removal by electron beam and electrical discharge induced non-thermal plasmas

An installation containing a DC negative corona discharge reactor, a pulse corona discharge reactor and a combined electron beam and microwave induced plasma reactor is presented. SO₂ is removed up to 42% through spontaneous reaction with ammonia without electron beam or microwave irradiation at the temperature below 70 °C. For the same removal efficiency of 98% for SO₂ and 80% for NO_x at separate EB irradiation of 40 kGy, the required absorbed dose is about two times smaller for simultaneous electron beam and microwave irradiation. The SO₂ removal efficiency of simultaneous DC or positive discharge and microwave discharge is higher than separate DC, pulse and MW discharge. Also, the applied voltage level at which the removal efficiency reaches the maximum value is less than for the separate application of DC or pulse discharge. The NO_x removal efficiency of DC or pulse discharge suffers little change by additional use of the microwave energy.     

Selecting Forwarding Neighbors in Wireless Ad Hoc Networks

Broadcasting is a fundamental operation which is frequent in wireless ad hoc networks. A simple broadcasting mechanism, known as flooding, is to let every node retransmit the message to all its 1-hop neighbors when receiving the first copy of the message. Despite its simplicity, flooding is very inefficient and can result in high redundancy, contention, and collision. One approach to reducing the redundancy is to let each node forward the message only to a small subset of 1-hop neighbors that cover all of the node's 2-hop neighbors. In this paper we propose two practical heuristics for selecting the minimum number of forwarding neighbors: an O(nlogn) time algorithm that selects at most 6 times more forwarding neighbors than the optimum, and an O(nlog² n) time algorithm with an improved approximation ratio of 3, where n is the number of 1- and 2-hop neighbors. The best previously known algorithm, due to Bronnimann and Goodrich [2], guarantees O(1) approximation in O(n ³ logn) time.     

Comparing the impact of different rescheduling strategies on the entropic-related complexity of manufacturing systems

The primary objective of this paper is to compare five rescheduling strategies according to their effectiveness in reducing entropic-related complexity arising from machine breakdowns in manufacturing systems. Entropic-related complexity is the expected amount of information required to describe the state of the system. Previous case studies carried out by the authors have guided computer simulations, which were carried out in Arena 5.0 in combination with MS Excel. Simulation performance is measured by: (1) entropic-related complexity measures, which quantify: (a) the complexity associated with the information content of schedules, and (b) the complexity associated with the variations between schedules; and (2) mean flow time. The results highlight two main points: (a) the importance of reducing unbalanced machine workloads by using the least utilised machine to process the jobs affected by machine breakdowns, and (b) low disruption strategies are effective at reducing entropic-related complexity; this means that applying rescheduling strategies in order to manage complexity can be beneficial up to a point, which, in low disruption strategies, is included in their threshold conditions. The contribution of this paper is two-fold. First, it extends the application of entropic-related complexity to every schedule generated through rescheduling, whereas previous work only applied it to the original schedule. Second, recommendations are proposed to schedulers for improving their rescheduling practice in the face of machine breakdowns. Those recommendations vary according to the manufacturing organisations’ product type and scheduling objectives. Further work includes: (a) preparing a detailed workbook to measure entropic-related complexity at shop-floor level; and (b) extending the analysis to other types of disturbances, such as customer changes.     

Model-driven design space exploration for multi-robot systems in simulation

Multi-robot systems are increasingly deployed to provide services and accomplish missions whose complexity or cost is too high for a single robot to achieve on its own. Although multi-robot systems offer increased reliability via redundancy and enable the execution of more challenging missions, engineering these systems is very complex. This complexity affects not only the architecture modelling of the robotic team but also the modelling and analysis of the collaborative intelligence enabling the team to complete its mission. Existing approaches for the development of multi-robot applications do not provide a systematic mechanism for capturing these aspects and assessing the robustness of multi-robot systems. We address this gap by introducing ATLAS, a novel model-driven approach supporting the systematic design space exploration and robustness analysis of multi-robot systems in simulation. The ATLAS domain-specific language enables modelling the architecture of the robotic team and its mission and facilitates the specification of the team’s intelligence. We evaluate ATLAS and demonstrate its effectiveness in three simulated case studies: a healthcare Turtlebot-based mission and two unmanned underwater vehicle missions developed using the Gazebo/ROS and MOOS-IvP robotic platforms, respectively.

     

Maximum Series-Parallel Subgraph

Consider the NP-hard problem of, given a simple graph?G, to find a series-parallel subgraph of?G with the maximum number of edges. The algorithm that, given a connected graph?G, outputs a spanning tree of?G, is a $\frac{1}{2}$ -approximation. Indeed, if n is the number of vertices in G, any spanning tree in G has?n?1 edges and any series-parallel graph on?n vertices has at most?2n?3 edges. We present a $\frac{7}{12}$ -approximation for this problem and results showing the limits of our approach.