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

Sensor Deployment and Relocation:A Unified Scheme

Journal of Computer Science & Technology 2008年第3期23卷 400-412页

作者： Michele Garetto Marco Gribaudo Carla-Fabiana Chiasserini Emilio Leonardi Dipartimento di Informatica Università di TorinoTorinoItaly Dipartimento di Elettronica Politecnico di TorinoTorinoItaly

Sensor networks are envisioned to revolutionize our daily life by ubiquitously monitoring our environment and/or adjusting it to suit our needs. Recent progress in robotics and low-power embedded systems has made it possible to add mobility to small, light, low-cost sensors to be used in teams or swarms. Augmenting static sensor networks with mobile nodes addresses many design challenges that exist in traditional static sensor networks. This paper addresses the problem of topology control in mobile wireless networks. Limitations in communication, computation and energy capabilities push towards the adoption of distributed, energy-efficient solutions to perform self-deployment and relocation of the nodes. We develop a unified, distributed algorithm that has the following features. During deployment, our algorithm yields a regular tessellation of the geographical area with a given node density, called monitoring configuration. Upon the occurrence of a physical phenomenon, network nodes relocate themselves so as to properly sample and control the event, while maintaining the network connectivity. Then, as soon as the event ends, all nodes return to the monitoring configuration. To achieve these goals, we use a virtual force-based strategy which proves to be very effective even when compared to an optimal centralized solution. We assess the performance of our approach in the presence of events with different shapes, and we investigate the transient behavior of our algorithm. This allows us to evaluate the effectiveness and the response time of the proposed solution under various environmental conditions.

关键词： distributed algorithm mobile network sensor relocation wireless sensor network

来源：评论

学校读者我要写书评

暂无评论

Move-optimal gossiping among mobile agents

引用

THEORETICAL COMPUTER SCIENCE 2008年第1-3期393卷 90-101页

作者： Suzuki, Tomoko Izumi, Taisuke Ooshita, Fukuhito Kakugawa, Hirotsugu Masuzawa, Toshimitsu Osaka Univ Grad Sch Informat Sci & Technol Osaka 5608531 Japan Nagoya Inst Technol Grad Sch Engn Syowa Ku Nagoya Aichi 4668555 Japan

Mobile-agent-based distributed systems are attracting widespread attention because of their adaptability and flexibility;mobile agents traverse the system and carry out a task at each node. In, mobile-agent-based systems, gossip is a fundamental task in cooperation among mobile agents. It requires one to accomplish all-to-all information exchange over all agents so that each agent can obtain the information each agent initially has. While rendezvous algorithms, which require that all agents rendezvous on a node at the same time, can achieve this requirement, it takes excessive cost for our objective. In this paper, we introduce the mobile agent gossip problem, in which each agent must obtain the information all other agents have. Each agent pi can obtain the information of p(j) (not equal p(i)) by meeting p(j) itself or any agent that already has information of p(j). Thus, the gossip is expected to accomplish the all-to-all information exchange with a smaller number of agents' moves than the rendezvous algorithms. In this paper, we investigate the complexity of the mobile agent gossip problem in terms of the total number of moves performed by agents. For several network topologies, we show the asymptotically tight upper and lower bounds for move complexity. This result is obtained from the fact that the mobile agent gossip problem and the node leader election problem is reducible to each other. (C) 2007 Elsevier B.V. All rights reserved.

关键词： mobile agent gossip leader election move complexity distributed algorithm

来源：评论

学校读者我要写书评

暂无评论

On the computability power and the robustness of set agreement-oriented failure detector classes

引用

distributed COMPUTING 2008年第3期21卷 201-222页

作者： Mostefaoui, Achour Rajsbaum, Sergio Raynal, Michel Travers, Corentin IRISA F-35042 Rennes France Univ Nacl Autonoma Mexico Inst Matemat Mexico City 04510 DF Mexico

