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

15th International Parallel and Distributed Processing Symposium, IPDPS 2001

作者： Kaklamanis, C. Computer Technology Institute Department of Computer Engineering and Informatics University of Patras Rio26500 Greece

ISBN: (纸本)0769509908

We study the problem of allocating optical bandwidth to sets of communication requests in all-optical networks that utilize Wavelength Division Multiplexing (WDM). WDM technology establishes communication between pairs of network nodes by establishing transmitter-receiver paths and assigning wavelengths to each path so that no two paths going through the same fiber link use the same wavelength. Optical bandwidth is the number of distinct wavelengths. Since state-of-the-art technology allows for a limited number of wavelengths, the engineering problem to be solved is to establish communication between pairs of nodes so that the total number of wavelengths used is minimized;this is known as the wavelength routing problem. In this paper we survey recent advances in bandwidth allocation in tree-shaped WDM all-optical networks. We present hardness results and lower bounds for the general problem and the special case of symmetric communication. We give the main ideas of deterministic greedy algorithms and study their limitations. We demonstrate how we can achieve optimal and nearly-optimal bandwidth utilization in networks with wavelength converters using simple algorithms. We also present recent results about the use of randomization for wavelength routing. © 2001 IEEE.

关键词： Bandwidth

来源：评论

学校读者我要写书评

暂无评论

Competitive analysis of on-line randomized call control in cellular networks 15

Competitive analysis of on-line randomized call control in c...

引用

15th International Parallel and Distributed Processing Symposium, IPDPS 2001

作者： Caragiaannis, I. Kaklamanis, C. Papaioannou, E. Computer Technology Institute Department of Computer Engineering and Informatics University of Patras Rio26500 Greece

ISBN: (纸本)0769509908

In this paper we address an important communication issue arising in cellular (mobile) networks that utilize Frequency Division Multiplexing (FDM) technology. In such networks, many users within the same geographical region can communicate simultaneously with other users of the network using distinct frequencies. The spectrum of the available frequencies is limited;thus, efficient solutions to the call control problem are essential. The objective of the call control problem is, given a spectrum of available frequencies and users that wish to communicate, to maximize the number of users that communicate without signal interference. Using competitive analysis, we study the performance of algorithm p-RANDOM;an intuitive on-line randomized call control algorithm proposed previously for cellular networks. We give upper and lower bounds of its competitive ratio against oblivious adversaries as a function of the parameter p. Optimizing the upper bound function, we prove that there exists a 2.651-competitive randomized call control algorithm. In this way, we significantly improve the best known upper bound on the competitiveness of on-line randomized call control which was 2.934. © 2001 IEEE.

关键词： Wireless networks

来源：评论

学校读者我要写书评

暂无评论

Analysis and experimental evaluation of an innovative and efficient routing protocol for ad-hoc mobile networks

引用

4th International Workshop on Algorithm engineering, WAE 2000

作者： Chatzigiannakis, I. Nikoletseas, S. Spirakis, P. Computer Technology Institute Patras Greece Computer Engineering and Informatics Department Patras University Greece

ISBN: (纸本)3540425128

An ad-hoc mobile network is a collection of mobile hosts, with wireless communication capability, forming a temporary network without the aid of any established fixed infrastructure. In such a (dynamically changing) network it is not at all easy to avoid broadcasting (and flooding). In this paper we propose, theoretically analyse and experimentally validate a new and efficient protocol for pairwise communication. The protocol exploits the co-ordinated motion of a small part of the network (*** is a semi-compulsory protocol) in order to provide to various sendersand receivers an efficient support for message passing. Our implementation platform is the LEDA system and we have tested the protocol forthree classes of graphs (grids, random graphs and bipartite multi-stagegraphs) each abstracting a different "motion topology". Our theoretical analysis (based on properties of random walks) and our experimental measurements indicate that only a small fraction of themobile stations are enough to be exploited by the support in order toachieve very fast communication between any pair of mobile stations. © Springer-Verlag Berlin Heidelberg 2001.

关键词： Routing protocols

来源：评论

学校读者我要写书评

暂无评论

An efficient routing protocol for hierarchical ad-hoc mobile networks 15

An efficient routing protocol for hierarchical ad-hoc mobile...

引用

15th International Parallel and Distributed Processing Symposium, IPDPS 2001

作者： Chatzigiannakis, I. Nikoletseas, S. Spirakis, P. Computer Technology Institute Patras Greece Computer Engineering and Informatics Department Patras University Greece

ISBN: (纸本)0769509908

