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

Forwarding Set Based distributed algorithm for Connected Dominating Set in WSN

SENSOR LETTERS 2012年第8期10卷 1918-1924页

作者： Tang, Yong Zhang, Jun Wang, Wenyong Xiang, Yu Zhang, Jun Univ Elect Sci & Technol China Sch Comp Sci & Engn Chengdu 611731 Peoples R China

In wireless sensor networks, virtual backbone network is an important approach to reduce reduplicate data transmission, save energy and bandwidth. Constructing a virtual backbone is identical with calculating connected dominating set, which is a NP-complete problem in graph theory. An algorithm using only 1-hop neighbor's information to attain CDS, named FWCDS (Forwarding set based distributed algorithm for Connected Dominating Set), is proposed in this paper. FWCDS algorithm is an enhancement of OHDC algorithm. There are two stages in the calculating process of our algorithm. In the first stage each node calculates the forwarding set severally. In the second stage, each node in the forwarding set determines whether it is a dominating node. Simulation results show that less extra messages and less convergence time is achieved by the algorithm with smaller CDS size.

关键词： Forwarding Set Connected Dominating Set distributed algorithm

来源：评论

学校读者我要写书评

暂无评论

distributed Nash Equilibrium Seeking for Quadratic Games with Security

引用

INTERNATIONAL JOURNAL OF COOPERATIVE INFORMATION SYSTEMS 2019年第4期28卷

作者： Zhang, Shouwei Liang, Shu Changchun Univ Technol Inst Informat Spreading Engn Changchun 130012 Jilin Peoples R China Univ Sci & Technol Beijing Key Lab Knowledge Automat Ind Proc Minist Educ Sch Automat & Elect Engn Beijing 100083 Peoples R China

Considering a game with quadratic cost functions, this paper presents a distributed algorithm with security, whereby each player updates its strategy variable without. using its private data and still achieves the Nash equilibrium. By using the theory of differential inclusions, Lyapunov function and invariance principle, the algorithm is proved to be convergent. Our algorithm can be used when it is required to seek the Nash equilibrium without disclosure of private data.

关键词： distributed algorithm Nash equilibrium game theory security continuous-time algorithm differential inclusion convergence analysis

来源：评论

学校读者我要写书评

暂无评论

Discrete-time algorithm for distributed Nash Equilibrium Seeking of A Class of Aggregative Games 36

Discrete-time Algorithm for Distributed Nash Equilibrium See...

引用

第36届中国控制会议

作者： Lingfei Wang Shu Liang Yiguang Hong NKU School of Mathematical Sciences Tianjin Key Laboratory of Systems and Control Institute of Systems ScienceChinese Academy of Sciences

ISBN: (纸本)9781538629185

In this paper,we investigate a distributed Nash equilibrium seeking problem for aggregative games with nonlinear aggregation *** our game model,the strategic interaction is associated with a sum of heterogeneous nonlinear mapping of local decisions,and the local cost functions are non-quadratic with the decision variables limited in local constraint *** propose a novel discrete-time distributed equilibrium seeking algorithm based on dynamic average consensus protocal and projected gradient *** virtue of variational inequalities and Lyapunov functions,we show that the algorithm can achieve the Nash equilibrium for the distributed aggregative game.

关键词： distributed algorithm Aggregative game Nash equilibrium Discrete-time algorithm

来源：评论

学校读者我要写书评

暂无评论

DFPS: distributed FP-growth algorithm Based on Spark 2

DFPS: Distributed FP-growth Algorithm Based on Spark

引用

2nd IEEE Advanced Information Technology, Electronic and Automation Control Conference (IAEAC)

作者： Shi, Xiujin Chen, Shaozong Yang, Hui Donghua Univ CST Shanghai Peoples R China

ISBN: (纸本)9781467389792

Frequent Itemset Mining (FIM) is the most important and time-consuming step of association rules mining. With the increment of data scale, many efficient single-machine algorithms of FIM, such as FP-growth and Apriori, cannot accomplish the computing tasks within reasonable time. As a result of the limitation of single-machine methods, researchers presented some distributed algorithms based on MapReduce and Spark, such as PFP and YAFIM. Nevertheless, the heavy disk I/O cost at each MapReduce operation makes PFP not efficient enough. YAFIM needs to generate candidate frequent itemsets in each iterative step. It makes YAFIM time-consuming. And if the scale of data is large enough, YAFIM algorithm will not work due to the limitation of memory since the candidate frequent itemsets need to be stored in the memory. And the size of candidate itemsets is very large especially facing the massive data. In this work, we propose a distributed FP-growth algorithm based on Spark, we call it DFPS. DFPS partitions computing tasks in such a way that each computing node builds the conditional FP-tree and adopts a pattern fragment growth method to mine the frequent itemsets independently. DFPS doesn't need to pass messages between nodes during mining frequent itemsets. Our performance study shows that DFPS algorithm is more excellent than YAFIM, especially when the length of transactions is long, the number of items is large and the data is massive. And DFPS has an excellent scalability. The experimental results show that DFPS is more than 10 times faster than YAFIM for T10I4D100K dataset and Pumsb_star dataset.

