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

Connectivity preserving obstacle avoidance localized motion planning algorithms for mobile wireless sensor networks

PEER-TO-PEER NETWORKING AND APPLICATIONS 2019年第3期12卷 647-659页

作者： Hassan, Md. Yeakub Hussain, Faisal Choudhury, Salimur Green Univ Bangladesh Dept Comp Sci & Engn Dhaka Bangladesh Islamic Univ Technol Dept Comp Sci & Engn Gazipur Bangladesh Lakehead Univ Dept Comp Sci Thunder Bay ON Canada

Mobile wireless sensor networks (MWSN) are better in terms of coverage and it plays an important role in ubiquitous wireless networks. We design Cellular Automaton (CA) based localized motion planning algorithms for mobile wireless sensors. We propose cellular automaton based algorithms for both dispersion and gathering problems. The dispersion algorithm is intended for self-deployment purpose with the goal of increasing the sensing coverage of the network. We apply a probabilistic approach that maximizes the network coverage as well as maintains the connectivity of the network. In addition, after finishing the dispersion, a gathering algorithm guides the sensors to round up to a single place for collection. It is noteworthy that both algorithms are synchronous which means that all sensors run algorithms in parallel at the same time. Moreover, our algorithms allow the sensors to avert obstacles in their path of movement. As cellular automaton functions depend on the local information about the network strictly, they are suitable for MWSN in practice. We evaluate the performance of our algorithm based on some defined metrics i.e., coverage, strongly connected coverage. We find that our dispersion algorithm maintains better coverage than state-of-the-art algorithm. Furthermore, in case of synchronous gathering, sensors get disconnected for some cases to form multiple clusters while using state-of-the-art algorithm, but our proposed gathering algorithm is always able to provide the connectivity.

关键词： Self-deployment Synchronous gathering Mobile wireless sensor network (MWSN) local algorithms Cellular automaton IoT Obstacles

来源：评论

学校读者我要写书评

暂无评论

localized algorithms for redundant readers elimination in RFID networks

引用

INTERNATIONAL JOURNAL OF PARALLEL EMERGENT AND DISTRIBUTED SYSTEMS 2019年第3期34卷 260-271页

作者： Rashid, Nafiul Choudhury, Salimur Salomaa, Kai Univ Calif Irvine Dept Elect Engn & Comp Sci Irvine CA USA Lakehead Univ Dept Comp Sci Thunder Bay ON Canada Queens Univ Sch Comp Kingston ON Canada

Redundant readers elimination is one of the fundamental optimization research problems in RFID networks. The problem is NP-hard and can be solved approximately using best known centralised set cover algorithms. However, either distributed or localised solutions for this problem are much more realistic and useful in practice. Different distributed and a few local algorithms are known in the literature. We propose a set of cellular automaton based algorithms for the redundant readers elimination optimization problem that are strictly local. We compare the performance of our algorithms in terms of eliminating redundant readers, tag read/write operation with other local algorithms and establish that our algorithms give much better results. We also compare our algorithms with the best known centralised approximation algorithms and find very competitive results even though our algorithms are localised. [GRAPHICS]

关键词： RFID networks readers tags local algorithms cellular automata

来源：评论

学校读者我要写书评

暂无评论

Survey of local algorithms

引用

ACM COMPUTING SURVEYS 2013年第2期45卷 24-24页

作者： Suomela, Jukka Univ Helsinki Helsinki Inst Informat Technol FIN-00014 Helsinki Finland

A local algorithm is a distributed algorithm that runs in constant time, independently of the size of the network. Being highly scalable and fault tolerant, such algorithms are ideal in the operation of large-scale distributed systems. Furthermore, even though the model of local algorithms is very limited, in recent years we have seen many positive results for nontrivial problems. This work surveys the state-of-the-art in the field, covering impossibility results, deterministic local algorithms, randomized local algorithms, and local algorithms for geometric graphs.

关键词： algorithms Theory local algorithms

来源：评论

学校读者我要写书评

暂无评论

On the Power of Preprocessing in Decentralized Network Optimization

On the Power of Preprocessing in Decentralized Network Optim...

引用

IEEE Conference on Computer Communications (IEEE INFOCOM)

作者： Foerster, Klaus-Tycho Hirvonen, Juho Schmid, Stefan Suomela, Jukka Univ Vienna Fac Comp Sci Vienna Austria Aalto Univ Dept Comp Sci Helsinki Finland

ISBN: (纸本)9781728105154

