The rapid development of sensor networks has made it possible to build a large-scale sensor overlay network by integrating separated sensor networks all over the world. In our previous research, we proposed to realize sensor overlay networks by connecting their gateways with skip graph (SG) overlay, which is distributed and self-organized, and supports retrieving sensing resources using their properties. Although this method has proven to be effective in some scenarios, the lack of proximity awareness of an SG makes it difficult to build large-scale sensor overlay systems efficiently. In this paper, we present the hierarchy-aware extension of SG (HSG), which uses a hierarchy-aware neighbor selection mechanism that integrates the hierarchy of the physical Internet into overlay construction and routing to improve latency and traffic locality. To construct an HSG efficiently under various network environments, we develop a hierarchy-aware sampling mechanism for nodes to identify better neighbors than SG. To verify and validate the feasibility of HSG as a building block of large-scale sensor overlay networks, we carried out extensive simulations in near practical scenarios, which were obtained by analyzing an Internet measurement dataset. We showed that HSG could improve the routing latency and locality significantly with little overhead.