Solving agreement problems deterministically, such as consensus and k-set agreement, in asynchronous distributed systems prone to an unbounded number of process failures has been shown to be impossible. To circumvent this impossibility, unreliable failure detectors for the crash failure model have been widely studied. These are oracles that provide information on failures. The exact nature of such information is defined by a set of abstract properties that a particular class of failure detectors satisfy. The weakest class of such failure detectors that allow to solve consensus is.. This paper considers failure detector classes from the literature that solve k-set agreement in the crash failure model, and studies their relative power. It shows that the family of failure detector classes lozenge S(x) (1 <= x <= n), and lozenge psi(y) (0 <= y <= n), can be "added" to provide a failure detector of the class Omega(z) (1 <= z <= n, a generalization of.). It also characterizes the power of such an "addition", namely, lozenge S(x) + lozenge psi(y) (sic) Omega(z) double left right arrow x+ y + z > t + 1, lozenge psi(y) can construct Omega(z) iff y+ z > t, and lozenge S(x) can construct Omega(z) iff x+ z > t + 1, where t is the maximum number of processes that can crash in a run. As an example, the paper shows that, while lozenge S(t) allows solving 2-set agreement (but not consensus) and lozenge psi(1) allows solving t-set agreement (but not ( t - 1)-set agreement), a system with failure detectors of both classes can solve consensus for any value of t. More generally, the paper studies the failure detector classes lozenge S(x), lozenge psi(y) and Omega(z), and shows which reductions among these classes are possible and which are not. The paper also presents a message-passing Omega(k)-based k-set agreement protocol and shows that Omega(k) is not enough to solve (k - 1)-set agreement. In that sense, it can be seen as a step toward the characterization of the weakest failure de

关键词： asynchronous system distributed algorithm fault-tolerance set-agreement unreliable failure detector

来源：评论

学校读者我要写书评

暂无评论

The foundation of self-developing blob machines for spatial computing

引用

PHYSICA D-NONLINEAR PHENOMENA 2008年第9期237卷 1282-1301页

作者： Gruau, Frederic Eisenbeis, Christine Maignan, Luidnel Inria Futurs Saclay Parc Orsay Univ F-91893 Orsay France Univ Paris 11 LRI F-91405 Orsay France Lab Informat Robot & Microelect Montpellier F-34000 Montpellier France Univ W England Bristol BS16 1QY Avon England

The current trend in electronics is to integrate more and more transistors on a chip and produce massive hardware resources. As a consequence, traditional computing models, which mainly compute in the temporal domain, do not work well anymore since it becomes increasingly difficult to orchestrate these massive-scale hardware resources in a centralized way. Spatial computing is a unifying term that embodies many unconventional computing models and means computing on a relatively homogeneous physical medium made of hardware components, where the communication time is dependent on the Euclidean distance between the components (locality constraint). This constraint makes the programming for high performance significantly more complex compared to classical non-spatial hardware because performance now depends on where computation happens in space (mapping problem). Blob computing is a new approach that addresses this parallel computing challenge in a radically new and unconventional way: it decouples the mapping of computations onto the hardware from the software programming while still elegantly exploiting the space of the underlying hardware. Hardware mapping of computations is done by a physical force-based approach that simulates forces between threads of computation (automata). Attractive forces are used to keep automata that need to communicate with each other closer while repulsive forces are used for load balancing. The advantage of these primitives is that they are simple enough to be implemented on an arbitrary computing medium. They form the basis of a runtime system (RTS) that transforms an arbitrary computing medium into an easier-to-program virtual machine called the blob machine. The basic objects of the blob machine are those automata, and the instructions let automata create new automata in specific ways so as to maintain a hierarchical organization (which facilitates both the mapping and the programming). We detail the basic instructions of the blob mach

关键词： spatial computing distributed algorithm self-developing network computer architecture computer language

来源：评论

学校读者我要写书评

暂无评论

Arbitrary pattern formation by asynchronous, anonymous, oblivious robots

引用

THEORETICAL COMPUTER SCIENCE 2008年第1-3期407卷 412-447页

