雲端伺服器向終端用戶提供了強大的計算能力，是一種很有前景的工作分配方法。然而，因工作分配到雲端伺服器處理可能會造成較長的傳輸與等待時間，邊緣運算的提出使得用戶能供將工作分配到較近的邊緣伺服器。然而，邊緣伺務器的擺放和工作分配會顯著的影響工作傳輸與作業的效能，進而影響使用者體驗。因此，在網路中，適當的伺服器擺放位置與公平的分配工作就顯得格外重要。本論文同時考慮了邊緣伺服器的工作量與工作傳輸所需要的距離來當作主要影響因素。而為了更進一步改善使用者體驗，邊緣伺服器的擺放位置會經過精心挑選，且分配到邊緣伺服器的工作也會經過均衡分配來達到負載平衡。此問題為一個混合整數線性規劃問題，對於此問題，本論文中提出了一種新的解決方法。此解決方案透過使用整合的拉格朗日對偶理論和次梯度方法來進行工作分配，並同時透過模擬退火演算法來尋找邊緣伺服器的最佳擺放位置。實驗結果證實，本論文所提出的方法可以達到比傳統啟發式演算法更好的結果。

Offloading tasks to cloud servers has increasingly been used to provide terminal users with powerful computation capabilities for a variety of services. Recently, edge computing, which offloads tasks from user devices to nearby edge servers, has been exploited to avoid the long latency associated with cloud computing. However, edge server placement and task allocation strongly affect the offloading process and the quality of a user's experience. Therefore, appropriately deploying the edge servers within a network and evenly allocating the workload to the servers are vital. This paper thus considers both the workload of edge servers and the distances involved in offloading tasks to these servers. To improve the user experience, edge server locations are carefully selected and the workload for the servers are allocated in a balanced manner. This scenario is formulated as a mixed-integer linear programming problem, and a novel solution that searches for the best server placement using simulated annealing while integrating task allocation using the Lagrangian duality theory with the sub-gradient method is proposed. Numerical simulations verify that the proposed algorithm can achieve better results than conventional heuristics.

