Abstract: We investigate the problem of ecient wireless energy recharging in Wireless Rechargeable Sensor Networks (WRSNs). In
such networks a special mobile entity (called the Mobile Charger) traverses the network and wirelessly replenishes the energy
of sensor nodes. In contrast to most current approaches, we envision methods that are distributed, adaptive and use limited
network information. We propose three new, alternative protocols for ecient recharging, addressing key issues which we
identify, most notably (i) to what extent each sensor should be recharged (ii) what is the best split of the total energy between
the charger and the sensors and (iii) what are good trajectories the MC should follow. One of our protocols (
LRP
) performs
some distributed, limited sampling of the network status, while another one (
RTP
) reactively adapts to energy shortage alerts
judiciously spread in the network. As detailed simulations demonstrate, both protocols signi cantly outperform known state
of the art methods, while their performance gets quite close to the performance of the global knowledge method (
GKP
) we
also provide, especially in heterogeneous network deployments.
Abstract: We study here the effect of concurrent greedy moves of players in atomic congestion games
where n selfish agents (players) wish to select a resource each (out of m resources) so that her selfish delay there is not much. Such games usually admit a global potential that decreases by sequential and selfishly improving moves. However, concurrent moves may not always lead to global convergence. On the other hand, concurrent play is desirable because it might essentially improve the system convergence time to some balanced state. The problem of ?maintaining? global progress while allowing concurrent play is
exactly what is examined and answered here. We examine two orthogonal settings : (i) A game where the players decide their moves without global information, each acting ?freely? by sampling resources randomly and locally deciding to migrate (if the new resource is better) via a random experiment. Here, the resources can have quite arbitrary latency that is load dependent. (ii) An ?organised? setting where the players are prepartitioned into selfish groups (coalitions) and where each coalition does an improving coalitional move.
Here the concurrency is among the members of the coalition. In this second setting, the resources have latency functions that are only linearly dependent on the load, since this is the only case so far where a global potential exists. In both cases (i), (ii) we show that the system converges to an ?approximate? equilibrium very fast (in logarithmic rounds where the logarithm is taken on the maximum value of the global potential). This is interesting, since two quite orthogonal settings lead to the same result. Our work considers concurrent selfish play for arbitrary latencies for the first time. Also, this is the first time where fast coalitional convergence
to an approximate equilibrium is shown. All our results refer to atomic games (ie players are finite and distinct).
Abstract: We study here the effect of concurrent greedy moves of players in atomic
congestion games where n selfish agents (players) wish to select a resource each (out
of m resources) so that her selfish delay there is not much. The problem of “maintaining”
global progress while allowing concurrent play is exactly what is examined
and answered here. We examine two orthogonal settings: (i) A game where the players
decide their moves without global information, each acting “freely” by sampling
resources randomly and locally deciding to migrate (if the new resource is better)
via a random experiment. Here, the resources can have quite arbitrary latency that is
load dependent. (ii) An “organised” setting where the players are pre-partitioned into
selfish groups (coalitions) and where each coalition does an improving coalitional
move. Our work considers concurrent selfish play for arbitrary latencies for the first
time. Also, this is the first time where fast coalitional convergence to an approximate
equilibrium is shown.
Abstract: We study here the effect of concurrent greedy moves of players in
atomic congestion games where n selfish agents (players) wish to select a re-
source each (out of m resources) so that her selfish delay there is not much. The
problem of maintaining global progress while allowing concurrent play is ex-
actly what is examined and answered here. We examine two orthogonal settings :
(i) A game where the players decide their moves without global information, each
acting freely by sampling resources randomly and locally deciding to migrate
(if the new resource is better) via a random experiment. Here, the resources can
have quite arbitrary latency that is load dependent. (ii) An organised setting
where the players are pre-partitioned into selfish groups (coalitions) and where
each coalition does an improving coalitional move. Our work considers concur-
rent selfish play for arbitrary latencies for the first time. Also, this is the first time
where fast coalitional convergence to an approximate equilibrium is shown.
Abstract: Top-k query processing is a fundamental building block for efficient ranking in a large number of applications. Efficiency is a central issue, especially for distributed settings, when the data is spread across different nodes in a network. This paper introduces novel optimization methods for top-k aggregation queries in such distributed environments. The optimizations can be applied to all algorithms that fall into the frameworks of the prior TPUT and KLEE methods. The optimizations address three degrees of freedom: 1) hierarchically grouping input lists into top-k operator trees and optimizing the tree structure, 2) computing data-adaptive scan depths for different input sources, and 3) data-adaptive sampling of a small subset of input sources in scenarios with hundreds or thousands of query-relevant network nodes. All optimizations are based on a statistical cost model that utilizes local synopses, e.g., in the form of histograms, efficiently computed convolutions, and estimators based on order statistics. The paper presents comprehensive experiments, with three different real-life datasets and using the ns-2 network simulator for a packet-level simulation of a large Internet-style network.
Abstract: We address the issue of measuring distribution fairness in Internet-scale networks. This problem has several interesting instances encountered in different applications, ranging from assessing the distribution of load between network nodes for load balancing purposes, to measuring node utilization for optimal resource exploitation, and to guiding autonomous decisions of nodes in networks built with market-based economic principles. Although some metrics have been proposed, particularly for assessing load balancing algorithms, they fall short. We first study the appropriateness of various known and previously proposed statistical metrics for measuring distribution fairness. We put forward a number of required characteristics for appropriate metrics. We propose and comparatively study the appropriateness of the Gini coefficient (G) for this task. Our study reveals as most appropriate the metrics of G, the fairness index (FI), and the coefficient of variation (CV) in this order. Second, we develop six distributed sampling algorithms to estimate metrics online efficiently, accurately, and scalably. One of these algorithms (2-PRWS) is based on two effective optimizations of a basic algorithm, and the other two (the sequential sampling algorithm, LBS-HL, and the clustered sampling one, EBSS) are novel, developed especially to estimate G. Third, we show how these metrics, and especially G, can be readily utilized online by higher-level algorithms, which can now know when to best intervene to correct unfair distributions (in particular, load imbalances). We conclude with a comprehensive experimentation which comparatively evaluates both the various proposed estimation algorithms and the three most appropriate metrics (G, CV, andFI). Specifically, the evaluation quantifies the efficiency (in terms of number of the messages and a latency indicator), precision, and accuracy achieved by the proposed algorithms when estimating the competing fairness metrics. The central conclusion is that the proposed metric, G, can be estimated with a small number of messages and latency, regardless of the skew of the underlying distribution.
Abstract: We address the issue of measuring storage, or query load distribution fairness in peer-to-peer data management systems. Existing metrics may look promising from the point of view of specific peers, while in reality being far from optimal from a global perspective. Thus, first we define the requirements and study the appropriateness of various statistical metrics for measuring load distribution fairness towards these requirements. The metric proposed as most appropriate is the Gini coefficient (G). Second, we develop novel distributed sampling algorithms to compute G on-line, with high precision, efficiently, and scalably. Third, we show how G can readily be utilized on-line by higher-level algorithms which can now know when to best intervene to correct load imbalances. Our analysis and experiments testify for the efficiency and accuracy of these algorithms, permitting the online use of a rich and reliable metric, conveying a global perspective of the distribution.
Abstract: Understanding the graph structure of the Internet is a crucial step for building accurate
network models and designing efficient algorithms for Internet applications.Yet,obtaining this graph
structure can be a surprisingly difficult task,as edges cannot be explicitly queried.For instance,
empirical studies of the network of InternetProtocol (IP) addresses typically rely on indirect methods
like trace route to build what are approximately single-source,all-destinations,shortest-path trees.
These trees only sample a fraction of the network’s edges,and a paper by Lakhinaetal.[2003]found
empirically that there sulting sample is intrinsically biased.Further,in simulations,they observed that the degree distribution under trace route sampling exhibits a power law even when the underlying
degree distribution is Poisson.
Abstract: In this work we tackle the open problem of self-join size (SJS) estimation in a large-scale distributed data system, where tuples of a relation are distributed over data nodes which comprise an overlay network. Our contributions include adaptations of five well-known SJS estimation centralized techniques (coined sequential, cross-sampling, adaptive, bifocal, and sample-count) to the network environment and a novel technique which is based on the use of the Gini coefficient. We develop analyses showing how Gini estimations can lead to estimations of the underlying Zipfian or power-law value distributions. We further contribute distributed sampling algorithms that can estimate accurately and efficiently the Gini coefficient. Finally, we provide detailed experimental evidence testifying for the claimed increased accuracy, precision, and efficiency of the proposed SJS estimation method, compared to the other methods. The proposed approach is the only one to ensure high efficiency, precision, and accuracy regardless of the skew of the underlying data.