作者： Flocchini, Paola Prencipe, Giuseppe Santoro, Nicola Widmayer, Peter Univ Ottawa Sch Informat Technol & Engn Ottawa ON K1N 6N5 Canada Univ Pisa Dipartimento Informat I-56100 Pisa Italy Carleton Univ Sch Comp Sci Ottawa ON K1S 5B6 Canada ETH Theoret Informat Zurich Switzerland

From an engineering point of view, the problem of coordinating a set of autonomous, mobile robots for the purpose of cooperatively performing a task has been studied extensively over the past decade. In contrast, in this paper we aim to understand the fundamental algorithmic limitations on what a set of autonomous mobile robots can or cannot achieve. We therefore study a hard task for a set of weak robots. The task is for the robots in the plane to form any arbitrary pattern that is given in advance. This task is fundamental in the sense that if the robots can form any pattern, they can agree on their respective roles in a subsequent, coordinated action. The robots are weak in several aspects. They are anonymous;they cannot explicitly communicate with each other, but only observe the positions of the others;they cannot remember the past;they operate in a very strong form of asynchronicity. We show that the tasks that such a system of robots can perform depend strongly on their common agreement about their environment, i.e. the readings of their environment sensors. If the robots have no common agreement about their environment, they cannot form an arbitrary pattern. If each robot has a compass needle that indicates North (the robot world is a flat surface, and compass needles are parallel), then any odd number of robots can form an arbitrary pattern, but an even number cannot (in the worst case). If each robot has two independent compass needles, say North and East, then any set of robots can form any pattern. (C) 2008 Elsevier B.V. All rights reserved.

关键词： Autonomous robots Pattern formation distributed computing distributed algorithm Mobile entities

来源：评论

学校读者我要写书评

暂无评论

An algorithm for k-mutual exclusion in decentralized systems

引用

COMPUTER COMMUNICATIONS 2008年第14期31卷 3223-3235页

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

The distributed k-mutual exclusion problem or, simply the k-mutex problem, is the problem of allowing at most k processes to access their critical sections simultaneously. This might be the consequence where k identical copies of a resource are made available in the distributed system or that the resource by its nature can be accessed by at most k processes simultaneously. When a process enters it critical section such that there are l < k processes in their critical sections, there is no interference of the mutual exclusion condition. In this paper, we present an algorithm for the k-mutex problem. The algorithm is token based and k tokens are used. A node may enter the critical section only if it possesses a token. The algorithm has a worst case message complexity of O(root n). Under heavy load the message requirement approaches 2 per critical section entry. The algorithm has been modified to enable fault tolerant capabilities. We have discussed node failure, message loss and link failure. (C) 2008 Elsevier B.V. All rights reserved.

关键词： mutual exclusion k-mutual exclusion distributed computing concurrency distributed algorithm

来源：评论

学校读者我要写书评

暂无评论

Using asynchrony and zero degradation to speed up indulgent consensus protocols

引用

JOURNAL OF PARALLEL AND distributed COMPUTING 2008年第7期68卷 984-996页

作者： Wu, Weigang Cao, Jiannong Yang, Jin Raynal, Michel Hong Kong Polytech Univ Dept Comp Kowloon Hong Kong Peoples R China Sun Yat Sen Univ Dept Comp Sci Guangzhou 510275 Peoples R China Entrop Communicat HK Unit 313 Hong Kong Hong Kong Peoples R China IRISA F-35042 Rennes France

Existing consensus protocols suffer from slowdowns caused by the failures of processes and the mistakes made by the underlying oracles. In this paper, we propose two novel techniques to circumvent such slowdowns in failure-detector-based consensus protocols. The first technique guarantees the Round-Zero-Degradation (RZD) property (an extension of the Zero-Degradation property) in order to avoid the slowdown caused by a failed coordinator process. The second technique, named "Look-Ahead", helps speed up the execution of the consensus protocol by making use of the messages delivered before their receivers enter the corresponding phases or rounds. The first technique is effective only when the underlying failure detector makes no or few mistakes, while the second technique always works well regardless of the performance of the failure detector. Moreover, Look-Ahead is a general technique and can be applied to consensus protocols based on any kind of oracle. By applying the two proposed techniques, several consensus protocols are developed. The simulation results show that the RZD technique is effective even if the error rate of the failure detector reaches about 15%, while the Look-Ahead technique can always improve the performance in all cases. (c) 2008 Elsevier Inc. All rights reserved.

