Optimized Hash Tree for Authentication in Sensor Networks

Authentication based on the Merkle tree has been proposed as an energy efficient approach in a resource constrained sensor network environment. It replaces complicated certificate verification with more power efficient hash computations. While previous works assumed complete binary Merkle tree structures, which can be used efficiently only in sensor networks with a specific number of sensor nodes, we investigate incomplete Merkle trees to support any number of sensors. For the incomplete Merkle tree, we demonstrate that an optimal structure can be found through mathematical analysis and simulation. A novel tree indexing scheme is also proposed to reduce communication overhead and save sensors resources during authentication