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

A distributed algorithm for Min-Max Tree and Max-Min Cut Problems in Communication Networks

IEEE-ACM TRANSACTIONS ON NETWORKING 2010年第4期18卷 1067-1076页

作者： Guo, Song Leung, Victor C. M. Univ Aizu Sch Comp Sci & Engn Aizu Wakamatsu Fukushima 9658580 Japan Univ British Columbia Dept Elect & Comp Engn Vancouver BC V6T 1Z4 Canada

We consider the problem of finding a multicast tree rooted at the source node and including all the destination nodes such that the maximum weight of the tree arcs is minimized. It is of paramount importance for many optimization problems, e.g., the maximum-lifetime multicast problem in multihop wireless networks, in the data networking community. We explore some important properties of this problem from a graph theory perspective and obtain a min-max-tree max-min-cut theorem, which provides a unified explanation for some important while separated results in the recent literature. We also apply the theorem to derive an algorithm that can construct a global optimal min-max multicast tree in a distributed fashion. In random networks with it nodes and m arcs, our theoretical analysis shows that the expected communication complexity of our distributed algorithm is in the order of 0(m). Specifically, the average number of messages is 2(n - 1 - gamma) - 2ln(n - 1) + m, at most, in which gamma is the Euler constant. To our best knowledge, this is the first contribution that possesses the distributed and scalable properties for the min-max multicast problem and is especially desirable to the large-scale resource-limited multihop wireless networks, like sensor networks.

关键词： Communication complexity distributed algorithm min-max tree Steiner tree

来源：评论

学校读者我要写书评

暂无评论

Sublinear bounds for randomized leader election

引用

THEORETICAL COMPUTER SCIENCE 2015年第PB期561卷 134-143页

作者： Kutten, Shay Pandurangan, Gopal Peleg, David Robinson, Peter Trehan, Amitabh Technion Israel Inst Technol Fac Ind Engn & Management Informat Syst Grp IL-32000 Haifa Israel Nanyang Technol Univ Div Math Sci Singapore 637371 Singapore Brown Univ Dept Comp Sci Providence RI 02912 USA Weizmann Inst Sci Dept Comp Sci & Appl Math IL-76100 Rehovot Israel

This paper concerns randomized leader election in synchronous distributed networks. A distributed leader election algorithm is presented for complete n-node networks that runs in O(1) rounds and (with high probability) uses only O(root nlog(3/2) n) messages to elect a unique leader (with high probability). When considering the "explicit" variant of leader election where eventually every node knows the identity of the leader, our algorithm yields the asymptotically optimal bounds of O(1) rounds and O(n) messages. This algorithm is then extended to one solving leader election on any connected non-bipartite n-node graph G in O(tau(G)) time and O(tau(G)root nlog(3/2) n) messages, where tau(G) is the mixing time of a random walk on G. The above result implies highly efficient (sublinear running time and messages) leader election algorithms for networks with small mixing times, such as expanders and hypercubes. In contrast, previous leader election algorithms had at least linear message complexity even in complete graphs. Moreover, super-linear message lower bounds are known for time-efficient deterministic leader,election algorithms. Finally, we present an almost matching lower bound for randomized leader election, showing that Omega (root n) messages are needed for any leader election algorithm that succeeds with probability at least 1/e + epsilon, for any small constant epsilon > 0. We view our results as a step towards understanding the randomized complexity of leader election in distributed networks. (C) 2014 Elsevier B.V. All rights reserved.

关键词： distributed algorithm Leader election Randomization Lower bound

来源：评论

学校读者我要写书评

暂无评论

Resource Allocation in Cellular Systems for Applications with Random Parameters

Resource Allocation in Cellular Systems for Applications wit...

引用

International Conference on Computing, Networking and Communications

作者： Zaid Kbah Ahmed Abdelhadi University of New Haven Hume Center Virginia Tech

ISBN: (纸本)9781467385800

In this paper, we conduct a study to optimize resource allocation for adaptive real-time and delay-tolerant applications in cellular systems. To represent the user applications via several devices and equipment, sigmoidal-like and logarithmic utility functions are used. A fairness proportional utility functions policy approach is used to allocate the resources among the user equipment (UE)s in a utility percentage form in order to ensure a minimum level of customer satisfaction for all the subscribers. Meanwhile, the priority of resources allocation is given to the real-time applications. We measure the effect of the stochastic variations of the adaptive real-time applications on the optimal rate allocation process and compare the results of the deterministic and stochastic systems. Our work is distinct from the other resource allocation optimization works in that we use the bisection method besides convex optimization techniques to optimally allocate rates, and we present the adaptive real-time applications in a stochastic form. We use Microsoft Visual Basic for Applications with Arena Simulation Software interface to simulate the optimization problem. Finally, we present our optimization algorithm results.

