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

Gathering Anonymous, Oblivious Robots on a Grid

THEORETICAL COMPUTER SCIENCE 2020年 815卷 289-309页

作者： Castenow, Jannik Fischer, Matthias Harbig, Jonas Jung, Daniel der Heide, Friedhelm Meyer Auf Paderborn Univ Heinz Nixdorf Inst Furstenallee 11 D-33102 Paderborn Germany Paderborn Univ Comp Sci Dept Furstenallee 11 D-33102 Paderborn Germany

We consider a swarm of nautonomous mobile robots distributed on a 2-dimensional grid. A basic task for such a swarm is to perform the gathering process: All robots have to gather at one not predefined place. On the grid there are configurations which, due to symmetry, cannot be gathered at a single point. Such configurations are 2 x 2squares. Therefore, we say that the swarm is gathered if all robots are located inside of a 2 x 2square. We assume the fully synchronous FSYNCtime model and the following very simple so-called Basic&Plainrobot model: The robots are oblivious, only have a constant viewing radius, are autonomous and indistinguishable, do not have a common compass, and cannot communicate. This implies that a robot's decision about its next action can only be based on the current relative positions of the robots in its viewing range. We consider connected swarms. We say two robots are connected if they are located in horizontally or vertically neighboring grid cells. We present the first gathering algorithm on the grid for this simple robot model and show that it gathers in time O(n(2)). Known algorithms for gathering on the grid need much stronger robot models: Either they have a common compass, or they have a finite memory and can communicate (via lights or flags) with robots in their viewing range. Finally, we extend our algorithm to the case where one of the robots is stationary, i.e. does not move. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Gathering problem Autonomous robots Stationary robots distributed algorithms Local algorithms Mobile agents Runtime bound Swarm formation problems

来源：评论

学校读者我要写书评

暂无评论

Message lower bounds via efficient network synchronization

引用

THEORETICAL COMPUTER SCIENCE 2020年 810卷 82-95页

作者： Pandurangan, Gopal Peleg, David Scquizzato, Michele Univ Houston Dept Comp Sci Houston TX 77204 USA Weizmann Inst Sci Dept Comp Sci & Appl Math IL-76100 Rehovot Israel Univ Padua Dept Math I-35121 Padua Italy

We present a uniform approach to derive message-time tradeoffs and message lower bounds for synchronous distributed computations using results from communication complexity theory. Since the models used in the classical theory of communication complexity are inherently asynchronous, lower bounds do not directly apply in a synchronous setting. To address this issue, we show a general result called Synchronous Simulation Theorem (SST) which allows to obtain message lower bounds for synchronous distributed computations by leveraging lower bounds on communication complexity. The SST is a by-product of a new efficient synchronizer for complete networks, called sigma, which has simulation overheads that are only logarithmic in the number of synchronous rounds with respect to both time and message complexity, even in networks with limited bandwidth. Synchronizer sigma is particularly efficient in simulating synchronous algorithms which employ silence, a situation that occurs when in some round no processor sends any message. In particular, a curious property of this synchronizer, which sets it apart from its predecessors, is that it is time-compressing, and hence in some cases it may result in a simulation that is faster than the original execution. While the SST gives near-optimal message lower bounds up to large values of the number of allowed synchronous rounds r (usually polynomial in the size of the input), it fails to provide meaningful bounds when the synchronous algorithm to be simulated may comprise a very large number of rounds. To complement the bounds provided by the SST, we then derive message lower bounds for the synchronous message-passing model that are unconditional, that is, independent of r, by establishing novel lower bounds for multi-party synchronous communication complexity. We apply our approach to show (almost) tight message-time tradeoffs and message lower bounds for several fundamental problems in the synchronous message-passing model of distribu

关键词： distributed algorithms Synchronous message-passing Communication complexity Lower bounds Synchronizers

来源：评论

学校读者我要写书评

暂无评论

Efficient Link Scheduling in Wireless Networks Under Rayleigh-Fading and Multiuser Interference

引用

IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS 2020年第8期19卷 5621-5634页

