The Load Balancing Problem

Load balancing is a critical problem for self-organized networks.

traffic social iot

Mesh & Sensor Networks

Transportation System

Social Networks

Internet of Things

Load balancing is critical for many network functionalities, such as:

  • Energy efficiency: Load unbalance is the main reason of "Energy hole" problem.
  • Traffic congestion: Load unbalance is definitely the main reason of traffic congestion.
  • Network lifetime: Only when loads are evenly assigned, the lifetime of the network can be optimized.
  • Transmission delay: Load unbalance is the main reason of delay because of the waiting time in queues.

Sept. 13th, 2010

Why is Load Balancing Difficult?

Load-balancing has received great research attention. But the load-balanding problem in multi-hop network is known very challenging.

  1. Centralized approaches for load-balancing in multi-hop networks are proved NP-complete.
  2. Distributed load-balancing using local information is challenged by instability and convergence to local optimum problems.
old
Illustration of Load Oscillation and Lcal Optimum problem

Sept. 13th, 2010

Our Approach

Think globally, Act locally. Solve the Distributed Load-balancing Problem by continuously self-updating of the nodes' local transmission probability assignments, using only Local Knowledge. This method is also called evolution of transmission probability assignments.

Inputs: For an arbitrary node $ i$ in a level $ k+1$ :

  1. $ L^t_{k+1,i}$ is the current load of node i.
  2. $ L=[L^t_{k,1},L^t_{k,2},…,L^t_{k,n}]$ , current loads of the parent candidates (PCs) of node $ i$ .
  3. $ P=[P^t_1,P^t_2,…,P^t_n]$ , current transmission probabilities to the parent candidates.

Constraints: for every node:

  1. Shortest-path constraint: parent candidates must be on the shortest-path routes.
  2. Concurrency unawareness: unaware of other siblings’ concurrent modifications

Objective:

  1. Optimal load-balancing in all levels.

Guided-Evoluton: Periodically evolving of the route selection probabilities, guided by the virtual balanced load of the parent level.

  • we devise that the key for distributed load balancing to overcome instability and local optimal solution is seeking for a qualitative guidance to guide the distributed evolving towards the global optimum.
  • Based on this idea, a guided-evolving algorithm is proposed. The expected balanced load of the $ k$ th level (denoted by $ E(L_k)$ ) works as the guidance for the children in level $ k+1$ to update their transmission probabilities.
  1. In every time step, using $ E(L_k)$ as the guidance, the children in level $ k+1$ adjust its transmission probabilities to turn its parent candidates' loads towards $ E(L_k)$ .
  2. Particularly, for a node $ j$ in level $ k+1$ and one of its parent candidates $ i$ in level $ k$ , $ j$ adjusts transmission probability to $ i$ by $ P_{j,i}^{t+1}= P_{j,i}^{t} \frac{E(L_k)}{L_{k,i}^t}/M$ , where $ M = \sum\limits_{m = 1}^{n_j } {P_{j,m }^t \frac{{E(L_k )}}{{L_{k,m }^t }}} $ is a normalizer to keep the sum of the transmission probabilities from $ j$ equal to 1; $ L_{k,i}^t$ is the load of node $ i$ at time $ t$ .
  3. By substituting $ M$ into $ P_{j,i}^{t+1}$ , we can see $ E(L_k)$ is counteracted, and actually doesn't appear in the algorithm.So the value of $ E(L_k)$ is actually not needed. Only a qualitative guidance that ``The homo-level nodes should have equal load" is required.
  4. The fact is that the total loads and the number of nodes are fixed in level $ k$ , when such a qualitative guidance is reached by nodes in level $ k$ , the balanced load $ E(L_k)$ is autonomously reached by the nodes.

Sept. 13th, 2010

Properties of Our Method

Using this virtual guidance, we designed and developed the distributed transmission probability evolving framework and formally proved its convergence and global optimality. It also provides following properties:

new
performance
The proposed method gurantee the convergence and level-based optimal load-balancing.
The proposed method also have properties of self-adaptive, quick convergence, and easy implenmentation
  1. Local: Fully distributed and limited to only local knowledge.
  2. Stable: Guarantees the network converges to a stable status.
  3. Optimal: Guarantees the optimal level-based load-balance.
  4. Self-Adaptive: Quickly Self-adapts to the network dynamics.
  5. Easily Implenmentated: Easily implemented in MAC and routing layers; Lightweight

Sept. 13th, 2010