臺灣博碩士論文加值系統

隨著第五代行動通訊技術的快速發展，車輛已具備和邊緣伺服器聯網之能力並可向其請求服務。然而，車輛有高度的移動特性，且邊緣伺服器涵蓋範圍有限，會導致車輛頻繁地切換不同邊緣伺服器，增加了服務遞送的困難。若服務具備共享性，則必須判斷是否存放服務運算結果，或者重新計算服務，以權衡計算資源與儲存資源的使用量。在服務配置能滿足所有請求的情況下，最佳化資源利用是一個有挑戰性的問題。
為了解決這個問題，我們將服務配置轉化成圖表。根據圖表，我們能夠判斷請求是否被滿足，同時也能計算資源的使用量。我們提出一個迭代演算法的框架，先由選擇器模組選出每一輪要處理的請求，再由配置器模組直接滿足該請求，直到所有請求都滿足為止。選擇器與配置器可以有不同的實作，我們提出兩種配置器，第一種將服務配置在車輛會經過的所有邊緣伺服器，但僅會停留一小段時間；第二種將服務盡可能延長服務停留的時間，最小化配置服務的邊緣伺服器數量。另外，我們使用雙向鏈結串列設計出管理請求狀態的方法，在問題不可解時，該方法能給予車輛速限指示，使問題變得可解。將迭代演算法以及請求狀態結合後，我們就能滿足所有請求，並且最小化資源使用。實驗結果顯示，我們的方法和天真的演算法相比能夠大幅降低資源使用，第一種配置器較適合節省計算資源，第二種則是節省儲存資源。

With the rapid development of the 5th generation mobile networks, vehicles are able to connect to edge servers and request services. However, the high mobility of vehicles combined with the short-range coverage of edge servers results in frequent handovers, increasing the difficulty of service delivery. With shareable services, there will be a trade off between storage resources and computation resources, resulting from whether buffering service results in edge servers for sharing or simply executing services for each request. It is challenging to allocate services so that all requests are satisfied while also minimizing resource consumption.
To solve this problem, we start by demonstrating the allocation problem in diagrams. Based on the diagrams, we are able to determine if a request is satisfied, and calculate the resource consumption. The proposed approach includes an iteration, which separates the solving process into selecting requests and allocating services for requests. These two parts can be implemented by pluggable modules. We propose two allocation approaches that guarantee to satisfy vehicle requests with variable velocities. The first approach allocates services at every edge server that the vehicle passes through, but with a short buffering time. The other approach extends the buffering time as long as possible so that the service is only allocated at necessary edge servers. Furthermore, we use doubly-linked lists to manage the states of requests. If there is no feasible solution, the states are able to tell us at what speed conditions the requests can be satisfied. Combining the allocation approaches and the states, we are able to satisfy requests with reduced resource consumption. Compared with the naive baseline, experimental results show both approaches consume lower resources. The first approach is better at reducing computation resources and is more suitable for smaller scales. On the other hand, the second approach has lower storage consumption, and its advantages are more obvious when the scales are large and the coverage of servers is small.

Acknowledgements iii
Abstract (Chinese) iv
Abstract vi
List of Tables x
List of Figures xi
Chapter 1. Introduction 1
1.1 Related Work ................................. 3
1.1.1 Vehicular Edge Computing ...................... 3
1.1.2 Service Allocation and Delivery.................... 4
1.1.3 Freshness................................ 5
1.1.4 Mobility ................................ 5
1.2 Thesis Organization.............................. 6
Chapter 2. System Model and Problem Descriptions 7
2.1 System Model................................. 7
2.1.1 Entities Descriptions.......................... 7
2.1.2 Scenario Descriptions ......................... 8
2.2 Assumptions.................................. 9
2.2.1 Variable Velocities........................... 9
2.2.2 Shared Services............................. 11
2.2.3 Time Windows of Requests ...................... 11
2.2.4 Freshness................................ 11
2.3 Problem Descriptions............................. 12
2.3.1 Request Diagram............................ 12
2.3.2 Trajectory Modeling.......................... 14
2.3.3 Allocation Diagram and Objectives.................. 15
Chapter 3. Proposed Approaches 18
3.1 Request State ................................. 19
3.1.1 Description of Request State ..................... 19
3.1.2 Implementation of Request State................... 21
3.2 Selection and Allocation ........................... 23
3.3 Merging and Alignment............................ 26
Chapter 4. Experimental Results 29
4.1 Experimental Setup.............................. 29
4.1.1 Servers ................................. 30
4.1.2 Vehicles................................. 30
4.1.3 Services and Requests......................... 30
4.1.4 Timesand Velocity .......................... 31
4.1.5 Objectives ............................... 31
4.2 Allocators and Request States ........................ 31
4.3 Selectors.................................... 33
4.4 Runtimes.................................... 34
4.5 Freshness.................................... 35
4.6 Coverage.................................... 36
4.7 Allocators Combination............................ 37
4.8 Visualization.................................. 38
4.9 Discussion ................................... 39
Chapter 5. Conclusions 41
Bibliography 43

