检索结果-内蒙古大学图书馆

Contention resolution in a non-synchronized multiple access channel

THEORETICAL COMPUTER SCIENCE 2017年 689卷 1-13页

作者： De Marco, Gianluca Kowalski, Dariusz R. Univ Salerno Dipartimento Informat I-84084 Fisciano SA Italy Univ Liverpool Dept Comp Sci Liverpool L69 3BX Merseyside England

Multiple access channel is a well-known communication model that deploys properties of many network systems, such as Aloha multi-access systems, local area Ethernet networks, satellite communication systems, packet radio networks. The fundamental aspect of this model is to provide efficient communication and computation in the presence of restricted access to the communication resource: at most one station can successfully transmit at a time, and a wasted round occurs when more than one station attempts to transmit at the same time. In this work we consider the problem of contention resolution in a multiple access channel in a realistic scenario when up to k stations out of n join the channel at different times. The goal is to let at least one station to transmit alone, which results in successful delivery of the message through the channel. We present three algorithms: two of them working under some constrained scenarios, and achieving optimal time complexity circle dot(klog(n/k) + 1), while the third general algorithm accomplishes the goal in time O (k log n log logn). (C) 2017 Elsevier B.V. All rights reserved.

关键词： Multiple access channel Contention resolution deterministic algorithms Distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

Algebraic algorithms to separate overlapping secondary surveillance radar replies

引用

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2007年第7期55卷 3746-3759页

作者： Petrochilos, Nicolas van der Veen, Alle-Jan Delft Univ Technol Dept Elect Engn NL-2628 CD Delft Netherlands Univ Roma Tor Vergata I-00133 Rome Italy

The secondary surveillance radar (SSR) is a transponder system used in air-traffic control (ATC). Due to growing traffic densities, it is increasingly likely that a ground station receives a mixture of responses of various aircraft, partly overlapping in frequency and time. Currently such "collisions" are disregarded, at a loss of system performance and reliability. In this paper, we propose to equip the ground station with an antenna array, and investigate techniques to blindly separate such a mixture based on source waveform properties. At baseband, a received SSR signal consists of a binary sequence with alphabet {0,1}, modulated by a complex exponential due to the residual carrier frequency. We present three algebraic algorithms to compute the separating beamformers by taking into account the particular modulation format of the received signal. The Cramer-Rao bound (CRB) is derived, extensive simulations are presented, and an experimental platform has been built to collect measurement data and demonstrate the algorithms.

关键词： array signal processing blind source separation deterministic algorithms secondary radar

来源：评论

学校读者我要写书评

暂无评论

Effect of customer worth of interrupted supply on the optimal design of small isolated power systems with increased renewable energy penetration

引用

IET GENERATION TRANSMISSION & DISTRIBUTION 2013年第3期7卷 265-275页

作者： Katsigiannis, Yiannis A. Georgilakis, Pavlos S. Technol Educ Inst Crete Dept Nat Resources & Environm GR-73135 Khania Greece NTUA Sch Elect & Comp Engn GR-15780 Athens Greece

The analysis and design of a small isolated power system (SIPS) with renewable energy sources (RES) and storage can be challenging, because of the large number of design options and the uncertainty in key parameters. RES add further complexity because their power output may be intermittent, seasonal and non-dispatchable. Owing to this characteristic, reliability evaluation of a RES-based SIPS cannot be implemented using the traditional deterministic and analytical methods. Moreover, this evaluation has to be done within a cost-benefit framework. This study models and investigates the effect of customer worth of interrupted supply (customer damage cost) on the optimal design of SIPS with storage and increased RES penetration. The SIPS optimal design is implemented with a genetic algorithm combined with local search procedure. In addition, this study examines the effect of the forced outage rate of SIPS components on SIPS optimal design via Monte Carlo simulation. The performance of the proposed hybrid optimisation methodology is investigated for a large number of alternative scenarios via sensitivity analysis, which study the effect on the results because of the uncertainty on weather data, components efficiency and cost data. The results show that the optimal design of a RES-based SIPS depends largely on the consideration of customer damage cost as well as the inclusion of components forced outage rate. The method and results presented in this article should be valuable in planning and operating SIPS with RES.

关键词： cost-benefit analysis deterministic algorithms energy storage genetic algorithms interrupters Monte Carlo methods power system economics power system planning power system reliability renewable energy sources sensitivity analysis power system planning weather data uncertainty sensitivity analysis hybrid optimisation methodology Monte Carlo simulation local search procedure genetic algorithm customer damage cost cost-benefit framework analytical method deterministic method reliability evaluation parameter uncertainty energy storage renewable energy source RES SIPS small isolated power system optimal design interrupted supply

来源：评论

学校读者我要写书评

暂无评论

Cone-based placement for field programmable gate arrays

引用

IET COMPUTERS AND DIGITAL TECHNIQUES 2011年第1期5卷 49-62页

作者： Banerjee, P. Saha, D. Sur-Kolay, S. Univ Calcutta Dept Comp Sci & Engn Kolkata 700009 India Indian Stat Inst Adv Comp & Microelect Unit Kolkata 700108 India

