An efficient distributed algorithm for maximum matching in general graphs

We present a distributed algorithm for maximum cardinality matching in general graphs. On a general graph withn vertices, our algorithm requiresO(n ^5/2) messages in the worst case. On trees, our algorithm computes a maximum matching usingO(n) messages after the election of a leader.Work on this paper has been supported by the Office of Naval Research under Contract N00014-85-K-0570.     

Distributed approximation of cellular coverage

We consider the following model of cellular networks. Each base station has a given finite capacity, and each client has some demand and profit. A client can be covered by a specific subset of the base stations, and its profit is obtained only if its demand is provided in full. The goal is to assign clients to base stations, so that the overall profit is maximized subject to base station capacity constraints.     

Linear election in pancake graphs

Pancake graphs have been proposed as an attractive alternative to hypercube networks. They have a smaller diameter and a lower degree. They also have a hierarchical structure which can be exploited in designing algorithms.In this paper, we propose a leader election algorithm for oriented pancake graphs. The algorithm has a message complexity that is linear in the order of the graph.     

Distributed election in complete networks

An improved version of Afek and Gafni's synchronous algorithm for distributed election in complete networks is given and anO(n) expected message complexity is shown. M.Y. Chan received her Ph.D. in 1988 from the University of Hong Kong, and her M.S. and B.A. degrees in computer science from the University of California, San Diego in 1980 and 1981, respectively. She is currently an Assistant Professor at the University of Texas at Dallas. Francis Y.L. Chin (S71-M76-SM85) received the B.Sc. degree in engineering science from the University of Toronto, Toronto, Canada, in 1972, and the M.S., M.A., and Ph.D. degrees in electrical engineering and computer science from Princeton University, New Jersey, in 1974, 1975, and 1976, respectively. Since 1975, he has taught at the University of Maryland, Baltimore Country, University of California, San Diego, University of Alberta, and Chinese University of Hong Kong. He is currently Head of the Department of Computer Science, University of Hong Kong. He has served as a program co-chairman of the 1988 International Conference on Computer Processing of Chinese and Oriental Languages (Toronto) and the International Computer Science Conference '88 (Hong Kong). His current research interests include algorithm design and analysis, parallel and distributed computing.     

A note on maximum independent sets in rectangle intersection graphs

Finding the maximum independent set in the intersection graph of n axis-parallel rectangles is NP-hard. We re-examine two known approximation results for this problem. For the case of rectangles of unit height, Agarwal, van Kreveld and Suri [Comput. Geom. Theory Appl. 11 (1998) 209-218] gave a (1+1/k)-factor algorithm with an O(nlogn+n^2k−1) time bound for any integer constant k?1; we describe a similar algorithm running in only O(nlogn+nΔ^k−1) time, where Δ?n denotes the maximum number of rectangles a point can be in. For the general case, Berman, DasGupta, Muthukrishnan and Ramaswami [J. Algorithms 41 (2001) 443-470] gave a ⌈log_kn⌉-factor algorithm with an O(n^k+1) time bound for any integer constant k?2; we describe similar algorithms running in O(nlogn+nΔ^k−2) and n^O(k/logk) time.     

A note on maximum independent set and related problems on box graphs

A box graph is the intersection graph of orthogonal rectangles in the plane. We show that maximum independent set and minimum vertex cover on box graphs can be solved in subexponential time, more precisely, in time , by applying Miller's simple cycle planar separator theorem [J. Comput. System Sci. 32 (1986) 265-279] (in spite of the fact that the input box graph might be strongly non-planar).     

Distributed match-making

In many distributed computing environments, processes are concurrently executed by nodes in a store- and-forward communication network. Distributed control issues as diverse as name server, mutual exclusion, and replicated data management involve making matches between such processes. We propose a formal problem called distributed match-making as the generic paradigm. Algorithms for distributed match-making are developed and the complexity is investigated in terms of messages and in terms of storage needed. Lower bounds on the complexity of distributed match-making are established. Optimal algorithms, or nearly optimal algorithms, are given for particular network topologies.The work of the second author was supported in part by the Office of Naval Research under Contract N00014-85-K-0168, by the Office of Army Research under Contract DAAG29-84-K-0058, by the National Science Foundation under Grant DCR-83-02391, and by the Defence Advanced Research Projects Agency (DARPA) under Contract N00014-83-K-0125. Current address of both authors: CWI, Kruislaan 413, 1098 SJ Amsterdam, The Netherlands.     

基于分布式时间反转法的水声组网通信

研究水下信息获取系统,在非均匀介质中实现声束的自适应聚焦,应用于水声组网通信时,可以很好地利用海洋信道中的多径特性,提高节点间的通信速率,为消除码间干扰和改善误码率,提出了一种基于分布式时间反转法的水卢组网通信方案,充分利用网络中多个独立节点的自身资源,组成分布式时反组网通信系统,组网节点不需要再设置传统时间反转法所必需的垂直线列阵,易于工程实现.利用海洋环境实测数据得到的仿真结果表明提出的分布式时反组网通信与传统时间反转法组网通信性能相当,联合判决反馈均衡器可进一步提高系统件能.     

一种基于环形结构的新型分布式入侵检测模型

分析了目前的分布式入侵检测系统的特点和协作方式,提出了基于逻辑环形分布式协作控制技术的分布式入侵检测模型,解决了目前分布式入侵检测系统中各系统闭协作效率低、配置复杂、检测响应慢等缺陷。详细论述了环形结构的分布式入侵检测系统的体系结构和系统框架,提出了一套基于环形结构的分布式入侵检测协作算法。     

