隨著科技進步，物聯網(IoT) 設備的數量以極為驚人的速度增加。不過物聯網設備有著計算能力有限以及電池續航力較差這樣明顯的缺點。因此，使用邊緣計算(Mobile Computing) 和集群技術(Clustering Technology) 等方法構建協作系統被認為是一種可以彌補這些不足的策略。這樣一來，物聯網設備可以將復雜的任務卸載到邊緣伺服器從而提高計算能力並因此減少任務所需的回應時間。本論文研究了物聯網中任務卸載的集群構建問題。也就是要在網路節點中構建集群以在處理卸載任務的邊緣伺服器之間平衡負載差異。這問題會被描述為整數規劃問題，用來部署邊緣伺服器並進行卸載任務的分配，而這些卸載任務的分配則受傳輸距離和使用者之任務請求率的影響。在本論文中，沒有選擇使用啟發式演算法(Heuristic Algorithm) 來解決問題，而是基於拉格朗日對偶理論(Lagrangian Duality Theory) 推導出對偶問題(Dual Problem)，並用次梯度下降方法(Sub-gradient Method) 求解。本論文提出了一種高效的集群建構方案，可以同時選擇邊緣伺服器位置和卸載任務的方式，此外還進行了不同的模擬實驗以顯示所提出的演算法是可以實踐並且有效率的。而這些實驗結果皆表明，本論文所提出的演算法能針對達成邊緣伺服器之間負載平衡的目的，表現出優秀的性能和可靠的執行時間。

The number of Internet of Things (IoT) devices has been growing steadily, but contemporary IoT devices tend to have limited power and computational capacity. To mitigate these deficiencies, collaboration systems have been built using mechanisms such as edge computing and clustering techniques. IoT devices can offload complex tasks onto edge servers to improve computational efficiency and reduce response time. This study focuses on the cluster construction problem for task offloading in IoT networks. Clusters are constructed in a network to balance the load among the edge servers that process the offloaded tasks. The cluster construction problem was formulated as an integer programming problem to deploy edge servers and allocate offloaded tasks subject to the constraints of the tasks’ transferring distance and request rates. Instead of solving the problem using heuristics, in this study, a dual problem is derived based on Lagrangian duality theory and solved by the sub-gradient method. An efficient cluster construction scheme that can simultaneously select edge server locations and offload task assignments is proposed. Extensive simulations are conducted to demonstrate the effectiveness and efficiency of the proposed algorithm. The proposed algorithm demonstrates excellent performance in terms of load balancing among the edge servers and the execution time.

