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

distributed (Δ+1)-coloring in the physical model

THEORETICAL COMPUTER SCIENCE 2014年第0期553卷 37-56页

作者： Yu, Dongxiao Wang, Yuexuan Hua, Qiang-Sheng Lau, Francis C. M. Univ Hong Kong Dept Comp Sci Hong Kong Hong Kong Peoples R China Tsinghua Univ Inst Interdisciplinary Informat Sci Beijing 100084 Peoples R China

In multi-hop radio networks, such as wireless ad-hoc networks and wireless sensor networks, nodes employ a MAC (Medium Access Control) protocol such as TDMA to coordinate accesses to the shared medium and to avoid interference of close-by transmissions. These protocols can be implemented using standard node coloring. The (Delta + 1)-coloring problem is to color all nodes in as few timeslots as possible using at most Delta + 1 colors such that any two nodes within distance R are assigned different colors, where R is a given parameter and Delta is the maximum degree of the modeled unit disk graph using R as a scaling factor. Being one of the most fundamental problems in distributed computing, this problem is well studied and there is a long chain of algorithms prescribed for it. However, all previous works are based on abstract models, such as message passing models and graph based interference models, which limit the utility of these algorithms in practice. In this paper, for the first time, we consider the distributed (Delta + 1)-coloring problem under the more practical SINR interference model. In particular, without requiring any knowledge about the neighborhood, we propose a novel randomized (Delta + 1)-coloring algorithm with time complexity O (Delta log n + log(2) n). For the case where nodes cannot adjust their transmission power, we give an O (Delta log(2) n) randomized algorithm, which only incurs a logarithmic multiplicative factor overhead. (C) 2014 Elsevier B.V. All rights reserved.

关键词： distributed algorithm Randomized algorithm Wireless ad-hoc and sensor networks Coloring Physical interference model

来源：评论

学校读者我要写书评

暂无评论

distributed Scheduling and Its Asymptotic Analysis for Cognitive Radio Networks Under the Many-Channel Regime

引用

IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY 2014年第8期63卷 4053-4063页

作者： Xue, Dongyue Ekici, Eylem Ohio State Univ Dept Elect & Comp Engn Columbus OH 43210 USA

The design of efficient and distributed scheduling algorithms is essential to garner the full potential of cognitive radio networks (CRNs). In this paper, we propose a distributed orthogonal frequency-division multiplexing (OFDM)-based scheduling algorithm, which is called the collision-queue-regulated algorithm, that aims to limit the collision rate to a level imposed by primary users of a CRN. Via a novel equivalent queue system analysis, we prove that the proposed algorithm can achieve at least a constant fraction of the capacity region in the many-channel regime, and our numerical studies indicate that the proposed distributed collision-queue-regulated algorithm achieves a throughput very close to that achievable by a centralized throughput-optimal back-pressure-based scheduling algorithm.

关键词： Asymptotic analysis cognitive radio networks distributed algorithm OFDM

来源：评论

学校读者我要写书评

暂无评论

Signature-Free Asynchronous Binary Byzantine Consensus with t < n/3, O(n²) Messages, and O(1) Expected Time

引用

JOURNAL OF THE ACM 2015年第4期62卷 31-31页

作者： Mostefaoui, Achour Moumen, Hamouma Raynal, Michel Univ Nantes LINA F-44322 Nantes France Univ Bejaia LMA Bejaia 06000 Algeria Inst Univ France F-35042 Rennes France Univ Rennes IRISA F-35042 Rennes France

This article is on broadcast and agreement in asynchronous message-passing systems made up of n processes, and where up to t processes may have a Byzantine Behavior. Its first contribution is a powerful, yet simple, all-to-all broadcast communication abstraction suited to binary values. This abstraction, which copes with up to t < n/3 Byzantine processes, allows each process to broadcast a binary value, and obtain a set of values such that ( 1) no value broadcast only by Byzantine processes can belong to the set of a correct process, and ( 2) if the set obtained by a correct process contains a single value v, then the set obtained by any correct process contains v. The second contribution of this article is a new round-based asynchronous consensus algorithm that copes with up to t < n/3 Byzantine processes. This algorithm is based on the previous binary broadcast abstraction and a weak common coin. In addition to being signature-free and optimal with respect to the value of t, this consensus algorithm has several noteworthy properties: the expected number of rounds to decide is constant;each round is composed of a constant number of communication steps and involves O(n(2)) messages;each message is composed of a round number plus a constant number of bits. Moreover, the algorithm tolerates message reordering by the adversary (i.e., the Byzantine processes).