作者： Yu, Jiguo Yu, Kan Yu, Dongxiao Lv, Weifeng Cheng, Xiuzhen Chen, Honglong Cheng, Wei Qilu Univ Technol Shandong Acad Sci Sch Comp Sci & Technol Jinan 250353 Peoples R China Natl Supercomp Ctr Jinan Shandong Comp Sci Ctr Jinan 250014 Peoples R China Shandong Lab Comp Networks Jinan 250014 Peoples R China Shandong Univ Sci & Technol Coll Comp Sci & Engn Qingdao 266510 Peoples R China Shandong Univ Sch Comp Sci & Technol Qingdao 266510 Peoples R China Beihang Univ Sch Comp Sci & Engn Beijing 100191 Peoples R China George Washington Univ Dept Comp Sci Washington DC 20052 USA China Univ Petr Coll Informat & Control Engn Qingdao 266510 Peoples R China Univ Washington Sch Engn & Technol Seattle WA 98195 USA

Link scheduling plays a key role in the network capacity and the transmission delay. In this paper, we study the problem of maximum link scheduling (MLS), aiming to characterize the maximum number of links that can be successfully scheduled simultaneously under Rayleigh-fading and multiuser interference. After analyzing the minimum distance between successful links in the existing GHW scheduling algorithm, we propose a DLS (Distance-based Link Scheduling) algorithm. Then, the global interference is characterized and bounded by introducing a separation distance between selected links, building on which we propose a distributed version of DLS (denoted by DDLS) that converges to a constant factor of the non-fading optimum within time complexity O(n\ln n) , where n is the number of links. Furthermore, we study the Shortest Link Scheduling (SLS) problem, which minimizes the number of time slots to successfully schedule each link for at least once. An algorithm for SLS with approximation factor of O(\ln n) is obtained by executing DDLS. Extensive simulations show that DDLS greatly outperforms GHW and the other two popular algorithms.

关键词： Wireless network link scheduling Rayleigh-fading interference model distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

Inference Under Information Constraints II: Communication Constraints and Shared Randomness

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2020年第12期66卷 7856-7877页

作者： Acharya, Jayadev Canonne, Clement L. Tyagi, Himanshu Cornell Univ Dept Elect & Comp Engn Ithaca NY 14853 USA IBM Res Almaden CA 95120 USA Indian Inst Sci Dept Elect Commun Engn Bangalore 560012 Karnataka India

A central server needs to perform statistical inference based on samples that are distributed over multiple users who can each send a message of limited length to the center. We study problems of distribution learning and identity testing in this distributed inference setting and examine the role of shared randomness as a resource. We propose a general-purpose simulate-and-infer strategy that uses only private-coin communication protocols and is sample-optimal for distribution learning. This general strategy turns out to be sample-optimal even for distribution testing among private-coin protocols. Interestingly, we propose a public-coin protocol that outperforms simulate-and-infer for distribution testing and is, in fact, sample-optimal. Underlying our public-coin protocol is a random hash that when applied to the samples minimally contracts the chi-squared distance of their distribution to the uniform distribution.

关键词： Protocols Testing Complexity theory Task analysis Switched mode power supplies Estimation Internet of Things Statistical analysis minimax techniques distributed algorithms goodness-of-fit parameter estimation

来源：评论

学校读者我要写书评

暂无评论

Performance evaluation of hybrid crowdsensing systems with stateful CrowdSenSim 2.0 simulator

引用

COMPUTER COMMUNICATIONS 2020年 161卷 225-237页

作者： Montori, Federico Bedogni, Luca Fiandrino, Claudio Capponi, Andrea Bononi, Luciano Univ Bologna Bologna Italy Univ Modena & Reggio Emilia Modena Italy IMDEA Networks Inst Madrid Spain Univ Luxembourg Luxembourg Luxembourg Univ Bologna Dept Comp Sci & Engn Comp Networks Internet Things Wireless & Mobile S Bologna Italy

