Inherent characteristics of mobile devices make resource discovery in mobile grid challenging. Adding to the complexity is heterogeneity and hence multi-attribute management of these devices. Decentralized resource discovery using DHTs incur maintenance overheads when changes in attributes are continuous and rapid. The paper proposes a novel dual heap non-DHT overlay (DEEPG) for query resolution dealing with inherent mobile characteristics along with a mathematical model to estimate the problem size. Simulation results show that DEEPG reduces search bound on query resolution and results in limited maintenance overheads. The results also indicate that higher the query sum reduced is the number of lookups for exact match query resolution.