7417284
Load Balancing in Hypercubic Distributed Hash Tables with Heterogeneous Processors
There has been a considerable amount of recent research on load balancing for distributed hash tables (DHTs), a fundamental tool in Peer-to-Peer networks. Previous work in this area makes the assumption of homogeneous processors, where each processor has the same power. Here, we study load balancing strategies for a class of DHTs, called hypercubic DHTs, with heterogenous processors. We assume that each processor has a size, representing its resource capabilities, and our objective is to balance the load density (load divided by size) over the processors in the system. Our main focus is the offline version of this load balancing problem, where all of the processor sizes are known in advance. This reduces to a natural question concerning the construction of binary trees. Our main result is an efficient algorithm for this problem. The algorithm is simple to describe, but proving that it does in fact solve our binary tree construction problem is not so simple. We also give upper and lower bounds on the competitive ratio of the online version of the problem.
15656771
On optimal communication cost for gathering correlated data through wireless sensor networks
In many energy-constrained wireless sensor networks, nodes cooperatively forward correlated sensed data to data sinks. In order to reduce the communication cost (e.g.overall energy) used for data collection, previous works have focused on specific coding schemes, such as Slepian-Wolf Code or Explicit Entropy Code. However, the minimum communication cost under arbitrary coding/routing schemes has not yet been characterized. In this paper, we consider the problem of minimizing the total communication cost of a wireless sensor network with a single sink. We prove that the minimum communication cost can be achieved using Slepian-Wolf Code and Commodity Flow Routing when the link communication cost is a convex function of link data rate. Furthermore, we find it useful to introduce a new metric distance entropy, a generalization of entropy, to characterize the data collection limit of networked sources. When the energy consumption is proportional to the link data rate (e.g.normally in 802.11), we show that distance entropy provides a lower bound of the communication cost and can be achieved by using a specific rate SWC and shortest path routing. Theoretically, achieving optimality may require global knowledge of the data correlation structure, which may not be available in practice. Therefore, we propose a simple, hierarchical scheme that primarily exploits data correlation between local neighboring nodes. We show that for several correlation structures and topologies, the communication cost achieved by this scheme is within a constant factor of the distance entropy, i.e., it is asymptotically optimal. Finally, we simulate our algorithm using radar reffectivity data as well as traces from Gaussian Markov Fields (GMF). As the network size goes large, for the radar data, we find our algorithm saves two thirds of the communication cost compared to a non-coding approach; as for the GMF data, our algorithm converges to a constant factor (1 .5_1.8) the distance entropy.
5750170
Bounds on the Gain of Network Coding and Broadcasting in Wireless Networks
Gupta and Kumar established that the per node throughput of ad hoc networks with multi-pair unicast traffic scales (poorly) as lambda(n) = Theta (1 / radic(n log n)) with an increasing number of nodes n. However, Gupta and Kumar did not consider the possibility of network coding and broadcasting in their model, and recent work has suggested that such techniques have the potential to greatly improve network throughput. In [1], we have shown that for the protocol communication model of Gupta and Kumar [2], the multi-unicast throughput of schemes using arbitrary network coding and broadcasting in a two-dimensional random topology also scales as lambda(n) = Theta (1 / radic(n log n))1, thus showing that network coding provides no order difference improvement on throughput. Of course, in practice the constant factor of improvement is important; thus, here we derive bounds for the throughput benefit ratio -the ratio of the throughput of the optimal network coding scheme to the throughput of the optimal non-coding flow scheme. We show that the improvement factor is 1+ Delta / 1+Delta /2for 1D random networks, where Delta > 0 is a parameter of the wireless medium that characterizes the intensity of the interference. We obtain this by giving tight bounds (both upper and lower) on the throughput of the coding and flow schemes. For 2D networks, we obtain an upper bound for the throughput benefit ratio as alpha (n) les 2cDelta radic(pi = 1+Delta/Delta) for large n, wnere cDelta = max {2, radic(Delta2 + 2Delta)}. This is obtained by finding an upper bound for the coding throughput and a lower bound for the flow throughput. We then consider the more general physical communication model as in Gupta and Kumar. We show that the coding scheme throughput in this case is upper bounded by Theta (1/n) for the 1D random network and by Theta(1/radic(n)) for the 2D case. We also show the flow scheme throughput for the ID case can achieve the same order throughput as the coding scheme. Combined with previous work on a 2D lower bound [3], we conclude that the throughput benefit ratio under the physical model is also bounded by a constant; thus, we have shown for both the protocol and physical model that the coding benefit in terms of throughput is a constant factor. Finally, we evaluate the potential coding gain from another important perspective - total energy efficiency - and show that the factor by which the total energy is decreased is upper bounded by 3.
15797818
From Alife Agents to a Kingdom of N Queens
This paper presents a new approach to solving N-queen problems, which involves a model of distributed autonomous agents with artificial life (ALife) and a method of representing N-queen constraints in an agent environment. The distributed agents locally interact with their living environment, i.e., a chessboard, and execute their reactive behaviors by applying their behavioral rules for randomized motion, least-conflict position searching, and cooperating with other agents etc. The agent-based N-queen problem solving system evolves through selection and contest according to the rule of Survival of the Fittest, in which some agents will die or be eaten if their moving strategies are less efficient than others. The experimental results have shown that this system is capable of solving large-scale N-queen problems. This paper also provides a model of ALife agents for solving general CSPs.
39795223
On the Use of Sender Adaptation to Improve Stability and Fairness for Layered Video Multicast
Layered multicast has been shown as a promising technique for distributing a video program to a potentially large number of heterogeneous receivers. While several layered multicast approaches have been proposed, prior work has almost exclusively focused on improving the perceived video quality in terms of PSNR value or/and the fairness among different receivers. In this paper, we first argue that stability is another major index for the video playback quality; in an extreme case even with the best possible achievable PSNR value, the frequent switching between different layers still can lead to significant quality degradation. We then introduce an end-to-end adaptation framework that improves the stability and fairness for receivers by employing a dynamic layer rate allocation scheme on the sender's side. Specifically, we propose a new metric, called Stability-aware Fairness Index (SFI), which can capture both the stability as well as fairness. We then formulate the optimal layer rate allocation problem with the objective of minimizing the expected SFI for all the receivers in a multicast session, and derive an efficient algorithm to solve the problem. Simulation results demonstrate that our scheme can significantly improve the degree of stability and fairness, thus leading to better video playback quality.
5692814
Mining associated implication networks: computational intermarket analysis
Current attempts to analyze international financial markets include the use of financial technical analysis and data mining techniques. In this paper, we propose a new approach that incorporates implication networks and association rules to form an associated network structure. The proposed approach explicitly addresses the issue of local vs. global influences between financial markets.
828752
Generalized monotone schemes, discrete paths of extrema, and discrete entropy conditions
Solutions of conservation laws satisfy the monotonicity property: the number of local extrema is a non-increasing function of time, and local maximum/minimum values decrease/increase monotonically in time. This paper investigates this property from a numerical standpoint. We introduce a class of fully discrete in space and time, high order accurate, difference schemes, called generalized monotone schemes. Convergence toward the entropy solution is proven via a new technique of proof, assuming that the initial data has a finite number of extremum values only, and the flux-function is strictly convex. We define discrete paths of extrema by tracking local extremum values in the approximate solution. In the course of the analysis we establish the pointwise convergence of the trace of the solution along a path of extremum. As a corollary, we obtain a proof of convergence for a MUSCL-type scheme that is second order accurate away from sonic points and extrema.
10618110
Dominating subgraphs in graphs with some forbidden structures
Abstract We characterize the triangle-free graphs with neither induced path of six vertices nor induced cycle of six vertices and the triangle-free graphs without induced path of six vertices in terms of dominating subgraphs.