[1] AECC, “White paper: Distributed computing in an aecc system,” in Automotive Edge Computing Consortium (AECC), 2021.
[2] S. Batabyal and P. Bhaumik, “Mobility models, traces and impact of mobility on opportunistic routing algorithms: A survey,” IEEE Communications Surveys Tutorials, vol. 17, no. 3, pp. 1679–1707, 2015.
[3] L. F. Bittencourt, J. Diaz-Montes, R. Buyya, O. F. Rana, and M. Parashar, “Mobility-aware application scheduling in fog computing,” IEEE Cloud Computing, vol. 4, no. 2, pp. 26–35, 2017.
[4] S. Chen, L. Shi, X. Ding, Z. Lv, and Z. Li, “Energy efficient resource allocation and trajectory optimization in uav-assisted mobile edge computing system,” in 2021 7th International Conference on Big Data Computing and Communications (BigCom), pp. 7–13, 2021.
[5] J. Feng, Z. Liu, C. Wu, and Y. Ji, “Ave: Autonomous vehicular edge computing framework with aco-based scheduling,” IEEE Transactions on Vehicular Technology, vol. 66, no. 12, pp. 10 660–10 675, 2017.
[6] C. Fu, X. Qiu, Z. Yun, S. Han, W. Wu, and C. J. Xue, “Keep fresh: Real-time data retrieval with speed adaptation in mobile cyber-physical systems,” in 2021 IEEE Real-Time Systems Symposium (RTSS), pp. 304–315, 2021.
[7] A. Gupta, J. J. Cherukara, D. Gangadharan, B. Kim, O. Sokolsky, and I. Lee, “E-pods: A fast heuristic for data/service delivery in vehicular edge computing,” in 2021 IEEE 93rd Vehicular Technology Conference (VTC2021-Spring), pp. 1–6, 2021.
[8] A. Hammoud, H. Sami, A. Mourad, H. Otrok, R. Mizouni, and J. Bentahar, “Ai, blockchain, and vehicular edge computing for smart and secure iov: Challenges and directions,” IEEE Internet of Things Magazine, vol. 3, no. 2, pp. 68–73, 2020.
[9] J. Hu, C. Chen, L. Cai, M. R. Khosravi, Q. Pei, and S. Wan, “Uav-assisted vehicular edge computing for the 6g internet of vehicles: Architecture, intelligence, and challenges,” IEEE Communications Standards Magazine, vol. 5, no. 2, pp. 12–18, 2021.
[10] Y. C. Hu, M. Patel, D. Sabella, N. Sprecher, and V. Young, “Mobile edge computing—a key technology towards 5g,” ETSI white paper, vol. 11, no. 11, pp. 1–16, 2015.
[11] X. Huang, L. He, and W. Zhang, “Vehicle speed aware computing task offloading and resource allocation based on multi-agent reinforcement learning in a vehicular edge computing network,” in 2020 IEEE International Conference on Edge Computing (EDGE), pp. 1–8, 2020.
[12] J. Kang, R. Yu, X. Huang, M. Wu, S. Maharjan, S. Xie, and Y. Zhang, “Blockchain for secure and efficient data sharing in vehicular edge computing and networks,” IEEE Internet of Things Journal, vol. 6, no. 3, pp. 4660–4670, 2019.
[13] H. Liu, S. Zhang, P. Zhang, X. Zhou, X. Shao, G. Pu, and Y. Zhang, “Blockchain and federated learning for collaborative intrusion detection in vehicular edge computing,” IEEE Transactions on Vehicular Technology, vol. 70, no. 6, pp. 6073–6084, 2021.
[14] P. Q. Liu L, Chen C et al., “Vehicular edge computing and networking: A survey,” in Mobile Networks and Applications, pp. 1145–1168. Springer, 2021.
[15] Z. Ning, P. Dong, X. Wang, J. J. P. C. Rodrigues, and F. Xia, “Deep reinforcement learning for vehicular edge computing: An intelligent offloading system,” vol. 10, no. 6, oct 2019. [Online]. Available: https: //doi.org/10.1145/3317572
[16] Y. Sun, X. Guo, J. Song, S. Zhou, Z. Jiang, X. Liu, and Z. Niu, “Adaptive learning-based task offloading for vehicular edge computing systems,” IEEE Transactions on Vehicular Technology, vol. 68, no. 4, pp. 3061–3074, 2019
[17] D. Wang, X. Tian, H. Cui, and Z. Liu, “Reinforcement learning-based joint task offloading and migration schemes optimization in mobility-aware mec network,” China Communications, vol. 17, no. 8, pp. 31–44, 2020.
[18] L.-Y. Wang, “Edge-computing-based task allocation and scheduling for con- nected and autonomous vehicles / li-yeou wang,” 2021.
[19] M. Xiong and K. Ramamritham, “Deriving deadlines and periods for real-time update transactions,” IEEE Transactions on Computers, vol. 53, no. 5, pp. 567–583, 2004.
[20] M. Xiong, S. Han, K.-Y. Lam, and D. Chen, “Deferrable scheduling for maintaining real-time data freshness: Algorithms, analysis, and results,” IEEE Transactions on Computers, vol. 57, no. 7, pp. 952–964, 2008.
[21] D. Ye, R. Yu, M. Pan, and Z. Han, “Federated learning in vehicular edge computing: A selective model aggregation approach,” IEEE Access, vol. 8, pp. 23 920–23 935, 2020.
[22] W. Zhan, C. Luo, J. Wang, C. Wang, G. Min, H. Duan, and Q. Zhu, “Deep- reinforcement-learning-based offloading scheduling for vehicular edge comput- ing,” IEEE Internet of Things Journal, vol. 7, no. 6, pp. 5449–5465, 2020.
[23] K. Zhang, J. Cao, and Y. Zhang, “Adaptive digital twin and multiagent deep reinforcement learning for vehicular edge computing and networks,” IEEE Transactions on Industrial Informatics, vol. 18, no. 2, pp. 1405–1413, 2022.
[24] Y. Zhao and B. Kim, “Optimizing allocation and scheduling of connected vehicle service requests in cloud/edge computing,” in 2020 IEEE 13th International Conference on Cloud Computing (CLOUD), pp. 361–369, 2020.