In wireless sensor networks (WSNs) localization systems are required to provide position information of sensor nodes. Location information of sensor nodes with unknown physical coordinates is acquired with the help of...
详细信息
ISBN:
(纸本)9781479938803
In wireless sensor networks (WSNs) localization systems are required to provide position information of sensor nodes. Location information of sensor nodes with unknown physical coordinates is acquired with the help of beacons or anchors. Beacon placement is one of the prominent factors that shape the localization performance in sensor networks. Placing more beacons in a network is generally not a cost-effective idea. However, a carefully designed technique can increase the accuracy by placing a limited number of beacons. This paper presents an integerlinearprogramming(ILP) formulation of optimal beacon placement (OBP) and also prove that the OBP problem is NP-hard. Requirement based beacon placement algorithm is proposed to optimize number of beacons to cover the entire WSN. Simulation result shows that the proposed beacon placement scheme is effective in a sensor network with high node density.
Discrete tomography deals with problems of determining shape of a discrete object from a set of projections. In this paper, we deal with a fundamental problem in discreet tomography: reconstructing a discrete object i...
详细信息
Discrete tomography deals with problems of determining shape of a discrete object from a set of projections. In this paper, we deal with a fundamental problem in discreet tomography: reconstructing a discrete object in R-3 from its orthogonal projections, which we call three-dimensional discrete tomography. This problem has been mostly studied under the assumption that complete data of the projections are available. However, in practice, there might be missing data in the projections, which come from, e.g., the lack of precision in the measurements. In this paper, we consider the three-dimensional discrete tomography with missing data. Specifically, we consider the following three fundamental problems in discrete tomography: the consistency, counting, and uniqueness problems, and classify the computational complexities of these problems in terms of the length of one dimension. We also generalize these results to higher-dimensional discrete tomography, which has applications in operations research and statistics.
In this paper, we study the recently introduced Traveling Car Renter Problem. This latter is a generalization of the well-known traveling salesman problem, where a solution is a set of paths of different colors as wel...
详细信息
In this paper, we study the recently introduced Traveling Car Renter Problem. This latter is a generalization of the well-known traveling salesman problem, where a solution is a set of paths of different colors as well as an orientation of each path in such a way that the union forms a directed Hamiltonian circuit. Considering costs associated with all edges and all ordered pairs of nodes for each color, the cost of a solution is the sum of the costs of its colored oriented paths, the cost of these later being the sum of the edge costs plus the costs of the arcs from their destination to their origin. We also consider the Quota version of this problem where a weight is associated with every node and the circuit formed by a solution may not be Hamiltonian but must cover a subset of nodes whose sum of weights should be greater than or equal to a fixed value. We propose integer linear programming formulations for these problems. We also propose some valid inequalities for strengthening the models and we devise branch-and-cut algorithms for solving these formulations. The computational results show the efficiency of our formulations as we solve to optimality almost all the instances of the literature, and outperform by an order of magnitude all published approaches.
In this study the authors are interested in safety-critical real-time applications implemented on distributed architectures supporting the time-sensitive networking (TSN) standard. The on-going standardisation of TSN ...
详细信息
In this study the authors are interested in safety-critical real-time applications implemented on distributed architectures supporting the time-sensitive networking (TSN) standard. The on-going standardisation of TSN is an IEEE effort to bring deterministic real-time capabilities into the IEEE 802.1 Ethernet standard supporting safety-critical systems and guaranteed quality-of-service. TSN will support time-triggered (TT) communication based on schedule tables, audio-video-bridging (AVB) flows with bounded end-to-end latency as well as best-effort messages. The authors first present a survey of research related to the optimisation of distributed cyber-physical systems using real-time Ethernet for communication. Then, the authors formulate two novel optimisation problems related to the scheduling and routing of TT and AVB traffic in TSN. Thus, the authors consider that they know the topology of the network as well as the set of TT and AVB flows. The authors are interested to determine the routing of both TT and AVB flows as well as the scheduling of the TT flows such that all frames are schedulable and the AVB worst-case end-to-end delay is minimised. The authors have proposed an integer linear programming formulation for the scheduling problem and a greedy randomised adaptive search procedure-based heuristic for the routing problem. The proposed approaches have been evaluated using several test cases.
We present CIDANE, a novel framework for genome-based transcript reconstruction and quantification from RNA-seq reads. CIDANE assembles transcripts efficiently with significantly higher sensitivity and precision than ...
详细信息
We present CIDANE, a novel framework for genome-based transcript reconstruction and quantification from RNA-seq reads. CIDANE assembles transcripts efficiently with significantly higher sensitivity and precision than existing tools. Its algorithmic core not only reconstructs transcripts ab initio, but also allows the use of the growing annotation of known splice sites, transcription start and end sites, or full-length transcripts, which are available for most model organisms. CIDANE supports the integrated analysis of RNA-seq and additional gene-boundary data and recovers splice junctions that are invisible to other methods. CIDANE is available at http://***/software/cidane/.
To maintain a predictable execution environment, an embedded system must ensure that applications are, in advance, provided with sufficient resources to process tasks, exchange information and to control peripherals. ...
详细信息
ISBN:
(纸本)9783981537024
To maintain a predictable execution environment, an embedded system must ensure that applications are, in advance, provided with sufficient resources to process tasks, exchange information and to control peripherals. The problem of assigning tasks to processing elements with limited resources, and routing communication channels through a capacitated interconnect is combined into an integer linear programming formulation. We describe a guided local search algorithm to solve this problem at run-time. This algorithm allows for a hybrid strategy where configurations computed at design-time may be used as references to lower the computational overhead at runtime. Computational experiments on a dataset with 100 tasks and 20 processing elements show the effectiveness of this algorithm compared to state-of-the-art solvers CPLEX and Gurobi. The guided local search algorithm finds an initial solution within 100 milliseconds, is competitive for small platforms, scales better with the size of the platform, and has lower memory usage (2-19%).
Decreasing the Internet power consumption is a challenging issue. Optical transport networks employing the wavelength division multiplexing (WDM) technique have been identified as energy efficient solutions to face th...
详细信息
Decreasing the Internet power consumption is a challenging issue. Optical transport networks employing the wavelength division multiplexing (WDM) technique have been identified as energy efficient solutions to face this issue, considering the expected high increase of Internet traffic. The authors study the energy efficiency of a recently-proposed switching technique for transport networks, the time-driven-switching (TDS), in which time-coordination of network elements is exploited to achieve 'sub-lambda' granularity in optical signal switching directly in the optical domain. In order to achieve the fast switching time required by TDS, semi-conductor optical amplifier-based optical switches are exploited. The authors discuss the properties, in terms of the energy efficiency, of a TDS transport network, focusing on the energy requirements of the TDS optical switches. The authors provide a qualitative description of the main contributors to energy consumption in a TDS network. The authors then develop an integer linear programming formulation, in which the physical impairments impact over optical signals is also considered. Power consumption over realistic case study networks for the TDS case is compared to the power consumption for the classical IP over WDM architecture, and in some cases TDS is demonstrated to save more than 55% of power consumption with respect to competing architectures.
Background: The gene duplication (GD) problem seeks a species tree that implies the fewest gene duplication events across a given collection of gene trees. Solving this problem makes it possible to use large gene fami...
详细信息
Background: The gene duplication (GD) problem seeks a species tree that implies the fewest gene duplication events across a given collection of gene trees. Solving this problem makes it possible to use large gene families with complex histories of duplication and loss to infer phylogenetic trees. However, the GD problem is NP-hard, and therefore, most analyses use heuristics that lack any performance guarantee. Results: We describe the first integerlinearprogramming (ILP) formulation to solve instances of the gene duplication problem exactly. With simulations, we demonstrate that the ILP solution can solve problem instances with up to 14 taxa. Furthermore, we apply the new ILP solution to solve the gene duplication problem for the seed plant phylogeny using a 12-taxon, 6, 084-gene data set. The unique, optimal solution, which places Gnetales sister to the conifers, represents a new, large-scale genomic perspective on one of the most puzzling questions in plant systematics. Conclusions: Although the GD problem is NP-hard, our novel ILP solution for it can solve instances with data sets consisting of as many as 14 taxa and 1, 000 genes in a few hours. These are the largest instances that have been solved to optimally to date. Thus, this work can provide large-scale genomic perspectives on phylogenetic questions that previously could only be addressed by heuristic estimates.
As minimum feature size and pitch spacing further decrease, triple patterning lithography (TPL) is a possible 193nm extension along the paradigm of double patterning lithography (DPL). However, there is very little st...
详细信息
ISBN:
(纸本)9781457713989
As minimum feature size and pitch spacing further decrease, triple patterning lithography (TPL) is a possible 193nm extension along the paradigm of double patterning lithography (DPL). However, there is very little study on TPL layout decomposition. In this paper, we show that TPL layout decomposition is a more difficult problem than that for DPL. We then propose a general integer linear programming formulation for TPL layout decomposition which can simultaneously minimize conflict and stitch numbers. Since ILP has very poor scalability, we propose three acceleration techniques without sacrificing solution quality: independent component computation, layout graph simplification, and bridge computation. For very dense layouts, even with these speedup techniques, ILP formulation may still be too slow. Therefore, we propose a novel vector programmingformulation for TPL decomposition, and solve it through effective semidefinite programming (SDP) approximation. Experimental results show that the ILP with acceleration techniques can reduce 82% runtime compared to the baseline ILP. Using SDP based algorithm, the runtime can be further reduced by 42% with some tradeoff in the stitch number (reduced by 7%) and the conflict (9% more). However, for very dense layouts, SDP based algorithm can achieve 140x speed-up even compared with accelerated ILP.
This paper considers the problem of indoor wireless planning using smart antennas. Smart antennas have gained much attention in wireless networking because of their capability in providing more spatial reuse and incre...
详细信息
ISBN:
(纸本)9781424492688
This paper considers the problem of indoor wireless planning using smart antennas. Smart antennas have gained much attention in wireless networking because of their capability in providing more spatial reuse and increased network capacity. Recent research has demonstrated their effectiveness in indoor environments where omni-directional antennas have been traditionally the dominant technology. Much of the work, however, assumes that a network is already deployed and focuses on scheduling antenna patterns. In this work, we investigate finding a wireless plan for an indoor environment where the wireless plan specifies minimum number of antennas required to provide complete coverage of the environment as well as the location, transmission power and beam pattern for each antenna. This problem is more challenging than radio planning using omnidirectional antennas because of the special shape of antenna beams. Both single-beam and multi-beam antenna patterns are considered and integer linear programming formulations are provided for computing the minimum cost wireless plan. Moreover, to solve large-scale instances of the problem an efficient polynomial-time heuristic is proposed.
暂无评论