智慧城市的進步與實現隨著目前軟硬體設備的升級指日可待，智慧城市中因為感測器的幫助下我們可以蒐集的資料種類各式各樣，也因此我們可以解決各式各樣的問題以提升城市內居民的生活品質以及人身安全。而我們的研究主旨便是利用感測器蒐集來的道路資料進行安全道路導航之模擬以保障市民在各種的移動方式如開車、騎自行車以及步行等的人身安全，利用定義非安全區域(Trap)的方式來模擬並給予一條安全且較短的推薦路徑。陷阱可以被定義成危險的情況之範圍，像是水災、停電、塞車…等。範圍之大小會隨著時間遞移與危險因素而改變。如此一來針對陷阱的大小給予使用者迴避危險的道路推薦用以迴避危險區域並基於起點和終點之距離的長度給予一條合適道路推薦，在節省時間的同時也能實時的躲避危險。我們的研究就是針對道路的長度與陷阱的遠近同時使用結合Power diagram的A star演算法並改變為適合我們的啟發式演算法(Heuristic Algorithm)給予一條最合適的推薦的道路導航決策。

The progress and realization of smart cities with the current upgrade of hardware and software equipment, the types of data that we can collect in the smart city with the help of sensors are various, so we can solve all kinds of problems. Improve the quality of life and personal safety of residents in the city. The main purpose of our research is to use the road data collected by the sensors to simulate the safe road navigation to protect the public's personal safety in various situations of transportation such as driving, cycling and walking, and to define non-safe areas (also named Traps). The way to simulate and give a safe and short recommended path. Trap can be defined as a range of dangerous situations, such as floods, power outages, traffic jams, etc. The size of the range will change over time and risk factors. In this way, the size of the trap is given to the user to avoid the dangerous road recommendation to avoid the dangerous area and give a suitable road recommendation based on the length of the distance between the starting point and the end point, and save time and avoid danger in real time. Our research is based on the length of the road and the distance of the trap. Using the A star algorithm combined with the Power diagram and changing to a heuristic algorithm suitable for us to give a most appropriate recommended road navigation decision.

摘要-----------------------------------i
Abstract------------------------------ii
第一章、緒論----------------------------1
1.1、背景、目的及重要性------------------1
1.2、國內外相關研究參考----------------2
第二章、問題假設與描述-------------------4
第三章、基於陷阱的智慧導航---------------9
3.1、陷阱的定義與設定-------------------9
3.2、Power Diagram--------------------10
3.3、道路安全度數值的定義與計算方法------12
3.4、基於陷阱的智慧導航演算法------------14
第四章、實驗結果-----------------------19
4.1、實驗模擬--------------------------19
4.2、各種情境的模擬結果-----------------20
4.3、實驗模擬數據分析-------------------26
第五章、結論---------------------------32
參考文獻-------------------------------33

