在無線車載通訊網路中，網路拓撲因為車輛的快速移動而變動頻繁，車輛之間連結的中斷經常發生，如何在傳送端車輛與目地端車輛建立一條穩定的網路封包傳輸路徑是相當重要的議題。近年來隨著自動駕駛車的發展，自動駕駛車的普及化是必然的趨勢。
由於自動駕駛車的軌跡資訊可精準預測，因此車輛進行網路傳輸時，可以利用軌跡資訊預測車輛間聯結的時間，並找出維持時間最長的路徑做為最穩定的傳輸路徑。然而隨著車輛密度的增加，找出最穩定路徑的時間複雜度將會隨著路徑的數目劇烈成長。本論文利用最大生成樹的特性，提出MST-based PTSRC。藉由最大生成樹，求最穩定路徑時不必先找出所有路徑，因此能夠節省許多計算時間。模擬結果顯示MST-based PTSRC在車輛密度高時可以大幅降低時間複雜度。

In VANETs, vehicle-to-vehicle communication is challenging due to fast topology change, frequent route disruptions and recoveries, and highly variable traffic density caused by vehicles' mobility. The stability of routes between source vehicle and destination vehicle is an important issue. Recently, some researchers have envisioned that most of the vehicles in the network will be self-driving vehicles in the near future. The most important characteristic of self-driving vehicular environments is that nearly perfect future position prediction of vehicles may be achieved. By utilizing the predicted trajectories information of self-driving vehicles, the link expiration time (LET) and the route expiration time (RET) can be estimated. The most stable forwarding route which has the longest RET will be constructed between source vehicle and destination vehicle.
However, the time complexity of nding the most stable path grows drastically with the increase of vehicle density. In this paper, by utilizing maximum spanning tree (MST), a MST-based PTSRC scheme in self-driving vehicular networks is proposed. The simulation results demonstrate the calculation efficiency of the proposed scheme is better than compared scheme especially in the high vehicle density.

