IIT Home Page CNR Home Page

Load Balancing Hashing for Geographic Hash Tables

Algorithmics, Mesh Networks, Wireless Networks, Wireless Sensor Networks, Sensor Networks

 

In this paper, we address the problem of balancing the network traffic load generated when querying a geographic hash table. State-of-the-art approaches can be used to improve load balancing by changing the underlying geo-routing protocol used to forward queries in the geographic hash table. However, this comes at the expense of considerably complicating the routing process, which no longer occurs along (near) straightline trajectories, but requires computing complex geometric transformations. Thus, current load balancing approaches are impractical in application scenarios where the nodes composing the geographic hash table have limited computational power, such as in most wireless sensor networks. In this paper, we propose a novel approach to solve the traffic load balancing problem in geographic hash tables: instead of changing the (near) straight-line geo-routing protocol used to send a query from the node issuing the query (the source) to the node managing the queried key (the destination), we propose to “reverse engineer” the hash function so that the resulting destination density, when combined with a given source density, yields a perfectly balanced load distribution. We first formally characterize the desired destination density as a solution of a complex integral equation. We then present explicit destination density functions (taken from the family of Beta distributions) yielding quasi-perfect load balancing under the assumption of uniformly distributed sources. Our theoretical results are derived under an infinite node density model. In order to prove practicality of our approach, we have performed extensive simulations resembling realistic wireless sensor network deployments showing the effectiveness of our approach in considerably improving load balancing. Differently from previous work, the load balancing technique proposed in this paper can be readily applied in geographic hash tables composed of computationally constrained nodes, as it is typically the case in wireless sensor networks.


2010

IIT authors:

Type: TR Technical reports
Field of reference: Information Technology and Communication Systems
IIT TR-30-2010

Activity: Algoritmica per reti wireless