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

A fault tolerant mutual exclusion algorithm for mobile ad hoc networks

PERVASIVE AND MOBILE COMPUTING 2008年第1期4卷 139-160页

作者： Wu, Weigang Cao, Jiannong Yang, Jin Hong Kong Polytech Univ Dept Comp Kowloon Hong Kong Peoples R China Nanjing Univ State Key Lab Novel Software Technol Nanjing 210093 Peoples R China

In this paper, we propose a permission-based message efficient mutual exclusion (MUTEX) algorithm for mobile ad hoc networks (MANETs). To reduce messages cost, the algorithm uses the "look-ahead" technique, which enforces MUTEX only among the hosts currently competing for the critical section. We propose mechanisms to handle dozes and disconnections of mobile hosts. The assumption of FIFO channel in the original "look-ahead" technique is also relaxed. The proposed algorithm can also tolerate link or host failures, using timeout-based mechanisms. Both analytical and simulation results show that the proposed algorithm works well under various conditions, especially when the mobility is high or load level is low. To our knowledge, this is the first permission-based MUTEX algorithm for MANETs. (C) 2007 Elsevier B.V. All rights reserved.

关键词： distributed algorithm Fault tolerance MANET Mobile computing Mutual exclusion

来源：评论

学校读者我要写书评

暂无评论

Hyperbolic embedding of Internet graph for distance estimation and overlay construction

引用

IEEE-ACM TRANSACTIONS ON NETWORKING 2008年第1期16卷 25-36页

作者： Shavitt, Yuval Tankel, Tomer Tel Aviv Univ Iby & Aladar Fleischman Fac Engn Sch Elect Engn Tel Aviv Israel

Estimating distances in the Internet has been studied in the recent years due to its ability to improve the performance of many applications, e.g., in the peer-to-peer realm. One scalable approach to estimate distances between nodes is to embed the nodes in some d dimensional geometric space and to use the pair distances in this space as the estimate for the real distances. Several algorithms were suggested in the past to do this in low dimensional Euclidean spaces. It was noted in recent years that the Internet structure has a highly connected core and long stretched tendrils, and that most of the routing paths between nodes in the tendrils pass through the core. Therefore, we suggest in this work, to embed the Internet distance metric in a hyperbolic space where routes are bent toward the center. We found that if the curvature, that defines the extend of the bending, is selected in the adequate range, the accuracy of Internet distance embedding can be improved. We demonstrate the strength of our hyperbolic embedding with two applications: selecting the closest server and building an application level multicast tree. For the latter, we present a distributed algorithm for building geometric multicast trees that achieve good trade-offs between delay (stretch) and load (stress). We also present a new efficient centralized embedding algorithm that enables the accurate embedding of short distances, something that have never been done before.

关键词： Geometry Internet Telecommunication Network Routing Hyperbolic Embedding Internet Graph Distance Estimation Overlay Construction Peer To Peer Realm D Dimensional Geometric Space Pair Distances Low Dimensional Euclidean Spaces Routing Paths Internet Distance Embedding Application Level Multicast Tree distributed algorithm Geometric Multicast Trees Centralized Embedding algorithm Internet Peer To Peer Computing Economic Indicators Routing Extraterrestrial Measurements Web Server distributed algorithms Delay Stress Multicast algorithms

来源：评论

学校读者我要写书评

暂无评论

UEEDA: Uniform and energy-efficient deployment algorithm for wireless sensor networks

引用

INTERNATIONAL JOURNAL OF COMMUNICATION SYSTEMS 2008年第5期21卷 453-467页

作者： Weng, Chien-Erh Lain, Jenn-Kaie Zhang, Jia-Ming Wen, Jyh-Horng Tunghai Univ Inst Elect Engn Taichung 40704 Taiwan Natl Yunlin Univ Sci & Technol Dept Elect Engn Yunlin Taiwan Natl Chung Cheng Univ Inst Elect Engn Chiayi Taiwan

Efficient and accurate sensor deployment is a critical requirement for the development of wireless sensor networks. Recently, distributed energy-efficient self-deployment algorithms, such as the intelligent deployment and clustering algorithm (IDCA) and the distributed self-spreading algorithm (DSSA), have been proposed to offer almost uniform distribution for sensor deployment by employing a synergistic combination of cluster structuring and a peer-to-peer deployment scheme. However, both DSSA and IDCA suffer from unnecessary movements that have arisen from an inappropriate design in partial force. To improve the performance of self-deployment algorithms, a uniform and energy-efficient deployment algorithm (UEEDA) is proposed in this paper. Simulation results demonstrate that the proposed UEEDA outperforms both DSSA and IDCA in terms of uniformity and algorithm convergence speed. Copyright (C) 2007 John Wiley & Sons, Ltd.

