淡江大學覺生紀念圖書館 (TKU Library)

系統識別號 U0002-2409202006355700
中文論文名稱 最小化任務完成時間之多無人機動態充電排程技術
英文論文名稱 A Dynamic Charging Scheduling Algorithm of Multi-UAV for Minimizing Mission Completion Time
校院名稱 淡江大學
系所名稱(中) 資訊工程學系碩士班
系所名稱(英) Department of Computer Science and Information Engineering
學年度 108
學期 2
出版年 109
研究生中文姓名 韓覲陽
研究生英文姓名 JIN-YANG HAN
學號 607410171
學位類別 碩士
語文別 中文
第二語文別 英文
口試日期 2020-07-10
論文頁數 64頁
口試委員 指導教授-石貴平
中文關鍵字 多無人機  多充電站  碰撞問題  充電排程規劃 
英文關鍵字 Multiple UAVs  multiple charging stations  collision problems  charging scheduling planning 
學科別分類 學科別應用科學資訊工程
中文摘要 無人機的應用非常廣泛,由於其靈活性與機動性,因此能夠適用於各種大型區域中,如軍事應用、工業控制與環境監測等。通常無人機在執行任務時,需要長距離飛行,由於其電池容量有限,往往需要依靠充電站補充其電量。在充電站數量有限的情況下,若無良好的充電排程,可能因多台無人機待在同一個充電站,而造成多無人機發生壅塞的情形,產生長久的等待充電時間及增加整體工作時間的問題。因此,如何針對無人機的充電需求,發展一個良好的排程,使無人機能即早完成充電且能盡早到達目的地,一直是學者共同努力的目標。本論文提出四種多樣化之動態充電排程模型,分別為單一充電站不可搶先不可換充電站、單一充電站可搶先不可換充電站、多充電站不可搶先可換充電站與多充電站可搶先且可換充電站,採用漸進式地優化,減少多無人機於充電站發生雍塞的問題,並且,進一步縮短整體無人機之瓶頸,以期達到任務完成時間最小化的目標。
英文摘要 UAV is widely used, because of its flexibility and mobility, it can be applied to various large areas, such as military applications, industrial control and environmental monitoring. Usually, UAVs need to fly for a long distance when performing tasks. Due to the limited battery capacity, it is necessary to rely on charging stations to supplement its power. In the case of limited number of charging stations, if it is not good, it will be better if it is not good The charging schedule of UAVs may be caused by multiple UAVs staying at the same charging station, which may lead to the problem of long waiting for charging and increasing the overall working time. Therefore, it is a common concern of scholars to develop a good charging schedule for UAVs to complete charging as soon as possible and arrive at the destination as soon as possible In this paper, four kinds of dynamic charging scheduling models are proposed, which are non preemptive non replaceable charging station for single charging station, preemptive non replaceable charging station for single charging station, non preemptive replaceable charging station for multiple charging stations, and preemptive and replaceable charging station for multiple charging stations Furthermore, the bottleneck of UAV is further reduced to minimize the mission completion time.
According to the experimental data, compared with CBDN algorithm, the four kinds of charging scheduling technology proposed in this paper can effectively solve the congestion of UAV network, shorten the time of UAV network movement, charging and waiting, and reduce the time of UAV arriving at the destination.
論文目次 目錄
目錄 V
圖目錄 VII
表目錄 IX
第一章、簡介 1
第二章、相關研究 6
第三章、網路環境與問題描述 10
3-1網路環境 10
3-2問題描述 12
3-3假設與限制 15
第四章、多無人機之動態充電排程技術 18
4-1模型介紹 19
4-2探索充電站階段 24
4-3充電排程階段 26
第五章、績效評估 36
第六章、結論 43
參考文獻 44
附錄-英文論文 46
圖 1:無人機環境 11
圖 2:影響任務完成因子 14
圖 3:無人機於充電站示意圖。 15
圖 4:安排多無人機於充電站 20
圖 5:模型一排程示意圖 20
圖 6:已有無人機於充電站充電 21
圖 7: 模型二排程示意圖 21
圖 8:更改充電站充電 22
圖 9:模型三排程示意圖 23
圖 10:中途更改充電站 24
圖 11:模型四排程示意圖 24
圖 12:充電站之使用率比較圖 38
圖 13:無人機數量與飛行時間的關係 39
圖 14:無人機數量與充電站使用效率 39
圖 15:充電站數量與飛行時間的關係 40
圖 16:充電站數量與充電站使用效率 41
圖 17:無人機速度與飛行時間 42
表 1:符號總表 12
表 2:模型一演算法 27
表 3:模型二演算法 29
表 4:模型三演算法 31
表 5:模型四演算法 34
表 6:模擬設置 37
參考文獻 [1] M. Lu, A. James and M. Bagheri, "Unmanned Aerial Vehicle (UAV) charging from powerlines," 2017 IEEE PES Asia-Pacific Power and Energy Engineering Conference (APPEEC), Bangalore,Nov, 2017, pp. 1-6.
[2] Y. Hu, J. Gao, X. Chen, F. Meng and Y. H. Wang, "Distribution Planning of UAV Automatic Charging Station Based on Genetic Algorithm," 2019 International Conference on Economic Management and Model Engineering (ICEMME), Malacca, Malaysia, 2019, pp. 446-452.
[3] K. Wei, J. Wu, W. Ma and H. Li, "State of charge prediction for UAVs based on support vector machine," in The Journal of Engineering, vol. 2019, no. 23, pp. 9133-9136, 12 2019.
[4] J. Xu, K. Zhu and R. Wang, "RF Aerially Charging Scheduling for UAV Fleet : A Q-Learning Approach," 2019 15th International Conference on Mobile Ad-Hoc and Sensor Networks (MSN), Shenzhen, China , Dec. 2019, pp. 194-199.
[5] C. H. Choi, H. J. Jang, S. G. Lim, H. C. Lim, S. H. Cho and I. Gaponov, "Automatic wireless drone charging station creating essential environment for continuous drone operation," 2016 International Conference on Control, Automation and Information Sciences (ICCAIS), Ansan, Oct. 2016, pp. 132-136.
[6] A. Trotta, M. D. Felice, F. Montori, K. R. Chowdhury and L. Bononi, "Joint Coverage, Connectivity, and Charging Strategies for Distributed UAV Networks," in IEEE Transactions on Robotics, vol. 34, no. 4, pp. 883-900, Aug. 2018.
[7] M. Erdelj, O. Saif, E. Natalizio and I. Fantoni, "UAVs that fly forever: Uninterrupted structural inspection through automatic UAV replacement" in Ad Hoc Netw., pp. 1-13, Dec. 2017.
[8] E. T. Alotaibi, S. S. Alqefari and A. Koubaa, "LSAR: Multi-UAV Collaboration for Search and Rescue Missions," in IEEE Access, vol. 7, pp. 55817-55832, 2019.
[9] C. Zhan and Y. Zeng, "Completion Time Minimization for Multi-UAV-Enabled Data Collection," in IEEE Transactions on Wireless Communications, vol. 18, no. 10, pp. 4859-4872, Oct. 2019.
[10] S. Zhang, Y. Zeng and R. Zhang, "Cellular-Enabled UAV Communication: Trajectory Optimization under Connectivity Constraint," 2018 IEEE International Conference on Communications (ICC), Kansas City, MO, 2018, pp. 1-6.
[11] Avellar, G.S.C.; Pereira, G.A.S.; Pimenta, L.C.A.; Iscold, P. Multi-UAV Routing for Area Coverage and Remote Sensing with Minimum Time. Sensors 2015.
[12] H. Binol, E. Bulut, K. Akkaya and I. Guvenc, "Time Optimal Multi-UAV Path Planning for Gathering its Data from Roadside Units," 2018 IEEE 88th Vehicular Technology Conference (VTC-Fall), Chicago, IL, USA, 2018, pp. 1-5.
[13] J. Li et al., "Joint Optimization on Trajectory, Altitude, Velocity, and Link Scheduling for Minimum Mission Time in UAV-Aided Data Collection," in IEEE Internet of Things Journal, vol. 7, no. 2, pp. 1464-1475, Feb. 2020.
[14] J. Kim, S. Kim, J. Jeong, H. Kim, J. Park and T. Kim, "CBDN: Cloud-Based Drone Navigation for Efficient Battery Charging in Drone Networks," in IEEE Transactions on Intelligent Transportation Systems, vol. 20, no. 11, pp. 4174-4191, Nov. 2019.
[15] H. Ghazzai, A. Kadri, M. Ben Ghorbel and H. Menouar, "Optimal Sequential and Parallel UAV Scheduling for Multi-Event Applications," 2018 IEEE 87th Vehicular Technology Conference (VTC Spring), Porto, 2018, pp. 1-6.
[16] X. Li, H. Yao, J. Wang, S. Wu, C. Jiang and Y. Qian, "Rechargeable Multi-UAV Aided Seamless Coverage for QoS-Guaranteed IoT Networks," in IEEE Internet of Things Journal, vol. 6, no. 6, pp. 10902-10914, Dec. 2019.
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2025-09-24公開。
  • 同意授權瀏覽/列印電子全文服務,於2025-09-24起公開。

  • 若您有任何疑問,請與我們聯絡!
    圖書館: 請來電 (02)2621-5656 轉 2487 或 來信