In-network indexing is a challenging problem in wireless sensor networks (WSNs), particularly when sensor nodes are mobile. In the past, several indexing structures have been proposed for WSNs for answering in-network queries, however, their maintenance efficiency in the presence of mobile nodes is relatively less understood. Assuming that mobility of the nodes is driven by an underlying mobility control algorithm or application, we present a novel distributed protocol for efficient maintenance of distributed hierarchical indexing structures. The proposed protocol is generic, in the sense that it is applicable to any hierarchical indexing structure that uses binary space partitioning (BSP), such as k-d trees, Quadtrees and Octrees. It is based on locally expanding and shrinking convex regions such that update costs are minimized. Based on SIDnet-SWANS simulator, our experimental results demonstrate the effectiveness of the proposed protocol under different mobility models, mobility speeds, and query streams.