[1] J. Cohen, “Embedded speech recognition applications in mobile phones: Status, trends, and challenges,”
in IEEE Intl. Conf. on Acoustics, Speech and Signal Process., pp. 5352–5355, IEEE, 2008.
[2] Y. Shangguan, J. Li, Q. Liang, R. Alvarez, and I. McGraw, “Optimizing speech recognition for the
edge,” arXiv preprint arXiv:1909.12408, 2019.
[3] B. P. Rimal, E. Choi, and I. Lumb, “A taxonomy and survey of cloud computing systems,” in Int. Joint
Conf., pp. 44–51, 2009.
[4] W. Shi, J. Cao, Q. Zhang, Y. Li, and L. Xu, “Edge computing: Vision and challenges,” IEEE internet
of things journal, vol. 3, no. 5, pp. 637–646, 2016.
[5] S. K. uz Zaman, A. I. Jehangiri, T. Maqsood, Z. Ahmad, A. I. Umar, J. Shuja, E. Alanazi, and W. Alasmary,
“Mobilityaware
computational offloading in mobile edge networks: a survey,” Cluster Computing
journal, pp. 1–22, 2021.
[6] S. Wan, X. Li, Y. Xue, W. Lin, and X. Xu, “Efficient computation offloading for internet of vehicles in
edge computingassisted
5g networks,” The Journal of Supercomput., vol. 76, no. 4, pp. 2518–2547,
2020.
[7] X. Xu, Y. Li, T. Huang, Y. Xue, K. Peng, L. Qi, and W. Dou, “An energyaware
computation offloading
method for smart edge computing in wireless metropolitan area networks,” Journal of Netw. and
Comput. Applica., vol. 133, pp. 75–85, 2019.
[8] A. Pradhan and S. K. Bisoy, “A novel load balancing technique for cloud computing platform based
on pso,” Journal of King Saud UniversityComput.
and Inform. Sci., 2020.
[9] G. Li, Y. Yao, J. Wu, X. Liu, X. Sheng, and Q. Lin, “A new load balancing strategy by task allocation
in edge computing based on intermediary nodes,” EURASIP Journal on Wireless Commun. and Netw.,
vol. 2020, no. 1, pp. 1–10, 2020.
[10] A. Auslender and M. Teboulle, “Lagrangian duality and related multiplier methods for variational
inequality problems,” SIAM Journal on Optim., vol. 10, no. 4, pp. 1097–1115, 2000.
[11] Q. Ye, B. Rong, Y. Chen, M. AlShalash,
C. Caramanis, and J. G. Andrews, “User association for
load balancing in heterogeneous cellular networks,” IEEE Trans. on Wirel. Commun., vol. 12, no. 6,
pp. 2706–2716, 2013.
[12] G. Athanasiou, P. C. Weeraddana, C. Fischione, and L. Tassiulas, “Optimizing client association
for load balancing and fairness in millimeterwave
wireless networks,” IEEE/ACM Trans. on Netw.,
vol. 23, no. 3, pp. 836–850, 2014.
[13] X. Chen, “Decentralized computation offloading game for mobile cloud computing,” IEEE Trans. on
Parallel and Distri. Syst., vol. 26, no. 4, pp. 974–983, 2014.
[14] M.H.
Chen, M. Dong, and B. Liang, “Multiuser
mobile cloud offloading game with computing
access point,” in 2016 5th IEEE Intl. Conf. on Cloud Netw., pp. 64–69, 2016.
[15] X. Ma, C. Lin, X. Xiang, and C. Chen, “Gametheoretic
analysis of computation offloading for
cloudletbased
mobile cloud computing,” in Proc. of Intl. Conf. on Modeling, Analysis and Simulation
of Wireless and Mobile Syst., pp. 271–278, 2015.
[16] J. Zheng, Y. Cai, Y. Wu, and X. Shen, “Dynamic computation offloading for mobile cloud computing:
A stochastic gametheoretic
approach,” IEEE Trans. on Mob. Comput., vol. 18, no. 4, pp. 771–786,
2018.
[17] H. Li, K. Ota, and M. Dong, “Learning iot in edge: Deep learning for the internet of things with edge
computing,” IEEE Netw., vol. 32, no. 1, pp. 96–101, 2018.
[18] J. Shuja, K. Bilal, W. Alasmary, H. Sinky, and E. Alanazi, “Applying machine learning techniques for
caching in nextgeneration
edge networks: A comprehensive survey,” Journal of Netw. and Computer
Appl., p. 103005, 2021.
[19] F. Zeng, Y. Ren, X. Deng, and W. Li, “Costeffective
edge server placement in wireless metropolitan
area networks,” Sensors, vol. 19, no. 1, p. 32, 2019.
[20] H. Yin, X. Zhang, H. H. Liu, Y. Luo, C. Tian, S. Zhao, and F. Li, “Edge provisioning with flexible
server placement,” IEEE Trans. on Parallel and Distrib. Syst., vol. 28, no. 4, pp. 1031–1045, 2016.
[21] J. Lim and D. Lee, “A load balancing algorithm for mobile devices in edge cloud computing environments,”
Electron., vol. 9, no. 4, p. 686, 2020.
[22] M. Tang and S. Pan, “A hybrid genetic algorithm for the energyefficient
virtual machine placement
problem in data centers,” Neural Process. letters, vol. 41, no. 2, pp. 211–221, 2015.
[23] X. Xu, Y. Xue, X. Li, L. Qi, and S. Wan, “A computation offloading method for edge computing with
vehicletoeverything,”
IEEE Access, vol. 7, pp. 131068–131077, 2019.
[24] Y. Li and S. Wang, “An energyaware
edge server placement algorithm in mobile edge computing,”
in IEEE Intl. Conf. on Edge Comput., pp. 66–73, 2018.
[25] X. Xu, B. Shen, X. Yin, M. R. Khosravi, H. Wu, L. Qi, and S. Wan, “Edge server quantification and
placement for offloading social media services in industrial cognitive iov,” IEEE Trans. on Industr.
Inform., vol. 17, no. 4, pp. 2910–2918, 2020.
[26] Y. Guo, S. Wang, A. Zhou, J. Xu, J. Yuan, and C.H.
Hsu, “User allocationaware
edge cloud placement
in mobile edge computing,” Software: Pract. and Exper., vol. 50, no. 5, pp. 489–502, 2020.
[27] B. Heller, R. Sherwood, and N. McKeown, “The controller placement problem,” ACM SIGCOMM
Computer Communi. Review, vol. 42, no. 4, pp. 473–478, 2012.
[28] D. Levin, A. Wundsam, B. Heller, N. Handigol, and A. Feldmann, “Logically centralized? state
distribution tradeoffs
in software defined networks,” pp. 1–6, 2012.
[29] D. Kreutz, F. M. Ramos, and P. Verissimo, “Towards secure and dependable softwaredefined
networks,”
pp. 55–60, 2013.
[30] P. Xiao, W. Qu, H. Qi, Z. Li, and Y. Xu, “The sdn controller placement problem for wan,” pp. 220–224,
2014.
[31] G. Wang, Y. Zhao, J. Huang, and Y. Wu, “An effective approach to controller placement in software
defined wide area networks,” IEEE Trans. on Netw. and Service Manag., vol. 15, no. 1, pp. 344–355,
2017.
[32] Q. Qin, K. Poularakis, G. Iosifidis, and L. Tassiulas, “Sdn controller placement at the edge: Optimizing
delay and overheads,” in IEEE Conf. on Computer Communi., pp. 684–692, IEEE, 2018.
[33] A. Nedic and A. Ozdaglar, “Distributed subgradient methods for multiagent
optimization,” IEEE
Trans. on Automat. Contr., vol. 54, no. 1, pp. 48–61, 2009.
[34] W. Wang and M. A. CarreiraPerpinán,
“Projection onto the probability simplex: An efficient algorithm
with a simple proof, and an application,” arXiv preprint arXiv:1309.1541, 2013.
[35] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, “Optimization by simulated annealing,” Sci., vol. 220,
no. 4598, pp. 671–680, 1983.
[36] H.S.
Park and C.H.
Jun, “A simple and fast algorithm for kmedoids
clustering,” Expert Syst. with
Appl., vol. 36, no. 2, pp. 3336–3341, 2009.
[37] R. RumipambaZambrano,
J. Perelló, and S. Spadaro, “Route, modulation format, mimo, and spectrum
assignment in flexgrid/
mcf transparent optical core networks,” Light. Technol., vol. 36, no. 16,
pp. 3534–3546, 2018.