We introduce a new model of ad-hoc mobile networks, which we call hierarchical, that are comprised of dense subnetworks of mobile users (corresponding to highly populated geographical areas, such as cities), interconnected across access ports by sparse but frequently used connections (such as highways). For such networks, we present an efficient routing protocol which extends the idea (introduced in [4]) of exploiting the co-ordinated motion of a small part of an ad-hoc mobile network (the "support") to achieve very fast communication between any two mobile users of the network. The basic idea of the new protocol presented here is, instead of using a unique (large) support for the whole network, to employ a hierarchy of (small) supports (one for each city) and also take advantage of the regular traffic of mobile users across the interconnection highways to communicate between cities. We combine here theoretical analysis (average case estimations based on random walk properties) and experimental implementations (carried out using the LEDA platform) to claim and validate results showing that such a hierarchical routing approach is, for this class of ad-hoc mobile networks, significantly more efficient than a simple extension of the basic "support" idea presented in [4]. © 2001 IEEE.

关键词： Routing protocols

来源：评论

学校读者我要写书评

暂无评论

Integrating GIS, GPS and GSM technologies for the effective management of ambulances

引用

computers, Environment and Urban Systems 2001年第3期25卷 267-278页

作者： Derekenaris, G. Garofalakis, J. Makris, C. Prentzas, J. Sioutas, S. Tsakalidis, A. Department of Computer Engineering and Informatics School of Engineering University of Patras 26500 Rion Patras Greece Computer Technology Institute Research Unit 5 PO Box 1122 26110 Patras Greece

In this paper, we describe a system offering a solution to the problem of ambulance management and emergency incident handling in the prefecture of Attica in Greece. It is based on the integration of geographic information system (GIS), global positioning system (GPS) and global system for mobile communication (GSM) technologies. The design of the system was the result of a project funded by the Greek Secretariat of Research and technology. A significant operation for the handling of emergency incidents is the routing of ambulances to incident sites and then to the closest appropriate hospitals. The response time of a real-time system like ours to such queries is of vital significance. By using efficient data structures for the implementation of the graph representing the road network, the time performance of the shortest-path algorithm can be enhanced. Incorporating the efficient algorithm within the GIS will increase our system's viability. © 2001 Elsevier Science Ltd. All rights reserved.

关键词： computer applications

来源：评论

学校读者我要写书评

暂无评论

An efficient communication strategy for ad-hoc mobile networks 15th

引用

15th International Conference on DIStributed Computing, DISC 2001

作者： Chatzigiannakis, I. Nikoletseas, S. Spirakis, P. Computer Technology Institute Patras Greece Greece Computer Engineering and Informatics Department Patras University Greece Greece

ISBN: (纸本)3540426051

We investigate the problem of communication in an ad-hoc mobile network, that is, we assume the extreme case of a total absense of any fixed network infrastructure (for example a case of rapid deployment of a set of mobile hosts in an unknown terrain). We propose, in such a case, that a small subset of the deployed hosts (which we call the support) should be used for network operations. However, the vast majority of the hosts are moving arbitrarily according to application needs. We then provide a simple, correct and efficient protocol for communication that avoids message flooding. Our protocol manages to establish communication between any pair of mobile hosts in small, a-priori guaranteed expected time bounds even in the worst case of arbitrary motions of the hosts that not in the support (provided that they do not deliberately try to avoid the support). These time bounds, interestingly, do not depend, on the number of mobile hosts that do not belong in the support. They depend only on the size of the area of motions. Our protocol can be implemented in very efficient ways by exploiting knowledge of the space of motions or by adding more power to the hosts of the support. Our results exploit and further develop some fundamental properties of random walks in finite graphs. © Springer-Verlag Berlin Heidelberg 2001.

关键词： Mobile ad hoc networks

来源：评论

学校读者我要写书评

暂无评论

Coupon collectors, q-binomial coefficients and the unsatisfiability threshold 7th

Coupon collectors, q-binomial coefficients and the unsatisfi...

引用

7th Italian Conference on Theoretical computer Science, ICTCS 2001

作者： Kaporis, Alexis C. Kirousis, Lefteris M. Stamatiou, Yannis C. Vamvakari, Malvina Zito, Michele University of Patras Department of Computer Engineering and Informatics Patras Rio26500 Greece Computer Technology Institute Kolokotroni 3 Patras26321 Greece Department of Computer Science University of Liverpool United Kingdom

ISBN: (纸本)9783540454465

