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

Robust self-stabilizing weight-based clustering algorithm

THEORETICAL COMPUTER SCIENCE 2009年第6-7期410卷 581-594页

作者： Johnen, Colette Nguyen, Le Huy Univ Bordeaux CNRS LaBRI Bordeaux France Univ Paris 11 CNRS UMR 8623 LRI Paris France

Ad hoc networks consist of wireless hosts that Communicate with each other in the absence of a fixed infrastructure. Such networks cannot rely on centralized and organized network management. The Clustering problem consists of partitioning network nodes into non-overlapping groups called clusters. Clusters give a hierarchical organization to the network that facilitates network management and that increases its scalability. In a weight-based clustering algorithm, the clusterheads are selected according to their weight (a node's parameter). The higher the weight of a node, the more suitable this node is for the role of clusterhead. In ad hoc networks, the amount of bandwidth, memory space or battery power of a node could be used to determine weight values. A self-stabilizing algorithm, regardless of the initial system configuration, converges to legitimate configurations without external intervention. Due to this property, self-stabilizing algorithms tolerate transient faults and they are adaptive to any topology change. In this paper, we present a robust self-stabilizing weight-based clustering algorithm for ad hoc networks. The robustness property guarantees that, starting from an arbitrary configuration, after one asynchronous round, the network is partitioned into clusters. After that, the network stays partitioned during the convergence phase toward a legitimate configuration where the clusters verify the "ad hoc clustering properties". (C) 2008 Elsevier B.V. All rights reserved.

关键词： distributed algorithm Ad hoc networking Weight-based clustering Self-stabilization Robustness

来源：评论

学校读者我要写书评

暂无评论

Congestion-aware channel assignment for multi-channel wireless mesh networks

引用

COMPUTER NETWORKS 2009年第14期53卷 2502-2516页

作者： Rad, A. Hamed Mohsenian Wong, Vincent W. S. Univ British Columbia Dept Elect & Comp Engn Vancouver BC V5Z 1M9 Canada

In this paper, we propose a distributed congestion-aware channel assignment (DCACA) algorithm for multi-channel wireless mesh networks (MC-WMNs). The frequency channels are assigned according to the congestion measures which indicate the congestion status at each link. Depending on the selected congestion measure (e.g., queueing delay, packet loss probability, and differential backlog), various design objectives can be achieved. Our proposed distributed algorithm is simple to implement as it only requires each node to perform a local search. Unlike most of the previous channel assignment schemes, our proposed algorithm assigns not only the non-overlapped (i.e., orthogonal) frequency channels, but also the partially-overlapped channels. In this regard, we introduce the channel overlapping and mutual interference matrices which model the frequency overlapping among different channels. Simulation results show that in the presence of elastic traffic (e.g., TCP Vegas or TCP Reno) sources, our proposed DCACA algorithm increases the aggregate throughput and also decreases the average packet round-trip compared with the previously proposed Load-Aware channel assignment algorithm. Furthermore, in a congested IEEE 802.11b network setting, compared with the use of three non-overlapped channels, the aggregate network throughput can further be increased by 25% and the average round-trip time can be reduced by more than one half when all the 11 partially-overlapped channels are used. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Multi-channel wireless mesh networks distributed algorithm Channel assignment Congestion control Cross-layer design Frequency overlapping

来源：评论

学校读者我要写书评

暂无评论

Revisiting simultaneous consensus with crash failures

引用

JOURNAL OF PARALLEL AND distributed COMPUTING 2009年第4期69卷 400-409页

作者： Moses, Yoram Raynal, Michel Univ Rennes IRISA CNRS INRIAUniv Joint Comp Res Lab F-35042 Rennes France Dept Elect Engn IL-32000 Haifa Israel

This paper addresses the "consensus with simultaneous decision" problem in a synchronous system prone to t process crashes. This problem requires that all the processes that do not crash decide on the same value (consensus), and that all decisions are made during the very same round (simultaneity). So, there is a double agreement, one on the decided value (data agreement) and one on the decision round (time agreement). This problem was first defined by Dwork and Moses who analyzed it and solved it using an analysis of the evolution of states of knowledge in a system with crash failures. The current paper presents a simple algorithm that optimally solves simultaneous consensus. Optimality means in this case that the simultaneous decision is taken in each and every run as soon as any protocol decides, given the same failure pattern and initial value. The design principle of this algorithm is simplicity, a first-class criterion. A new optimality proof is given that is stated in purely combinatorial terms. (C) 2009 Elsevier Inc. All rights reserved.

关键词： Agreement problem Consensus distributed algorithm Early decision Process crash failure Simultaneity Synchronous message-passing system Knowledge Common knowledge

来源：评论

学校读者我要写书评

暂无评论

Prolonging the system lifetime and equalising the energy for heterogeneous sensor networks using RETT protocol

引用

INTERNATIONAL JOURNAL OF SENSOR NETWORKS 2009年第2期6卷 65-77页

作者： Matrouk, Khaled Landfeldt, Bjorn Al Hussein Bin Talal Univ Sch Comp Engn & Informat Technol Maan 20S Jordan Univ Sydney Sch Informat Technol Sydney NSW 2006 Australia

In some Wireless Sensor Network (WSN) deployments, nodes may be used for different purposes (sensing, data pre-processing, actuation, etc.). Even if such a network is organised into clusters, this creates heterogeneity in terms of energy capability, which needs to be managed and balanced in order to ensure proper sensing capability with maximised lifespan. In this paper, we present Routing based on Energy Temperature Transformation (RETT), a protocol that transforms the expected lifetime of each node into an equivalent temperature, and then by using the heat conduction formulas, finds the hottest path for sending data to a data sink in order to equalise the residual energy throughout the WSN. We investigate RETT's ability to cope with heterogeneity and investigate its resilience and scalability based on node density and network size through a simulation study. We find that RETT is well suited to managing energy in the heterogeneous WSN case.

关键词： heterogeneous sensor networks efficient routing distributed algorithm lifetime

来源：评论

学校读者我要写书评

暂无评论

Multirobot Rendezvous With Visibility Sensors in Nonconvex Environments

引用

IEEE TRANSACTIONS ON ROBOTICS 2009年第2期25卷 340-352页

作者： Ganguli, Anurag Cortes, Jorge Bullo, Francesco UtopiaCompression Corp Los Angeles CA 90064 USA Univ Calif San Diego Dept Mech & Aerosp Engn La Jolla CA 92093 USA Univ Calif Santa Barbara Ctr Control Dynam Syst & Computat Santa Barbara CA 93106 USA

This paper presents a coordination algorithm for mobile autonomous robots. Relying on distributed sensing, the robots achieve rendezvous, i.e., they move to a common location. Each robot is a point mass moving in a simply connected, nonconvex, unknown environment according to an omnidirectional kinematic model. It is equipped with line-of-sight limited-range sensors, i.e., it can measure the relative position of any object (robots or environment boundary) if and only if the object is within a given distance and there are no obstacles in between. The perimeter minimizing algorithm is designed using the notions of robust visibility, connectivity-preserving constraint sets, and proximity graphs. The algorithm provably achieves rendezvous if the interagent sensing graph is connected at any time during the evolution of the group. Simulations illustrate the theoretical results and the performance of the proposed algorithm in asynchronous setups and with measurement errors, control errors, and nonzero robot size. Simulations to illustrate the importance of visibility constraints and comparisons with the optimal centralized algorithm are also included.

关键词： Cooperative control distributed algorithm multirobot coordination nonlinear systems and control visibility

来源：评论

学校读者我要写书评

暂无评论

RETT-gen: A globally efficient routing protocol for wireless sensor networks by equalising sensor energy and avoiding energy holes

引用

AD HOC NETWORKS 2009年第3期7卷 514-536页

作者： Matrouk, Khaled Landfeldt, Bjorn Al Hussein Bin Tatal Univ Sch Comp Engn & Informat Technol Maan 20 Jordan Univ Sydney Sch Informat Technol Sydney NSW 2006 Australia

Wireless sensor networks are composed of a large number of sensor nodes with limited energy resources. Once deployed, the sensor nodes are usually inaccessible to the user. and thus replacement of the energy resource is not feasible. Hence, energy efficiency is a key design issue that needs to be enhanced in order to improve the life span of the entire network. Several routing protocols have been proposed to improve the effective lifetime of the network with limited energy supply. In this paper, we propose routing based on energy-temperature transformation, RETT-gen, a scalable energy-efficient clustering and routing protocol designed for wireless sensor networks. The main goal of RETT-gen is to evenly distribute the energy load among all the sensor nodes in the network so that there are no overly-utilized sensor nodes that will run out of energy before the others. To achieve this goal, RETT-gen uses heat conductivity as a metaphor and uses the heat dissipation difference equations. In RETT-gen, we transform the expected lifetime of each sensor node to an equivalent temperature, and then by using the heat dissipation equations, we find the hottest path for sending data to the base station, which will not always be the shortest path. We evaluate the performance of the RETT-gen protocol via simulations, and compare it to the performance of well-known routing protocols (i.e. LEACH [W. Heinzelman, A. Chandrakasan, H. Balakrishnan, Energy-efficient communication protocol for wireless microsensor networks, in: Proceedings of the 33rd Hawaii International Conference on System Sciences (HICSS'00), 2000.] and EEUC [C. Li, M. Ye, G. Chen, J. Wu, An energy-efficient unequal clustering mechanism for wireless sensor networks, in: Proceedings of the International IEEE Conference on Mobile Adhoc and Sensor Systems (MASS), 2005.]). Simulation results show that by equalizing the sensor nodes energy, RETT-gen insures that the lifetime of the entire sensor network is maximized, the co

关键词： Sensor networks Clustering Efficient routing distributed algorithm Lifetime

来源：评论

学校读者我要写书评

暂无评论

Adaptive multicast on mobile ad hoc networks using tree-based meshes with variable density of redundant paths

引用

WIRELESS NETWORKS 2009年第8期15卷 1029-1041页

作者： Moh, Sangman Lee, Sang Jun Yu, Chansu Chosun Univ Sch Comp Engn Kwangju 501759 South Korea Cleveland State Univ Dept Elect & Comp Engn Cleveland OH 44115 USA

Multicasting has been extensively studied for mobile ad hoc networks (MANETs) because it is fundamental to many ad hoc network applications requiring close collaboration of multiple nodes in a group. A general approach is to construct an overlay structure such as multicast tree or mesh and to deliver a multicast packet to multiple receivers over the overlay structure. However, it either incurs a lot of overhead (multicast mesh) or performs poorly in terms of delivery ratio (multicast tree). This paper proposes an adaptive multicast scheme, called tree-based mesh with k-hop redundant paths (TBMk), which constructs a multicast tree and adds some additional links/nodes to the multicast structure as needed to support redundancy. It is designed to make a prudent tradeoff between the overhead and the delivery efficiency by adaptively controlling the path redundancy depending on network traffic and mobility. In other words, when the network is unstable with high traffic and high mobility, a large k is chosen to provide more robust delivery of multicast packets. On the other hand, when the network traffic and the mobility are low, a small k is chosen to reduce the overhead. It is observed via simulation that TBMk improves the packet delivery ratio as much as 35% compared to the multicast tree approach. On the other hand, it reduces control overhead by 23-87% depending on the value of k compared to the multicast mesh approach. In general, TBMk with the small value of k offers more robust delivery mechanism but demands less overhead than multicast trees and multicast meshes, respectively.

关键词： Mobile ad hoc network Multicast distributed algorithm Adaptive multicast Tradeoffs

来源：评论

学校读者我要写书评

暂无评论

A distributed algorithm for the Facility Location Problem

引用

Electronic Notes in Discrete Mathematics 2006年第SPEC. ISS.期25卷 91-91页

作者： Gehweiler, Joachim Lammersen, Christiane Sohler, Christian Heinz Nixdorf Institute Computer Science Departement University of Paderborn 33102 Paderborn Germany Heinz Nixdorf Institute Computer Science Departement University of Paderborn 33102 Paderborn Germany Heinz Nixdorf Institute Computer Science Departement University of Paderborn 33102 Paderborn Germany

来源：评论

学校读者我要写书评

暂无评论

(l,k)-ROUTING ON PLANE GRIDS\

引用

JOURNAL OF INTERCONNECTION NETWORKS 2009年第1-2期10卷 27-57页

作者： Huc, Florian Sau, Ignasi Zerovnik, Janez Ctr Univ Informat Battelle Batiment ARoute Drize 7 CH-1227 Geneva Switzerland UNSA CNRS INRIA Mascotte ProjectI3S F-06902 Sophia Antipolis France UPC MA4 Graph Theory & Combinator Grp Barcelona Spain Inst Math Phys & Mech IMFM Ljubljana Slovenia Univ Ljubljana FME Ljubljana Slovenia

The packet routing problem plays an essential role in communication networks. It involves how to transfer data from some origins to some destinations within a reasonable amount of time. In the (l,k)-routing problem, each node can send at most l packets and receive at most k packets. Permutation routing is the particular case l = k = 1. In the r-central routing problem, all nodes at distance at most r from a fixed node v want to send a packet to v. In this article we study the permutation routing, the r-central routing and the general (l,k)-routing problems on plane grids, that is square grids, triangular grids and hexagonal grids. We use the store-and-forward Delta-port model, and we consider both full and half-duplex networks. We first survey the existing results in the literature about packet routing, with special emphasis on (l,k)-routing on plane grids. Our main contributions are the following: 1. Tight permutation routing algorithms on full-duplex hexagonal grids, and half duplex triangular and hexagonal grids. 2. Tight r-central routing algorithms on triangular and hexagonal grids. 3. Tight (k,k)-routing algorithms on square, triangular and hexagonal grids. 4. Good approximation algorithms (in terms of running time) for (l,k)-routing on square, triangular and hexagonal grids, together with new lower bounds on the running time of any algorithm using shortest path routing. These algorithms are all completely distributed, i.e., can be implemented independently at each node. Finally, we also formulate the (l,k)-routing problem as a Weighted Edge Coloring problem on bipartite graphs.

关键词： Packet routing distributed algorithm (l,k)-routing plane grids permutation routing shortest path oblivious algorithm

来源：评论

学校读者我要写书评

暂无评论

A decentralized control mechanism for stream processing networks

引用

ANNALS OF OPERATIONS RESEARCH 2009年第1期170卷 161-182页

作者： Liu, Zhen Tang, Ao Xia, Cathy H. Zhang, Li IBM TJ Watson Res Ctr Hawthorne NY 10532 USA CALTECH Dept Elect Engn Pasadena CA 91125 USA

Data streaming applications are becoming more and more common due to the rapid development in emerging areas such as sensor networks, multimedia streaming, and on-line data mining, etc. These applications are often running in a decentralized, distributed environment. The requirements for processing large volumes of streaming data at real time have posed many great design challenges. One of the critical issues is to optimize the ongoing resource consumption of multiple, distributed, cooperating processing units. In this paper, we consider a generic model for the general stream data processing systems. We address the resource allocation problem for a collection of processing units so as to maximize the weighted sum of the throughput of different streams. Each processing unit may require multiple input data streams simultaneously and produce one or many valuable output streams. We develop decentralized control mechanisms that maximize the overall system throughput in such data stream processing networks. Performance analysis on the optimality and complexity of these mechanisms are also provided.

关键词： Stream processing Resource allocation distributed algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：