关键词： frequent itemset mining association rules mining FP-growth Spark RDD Big Data distributed algorithm

来源：评论

学校读者我要写书评

暂无评论

Study on Stocks Based on Big Data Methods and Computer Programs

Study on Stocks Based on Big Data Methods and Computer Progr...

引用

Image Processing, Electronics and Computers (IPEC), Asia-Pacific Conference on

作者： Cheng Wang Hailei Zou Juncheng Yin Applied Math Dept China Jiliang Univ. Hang Zhou City China

ISBN: (数字)9781728160672

ISBN: (纸本)9781728160689

Recently big data is a hot topic in many fields. Here we use distributed algorithms to treat big data in Chinese stock market. First the two stock indexes (Shanghai Composite and Shenzhen Composite indexes) from 1990-2019 are collected. Then the data are divided to several subsets and are analyzed separately via computer programs. Finally the results for every subset are combined due to distributed algorithms theory. In addition to big data scheme, we adopt stochastic processes theory and moment equations methods.

关键词： distributed algorithm Big data Lèvy processes Chinese stock index Moment estimations Lè vy processes big data distributed algorithms stocks Computers

来源：评论

学校读者我要写书评

暂无评论

Context-Aware and Energy-Efficient Protocol for the distributed Wireless Sensor Networks 28

Context-Aware and Energy-Efficient Protocol for the Distribu...

引用

28th International Telecommunication Networks and Applications Conference (ITNAC)

作者： Chen, Da-Ren Hsu, Ming-Yang Chang, Hao-Yen Natl Taichung Univ Sci & Technol Taichung 404 Taiwan

ISBN: (纸本)9781538671771

Wireless sensor network (WSNs) are composed of a large number of battery-powered wireless sensors, which acquire and monitor physical data from their surroundings through self-organization. Sensors are deployed randomly in a target area where maintenance and battery replacement are difficult or even impossible. To effectively save energy and prolong network lifetimes, networks typically adopt clustering protocols with hierarchical inter-cluster topologies for network management and data acquisition in WSNs. However, such solutions require cluster re-configuration due to early death of cluster heads (CHs) and energy inefficiency. This paper proposes a coverage- and energy-aware protocol with intra- and inter-cluster methods called CEMST based on newly defined parameters for sensor overlapping and node density functions. In addition, to adapt network dynamics while improving energy efficiency, a self-stabilizing algorithm is proposed with the Boruvka algorithm to respectively construct minimum spanning trees (MST) for intra- and inter-cluster routes. Simulation results indicate that CEMST yields more balanced clustering structures than previous efficient protocols, and provides longer network lifetime than those methods.

关键词： Wireless sensor networks residual energy Dijkstra's algorithm minimum spanning tree Boruvkaalgorithm distributed algorithm self-stabilizing algorithm

来源：评论

学校读者我要写书评

暂无评论

distributed algorithms for searching generalized Nash equilibrium of non-cooperative games

Distributed algorithms for searching generalized Nash equili...

引用

2017中国智能物联系统会议

作者： LU Kaihong JING Gangshan School of Mechano-Electronic Engineering Xidian UniversityXi'an710071P.R.China

In this paper,the distributed Nash equilibrium searching problem of a game is investigated,where the feasible action sets are constrained by nonlinear inequalities and linear *** from most of the existing investigations on distributed Nash equilibrium searching problems,we consider the case where both cost functions and feasible action sets depend on actions of all players,and each player can only have access to the information of its *** address this problem,a continuous-time distributed gradient-based projected algorithm is proposed,where a leader-following consensus algorithm is employed for each player to estimate actions of *** mild assumptions on cost functions and graphs,it is shown that players' actions asymptotically converge to a generalized Nash *** examples are presented to demonstrate the effectiveness of the theoretical results.

关键词： Nash equilibrium distributed algorithm Consensus Non-cooperative game

来源：评论

学校读者我要写书评

暂无评论

Local Mixing Time: distributed Computation and Applications 32

Local Mixing Time: Distributed Computation and Applications

引用

32nd IEEE International Parallel and distributed Processing Symposium (IPDPS)

作者： Molla, Anisur Rahaman Pandurangan, Gopal NISER Bhubaneswar Sch Comp Sci Bhubaneswar 752050 Odisha India Univ Houston Dept Comp Sci Houston TX 77204 USA