[1] Y. Toor, P. Muhlethaler, and A. Laouiti, “Vehicle Ad Hoc Networks: Applications and Related Technical Issues,” IEEE Communications Surveys and Tutorials, vol. 10, no. 3, pp. 74–88, Sept. 2008.
[2] S. Ucar, S. C. Ergen, and O. Ozkasap, “Multihop-Cluster-Based IEEE 802.11p and LTE Hybrid Architecture for VANET Safety Message Dissemination,” IEEE Transactions on Vehicular Technology, vol. 65, no. 4, pp. 2621–2636, Apr. 2016.
[3] W. Li and H. Song, “ART: An Attack-Resistant Trust Management Scheme for Securing Vehicular Ad Hoc Networks,” IEEE Transactions on Intelligent Transportation Systems, vol. 17, no. 4, pp. 960–969, Apr. 2016.
[4] D. Jia, K. Lu, J. Wang, X. Zhang, and X. Shen, “A Survey on Platoon-Based Vehicular Cyber-Physical Systems,” IEEE Communications Surveys & Tutorials, vol. 18, no. 1, pp. 263–284, Firstquarter 2016.
[5] G. Dimitrakopoulos and P. Demestichas, “Intelligent Transportation Systems,” IEEE Vehicular Technology Magazine, vol. 5, no. 1, pp. 77–84, Mar. 2010.
[6] J. J. Blum, A. Eskandarian, and L. J. Hoffman, “Challenges of Intervehicle Ad Hoc Networks,” IEEE Transactions on Intelligent Transportation Systems, vol. 5, no. 4, pp. 347–351, Dec. 2004.
[7] “IEEE news releases,” Sept. 2012. [Online]. Available: http://www.ieee.org/about/news/2012/5septembern 2n 2012.html
[8] P. J. He, K. F. Ssu, and Y. Y. Lin, “Sharing Trajectories of Autonomous Driving Vehicles to Achieve Time-efficient Path Navigation,” in IEEE Vehicular Networking Conference, Dec. 2013, pp. 119–126.
[9] C.-E. Chang, K. F. Ssu, and Y. Y. Lin, “Trajectory-based Data Forwarding with Future Neighbor Prediction in Autonomous Driving Vehicular Environments,” in Proc. of the 2015 IEEE 40th Local Computer Networks Conference Workshops, Oct. 2015, pp. 884–892.
[10] H. H. Lin and K. F. Ssu, “Utilizing Predicted Trajectories for Stabilitybased Route Construction in Self-driving Vehicular Networks,” Master’s thesis, July 2016.
[11] I. Leontiadis, G. Marfia, D. Mack, G. Pau, C. Mascolo, and M. Gerla, “On the Effectiveness of an Opportunistic Traffic Management System for Vehicular Networks,” IEEE Transactions on Intelligent Transportation Systems, vol. 12, no. 4, pp. 1537–1548, Dec. 2011.
[12] D. B. Johnson, D. A. Maltz, and J. Broch, “DSR: The Dynamic Source Routing Protocol for Multi-Hop Wireless Ad Hoc Networks,” in Ad Hoc Networking, C. E. Perkins, Ed. Addison-Wesley, Mar. 2001, ch. 5, pp. 139–172.
[13] C. Perkins and E. Royer, “Ad-hoc On-demand Distance Vector Routing,” in IEEE Workshop on Mobile Computing Systems and Applications, Feb. 1999, pp. 90–100.
[14] C. Lochert, H. Hartenstein, J. Tian, H. Fussler, D. Hermann, and M. Mauve, “A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks,” in Proc. of 16th Annual Joint Conference of the IEEE Computer and Communications Societies, Apr. 1997, p. 1405.
[15] Z. Cheng and B. Heinzelman, Wendi, “Discovering Long Lifetime Routes in Mobile Ad Hoc Networks,” Computer Networks, vol. 6, no. 5, pp. 661–674, July 2008.
[16] J. Kleinberg and E. Tardos, Algorithm Design. Pearson Education, Inc., 2005, ch. 4, p. 147.
[17] T. Taleb, E. Sakhaee, A. Jamalipour, and K. Hashimoto, “A Stable Routing Protocol to Support ITS Services in VANET Networks,” IEEE Transactions on Vehicular Technology, vol. 56, no. 6, pp. 3337–3347,
Nov. 2007.
[18] Y. He, W. Xu, and X. Lin, “A Stable Routing Protocol for Highway Mobility over Vehicular Ad-Hoc Networks,” in IEEE Vehicular Technology Conference, May 2015, pp. 1–5.
[19] M. K. Nasir, S. A. A. Shah, and M. A. Qureshi, “Adapting Geographical DTN Routing for Enhanced Connectivity in Partitioned VANETs on Highways,” in IEEE Region 10 Symposium, Apr. 2014, pp. 1–6.
[20] R. Dube, C. D. Rais, K.-Y. Wang, and S. K. Tripathi, “Signal stabilitybased adaptive routing (SSA) for ad hoc mobile networks,” in IEEE Personal Communications, vol. 4, no. 1, Feb. 1997, pp. 36–45.
[21] H.-M. Tsai, N. Wisitpongphan, and O. K. Tonguz, “Link-quality Aware Ad Hoc On-demand Distance Vector Routing Protocol,” in 1st International Symposium on Wireless Pervasive Computing, Jan. 2006, pp. 1–6.
[22] N. Panwar and M. Dave, “Stability Based Routing Scheme for Vehicular Networks,” in Computational Intelligence and Communication Networks, Nov. 2012, pp. 191–196.
[23] H. Guo, L. Rui, R. Shi, H. Huang, and X. Qiu, “A New ICN routing selecting algorithm based on Link Expiration Time of VANET under the highway environment,” in IFIP/IEEE Symposium on Integrated Network and Service Management, May 2017, pp. 1–4.
[24] N. Sofra, A. Gkelias, and K. K. Leung, “Route Construction for Long Lifetime in VANETs,” IEEE Transactions on Vehicular Technology, vol. 60, no. 7, pp. 3450–3461, Sept. 2011.
[25] N. Alsharif, K. Aldubaikhy, and X. Shen, “Link Duration Estimation using Neural Networks based Mobility Prediction in Vehicular Networks,” in IEEE Canadian Conference on Electrical and Computer Engineering, May 2016, pp. 1–4.
[26] Vehicle Safety Communications Project - Final Report, 2006.
[27] J. Kleinberg and E. Tardos, Algorithm Design. Pearson Education, Inc., 2005, ch. 4, p. 146.
[28] ——, Algorithm Design. Pearson Education, Inc., 2005, ch. 3, pp. 79–82.
[29] “EstiNet,” 2015. [Online]. Available: http://www.estinet.com
[30] S. Y. Wang, C. L. Chou, Y. H. Chiu, Y. S. Tzeng, M. S. Hsu, Y. W. Cheng, W. L. Liu, and T. W. Ho, “NCTUns 4.0: An Integrated Simulation Platform for Vehicular Traffic, Communication, and Network Researches,” in IEEE Vehicular Technology Conference, Sept. 2007, pp. 2081–2085.
[31] S. Y. Wang and C. C. Lin, “NCTUns 5.0: A Network Simulator for IEEE 802.11(p) and 1609 Wireless Vehicular Network Researches,” in IEEE Vehicular Technology Conference, Sept. 2008, pp. 1–2.
[32] ——, “NCTUns 6.0: A Simulator for Advanced Wireless Vehicular Network Research,” in IEEE Vehicular Technology Conference, May 2010, pp. 1–2.