隨著基於雲端服務的應用程式如雨後春筍般出現，如Google Workspace與亞馬遜雲端服務(AWS)，已經給人們帶來許多使用上的方便。對服務提供商與服務使用者來說，利用雲端運算已經逐漸變成一個趨勢。由於通訊科技持續進化，使用日常生活中的裝置連到網際網路也變得非常便利，然而這會造成越來越多終端裝置，如智慧型手機或是物聯網裝置，傳送工作運算要求給雲端運算伺服器，這將導致裝置們所傳送的工作要求的平均等待時間被拉的很長。除此之外，使用者與雲端運算伺服器的距離也非常遙遠，在傳送距離這麼大的時候，也會造成傳輸延遲時間變大。為了去改善雲端服務的使用體驗(QoE)，邊緣運算的概念就被提出來解決這個問題。利用架設多個邊緣伺服器在距離使用者的地方，俗稱邊緣網路，以分擔來自終端裝置的服務請求。通過在接近使用者的多個邊緣伺服器去處理運算請求，可以達到較低的通訊延遲與運算等待時間，也可以降低在整體網路中傳輸的流量。因此，這些邊緣伺服器在網路拓墣中的架設位置就顯得非常重要。同時，使用者們要向多個邊緣伺服器中的哪一個送出服務請求也是個難題，因為隨著邊緣伺服器的佈置位置不同，也會影響到與使用者之間的距離。在這本論文中，一個平衡工作負載的模型被提出，並把使用者與邊緣伺服器的距離給納入考量。這個問題被簡化成一個混合整數的非線性問題。最後，我們設計一個特別的演算法用來替這個問題找出近似解，並在模擬實驗中獲得較其他演算法更優的運算效率與近似解效益。

The emergence of several cloud-based applications, such as Google Workspace and Amazon Web Services (AWS), has brought users much convenience. Cloud computing has become a trend for both application developers and users, since communication technology keeps evolving, access to the Internet for devices is much easier than before. However, the more and more computing requirement from terminal devices like the smartphone or IoT sensor may cause a long queuing time in a single cloud server. Besides, the long-distance transmission between devices and a remote cloud server may cause a severe communication delay. To improve the Quality of Experience (QoE), edge computing is proposed to set multiple edge servers close to devices and share the workload. Deploying the edge servers close to users rather than forwarding all the requests to the cloud server far away can reduce the response time and traffic load in the network. Therefore, the locations of placement for edge servers are quite essential in the topology. Also, the assignment of computing requests to edge servers is still a challenging problem in workload balance since different locations of edge servers will lead to various distances from a device to the offloading edge server. In this paper, a load balancing model, which also takes distance from devices to edge servers into account, is proposed. The objective function is formulated as a mixed-integer non-linear problem (MINLP). Moreover, A specific algorithm, $K$-Center Cluster Balance (KCCB), is also proposed to find a feasible solution for this problem. The simulation result shows that KCCB has more computational efficiency and a better solution than other algorithms.