Mobile crowdsensing (MCS) has become a popular paradigm for data collection in urban environments. In MCS systems, a crowd supplies sensing information for monitoring phenomena through mobile devices. Depending on the degree of involvement of users, MCS systems can be participatory, opportunistic or hybrid, which combines strengths of above approaches. Typically, a large number of participants is required to make a sensing campaign successful which makes impractical to build and deploy large testbeds to assess the performance of MCS phases like data collection, user recruitment, and evaluating the quality of information. Simulations offer a valid alternative. In this paper, we focus on hybrid MCS and extend CrowdSenSim 2.0 in order to support such systems. Specifically, we propose an algorithm for efficient re-route users that would offer opportunistic contribution towards the location of sensitive MCS tasks that require participatory-type of sensing contribution. We implement such design in CrowdSenSim 2.0, which by itself extends the original CrowdSenSim by featuring a stateful approach to support algorithms where the chronological order of events matters, extensions of the architectural modules, including an additional system to model urban environments, code refactoring, and parallel execution of algorithms.

关键词： Mobile crowdsensing Simulation Modeling distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

Alternating Minimization Based First-Order Method for the Wireless Sensor Network Localization Problem

引用

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2020年 68卷 6418-6431页

作者： Gur, Eyal Sabach, Shoham Shtern, Shimrit Technion Israel Inst Technol Fac Ind Engn & Management IL-3200003 Haifa Israel

We propose an algorithm for the Wireless Sensor Network localization problem, which is based on the well-known algorithmic framework of Alternating Minimization. We start with a non-smooth and non-convex minimization, and transform it into an equivalent smooth and non-convex problem, which stands at the heart of our study. This paves the way to a new method which is globally convergent: not only does the sequence of objective function values converge, but the sequence of the location estimates also converges to a unique location that is a critical point of the corresponding (original) objective function. The proposed algorithm has a range of fully distributed to fully centralized implementations, which all have the property of global convergence. The algorithm is tested over several network configurations, and it is shown to produce more accurate solutions within a shorter time relative to existing methods.

关键词： Signal processing algorithms Wireless sensor networks Minimization Convergence Noise measurement Optimization Distance measurement Alternating minimization distributed algorithms global convergence non-convex optimization non-smooth optimization wireless sensor network localization

来源：评论

学校读者我要写书评

暂无评论

Pushing lines helps: Efficient universal centralised transformations for programmable matter

引用

THEORETICAL COMPUTER SCIENCE 2020年 830卷 43-59页

作者： Almethen, Abdullah Michail, Othon Potapov, Igor Univ Liverpool Dept Comp Sci Ashton St Liverpool L69 3BX Merseyside England

In this work, we study a discrete system of entities residing on a two-dimensional square grid. Each entity is modelled as a node occupying a distinct cell of the grid. The set of all nnodes forms initially a connected shape A. Entities are equipped with a linear-strength pushing mechanism that can push a whole line of entities in parallel in a single time-step on one position in a given (one of the four possible) direction of a grid. A target connected shape Bis also provided and the goal is to transformAinto Bvia a sequence of line moves. Existing models based on local movement of individual nodes, such as rotating or sliding a single node, can be shown to be special cases of the present model, therefore their (inefficient, Theta(n(2))-time) universal transformationscarry over. Our main goal is to investigate whether the parallelism inherent in this new type of movement can be exploited for efficient, i.e., sub-quadratic worst-case, transformations. This paper provides several solutions for specific and universal centralised transformations in the context of the new model. In particular we first design O(n logn)-time universal transformation without preserving the connectivity of original shape. Then we focus on transformations which preserve the connectivity of the shape throughout its course and develop an O(n root n)-time transformation for the apparently hard instance of transforming a diagonal Ainto a straight line B. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Programmable matter Transformation Reconfigurable robotics Shape formation Complexity distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

Resilient Containment Control in Adversarial Environment

引用

IEEE TRANSACTIONS ON CONTROL OF NETWORK SYSTEMS 2020年第4期7卷 1951-1959页

作者： Yan, Jiaqi Wen, Changyun Nanyang Technol Univ Sch Elect & Elect Engn Singapore 639798 Singapore

