低軌道(LEO)衛星網路並沒有靜止軌道(GEO)同步衛星如此強的負載能力及信息處理速度乘載全球的通訊量，所以本論文設計了雙層巨型衛星星座(Large satellite constellation)及4進4出或8進8出的混合雷射(laser)及微波(microwave)的衛星間的鏈路(inter satellite link)滿足現今網路用戶數目及需求量越來越大的情況，但新的網路架構也對我們的研究帶來了巨大的挑戰。
本論文提出「壅塞避免之地理路由協定」(congestion avoidance Geographic Routing, CAGR)，使用On-line演算法能夠動態的應對衛星發生的各種狀況，其中的「貪婪式轉發」不只是會根據鄰居衛星位置分布狀況決定轉發衛星，更通過流量臨界值(traffic threshold)盡量避開負載較大的衛星，且使用球面轉平面投影能夠判斷角度及三維轉換二維經緯度使其能夠判斷交叉讓「邊緣轉發」在3D衛星網路上能夠運行，根據模擬結果我們的演算法能夠有效避開壅塞(avoid congestion)，使整個網路負載平衡，且從數據觀察出流量臨界值的最佳參數設計與封包到達率(arrive rate)之間的關係，隨著整個衛星網路的負載越大我們的演算法優勢就越明顯。

The Low Earth Orbit (LEO) satellite network does not have such strong load capacity and information processing speed as Geostationary Orbit (GEO) synchronous satellites, making it challenging to handle the global communication demands. Therefore, this paper proposes a dual-shell Large satellite constellation with 4-in-4-out or 8-in-8-out hybrid laser and microwave inter-satellite links (ISLs) to meet the increasing needs of network users. However, this new network architecture also brings significant challenges to our research.

This thesis introduces the "Congestion Aviodance Geographic Routing" (CAGR) protocol, utilizing an online algorithm to dynamically adapt to various satellite conditions. The "greedy forwarding" not only determines the forwarding satellites based on the distribution of neighboring satellites but also employs traffic thresholds to avoid heavily loaded satellites. By using spherical to planar projection, the algorithm is capable of considering angles and converting 3D coordinates to 2D latitude and longitude, enabling the "edge forwarding" to operate in a 3D satellite network. Simulation results demonstrate that our algorithm effectively avoids congestion, achieving load balancing across the entire network. Additionally, from the observed data, we establish the optimal parameter design of traffic thresholds and their relationship with packet arrival rates. As the overall satellite network load increases, the advantages of our algorithm become more evident.

摘要 I
Abstract III
誌謝 V
目錄 VII
圖目錄 IX
表目錄 XIII
第一章. 緒論 1
1.1. 前言 1
1.2. 研究動機 2
1.3. 研究目標 3
1.4. 研究方法 5
1.5. 各章節介紹 5
第二章. 相關研究背景介紹 7
2.1. 衛星星座架構 7
2.1.1. Walker delta constellation 7
2.1.2. Walker star constellation 9
2.2. 衛星網路圖 10
2.2.1. 單層衛星之間的inter satellite link 11
2.3. 多層衛星之間的inter satellite link 13
2.4. Two-line element set 14
2.5. 3D地理路由與3D結構圖 14
2.5.1. 3D Greedy Forwarding 15
2.6.1. Perimeter Forwarding 15
2.6. 衛星路由避免壅塞和負載平衡 18
2.7. 時變性的衛星網路路由 19
2.8. Our contribution 20
第三章. 問題陳述及參數定義 21
3.1. 網路環境設定 21
3.2. 衛星上的local maximum problem[27] 24
3.3. Routing model in mathematics 25
3.4. Inter satellite link delay 26
3.5. Propagation delay 26
3.6. Queuing delay 28
3.7. Transmission delay 30
第四章. 避免壅塞與負載感知地理式路由協定 33
4.1. 封包格式 33
4.2. 避免壅塞與負載感知地理式路由 (CAGR-Congestion avoidance geographic routing with load awarness) 34
4.3. 避免壅塞貪婪轉發演算法 37
4.4. Greedy Forwarding Function 38
4.5. Why Perimeter Forwarding can reach target 40
4.6. Right(Left)-hand Perimeter Forwarding Function 42
4.6.1. 衛星網路在球面上的投影 44
4.6.2. Intersection 判斷原理 46
4.6.3. 3D衛星網路平面化 48
4.7. Back Previous Function 49
第五章. 模擬實驗 53
5.1. Build queuing environment 54
5.2. Inter satellite link modern version 55
5.2.1. M/D/1/\infty/\infty模擬結果 55
5.2.2. M/M/1/\infty/\infty模擬結果 60
5.2.3. M/M/1/N/\infty模擬結果 64
5.3. Inter satellite link future version 72
5.3.1 M/D/1/\infty/\infty模擬結果 72
5.3.2 M/M/1/\infty/\infty模擬結果 76
5.3.3 M/M/1/\mathbf{N}/\infty模擬結果 80
5.4. 流量臨界值(traffic threshold)及參數設定的緣由 87
第六章. 結論及未來方向 93
6.1. 結論 93
6.2. 未來研究方向 93
參考文獻 95