关键词： algorithms Reliability Theory Asynchronous message-passing system broadcast abstraction Byzantine process common coin consensus distributed algorithm optimal resilience randomized algorithm signature-free algorithm simplicity

来源：评论

学校读者我要写书评

暂无评论

distributed and Asynchronous Data Collection in Cognitive Radio Networks with Fairness Consideration

引用

IEEE TRANSACTIONS ON PARALLEL AND distributed SYSTEMS 2014年第8期25卷 2020-2029页

作者： Cai, Zhipeng Ji, Shouling He, Jing (Selena) Wei, Lin Bourgeois, Anu G. Georgia State Univ Dept Comp Sci Atlanta GA 30303 USA Georgia Inst Technol Sch Elect & Comp Engn Atlanta GA 30332 USA Kennesaw State Univ Dept Comp Sci Kennesaw GA 30144 USA S Dakota State Univ Dept Agr & Biosyst Brookings SD USA

As a promising communication paradigm, Cognitive Radio Networks (CRNs) have paved a road for Secondary Users (SUs) to opportunistically exploit unused licensed spectrum without causing unacceptable interference to Primary Users (PUs). In this paper, we study the distributed data collection problem for asynchronous CRNs, which has not been addressed before. We study the Proper Carrier-sensing Range (PCR) for SUs. By working with this PCR, an SU can successfully conduct data transmission without disturbing the activities of PUs and other SUs. Subsequently, based on the PCR, we propose an Asynchronous distributed Data Collection (ADDC) algorithm with fairness consideration for CRNs. ADDC collects a snapshot of data to the base station in a distributed manner without the time synchronization requirement. The algorithm is scalable and more practical compared with centralized and synchronized algorithms. Through comprehensive theoretical analysis, we show that ADDC is order-optimal in terms of delay and capacity, as long as an SU has a positive probability to access the spectrum. Furthermore, we extend ADDC to deal with the continuous data collection issue, and analyze the delay and capacity performances of ADDC for continuous data collection, which are also proven to be order-optimal. Finally, extensive simulation results indicate that ADDC can effectively accomplish a data collection task and significantly reduce data collection delay.

关键词： Cognitive radio networks data collection snapshot data collection continuous data collection distributed algorithm asynchronous wireless network delay capacity

来源：评论

学校读者我要写书评

暂无评论

distributed coordinated in-vehicle online routing using mixed-strategy congestion game

引用

TRANSPORTATION RESEARCH PART B-METHODOLOGICAL 2014年 67卷 1-17页

作者： Du, Lili Han, Lanshan Li, Xiang-Yang IIT Dept Civil Architectural & Environm Engn Chicago IL 60616 USA Nielsen Mkt Analyt Evanston IL 60201 USA IIT Dept Comp Sci Chicago IL 60616 USA

This study proposes a coordinated online in-vehicle routing mechanism for smart vehicles with real-time information exchange and portable computation capabilities. The proposed coordinated routing mechanism incorporates a discrete choice model to account for drivers' behavior, and is implemented by a simultaneously-updating distributed algorithm. This study shows the existence of an equilibrium coordinated routing decision for the mixed-strategy routing game and the convergence of the distributed algorithm to the equilibrium routing decision, assuming individual smart vehicles are selfish players seeking to minimize their own travel time. Numerical experiments conducted based on Sioux Falls city network indicate that the proposed distributed algorithm converges quickly under different smart vehicle penetrations, thus it possesses a great potential for online applications. Moreover, the proposed coordinated routing mechanism outperforms traditional independent selfish-routing mechanism;it reduces travel time for both overall system and individual vehicles, which represents the core idea of Intelligent Transportation Systems (ITS). (C) 2014 Elsevier Ltd. All rights reserved.

关键词： Online coordinated in-vehicle routing guidance Routing game distributed algorithm Discrete choice model

来源：评论

学校读者我要写书评

暂无评论

On the Complexity of Universal Leader Election

引用

JOURNAL OF THE ACM 2015年第1期62卷 7-7页