ISBN: (纸本)9781538643686

The mixing time of a graph is an important metric, which is not only useful in analyzing connectivity and expansion properties of the network, but also serves as a key parameter in designing efficient algorithms. We introduce a new notion of mixing of a random walk on a (undirected) graph, called local mixing. Informally, the local mixing with respect to a given node s, is the mixing of a random walk probability distribution restricted to a large enough subset of nodes - say, a subset of size at least n/beta for a given parameter beta - containing s. The time to mix over such a subset by a random walk starting from a source node s is called the local mixing time with respect to s. The local mixing time captures the local connectivity and expansion properties around a given source node and is a useful parameter that determines the running time of algorithms for partial information spreading, gossip etc. Our first contribution is formally defining the notion of local mixing time in an undirected graph. We then present an efficient distributed algorithm which computes a constant factor approximation to the local mixing time with respect to a source node s in (O) over tilde (tau(s)) rounds(1), where tau(s) is the local mixing time w.r.t s in an n-node regular graph. This bound holds when tau(s) is significantly smaller than the conductance of the local mixing set (i.e., the set where the walk mixes locally);this is typically the interesting case where the local mixing time is significantly smaller than the mixing time (with respect to s). We also present a distributed algorithm that computes the exact local mixing time in (O) over tilde (tau D-s) rounds, where D - min{tau(s), D} and D is the diameter of the graph (this bound holds unconditionally without any assumptions on tau(s)). Our algorithms work in the CONGEST model of distributed computing. Since the local mixing time can be significantly smaller than the mixing time (or even the diameter) in many graphs, it serv

关键词： distributed algorithm random walk mixing time conductance weak-conductance information spreading

来源：评论

学校读者我要写书评

暂无评论

PROVABLY COMMUNICATION-EFFICIENT ASYNCHRONOUS distributed INFERENCE FOR CONVEX AND NONCONVEX PROBLEMS

PROVABLY COMMUNICATION-EFFICIENT ASYNCHRONOUS DISTRIBUTED IN...

引用

IEEE Global Conference on Signal and Information Processing (GlobalSIP)

作者： Ren, Jineng Haupt, Jarvis Univ Minnesota Twin Cities Dept Elect & Comp Engn Minneapolis MN 55455 USA

ISBN: (纸本)9781728112954

This paper proposes and analyzes an asynchronous communi cation-efficient distributed optimization framework for a general type of machine learning and signal processing problems. At each iteration, worker machines compute gradients of a known empirical loss function using their own local data, and a master machine solves a related minimization problem to update the current estimate. We establish that the proposed algorithm converges with a sublinear rate over the number of communication rounds, coinciding with the best theoretical rate that can be achieved for nonconvex nonsmooth problems. Moreover, under a strong convexity assumption of the smooth part of the loss function, linear convergence is established. Extensive numerical experiments show that the performance of the proposed approach indeed improves-sometimes significantly - over other state-of-the-art algorithms in terms of total communication efficiency.

关键词： Communication-efficient asynchronous distributed algorithm nonconvex convergence

来源：评论

学校读者我要写书评

暂无评论

distributed Coloring in Sparse Graphs with Fewer Colors 18

Distributed Coloring in Sparse Graphs with Fewer Colors

引用

37th ACM SIGACT-SIGOPS Symposium on Principles of distributed Computing (PODC)

作者： Aboulker, Pierre Bonamy, Marthe Bousquet, Nicolas Esperet, Louis Univ Grenoble Alpes Lab G SCOP CNRS Grenoble France Univ Bordeaux LaBRI CNRS Bordeaux France

ISBN: (纸本)9781450357951

This paper is concerned with efficiently coloring sparse graphs in the distributed setting with as few colors as possible. According to the celebrated Four Color Theorem, planar graphs can be colored with at most 4 colors, and the proof gives a (sequential) quadratic algorithm finding such a coloring. A natural problem is to improve this complexity in the distributed setting. Using the fact that planar graphs contain linearly many vertices of degree at most 6, Goldberg, Plotkin, and Shannon obtained a deterministic distributed algorithm coloring n-vertex planar graphs with 7 colors in O(logn) rounds. Here, we show how to color planar graphs with 6 colors in polylog(n) rounds. Our algorithm indeed works more generally in the list-coloring setting and for sparse graphs (for such graphs we improve by at least one the number of colors resulting from an efficient algorithm of Barenboim and Elkin, at the expense of a slightly worst complexity). Our bounds on the number of colors turn out to be quite sharp in general. Among other results, we show that no distributed algorithm can color every n-vertex planar graph with 4 colors in o(n) rounds.

关键词： Graph coloring distributed algorithm maximum average degree

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：