Performance of standard processes over large distributed networks typically scales with the size of the network. For example, in planar topologies where nodes communicate with their natural neighbors, the scaling factor is @math , where @math is the number of nodes. As the size of the network increases, this makes global convergence over the entire network less practical. On the other hand, for several applications, such as load balancing or detection of local events, global convergence may not be necessary or even relevant. We introduce simple distributed iterative processes which limit the scope of the computational task to a smaller subnetwork of the entire network. This is achieved using one additional local parameter which controls the size of the subnetwork. We establish termination and convergence rate of such processes in theory, in experiment, in comparison to the well understood behavior of Markov processes, and for a variety of network topologies and initial conditions.
@cite_30: In this paper we study diffusion schemes for dynamic load balancing on message passing multiprocessor networks. One of the main results concerns conditions under which these dynamic schemes converge and their rates of convergence for arbitrary topologies. These results use the eigenstructure of the iteration matrices that arise in dynamic load balancing. We completely analyze the hypercube network by explicitly computing the eigenstructure of its node adjacency matrix. Using a realistic model of interprocessor communications, we show that a diffusion approach to load balancing on a hypercube multiprocessor is inferior to another approach which we call the dimension exchange method. For a d-dimensional hypercube, we compute the rate of convergence to a uniform work distribution and show that after d + 1 iterations of a diffusion type approach, we can guarantee that the work distribution is approximately within e-* of the uniform distribution independent of the hypercube dimension d. Both static and dynamic random models of work distribution are studied. o
@cite_14: We study wireless network routing algorithms that use only short paths, for minimizing latency, and achieve good load balance, for balancing the energy use. We consider the special case when all the nodes are located in a narrow strip with width at most spl radic 3 2 spl ap 0.86 times the communication radius. We present algorithms that achieve good performance in terms of both measures simultaneously. In addition, our algorithms only use local information and can deal with dynamic change and mobility efficiently.
@cite_8: Wireless sensor networks have potential to monitor environments for both military and civil applications. Due to inhospitable conditions these sensors are not always deployed uniformly ion the area of interest. Since sensors are generally constrained in on-board energy supply, efficient management of the network is crucial to extend the life of the sensors. Sensors' energy cannot support long haul communication to reach a remote command site and thus requires many levels of hops or a gateway to forward the data on behalf of the sensor. In this paper, we propose an algorithm to network these sensors in to well define clusters with less energy-constrained gateway nodes acting as cluster-heads, and balance load among these gateways. Simulation results show how our approach can balance the load and improve the lifetime of the system.
@cite_24: By spreading the workload across a sensor network, load balancing reduces hot spots in the sensor network and increases the energy lifetime of the sensor network. In this paper, we design a node-centric algorithm that constructs a load-balanced tree in sensor networks of asymmetric architecture. We utilize a Chebyshev Sum metric to evaluate via simulation the balance of the routing trees produced by our algorithm. We find that our algorithm achieves routing trees that are more effectively balanced than the routing based on breadth-first search (BFS) and shortest-path obtained by Dijkstra's algorithm.
@cite_16: Load balanced routing in a network, i.e., minimizing the maximum traffic load any node carries for unsplittable flows, is a well known NP-hard problem. Finding practical algorithms remains a long standing challenge. In this paper we propose greedy routing using virtual coordinates that achieves both small path stretch ratio (compared to shortest path) and small load balancing ratio (compared to optimal load balanced routing), in a large scale wireless sensor network deployed densely inside a geometric domain with complex shape. We first provide a greedy routing scheme on a disk with a stretch ratio of at most 2, and under which the maximum load is a factor 4√2 smaller than the maximum load under shortest path routing. This is the first simple routing scheme with a small stretch that has been proven to outperform shortest path routing in terms of load balancing. Then we transform a network of arbitrary shape to a disk by an area preserving map φ. We show that both the path length and the maximum traffic load in the original network only increases by an additional factor of d2, where d is the maximum length stretch of φ. Combined with the result on a disk we again achieve both bounded stretch and bounded load balancing ratio. Our simulation results evaluated the practical performance on both quality measures.
Consensus algorithms are used in load balancing. In fact, it was one of the early methods to balance loads @cite_30 Load balancing has shown to reduce the hot spots in the sensor networks @cite_24 . It also helps in extending the lifespan, sensor's energy might not be sufficient to support long communication and may require hops to forward the information @cite_8 . The load balancing is also used frequently for routing in networks @cite_14 @cite_16 .