1. NCCU Academic Hub
  2. Publications
  3. College of Informatics
  4. Theses
  5. Item

Publications-Theses

Article View/Open

Publication Export

Google ScholarTM

NCCU Library

Citation Infomation

Related Publications in TAIR

題名 基於無人機微服務網路的吞吐量與能耗聯合優化之啟發式方法
A Heuristic Approach to Joint Throughput and Energy Optimization in UAV-Based Microservices Networks
作者 林尚儀
Lin, Shang-Yi
貢獻者 郭桐惟
Kuo, Tung-Wei
林尚儀
Lin, Shang-Yi
關鍵詞 無人機網路
微服務架構
吞吐量與能耗聯合最佳化
混合整數線性規劃
貪婪啟發式演算法
UAV networks
Microservices architecture
Joint optimization of throughput and energy
Mixed Integer Linear Programming (MILP)
Greedy heuristic algorithm
日期 2026
上傳時間 2-Mar-2026 13:42:38 (UTC+8)
摘要 本研究聚焦於以微服務為基礎的無人機網路（microservices-based UAV networks），探討在農村與災後地區等基礎設施不足場景中，如何在有限的無人機與能源預算下，同時兼顧網路吞吐量與能耗的權衡問題。 我們首先重新檢視既有方法的 MILP 模型中造成計算複雜度升高的二次乘積項，透過引入輔助變數與改寫限制式，將其轉換為邏輯意義等價的線性 MILP。結果顯示，線性化後的模型在不同場景下皆能維持與原始模型相同的最佳目標值與部署決策，同時將求解時間縮短數十倍至數千倍。 其次，我們提出一個三階段貪婪啟發式演算法：第一階段以最低吞吐量需求為基準建立可行部署。第二階段在不增加無人機數量的前提下，於區域內重整請求與剩餘資源配置。第三階段則採用迭代式增援策略，僅在新增無人機能明顯提升目標函數時才接受變更。模擬結果顯示，在多種需求分佈、服務參數與區域規模設定下，所提出的三階段貪婪啟發式演算法能在遠低於 MILP 的計算時間內，達成近似於 MILP 最佳解的表現。
This study focuses on microservices-based UAV networks, addressing the trade-off between network throughput and energy consumption in infrastructure-deficient scenarios, such as rural and post-disaster areas, under limited UAV and energy budgets. First, we re-examine the quadratic product terms in the original model that lead to high computational complexity. By introducing auxiliary variables and reformulating constraints, we transform the model into an equivalent linear Mixed Integer Linear Programming (MILP) model. The results demonstrate that the linearized model maintains the same optimal objective values and deployment decisions as the original model across various scenarios while reducing the solving time by tens to thousands of times. Second, we propose a 3-Phase Greedy heuristic algorithm. The first phase establishes a feasible deployment based on minimum throughput requirements. The second phase reorganizes request allocation and residual resources within areas without increasing the number of UAVs. The third phase adopts an iterative reinforcement strategy, accepting changes only when adding a new UAV significantly improves the objective function. Simulation results indicate that under various demand distributions, service parameters, and area scale settings, the proposed 3-Phase Greedy method achieves performance close to the MILP optimal solution with significantly lower computation time.
參考文獻 [1] M. Basharat, M. Naeem, Z. Qadir, and A. Anpalagan, "Resource optimization in uav-assisted wireless networks comprehensive survey," Transactions on Emerging Telecommunications Technologies, vol. 33, no. 7, p. e4464, 2022. [2] J. Galan-Jimenez, E. Moguel, J. Garcia-Alonso, and J. Berrocal, "Energy-efficient and solar powered mission planning of uav swarms to reduce the coverage gap in rural areas: The 3d case," Ad Hoc Networks, vol. 118, p. 102517, 2021. [3] J. Galán-Jiménez, A. G. Vegas, and J. Berrocal, "Energy-efficient deployment of iot applications in remote rural areas using uav networks," in 2022 14th IFIP Wireless and Mobile Networking Conference (WMNC), pp. 70-74, IEEE, 2022. [4] A. Abada, B. Yang, and T. Taleb, "Traffic flow modeling for uav-enabled wireless networks," in 2020 International Conference on Networking and Network Applications (NaNA), pp. 59-64, IEEE, 2020. [5] S. G. Gil, J. M. Murillo, and J. Galán-Jiménez, "Optimizing iot microservices placement for latency reduction in uav-assisted wireless networks," in 2023 IEEE 20th International Conference on Mobile Ad Hoc and Smart Systems (MASS), pp. 658-663, IEEE, 2023. [6] L. Matlekovic, F. Juric, and P. Schneider-Kamp, "Microservices for autonomous uav inspection with uav simulation as a service," Simulation Modelling Practice and Theory, vol. 119, p. 102548, 2022. [7] Q. Zhang, M. Jiang, Z. Feng, W. Li, W. Zhang, and M. Pan, "Iot enabled uav: Network architecture and routing algorithm," IEEE Internet of Things Journal, vol. 6, no. 2, pp. 3727-3742, 2019. [8] S. G. Gil, J. A. G. de la Hiz, D. R. Ramos, J. M. Murillo, and J. Galán-Jimenez, "Drl-based coverage optimization in uav networks for microservice-based iot applications," in Applications of Machine Learning in UAV Networks, pp. 27-54, IGI Global, 2024. [9] M. Kishk, A. Bader, and M.-S. Alouini, "Aerial base station deployment in 6g cellular networks using tethered drones: The mobility and endurance tradeoff," IEEE Vehicular Technology Magazine, vol. 15, no. 4, pp. 103-111, 2020. [10] J. Gómez-DelaHiz, A. Fakhreddine, J. M. Murillo, and J. Galán-Jiménez, "Joint optimization of throughput and energy consumption in microservices-based uav networks," in IEEE INFOCOM 2024-IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), pp. 1-6, IEEE, 2024. [11] J. Gómez-delaHiz, A. García-López, S. García-Gil, D. Ramos-Ramos, A. Fakhreddine, J. M. Murillo, and J. Galán-Jiménez, "Throughput-energy efficiency trade-off in microservices-based uav networks," in 2024 IEEE Symposium on Computers and Communications (ISCC), pp. 1-6, 2024. [12] M. Alzenad, A. El-Keyi, F. Lagum, and H. Yanikomeroglu, "3-d placement of an unmanned aerial vehicle base station (uav-bs) for energy-efficient maximal coverage," IEEE Wireless Communications Letters, vol. 6, no. 4, pp. 434-437, 2017. [13] L. Wang, B. Hu, and S. Chen, "Energy efficient placement of a drone base station for minimum required transmit power," IEEE Wireless Communications Letters, vol. 9, no. 12, pp. 2010-2014, 2018. [14] M. Chen, M. Mozaffari, W. Saad, C. Yin, M. Debbah, and C. S. Hong, "Caching in the sky: Proactive deployment of cache-enabled unmanned aerial vehicles for optimized quality-of-experience," IEEE Journal on Selected Areas in Communications, vol. 35, no. 5, pp. 1046-1061, 2017. [15] L. Amorosi, L. Chiaraviglio, F. D'Andreagiovanni, and N. Blefari-Melazzi, "Energy-efficient mission planning of uavs for 5g coverage in rural zones," in 2018 IEEE international conference on environmental engineering (EE), pp. 1-9, IEEE, 2018. [16] J. G. Jiménez, L. Chiaraviglio, L. Amorosi, and N. Blefari-Melazzi, "Multi-period mission planning of uavs for 5g coverage in rural areas: a heuristic approach," in 2018 9th International Conference on the Network of the Future (NOF), pp. 52-59, IEEE, 2018. [17] C. Zhan and H. Lai, "Energy minimization in internet-of-things system based on rotary-wing uav," IEEE Wireless Communications Letters, vol. 8, no. 5, pp. 1341-1344, 2019. [18] J. Zhang, Z. Li, W. Xu, J. Peng, W. Liang, Z. Xu, X. Ren, and X. Jia, "Minimizing the number of deployed uavs for delay-bounded data collection of iot devices," in IEEE INFOCOM 2021-IEEE Conference on Computer Communications, pp. 1-10, IEEE, 2021. [19] H. Huang, C. Huang, and D. Ma, "A method for deploying the minimal number of uav base stations in cellular networks," IEEE/CAA Journal of Automatica Sinica, vol. 7, no. 2, pp. 559-567, 2020. [20] L. Chiaraviglio, L. Amorosi, F. Malandrino, C. F. Chiasserini, P. Dell'Olmo, and C. Casetti, "Optimal throughput management in uav-based networks during disasters," in IEEE INFOCOM 2019-IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), pp. 307-312, IEEE, 2019. [21] W. Xu, Y. Sun, R. Zou, W. Liang, Q. Xia, F. Shan, T. Wang, X. Jia, and Z. Li, "Throughput maximization of uav networks," IEEE/ACM Transactions on Networking, vol. 30, no. 2, pp. 881-895, 2021. [22] I. Donevski, C. Raffelsberger, M. Sende, A. Fakhreddine, and J. J. Nielsen, "An experimental analysis on drone-mounted access points for improved latency-reliability," in Proceedings of the 7th Workshop on Micro Aerial Vehicle Networks, Systems, and Applications, pp. 31-36, 2021. [23] H. Hellaoui, M. Bagaa, A. Chelli, T. Taleb, and B. Yang, "On supporting multiservices in uav-enabled aerial communication for internet of things," IEEE Internet of Things Journal, vol. 10, no. 15, pp. 13754-13768, 2023. [24] T. LI, M. SHENG, R. LYU, J. LIU, and J. LI, "Uav assisted heterogeneous wireless networks: potentials and challenges," ZTE Communications, vol. 16, no. 2, pp. 3-8, 2019. [25] L. Amorosi, L. Chiaraviglio, and J. Galan-Jimenez, "Optimal energy management of uav-based cellular networks powered by solar panels and batteries: Formulation and solutions," IEEE Access, vol. 7, pp. 53698-53717, 2019.
描述 碩士
國立政治大學
資訊科學系
111753220
資料來源 http://thesis.lib.nccu.edu.tw/record/#G0111753220
資料類型 thesis
dc.contributor.advisor 郭桐惟zh_TW
dc.contributor.advisor Kuo, Tung-Weien_US
dc.contributor.author (Authors) 林尚儀zh_TW
dc.contributor.author (Authors) Lin, Shang-Yien_US
dc.creator (作者) 林尚儀zh_TW
dc.creator (作者) Lin, Shang-Yien_US
dc.date (日期) 2026en_US
dc.date.accessioned 2-Mar-2026 13:42:38 (UTC+8)-
dc.date.available 2-Mar-2026 13:42:38 (UTC+8)-
dc.date.issued (上傳時間) 2-Mar-2026 13:42:38 (UTC+8)-
dc.identifier (Other Identifiers) G0111753220en_US
dc.identifier.uri (URI) https://nccur.lib.nccu.edu.tw/handle/140.119/161938-
dc.description (描述) 碩士zh_TW
dc.description (描述) 國立政治大學zh_TW
dc.description (描述) 資訊科學系zh_TW
dc.description (描述) 111753220zh_TW
dc.description.abstract (摘要) 本研究聚焦於以微服務為基礎的無人機網路（microservices-based UAV networks），探討在農村與災後地區等基礎設施不足場景中，如何在有限的無人機與能源預算下，同時兼顧網路吞吐量與能耗的權衡問題。 我們首先重新檢視既有方法的 MILP 模型中造成計算複雜度升高的二次乘積項，透過引入輔助變數與改寫限制式，將其轉換為邏輯意義等價的線性 MILP。結果顯示，線性化後的模型在不同場景下皆能維持與原始模型相同的最佳目標值與部署決策，同時將求解時間縮短數十倍至數千倍。 其次，我們提出一個三階段貪婪啟發式演算法：第一階段以最低吞吐量需求為基準建立可行部署。第二階段在不增加無人機數量的前提下，於區域內重整請求與剩餘資源配置。第三階段則採用迭代式增援策略，僅在新增無人機能明顯提升目標函數時才接受變更。模擬結果顯示，在多種需求分佈、服務參數與區域規模設定下，所提出的三階段貪婪啟發式演算法能在遠低於 MILP 的計算時間內，達成近似於 MILP 最佳解的表現。zh_TW
dc.description.abstract (摘要) This study focuses on microservices-based UAV networks, addressing the trade-off between network throughput and energy consumption in infrastructure-deficient scenarios, such as rural and post-disaster areas, under limited UAV and energy budgets. First, we re-examine the quadratic product terms in the original model that lead to high computational complexity. By introducing auxiliary variables and reformulating constraints, we transform the model into an equivalent linear Mixed Integer Linear Programming (MILP) model. The results demonstrate that the linearized model maintains the same optimal objective values and deployment decisions as the original model across various scenarios while reducing the solving time by tens to thousands of times. Second, we propose a 3-Phase Greedy heuristic algorithm. The first phase establishes a feasible deployment based on minimum throughput requirements. The second phase reorganizes request allocation and residual resources within areas without increasing the number of UAVs. The third phase adopts an iterative reinforcement strategy, accepting changes only when adding a new UAV significantly improves the objective function. Simulation results indicate that under various demand distributions, service parameters, and area scale settings, the proposed 3-Phase Greedy method achieves performance close to the MILP optimal solution with significantly lower computation time.en_US
dc.description.tableofcontents 誌謝 i 摘要 ii Abstract iii 目錄 v 圖目錄 vii 表目錄 ix 1 緒論 1 1.1 研究背景 1 1.2 研究目標 3 2 無人機部署系統模型 5 2.1 系統模型 5 2.2 問題定義 6 2.2.1 輸入參數 7 2.2.2 變數定義 8 2.2.3 目標函數與限制式 8 2.3 與現有模型之關係 10 2.3.1 既有的吞吐量與能耗聯合優化模型 10 2.3.2 MILP：避免二次項 11 3 無人機部署演算法 15 3.1 3-Phase Greedy Heuristic 15 3.2 Phase 1：最低需求部署 17 3.3 Phase 2：資源配置優化 21 3.4 Phase 3：迭代式無人機增援 26 3.5 討論：3-Phase Greedy 與 MILP 等價之條件分析 32 4 實驗結果與分析 35 4.1 實驗設定 35 4.1.1 評估指標 35 4.1.2 比較方法 36 4.1.3 實驗參數與情境設定 37 4.2 結果分析 40 4.2.1 解的品質分析 41 4.2.2 執行時間效能分析 52 4.2.3 消融研究 60 5 相關研究 65 5.1 能耗優化 65 5.1.1 基地台部署位置 65 5.1.2 任務規劃與能源管理 66 5.1.3 軌跡設計 66 5.1.4 無人機數量優化 66 5.2 吞吐量與服務品質優化 67 5.3 傳輸延遲優化 67 5.4 覆蓋範圍優化 68 6 結論 70 參考文獻 72zh_TW
dc.format.extent 3392254 bytes-
dc.format.mimetype application/pdf-
dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#G0111753220en_US
dc.subject (關鍵詞) 無人機網路zh_TW
dc.subject (關鍵詞) 微服務架構zh_TW
dc.subject (關鍵詞) 吞吐量與能耗聯合最佳化zh_TW
dc.subject (關鍵詞) 混合整數線性規劃zh_TW
dc.subject (關鍵詞) 貪婪啟發式演算法zh_TW
dc.subject (關鍵詞) UAV networksen_US
dc.subject (關鍵詞) Microservices architectureen_US
dc.subject (關鍵詞) Joint optimization of throughput and energyen_US
dc.subject (關鍵詞) Mixed Integer Linear Programming (MILP)en_US
dc.subject (關鍵詞) Greedy heuristic algorithmen_US
dc.title (題名) 基於無人機微服務網路的吞吐量與能耗聯合優化之啟發式方法zh_TW
dc.title (題名) A Heuristic Approach to Joint Throughput and Energy Optimization in UAV-Based Microservices Networksen_US
dc.type (資料類型) thesisen_US
dc.relation.reference (參考文獻) [1] M. Basharat, M. Naeem, Z. Qadir, and A. Anpalagan, "Resource optimization in uav-assisted wireless networks comprehensive survey," Transactions on Emerging Telecommunications Technologies, vol. 33, no. 7, p. e4464, 2022. [2] J. Galan-Jimenez, E. Moguel, J. Garcia-Alonso, and J. Berrocal, "Energy-efficient and solar powered mission planning of uav swarms to reduce the coverage gap in rural areas: The 3d case," Ad Hoc Networks, vol. 118, p. 102517, 2021. [3] J. Galán-Jiménez, A. G. Vegas, and J. Berrocal, "Energy-efficient deployment of iot applications in remote rural areas using uav networks," in 2022 14th IFIP Wireless and Mobile Networking Conference (WMNC), pp. 70-74, IEEE, 2022. [4] A. Abada, B. Yang, and T. Taleb, "Traffic flow modeling for uav-enabled wireless networks," in 2020 International Conference on Networking and Network Applications (NaNA), pp. 59-64, IEEE, 2020. [5] S. G. Gil, J. M. Murillo, and J. Galán-Jiménez, "Optimizing iot microservices placement for latency reduction in uav-assisted wireless networks," in 2023 IEEE 20th International Conference on Mobile Ad Hoc and Smart Systems (MASS), pp. 658-663, IEEE, 2023. [6] L. Matlekovic, F. Juric, and P. Schneider-Kamp, "Microservices for autonomous uav inspection with uav simulation as a service," Simulation Modelling Practice and Theory, vol. 119, p. 102548, 2022. [7] Q. Zhang, M. Jiang, Z. Feng, W. Li, W. Zhang, and M. Pan, "Iot enabled uav: Network architecture and routing algorithm," IEEE Internet of Things Journal, vol. 6, no. 2, pp. 3727-3742, 2019. [8] S. G. Gil, J. A. G. de la Hiz, D. R. Ramos, J. M. Murillo, and J. Galán-Jimenez, "Drl-based coverage optimization in uav networks for microservice-based iot applications," in Applications of Machine Learning in UAV Networks, pp. 27-54, IGI Global, 2024. [9] M. Kishk, A. Bader, and M.-S. Alouini, "Aerial base station deployment in 6g cellular networks using tethered drones: The mobility and endurance tradeoff," IEEE Vehicular Technology Magazine, vol. 15, no. 4, pp. 103-111, 2020. [10] J. Gómez-DelaHiz, A. Fakhreddine, J. M. Murillo, and J. Galán-Jiménez, "Joint optimization of throughput and energy consumption in microservices-based uav networks," in IEEE INFOCOM 2024-IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), pp. 1-6, IEEE, 2024. [11] J. Gómez-delaHiz, A. García-López, S. García-Gil, D. Ramos-Ramos, A. Fakhreddine, J. M. Murillo, and J. Galán-Jiménez, "Throughput-energy efficiency trade-off in microservices-based uav networks," in 2024 IEEE Symposium on Computers and Communications (ISCC), pp. 1-6, 2024. [12] M. Alzenad, A. El-Keyi, F. Lagum, and H. Yanikomeroglu, "3-d placement of an unmanned aerial vehicle base station (uav-bs) for energy-efficient maximal coverage," IEEE Wireless Communications Letters, vol. 6, no. 4, pp. 434-437, 2017. [13] L. Wang, B. Hu, and S. Chen, "Energy efficient placement of a drone base station for minimum required transmit power," IEEE Wireless Communications Letters, vol. 9, no. 12, pp. 2010-2014, 2018. [14] M. Chen, M. Mozaffari, W. Saad, C. Yin, M. Debbah, and C. S. Hong, "Caching in the sky: Proactive deployment of cache-enabled unmanned aerial vehicles for optimized quality-of-experience," IEEE Journal on Selected Areas in Communications, vol. 35, no. 5, pp. 1046-1061, 2017. [15] L. Amorosi, L. Chiaraviglio, F. D'Andreagiovanni, and N. Blefari-Melazzi, "Energy-efficient mission planning of uavs for 5g coverage in rural zones," in 2018 IEEE international conference on environmental engineering (EE), pp. 1-9, IEEE, 2018. [16] J. G. Jiménez, L. Chiaraviglio, L. Amorosi, and N. Blefari-Melazzi, "Multi-period mission planning of uavs for 5g coverage in rural areas: a heuristic approach," in 2018 9th International Conference on the Network of the Future (NOF), pp. 52-59, IEEE, 2018. [17] C. Zhan and H. Lai, "Energy minimization in internet-of-things system based on rotary-wing uav," IEEE Wireless Communications Letters, vol. 8, no. 5, pp. 1341-1344, 2019. [18] J. Zhang, Z. Li, W. Xu, J. Peng, W. Liang, Z. Xu, X. Ren, and X. Jia, "Minimizing the number of deployed uavs for delay-bounded data collection of iot devices," in IEEE INFOCOM 2021-IEEE Conference on Computer Communications, pp. 1-10, IEEE, 2021. [19] H. Huang, C. Huang, and D. Ma, "A method for deploying the minimal number of uav base stations in cellular networks," IEEE/CAA Journal of Automatica Sinica, vol. 7, no. 2, pp. 559-567, 2020. [20] L. Chiaraviglio, L. Amorosi, F. Malandrino, C. F. Chiasserini, P. Dell'Olmo, and C. Casetti, "Optimal throughput management in uav-based networks during disasters," in IEEE INFOCOM 2019-IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), pp. 307-312, IEEE, 2019. [21] W. Xu, Y. Sun, R. Zou, W. Liang, Q. Xia, F. Shan, T. Wang, X. Jia, and Z. Li, "Throughput maximization of uav networks," IEEE/ACM Transactions on Networking, vol. 30, no. 2, pp. 881-895, 2021. [22] I. Donevski, C. Raffelsberger, M. Sende, A. Fakhreddine, and J. J. Nielsen, "An experimental analysis on drone-mounted access points for improved latency-reliability," in Proceedings of the 7th Workshop on Micro Aerial Vehicle Networks, Systems, and Applications, pp. 31-36, 2021. [23] H. Hellaoui, M. Bagaa, A. Chelli, T. Taleb, and B. Yang, "On supporting multiservices in uav-enabled aerial communication for internet of things," IEEE Internet of Things Journal, vol. 10, no. 15, pp. 13754-13768, 2023. [24] T. LI, M. SHENG, R. LYU, J. LIU, and J. LI, "Uav assisted heterogeneous wireless networks: potentials and challenges," ZTE Communications, vol. 16, no. 2, pp. 3-8, 2019. [25] L. Amorosi, L. Chiaraviglio, and J. Galan-Jimenez, "Optimal energy management of uav-based cellular networks powered by solar panels and batteries: Formulation and solutions," IEEE Access, vol. 7, pp. 53698-53717, 2019.zh_TW