Open Access
ARTICLE
Weighted De-Synchronization Based Resource Allocation in Wireless Networks
1 School of Electronics and Electrical Engineering (EEE) at Chung-Ang University, Seoul, 156-756, Korea
2 Department of Intelligent Energy and Industry, Chung-Ang University, Seoul, 156-756, Korea
* Corresponding Author: Jung-Ryun Lee. Email:
Computers, Materials & Continua 2023, 75(1), 1815-1826. https://doi.org/10.32604/cmc.2023.032376
Received 16 May 2022; Accepted 15 September 2022; Issue published 06 February 2023
Abstract
Considering the exponential growth of wireless devices with data-starving applications fused with artificial intelligence, the significance of wireless network scalability using distributed behavior and fairness among users is a crucial feature in guaranteeing reliable service to numerous users in the network environment. The Kuramoto model is described as nonlinear self-sustained phase oscillators spinning at varying intrinsic frequencies connected through the sine of their phase differences and displays a phase transition at a specific coupling strength, in which a mutual behavior is accomplished. In this work, we apply the Kuramoto model to achieve a weighted fair resource allocation in a wireless network, where each user has different quality of service (QoS) requirements. Because the original Kuramoto model is the synchronization model, we propose a new weighting parameter for representing requirement of each node resource and modify the Kuramoto model to achieve weighted fair resource allocation for users with different QoS requirements. The proposed modified Kuramoto model allocates all users the resource based on their weight among contending nodes in a distributed manner. We analyze the convergence condition for the proposed model, and the results reveal that the proposed algorithm achieves a weighted fair resource allocation and with potentially high convergence speed compared to previous algorithm.Keywords
Over the last decade, mobile wireless communication technology has undergone spectacular development globally. The upcoming wireless communication systems are expected to produce artificial intelligence fusing applications which will provide high-quality services ranging from wireless multimedia to autonomous applications [1]. In particular, the ongoing demand for wireless devices and tremendous growth in the installation of data-consuming internet of things (IoT) services will additionally reduce the limited wireless resources [2]. Thus, methods for efficiently managing wireless resources are required to address the ever-fast changing and growing number of devices in the network. The essential considerations in designing a resource allocation method include fairness in QoS, scalability, and decentralization [3].
Fairness is a significant factor for resource allocation in wireless networks because consumers use radio wireless resources in diverse applications such as intelligent transportation, smart environment monitoring, fuel station, health care unit, water management, or smart rural village [4,5], and therefore the consumers have different demands for wireless resources [6]. Algorithms for fair resource allocation can be categorized into two broad types: centralized and distributed. Centralized algorithms require at least a central node as a coordinator to manage the resources, whereas distributed algorithms can work without relying on any particular central node as long as all nodes maintain a connection in the same network [7]. In resource allocation, weight generally refers to priorities based on criteria such as the willingness to pay for resources, importance of the task or service. In many circumstances, the appropriate notion of fairness is something other than the uniform sharing of resources. In wireless networks, the importance of weighted resource allocation is emphasized when nodes in a network require a different QoS. Weighted resource allocation provides resources proportional to the node requirements to alleviate QoS issues because assigning an equal amount of resources in a weighted network can degrade QoS or cause unfair QoS. The consequence of unfair QoS levels is unbalanced service provision and potential service suspension due to resource starvation. Therefore, by allocating resources according to the users’ needs, a fair QoS can be achieved [8].
With a large network environment, the number of nodes can vary rapidly according to the network dynamics, such as channel conditions, node mobility, and services, requiring a careful architecture and management of the network and resources [9,10]. In such a scenario, it is more efficient to run the resource allocation algorithm in a distributed manner rather than in a centralized way. Distributed resource allocation allows each node to use the needed resource while reserving some resources for the rest of the nodes in the network. Plus, distributed resource allocation reduces the network overhead and complexity. Many researchers have conducted studies on weighted and non-weighted resource allocation in wireless networks. To accomplish weighted fairness in a distributed network environment, the authors in [11] proposed a weighted de-synchronization-based link scheduling mechanism (WDESYNC-TDMA), in which the concept of traffic weight is additionally applied to the conventional DESYNC [12]. Through simulation, WDESYNC-TDMA can achieve self-scheduling task according to the traffic load. In [13], the authors applied the Kuramoto synchronization model to address load balancing in base stations (BS). The proposed method involves transferring the load from BS and offloading it to access points (AP). The simulation results show a quick reduction in difference load level among BS and the excessive load is offloaded to AP. The authors in [14] applied an altered Kuramoto model to desynchronize the resource in wireless network. The study focuses on using the desynchronization of the Kuramto model and map it to time division multiple access (TDMA) timeslot. The results suggest short convergence time and fairly allocated resources among users. In [15], to avoid congestion and provide weighted fairness, the authors developed an adaptive rate-based congestion control. The method involves flexibly determining the utilisation factors based on gradient method such that the lower rate is determined by the source with smaller value of round trip time. According to [16], a novel decentralized rate control-based congestion avoidance protocol was proposed to achieve weighted fairness along with energy efficiency. The protocol adaptively calibrates the total rate of the data entering nodes while achieving global weighted fairness. In [17], the authors studied weighted fairness in a caching system using Markov chain. The proposed method is called weighted fair caching which provides owners fairness or enables them to manage the resource allocation among the content.
With recent rapid increases in the number of devices connected to wireless networks, the importance of scalable radio resource management operating in a distributed manner and the role of fairness among nodes are critical aspects in ensuring reliable services to numerous nodes in such network environments. In this paper, we consider the Kuramoto model for achieving fair and distributed radio resource allocation in a wireless network. Because the conventional Kuramoto model is designed for synchronization only and is thus not suitable for fair resource allocation, we propose a modified Kuramoto-Desync model, whose purpose is to achieve fair resource allocation among nodes in a distributed manner. The proposed Kuramoto-Desync model evenly spaces the phases of all the nodes in the network. By mapping the evenly spaced phase interval of each node to the time-division multiple access or TDMA-based data time slot, we achieve fair resource allocation among contending nodes in a distributed way. The necessary condition for the convergence of the Kuramoto-Desync model is analyzed. The simulation results show that the proposed model successfully performs fair resource allocation even in dynamic network topology and that the convergence speed of the proposed model is quite stable compared to that of the comparison model.
Fairness can be achieved when the amount of resources allocated to users is the same. Likewise, leveraging a synchronization model such as Kuramoto model in resource allocation can lead to improvement in fairness. Achieving fairness can result in improved throughput and reducing packet collision [18].
The Kuramoto model can be described as nonlinear self-sustained phase oscillators spinning at varying intrinsic frequencies connected through the sine of their phase differences. The model displays a phase transition at a specific coupling strength, in which a mutual behavior is accomplished. Hence, the Kuramoto model is only applicable for fair resource allocation, where all allocated resources are equal.
In this paper, we study the wireless resource allocation algorithm based on the Kuramoto model. The original Kuramoto model is the synchronization model; thus, we propose a modified version of the model to achieve weighted de-synchronization according to the weight of each node, so that it is applicable to resource allocation for network users with different QoS. The simulation results present scalability in dense network environment and better convergence speed compared to the previous algorithm.
2 Weighted Kuramoto De-Synchronization Model
The Kuramoto model represents oscillators of firm natural frequencies and non-adjustable coupling constants connected via all-to-all coupling. The first work was proposed by Winfree [19], and was later extended and expressed in simpler mathematical terms by Kuramoto [20]. The Kuramoto model consists of a population of N phase oscillators which are governed as follows:
where
Many studies ranging from physical and chemical to biological and social systems, have used of Kuramoto model to synchronize a large population of interrelated elements [21].
2.2 The Proposed Weighted Kuramoto Model
We know that the Kuramoto model is a synchronization procedure that models chaotic oscillator-like systems to behave in an orderly fashion where the oscillator operates at the same rate. Accordingly, to solve the resource allocation problem in an unfair wireless network system, we propose a modified Kuramoto model, the weighted Kuramoto desynchronization model. The weighted Kuramoto desynchronization model can achieve weighted fairness by allocating the resource (phase angle spacing) according to the needs of different nodes. The proposed weighted Kuramoto de-synchronization model can be expressed as follows:
where
Before computing
In this section, we prove the convergence condition of the proposed weighted Kuramoto model. A useful metric in the study of the phase coupling oscillators model is the phase centroid that can be defined as follows:
The magnitude of the phase centroid,
In the next part we will prove the condition of learning rate
Theorem 1. Assume there are N oscillators in the network that update their phases according to (3). When
Proof. Let the Lyapunov candidate at time step t be given by
where
where
To study
Case 1
Case 2,
In Case 1
Let
By approximation,
Therefore,
Let
where (15) can be rewritten as
Therefore,
4 Application of Weighted Kuramoto De-Synchronization in Wireless Networks
This section explains how the proposed weighted Kuramoto model is applied to TDMA-based networks to achieve fair resource allocation. Suppose N nodes are in a network, which fires periodically with a period of TDMA frame size. Fundamentally, the action of firing denotes broadcasting a firing message that all the other nodes can hear. A node in the network identifies phase information of its neighboring nodes by overhearing their firing action. A node updates its phase according to the weighted Kuramoto model. When a node phase becomes
The proposed weighted Kuramoto de-synchronization model allows nodes to automatically manage the slot sizes for fully utilizing bandwidth without incurring any collisions. The mapping relation between the phase of a node and resource allocation in a TDMA frame is described as follows. First, we split the phase circle into a line segment. At time
In this section, we analyze the performance of the proposed algorithm under different environment. In Fig. 1, five nodes are randomly initialized in the network in the range of
In Fig. 9, we compare the convergence speed of the proposed to WDESYNC-TDMA [11]. In this simulation, we compare the number of rounds that are taken to a given number of nodes in the network for the algorithm to converge. It can be seen that the proposed model achieves a noticeable faster convergence speed (lower number of iteration) compared to that of the WDESYNC-TDMA. As the number of nodes grows the convergence speed of the WDESYNC-TDMA also increases whereas the proposed model maintains a stable rate, highlighting the potential scalability of the proposed algorithm within dense network environment.
This paper provides insight into weighted wireless networks, where each user has different resource requirements. We propose a weighted Kuramoto de-synchronization model to allocate resources to each user according to their network traffic weight to achieve fair resource allocation and to utilize resources efficiently. Furthermore, we analytically derive the required conditions for convergence. In the simulation results, we assess the performance of the weighted Kuramoto model in various scenarios. In addition, the proposed model exhibits fast convergence, which demonstrates flexibility and high adaptability in the dense network environment.
Due to the nature of multi-hop network, in the weighted Kuramoto de-synchronization model, one node cannot relay its information to the other nodes across the network. Hence, in the future, we plan to study the weighted Kuramoto de-synchronization model in a multi-hop network. In addition, overhearing neighboring nodes and phase updating can cause energy consumption issue. For this reason, we plan to study the application of sleep mode in the Kuramoto model to increase the energy efficiency of the network.
Funding Statement: This research was supported by the MSIT (Ministry of Science and ICT), Korea, under the ITRC support program (IITP-2021-2018-0-01799) supervised by the IITP (Institute for Information & communications Technology Planning & Evaluation), by the Korea Institute of Energy Technology Evaluation and Planning (KETEP) and the Ministry of Trade, Industry & Energy (MOTIE) of the Republic of Korea (No. 20214000000280), and by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MEST) (No.NRF-2020R1A2C1010929).
Conflicts of Interest: The authors declare that they have no conflicts of interest to report regarding the present research work.
References
1. C. Wang, M. D. Renzo, S. Stanczak, S. Wang and E. G. Larsson, “Artificial intelligence enabled wireless networking for 5G and beyond: Recent advances and future challenges,” IEEE Wireless Communications, vol. 27, no. 1, pp. 16–23, 2020. [Google Scholar]
2. W. Saad, M. Bennis and M. Chen, “A vision of 6G wireless systems: Applications, trends, technologies, and open research problems,” IEEE Network, vol. 34, no. 3, pp. 134–142, 2020. [Google Scholar]
3. L. D. Xu, W. He and S. Li, “Internet of things in industries: A survey,” IEEE Transactions on Industrial Informatics, vol. 10, no. 4, pp. 2233–2243, 2014. [Google Scholar]
4. H. Mohapatra and A. K. Rath, “Survey on fault tolerance-based clustering evolution in WSN,” IET Networks, vol. 9, no. 4, pp. 145–155, 2020. [Google Scholar]
5. H. Mohapatra and A. K. Rath, “Detection and avoidance of water loss through municipality taps in India by using smart taps and ICT,” IET Wireless Sensor Systems, vol. 9, no. 6, pp. 447–457, 2019. [Google Scholar]
6. NTT. DoCoMo Inc., “White Paper: 5G radio access: Requirements, concept and technologies,” 2014. [Online]. Available: https://www.docomo.ne.jp/english/binary/pdf/corporate/technology/whitepaper_5g/DOCOMO_5G_White_Paper.pdf. [Google Scholar]
7. D. Baker and A. Ephremides, “The architectural organization of a mobile radio network via a distributed algorithm,” IEEE Transactions on Communications, vol. 29, no. 11, pp. 1694–1701, 1981. [Google Scholar]
8. F. Harada, T. Ushio and Y. Nakamoto, “Adaptive resource allocation control for fair qos management,” IEEE Transactions on Computers, vol. 56, no. 3, pp. 344–357, 2007. [Google Scholar]
9. H. Mohapatra and A. K. Rath, “Fault-tolerant mechanism for wireless sensor network,” IET Wireless Sensor Systems, vol. 10, no. 1, pp. 23–30, 2020. [Google Scholar]
10. H. Mohapatra and A. K. Rath, “Fault tolerance in WSN through pe-leach protocol,” IET Wireless Sensor Systems, vol. 9, no. 6, pp. 358–365, 2019. [Google Scholar]
11. Y. Taniguchi, “De-synchronization-based weighted scheduling adaptive to traffic load for wireless networks,” in Int. Conf. on Computer, Communications, and Control Technology (I4CT), Langkawi, pp. 130–134, 2014. [Google Scholar]
12. J. Degesys, I. Rose, A. Patel and R. Nagpal, “DESYNC: Self-organizing de-synchronization and tdma on wireless sensor networks,” in Proc. of ACM/IEEE Int. Conf. on Information Processing in Sensor Networks, Toronto, Ontario, Canada, pp. 11–20, 2007. [Google Scholar]
13. Q. Wang, S. Wang, M. Zhu, M. Ma and H. Chen, “A Bio-inspired and user-experience preferred load-balance algorithm for heterogeneous networks,” in IEEE/CIC Int. Conf. on Communications in China (ICCC), Beijing, China, pp. 335–340, 2018. [Google Scholar]
14. U. -S. Yu, H. -H. Choi and J. -R. Lee, “Kuramoto-desync: Distributed and fair resource allocation in a wireless network,” IEEE Access, vol. 7, pp. 104769–104776, 2019. [Google Scholar]
15. L. Khoshnevisan and F. R. Salmasi, “Adaptive rate-based congestion control with weighted fairness through multi-loop gradient projection internal model controller,” IET Control Theory Applications, vol. 9, no. 18, pp. 2641–2647, 2015. [Google Scholar]
16. G. Li and J. Li, “Global weighted fairness guaranteed congestion avoidance protocol for wireless sensor networks,” in 2011 Proc. IEEE Int. Conf. on Computer Communications (INFOCOM), Shanghai, China, pp. 601–605, 2011. [Google Scholar]
17. L. Shi, X. Wang, R. T. B. Ma and Y. C. Tay, “Weighted fair caching: Occupancy-centric allocation for space-shared resources,” Performance Evaluation, vol. 127–128, pp. 194–211, 2018. [Google Scholar]
18. H. Obata, R. Hamamoto, C. Takano and K. Ishida, “SP-MAC: A media access control method based on the synchronization phenomena of coupled oscillators over WLAN,” IEICE Transactions on Information and Systems, vol. E98.D, no. 12, pp. 2060–2070, 2015. [Google Scholar]
19. A. T. Winfree, “Biological rhythms and the behavior of populations of coupled oscillators,” Journal of Theoretical Biology, vol. 16, no. 1, pp. 15–42, 1967. [Google Scholar]
20. Y. Kuramoto, “Self-entrainment of a population of coupled non-linear oscillators,” in Proc. Int. Symp. Mathematical Problems in Theorical Physics, in Lecture Notes in Physics. Berlin, Germany, Springer, pp. 420–422, 1975. [Google Scholar]
21. J. A. Acebrón, L. L. Bonilla, C. J. Pérez Vicente, F. Ritort and R. Spigler, “The kuramoto model: A simple paradigm for synchronization phenomena,” Reviews of Modern Physics, vol. 77, no. 1, pp. 137–185, 2005. [Google Scholar]
Cite This Article
This work is licensed under a Creative Commons Attribution 4.0 International License , which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.