关键词： sensor deployment self-deployment wireless sensor networks distributed algorithm

来源：评论

学校读者我要写书评

暂无评论

Interference-Aware Joint Routing and TDMA Link Scheduling for Static Wireless Networks

引用

IEEE TRANSACTIONS ON PARALLEL AND distributed SYSTEMS 2008年第12期19卷 1709-1725页

作者： Wang, Yu Wang, Weizhao Li, Xiang-Yang Song, Wen-Zhan Univ N Carolina Dept Comp Sci Charlotte NC 28223 USA Google Inc Irvine CA 92612 USA IIT Dept Comp Sci Chicago IL 60616 USA Microsoft Res Asia Beijing 100080 Peoples R China Washington State Univ Sch Engn & Comp Sci Vancouver WA 98686 USA

We study efficient interference-aware joint routing and TDMA link scheduling for a multihop wireless network to maximize its throughput. Efficient link scheduling can greatly reduce the interference effect of close-by transmissions. Unlike the previous studies that often assume a unit disk graph (UDG) model, we assume that different terminals could have different transmission ranges and different interference ranges. In our model, it is also possible that a communication link may not exist due to barriers or is not used by a predetermined routing protocol, while the transmission of a node always result interference to all nonintended receivers within its interference range. Using a mathematical formulation, we develop interference-aware joint routing and synchronized TDMA link schedulings that optimize the networking throughput subject to various constraints. Our linear programming formulation will find a flow routing whose achieved throughput is at least a constant fraction of the optimum, and the achieved fairness is also a constant fraction of the requirement. Then, by assuming known link capacities and link traffic loads, we study link scheduling under the request-to-send and clear-to-send (RTS/CTS) interference model and the protocol interference model (PrIM) with fixed transmission power. For both models, we present both efficient centralized and distributed algorithms that use timeslots within a constant factor of the optimum. We also present efficient distributed algorithms whose performances are still comparable with optimum, but with much less communications. We prove that the timeslots needed by our faster distributed algorithms are only at most O(min(log n, log psi)) for RTS/CTS interference model and PrIM. Our theoretical results are corroborated by extensive simulation studies.

关键词： Link scheduling interference graph coloring distributed algorithm wireless networks

来源：评论

学校读者我要写书评

暂无评论

Task scheduling in multiprocessing systems using duplication

引用

JOURNAL OF SYSTEMS ARCHITECTURE 2008年第5期54卷 519-529页

作者： Chaudhuri, Pranay Elcock, Jeffrey Univ W Indies Dept Comp Sci Math & Phys Bridgetown Barbados

Task scheduling continues to be one of the most challenging problems in both parallel and distributed computing environments. In this paper, we present a task scheduling algorithm, which uses duplication, to optimally schedule any application represented in the form of a directed acyclic graph (DAG). It has a time complexity of O(d vertical bar V vertical bar(3)), where vertical bar V vertical bar represents the number of tasks and d the maximum indegree of tasks. (C) 2007 Elsevier B.V. All rights reserved.

关键词： task scheduling distributed computing environment distributed algorithm optimal schedule time complexity

来源：评论

学校读者我要写书评

暂无评论

Maximizing multicast communication lifetime in wireless mobile ad hoc networks

引用

IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY 2008年第4期57卷 2414-2425页

作者： Guo, Song Yang, Oliver Univ Aizu Sch Comp Sci & Technol Fukushima 9658580 Japan Univ Ottawa Sch Informat Technol & Engn Ottawa ON K1N 6N5 Canada

We consider the problem of maximizing the lifetime of a given multicast connection in mobile ad hoc networks (MANETs) that use omnidirectional antennas and have limited energy resources. Unlike most multicast algorithms that use centralized greedy algorithms to achieve maximum lifetime in static ad hoc networks, we present two distributed multicast algorithms, i.e., basic energy-efficient multicast (BEEM) and distributed maximum lifetime multicast (DMLM), for the same optimization problem in MANETs. Our distributed algorithms also explore the localized operations to take advantage of the power saving offered by the wireless multicast advantage property in mobile networks. The extensive simulation results have shown that our DMLM algorithm outperforms other proposals in terms of multicast lifetime under different node mobilities.

关键词： distributed algorithm maximum lifetime multicast (MLM) mobile ad hoc network (MANET)

