IIT Home Page CNR Home Page

Load Balancing Hashing for Geographic Hash Tables

In this paper, we address the problem of balancing the network traffic load when the data generated in a wireless sensor network is stored on the sensor node themselves, and  accessed through querying a geographic hash table. Existing approaches allow balancing network load by changing the 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) straight-line trajectories, but requires computing complex geometric transformations.
In this paper, we demonstrate that it is possible to balance network traffic load in a geographic hash table without changing the underlying geo-routing protocol. 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 used to store data in the network, implementing a sort of “load-aware” assignment of key ranges to wireless sensor nodes. This innovative methodology is instantiated into two specific approaches: an analytical one, in which the destination density function yielding quasi-perfect load balancing is analytically characterized under uniformity assumptions for what concerns location of nodes and query sources; and an iterative, heuristic approach that can be used whenever these uniformity assumptions are not fulfilled. In order to prove practicality of our load balancing methodology, we have performed extensive simulations resembling realistic wireless sensor network deployments showing the effectiveness of the two proposed approaches in considerably improving load balancing and extending network lifetime. Simulation results also show that our proposed technique achieves better load balancing than an existing approach based on modifying geo-routing.


IEEE Transactions on Parallel and Distributed Systems, 2012

IIT authors:

Type: Article in ISI Journal
Field of reference: Information Technology and Communication Systems
August 2012 Da pagina 1508 a pagina 1519

Activity: Algoritmica per reti wireless