The MIN ENERGY BROADCAST problem consists in assigning transmission ranges to the nodes of an ad-hoc network in order to guarantee a directed spanning tree from a given source node and, at the same time, to minimize t...
详细信息
ISBN:
(纸本)9781605582351
The MIN ENERGY BROADCAST problem consists in assigning transmission ranges to the nodes of an ad-hoc network in order to guarantee a directed spanning tree from a given source node and, at the same time, to minimize the energy consumption (i.e. the energy cost) yielded by the range assignment. MIN ENERGY BROADCAST is known to be NP-hard. We consider random-grid networks where nodes are chosen independently at random from the n points of a root n x root n square grid in the plane. The probability of the existence of a node at a given point of the grid does depend on that point, that is, the probability distribution can be non-uniform. By using information-theoretic arguments, we prove a lower bound (1 - epsilon) n/pi on the energy cost of any feasible solution for this problem. Then, we provide an efficient solution of energy cost not larger than 1.1204n/pi. Finally, we present a fully-distributed protocol that constructs a broadcast range assignment of energy cost not larger than 8n, thus still yielding constant approximation. The energy load is well balanced and, at the same time, the work complexity (i.e. the energy due to all message transmissions of the protocol) is asymptotically optimal. The completion time of the protocol is only a O(logn) factor slower than the optimum. The approximation quality of our distributed solution is also experimentally evaluated. All bounds hold with probability at least 1 - 1/n(circle minus(1)).
Transmission power control is one of the key enabling technologies in opportunistic spectrum sharing for secondary users to optimize their performance without incurring undesirable interference on primary users. Vario...
详细信息
ISBN:
(纸本)9781467325691
Transmission power control is one of the key enabling technologies in opportunistic spectrum sharing for secondary users to optimize their performance without incurring undesirable interference on primary users. Various optimization models and algorithms for different scenarios and design objectives have hence been proposed in related work. While ideally these algorithms can find optimal solutions for power control, in practice it is very likely that the output powers are suboptimal or even infeasible if these algorithms are applied in a distributed environment. The reasons are due to various practical considerations such as the overheads of power training, use of the control channel, and dynamics of primary user activity. To address the problem of unfit outputs thus obtained, we investigate in this paper low-complexity algorithms that can be used in tandem with these distributed algorithms by quickly adapting undesirable solutions for use by secondary users such that feasibility is restored and/or optimality is improved. Compared with the approach of finding a new solution based on linear approximation of the optimization problem, we show through evaluations that the proposed algorithm is simple yet effective in achieving the desired goal.
This paper presents the development of a distributed computing framework based on standard web technologies. The workload is specified as Javascript code, split into pieces served via HTTP and executed by web workers ...
详细信息
ISBN:
(纸本)9781479961306
This paper presents the development of a distributed computing framework based on standard web technologies. The workload is specified as Javascript code, split into pieces served via HTTP and executed by web workers inside the clients' web browser. Initially developed to run genetic algorithms in a parallel fashion, our implementation has been generalized into a system powerful enough to run any kind of computationally intensive work. It allows running a distributed algorithm in a huge number of different devices. There are no special software requirements since every modern platform with a powerful CPU and a network connection has at least one web browser available. The tests show tasks can be run in web browsers in a secure and efficient manner. We show the great portability and performance achieved using a simple test bed problem.
In this paper,a multi-agent distributed continuous-time algorithm is proposed to solve a large-scale linear algebraic equation Ax = *** many existing results assuming each agent knows a few rows of A,the algorithm pro...
详细信息
ISBN:
(纸本)9781538629185
In this paper,a multi-agent distributed continuous-time algorithm is proposed to solve a large-scale linear algebraic equation Ax = *** many existing results assuming each agent knows a few rows of A,the algorithm proposed in this paper assumes each agent knows a few columns of *** solve the linear algebraic equation,the problem is first converted to an optimization problem with a linear ***,a distributed continuous-time algorithm is designed based on the Lagrangian function of the optimization *** algorithm is proved to solve the linear algebraic equation with any initial condition via a Lyapunov *** example is presented to show the efficacy of the proposed algorithm.
Opportunistic or Delay Tolerant Networks (DTNs) are envisioned to complement existing wireless technologies (cellular, WiFi). Wireless peers communicate when in contact, forming a network "on the fly", whose...
详细信息
ISBN:
(纸本)9781424492688
Opportunistic or Delay Tolerant Networks (DTNs) are envisioned to complement existing wireless technologies (cellular, WiFi). Wireless peers communicate when in contact, forming a network "on the fly", whose connectivity graph is highly dynamic and only partly connected. Because of this stringent environment, solutions to common networking problems (routing, congestion control, etc.) in this context are greedy, choosing the best solution among the locally available ones. This shared trait motivates the common treatment of such greedy algorithms for DTNs and raises some interesting questions: Do they converge? How fast are they? Yet, existing models study individual solutions. Moreover, they often assume homogeneous node mobility. The study of real world traces reveals considerable heterogeneity and non-trivial structure in human mobility. While algorithms have been proposed, accounting for this heterogeneity, their analytical tractability is still a challenge. In this paper, we propose a new model for greedy DTN algorithms, supporting the full heterogeneity of node mobility. We provide closed form solutions for crucial performance metrics (delivery probability and delay) and prove necessary and sufficient conditions for algorithm convergence. For illustration, we apply our model to the content placement problem, a variant of distributed caching. We use real and synthetic mobility traces to validate our findings and examine the impact of mobility properties in depth.
An introductory course on distributed systems typically exposes students to some basic synchronization distributed algorithms. This is often the first exposure for these students to the topic of distributed algorithms...
详细信息
ISBN:
(纸本)9781728184784
An introductory course on distributed systems typically exposes students to some basic synchronization distributed algorithms. This is often the first exposure for these students to the topic of distributed algorithms. In addition, in a systems course, these algorithms are typically covered in an informal way, avoiding proofs of correctness or complexity analysis. Hence, this first exposure can be challenging to students. Visualization of these algorithms can help alleviate some of these challenges. We present a suite to visualize six basic algorithms on total ordering, critical sections, and leader election.
In this work, we consider the problem of designing adaptive distributed processing algorithms in large sensor networks that are efficient in terms of minimizing the total power spent for gathering the spatially correl...
详细信息
ISBN:
(纸本)0780393058
In this work, we consider the problem of designing adaptive distributed processing algorithms in large sensor networks that are efficient in terms of minimizing the total power spent for gathering the spatially correlated data from the sensor nodes to a sink node. We take into account both the power spent for purposes of communication as well as the power spent for local computation. Our distributed algorithms are also matched to the nature of the correlated field, namely, for piecewise smooth signals, we provide two distributed multiresolution wavelet-based algorithms, while for correlated Gaussian fields, we use distributed prediction based processing. In both cases, we provide distributed algorithms that perform network division into groups of dif ferent sizes. The distribution of the group sizes within the network is the result of an optimal trade-off between the local communication inside each group needed to perform decorrelation, the communication needed to bring the processed data (coefficients) to the sink and the local computation cost, which grows as the network becomes larger. Our experimental results show clearly that important gains in power consumption can be obtained with respect to the case of not performing any distributed decorrelating processing.
The design and the proof of distributed algorithms are difficult tasks due to the lack of knowledge of the global state and the non determinism in the execution of the processes. Formal methods can guarantee that thes...
详细信息
ISBN:
(纸本)9780769550022
The design and the proof of distributed algorithms are difficult tasks due to the lack of knowledge of the global state and the non determinism in the execution of the processes. Formal methods can guarantee that these algorithms run as designed. In this paper, we show that the proof of complex distributed algorithms can be simplified by combining already proved sub-algorithms. To do so, we use a high level encoding of distributed algorithms in form of graph relabeling systems and we propose a formal proof methodology. The proposed methodology combines refinement and decomposition techniques and relies on the correct-by-construction paradigm used by the Event-B method.
In this brief announcement we summarize our results concerning distributed algorithms for LP-type problems in the well-known gossip model. LP-type problems include many important classes of problems such as (integer) ...
详细信息
ISBN:
(纸本)9781450361842
In this brief announcement we summarize our results concerning distributed algorithms for LP-type problems in the well-known gossip model. LP-type problems include many important classes of problems such as (integer) linear programming, geometric problems like smallest enclosing ball and polytope distance, and set problems like hitting set and set cover. In the gossip model, a node can only push information to or pull information from nodes chosen uniformly at random. Protocols for the gossip model are usually very practical due to their fast convergence, their simplicity, and their stability under stress and disruptions. Our algorithms are very efficient (logarithmic rounds or better with just polylogarithmic communication work per node per round) whenever the combinatorial dimension of the given LP-type problem is constant, even if the size of the given LP-type problem is polynomially large in the number of nodes.
作者：
An, XinPang, JunShandong Univ
Sch Comp Sci & Technol Jinan 250101 Shandong Peoples R China Univ Luxembourg
Comp Sci & Commun 6 Rue Richard Coudenhove Kalergi L-1359 Luxembourg Luxembourg
In the field of distributed computing, there are many round-based algorithms to solve fundamental problems, such as leader election and distributed consensus. Due to the nature of these algorithms, round numbers are u...
详细信息
ISBN:
(纸本)9780769540153
In the field of distributed computing, there are many round-based algorithms to solve fundamental problems, such as leader election and distributed consensus. Due to the nature of these algorithms, round numbers are unbounded and can increase infinitely during executions of the algorithms. This can lead to the state space explosion problem when verifying correctness of these algorithms using model checking. In this paper, we present a general idea of investigating the bounded distance of round numbers in round-based algorithms. We can manage to transform their state spaces into finite by maintaining such relations in a proper way, and thus make automatic verification of these algorithms possible. We apply this idea to several algorithms and present their verification results in the model checker Spin.
暂无评论