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

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Joint Incentive and Resource Allocation Design for User Provided Network Under 5G Integrated Access and Backhaul Networks

引用

IEEE TRANSACTIONS ON NETWORK SCIENCE AND ENGINEERING 2020年第2期7卷 673-685页

作者： Liu, Yao Tang, Aimin Wang, Xudong Shanghai Jiao Tong Univ Univ Michigan Shanghai Jiao Tong Univ Joint Inst Shanghai 200240 Peoples R China

User provided network (UPN) allows a user with high channel quality to share the network access for users with poor channel quality. As a result, both the quality of experience and efficiency of network resource can be improved by UPN. However, the success of UPN relies heavily on the willingness of users to participate in sharing, so the design of incentive mechanisms is critical for UPN. In this paper, the UPN formed by D2D links under 5G integrated access and backhaul (IAB) networks is considered. In IAB networks, both access and backhaul links use wireless transmissions and dynamically share all the spectrum resources. Thus, the resource allocation for all the links also has a great impact on the UPN efficiency. To this end, a novel joint incentive and resource allocation design is explored. More specifically, considering the fairness between users, a Nash bargaining problem as a cooperative game is formulated by considering the user utility, the sensitivity of battery energy, the incentive compensation, and the limitation of network resources. To achieve the optimal Nash bargaining solution, a centralized algorithm is first designed, in which all the user information is collected by the operator for conducting centralized optimization. Thus, the centralized algorithm leads to a privacy problem. To this end, a distributed algorithm is developed to decompose the primal problem into subproblems for the operator and each user. By passing intermediate parameters between users and iterative execution of subproblems, the solution of the distributed algorithm is proved to converge to the optimal solution of the centralized algorithm. Extensive numerical results have been conducted to show that our design can effectively improve both the user experience and network throughput, i.e., operator's revenue.

关键词： Resource management 5G mobile communication Device-to-device communication Wireless communication distributed algorithms Mesh networks Cellular networks User provided network integrated access and backhaul incentive mechanism bargain

来源：评论

学校读者我要写书评

暂无评论

Combining Contract Theory and Lyapunov Optimization for Content Sharing With Edge Caching and Device-to-Device Communications

引用

IEEE-ACM TRANSACTIONS ON NETWORKING 2020年第3期28卷 1213-1226页

作者： Asheralieva, Alia Niyato, Dusit Southern Univ Sci & Technol Dept Comp Sci & Engn Shenzhen 518055 Peoples R China Nanyang Technol Univ Sch Comp Sci & Engn Singapore 639798 Singapore

The paper proposes a novel framework based on the contract theory and Lyapunov optimization for content sharing in a wireless content delivery network (CDN) with edge caching and device-to-device (D2D) communications. The network is partitioned into a set of clusters. In a cluster, users can share contents via D2D links in coordination with the cluster head. Upon receiving the content request from any user in its cluster, the cluster head either delivers the content itself or forwards the request to another node, i.e., a base station (BS) or another user in the cluster. The content access at the BS and in each cluster is modeled as a queuing system, where arrivals represent the content requests directed to respective nodes. The objective is to assign content delivery nodes to stabilize all queues while minimizing the time-averaged network cost given incomplete information about content sharing costs of the users and unknown distribution of the network state defined by users' locations and their cached/requested content. The proposed framework allows the users to truthfully reveal their content sharing expenditures, minimize the time-averaged network cost and stabilize the queuing system representing the CDN. Based on this framework, a distributed content access and delivery algorithm where the node assignments are made by every cluster head independently is developed. It is shown that the algorithm converges to the optimal policy with the trade-off in total queue backlog and achieves a superior performance compared with some other D2D content sharing policies.

关键词： Device-to-device communication Contracts Wireless communication Optimization Stochastic processes Computational modeling Clustering algorithms Content sharing contract theory device-to-device communication distributed algorithms dynamic spectrum access incomplete information Lyapunov optimization stochastic network control

来源：评论

学校读者我要写书评

暂无评论

Multi-Layer Decomposition of Network Utility Maximization Problems

引用

IEEE-ACM TRANSACTIONS ON NETWORKING 2020年第5期28卷 2077-2091页

作者： Karakoc, Nurullah Scaglione, Anna Nedic, Angelia Reisslein, Martin Arizona State Univ Sch Elect Comp & Energy Engn Tempe AZ 85287 USA

We describe a distributed framework for resource sharing problems that arise in communications, micro-economics, and various networking applications. In particular, we consider a hierarchical multi-layer decomposition for network utility maximization (ML-NUM), where functionalities are assigned to different layers. The proposed methodology creates solutions with central management and distributed computations to the resource allocation problems. In non-stationary environments, the technique aims to respond quickly to the dynamics of the network by decreasing delay by partially shifting the communication and computational burden to the network edges. Our main contribution is a detailed analysis under the assumption that the network changes are on the same time-scale as the convergence time of the algorithms used for local computations. Moreover, assuming strong concavity and smoothness of the users' objective functions, and under some stability conditions for each layer, we present convergence rates and optimality bounds for the ML-NUM framework. In addition, the main benefits of the proposed method are demonstrated with numerical examples.

关键词： Resource management Convergence Heuristic algorithms Indexes Gradient methods distributed algorithms IEEE transactions distributed computation network resource allocation

来源：评论

学校读者我要写书评

暂无评论

Sparse matrix multiplication and triangle listing in the Congested Clique model

引用

THEORETICAL COMPUTER SCIENCE 2020年 809卷 45-60页

作者： Censor-Hillel, Keren Leitersdorf, Dean Turner, Elia Technion Dept Comp Sci Haifa Israel

We show how to multiply two n x n matrices S and T over semirings in the CONGESTED CLIQUE model, where n nodes communicate in a fully connected synchronous network using O(log n)-bit messages, within O (nz(S)(1/3) nz(T)(1/3)/n + 1) rounds of communication, where nz(S) and nz(T) denote the number of non-zero elements in S and T. respectively. By leveraging the sparsity of the input matrices, our algorithm greatly reduces communication costs compared with general multiplication algorithms [Censor-Hillel et al. (2015) [9]], and thus improves upon the state-of-the-art for matrices with o(n(2)) non-zero elements. Moreover, our algorithm exhibits the additional strength of surpassing previous solutions also in the case where only one of the two matrices is such. Particularly, this allows to efficiently raise a sparse matrix to a power greater than 2. As applications, we show how to speed up the computation on non-dense graphs of 4-cycle counting and all-pairs-shortest-paths. Our algorithmic contribution is a new deterministic method of restructuring the input matrices in a sparsity-aware manner, which assigns each node with element-wise multiplication tasks that are not necessarily consecutive but guarantee a balanced element distribution, providing for communication-efficient multiplication. Moreover, this new deterministic method for restructuring matrices may be used to restructure the adjacency matrix of input graphs, enabling faster deterministic solutions for graph related problems. As an example, we present a new sparsity aware, deterministic algorithm which solves the triangle listing problem in O (m/n(5/3) + 1) rounds, a complexity that was previously obtained by a randomized algorithm [Pandurangan et al. (2018) [26]] and that matches the known lower bound of (Omega) over bar (n(1/3)) when m = n(2) of [Izumi and Le Gall (2017) [19], Pandurangan et al. (2018) [26]]. Naturally, our triangle listing algorithm also implies triangle counting within the same complexity

关键词： distributed algorithms Congested clique Matrix multiplication Triangle listing

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：