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

distributed link scheduling in wireless networks

DISCRETE MATHEMATICS algorithmS AND APPLICATIONS 2020年第5期12卷

作者： Bermond, Jean-Claude Mazauric, Dorian Misra, Vishal Nain, Philippe Univ Cote Azur CNRS Inria I3S 2004 Route LuciolesBP 93 F-06902 Sophia Antipolis France Columbia Univ Dept Comp Sci New York NY 10027 USA ENS Lyon LIP INRIA 46 Ave Italie F-69364 Lyon France

This work investigates distributed transmission scheduling in wireless networks. Due to interference constraints, "neighboring links" cannot be simultaneously activated, otherwise transmissions will fail. Here, we consider any binary model of interference. We use the model described by Bui et al. in [L. X. Bui, S. Sanghavi and R. Srikant, distributed link scheduling with constant overhead, IEEE/ACM Trans. Netw. 17(5) (2009) 1467-1480;S. Sanghavi, L. Bui and R. Srikant, distributed link scheduling with constant overhead, in Proc. ACM Sigrnetrics (San Diego, CA, USA, 2007), pp. 313-324.1. We assume that time is slotted and during each slot there are two phases: one control phase in which a link scheduling algorithm determines a set of non-interfering links to be activated, and a data phase in which data is sent through these links. We assume random arrivals on each link during each slot, so that a queue is associated to each link. Since nodes do not have a global knowledge of the queues sizes, our aim (like in [L. X. Bui, S. Sanghavi and R. Srikant, distributed link scheduling with constant overhead, IEEE/ACM Trans. Netw. 17(5) (2009) 1467-1480;S. Sanghavi, L. Bui and R. Srikant, distributed link scheduling with constant overhead, in Proc. ACM Sigmetrics (San Diego, CA, USA, 2007), pp. 313-324.]) is to design a distributed link scheduling algorithm. To be efficient, the control phase should be as short as possible;this is done by exchanging control messages during a constant number of mini-slots (constant overhead). In this paper, we design the first fully distributed local algorithm with the following properties: it works for any arbitrary binary interference model;it has a constant overhead (independent of the size of the network and the values of the queues), and it does not require any knowledge of the queue-lengths. We prove that this algorithm gives a maximal set of active links, where for any non-active link there exists at least one active link in its interfer

关键词： Wireless network link scheduling algorithm binary interference distributed algorithm stability graph

来源：评论

学校读者我要写书评

暂无评论

Competition-based distributed BS Power Activation and User Scheduling algorithm

引用

JOURNAL OF COMMUNICATIONS AND NETWORKS 2017年第1期19卷 41-50页

作者： Lee, Changsik Kim, Jihwan Kwak, Jeongho Kim, Eunkyung Chong, Song Korea Adv Inst Sci & Technol Sch Elect Engn Daejeon South Korea ETRI Daejeon South Korea Samsung Elect Suwon South Korea Inst Rech Sci INRS Place Bonaventure 800Bur 6900 Montreal PQ H5A 1K6 Canada

Existing cellular technologies in unlicensed band such as license assisted access (LAA)-LTE do not capture inter-cell interference (ICI) management which becomes more important in modern small cell network environments. Moreover, existing ICI management techniques not only can be operated in only licensed frequency band due to their centralized properties, but also have high computational complexities. In this paper, by invoking distributed optimization, we propose a fully distributed base station (BS) activation and user scheduling framework which can be operated in even unlicensed band because of its competition properties. Our simulation results demonstrate that (i) proposed competition-based BS activation and user scheduling framework (CBA) increases throughput of cell edge users by 112%-335% compared to conventional algorithms, (ii) the CBA properly catches up with the performance of optimal algorithm up to 93% in terms of overall performance and up to 95% in terms of edge user throughput, and (iii) the CBA also provides higher performance gains in the larger ratio of edge users and the smaller cell size, which indicates that the CBA well adapts to cellular network trend where cells are gradually smaller and densely deployed.

关键词： distributed algorithm edge user inter-cell interference small cell transmit power activation control user scheduling

来源：评论

学校读者我要写书评

暂无评论

Deterministic scaffold assembly by self-reconfiguring micro-robotic swarms

引用

SWARM AND EVOLUTIONARY COMPUTATION 2020年 58卷 100722-100722页

作者： Thalamy, Pierre Piranda, Benoit Lassabe, Frederic Bourgeois, Julien Univ Bourgogne Franche Comte CNRS FEMTO ST Inst 1 Cours Leprince Ringuet F-25200 Montbeliard France

The self-reconfiguration of large swarms of modular robotic units from one object into another is an intricate problem whose critical parameter that must be optimized is the time required to perform a transformation. Various optimizations methods have been proposed to accelerate transformations, as well as techniques to engineer the shape itself, such as scaffolding which creates an internal object structure filled with holes for easing the motion of modules. In this paper, we propose a novel deterministic and distributed method for rapidly constructing the scaffold of an object from an organized reserve of modules placed underneath the reconfiguration scene. This innovative scaffold design is parameterizable and has a face-centered-cubic lattice structure made from our rotating-only micro-modules. Our method operates at two levels of planning, scheduling the construction of components of the scaffold to avoid deadlocks at one level, and handling the navigation of modules and their coordination to avoid collisions in the other. We provide an analysis of the method and perform simulations on shapes with an increasing level of intricacy to show that our method has a reconfiguration time complexity of O((3)root N) time steps for a subclass of convex shapes, with N the number of modules in the shape. We then proceed to explain how our solution can be further extended to any shape.

关键词： Modular robotic swarm Self-reconfiguration Large-scale swarm coordination distributed algorithm Scaffolding

来源：评论

学校读者我要写书评

暂无评论

AN EXPONENTIAL SEPARATION BETWEEN RANDOMIZED AND DETERMINISTIC COMPLEXITY IN THE LOCAL MODEL

引用

SIAM JOURNAL ON COMPUTING 2019年第1期48卷 122-143页

作者： Chang, Yi-Jun Kopelowitz, Tsvi Pettie, Seth Univ Michigan EECS Ann Arbor MI 48105 USA Bar Ilan Univ Comp Sci IL-5290002 Ramat Gan Israel

Over the past 30 years numerous algorithms have been designed for symmetry breaking problems in the LOCAL model, such as maximal matching, MIS, vertex coloring, and edge coloring. For most problems the best randomized algorithm is at least exponentially faster than the best deterministic algorithm. In this paper we prove that these exponential gaps are necessary and establish numerous connections between the deterministic and randomized complexities in the LOCAL model. Each of our results has a very compelling take-away message: Fast Delta-coloring of trees requires random bits. Building on a recent randomized lower bound of Brandt et al. [A lower bound for the distributed Lovasz local lemma, in Proceedings of the 48th ACM Symposium on Theory of Computing (STOC), ACM, New York, 2016, pp. 479-488], we prove that the randomized complexity of Delta-coloring a tree with maximum degree Delta is O(log(Delta) log n + log* n) for any Delta >= 55, whereas its deterministic complexity is Omega(log(Delta) n) for any Delta >= 3. This also establishes a large separation between the deterministic complexity of Delta-coloring and (Delta+1)-coloring trees. There is a gap in the deterministic complexity hierarchy. We show that any deterministic algorithm for a natural class of problems that runs in O(1) + o(log(Delta) n) rounds can be transformed to run in O(log*n - log* Delta + 1) rounds. If the transformed algorithm violates a lower bound (even allowing randomization), then one can conclude that the problem requires Omega(log(Delta) n) time deterministically. This gives an alternate proof that deterministically Delta-coloring a tree with small Delta takes Omega(log(Delta) n) rounds. Graph shattering is necessary. We prove that the randomized complexity of any natural problem on instances of size n is at least its deterministic complexity on instances of size root logn. This shows that any randomized O(1)+o(log(Delta) log n)-round algorithm can be derandomized to run in determinist

关键词： coloring distributed algorithm local model symmetry breaking

来源：评论

学校读者我要写书评

暂无评论

Information Value on Private State Inference in Network Systems

引用

IFAC-PapersOnLine 2020年第2期53卷 3457-3462页

作者： Hao Jiang Xuda Ding Jianping He Yunfeng Peng The Dept. of Automation Shanghai Jiao Tong University and the Key Laboratory of System Control and Information Processing Ministry of Education of China Shanghai China 200240

In network systems, neighboring nodes usually need to exchange and update their state information iteratively to achieve a global computation and control goal. Considering the nodes’ states may include some sensitive/private information, e.g., location and income, different random mechanizes have been proposed to preserve the privacy of the states. However, no matter what type of random mechanisms is used, the eavesdropping attacker can infer/estimate a node’s state based on the information it holds, and the estimation depends on the available information. The relationship between the estimation and the information is a critical and open issue. Therefore, in this paper, we investigate how to obtain the optimal estimation of a node’s state with available information and how to quantify the value of the information in the state inference. First, we exploit a utility function to quantify the utility of the estimation accuracy, and then the optimal estimation and information value are defined to depict the estimation and quantify the information, respectively. Next, the optimal estimation under different settings of the noise and utility function is provided. Lastly, we obtain some essential properties of information value and analyze the value of state outputs in distributed algorithms.

关键词： distributed algorithm Noise adding process Optimal estimation Data privacy Average consensus

来源：评论

学校读者我要写书评

暂无评论

Unifying Concurrent Objects and distributed Tasks: Interval-Linearizability

引用

JOURNAL OF THE ACM 2018年第6期65卷 45.1-45.42页

作者： Castaneda, Armando Rajsbaum, Sergio Raynal, Michel Univ Nacl Autonoma Mexico Inst Matemat Mexico City DF Mexico Univ Rennes IRISA F-35042 Rennes France Hong Kong Polytech Univ Hong Kong Peoples R China Inst Matemat Ciudad De Mexico 04510 Mexico

Tasks and objects are two predominant ways of specifying distributed problems where processes should compute outputs based on their inputs. Roughly speaking, a task specifies, for each set of processes and each possible assignment of input values, their valid outputs. In contrast, an object is defined by a sequential specification. Also, an object can be invoked multiple times by each process, while a task is a one-shot problem. Each one requires its own implementation notion, stating when an execution satisfies the specification. For objects, linearizability is commonly used, while tasks implementation notions are less explored. The article introduces the notion of interval-sequential object, and the corresponding implementation notion of interval-linearizability, to encompass many problems that have no sequential specification as objects. It is shown that interval-sequential specifications are local, namely, one can consider interval-linearizable object implementations in isolation and compose them for free, without sacrificing interval-linearizability of the whole system. The article also introduces the notion of refined tasks and its corresponding satisfiability notion. In contrast to a task, a refined task can be invoked multiple times by each process. Also, objects that cannot be defined using tasks can be defined using refined tasks. In fact, a main result of the article is th at interval-sequential objects and refined tasks have the same expressive power and both are complete in the sense that they are able to specify any prefix-closed set of well-formed executions. Interval-linearizability and refined tasks go beyond unifying objects and tasks;they shed new light on both of them. On the one hand, interval-linearizability brings to task the following benefits: an explicit operational semantics, a more precise implementation notion, a notion of state, and a locality property. On the other hand, refined tasks open new possibilities of applying topological tech

关键词： Asynchronous system concurrency concurrent object distributed algorithm distributed task linearizability object composability non-determinism process crash sequential specification set-linearizability

来源：评论

学校读者我要写书评

暂无评论

A STUDY ON THE ERROR OF distributed algorithmS FOR BIG DATA CLASSIFICATION WITH SVM

引用

ANZIAM JOURNAL 2017年第3-4期58卷 231-237页

作者： Wang, Cheng Cao, Feilong China Jiliang Univ Appl Math Dept Hangzhou Zhejiang Peoples R China

The error of a distributed algorithm for big data classification with a support vector machine (SVM) is analysed in this paper. First, the given big data sets are divided into small subsets, on which the classical SVM with Gaussian kernels is used. Then, the classification error of the SVM for each subset is analysed based on the Tsybakov exponent, geometric noise, and width of the Gaussian kernels. Finally, the whole error of the distributed algorithm is estimated in terms of the error of each subset.

关键词： distributed algorithm big data support vector machine Tsybakov exponent geometric noise exponent

来源：评论

学校读者我要写书评

暂无评论

distributed Event Localization via Alternating Direction Method of Multipliers

引用

IEEE TRANSACTIONS ON MOBILE COMPUTING 2018年第2期17卷 348-361页

作者： Zhang, Chunlei Wang, Yongqiang Clemson Univ Dept Elect & Comp Engn Clemson SC 29634 USA

This paper addresses the problem of distributed event localization using noisy range measurements with respect to sensors with known positions. Event localization is fundamental in many wireless sensor network applications such as homeland security, law enforcement, and environmental studies. However, most existing distributed algorithms require the target event to be within the convex hull of the deployed sensors. Based on the alternating direction method of multipliers (ADMM), we propose two scalable distributed algorithms named GS-ADMM and J-ADMM which do not require the target event to be within the convex hull of the deployed sensors. More specifically, the two algorithms can be implemented in a scenario in which the entire sensor network is divided into several clusters with cluster heads collecting measurements within each cluster and exchanging intermediate computation information to achieve localization consistency (consensus) across all clusters. This scenario is important in many applications such as homeland security and law enforcement. Simulation results confirm effectiveness of the proposed algorithms.

关键词： Event localization wireless sensor network distributed algorithm

来源：评论

学校读者我要写书评

暂无评论

Stochastic mirror descent method for distributed multi-agent optimization

引用

OPTIMIZATION LETTERS 2018年第6期12卷 1179-1197页

作者： Li, Jueyou Li, Guoquan Wu, Zhiyou Wu, Changzhi Chongqing Normal Univ Sch Math Sci Chongqing 400047 Peoples R China Univ Sydney Sch Elect & Informat Engn Sydney NSW 2006 Australia Curtin Univ Sch Built Environm Bentley WA 6102 Australia

This paper considers a distributed optimization problem encountered in a time-varying multi-agent network, where each agent has local access to its convex objective function, and cooperatively minimizes a sum of convex objective functions of the agents over the network. Based on the mirror descent method, we develop a distributed algorithm by utilizing the subgradient information with stochastic errors. We firstly analyze the effects of stochastic errors on the convergence of the algorithm and then provide an explicit bound on the convergence rate as a function of the error bound and number of iterations. Our results show that the algorithm asymptotically converges to the optimal value of the problem within an error level, when there are stochastic errors in the subgradient evaluations. The proposed algorithm can be viewed as a generalization of the distributed subgradient projection methods since it utilizes more general Bregman divergence instead of the Euclidean squared distance. Finally, some simulation results on a regularized hinge regression problem are presented to illustrate the effectiveness of the algorithm.

关键词： distributed algorithm Multi-agent network Mirror descent Stochastic approximation Convex optimization

来源：评论

学校读者我要写书评

暂无评论

Verification of an Industrial Asynchronous Leader Election algorithm Using Abstractions and Parametric Model Checking 1

引用

International Conference on Verification, Model Checking, and Abstract Interpretation (VMCAI)

作者： Andre, Etienne Fribourg, Laurent Mota, Jean-Marc Soulat, Romain Univ Paris 13 LIPN CNRS UMR 7030 F-93430 Villetaneuse France CNRS JFLI Tokyo Japan Natl Inst Informat Tokyo Japan Univ Paris Saclay LSV ENS Paris Saclay Paris France Univ Paris Saclay CNRS Paris France Univ Paris Saclay INRIA Paris France Thales Res & Technol Palaiseau France

ISBN: (数字)9783030112455

ISBN: (纸本)9783030112455;9783030112448

The election of a leader in a network is a challenging task, especially when the processes are asynchronous, i. e., execute an algorithm with time-varying periods. Thales developed an industrial election algorithm with an arbitrary number of processes, that can possibly fail. In this work, we prove the correctness of a variant of this industrial algorithm. We use a method combining abstraction, the SafeProver solver, and a parametric timed model-checker. This allows us to prove the correctness of the algorithm for a large number p of processes (p = 5000).

关键词： Leader election distributed algorithm Model checking SaveProver Parameterized verification Parametric timed automata

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：