This article considers the problem of containment control in an adversarial environment, where some of the agents might be misbehaving (or faulty). Despite the influence of network misbehaviors, the normal followers aim to move into the convex hull spanned by the normal leaders. Toward this goal, resilient containment control is investigated in this work. We propose secure protocols for both first-order and second-order systems, where each normal follower ignores the most extreme values in its neighborhood and modifies its state based on the remaining ones. Assuming that the number of malicious agents is locally upper bounded, sufficient conditions on the network topology are derived to guarantee the achievement of resilient containment. Numerical examples are also provided in the end to verify our theoretical results.

关键词： Protocols Control systems Security Network topology distributed algorithms Standards Signal processing algorithms Containment control cybersecurity resilient algorithms robust graphs

来源：评论

学校读者我要写书评

暂无评论

Step-by-step community detection in volume-regular graphs

引用

THEORETICAL COMPUTER SCIENCE 2020年 847卷 49-67页

作者： Becchetti, Luca Cruciani, Emilio Pasquale, Francesco Rizzo, Sara Sapienza Univ Roma Rome Italy CNRS UCA Lab I3S INRIA Sophia Antipolis France Univ Roma Tor Vergata Rome Italy Gran Sasso Sci Inst Laquila Italy

Spectral techniques have proved amongst the most effective approaches to graph clustering. However, in general they require explicit computation of the main eigenvectors of a suitable matrix (usually the Laplacian matrix of the graph). Recent work (e.g., Becchetti et al., SODA 2017) suggests that observing the temporal evolution of the power method applied to an initial random vector may, at least in some cases, provide enough information on the space spanned by the first two eigenvectors, so as to allow recovery of a hidden partition without explicit eigenvector computations. While the results of Becchetti et al. apply to perfectly balanced partitions and/or graphs that exhibit very strong forms of regularity, we extend their approach to graphs containing a hidden k partition and characterized by a milder form of volume-regularity. We show that the class of k-volume regular graphs is the largest class of undirected (possibly weighted) graphs whose transition matrix admits k "stepwise" eigenvectors (i.e., vectors that have constant entries over the components corresponding to the same set of the hidden partition). To obtain this result, we highlight a connection between volume regularity and lumpability of Markov chains. Moreover, we prove that if the stepwise eigenvectors are those associated to the first k largest eigenvalues of the transition matrix of a random walk on the graph and the gap between the k-th and the (k + 1)-th eigenvalues is sufficiently large, the AVERAGING dynamics of Becchetti et al. recovers the underlying community structure of the graph in logarithmic time, with high probability. (C) 2020 Elsevier B.V. All rights reserved.

关键词： distributed algorithms Community detection Markov chains Spectral analysis

来源：评论

学校读者我要写书评

暂无评论

Learning to Coordinate in a Decentralized Cognitive Radio Network in Presence of Jammers

引用

IEEE TRANSACTIONS ON MOBILE COMPUTING 2020年第11期19卷 2640-2655页

作者： Sawant, Suneet Kumar, Rohit Hanawal, Manjesh K. Darak, Sumit J. Indian Inst Technol Dept Elect Engn Mumbai 400076 Maharashtra India Natl Inst Technol Dept ECE Delhi 110040 India Indian Inst Technol IEOR Mumbai 400076 Maharashtra India Indraprastha Inst Informat Technol Dept ECE Delhi 110020 India

Efficient utilization of licensed spectrum in the cognitive radio network is challenging due to lack of coordination among the Secondary Users (SUs). distributed algorithms proposed in the literature aim to maximize the network throughput by ensuring orthogonal channel allocation for the SUs. However, these algorithms work under the assumption that all the SUs faithfully follow the algorithms which may not always hold due to the decentralized nature of the network. In this paper, we study distributed algorithms that are robust against malicious behavior (jamming attack). We consider both the cases of jammers launching coordinated and uncoordinated attacks. In the coordinated attack, the jammers select non-overlapping channels to attack in each time slot and can significantly increase the number of collisions for SUs. We setup the problem in each scenario as a multi-player bandit and develop algorithms. The analysis shows that when the SUs faithfully implement proposed algorithms, the regret is constant with high probability. We validate our claims through exhaustive synthetic experiments and also through a realistic USRP based experiment.

关键词： Jamming Channel estimation Signal processing algorithms distributed algorithms Channel allocation Knowledge engineering Throughput Cognitive radio network jamming attack distributed learning

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：