[1] J. Chase, “The evolution of the internet of things,” Texas Instruments, vol. 1,
no. 1388, pp. 1–7, 2013.
[2] A. Al-Fuqaha, M. Guizani, M. Mohammadi, M. Aledhari, and M. Ayyash, “Internet
of things: A survey on enabling technologies, protocols, and applications,” IEEE
Communications Surveys Tutorials, vol. 17, no. 4, pp. 2347–2376, 2015.
[3] G. A. Akpakwu, B. J. Silva, G. P. Hancke, and A. M. Abu-Mahfouz, “A survey on 5G
networks for the internet of things: Communication technologies and challenges,” IEEE Access, vol. 6, pp. 3619–3647, 2018.
[4] K. A. Nuaimi, N. Mohamed, M. A. Nuaimi, and J. Al-Jaroodi, “A survey of load balancing in cloud computing: Challenges and algorithms,” in 2012 Second Symposium
on Network Cloud Computing and Applications, pp. 137–142, 2012.
[5] R. Lu, H. Zhu, X. Liu, J. K. Liu, and J. Shao, “Toward efficient and privacypreserving computing in big data era,” IEEE Network, vol. 28, no. 4, pp. 46–50,
2014.
[6] 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.
[7] M. Satyanarayanan, P. Bahl, R. Caceres, and N. Davies, “The case for VM-based
cloudlets in mobile computing,” IEEE Pervasive Computing, vol. 8, no. 4, pp. 14–
23, 2009.
[8] F. Bonomi, R. Milito, J. Zhu, and S. Addepalli, “Fog computing and its role in the
internet of things,” MCC ’12, (Association for Computing Machinery, 2012.
[9] B. P. Rimal, E. Choi, and I. Lumb, “A taxonomy and survey of cloud computing systems,” in 2009 Fifth International Joint Conference on INC, IMS and IDC, pp. 44–
51, 2009.
[10] A. Sharma, A. Roy, S. Ghosal, R. Chaki, and U. Bhattacharya, “Load balancing in
cellular network: A review,” in 2012 Third International Conference on Computing,
Communication and Networking Technologies (ICCCNT’12), pp. 1–5, 2012.
[11] R. Mogi, T. Nakayama, and T. Asaka, “Load balancing method for IoT sensor system
using multi-access edge computing,” in 2018 Sixth International Symposium on Computing and Networking Workshops (CANDARW), pp. 75–78, 2018.
[12] L. Farhan, S. T. Shukur, A. E. Alissa, M. Alrweg, U. Raza, and R. Kharel, “A survey on the challenges and opportunities of the internet of things (IoT),” in 2017 Eleventh International Conference on Sensing Technology (ICST), pp. 1–5, 2017.
[13] Q. Fan and N. Ansari, “Towards traffic load balancing in drone-assisted communications for IoT,” IEEE Internet of Things Journal, vol. 6, no. 2, pp. 3633–3640, 2019.
[14] Y. Li and S. Wang, “An energy-aware edge server placement algorithm in mobile
edge computing,” in 2018 IEEE International Conference on Edge Computing (EDGE), pp. 66–73, 2018.
[15] A. Shahraki, A. Taherkordi, ￿. Haugen, and F. Eliassen, “A survey and future directions on clustering: From WSNs to IoT and modern networking paradigms,” IEEE
Transactions on Network and Service Management, vol. 18, no. 2, pp. 2242–2274, 2021.
[16] L. Xu, R. Collier, and G. M. P. O’Hare, “A survey of clustering techniques in wsns and consideration of the challenges of applying such to 5G IoT scenarios,” IEEE
Internet of Things Journal, vol. 4, no. 5, pp. 1229–1249, 2017.
[17] N. Israr and I. Awan, “Multihop clustering algorithm for load balancing in wireless sensor networks,” International journal of simulation: systems, science and technology, vol. 8, pp. 13–24, 2007.
[18] A. Amis and R. Prakash, “Load-balancing clusters in wireless ad hoc networks,”in Proceedings 3rd IEEE Symposium on Application-Specific Systems and Software
Engineering Technology, pp. 25–32, 2000.
[19] T. M. Behera, S. K. Mohapatra, U. C. Samal, M. S. Khan, M. Daneshmand, and A. H.
Gandomi, “Residual energy-based cluster-head selection in WSNs for IoT application,”
IEEE Internet of Things Journal, vol. 6, no. 3, pp. 5132–5139, 2019.
[20] L. Qiu, V. Padmanabhan, and G. Voelker, “On the placement of web server replicas,” in Proceedings IEEE INFOCOM 2001. Conference on Computer Communications.
Twentieth Annual Joint Conference of the IEEE Computer and Communications Society
(Cat. No.01CH37213), vol. 3, pp. 1587–1596 vol.3, 2001.
[21] Y. Jiang and J. Jiang, “Contextual resource negotiation-based task allocation and
load balancing in complex software systems,” IEEE Transactions on Parallel and
Distributed Systems, vol. 20, no. 5, pp. 641–653, 2009.
[22] Y. Chen, Y. Lin, Z. Zheng, P. Yu, J. Shen, and M. Guo, “Preference-aware edge server placement in the internet of things,” IEEE Internet of Things Journal, vol. 9, no. 2, pp. 1289–1299, 2022.
[23] M. Jia, W. Liang, Z. Xu, M. Huang, and Y. Ma, “Qos-aware cloudlet load balancing
in wireless metropolitan area networks,” IEEE Transactions on Cloud Computing, vol. 8, no. 2, pp. 623–634, 2020.
[24] Y. Jiang, “A survey of task allocation and load balancing in distributed systems,” IEEE Transactions on Parallel and Distributed Systems, vol. 27, no. 2, pp. 585–599, 2016.
[25] P. Kumarawadu, D. J. Dechene, M. Luccini, and A. Sauer, “Algorithms for node
clustering in wireless sensor networks: A survey,” in 2008 4th International Conference on Information and Automation for Sustainability, pp. 295–300, 2008.
[26] J. Lu, Z. Zhang, T. Hu, P. Yi, and J. Lan, “A survey of controller placement problem in software-defined networking,” IEEE Access, vol. 7, pp. 24290–24307, 2019.
[27] W. Dargie and J. Wen, “A simple clustering strategy for wireless sensor networks,” IEEE Sensors Letters, vol. 4, no. 6, pp. 1–4, 2020.
[28] G. Laporte, S. Nickel, and F. Saldanha-da Gama, “Introduction to location science,” in Location science, pp. 1–21, 2019.
[29] M. L. Brandeau and S. S. Chiu, “An overview of representative problems in location research,” Management science, vol. 35, no. 6, pp. 645–674, 1989.
[30] E. Cela, The quadratic assignment problem: theory and algorithms, vol. 1. 2013.
[31] H. Yin, X. Zhang, H. H. Liu, Y. Luo, C. Tian, S. Zhao, and F. Li, “Edge provisioning with flexible server placement,” IEEE Transactions on Parallel and Distributed Systems, vol. 28, no. 4, pp. 1031–1045, 2017.
[32] F. Zeng, Y. Ren, X. Deng, and W. Li, “Cost-effective edge server placement in wireless metropolitan area networks,” Sensors, vol. 19, no. 1, 2019.
[33] Z. Xu, W. Liang, W. Xu, M. Jia, and S. Guo, “Capacitated cloudlet placements in
wireless metropolitan area networks,” in 2015 IEEE 40th Conference on Local Computer
Networks (LCN), pp. 570–578, 2015.
[34] Q. Ye, B. Rong, Y. Chen, M. Al-Shalash, C. Caramanis, and J. G. Andrews, “User
association for load balancing in heterogeneous cellular networks,” IEEE Transactions
on Wireless Communications, vol. 12, no. 6, pp. 2706–2716, 2013.
[35] T.-C. Chang, C.-H. Lin, K. C.-J. Lin, and W.-T. Chen, “Load-balanced sensor grouping for IEEE 802.11ah networks,” in 2015 IEEE Global Communications Conference
(GLOBECOM), pp. 1–6, 2015.
[36] M. Bouet and V. Conan, “Mobile edge computing resources optimization: A geoclustering approach,” IEEE Transactions on Network and Service Management,
vol. 15, no. 2, pp. 787–796, 2018.
[37] P. R. McMullen and R. Strong, “Determination of lockbox collection points via simulated annealing,” Journal of the Operational Research Society, vol. 50, no. 1, pp. 44–51, 1999.
[38] G. Wang, Y. Zhao, J. Huang, and Y. Wu, “An effective approach to controller placement in software defined wide area networks,” IEEE Transactions on Network and
Service Management, vol. 15, no. 1, pp. 344–355, 2018.
[39] 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 Transactions on Networking, vol. 23, no. 3, pp. 836–850, 2015.
[40] P.-C. Huang, T.-L. Chin, and T.-Y. Chuang, “Server placement and task allocation
for load balancing in edge-computing networks,” IEEE Access, vol. 9, pp. 138200–
138208, 2021.
[41] P. Belotti, C. Kirches, S. Leyffer, J. Linderoth, J. Luedtke, and A. Mahajan, “Mixedinteger nonlinear optimization,” Acta Numerica, vol. 22, pp. 1–131, 2013.
[42] H.-S. Park and C.-H. Jun, “A simple and fast algorithm for k-medoids clustering,”
Expert Systems with Applications, vol. 36, no. 2, Part 2, pp. 3336–3341, 2009.
[43] A. Nedic and A. Ozdaglar, “Distributed subgradient methods for multi-agent optimization,” IEEE Transactions on Automatic Control, vol. 54, no. 1, pp. 48–61, 2009.
[44] E. Schubert and P. J. Rousseeuw, “Faster k-medoids clustering: improving the PAM,
CLARA, and CLARANS algorithms,” in International conference on similarity search and applications, pp. 171–187, 2019.
[45] B. Bicsi, “Network design basics for cabling professionals,” City: McGraw-Hill Professional, pp. 0885–8950, 2002.