[1] J. Santos, P. Leroux, T. Wauters, B. Volckaert, and F. De Turck, “Anomaly detection for smart city
applications over 5G low power wide area networks,” in Proc. IEEE/IFIP Netw. Oper. Manage. Symp.,
pp. 1–9, May 2018.
[2] V. L. Kalyani and D. Sharma, “IoT: machine to machine (M2M), device to device (D2D) internet of
everything (IoE) and human to human (H2H): future of communication,” J. Manag. Eng. Inf. Technol(JEMIT), vol. 2, no. 6, pp. 17–23, Dec. 2015.
[3] J. Gubbi, R. Buyya, S. Marusic, and M. Palaniswami, “Internet of things (IoT): A vision, architectural
elements, and future directions,” Future Gen. Comp. Syst., vol. 29, no. 7, pp. 1645–1660, Sep. 2013.
[4] J. Gausemeier, J. Fruend, C. Matysczok, B. Bruederlin, and D. Beier, “Development of a real time
image based object recognition method for mobile AR­devices,” in Proc. 2nd Int’l. Conf. Comput.
Graphics, Virtual Reality, Visualisation and Interaction in Africa, pp. 133–139, Feb. 2003.
[5] A. Celesti, D. Mulfari, M. Fazio, M. Villari, and A. Puliafito, “Exploring container virtualization in
IoT clouds,” in Proc. IEEE Int. Conf. Smart Comput. (SMARTCOMP), pp. 1–6, May 2016.
[6] X. Xu, “From cloud computing to cloud manufacturing,” Robot. Comput.­Integr. Manuf., vol. 28,
no. 1, pp. 75–86, Feb. 2012.
[7] C. Blum, P. Pinacho, M. López­Ibáñez, and J. A. Lozano, “Construct, merge, solve & adapt a new
general algorithm for combinatorial optimization,” Comput. Oper. Res., vol. 68, pp. 75–88, Apr. 2016.
[8] D. N. Simopoulos, S. D. Kavatza, and C. D. Vournas, “Unit commitment by an enhanced simulated
annealing algorithm,” IEEE Trans. Power Syst., vol. 21, no. 1, pp. 68–76, Feb. 2006.
[9] K. Wagstaff, C. Cardie, S. Rogers, S. Schrödl, et al., “Constrained k­means clustering with background
knowledge,” in Proc. 18th Int. Conf. Mach. Learning(ICML), vol. 1, pp. 577–584, Jan. 2001.
[10] M. Satyanarayanan, P. Bahl, R. Caceres, and N. Davies, “The case for VM­based cloudlets in mobile
computing,” IEEE Pervasive Comput., vol. 8, no. 4, pp. 14–23, Oct./Dec. 2009.
[11] F. Bonomi, R. Milito, J. Zhu, and S. Addepalli, “Fog computing and its role in the internet of things,”
in Proc. 1st Edition MCC Workshop Mobile Cloud Comput., pp. 13–16, Aug. 2012.
[12] P. McMullen and R. Strong, “Determination of lockbox collection points via simulated annealing,” J.
Op. Res. Soc., vol. 50, no. 1, pp. 44–51, Jan. 1999.
[13] G. Laporte, S. Nickel, and F. Saldanha da Gama, eds., Location science. Berlin, Germany:Springer,
ISBN: 978­3­319­13111­5, 2015.
[14] B. Tang, H. Gupta, and S. R. Das, “Benefit­based data caching in ad hoc networks,” IEEE Tran. Mobile
Comput., vol. 7, no. 3, pp. 289–304, Mar. 2008.
[15] H. Yin, X. Zhang, H. H. Liu, Y. Luo, C. Tian, S. Zhao, and F. Li, “Edge provisioning with flexible
server placement,” IEEE Trans. Parallel Distrib. Syst., vol. 28, no. 4, pp. 1031–1045, Apr. 2017.
[16] Y. Ren, F. Zeng, W. Li, and L. Meng, “A low­cost edge server placement strategy in wireless
metropolitan area networks,” in Proc. 27th Int. Conf. Comput. Commun. Netw. (ICCCN), pp. 1–6,
IEEE, Jul. 2018.
[17] B. Heller, R. Sherwood, and N. McKeown, “The controller placement problem,” SIGCOMM Comp.
Commun. Rev., vol. 42, no. 4, pp. 473–478, Sep. 2012.
[18] G. Yao, J. Bi, Y. Li, and L. Guo, “On the capacitated controller placement problem in software defined
networks,” IEEE Commun. Letters, vol. 18, no. 8, pp. 1339–1342, Aug. 2014.
[19] G. Wang, Y. Zhao, J. Huang, and Y. Wu, “An effective approach to controller placement in software
defined wide area networks,” IEEE Trans. Netw. Service Manage., vol. 15, no. 1, pp. 344–355, Mar.
2018.
[20] Q. Qin, K. Poularakis, G. Iosifidis, and L. Tassiulas, “SDN controller placement at the edge: Optimizing delay and overheads,” in Proc. IEEE Conf. Comput. Commun. (INFOCOM), pp. 684–692, Apr.
2018.
[21] G. Athanasiou, P. C. Weeraddana, C. Fischione, and L. Tassiulas, “Optimizing client association for
load balancing and fairness in millimeter­wave wireless networks,” IEEE/ACM Trans. Netw., vol. 23,
no. 3, pp. 836–850, Jun. 2015.
[22] Y. Dai, D. Xu, S. Maharjan, and Y. Zhang, “Joint load balancing and offloading in vehicular edge
computing and networks,” IEEE Internet Things J., vol. 6, no. 3, pp. 4377–4387, Jun. 2019.
[23] X. Niu, S. Shao, C. Xin, J. Zhou, S. Guo, X. Chen, and F. Qi, “Workload allocation mechanism
for minimum service delay in edge computing­based power internet of things,” IEEE Access, vol. 7,
pp. 83771–83784, May 2019.
[24] M. M. S. Maswood, M. R. Rahman, A. G. Alharbi, and D. Medhi, “A novel strategy to achieve
bandwidth cost reduction and load balancing in a cooperative three­layer fog­cloud computing environment,” IEEE Access, vol. 8, pp. 113737–113750, Jun. 2020.
[25] X. Chen, L. Jiao, W. Li, and X. Fu, “Efficient multi­user computation offloading for mobile­edge
cloud computing,” IEEE/ACM Trans. Netw., vol. 24, no. 5, pp. 2795–2808, Oct. 2016.
[26] T. Han and N. Ansari, “Network utility aware traffic load balancing in backhaul­constrained cacheenabled small cell networks with hybrid power supplies,” IEEE Trans. Mobile Comput., vol. 16, no. 10,
pp. 2819–2832, Oct. 2017.
[27] Q. Fan and N. Ansari, “Towards workload balancing in fog computing empowered IoT,” IEEE Trans.
Netw. Sci. Eng., vol. 7, no. 1, pp. 253–262, Jan./Mar. 2020.
[28] T. Hu, P. Yi, J. Zhang, and J. Lan, “A distributed decision mechanism for controller load balancing
based on switch migration in SDN,” China Commun., vol. 15, no. 10, pp. 129–142, Oct. 2018.
[29] G. Li, X. Wang, and Z. Zhang, “SDN­based load balancing scheme for multi­controller deployment,”
IEEE Access, vol. 7, pp. 39612–39622, Mar. 2019.
[30] L. Qiu, V. N. Padmanabhan, and G. M. Voelker, “On the placement of web server replicas,” in Proc.
IEEE Conf. Comput. Commun. (INFOCOM), vol. 3, pp. 1587–1596, Apr. 2001.
[31] T.­L. Chin, Y.­S. Chen, and K.­Y. Lyu, “Queuing model based edge placement for work offloading in
mobile cloud networks,” IEEE Access, vol. 8, pp. 47295–47303, Mar. 2020.
[32] S. Wang, Y. Zhao, J. Xu, J. Yuan, and C.­H. Hsu, “Edge server placement in mobile edge computing,”
J. Parallel Distrib. Comput., vol. 127, pp. 160–168, May 2019.
[33] Y. Li and S. Wang, “An energy­aware edge server placement algorithm in mobile edge computing,”
in Proc. IEEE Int. Conf. Edge Comput. (EDGE), pp. 66–73, Jul. 2018.
[34] P. Laborie, J. Rogerie, P. Shaw, and P. Vilím, “IBM ILOG CP optimizer for scheduling,” Constraints,
vol. 23, no. 2, pp. 210–250, Apr. 2018.
[35] H. Badri, T. Bahreini, D. Grosu, and K. Yang, “A sample average approximation­based parallel algorithm for application placement in edge computing systems,” in Proc. IEEE Int. Conf. on Cloud Eng.
(IC2E), pp. 198–203, Apr. 2018.
[36] J. Xu, L. Chen, and P. Zhou, “Joint service caching and task offloading for mobile edge computing in
dense networks,” in Proc. IEEE Conf. Comput. Commun. (INFOCOM), pp. 207–215, Oct. 2018.
[37] N. Mouawad, R. Naja, and S. Tohme, “Optimal and dynamic SDN controller placement,” in Proc. Int.
Conf. Comp. and Appl. (ICCA), pp. 1–9, IEEE, Aug. 2018.
[38] K. Yang, D. Guo, B. Zhang, and B. Zhao, “Multi­controller placement for load balancing in SDWAN,”
IEEE Access, vol. 7, pp. 167278–167289, Nov. 2019.
[39] C.­W. Lin, “Analysis of response time for task offloading in mobile edge computing,” m.s. thesis,
Sch. of Comp. Sci. and Inform. Eng., National Taiwan Univ. of Sci. and Tech.(NTUST), Taipei, Taiwan(R.O.C.), Aug. 2019.
[40] M. S. Daskin, Network and discrete location: models, algorithms, and applications. John Wiley &
Sons, ISBN: 978­1­118­53701­5, Jun. 2013.
[41] N. L. van Adrichem, F. Iqbal, and F. A. Kuipers, “Backup rules in software­defined networks,” in
Proc. IEEE Conf. Netw. Function Virtualization Softw. Defined Netw. (NFV­SDN), pp. 179–185, Nov.
2016.