Recently, the development in wireless devices has made it possible to connect numerous devices by constructing networks only amongst themselves. Cyber-physical Systems (CPSs) are likely to emerge through such network environments to connect both humans and machines so that a smart society can evolve with remarkably convenient and yet foreseen pervasive communication. It is, however, difficult to establish adequate network infrastructures anywhere and anytime. Therefore, a critical research issue is to formulate an effective method for constructing networks. To address this issue, we focus on mobile ad-hoc based CPSs, which is a network system consisting of mobile devices. Because it does not require any specific facility, the mobile ad-hoc based CPS may be considered to be a good candidate for realizing next generation CPSs. It, however, presents two major research challenges, namely the difficulty to maintain high connectivity in the network constructed by only mobile nodes, and the need to reduce the power consumption of the nodes. For addressing these two challenges in the mobile ad-hoc based CPS, we propose a novel method called mobility aware, local tree-based reliable topology to construct the network with adequate network connectivity while ensuring a low level of power consumption.