Distributed measurement and control system based on microcontrollers with automatic program generation

The paper describes an open architecture microcontroller based distributed measurement and control system with automatic generation of application program. Interpretation of functions and generation of program for control of the newly added distributed unit or distributed unit of a new type connected to the system performs automatically, without user assistance. The elements of the system are interconnected by means of a serial common bus according to the reduced OSI protocol. The proposed concept was tested in a system developed by using 8-bit Atmel microcontrollers of 89S and 89C series. Apart from the central unit, intelligent distributed units were developed for the control of a stepper motor, programmable linear movement, control of halogen lamps, acquisition and generation of analogue, digital and timing pulses and a real time clock (RTC).     

Distributed algorithms for reaching consensus on general functions

This paper presents analysis and design results for distributed consensus algorithms in multi-agent networks. We consider continuous consensus functions of the initial state of the network agents. Under mild smoothness assumptions, we obtain necessary and sufficient conditions characterizing any algorithm that asymptotically achieves consensus. This characterization is the building block to obtain various design results for networks with weighted, directed interconnection topologies. We first identify a class of smooth functions for which one can synthesize in a systematic way distributed algorithms that achieve consensus. We apply this result to the family of weighted power mean functions, and characterize the exponential convergence properties of the resulting algorithms. We establish the validity of these results for scenarios with switching interconnection topologies. Finally, we conclude with two discontinuous distributed algorithms that achieve, respectively, max and min consensus in finite time.     

1.5-Approximation algorithm for weighted maximum routing and wavelength assignment on rings

We give a 1.5-approximation algorithm for the weighted maximum routing and wavelength assignment problem on undirected ring networks. This improves the previous 1.58-approximation result.     

Distributed algorithms for finding and maintaining a k-tree core in a dynamic network

A k-core C_k of a tree T is subtree with exactly k leaves for k?n_l, where n_l the number of leaves in T, and minimizes the sum of the distances of all nodes from C_k. In this paper first we propose a distributed algorithm for constructing a rooted spanning tree of a dynamic graph such that root of the tree is located near the center of the graph. Then we provide a distributed algorithm for finding k-core of that spanning tree. The spanning tree is constructed in two stages. In the first stage, a forest of trees is generated. In the next stage these trees are connected to form a single rooted tree. An interesting aspect of the first stage of proposed spanning algorithm is that it implicitly constructs the (convex) hull of those nodes which are not already included in the spanning forest. The process is repeated till all non root nodes of the graph have chosen a unique parent. We implemented the algorithms for finding spanning tree and its k-core. A core can be quite useful for routing messages in a dynamic network consisting of a set of mobile devices.     

基于校园网的分布式入侵检测系统设计与分析

分析了数字化校园网面临的安全性问题,在比较了常用入侵检测系统优缺点的基础上,克服了传统入侵检测系统的缺点,设计了一种实用、低成本的校园网分布式入侵检测系统。与以往的入侵检测系统相比较,这种方法有着很高的效率,且能够快速地检测出针对校园网的各种入侵威胁,极大地保护了校园网的安全。     

A note on models for graph representations

This paper is intended more to ask questions than give answers. Specifically, we consider models for labeling schemes, and discuss issues regarding the number of labels consulted vs. the sizes of the labels.     

Incremental deployment of network monitors based on Group Betweenness Centrality

In many applications we are required to increase the deployment of a distributed monitoring system on an evolving network. In this paper we present a new method for finding candidate locations for additional deployment in the network. This method is based on the Group Betweenness Centrality (GBC) measure that is used to estimate the influence of a group of nodes over the information flow in the network. The new method assists in finding the location of k additional monitors in the evolving network, such that the portion of additional traffic covered is at least (1−1/e) of the optimal.     

A note on leader election in directed split-stars and directed alternating group graphs

A leader node is defined to be any node of the network unambiguously identified by some characteristics. In this paper, we first present a distributed algorithm for finding a leader node of a directed split-star. Moreover, an efficient self-stabilizing leader election algorithm that converges with linear rounds is proposed for directed split-stars. Actually, the distributed algorithm and the self-stabilizing algorithm are also applicable to the problem of directed alternating group graphs. As far as we know, no self-stabilizing leader election algorithm was known for the two graphs.     

基于分布式压缩感知的无线传感器网络异常数据处理

无线传感器网络的海量数据采集、传输和处理,对传感器节点的处理能力和功耗提出了严峻挑战,而且现实环境中传感器故障或者环境因素的突变会导致部分采集数据异常,而传统的数据处理方法无法对包含异常的数据进行有效的处理。针对上述问题,文中提出了两类无线传感器网络的异常数据模型,以及相应的基于分布式压缩感知的异常数据处理方法。通过协同的多个传感器进行数据压缩采样,当多个传感器采集的数据包含异常成分时,分布式压缩感知技术对数据中相同的正常分量进行一次统一重构,仅对不同的异常分量进行单独重构,从而避免了对相同数据分量的重复处理,提高了对包含异常成分数据处理的效率。另外,分布式压缩感知技术充分利用数据间的相关性,可有效减少传感器网络的数据采集量,加强其对抗异常数据的鲁棒性。对两类异常数据模型的数值仿真结果表明:相比于传统的基于单组测量值的压缩感知技术,基于分布式压缩感知技术的数据处理方法在提高异常数据重构准确率的同时,将采样数据量减少了约33%,证明了该方法的有效性。