Project Title: Load Balancing Routing for Large-Scale Wireless Networks

 

uncc0.gif (5903 bytes)

Sponsor: UNC-Charlotte Faculty Research Grant (FRG)

Duration: January 2008 - May 2009

Investigators: Dr. Yu Wang (PI)

Students: Fan Li, Siyuan Chen

 

Abstract:

With the development of wireless technology and availability of cheap wireless devices, large-scale wireless networks are becoming a reality. Routing is one of the key topics in wireless networks which determine the route or path taken by packets as they flow from a source to a destination. Various routing protocols have been proposed and studied in literature. Most of the existing routing protocols are based on the shortest path algorithm where the packets are traveled via the shortest distance path between the source and the destination. Taking the shortest path can achieve smallest delay and shortest traveled distance, however it may lead to uneven distribution of traffic load in a network. As observed in previous work, under uniform communication scenario, the center of a network becomes crowded, since shortest paths go through the center rather than through the periphery of a network. This is also the observation from metropolitan transportation system where downtown area is always the hot spot for traffic and congestion. This crowded center effect causes extraordinary problems especially within large-scale wireless networks. To address the uneven load distribution problem of current routing protocols and eliminate the crowded center effect, in this project, we focus on the design of new load balancing routing protocols for large-scale wireless networks.

 

load.jpg (184546 bytes)

 

Objective:

Develop efficient routing protocols and algorithms to balance traffic load in large-scale wireless networks, which can optimize load distribution of the network while guaranteeing the performance of communications in a highly dynamic environment.

 

Research Activities:

We are studing the following load balancing routing problems in large-scale wireless networks, which aims to address the uneven load distribution problem of current routing protocols and eliminate the crowded center effect :

  1. Design new load balancing routing protocols for two-dimensional wireless networks based on stereographic projection techniques.

  2. Provide the theoretical analysis of the performances of the proposed methods using graph theory and projective geometry analysis.

  3. Design new load balancing routing protocols for three-dimensional wireless networks.

Stereographic Projection Method: Imagine that nodes are deployed on the surface of a three dimensional sphere instead of a planar shape. If nodes communicate only on the sphere surface and the communication is uniform, the crowded center effect vanishes due to symmetry (there is no such thing as a "center" on the sphere surface). Thus, a natural idea is to find a way to map the two-dimensional network on a 3D sphere and route greedily on those virtual coordinates. In projective geometry, the stereographic projection is a certain mapping (or function) that projects a sphere onto a plane.

projection.jpg (96611 bytes)

 

Research Findings and Outcomes:

  1. We have designed a new set of load balancing routing protocols (namely Circular Sailing Routing, CSR) for two-dimensional/three-dimensional wireless networks based on novel stereographic projection techniques in which the network is mapped to a 3D/4D sphere and routing is performed on the surface of the sphere.
  2. By using graph theory and projective geometry techniques, we found the relationship between the spherical distance of two nodes on the sphere and the circular distance of their projections in the plane, thus we proved that the stretch factor of CSR compared to shortest path routing is bounded by a constant.
  3. Via extensive simulations, we have showed that the proposed routing protocols can achieve nice load balancing and eliminate the crowded center effect in large scale wireless networks.

Related Publication:

  1. "Load Balancing Routing with Bounded Stretch", Fan Li, Siyuan Chen, Yu Wang, EURASIP Journal on Wireless Communications and Networking, Volume: 2010, Article ID: 623706, 16 pages, 2010.
  2. "Circular Sailing Routing for Wireless Networks", Fan Li, Yu Wang, IEEE 27th Conference on Computer Communications (INFOCOM 2008), Phoenix, AZ, April 2008.
  3. "Load Balancing Routing in Three Dimensional Wireless Networks", Fan Li, Siyuan Chen, Yu Wang, Jiming Chen, 2008 IEEE International Conference on Communications (ICC2008), Beijing, China, May 2008.
  4. "Stretch Factor of Curveball Routing in Wireless Network: Cost of Load Balancing", Fan Li, Yu Wang, 2008 IEEE International Conference on Communications (ICC2008), Beijing, China, May 2008.