Optimally-balanced Hash Tree Generation in Ad Hoc Networks

Abstract

Ideally a hash tree is a perfect binary tree with leaves equal to power of two. Each leaf node in this type of tree can represent a mobile node in an ad hoc network. Each leaf in the tree contains hash value of mobile node’s identification (ID) and public key (PK). Such a tree can be used for authenticating PK in ad hoc networks. Most of the previous works based on hash tree assumed perfect hash tree structures, which can be used efficiently only in networks with a specific number of mobile nodes. Practically the number of mobile nodes may not be always equal to a power of two and the conventional algorithms may result in an inefficient tree structure. In this paper the issue of generating a hash tree is addressed by proposing an algorithm to generate an optimally-balanced structure for a complete hash tree. It is demonstrated through both the mathematical analysis and simulation that such a tree is optimally-balanced and can efficiently be used for public key authentication in ad hoc networks.