来源：评论

学校读者我要写书评

暂无评论

A robust randomized algorithm to perform independent tasks

引用

JOURNAL OF DISCRETE algorithmS 2008年第4期6卷 651-665页

作者： Chlebus, Bogdan S. Gasieniec, Leszek Kowalski, Dariusz R. Shvartsman, Alex A. Univ Colorado Denver Dept Comp Sci & Engn Denver CO 80217 USA Univ Liverpool Dept Comp Sci Liverpool L69 3BX Merseyside England Univ Connecticut Dept Comp Sci & Engn Storrs CT 06269 USA MIT Comp Sci Lab Cambridge MA 02139 USA

The Do-All problem is about scheduling t similar and independent tasks to be performed by p processors prone to crashes. We assume that the distributed system is synchronous with processors communicating by message passing. Crashes are determined by a fully adaptive adversary that is restricted only by an upper bound f on the number of crashes. The complexity of algorithms is measured by work and communication, where work is defined as the number of available-processor steps, and communication as the number of point-to-point messages. We develop a randomized algorithm with W = O(t + p. log(2) p/log log p) expected work and O((p/p-f)(3.4) W) expected communication, for an arbitrary number f < p of crashes. (C) 2008 Elsevier B.V. All rights reserved.

关键词： Randomization distributed algorithm Message passing Crash failure Scheduling tasks Ramanujan graphs

来源：评论

学校读者我要写书评

暂无评论

Reduced Complexity algorithm for Spreading Sequence Design

引用

IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS II-EXPRESS BRIEFS 2008年第12期55卷 1309-1313页

作者： Lacatus, Catalin Akopian, David Shadaram, Mehdi Univ Texas San Antonio Dept Elect & Comp Engn San Antonio TX 78249 USA

This paper describes a novel gradient descent algorithm for the constrained optimization of spreading sequence design in the uplink of CDMA systems that use codeword adaptation. We prove that the proposed algorithm converges to the optimal sequence. In addition, the paper demonstrates the convergence of the parallel distributed optimization which is confirmed by simulations. Parallel optimization ensures faster convergence and thus reduces computational load. The performance of the parallel algorithm is improved as the number of active users increases.

关键词： CDMA constrained optimization distributed algorithm spreading sequence

来源：评论

学校读者我要写书评

暂无评论

An Enhanced Self-deployment algorithm in Mobile Sensor Network

An Enhanced Self-deployment Algorithm in Mobile Sensor Netwo...

引用

International Seminar on Future Information Technology and Management Engineering

作者： Yang, Minghua Cao, Yuanda Tan, Li Yu, Jiong Beijing Inst Technol Sch Comp Sci Beijing Lab Intelligent Informat Technol Beijing 100081 Peoples R China

ISBN: (纸本)9780769534800

In order to enforce the sensing performance of mobile sensor network (MSN), an enhanced self-deployment (ESD) algorithm is proposed in this paper. By designing the virtual repulsive force between nodes, the movement equation and the virtual attracting-field in the sensing area, the problems of the network partition and coverage holes which are aroused by conventional potential-field-based deployment approach is solved. Simulation results show that ESD algorithm exhibits excellent performance and expands the generalization of MSN greatly.

关键词： artificial-potential-field distributed algorithm sensor deployment sensor network Sensor networks sensor placement distributed algorithms EMERGENCY SHUTDOWN DEVICE

来源：评论

学校读者我要写书评

暂无评论

A combined localization and geographic routing algorithm for rapidly-deployed wireless sensor networks

引用

INTERNATIONAL JOURNAL OF distributed SENSOR NETWORKS 2008年第1期4卷 44-63页

作者： Qu, Hui Wicker, Stephen B. Cornell Univ Sch Elect & Comp Engn Ithaca NY 14853 USA

We consider a network of randomly-deployed, low-cost sensors and a single powerful sink node. A partition-based localization algorithm is proposed in which the sink node imparts sector-based location information through the phased-array transmission of a series of beacons. One-hop neighbor information is used by each sensor in a series of sector-partitioning routines to identify the sub-sector in which it resides. A geographic routing algorithm is then proposed which uses the sector-based localization results as the basis for a routing algorithm. Simulation results indicate that the performance of our localization algorithm improves with node density, and that the performance of the combined localization and routing algorithm in the presence of severe measurement noise is comparable with that provided by the same routing algorithm using perfect location information.

关键词： partition-based localization geographical routing energy-preserving distributed algorithm wireless sensor networks

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：