As communication networks are growing at a fast pace, the need for more scalable approaches to operate such networks is pressing. Decentralization and locality are key concepts to provide scalability. Existing models for which local algorithms are designed fail to model an important aspect of many modern communication networks such as software-defined networks: the possibility to precompute distributed network state. We take this as an opportunity to study the fundamental question of how and to what extent local algorithms can benefit from preprocessing. In particular, we show that preprocessing allows for significant speedups of various networking problems. A main benefit is the precomputation of structural primitives, where purely distributed algorithms have to start from scratch. Maybe surprisingly, we also show that there are strict limitations on how much preprocessing can help in different scenarios. To this end, we provide approximation bounds for the maximum independent set problem which however show that our obtained speedups are asymptotically optimal. Even though we show that physical link failures in general hinder the power of preprocessing, we can still facilitate the precomputation of symmetry breaking processes to bypass various runtime harriers. We believe that our model and results are of interest beyond the scope of this paper and apply to other dynamic networks as well.

关键词： Decentralization local algorithms Software-defined networks

来源：评论

学校读者我要写书评

暂无评论

Distributed Learning of Hop Count Distributions in Ad Hoc Networks 17

Distributed Learning of Hop Count Distributions in Ad Hoc Ne...

引用

17th ACM International Symposium on Mobility Management and Wireless Access (MobiWac)

作者： Shamoun, Simon CUNY New York NY 10021 USA Bar Ilan Univ Ramat Gan Israel

ISBN: (纸本)9781450369053

This is a study of the feasibility of learning the hop count distribution of a mobile ad hoc network using in-network data. The nodes maintain a histogram of the hop count from the source of all packets received and share the histograms with one another. This can be used to learn the distribution between all pairs of nodes or groups of nodes. The effectiveness of this method and the effect of various factors is shown by simulation. The advantage of this method over theoretical and experimental analysis of the hop count distribution is that it is not tied to specific models of node distribution, propagation, and network protocols, and can be used to learn the distribution in real time. It is useful for the dynamic optimization of methods needed for the efficient and effective operation of an ad hoc network.

关键词： hop count distribution distributed learning mobile ad hoc networks local algorithms nonparametric statistics distribution functions

来源：评论

学校读者我要写书评

暂无评论

Community detection using preference networks

引用

PHYSICA A-STATISTICAL MECHANICS AND ITS APPLICATIONS 2018年 495卷 126-136页

作者： Tasgin, Mursel Bingol, Haluk O. Bogazici Univ Dept Comp Engn Istanbul Turkey

Community detection is the task of identifying clusters or groups of nodes in a network where nodes within the same group are more connected with each other than with nodes in different groups. It has practical uses in identifying similar functions or roles of nodes in many biological, social and computer networks. With the availability of very large networks in recent years, performance and scalability of community detection algorithms become crucial, i.e. if time complexity of an algorithm is high, it cannot run on large networks. In this paper, we propose a new community detection algorithm, which has a local approach and is able to run on large networks. It has a simple and effective method;given a network, algorithm constructs a preference network of nodes where each node has a single outgoing edge showing its preferred node to be in the same community with. In such a preference network, each connected component is a community. Selection of the preferred node is performed using similarity based metrics of nodes. We use two alternatives for this purpose which can be calculated in 1-neighborhood of nodes, i.e. number of common neighbors of selector node and its neighbors and, the spread capability of neighbors around the selector node which is calculated by the gossip algorithm of Lind ***. Our algorithm is tested on both computer generated LFR networks and real-life networks with ground truth community structure. It can identify communities accurately in a fast way. It is local, scalable and suitable for distributed execution on large networks. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Complex networks Community detection local algorithms Gossip spreading

来源：评论

学校读者我要写书评

暂无评论

A fast network-decomposition algorithm and its applications to constant-time distributed computation

引用

THEORETICAL COMPUTER SCIENCE 2018年 751卷 2-23页

作者： Barenboim, Leonid Elkin, Michael Gavoille, Cyril Open Univ Israel Raanana Israel Ben Gurion Univ Negev Beer Sheva Israel Univ Bordeaux LaBRI Bordeaux France

A partition (C-1, C-2, . . . ,C-q) of G = (V, E) into clusters of strong (respectively, weak) diameter d, such that the supergraph obtained by contracting each C-i is l-colorable is called a strong (resp., weak) (d, l)-network-decomposition. Network-decompositions were introduced in a seminal paper by Awerbuch, Goldberg, Luby and Plotkin in 1989. Awerbuch et al. showed that strong (d, l)-network-decompositions with d = l = exp {O(root logn log logn)} can be computed in distributed deterministic time O(d). Even more importantly, they demonstrated that network-decompositions can be used for a great variety of applications in the message-passing model of distributed computing. The result of Awerbuch et al. was improved by Panconesi and Srinivasan in 1992: in the latter result d = l = exp{O(root logn)}, and the running time is O(d) as well. In another remarkable breakthrough Linial and Saks (in 1992) showed that weak (O(logn), O(logn))-network-decompositions can be computed in distributed randomized time O(log(2)n). Much more recently Barenboim (2012) devised a distributed randomized constant-time algorithm for computing strong network decompositions with d = O(1). However, the parameter l in his result is O (n(1/2+epsilon)). In this paper we drastically improve the result of Barenboim and devise a distributed randomized constant-time algorithm for computing strong (O(1), O(n(epsilon)))-network-decompositions. As a corollary we derive a constant-time randomized O(n(epsilon))-approximation algorithm for the distributed minimum coloring problem, improving the previously bestknown O(n(1/2+epsilon)) approximation guarantee. We also derive other improved distributed algorithms for a variety of problems. Most notably, for the extremely well-studied distributed minimum dominating set problem currently there is no known deterministic polylogarithmic-time algorithm. We devise a deterministic polylogarithmic-time approximation algorithm for this problem, addressing an open proble