作者： Kutten, Shay Pandurangan, Gopal Peleg, David Robinson, Peter Trehan, Amitabh Technion Israel Inst Technol IL-32000 Haifa Israel Nanyang Technol Univ Nanyang Singapore Brown Univ Providence RI 02912 USA Weizmann Inst Sci Rehovot Israel Natl Univ Singapore Dept Comp Sci Singapore 117548 Singapore Queens Univ Belfast Sch Elect Elect Engn & Comp Sci Belfast BT9 5BN Antrim North Ireland

Electing a leader is a fundamental task in distributed computing. In its implicit version, only the leader must know who is the elected leader. This article focuses on studying the message and time complexity of randomized implicit leader election in synchronous distributed networks. Surprisingly, the most "obvious" complexity bounds have not been proven for randomized algorithms. In particular, the seemingly obvious lower bounds of Omega(m) messages, where m is the number of edges in the network, and Omega(D) time, where D is the network diameter, are nontrivial to show for randomized (Monte Carlo) algorithms. (Recent results, showing that even Omega(n), where n is the number of nodes in the network, is not a lower bound on the messages in complete networks, make the above bounds somewhat less obvious). To the best of our knowledge, these basic lower bounds have not been established even for deterministic algorithms, except for the restricted case of comparison algorithms, where it was also required that nodes may not wake up spontaneously and that D and n were not known. We establish these fundamental lower bounds in this article for the general case, even for randomized Monte Carlo algorithms. Our lower bounds are universal in the sense that they hold for all universal algorithms (namely, algorithms that work for all graphs), apply to every D, m, and n, and hold even if D, m, and n are known, all the nodes wake up simultaneously, and the algorithms can make any use of node's identities. To show that these bounds are tight, we present an O(m) messages algorithm. An O(D) time leader election algorithm is known. A slight adaptation of our lower bound technique gives rise to an Omega(m) message lower bound for randomized broadcast algorithms. An interesting fundamental problem is whether both upper bounds (messages and time) can be reached simultaneously in the randomized setting for all graphs. The answer is known to be negative in the deterministic setting. We answ

关键词： Theory algorithms Leader election lower bound distributed algorithm

来源：评论

学校读者我要写书评

暂无评论

À Load-balancing and Self-adaptation Clustering for Lifetime Prolonging in Large Scale Wireless Sensor Networks

引用

Procedia Computer Science 2015年 73卷 66-75页

作者： Chirihane Gherbi Zibouda Aliouat Mohammed Benmohammed University of OEB Algeria University of Ferhat Abbes Setif Algeria University Of Constantine Algeria

Hierarchical routing is an efficient way to lower energy consumption within a cluster, performing data aggregation and fusion in order decrease the number of transmitted messages to the BS. In this paper, a novel hierarchical approach called distributed energy efficient adaptive clustering protocol with gathering data (DEACP) is proposed for Wireless sensor network. Since nodes in a sensor network have limited energy, prolonging the network lifetime and improving scalability become important. we have proposed (DEACP) approach to reach the following objectives: reduce the overall network energy consumption, balance the energy consumption among the sensors and extend the lifetime of the network, the clustering must be completely distributed, the clustering should be efficient in complexity of message and time, the cluster-heads should be well-distributed across the network, the load balancing should be done well, the clustered WSN should be fully-connected. As a result transmission power of the node is reduce which subsequently reduces the energy consumption of the node. Our proposed work is simulated through Network Simulator (NS-2). We consider the problem of conserving energy in a single node in a wireless sensor network by turning off the node's radio for periods of a fixed time length. While packets may continue to arrive at the node's buffer during the sleep periods, the node cannot transmit them until it wakes up. The objective is to design sleep control laws that minimize the expected value of a cost function representing both energy consumption costs and holding costs for backlogged packets. The resource reservation is used to decompose the total simulation time of network into smaller time slots depending upon number of nodes in the network using TDMA technique. Simulations show that (DEACP) clusters have good performance characteristics.

关键词： Energy saving distributed algorithm Cluster- based Routing Wireless Sensor Network.

来源：评论

学校读者我要写书评

暂无评论

Weak vs. Self vs. Probabilistic Stabilization

引用

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 2015年第3期26卷 293-319页

作者： Devismes, Stephane Tixeuil, Sebastien Yamashita, Masafumi Univ Grenoble 1 VERMA UMR 5104 Grenoble France Univ Paris 06 Sorbonne Univ Paris France IUF Paris France Kyushu Univ Dept Informat Fukuoka Japan

