In the context of Smart City environments, wireless sensor networking is playing a major role when enabling the utilization of networked infrastructures to introduce or improve a wide variety of services to be available to the citizens. How nodes communicate with each other is a key issue in these types of networks. This work presents a simple but yet efficient network discovery and tree construction protocol as well as an intelligent metric for route selection in smart environments that combines several parameters through the use of fuzzy logic. We have carried out an extensive set of experiments using the I3ASensorBed testbed, that shows the efficiency of our proposal, when compared to other well known routing metrics by reducing the system load and increasing the network efficiency. © 2013 IEEE.