deterministic greedy methods have been proposed to place the netlist of configurable logic blocks (CLBs) and primary input output blocks (IOBs) quickly on a two-dimensional (2D) island-style field programmable gate array (FPGA) consisting of either one or multiple 2D island-style arrays of CLBs and IOBs. The first method, 'ConeCLBPlace', starts with a random placement of the primary output blocks along the periphery of the 2D array of CLBs, then places the CLBs and primary input blocks in a greedy deterministic way. In the second method, 'ConeIOBPlace', the IOBs are first placed on the periphery of the FPGA chip using a deterministic heuristic, and then the CLBs are placed within the 2D array using a typical simulated annealing (SA) flow. The third method, 'ConePlace', combines the above two deterministic approaches by first placing the IOBs only using ConeIOBPlace, and then the CLBs using ConeCLBPlace deterministically. Finally, a low-temperature SA is executed in order to obtain a high-quality final placement. ConeCLBPlace and ConePlace produce placements 2.34x and 1.83x faster than the placement step of popular FPGA place-and-route tool VPR (versatile place and route) on the average. The bounding box costs of placement produced by ConeCLBPlace and ConePlace, after execution of the iterative SA steps, are 1.05x and 1.14x of VPR, respectively, on the average, whereas the critical path delay obtained after routing is 1.03x of VPR for both methods on the average, implying almost the same quality of VPR. This justifies the utility of the methods proposed.

关键词： multiple 2D island-style arrays primary input output blocks Logic circuits Logic and switching circuits field programmable gate arrays two-dimensional island-style field programmable gate array simulated annealing ConeIOBPlace deterministic algorithms deterministic greedy methods greedy algorithms bounding box placement costs cone-based placement configurable logic blocks

来源：评论

学校读者我要写书评

暂无评论

What Monte Carlo models can do and cannot do efficiently?

引用

APPLIED MATHEMATICAL MODELLING 2008年第8期32卷 1477-1500页

作者： Atanassov, Emanouil Dimov, Ivan T. Univ Reading ACET Reading RG6 6AH Berks England Bulgarian Acad Sci Dept Parallel Algorithms Inst Parallel Proc BU-1113 Sofia Bulgaria

The question "what Monte Carlo models can do and cannot do efficiently" is discussed for some functional spaces that define the regularity of the input data. Data classes important for practical computations are considered: classes of functions with bounded derivatives and Holder type conditions, as well as Korobov-like spaces. Theoretical performance analysis of some algorithms with unimprovable rate of convergence is given. Estimates of computational complexity of two classes of algorithms - deterministic and randomized for both problems - numerical multidimensional integration and calculation of linear functionals of the solution of a class of integral equations are presented. (c) 2007 Elsevier Inc. All rights reserved.

关键词： Monte Carlo algorithms deterministic algorithms multidimensional integration integral equations unimprovable rate of convergence

来源：评论

学校读者我要写书评

暂无评论

Hybridized classification algorithms for data classification applications: A review

引用

EGYPTIAN INFORMATICS JOURNAL 2021年第2期22卷 185-192页

作者： Sherwani, F. Ibrahim, B. S. K. K. Asad, Muhammad Mujtaba FAST Natl Univ Comp & Emerging Sci Dept Comp Sci Karachi Sindh Pakistan Coventry Univ Fac Engn Environm & Comp Sch Mech Aerosp & Automot Priory St Coventry CV1 5FB W Midlands England Sukkur IBA Univ Dept Educ Airport Rd Sukkur Sindh Pakistan

Machine-based classification usually involves some computer programs, known as algorithms, developed using several mathematical formulations to accelerate the automated classification process. Along with the exponential increase in the size and computational complexity of the data today, such optimized, robust, agile and reliable computational algorithms are required which can efficiently carry out these conforming classification tasks. In this review paper, deterministic optimization techniques have been analysed that are efficiently employed for machine learning applications. In this review, systematic literature review approach has been adopted in which 200 research articles were downloaded from which 100 latest articles has been selected based on the most commonly employed neural networks' techniques. Moreover, the reported neural networks techniques based on Back Propagation Neural Network (BPNN), Recurrent Neural Networks (RNNs) Algorithm and Levenberg-Marquardt (LM) with several hybridized classification algorithms based on optimization techniques have been indicated that are commonly used to optimize and benefit the classification process. (C) 2021 THE AUTHORS. Published by Elsevier BV on behalf of Faculty of Computers and Artificial Intelligence, Cairo University.

关键词： Recurrent Neural Networks (RNNs) algorithm Back Propagation Neural Network (BPNN) deterministic algorithms Machine learning Levenberg-Marquardt (LM)

来源：评论

学校读者我要写书评

暂无评论

Generalized framework for Group Testing: Queries, feedbacks and adversaries

引用

THEORETICAL COMPUTER SCIENCE 2022年 919卷 18-35页

作者： Klonowski, Marek Kowalski, Dariusz R. Pajak, Dominik Wroclaw Univ Sci & Technol Wroclaw Poland Augusta Univ Augusta GA 30912 USA