关键词： Resource allocation QoS Robustness Real-time applications distributed algorithm Stochastic modeling

来源：评论

学校读者我要写书评

暂无评论

Joint Downlink Base Station Association and Power Control for Max-Min Fairness: Computation and Complexity

引用

IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS 2015年第6期33卷 1040-1054页

作者： Sun, Ruoyu Hong, Mingyi Luo, Zhi-Quan Univ Minnesota Dept Elect & Comp Engn Minneapolis MN 55455 USA Iowa State Univ Dept Ind & Mfg Syst Engn Ames IA 50011 USA Chinese Univ Hong Kong Shenzhen Peoples R China

In a heterogeneous network (HetNet) with a large number of low power base stations (BSs), proper user-BS association and power control is crucial to achieving desirable system performance. In this paper, we systematically study the joint BS association and power allocation problem for a downlink cellular network under the max-min fairness criterion. First, we show that this problem is NP-hard. Second, we show that the upper bound of the optimal value can be easily computed, and propose a two-stage algorithm to find a high-quality suboptimal solution. Simulation results show that the proposed algorithm is near-optimal in the high-SNR regime. Third, we show that the problem under some additional mild assumptions can be solved to global optima in polynomial time by a semi-distributed algorithm. This result is based on a transformation of the original problem to an assignment problem with gains log(g(ij)), where {g(ij)} are the channel gains.

关键词： Base station association distributed algorithm downlink interference channel polynomial time solvable power control

来源：评论

学校读者我要写书评

暂无评论

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卷 1–21页

作者： 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

来源：评论

学校读者我要写书评

暂无评论

Greedy-Based distributed algorithms for Green Traffic Routing 23

Greedy-Based Distributed Algorithms for Green Traffic Routin...

引用

23rd International Conference on Computer Communication and Networks (ICCCN)

作者： Song, Yunlong Liu, Min Chinese Acad Sci Comp Technol Inst Beijing Peoples R China Univ Chinese Acad Sci Beijing Peoples R China

ISBN: (纸本)9781479935727

Green networking has become a hot research area in recent years. Most works just focus on centralized algorithms, where a central controller is used to collect all the information of the network and compute the energy aware traffic routing. However, these centralized algorithms only fit to the scenario when the network is not large and assume that all the network's information can be timely collected. When the above condition is not satisfied, the centralized algorithms will not work any more. In this paper, we study the basic principles of energy aware traffic routing and use them to explore a greedy-based distributed algorithm. The evaluation shows that our algorithm can reduce more energy consumption (almost 15%) than the existing distributed algorithms.

关键词： greedy principle distributed algorithm green networking

来源：评论

学校读者我要写书评

暂无评论

Rendezvous of heterogeneous mobile agents in edge-weighted networks

引用

THEORETICAL COMPUTER SCIENCE 2015年 608卷 219-230页

作者： Dereniowski, Dariusz Klasing, Ralf Kosowski, Adrian Kuszner, Lukasz Gdansk Univ Technol Fac Elect Telecommun & Informat PL-80233 Gdansk Poland CNRS LaBRI F-33405 Talence France Univ Bordeaux F-33405 Talence France Inria Paris GANG Project F-75205 Paris 13 France CNRS LIAFA F-75205 Paris 13 France Paris Diderot Univ F-75205 Paris 13 France

We introduce a variant of the deterministic rendezvous problem for a pair of heterogeneous agents operating in an undirected graph, which differ in the time they require to traverse particular edges of the graph. Each agent knows the complete topology of the graph and the initial positions of both agents. The agent also knows its own traversal times for all of the edges of the graph, but is unaware of the corresponding traversal times for the other agent. The goal of the agents is to meet on an edge or a node of the graph. In this scenario, we study the time required by the agents to meet, compared to the meeting time T-OPT in the offline scenario in which the agents have complete knowledge about each others' speed characteristics. When no additional assumptions are made, we show that rendezvous in our model can be achieved after time O (nT(OPT)) in an n-node graph, and that such time is essentially in some cases the best possible. However, we prove that the rendezvous time can be reduced to Theta(T-OPT) when the agents are allowed to exchange Theta(n) bits of information at the start of the rendezvous process. We then show that under some natural assumption about the traversal times of edges, the hardness of the heterogeneous rendezvous problem can be substantially decreased, both in terms of time required for rendezvous without communication, and the communication complexity of achieving rendezvous in time Theta(T-OPT). (C) 2015 Published by Elsevier B.V.