关键词： Distributed algorithms local algorithms Dominating sets Coloring Spanners

来源：评论

学校读者我要写书评

暂无评论

Scalable algorithms in the Age of Big Data and Network Sciences: Characterization, Primitives, and Techniques 18

Scalable Algorithms in the Age of Big Data and Network Scien...

引用

11th ACM International Conference on Web Search and Data Mining

作者： Teng, Shang-Hua Univ Southern Calif Los Angeles CA 90007 USA

ISBN: (纸本)9781450355810

In the age of network sciences and machine learning, efficient algorithms are now in higher demand more than ever before. Big Data fundamentally challenges the classical notion of efficient algorithms: algorithms that used to be considered efficient, according to polynomial-time characterization, may no longer be adequate for solving today's problems. It is not just desirable, but essential, that efficient algorithms should be scalable. In other words, their complexity should be nearly linear or sub-linear with respect to the problem size. Thus, scalability, not just polynomial-time computability, should be elevated as the central complexity notion for characterizing efficient computation. Using several basic tasks in network analysis, machine learning, and optimization as examples - in this talk - I will highlight a family of fundamental algorithmic techniques for designing provably-good scalable algorithms.

关键词： scalable algorithms graph sparsification local algorithms advanced sampling big data network sciences machine learning

来源：评论

学校读者我要写书评

暂无评论

A fast network-decomposition algorithm and its applications to constant-time distributed computation 1

引用

22nd International Colloquium on Structural Information and Communication Complexity (SIROCCO)

作者： Barenboim, Leonid Elkin, Michael Gavoille, Cyril Open Univ Israel Raanana Israel Ben Gurion Univ Negev Beer Sheva Israel Univ Bordeaux LaBRI Bordeaux France

ISBN: (数字)9783319252582

ISBN: (纸本)9783319252575

关键词： Distributed algorithms local algorithms Dominating sets Coloring Spanners

来源：评论

学校读者我要写书评

暂无评论

A local algorithm to approximate the global clustering of streams generated in ubiquitous sensor networks

引用

INTERNATIONAL JOURNAL OF DISTRIBUTED SENSOR NETWORKS 2018年第10期14卷 1-1页

作者： Rodrigues, Pedro Pereira Araujo, Joao Gama, Joao Lopes, Luis Ctr Hlth Technol & Serv Res CINTESIS Rua Dr Placido Costa P-4200450 Porto Portugal Univ Porto Fac Med MEDCIDS FMUP Dept Community Med Informat & Hlth Decis Sci Porto Portugal INESC TEC Artificial Intelligence & Decis Support Lab LIAAD Porto Portugal INESC TEC Ctr Res Adv Comp Syst CRACS Porto Portugal Univ Porto Fac Econ FEP Porto Portugal Univ Porto Fac Sci DCC FCUP Dept Comp Sci Porto Portugal

In ubiquitous streaming data sources, such as sensor networks, clustering nodes by the data they produce gives insights on the phenomenon being monitored. However, centralized algorithms force communication and storage requirements to grow unbounded. This article presents L2GClust, an algorithm to compute local clusterings at each node as an approximation of the global clustering. L2GClust performs local clustering of the sources based on the moving average of each node's data over time: the moving average is approximated using memory-less statistics;clustering is based on the furthest-point algorithm applied to the centroids computed by the node's direct neighbors. Evaluation is performed both on synthetic and real sensor data, using a state-of-the-art sensor network simulator and measuring sensitivity to network size, number of clusters, cluster overlapping, and communication incompleteness. A high level of agreement was found between local and global clusterings, with special emphasis on separability agreement, while an overall robustness to incomplete communications emerged. Communication reduction was also theoretically shown, with communication ratios empirically evaluated for large networks. L2GClust is able to keep a good approximation of the global clustering, using less communication than a centralized alternative, supporting the recommendation to use local algorithms for distributed clustering of streaming data sources.

关键词： Distributed clustering data streams local algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：