Self-stabilization is a strong property, which guarantees that a distributed system always resumes a correct behavior starting from an arbitrary initial state. Since it is a strong property, some problems cannot have self-stabilizing solutions. Weaker guarantees hence have been later introduced to cope with impossibility results, e.g, probabilistic self stabilization only guarantees probabilistic convergence to a correct, behavior, and weak stabilization only guarantees the possibility of convergence. In this paper, we investigate the relative power of self, probabilistic, and weak stabilization, with respect to the set of problems that can be solved. Weak stabilization is by definition stronger than self stabilization and probabilistic self-stabilization in that precise sense. We first show that weak stabilization allows to solve problems having no self-stabilizing solution. We then show that any finite state deterministic weak stabilizing algorithm to solve a problem under the strongly fair scheduler is always a probabilistic;self-stabilizing algorithm to solve the same problem under the randomized scheduler. Unfortunately, this good property does not hold in general for infinite state algorithms. We however show that for some classes of infinite state algorithms, this property holds. These results hint at more practical use of weak stabilizing algorithms, as they are easier to design and prove their correctness than their self stabilizing and probabilistic self stabilizing counterparts.

关键词： distributed systems distributed algorithm fault-tolerance self-stabilization weak stabilization probabilistic self-stabilization

来源：评论

学校读者我要写书评

暂无评论

Location-free Minimum Coverage Determination in a Heterogeneous Wireless Sensor Network

引用

Procedia Computer Science 2015年 65卷 48-57页

作者： Ahmed M. Khedr Computer Science Department Science College Sharjah University Sharjah 27272 UAE Mathematics Department Faculty of Science Zagazig University Zagazig Egypt

The minimum connected cover problem is one of the most fundamental issues in wireless sensor networks, which directly affects the capability and efficiency of the wireless sensor network (WSN). Constructing a minimum connected coverage has a great relevance for network services, such as prolonged system lifetime by utilizing redundant deployment of sensor nodes where the main challenge in the design of sensor networks is the limited battery power of the sensors and the difficulty of replacing and/or recharging these batteries. Thus, it is necessary that the sensors be densely deployed and energy-efficient protocols be designed to maximize the network lifetime while meeting the specific application requirements in terms of coverage and connectivity. In this paper, we propose a new distributed algorithm to find the minimum connected cover of the queried region by discovering the redundant sensors for heterogeneous sensors, each with arbitrary sensing range and is not aware of its location or relative direction of its neighbor. We provide performance metrics to analyze the performance of our approach and the simulation results show that our approach clearly improves the network lifetime over existing algorithms.

关键词： Arbitrary sensing radius distributed algorithm Free-localization Minimum connected cover redundant sensor Wireless sensor networks.

来源：评论

学校读者我要写书评

暂无评论

Efficient Self-Stabilizing algorithm for Independent Strong Dominating Sets in Arbitrary Graphs

引用

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 2015年第6期26卷 751-768页

作者： Neggazi, Brahim Guellati, Nabil Haddad, Mohammed Kheddouci, Hamamache Univ Lyon 1 CNRS LIRIS UMR5205 F-69622 Villeurbanne France Univ Abderrahmane Mira Dept Comp Sci Bejaia 06000 Algeria

In computer networks area, the minimal dominating sets (MDS) and maximal independent sets (MIS) structures are very useful for creating virtual network overlays. Often, these set structures are used for designing efficient protocols in wireless sensor and adhoc networks. In this paper, we give a particular interest to one kind of these sets, called Independent Strong Dominating Set (ISD-set). In addition to its domination and independence properties, the ISD-set considers also node's degrees that make it very useful in practical applications where nodes with larger degrees play important role in the networks. For example, some net clustering protocols chose nodes with large degrees to be cluster-heads, which is exactly the result obtained by an ISD-set algorithm. Thence, we propose the first distributed self-stabilizing algorithm for computing an ISD-set of an arbitrary graph (called ISDS). Then, we prove that ISDS algorithm operates under the unfair distributed scheduler and converges after at most (n + 1) rounds requiring only O(log Delta) space memory per node where Delta is the maximum node degree. The complexity of ISDS algorithm in rounds has the same order as the best known self stabilizing algorithms for finding MDS and MIS. Moreover, performed simulations and comparisons with well-known self-stabilizing algorithms for MDS and MIS problems showed the efficiency of ISDS, especially for reducing the cardinality of dominating sets founded by the algorithms.

关键词： Self-stabilization independent strong dominating-set weak domination dominating set independent set distributed algorithm fault-tolerance

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：