关键词： distributed algorithm Mobile agents Rendezvous

来源：评论

学校读者我要写书评

暂无评论

Mobile Ad Hoc Networks: Local distributed algorithms for Virtual Backbone 22

Mobile Ad Hoc Networks: Local Distributed Algorithms for Vir...

引用

22nd Telecommunications Forum Telfor (TELFOR)

作者： Borovina, Nihad Perunicic, Branislava Univ Sarajevo Fac Elect Engn Sarajevo Bosnia & Herceg Univ Sarajevo Sarajevo Bosnia & Herceg

ISBN: (纸本)9781479961917

Mobile ad hoc networks are temporary, wireless, multi-hop, self-organizing networks in which terminals have weak battery supply, processing power and limited bandwidth. In addition to traditional cellular networks (GSM, 3G, LTE) and increasingly popular WiFi networks, mobile ad hoc networks will be present in many spheres of human activity in the future. Especially important application areas are rescue and disaster recovery missions. In recent years, routing algorithms for mobile ad hoc networks have been popular research topics. This paper represents a survey of local distributed algorithms which are used for virtual backbone-based routing. The virtual backbone transforms an original flat structure of the mobile ad hoc networks into hierarchical, which is more appropriate for routing management. This paper presents various categories of algorithms and can facilitate decision of which algorithm is suitable for particular purpose.

关键词： Ad hoc network clustering connected dominating set distributed algorithm virtual backbone

来源：评论

学校读者我要写书评

暂无评论

Heuristic routing with bandwidth and energy constraints in sensor networks

引用

APPLIED SOFT COMPUTING 2015年 29卷 12-25页

作者： Priya, Kavi Revathi, T. Muneeswaran, K. Vijayalakshmi, K. Mepco Schlenk Engn Coll Autonomous Sivakasi Tamil Nadu India Mepco Schlenk Engn Coll Autonomous Dept IT Sivakasi Tamil Nadu India Mepco Schlenk Engn Coll Autonomous Dept CSE Sivakasi Tamil Nadu India Ramco Inst Technol Dept CSE Rajapalayam India

Most of the routing algorithms devised for sensor networks considered either energy constraints or bandwidth constraints to maximize the network lifetime. In the real scenario, both energy and bandwidth are the scarcest resource for sensor networks. The energy constraints affect only sensor routing, whereas the link bandwidth affects both routing topology and data rate on each link. Therefore, a heuristic technique that combines both energy and bandwidth constraints for better routing in the wireless sensor networks is proposed. The link bandwidth is allocated based on the remaining energy making the routing solution feasible under bandwidth constraints. This scheme uses an energy efficient algorithm called nearest neighbor tree (NNT) for routing. The data gathered from the neighboring nodes are also aggregated based on averaging technique in order to reduce the number of data transmissions. Experimental results show that this technique yields good solutions to increase the sensor network lifetime. The proposed work is also tested for wildfire application. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Sensor networks routing Bandwidth constraint Energy constraint Nearest neighbor tree distributed algorithm Maximum lifetime

来源：评论

学校读者我要写书评

暂无评论

Quickest Detection of False Data Injection Attack in Wide-Area Smart Grids

引用

IEEE TRANSACTIONS ON SMART GRID 2015年第6期6卷 2725-2735页

作者： Li, Shang Yilmaz, Yasin Wang, Xiaodong Columbia Univ Dept Elect Engn New York NY 10027 USA Univ Michigan Dept Elect Engn & Comp Sci Ann Arbor MI 48109 USA Columbia Univ Dept Elect Engn New York NY 10027 USA King Abdulaziz Univ Jeddah 21413 Saudi Arabia

We consider the sequential (i.e., online) detection of false data injection attacks in smart grid, which aims to manipulate the state estimation procedure by injecting malicious data to the monitoring meters. The unknown parameters in the system, namely the state vector, injected malicious data and the set of attacked meters pose a significant challenge for designing a robust, computationally efficient, and high-performance detector. We propose a sequential detector based on the generalized likelihood ratio to address this challenge. Specifically, the proposed detector is designed to be robust to a variety of attacking strategies, and load situations in the power system, and its computational complexity linearly scales with the number of meters. Moreover, it considerably outperforms the existing first-order cumulative sum detector in terms of the average detection delay and robustness to various attacking strategies. For wide-area monitoring in smart grid, we further develop a distributed sequential detector using an adaptive sampling technique called level-triggered sampling. The resulting distributed detector features single bit per sample in terms of the communication overhead, while preserving the high performance of the proposed centralized detector.

关键词： Cyber security distributed algorithm generalized CUSUM level-triggered sampling smart grid quickest detection wide-area monitoring

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：