Smart　cities　can　manage　assets　and　resources　efficiently　by　using　different　types　of　electronic　data　collection　sensors,　devices　and　vehicles.　However,　growing　complexity　of　systems　and　heterogeneous　networking　also　enlarge　the　destructive　effect　of　compromised　or　malicious　sensor　nodes.　In　this　paper,　we　introduce　electric　vehicles　to　conduct　trust　evaluation　for　heterogeneous　vehicle　network　in　smart　cities.　Compared　with　traditional　trust　evaluation　mechanism,　mobility-based　trust　evaluation　owns　the　advantages　of　low　energy　consumption　and　high　evaluation　accuracy.　Meanwhile,　we　investigate　the　problem　of　minimizing　transmission　hops　of　trust　evaluation　and　refers　to　this　as　the　mobile　trust　evaluation　problem　(MTEP).　We　first　formalize　the　MTEP　into　an　optimization　problem　and　present　a　heuristic　moving　strategy　of　single　electric　vehicle.　Then,　we　consider　the　MTEP　with　multiple　electric　vehicles.　By　scheduling　the　electric　vehicles　to　access　the　nodes　on　spanning　tree　with　maximum　neighbor　distance　ratio,　the　algorithm　can　improve　the　efficiency　of　trust　evaluation.　In　experiments,　we　compare　moving　strategy　of　single　electric　vehicle　and　multiple　electric　vehicles　with　existing　methods　respectively.　The　results　demonstrate　that　the　proposed　algorithms　are　able　to　effectively　reduce　the　entire　transmission　hops　of　trust　evaluation　and　thus　prolong　the　life　of　the　network.　©　2000-2011　IEEE.