Empty cell management for grid based resource discovery protocols in ad hoc networks

Abstract

The performance of the grid based resource discovery protocols rank them among the most efficient discovery protocols for ad hoc networks. In these location aware protocols, the field is divided into geographical regions, called \emph{cells}, and pieces of information are stored and retrieved from a cell determined by a given hashing function and the unique identifier of the piece of information. However, because of obstacles and node mobility, real scenarios will create a heterogeneous density of nodes on the field and thus there will be empty cells in the grid. This phenomenon results in failures for most of the grid based protocols that have been proposed. In this thesis, we address this issue and propose Hidagrid, a fully distributed protocol that manages the empty cells of a grid by consistently relocating the data items sent to empty cells. As a result, Hidagrid acts as a sub layer that makes the actual grid appear homogeneous for any grid based resource discovery protocol. Extensive simulations show the severity of the empty cells on the resource discovery performance, and the benefits of using Hidagrid, which significantly increases the hit ratio and limits the communication overhead of the resource discovery protocol.