In the Group Testing problem, the objective is to learn a subset K of some much larger domain N, using the shortest-possible sequence of queries Q. A feedback to a query provides some information about the intersection between the query and subset K. Several specific feedbacks have been studied in the literature, often proving different formulas for the estimate of the query complexity of the problem, defined as the shortest length of queries' sequence solving Group Testing problem with specific feedback. In this paper we study what are the properties of the feedback that influence the query complexity of Group Testing and what is their measurable impact. We propose a generic framework that covers a vast majority of relevant settings considered in the literature, which depends on two fundamental parameters of the feedback: input capacity alpha and output expressiveness beta. They upper bound the logarithm of the size of the feedback function domain and image, respectively. To justify the value of the framework, we prove upper bounds on query complexity of non-adaptive, deterministic Group Testing under some "efficient" feedbacks, for minimum, maximum and general expressiveness, and complement them with a lower bound on all feedbacks with given parameters alpha, beta. Our upper bounds also hold if the feedback function could get an input twisted by a malicious adversary, in case the intersection of a query and the hidden set is bigger than the feedback capacitya. We also show that slight change in the feedback function may result in substantial worsening of the query complexity. Additionally, we analyze explicitly constructed randomized counterparts of the deterministic results. Our results provide some insights to what are the most useful bits of information an output-restricted feedback could provide, and open a number of challenging research directions. (C) 2022 Elsevier B.V. All rights reserved.

关键词： Group testing Queries Feedback functions Adversaries Non-adaptive algorithms deterministic algorithms Randomized algorithms Lower bound

来源：评论

学校读者我要写书评

暂无评论

Distributed streams algorithms for sliding windows

引用

THEORY OF COMPUTING SYSTEMS 2004年第3期37卷 457-478页

作者： Gibbons, PB Tirthapura, S Intel Res Pittsburgh Pittsburgh PA 15213 USA Iowa State Univ Dept Elect & Comp Engn Ames IA 50010 USA

Massive data sets often arise as physically distributed, parallel data streams, and it is important to estimate various aggregates and statistics on the union of these streams. This paper presents algorithms for estimating aggregate functions over a "sliding window" of the N most recent data items in one or more streams. Our results include: 1. For a single stream, we present the first epsilon-approximation scheme for the number of 1's in a sliding window that is optimal in both worst case time and space. We also present the first E-approximation scheme for the sum of integers in [0..R] in a sliding window that is optimal in both worst case time and space (assuming R is at most polynomial in N). Both algorithms are deterministic and use only logarithmic memory words. 2. In contrast, we show that any deterministic algorithm that estimates, to within a small constant relative error, the number of 1's (or the sum of integers) in a sliding window on the union of distributed streams requires Omega(N) space. 3. We present the first (randomized) (epsilon, delta)-approximation scheme for the number of 1's in a sliding window on the union of distributed streams that uses only logarithmic memory words. We also present the first (epsilon, delta)-approximation scheme for the number of distinct values in a sliding window on distributed streams that uses only logarithmic memory words. Our results are obtained using a novel family of synopsis data structures called waves.

关键词： sliding windows Unions deterministic algorithms Logarithmic rivers streams Distribute

来源：评论

学校读者我要写书评

暂无评论

Reachability, confluence, and termination analysis with state-compatible automata

引用

INFORMATION AND COMPUTATION 2017年第Part3期253卷 467-483页

作者： Felgenhauer, Bertram Thiemann, Rene Univ Innsbruck Inst Comp Sci Innsbruck Austria

Regular tree languages are a popular device for reachability analysis over term rewrite systems, with many applications like analysis of cryptographic protocols, or confluence and termination analysis. At the heart of this approach lies tree automata completion, first introduced by Genet for left-linear rewrite systems. Korp and Middeldorp introduced so-called quasi-deterministic automata to extend the technique to non-left-linear systems. In this paper, we introduce the simpler notion of state-compatible automata, which are slightly more general than quasi-deterministic, compatible automata. This notion also allows us to decide whether a regular tree language is closed under rewriting, a problem which was not known to be decidable before. The improved precision has a positive impact in applications which are based on reachability analysis, namely termination and confluence analysis. Our results have been formalized in the theorem prover Isabelle/HOL. This allows to certify automatically generated proofs that are using tree automata techniques. (C) 2016 The Authors. Published by Elsevier Inc.

关键词： CRYPTOGRAPHY FORMAL languages TREE graphs MACHINE theory deterministic algorithms

来源：评论

学校读者我要写书评

暂无评论

Global optimization requires global information

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 1998年第3期96卷 575-588页

作者： Stephens, CP Baritompa, W Univ Canterbury Dept Math & Stat Christchurch 1 New Zealand

There are many global optimization algorithms which do not use global information. We broaden previous results, showing limitations on such algorithms, even if allowed to run forever. We show that deterministic algorithms must sample a dense set to find the global optimum value and can never be guaranteed to converge only to global optimizers. Further, analogous results show that introducing a stochastic element does not overcome these limitations. An example is simulated annealing in practice. Our results show that there are functions for which the probability of success is arbitrarily small.

关键词： global optimization convergence stochastic algorithms deterministic algorithms

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：