关键词： consensus asynchronous system fault tolerance failure detector distributed algorithm

来源：评论

学校读者我要写书评

暂无评论

Computing with data non-determinism: Wait time management for peer-to-peer systems

引用

COMPUTER COMMUNICATIONS 2008年第3期31卷 629-642页

作者： Khan, Javed I. Haque, Asrar U. Kent State Univ Media Commun & Networking Res Lab Dept Math & Comp Sci Kent OH 44242 USA

One of the unusual challenges faced by peer-to-peer algorithms as opposed to classical distributed algorithms is that these have to compute with data non-determinism where there is no guarantee that data from a particular node will be delivered in time or delivered at all. Each distributed component not only has to work in such environment, but also has to decide how long to wait for peers to respond. A large wait can inordinately delay entire computation. A smaller wait can reduce the coverage of the algorithm and drastically degenerate the quality of final result produced. In this paper, we investigate a set of wait management schemas which tries to minimize the overall completion time and maximize the quality of solution. We present detail analyses of the schemas for various scenarios including large power law networks and forms of non-responsiveness. The work promises dramatic improvement in peer-to-peer search and other computations. (c) 2007 Elsevier B.V. All rights reserved.

关键词： P2P timeout schema distributed algorithm

来源：评论

学校读者我要写书评

暂无评论

Dynamic load balancing through association control of mobile users in WiFi networks

引用

IEEE TRANSACTIONS ON CONSUMER ELECTRONICS 2008年第2期54卷 342-348页

作者： Gong, Huazhi Kim, JongWon GIST Networked Media Lab Dept Informat & Mechatron Kwangju South Korea

With the development of IEEE 802.11 AMC (Medium Access Control) protocols, efficient utilization of wireless local area networks (WLANs) has become a very important issue. In typical IEEE 802.11 networks, the association between mobile users (MUs) and access point (AP) is based on the signal strength information. As a result, it often results in the extremely unfair bandwidth allocation among MUs. In this paper, we propose a distributed association algorithm to achieve load balancing among the APs. The proposed algorithm gradually balances the AP loads for the available multiple bit rate choices in a distributed manner. We analyze the stability and overhead of the proposed algorithm, and show the improvement of the fairness via computer simulation. Additionally, we have implemented a prototype on a testbed to prove its feasibility(1).

关键词： distributed algorithm WLANs AP selection association algorithm fairness and load balancing

来源：评论

学校读者我要写书评

暂无评论

Self-orienting wireless multimedia sensor networks for occlusion-free viewpoints

引用

COMPUTER NETWORKS 2008年第13期52卷 2558-2567页

作者： Tezcan, Nurcan Wang, Wenye N Carolina State Univ Dept Elect & Comp Engn Raleigh NC 27606 USA

Wireless multimedia sensor networks (WMSN) are formations of a large number of compact form-factor computing devices that can capture multimedia content, such as video and audio, and communicate them over wireless channels. The efficiency of a WMSN heavily depends on the correct orientation (i.e., view) of its individual sensory units in the field, In this paper, we study the problem of self-orientation in WMSN, that is finding the most beneficial orientation for all multimedia sensors to maximize multimedia coverage. We propose a new algorithm to determine a node's multimedia coverage and find the sensor orientation that minimizes the negative effect of occlusions and overlapping regions in the sensing field. Our approach enables multimedia sensor nodes to compute their directional coverage leading to an efficient and self-configurable sensor orientation calculation. By using simulations, we show that the occlusion-free viewpoint approach increases the multimedia coverage significantly. The self-orientation methodology is designed in the form of a distributed algorithm, making it a suitable candidate for deployment in practical systems. (C) 2008 Elsevier B.V. All rights reserved.

关键词： multimedia coverage multimedia sensor network visible field of view occlusion self-orientation distributed algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：