The problem of determining the unsatisfiability threshold for random 3-SAT formulas consists in determining the clause to variable ratio that marks the (experimentally observed) abrupt change from almost surely satisfiable formulas to almost surely unsatisfiable. Up to now, there have been rigorously established increasingly better lower and upper bounds to the actual threshold value. An upper bound of 4.506 was announced by Dubois et al. in 1999 but, to the best of our knowledge, no complete proof has been made available from the authors yet. We consider the problem of bounding the threshold value from above using methods that, we believe, are of interest on their own right. More specifically, we explain how the method of local maximum satisfying truth assignments can be combined withresu lts for coupon collector’s probabilities in order to achieve an upper bound for the unsatisfiability threshold less than 4.571. Thus, we improve over the best, with an available complete proof, previous upper bound, which was 4.596. In order to obtain this value, we also establish a bound on the q-binomial coefficients (a generalization of the binomial coefficients) which may be of independent interest. © Springer-Verlag Berlin Heidelberg 2001.

关键词： Artificial intelligence

来源：评论

学校读者我要写书评

暂无评论

An experimental study of basic communication protocols in ad-hoc mobile networks 1

引用

5th International Workshop on Algorithm engineering, WAE 2001

作者： Chatzigiannakis, Ioannis Nikoletseas, Sotiris Paspallis, Nearchos Spirakis, Paul Zaroliagis, Christos Computer Technology Institute P.O. Box 1122 Patras26110 Greece Department of Computer Engineering and Informatics University of Patras Patras26500 Greece

ISBN: (数字)9783540446880

ISBN: (纸本)3540425004

We investigate basic communication protocols in ad-hoc mobile networks. We follow the semi-compulsory approach according to which a small part of the mobile users, the support Σ, that moves in a predetermined way is used as an intermediate pool for receiving and delivering messages. Under this approach, we present a new semi-compulsory protocol called the runners in which the members of Σ perform concurrent and continuous random walks and exchange any information given to them by senders when they meet. We also conduct a comparative experimental study of the runners protocol with another existing semicompulsory protocol, called the snake, in which the members of Σ move in a coordinated way and always remain pairwise adjacent. The experimental evaluation has been carried out in a new generic framework that we developed to implement protocols for mobile computing. Our experiments showed that for both protocols only a small support is required for efficient communication, and that the runners protocol outperforms the snake protocol in almost all types of inputs we considered. © Springer-Verlag Berlin Heidelberg 2001.

关键词： Mobile ad hoc networks

来源：评论

学校读者我要写书评

暂无评论

The unsatisfiability threshold revisited

引用

Electronic Notes in Discrete Mathematics 2001年 9卷 81-95页

作者： Kaporis, Alexis C. Kirousis, Lefteris M. Stamatiou, Yannis C. Vamvakari, Malvina Zito, Michele University of Patras Department of Computer Engineering and Informatics University Campus GR-265 04 Patras Greece Computer Technology Institute GR-262 21 Patras 61 Riga Feraiou Str. Greece Department of Computer Science University of Liverpool United Kingdom

The problem of determining the unsatisfiability threshold for random 3-SAT formulas consists in determining the clause to variable ratio that marks the experimentally observed abrupt change from almost surely satisfiable formulas to almost surely unsatisfiable. Up to now, there have been rigorously established increasingly better lower and upper bounds to the actual threshold value. In this paper, we consider the problem of bounding the threshold value from above using methods that, we believe, are of interest on their own right. More specifically, we show how the method of local maximum satisfying truth assignments can be combined with results for the occupancy problem in random allocation schemes of balls into bins in order to achieve an upper bound for the unsatisfiability threshold less than 4.571. Thus we improve over the best, with an available complete proof, previous upper bound, which was 4.596. In order to obtain this value, we also establish a bound on the q-binomial coefficients (a generalization of the binomial coefficients) which, we believe, is of independent interest.

关键词： Complexity Phase transition Probabilistic analysis Satisfiability

来源：评论

学校读者我要写书评

暂无评论

On the design of modulo 2/sup n//spl plusmn/1 adders

On the design of modulo 2/sup n//spl plusmn/1 adders

引用

IEEE International Conference on Electronics, Circuits and Systems (ICECS)

作者： C. Efstathiou H.T. Vergos D. Nikolos Department of Informatics TEI Athens Athens Greece Computer Technology Institute CTI Patras Greece Computer Engineering & Informatics Department University of Patras Patras Greece

In this paper we present new architectures for the design of modulo 2/sup n//spl plusmn/1 adders, which are based on the use of the same design block. Our design block incorporates a parallel-prefix carry computation unit with a carry increment stage. VLSI implementations of the proposed architectures in a static CMOS technology reveal their superiority against all already known architectures when the area * time/sup 2/ product is used as a metric and n > 8.

关键词： computer architecture Tree data structures Logic Algorithm design and analysis Costs Concurrent computing Tin Delay

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：