[1]F. AURENHAMMER, “Power Diagrams: Properties, Algorithms and Applications”, 1987 Society for Industrial and Applied Mathematics, pp. 78-96, February 1987.
[2]P. Balister, S. Kumar and P. Sinha, Z. Zheng,”Trap Coverge: Allowing Coverage Holes of Bounded Diameter in Wireless Sensor Network”, IEEE INFOCOM 2009, Rio de Janeiro, Brazil, pp.19-25, April 2009.
[3]E. Bini, S. Fontanelli and P. Santi, “Dynamic route planning in vehicular networks based on future travel estimation” In IEEE VN, 2010, New Jersey City, NJ, USA, Dec. 2010.
[4]Jiming Chen, Yu Gu, Shibo He and Tian He, Junkun Li, Youxian Sun,”On Energy-Efficient Trap Coverage in Wireless Sensor Network”, 2011 IEEE 32nd Real-Time Systems Symposium, Vienna, Austria, Dec. 2011.
[5]Bih Lii Chua, Renee Ka Yin Chin, Chun Hoe Lee, Kit Guan Lim and Kenenth Tze Kin Teo,”Progressing Toward Urban Topology amd Mobility Trace for Vehicular Ad Hoc Network(VANET)”, Langkawi, Malaysia, 2016 IEEE Conference on Open Systems (ICOS), Oct. 2016.
[6]Tzung-Shi Chen ,Chia-Hsu Kuo and Siou-Ci Syu ,” Robust Mechanism of Trap Coverage and Target Tracking in Mobile Sensor Networks”, IEEE Internet of Things Journal ( Volume: 5 , Issue: 4 , Aug. 2018 ), pp. 3019-3030, April 2018.
[7]W. Chen, D. Li and S. Zhu, “Van: Vehicle-assisted shortest-time path navigation.”, In IEEE MASS, 2010, San Francisco, CA, USA, Nov. 2010.
[8]Soufiene Djahel, John Murphy and David Smith, ”A SUMO Based Evaluation of Road Incidents’ Impact on Traffic Congestion Level in Smart Cities”, 39th Annual IEEE Conference on Local Computer Networks Workshops, Edmonton, AB, Canada, Sept. 2014.
[9]Eric Feron , Jonathan How, Bart De Moor and Tom Schouwenaars , “Mixed integer programming for multi-vehicle path planning”, 2001 European Control Conference (ECC), pp.2603-2608, Porto, Portugal, April 2015.
[10]Bu Fu, Junsheng Liu and Qishuang Wang,“Multi-Sensor Integrated Navigation System for Ships Based on Adaptive Kalman Filter.”, 2019 IEEE International Conference on Mechatronics and Automation (ICMA), Tianjin, China, China, Aug. 2019.
[11]Q. W. Fu , S. H. Li , Y. Liu and Sh. Zhu , “Low-Cost MEMS-IMU/RTK Tightly Coupled Vehicle Navigation System with Robust Lane-Level Position Accuracy.”, 2019 26th Saint Petersburg International Conference on Integrated Navigation Systems (ICINS), Saint Petersburg, Russia, Russia, May 2019.
[12]Mevlut Turker Garip, Mehmet Emre Gursoy, Mario Gerla and Peter Reihe,”Scalable Reactive Vehicle-to-Vehicle Congestion Avoidance Mechanism”,2015 12th Annual IEEE Consumer Communications and Networking Conference (CCNC), Las Vegas, NV, Jan. 2015.
[13]Shang Gao, Zecheng Li, Zhe Peng, Yi Qian and Bin Xiao,”Vehicle Safety Improvement through Deep Learningamd Mobile Sensing”, IEEE Network, pp.28-33, August 2018.
[14]Louis Alberto Gutierrez, Nan Han, Shaojie Qiao and William Zhu,”TraPlan: An Effective Three-in-One Trajectory Prediction Model in Transportation Network”, IEEE Transactions on Intelligent Transportation Systems, pp.1188-1198, September 2014.
[15]Rui Jia, Pengcheng Jiang, Lei Liu, Lizhen Cui and Yuliang Shi ,“Data Driven Congestion Trends Prediction of Urban Transportation”, IEEE Internet of Things Journal ( Volume: 5 , Issue: 2 ), pp.581-591, June 2017.
[16]Shang Gao, Zecheng Li, Zhe Peng, Yi Qian and Bin Xiao, “Vehicle Safety Improvement through Deep Learning and Mobile Sensing”, IEEE Network,(Volume 32, Issue 4), pp.28-33, August 2018.
[17]Hongbo Jiang, Hongzhi Lin and Chen Wang, ”CANS: Towards Congestion-Adaptive and Small Stretch Emergency Navigation with Wireless Sensor Networks”, IEEE Transactions on Mobile Computing, pp.1077-1089, July 2015.
[18]Jaehoon Jeong, Jinyong Kim, Hyoungshick Kim, Taeho Kim, Jinho Lee and Jung-Soo Park,”SAN: Self-Adaptive Navigation for Drone Battery Charging in Wireless Drone Networks”, 2016 30th International Conference on Advanced Information Networking and Applications Workshops (WAINA), Crans-Montana, Switzerland, March 2016.
[19]F. Koushanfar , S.Megerian, M. Potkonjak and M.B. Srivastava,”Worst and Best-case Coverage in Sensor Networks”, IEEE Transactions on Mobile Computing , pp.84-92, January 2005.
[20]Xiangjie Kong, Jianxin Li, Chengfei Liu, Jinzhong Wang, Zhibo Wang and Feng Xia,” Exploring Human Mobility Patterns in Urban Scenarios: A Trajectory Data Perspective ”, IEEE Communications Magazine ( Volume: 56 , Issue: 3 , March 2018 ), pp.142-149, March 2018.
[21]Xuelian Lin, Rajiv Ranjan, Tianyu Wo, Hailun Wang, Jie Xu, Renyu Yang and Mingming Zhang, ”SMTP: An Optimized Storage Method for Vehicle Trajectory Data Exploiting Trajectory Patterns”, 2016 IEEE 18th International Conference on High Performance Computing and Communications, IEEE 14th International Conference on Smart City; IEEE 2nd International Conference on Data Science and Systems, Sydney, NSW, Australia, Dec. 2016.
[22]Feifei Li, Jeff M. Phillips and Dong Xie,“Distributed Trajectory Similarity Search”, Proceedings of the VLDB Endowment, Vol. 10, No. 11, pp.1478-1489, July 2017.
[23]Milos Milojevic , Veselin Rakocevic,“Short Paper: Distributed Vehicular Traffic Congestion Detection Algorithm for Urban Environments”, 2013 IEEE Vehicular Networking Conference, Boston, MA, USA, Dec. 2013.
[24]Yawei Pang, Lan Zhang, Haichuan Ding, Yuguang Fang and Shigang Chen,” SPATH: Finding the Safest Walking Path in Smart Cities”, IEEE Transactions on Vehicular Technology, pp.7071-7079, May 2019.
[25]Guo Qing, Xu Yue and Zhang Zheng,” Path-planning of automated guided vehicle based on improved Dijkstra algorithm”, 2017 29th Chinese Control And Decision Conference (CCDC), Chongqing, China, May 2017.
[26]X. Hu , Zh. Wang ,“A New Method Based on Dual-State Chi-Square Fault-Tolerant to Inertial/Acoustic Range Integrated Navigation System with Single Transponder.”, 2019 26th Saint Petersburg International Conference on Integrated Navigation Systems (ICINS), Saint Petersburg, Russia, Russia, , May 2019.