[1] Y. Su, Y. Liu, Y. Zhou, J. Yuan, H. Cao and J. Shi, "Broadband LEO Satellite Communications: Architectures and Key Technologies," in IEEE Wireless Communications, vol. 26, no. 2, pp. 55-61, April 2019, doi: 10.1109/MWC.2019.1800299.
[2] F. Cadger, K. Curran, J. Santos and S. Moffett, "A Survey of Geographical Routing in Wireless Ad-Hoc Networks," in IEEE Communications Surveys & Tutorials, vol. 15, no. 2, pp. 621-653, Second Quarter 2013, doi: 10.1109/SURV.2012.062612.00109.
[3] H. Huang, H. Yin, Y. Luo, X. Zhang, G. Min and Q. Fan, "Three-dimensional geographic routing in wireless mobile ad hoc and sensor networks," in IEEE Network, vol. 30, no. 2, pp. 82-90, March-April 2016, doi: 10.1109/MNET.2016.7437029.
[4] Leyva-Mayorga, Israel et al. “NGSO Constellation Design for Global Connectivity.” ArXiv abs/2203.16597 (2022): n. pag.
[5] Debopam Bhattacherjee and Ankit Singla. 2019. Network topology design at 27,000 km/hour. In Proceedings of the 15th International Conference on Emerging Networking Experiments And Technologies (CoNEXT '19). Association for Computing Machinery, New York, NY, USA, 341–354. https://doi.org/10.1145/3359989.3365407
[6] Q. Chen, G. Giambene, L. Yang, C. Fan and X. Chen, "Analysis of Inter-Satellite Link Paths for LEO Mega-Constellation Networks," in IEEE Transactions on Vehicular Technology, vol. 70, no. 3, pp. 2743-2755, March 2021, doi: 10.1109/TVT.2021.3058126.
[7] Zheng, F., Wang, C., Zhou, Z. et al. LEO laser microwave hybrid inter-satellite routing strategy based on modified Q-routing algorithm. J Wireless Com Network 2022, 36 (2022). https://doi.org/10.1186/s13638-022-02119-1
[8] L. Yang and J. Sun, "Multi-service Routing Algorithm Based on Geo/Leo Satellite Networks," 2016 International Conference on Network and Information Systems for Computers (ICNISC), Wuhan, China, 2016, pp. 80-84, doi: 10.1109/ICNISC.2016.027.
[9] M. Nugroho and N. M. N. Khamsah, "Study on Impact of Outdated Two-Line Element Sets in Tracking of LAPAN-A2 and LAPAN-A3 Satellites," 2018 IEEE International Conference on Aerospace Electronics and Remote Sensing Technology (ICARES), Bali, Indonesia, 2018, pp. 1-6, doi: 10.1109/ICARES.2018.8547116.
[10] Kranakis, Evangelos et al. “Compass routing on geometric networks.” Canadian Conference on Computational Geometry (1999).
[11] Brad Karp and H. T. Kung. 2000. GPSR: greedy perimeter stateless routing for wireless networks. In Proceedings of the 6th annual international conference on Mobile computing and networking (MobiCom '00). Association for Computing Machinery, New York, NY, USA, 243–254. https://doi.org/10.1145/345910.345953
[12] K. Gabriel and M. Pearlman. A New Statistical Approach to Geographic Variation Analysis. Systematic Zoology, 18:259278, 1969
[13] G. Toussaint. The Relative Neighborhood Graph of a Finite Planar Set. Pattern Recognition, 12(5):261268, 1980.
[14] Jie Gao, L. J. Guibas, J. Hershberger, Li Zhang and An Zhu, "Geometric spanners for routing in mobile networks," in IEEE Journal on Selected Areas in Communications, vol. 23, no. 1, pp. 174-185, Jan. 2005, doi: 10.1109/JSAC.2004.837364.
[15] Wang, Yu & İk, Tsì-Uí & Huang, Minsu & Li, Fan. (2010). Three Dimensional Greedy Routing in Large-Scale Random Wireless Sensor Networks. Ad Hoc Networks Journal. 11. 10.1016/j.adhoc.2010.10.003.
[16] C. Liu and J. Wu, "Efficient Geometric Routing in Three Dimensional Ad Hoc Networks," IEEE INFOCOM 2009, Rio de Janeiro, Brazil, 2009, pp. 2751-2755, doi: 10.1109/INFCOM.2009.5062225.
[17] Xia, S.; Yin, X.; Wu, H.; Jin, M.; Gu, X.D. Deterministic Greedy Routing with Guaranteed Delivery in 3D Wireless Sensor Networks. Axioms 2014, 3, 177-201. https://doi.org/10.3390/axioms3020177
[18] Yu Wang, Chih-Wei Yi, Minsu Huang, and Fan Li. 2013. Three-dimensional greedy routing in large-scale random wireless sensor networks. Ad Hoc Netw. 11, 4 (June, 2013), 1331–1344. https://doi.org/10.1016/j.adhoc.2010.10.003
[19] M. Mohorcic, M. Werner, et al., “Adaptive routing for packet-oriented intersatellite link networks: performance in various traffic scenarios,” IEEE Transactions on Wireless Communications, vol. 1, no. 4, Oct 2002, pp. 808–818.
[20] R. Kucukates and C. Ersoy, “High performance routing in a leo satellite network,” in Proceedings of the Eighth IEEE Symposium on Computers and Communications. ISCC 2003, vol. 2, July 2003, pp. 1403–1408
[21] W. Liu, Y. Tao, et al., “Load-balancing routing algorithm based on segment routing for traffic return in leo satellite networks,” IEEE Access, vol. 7, 2019, pp. 112 044–112 053.
[22] C. Dong, X. Xu, A. Liu and X. Liang, "Load balancing routing algorithm based on extended link states in LEO constellation network," in China Communications, vol. 19, no. 2, pp. 247-260, Feb. 2022, doi: 10.23919/JCC.2022.02.020.
[23] J. Tao, Z. Na and N. Zhang, "Time-varying Graph Model for LEO Satellite Network Routing," 2022 9th International Conference on Dependable Systems and Their Applications (DSA), Wulumuqi, China, 2022, pp. 486-491, doi: 10.1109/DSA56465.2022.00070.
[24] Z. Han, C. Xu, G. Zhao, S. Wang, K. Cheng and S. Yu, "Time-Varying Topology Model for Dynamic Routing in LEO Satellite Constellation Networks," in IEEE Transactions on Vehicular Technology, vol. 72, no. 3, pp. 3440-3454, March 2023, doi: 10.1109/TVT.2022.3217952.
[25] P. Zha, C. Long, J. Wu and S. Li, "Satellite Lifetime Predicted Greedy Perimeter Stateless Routing Protocol for LEO Satellite Network," 2020 Chinese Automation Congress (CAC), Shanghai, China, 2020, pp. 5102-5107, doi: 10.1109/CAC51589.2020.9326774.
[26] Mark Handley. 2018. Delay is Not an Option: Low Latency Routing in Space. In Proceedings of the 17th ACM Workshop on Hot Topics in Networks (HotNets '18). Association for Computing Machinery, New York, NY, USA, 85–91. https://doi.org/10.1145/3286062.3286075
[27] T. R. Henderson and R. H. Katz, "On distributed, geographic-based packet routing for LEO satellite networks," Globecom '00 - IEEE. Global Telecommunications Conference. Conference Record (Cat. No.00CH37137), San Francisco, CA, USA, 2000, pp. 1119-1123 vol.2, doi: 10.1109/GLOCOM.2000.891311.
[28] W. Liang, Z. Naitong and W. Pingping, "Dynamic characteristics of inter-satellite links in LEO networks," in Journal of Systems Engineering and Electronics, vol. 14, no. 4, pp. 25-29, Dec. 2003.
[29] Prosenjit Bose, Pat Morin, Ivan Stojmenović, and Jorge Urrutia. 1999. Routing with guaranteed delivery in ad hoc wireless networks. In Proceedings of the 3rd international workshop on Discrete algorithms and methods for mobile computing and communications (DIALM '99). Association for Computing Machinery, New York, NY, USA, 48–55. https://doi.org/10.1145/313239.313282