KR102803930B1 - Resource allocation method and apparatus using sequential parameter estimation - Google Patents
Resource allocation method and apparatus using sequential parameter estimation Download PDFInfo
- Publication number
- KR102803930B1 KR102803930B1 KR1020210192985A KR20210192985A KR102803930B1 KR 102803930 B1 KR102803930 B1 KR 102803930B1 KR 1020210192985 A KR1020210192985 A KR 1020210192985A KR 20210192985 A KR20210192985 A KR 20210192985A KR 102803930 B1 KR102803930 B1 KR 102803930B1
- Authority
- KR
- South Korea
- Prior art keywords
- time slot
- current time
- users
- resources
- resource allocation
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
Images
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04W—WIRELESS COMMUNICATION NETWORKS
- H04W72/00—Local resource management
- H04W72/50—Allocation or scheduling criteria for wireless resources
- H04W72/53—Allocation or scheduling criteria for wireless resources based on regulatory allocation policies
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06N—COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
- G06N20/00—Machine learning
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04W—WIRELESS COMMUNICATION NETWORKS
- H04W72/00—Local resource management
- H04W72/04—Wireless resource allocation
- H04W72/044—Wireless resource allocation based on the type of the allocated resource
- H04W72/0446—Resources in time domain, e.g. slots or frames
Landscapes
- Engineering & Computer Science (AREA)
- Software Systems (AREA)
- Signal Processing (AREA)
- Computer Networks & Wireless Communication (AREA)
- Theoretical Computer Science (AREA)
- Evolutionary Computation (AREA)
- Medical Informatics (AREA)
- Physics & Mathematics (AREA)
- Computing Systems (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Mathematical Physics (AREA)
- Data Mining & Analysis (AREA)
- Computer Vision & Pattern Recognition (AREA)
- Artificial Intelligence (AREA)
- Data Exchanges In Wide-Area Networks (AREA)
Abstract
연속적 파라미터 추정을 이용한 자원 할당 방법 및 장치가 개시된다. 자원 할당 방법은 이전 타임 슬롯에서의 사용자 수와 현재 타임 슬롯에서의 사용자 수가 동일한지 여부를 식별하는 단계; 상기 이전 타임 슬롯에서의 사용자 수와 상기 현재 타임 슬롯에서의 사용자 수가 동일한 경우, 상기 이전 타임 슬롯에서의 협상 해법을 이용하여 상기 현재 타임 슬롯에서의 협상 해법을 찾기 위한 축소된 탐색 공간을 설정하는 단계; 및 상기 축소된 탐색 공간 내에서 협상 해법을 연산함으로써 상기 현재 타임 슬롯 내의 사용자들에게 자원을 할당하는 단계를 포함할 수 있다.A method and device for resource allocation using continuous parameter estimation are disclosed. The resource allocation method may include a step of identifying whether the number of users in a previous time slot is the same as the number of users in a current time slot; a step of setting a reduced search space for finding a negotiation solution in the current time slot using a negotiation solution in the previous time slot if the number of users in the previous time slot is the same; and a step of allocating resources to users in the current time slot by computing a negotiation solution in the reduced search space.
Description
본 발명은 연속적 파라미터 추정을 이용한 자원 할당 방법 및 장치에 관한 것으로, 보다 구체적으로는 동적 시스템에서 협상 해법을 구하는 과정에서 초래되는 높은 계산 복잡도 문제를 해결하기 위하여 탐색 공간을 감소시키는 방법 및 장치에 관한 것이다.The present invention relates to a method and device for resource allocation using continuous parameter estimation, and more specifically, to a method and device for reducing a search space in order to solve the problem of high computational complexity resulting from the process of finding a negotiation solution in a dynamic system.
최근에는 스마트폰, 태블릿 PC, 웨어러블 기기 등 모바일 기기가 널리 보급됨에 따라 다수의 기기가 하나의 통신 및 네트워크 환경을 공유하는 상황이 자주 발생하고 있다. 이에 따라 자원이 한정된 네트워크 환경에서 사용자 환경 및 미디어 특성에 맞게 네트워크 자원을 효율적으로 활용하는 것이 중요한 이슈가 되었다.Recently, as mobile devices such as smartphones, tablet PCs, and wearable devices have become widespread, situations where multiple devices share a single communication and network environment are occurring frequently. Accordingly, in a network environment with limited resources, it has become an important issue to efficiently utilize network resources according to user environments and media characteristics.
이때, 멀티 유저 네트워크 환경에서의 주요 성능은 크게 자원 할당 방법으로 평가될 수 있다. 이를 위해, 기존 연구에서 효율적인 자원 할당과 동시에 멀티미디어 사용자들의 서비스 품질(Quality of Service)을 보장할 수 있는 방법으로 i)내쉬 협상해법(Nash bargaining solution, NBS) 및 ii)칼라이-스모로딘스키 협상 해법(Kalai-Smorodinsky bargaining solution, KSBS)와 같은 몇 가지 협상 전략이 고려되어 왔다.At this time, the main performance in a multi-user network environment can be largely evaluated by the resource allocation method. To this end, several negotiation strategies such as i) Nash bargaining solution (NBS) and ii) Kalai-Smorodinsky bargaining solution (KSBS) have been considered in previous studies as a method that can guarantee the quality of service (QoS) of multimedia users while efficiently allocating resources.
여기서, NBS은 공리적 협상 해법을 기반으로 한 게임 이론적 방법으로 주어진 문제를 접근하며 자원 할당 방법으로 널리 알려진 협상 해법이다. 하지만, NBS은 사용자의 수가 늘어날수록 NBS를 수행하는 데 필요한 계산 복잡도가 기하급수적으로 증가한다는 한계를 가지고 있어 네트워크 환경 변화 (사용자의 수 변화)에 맞추어 실시간으로 자원 할당을 해주지 못하는 것이 가장 큰 문제점으로 꼽혀 왔다. 이에 따라 계산 복잡도를 줄이기 위해 불필요한 연산을 제외함으로써, 빠르게 NBS를 도출할 수 있는 다양한 네트워크 자원 할당 방법이 제시되었으나, 제시된 방법들은 사용자의 수가 동적으로 변화하는 환경에서는 적용하기에 여전히 한계를 가지고 있다.Here, NBS is a game-theoretic method based on an axiomatic negotiation solution, and is a negotiation solution widely known as a resource allocation method. However, NBS has a limitation that the computational complexity required to perform NBS increases exponentially as the number of users increases, and the biggest problem is that it cannot allocate resources in real time according to changes in the network environment (changes in the number of users). Accordingly, various network resource allocation methods have been proposed to quickly derive NBS by excluding unnecessary operations to reduce the computational complexity, but the proposed methods still have limitations in applying them in an environment where the number of users changes dynamically.
따라서, 상술한 한계를 해결하기 위해, 네트워크 자원 할당에 대해 협력적인 접근 방법을 이용하여 멀티미디어 서비스 품질 보장과 동시에 전체 네트워크 효용을 높일 수 있는 방법이 필요하다.Therefore, to solve the above-mentioned limitations, a method is needed to increase the overall network utility while ensuring multimedia service quality by using a cooperative approach to network resource allocation.
본 발명은 이전 타임 슬롯에서의 유효 효용 집합과 현재 타임 슬롯에서의 유효 효용 집합 사이의 차원이 변하지 않는 경우, 이전 타임 슬롯에서의 협상 해법을 기반으로 현재 타임 슬롯에서의 협상 해법을 찾기 위한 탐색 공간을 감소시키는 방법 및 장치를 제공할 수 있다.The present invention can provide a method and device for reducing a search space for finding a negotiation solution in a current time slot based on a negotiation solution in a previous time slot when the dimension between the effective utility set in a previous time slot and the effective utility set in a current time slot does not change.
또한, 본 발명은 이전 타임 슬롯에서의 유효 효용 집합과 현재 타임 슬롯에서의 유효 효용 집합 사이의 차원이 변하는 경우, 기계학습을 통해 미리 계산된 현재 타임 슬롯에서의 협상 해법을 이용함으로써 자원 할당을 위한 계산 복잡도를 감소시키는 방법 및 장치를 제공할 수 있다.In addition, the present invention can provide a method and device for reducing computational complexity for resource allocation by using a negotiation solution in the current time slot that is pre-calculated through machine learning when the dimension between the effective utility set in the previous time slot and the effective utility set in the current time slot changes.
본 발명의 일실시예에 따른 자원 할당 방법은 이전 타임 슬롯에서의 사용자 수와 현재 타임 슬롯에서의 사용자 수가 동일한지 여부를 식별하는 단계; 상기 이전 타임 슬롯에서의 사용자 수와 상기 현재 타임 슬롯에서의 사용자 수가 동일한 경우, 상기 이전 타임 슬롯에서의 협상 해법을 이용하여 상기 현재 타임 슬롯에서의 협상 해법을 찾기 위한 축소된 탐색 공간을 설정하는 단계; 및 상기 축소된 탐색 공간 내에서 협상 해법을 연산함으로써 상기 현재 타임 슬롯 내의 사용자들에게 자원을 할당하는 단계를 포함할 수 있다.A resource allocation method according to one embodiment of the present invention may include the steps of: identifying whether the number of users in a previous time slot is the same as the number of users in a current time slot; setting a reduced search space for finding a negotiation solution in the current time slot by using a negotiation solution in the previous time slot if the number of users in the previous time slot is the same; and allocating resources to users in the current time slot by computing a negotiation solution in the reduced search space.
상기 축소된 탐색 공간을 설정하는 단계는 상기 이전 타임 슬롯에서의 각 사용자가 할당 가능한 자원을 모두 사용하였을 때 획득 가능한 효용과 상기 현재 타임 슬롯에서의 각 사용자가 할당 가능한 자원을 모두 사용하였을 때 획득 가능한 효용을 이용하여 변환 행렬을 생성하는 단계; 상기 생성된 변환 행렬과 상기 이전 타임 슬롯에서의 협상 해법을 이용하여 합의 실패점을 식별하는 단계; 및 상기 합의 실패점에서의 자원 총합을 이용하여 상기 현재 타임 슬롯에서 협상 해법을 찾기 위한 상기 축소된 탐색 공간을 결정하는 단계를 포함할 수 있다.The step of setting the reduced search space may include the step of generating a transformation matrix using the utility obtainable when each user in the previous time slot uses all allocatable resources and the utility obtainable when each user in the current time slot uses all allocatable resources; the step of identifying an agreement failure point using the generated transformation matrix and the negotiation solution in the previous time slot; and the step of determining the reduced search space for finding a negotiation solution in the current time slot using the sum of resources at the agreement failure point.
상기 변환 행렬은 상기 이전 타임 슬롯에서의 각 사용자가 할당 가능한 자원을 모두 사용하였을 때 획득 가능한 효용과 상기 현재 타임 슬롯에서의 각 사용자가 할당 가능한 자원을 모두 사용하였을 때 획득 가능한 효용의 비율을 대각선 원소로 하고, 상기 대각선 원소 이외의 나머지가 모두 0 값을 가질 수 있다.The above transformation matrix has as its diagonal elements the ratio of the utility obtainable when each user in the previous time slot uses all allocatable resources and the utility obtainable when each user in the current time slot uses all allocatable resources, and all remaining elements other than the diagonal elements can have a value of 0.
상기 합의 실패점은 상기 생성된 변환 행렬과 상기 이전 타임 슬롯에서의 협상 해법을 곱한 결과로 벡터 값을 가질 수 있다.The above agreement failure point can have a vector value as a result of multiplying the generated transformation matrix and the negotiation solution in the previous time slot.
상기 축소된 탐색 공간은 상기 합의 실패점의 각 인덱스(Index) 마다 상기 현재 타임 슬롯에서의 각 사용자에 대한 효용 함수의 역함수를 모두 합산함으로써 결정되는 상기 합의 실패점에서의 자원 총합과 상기 현재 타임 슬롯에서 할당 가능한 자원 중 작은 값을 하한으로 설정하고, 큰 값을 상한으로 설정함으로써 결정될 수 있다.The reduced search space can be determined by setting the smaller value of the total resources at the consensus failure point and the allocatable resources in the current time slot as the lower limit, and setting the larger value as the upper limit, which is determined by adding up the inverse functions of the utility functions for each user in the current time slot for each index of the consensus failure point.
본 발명의 일실시예에 따른 자원 할당 방법은 기계학습을 통해 연속적인 복수의 타임 슬롯들 각각에 대한 사용자 수를 예측하여 상기 복수의 타임 슬롯들 각각에 대한 협상 해법을 미리 계산하는 단계; 이전 타임 슬롯에서의 사용자 수와 현재 타임 슬롯에서의 사용자 수가 다른 경우, 상기 기계학습을 통해 예측된 현재 타임 슬롯에서의 예상 사용자 수와 실제 사용자 수가 동일한지 여부를 식별하는 단계; 및 상기 현재 타임 슬롯에서의 예상 사용자 수와 실제 사용자 수가 동일한 것으로 식별된 경우, 상기 미리 계산된 협상 해법을 통해 상기 현재 타임 슬롯 내의 실제 사용자에게 자원을 할당하는 단계를 포함할 수 있다.A resource allocation method according to one embodiment of the present invention may include the steps of: predicting the number of users for each of a plurality of consecutive time slots through machine learning and calculating a negotiation solution for each of the plurality of time slots in advance; identifying whether the expected number of users in the current time slot predicted through the machine learning and the actual number of users are the same if the number of users in the previous time slot and the number of users in the current time slot are different; and allocating resources to the actual users in the current time slot through the pre-calculated negotiation solution if the expected number of users in the current time slot and the actual number of users are identified as being the same.
상기 자원을 할당하는 단계는 상기 기계 학습을 통해 예측된 예상 사용자가 상기 현재 타임 슬롯에 대한 임의의 할당 가능한 자원을 모두 사용하였을 때 획득 가능한 효용과 상기 실제 사용자가 상기 현재 타임 슬롯에서 할당 가능한 자원을 모두 사용하였을 때 획득 가능한 효용을 이용하여 변환 행렬을 생성하는 단계; 상기 생성된 변환 행렬과 상기 현재 타임 슬롯에서의 미리 계산된 협상 해법을 이용하여 합의 실패점을 식별하는 단계; 및 상기 합의 실패점에서의 자원 총합으로 이용하여 상기 현재 타임 슬롯에서 협상 해법을 찾기 위한 축소된 탐색 공간을 결정하는 단계를 포함할 수 있다.The step of allocating the above resources may include the step of generating a transformation matrix using a utility obtainable when a predicted expected user uses all of an allocatable resource for the current time slot predicted through the machine learning and a utility obtainable when the actual user uses all of the allocatable resource in the current time slot; the step of identifying an agreement failure point using the generated transformation matrix and a pre-calculated negotiation solution in the current time slot; and the step of determining a reduced search space for finding a negotiation solution in the current time slot using the sum of resources at the agreement failure point.
상기 변환 행렬은 상기 예상 사용자가 상기 현재 타임 슬롯에 대한 임의의 할당 가능한 자원을 모두 사용하였을 때 획득 가능한 효용과 상기 실제 사용자가 상기 현재 타임 슬롯에서 할당 가능한 자원을 모두 사용하였을 때 획득 가능한 효용의 비율을 대각선 원소로 하고, 상기 대각선 원소 이외의 나머지가 모두 0 값을 가질 수 있다.The above transformation matrix may have as its diagonal elements the ratio of the utility obtainable when the expected user uses all of the allocatable resources for the current time slot and the utility obtainable when the actual user uses all of the allocatable resources in the current time slot, and all remaining elements other than the diagonal elements may have a value of 0.
상기 합의 실패점은 상기 생성된 변환 행렬과 상기 현재 타임 슬롯에서의 미리 계산된 협상 해법을 곱한 결과로 벡터 값을 가질 수 있다.The above agreement failure point may have a vector value as a result of multiplying the generated transformation matrix and the pre-calculated negotiation solution in the current time slot.
상기 축소된 탐색 공간은 상기 합의 실패점의 각 인덱스(Index) 마다 상기 현재 타임 슬롯에서의 실제 사용자에 효용 함수의 역함수를 모두 합산함으로써 결정되는 상기 합의 실패점에서의 자원 총합과 상기 현재 타임 슬롯에서 할당 가능한 자원 중 작은 값을 하한으로 설정하고, 큰 값을 상한으로 설정함으로써 결정될 수 있다.The reduced search space can be determined by setting the smaller value of the total resources at the consensus failure point and the allocatable resources in the current time slot as the lower limit, and setting the larger value as the upper limit, which is determined by adding up the inverse functions of the utility functions of the actual users in the current time slot for each index of the consensus failure point.
본 발명의 일실시예에 따른 자원 할당 장치는 프로세서를 포함하고, 상기 프로세서는 이전 타임 슬롯에서의 사용자 수와 현재 타임 슬롯에서의 사용자 수가 동일한지 여부를 식별하고, 상기 이전 타임 슬롯에서의 사용자 수와 상기 현재 타임 슬롯에서의 사용자 수가 동일한 경우, 상기 이전 타임 슬롯에서의 협상 해법을 이용하여 상기 현재 타임 슬롯에서의 협상 해법을 찾기 위한 축소된 탐색 공간을 설정하며, 상기 축소된 탐색 공간 내에서 협상 해법을 연산함으로써 상기 현재 타임 슬롯 내의 사용자들에게 자원을 할당할 수 있다.According to one embodiment of the present invention, a resource allocation device includes a processor, wherein the processor identifies whether the number of users in a previous time slot is the same as the number of users in a current time slot, and if the number of users in the previous time slot is the same as the number of users in the current time slot, sets a reduced search space for finding a negotiation solution in the current time slot using a negotiation solution in the previous time slot, and allocates resources to users in the current time slot by computing the negotiation solution within the reduced search space.
상기 프로세서는 상기 이전 타임 슬롯에서의 각 사용자가 할당 가능한 자원을 모두 사용하였을 때 획득 가능한 효용과 상기 현재 타임 슬롯에서의 각 사용자가 할당 가능한 자원을 모두 사용하였을 때 획득 가능한 효용을 이용하여 변환 행렬을 생성하고, 상기 생성된 변환 행렬과 상기 이전 타임 슬롯에서의 협상 해법을 이용하여 합의 실패점을 식별하며, 상기 합의 실패점에서의 자원 총합을 이용하여 상기 현재 타임 슬롯에서 협상 해법을 찾기 위한 상기 축소된 탐색 공간을 결정할 수 있다.The above processor may generate a transformation matrix by using the utility obtainable when each user in the previous time slot uses all allocatable resources and the utility obtainable when each user in the current time slot uses all allocatable resources, identify an agreement failure point by using the generated transformation matrix and the negotiation solution in the previous time slot, and determine the reduced search space for finding a negotiation solution in the current time slot by using the sum of resources at the agreement failure point.
상기 변환 행렬은 상기 이전 타임 슬롯에서의 각 사용자가 할당 가능한 자원을 모두 사용하였을 때 획득 가능한 효용과 상기 현재 타임 슬롯에서의 각 사용자가 할당 가능한 자원을 모두 사용하였을 때 획득 가능한 효용의 비율을 대각선 원소로 하고, 상기 대각선 원소 이외의 나머지가 모두 0 값을 가질 수 있다.The above transformation matrix has as its diagonal elements the ratio of the utility obtainable when each user in the previous time slot uses all allocatable resources and the utility obtainable when each user in the current time slot uses all allocatable resources, and all remaining elements other than the diagonal elements can have a value of 0.
상기 합의 실패점은 상기 생성된 변환 행렬과 상기 이전 타임 슬롯에서의 협상 해법을 곱한 결과로 벡터 값을 가질 수 있다.The above agreement failure point can have a vector value as a result of multiplying the generated transformation matrix and the negotiation solution in the previous time slot.
상기 축소된 탐색 공간은 상기 합의 실패점의 각 인덱스(Index) 마다 상기 현재 타임 슬롯에서의 각 사용자에 대한 효용 함수의 역함수를 모두 합산함으로써 결정되는 상기 합의 실패점에서의 자원 총합과 상기 현재 타임 슬롯에서 할당 가능한 자원 중 작은 값을 하한으로 설정하고, 큰 값을 상한으로 설정함으로써 결정될 수 있다.The reduced search space can be determined by setting the smaller value of the total resources at the consensus failure point and the allocatable resources in the current time slot as the lower limit, and setting the larger value as the upper limit, which is determined by adding up the inverse functions of the utility functions for each user in the current time slot for each index of the consensus failure point.
본 발명의 일실시예에 따른 자원 할당 장치는 프로세서를 포함하고, 상기 프로세서는 기계학습을 통해 연속적인 복수의 타임 슬롯들 각각에 대한 사용자 수를 예측하여 상기 복수의 타임 슬롯들 각각에 대한 협상 해법을 미리 계산하고, 이전 타임 슬롯에서의 사용자 수와 현재 타임 슬롯에서의 사용자 수가 다른 경우, 상기 기계학습을 통해 예측된 현재 타임 슬롯에서의 예상 사용자 수와 실제 사용자 수가 동일한지 여부를 식별하며, 상기 현재 타임 슬롯에서의 예상 사용자 수와 실제 사용자 수가 동일한 것으로 식별된 경우, 상기 미리 계산된 협상 해법을 통해 상기 현재 타임 슬롯 내의 실제 사용자에게 자원을 할당할 수 있다.According to one embodiment of the present invention, a resource allocation device includes a processor, wherein the processor predicts the number of users for each of a plurality of consecutive time slots through machine learning, and calculates a negotiation solution for each of the plurality of time slots in advance, and if the number of users in a previous time slot is different from the number of users in a current time slot, identifies whether the expected number of users in a current time slot predicted through the machine learning and the actual number of users are the same, and if it is identified that the expected number of users in the current time slot and the actual number of users are the same, resources can be allocated to the actual users in the current time slot through the pre-calculated negotiation solution.
상기 프로세서는 상기 기계 학습을 통해 예측된 예상 사용자가 상기 현재 타임 슬롯에 대한 임의의 할당 가능한 자원을 모두 사용하였을 때 획득 가능한 효용과 상기 실제 사용자가 상기 현재 타임 슬롯에서 할당 가능한 자원을 모두 사용하였을 때 획득 가능한 효용을 이용하여 변환 행렬을 생성하고, 상기 생성된 변환 행렬과 상기 현재 타임 슬롯에서의 미리 계산된 협상 해법을 이용하여 합의 실패점을 식별하며, 상기 합의 실패점에서의 자원 총합으로 이용하여 상기 현재 타임 슬롯에서 협상 해법을 찾기 위한 축소된 탐색 공간을 결정할 수 있다.The above processor generates a transformation matrix by using the utility obtainable when the expected user predicted through the machine learning uses all of the allocatable resources for the current time slot and the utility obtainable when the actual user uses all of the allocatable resources in the current time slot, and identifies an agreement failure point by using the generated transformation matrix and a pre-calculated negotiation solution in the current time slot, and determines a reduced search space for finding a negotiation solution in the current time slot by using the sum of resources at the agreement failure point.
상기 변환 행렬은 상기 예상 사용자가 상기 현재 타임 슬롯에 대한 임의의 할당 가능한 자원을 모두 사용하였을 때 획득 가능한 효용과 상기 실제 사용자가 상기 현재 타임 슬롯에서 할당 가능한 자원을 모두 사용하였을 때 획득 가능한 효용의 비율을 대각선 원소로 하고, 상기 대각선 원소 이외의 나머지가 모두 0 값을 가질 수 있다.The above transformation matrix may have as its diagonal elements the ratio of the utility obtainable when the expected user uses all of the allocatable resources for the current time slot and the utility obtainable when the actual user uses all of the allocatable resources in the current time slot, and all remaining elements other than the diagonal elements may have a value of 0.
상기 합의 실패점은 상기 생성된 변환 행렬과 상기 현재 타임 슬롯에서의 미리 계산된 협상 해법을 곱한 결과로 벡터 값을 가질 수 있다.The above agreement failure point may have a vector value as a result of multiplying the generated transformation matrix and the pre-calculated negotiation solution in the current time slot.
상기 축소된 탐색 공간은 상기 합의 실패점의 각 인덱스(Index) 마다 상기 현재 타임 슬롯에서의 실제 사용자에 효용 함수의 역함수를 모두 합산함으로써 결정되는 상기 합의 실패점에서의 자원 총합과 상기 현재 타임 슬롯에서 할당 가능한 자원 중 작은 값을 하한으로 설정하고, 큰 값을 상한으로 설정함으로써 결정될 수 있다.The reduced search space can be determined by setting the smaller value of the total resources at the consensus failure point and the allocatable resources in the current time slot as the lower limit, and setting the larger value as the upper limit, which is determined by adding up the inverse functions of the utility functions of the actual users in the current time slot for each index of the consensus failure point.
본 발명의 일실시예에 의하면, 이전 타임 슬롯에서의 유효 효용 집합과 현재 타임 슬롯에서의 유효 효용 집합 사이의 차원이 변하지 않는 경우, 이전 타임 슬롯에서의 협상 해법을 기반으로 현재 타임 슬롯에서의 협상 해법을 찾기 위한 탐색 공간을 감소시킬 수 있다.According to one embodiment of the present invention, when the dimension between the effective utility set in the previous time slot and the effective utility set in the current time slot does not change, the search space for finding a negotiation solution in the current time slot can be reduced based on the negotiation solution in the previous time slot.
또한, 본 발명의 일실시예에 의하면, 이전 타임 슬롯에서의 유효 효용 집합과 현재 타임 슬롯에서의 유효 효용 집합 사이의 차원이 변하는 경우, 기계학습을 통해 미리 계산된 현재 타임 슬롯에서의 협상 해법을 이용함으로써 자원 할당을 위한 계산 복잡도를 감소시킬 수 있다.In addition, according to one embodiment of the present invention, when the dimension between the effective utility set in the previous time slot and the effective utility set in the current time slot changes, the computational complexity for resource allocation can be reduced by using a negotiation solution in the current time slot that is pre-calculated through machine learning.
도 1은 본 발명의 일실시예에 따른 자원 할당 장치를 포함하는 전체 구성도를 도시한 도면이다.
도 2는 본 발명의 일실시예에 따른 자원 할당 장치가 수행하는 자원 할당 방법의 개념도를 나타낸 도면이다.
도 3은 본 발명의 일실시예에 따른 협상 해법의 연속적 예측을 통한 자원 할당 방법을 플로우차트로 나타낸 도면이다.
도 4는 본 발명의 일실시예에 따른 데이터 처리 기반의 파라미터 추정을 통한 자원 할당 방법을 플로우차트로 나타낸 도면이다.FIG. 1 is a drawing illustrating an overall configuration including a resource allocation device according to one embodiment of the present invention.
FIG. 2 is a diagram illustrating a conceptual diagram of a resource allocation method performed by a resource allocation device according to one embodiment of the present invention.
FIG. 3 is a flowchart illustrating a resource allocation method through continuous prediction of a negotiation solution according to one embodiment of the present invention.
FIG. 4 is a flowchart illustrating a resource allocation method through parameter estimation based on data processing according to one embodiment of the present invention.
이하, 본 발명의 실시예를 첨부된 도면을 참조하여 상세하게 설명한다. Hereinafter, embodiments of the present invention will be described in detail with reference to the attached drawings.
도 1은 본 발명의 일실시예에 따른 자원 할당 장치를 포함하는 전체 구성도를 도시한 도면이다.FIG. 1 is a drawing illustrating an overall configuration including a resource allocation device according to one embodiment of the present invention.
도 1을 참고하면, 자원 할당 장치(101)는 네트워크(102)에 접속하는 복수의 사용자가 공유하는 한정된 전체 자원(103)을 전략적으로 분배할 수 있다. 다시 말해, 자원 할당 장치(101)는 네트워크(102)에서 제공하는 자원에 대한 접속한 n명 사용자들(104) 각각의 효용성을 고려하여 전체 자원(103) 중 최적 자원을 각각 배분할 수 있다. 여기서, 전체 자원(103)은 네트워크(102)에서 지원 가능한 자원으로써, 고정된 개수로 존재할 수 있다. 반면, 네트워크(102)의 접속 가능한 사용자는 사용자의 이동성에 따라 추가되거나 또는 감소될 수 있다. 다시 말해, 사용자는 기존에 최적 자원이 배분된 n명 사용자로부터 a명 만큼 증가 또는 n-b명 만큼 감소될 수 있다. 즉, 사용자는 동일한 네트워크(102) 환경에서 한정된 자원을 공유하는 복수의 사용자의 수가 유동적으로 매시간 타임 슬롯 마다 변화할 수 있다.Referring to FIG. 1, the resource allocation device (101) can strategically distribute the limited total resources (103) shared by multiple users connected to the network (102). In other words, the resource allocation device (101) can distribute optimal resources among the total resources (103) to each of the n connected users (104) considering the utility of the resources provided by the network (102). Here, the total resources (103) are resources that can be supported by the network (102) and can exist in a fixed number. On the other hand, the number of users that can be connected to the network (102) can be added or decreased according to the mobility of the users. In other words, the number of users can be increased by a or decreased by n-b from the n users to whom the optimal resources are previously distributed. In other words, the number of users that share limited resources in the same network (102) environment can dynamically change for each time slot.
그리고, 자원 할당 장치(101)는 기존에 최적 자원이 배분된 n명 사용자로부터 증가 또는 감소된 사용자(105)를 고려하여 사용자들(104), (105) 각각에 대한 최적 자원을 재설정할 수 있다. 다시 말해, 자원 할당 장치(101)는 n명 사용자들(104) 각각에 배분된 최적 자원으로부터 증가된 n+a명 사용자들 또는 n-b명 감소된 나머지에 해당하는 b명 사용자들 각각에 대한 최적 자원을 재설정할 수 있다.And, the resource allocation device (101) can reset the optimal resources for each of the users (104) and (105) by considering the users (105) increased or decreased from the n users to whom the optimal resources were previously allocated. In other words, the resource allocation device (101) can reset the optimal resources for each of the n+a users increased from the optimal resources allocated to each of the n users (104) or the b users corresponding to the n-b decreased remainder.
이를 위해, 자원 할당 장치(101)는 네트워크(102)에서 유동적으로 변화하는 사용자에 대해 실시간으로 빠르게 자원을 분배하기 위한 전략으로 협력 게임 이론의 내쉬 협상 해법(Nash Bargaining Solution, NBS)을 이용할 수 있다. 여기서, 게임 이론의 한 분야인 협력 게임 이론은 게임에 참여한 사용자들이 효율적이며 공평한 자원 분할에 초점을 맞추기 위한 이론으로써, 공리적 협상 해법을 포함한다. 또한, 협력 게임 이론은 협상 문제를 통하여 참여한 사용자들이 공평하고 최적화된 합의점(agreement point)에 도달했을 때, 이에 대하여 협상 문제의 해법이라고 하며 이러한 합의점을 공리적인 접근 방법으로 제시한 해법을 공리적 협상 해법이라 할 수 있다.To this end, the resource allocation device (101) can use the Nash Bargaining Solution (NBS) of the cooperative game theory as a strategy for quickly distributing resources in real time to users who change dynamically in the network (102). Here, the cooperative game theory, which is a field of game theory, is a theory for users participating in the game to focus on efficient and fair resource division, and includes an utilitarian negotiation solution. In addition, the cooperative game theory is a solution to the negotiation problem when the users participating in the negotiation problem reach a fair and optimal agreement point, and a solution that presents this agreement point using an utilitarian approach can be called an utilitarian negotiation solution.
이 때, 자원 할당 장치(101)는 이러한 협력 게임 이론에 기초하여 네트워크(102)에 접속한 n명 사용자들 각각에 자원을 할당하는 과정을 협상 문제로 파악하고, 이에 대한 해법으로써 내쉬 협상 해법(NBS: Nash Bargaining Solution)을 이용할 수 있다.At this time, the resource allocation device (101) can identify the process of allocating resources to each of n users connected to the network (102) as a negotiation problem based on this cooperative game theory, and can use the Nash Bargaining Solution (NBS) as a solution to this problem.
또한, 자원 할당 장치(101)는 네트워크(102)에 미리 접속된 n명 사용자들(104) 각각에 대하여 내쉬 협상 해법을 통해 전체 자원(103)에 대한 최적 자원을 배분할 수 있다. 그리고, 자원 할당 장치(101)는 최적 자원이 배분된 n명 사용자로부터 증가 또는 감소된 사용자(105)에 대하여 내쉬 협상 해법을 재 적용함으로써, n+a명 사용자들 또는 n-b명 감소된 나머지에 해당하는 b명 사용자들 각각에 대한 최적 자원을 재설정할 수 있다.In addition, the resource allocation device (101) can allocate optimal resources for the entire resources (103) to each of n users (104) pre-connected to the network (102) through a Nash negotiation solution. In addition, the resource allocation device (101) can reset optimal resources for each of n+a users or b users corresponding to n-b reduced remainders by reapplying the Nash negotiation solution to users (105) increased or decreased from n users to whom optimal resources were allocated.
이때, 매시간 슬롯 마다 사용자 수가 변화하는 경우 처음부터 내쉬 협상 해법을 연산함으로써 높은 계산 복잡도가 초래될 수 있는데 본 발명에서 제공하는 자원 할당 장치(101)는 이와 같은 높은 계산 복잡도를 해결하기 위하여 내쉬 협상 해법을 찾기 위한 탐색 공간을 감소시키는 방법을 제공할 수 있다.At this time, if the number of users changes for each time slot, high computational complexity may be caused by calculating the Nash negotiation solution from the beginning. The resource allocation device (101) provided by the present invention can provide a method of reducing the search space for finding the Nash negotiation solution in order to resolve such high computational complexity.
도 2는 본 발명의 일실시예에 따른 자원 할당 장치가 수행하는 자원 할당 방법의 개념도를 나타낸 도면이다.FIG. 2 is a diagram illustrating a conceptual diagram of a resource allocation method performed by a resource allocation device according to one embodiment of the present invention.
본 발명의 자원 할당 장치(101)는 이전 타임 슬롯에서의 유효 효용 집합과 현재 타임 슬롯에서의 유효 효용 집합 사이의 차원 변화 여부에 따라 현재 타임 슬롯에서의 협상 해법을 찾기 위한 탐색 공간을 감소시키기 위한 서로 다른 방법을 제공할 수 있다.The resource allocation device (101) of the present invention can provide different methods for reducing the search space for finding a negotiation solution in the current time slot depending on whether there is a change in dimension between the effective utility set in the previous time slot and the effective utility set in the current time slot.
먼저, 자원 할당 장치(101)는 이전 타임 슬롯에서의 유효 효용 집합과 현재 타임 슬롯에서의 유효 효용 집합 사이의 차원이 변하지 않는 경우, 내쉬 협상 해법의 연속적 예측을 통해 현재 타임 슬롯에서의 내쉬 협상 해법을 찾기 위한 탐색 공간을 감소시킬 수 있다.First, the resource allocation device (101) can reduce the search space for finding a Nash negotiation solution in the current time slot through continuous prediction of the Nash negotiation solution when the dimension between the effective utility set in the previous time slot and the effective utility set in the current time slot does not change.
보다 구체적으로 이전 타임 슬롯 에서의 사용자 수 과 현재 시간 슬롯 에서의 사용자 수 가 동일한 경우, 즉, 유효 효용 집합의 차원이 변하지 않는 경우, 자원 할당 장치(101)는 이전 타임 슬롯에서 할당 가능한 자원 , 현재 타임 슬롯에서 할당 가능한 자원 및 이전 타임 슬롯에서의 협상 해법 을 이용하여 현재 타임 슬롯에서의 합의 실패점 을 결정할 수 있다. More specifically, the previous time slot Number of users in and current time slot Number of users in If the resource allocation device (101) is the same, i.e., the dimension of the effective utility set does not change, the resource allocation device (101) allocates the resources that can be allocated in the previous time slot. , resources available for allocation in the current time slot. and negotiated solutions in previous time slots Using the consensus failure point in the current time slot can decide.
이후 자원 할당 장치(101)는 이와 같이 결정된 합의 실패점에서 현재 타임 슬롯 내의 사용자들에 할당 가능한 자원 총합을 결정하고, 결정된 합의 실패점에서의 자원 총합 과 현재 타임 슬롯에서 할당 가능한 자원을 이용하여 현재 타임 슬롯에서의 협상 해법 를 찾기 위한 탐색 공간을 감소시킬 수 있다.Afterwards, the resource allocation device (101) determines the total amount of resources that can be allocated to users within the current time slot at the agreed failure point determined in this manner, and the total amount of resources at the agreed failure point determined and negotiate a solution in the current time slot using the resources available in the current time slot. can reduce the search space for finding .
그리고, 자원 할당 장치(101)는 이와 같이 감소된 탐색 공간 내에서 현재 타임 슬롯에 대한 최적의 협상 해법을 결정할 수 있다.And, the resource allocation device (101) can determine an optimal negotiation solution for the current time slot within the reduced search space.
이와는 달리 자원 할당 장치(101)는 이전 타임 슬롯에서의 유효 효용 집합과 현재 타임 슬롯에서의 유효 효용 집합 사이의 차원이 변하는 경우, 데이터 처리 기반의 파라미터 추정을 통해 현재 타임 슬롯에서의 내쉬 협상 해법을 찾기 위한 탐색 공간을 감소시킬 수 있다.In contrast, the resource allocation device (101) can reduce the search space for finding a Nash negotiation solution in the current time slot through parameter estimation based on data processing when the dimension between the effective utility set in the previous time slot and the effective utility set in the current time slot changes.
보다 구체적으로 이전 타임 슬롯 에서의 사용자 수 과 현재 시간 슬롯 에서의 사용자 수 가 서로 다른 경우, 즉, 유효 효용 집합의 차원이 변하는 경우, 자원 할당 장치(101)는 기계학습을 통해 연속적인 복수의 타임 슬롯들 각각에 대한 사용자 수를 예측하고, 예측된 사용자 수에 기초하여 복수의 타임 슬롯들 각각에 대한 협상 해법을 미리 계산할 수 있다.More specifically, the previous time slot Number of users in and current time slot Number of users in When the number of users for each of the multiple consecutive time slots is different, i.e., the dimension of the effective utility set changes, the resource allocation device (101) can predict the number of users for each of the multiple consecutive time slots through machine learning and calculate a negotiation solution for each of the multiple time slots in advance based on the predicted number of users.
자원 할당 장치(101)는 이전 타임 슬롯에서의 사용자 수와 현재 타임 슬롯에서의 사용자 수가 서로 다른 경우, 기계학습을 통해 예측된 현재 타임 슬롯에서의 예상 사용자 수와 실제 사용자 수가 서로 동일한지 여부를 식별할 수 있다. 만약 현재 타임 슬롯에서의 예상 사용자 수와 실제 사용자 수가 동일한 것으로 식별된 경우, 자원 할당 장치(101)는 현재 시간 슬롯에서의 예상 사용자 수 , 예상 사용자 수에 대응하여 현재 시간 슬롯에서 할당 가능한 자원 및 예상 사용자 수에 기초하여 미리 계산된 현재 시간 슬롯에서의 협상 해법 을 이용하여 현재 타임 슬롯에서의 합의 실패점 을 결정할 수 있다. The resource allocation device (101) can identify whether the expected number of users in the current time slot and the actual number of users predicted through machine learning are the same if the number of users in the previous time slot and the number of users in the current time slot are different. If the expected number of users in the current time slot and the actual number of users are identified as being the same, the resource allocation device (101) can identify whether the expected number of users in the current time slot , the resources available for allocation in the current time slot in response to the expected number of users. and negotiated solution in the current time slot pre-calculated based on the expected number of users. Using the consensus failure point in the current time slot can decide.
이후 자원 할당 장치(101)는 이와 같이 결정된 합의 실패점에서 현재 타임 슬롯 내의 실제 사용자들에 할당 가능한 자원 총합을 결정하고, 결정된 합의 실패점에서의 자원 총합 과 현재 타임 슬롯에서 할당 가능한 자원을 이용하여 현재 타임 슬롯에서의 협상 해법 를 찾기 위한 탐색 공간을 감소시킬 수 있다.Afterwards, the resource allocation device (101) determines the total amount of resources that can be allocated to actual users within the current time slot at the agreed failure point determined in this manner, and the total amount of resources at the agreed failure point determined and negotiate a solution in the current time slot using the resources available in the current time slot. can reduce the search space for finding .
그리고, 자원 할당 장치(101)는 이와 같이 감소된 탐색 공간 내에서 현재 타임 슬롯에 대한 최적의 내쉬 협상 해법을 결정할 수 있다.And, the resource allocation device (101) can determine the optimal Nash negotiation solution for the current time slot within the reduced search space.
도 3은 본 발명의 일실시예에 따른 협상 해법의 연속적 예측을 통한 자원 할당 방법을 플로우차트로 나타낸 도면이다.FIG. 3 is a flowchart illustrating a resource allocation method through continuous prediction of a negotiation solution according to one embodiment of the present invention.
단계(310)에서, 자원 할당 장치(101)는 이전 타임 슬롯에서의 사용자 수와 현재 타임 슬롯에서의 사용자 수가 동일한지 여부를 식별할 수 있다.In step (310), the resource allocation device (101) can identify whether the number of users in the previous time slot and the number of users in the current time slot are the same.
단계(320)에서, 자원 할당 장치(101)는 이전 타임 슬롯에서의 사용자 수와 현재 타임 슬롯에서의 사용자 수가 동일한 것으로 식별된 경우, 이전 타임 슬롯에서의 각 사용자가 할당 가능한 자원을 모두 사용하였을 때 획득 가능한 효용과 현재 타임 슬롯에서의 각 사용자가 할당 가능한 자원을 모두 사용하였을 때 획득 가능한 효용을 이용하여 변환 행렬을 생성할 수 있다.In step (320), if the number of users in the previous time slot and the number of users in the current time slot are identified as being the same, the resource allocation device (101) can generate a transformation matrix by using the utility obtainable when each user in the previous time slot uses all allocatable resources and the utility obtainable when each user in the current time slot uses all allocatable resources.
보다 구체적으로 자원 할당 장치(101)는 이전 타임 슬롯에서의 각 사용자 가 할당 가능 자원을 모두 사용하였을 때의 효용 와 현재 타임 슬롯에서의 각 사용자 가 할당 가능 자원을 모두 사용하였을 때의 효용 의 비율을 대각선 원소로 하고, 대각선 원소 이외의 나머지가 모두 0 값을 가지는 변환 행렬 를 아래의 식1과 같이 생성할 수 있다.More specifically, the resource allocation device (101) allocates each user in the previous time slot Utility when all allocatable resources are used and each user in the current time slot Utility when all allocatable resources are used A transformation matrix in which the ratio of diagonal elements is 0, and all elements other than the diagonal elements have a value of 0. can be generated as shown in Equation 1 below.
<식 1><Formula 1>
단계(330)에서, 자원 할당 장치(101)는 생성된 변환 행렬과 이전 타임 슬롯에서의 협상 해법을 이용하여 현재 타임 슬롯에서의 합의 실패점을 식별할 수 있다. 이때, 합의 실패점 는 아래의 식 2와 같이 변환 행렬과 이전 타임 슬롯에서의 협상 해법을 곱한 결과로써 벡터 값을 가질 수 있다. In step (330), the resource allocation device (101) can identify an agreement failure point in the current time slot by using the generated transformation matrix and the negotiation solution in the previous time slot. At this time, the agreement failure point can have a vector value as a result of multiplying the transformation matrix and the negotiation solution in the previous time slot, as in Equation 2 below.
<식 2><Formula 2>
단계(340)에서, 자원 할당 장치(101)는 합의 실패점에서의 자원 총합을 이용하여 현재 타임 슬롯에서 협상 해법을 찾기 위한 축소된 탐색 공간을 결정할 수 있다. 보다 구체적으로 합의 실패점은 매 타임 슬롯 마다 하나씩 존재할 수 있으며, 합의 실패점이 가지는 벡터 값은 해당 타임 슬롯에 있는 사용자 수와 동일한 인덱스(Index)를 가질 수 있다. 이때, 각 인덱스는 각 사용자 가 합의 실패 시 가지게 되는 효용으로써 합의 실패점에서의 자원 총합은 각 인덱스에서의 자원을 모두 합산한 값을 의미할 수 있다.In step (340), the resource allocation device (101) can determine a reduced search space for finding a negotiation solution in the current time slot by using the total resources at the agreement failure point. More specifically, there can be one agreement failure point for each time slot, and the vector value of the agreement failure point can have an index equal to the number of users in the corresponding time slot. At this time, each index is As a utility that is acquired when agreement fails, the sum of resources at the point of agreement failure can mean the sum of all resources at each index.
자원 할당 장치(101)는 이와 같은 합의 실패점에서의 각 인덱스(Index) 마다 각 사용자가 합의 실패 시 갖게 되는 효용 함수의 역함수를 구한 뒤 이를 모두 합산함으로써 합의 실패점에서의 자원 총합 을 결정할 수 있다. The resource allocation device (101) calculates the inverse function of the utility function that each user will have when the agreement fails for each index at the agreement failure point and adds them all up to obtain the total resource at the agreement failure point. can decide.
자원 할당 장치(101)는 이와 같이 결정된 합의 실패점에서의 자원 총합과 현재 타임 슬롯에서 할당 가능한 자원 중 작은 값을 하한으로 설정하고, 큰 값을 상한으로 설정함으로써 축소된 탐색 공간을 결정할 수 있다.The resource allocation device (101) can determine a reduced search space by setting a smaller value among the total resources at the agreed failure point determined in this manner and the resources allocatable in the current time slot as the lower limit, and setting a larger value as the upper limit.
마지막으로 단계(350)에서, 자원 할당 장치(101)는 축소된 탐색 공간 내에서 현재 타임 슬롯에 대한 협상 해법을 연산함으로써 낮은 계산 복잡도를 가지면서도 최적의 협상 해법을 결정할 수 있다.Finally, in step (350), the resource allocation device (101) can determine an optimal negotiation solution with low computational complexity by computing a negotiation solution for the current time slot within the reduced search space.
도 4는 본 발명의 일실시예에 따른 데이터 처리 기반의 파라미터 추정을 통한 자원 할당 방법을 플로우차트로 나타낸 도면이다.FIG. 4 is a flowchart illustrating a resource allocation method through parameter estimation based on data processing according to one embodiment of the present invention.
도 4에서 제공하는 데이터 처리 기반의 파라미터 추정을 통한 자원 할당 방법은 유효 효용 집합의 차원이 변하거나 타임 슬롯이 1이라 이전 타임 슬롯이 없는 경우에 사용될 수 있다.The resource allocation method using parameter estimation based on data processing provided in Fig. 4 can be used when the dimension of the effective utility set changes or when the time slot is 1 and there is no previous time slot.
단계(410)에서, 자원 할당 장치(101)는 기계학습을 통해 연속적인 복수의 타임 슬롯들 각각에 대한 사용자 수를 예측하여 복수의 타임 슬롯들 각각에 대한 협상 해법을 미리 계산할 수 있다.In step (410), the resource allocation device (101) can predict the number of users for each of the multiple consecutive time slots through machine learning and calculate a negotiation solution for each of the multiple time slots in advance.
단계(420)에서, 자원 할당 장치(101)는 이전 타임 슬롯에서의 사용자 수와 현재 타임 슬롯에서의 사용자 수가 서로 다른 경우, 기계학습을 통해 예측된 현재 타임 슬롯에서의 예상 사용자 수와 실제 사용자 수가 서로 동일한지 여부를 식별할 수 있다.In step (420), the resource allocation device (101) can identify whether the expected number of users in the current time slot predicted through machine learning and the actual number of users are the same, if the number of users in the previous time slot and the number of users in the current time slot are different from each other.
단계(430)에서, 현재 타임 슬롯에서의 예상 사용자 수와 실제 사용자 수가 동일한 것으로 식별된 경우, 자원 할당 장치(101)는 기계 학습을 통해 예측된 예상 사용자가 현재 타임 슬롯에 대한 임의의 할당 가능한 자원을 모두 사용하였을 때 획득 가능한 효용과 실제 사용자가 현재 타임 슬롯에서 할당 가능한 자원을 모두 사용하였을 때 획득 가능한 효용을 이용하여 변환 행렬을 생성할 수 있다.In step (430), if it is identified that the expected number of users in the current time slot and the actual number of users are the same, the resource allocation device (101) can generate a transformation matrix using the utility obtainable when the expected users predicted through machine learning use all of the allocatable resources for the current time slot and the utility obtainable when the actual users use all of the allocatable resources in the current time slot.
보다 구체적으로 자원 할당 장치(101)는 예상 사용자 가 현재 타임 슬롯에 대한 임의의 할당 가능 자원을 모두 사용하였을 때의 효용 과 실제 사용자 가 현재 타임 슬롯에서의 할당 가능 자원을 모두 사용하였을 때의 효용 의 비율을 대각선 원소로 하고, 대각선 원소 이외의 나머지가 모두 0 값을 가지는 변환 행렬 를 아래의 식 3과 같이 생성할 수 있다.More specifically, the resource allocation device (101) is an expected user Utility when all randomly allocatable resources for the current time slot are used and real users Utility when all available resources in the current time slot are used A transformation matrix in which the ratio of diagonal elements is 0, and all elements other than the diagonal elements have a value of 0. can be generated as shown in Equation 3 below.
<식 3><Formula 3>
단계(440)에서, 자원 할당 장치(101)는 생성된 변환 행렬 및 예상 사용자 수에 기초하여 미리 계산된 현재 시간 슬롯에서의 협상 해법 을 이용하여 현재 타임 슬롯에서의 합의 실패점을 식별할 수 있다. 이때, 합의 실패점 는 아래의 식 4와 같이 변환 행렬과 예상 사용자 수에 기초하여 미리 계산된 현재 시간 슬롯에서의 협상 해법을 곱한 결과로써 벡터 값을 가질 수 있다.In step (440), the resource allocation device (101) negotiates a solution in the current time slot that is pre-calculated based on the generated transformation matrix and the expected number of users. We can identify the consensus failure point in the current time slot using . At this time, the consensus failure point can have a vector value as a result of multiplying the negotiation solution in the current time slot calculated in advance based on the transformation matrix and the expected number of users, as in Equation 4 below.
<식 4><Formula 4>
단계(450)에서, 자원 할당 장치(101)는 합의 실패점에서의 자원 총합을 이용하여 현재 타임 슬롯에서 협상 해법을 찾기 위한 축소된 탐색 공간을 결정할 수 있다. 보다 구체적으로 자원 할당 장치(101)는 합의 실패점의 각 인덱스(Index) 마다 현재 타임 슬롯에서의 실제 사용자에 대한 효용 함수의 역함수를 구한 뒤 이를 모두 합산함으로써 합의 실패점에서의 자원 총합 을 결정할 수 있다. In step (450), the resource allocation device (101) can determine a reduced search space for finding a negotiation solution in the current time slot by using the total resources at the agreement failure point. More specifically, the resource allocation device (101) calculates the inverse function of the utility function for the actual user in the current time slot for each index of the agreement failure point and then adds them all up to obtain the total resources at the agreement failure point. can decide.
자원 할당 장치(101)는 이와 같이 결정된 합의 실패점에서의 자원 총합과 현재 타임 슬롯에서 할당 가능한 자원 중 작은 값을 하한으로 설정하고, 큰 값을 상한으로 설정함으로써 축소된 탐색 공간을 결정할 수 있다.The resource allocation device (101) can determine a reduced search space by setting a smaller value among the total resources at the agreed failure point determined in this manner and the resources allocatable in the current time slot as the lower limit, and setting a larger value as the upper limit.
마지막으로 단계(460)에서, 자원 할당 장치(101)는 축소된 탐색 공간 내에서 현재 타임 슬롯에 대한 협상 해법을 연산함으로써 낮은 계산 복잡도를 가지면서도 최적의 협상 해법을 결정할 수 있다.Finally, at step (460), the resource allocation device (101) can determine an optimal negotiation solution with low computational complexity by computing a negotiation solution for the current time slot within the reduced search space.
한편, 본 발명에 따른 방법은 컴퓨터에서 실행될 수 있는 프로그램으로 작성되어 마그네틱 저장매체, 광학적 판독매체, 디지털 저장매체 등 다양한 기록 매체로도 구현될 수 있다.Meanwhile, the method according to the present invention can be written as a program that can be executed on a computer and can be implemented in various recording media such as a magnetic storage medium, an optical reading medium, and a digital storage medium.
본 명세서에 설명된 각종 기술들의 구현들은 디지털 전자 회로조직으로, 또는 컴퓨터 하드웨어, 펌웨어, 소프트웨어로, 또는 그들의 조합들로 구현될 수 있다. 구현들은 데이터 처리 장치, 예를 들어 프로그램가능 프로세서, 컴퓨터, 또는 다수의 컴퓨터들의 동작에 의한 처리를 위해, 또는 이 동작을 제어하기 위해, 컴퓨터 프로그램 제품, 즉 정보 캐리어, 예를 들어 기계 판독가능 저장 장치(컴퓨터 판독가능 매체) 또는 전파 신호에서 유형적으로 구체화된 컴퓨터 프로그램으로서 구현될 수 있다. 상술한 컴퓨터 프로그램(들)과 같은 컴퓨터 프로그램은 컴파일된 또는 인터프리트된 언어들을 포함하는 임의의 형태의 프로그래밍 언어로 기록될 수 있고, 독립형 프로그램으로서 또는 모듈, 구성요소, 서브루틴, 또는 컴퓨팅 환경에서의 사용에 적절한 다른 유닛으로서 포함하는 임의의 형태로 전개될 수 있다. 컴퓨터 프로그램은 하나의 사이트에서 하나의 컴퓨터 또는 다수의 컴퓨터들 상에서 처리되도록 또는 다수의 사이트들에 걸쳐 분배되고 통신 네트워크에 의해 상호 연결되도록 전개될 수 있다.The implementations of the various technologies described herein may be implemented as digital electronic circuitry, or as computer hardware, firmware, software, or combinations thereof. The implementations may be implemented as a computer program product, i.e., a computer program tangibly embodied in an information carrier, e.g., a machine-readable storage medium (computer-readable medium) or a radio signal, for processing by the operation of a data processing device, e.g., a programmable processor, a computer, or multiple computers, or for controlling the operation thereof. A computer program, such as the computer program(s) described above, may be written in any form of programming language, including compiled or interpreted languages, and may be deployed in any form, including as a stand-alone program or as a module, component, subroutine, or other unit suitable for use in a computing environment. The computer program may be deployed to be processed on one computer or multiple computers at a single site, or distributed across multiple sites and interconnected by a communications network.
컴퓨터 프로그램의 처리에 적절한 프로세서들은 예로서, 범용 및 특수 목적 마이크로프로세서들 둘 다, 및 임의의 종류의 디지털 컴퓨터의 임의의 하나 이상의 프로세서들을 포함한다. 일반적으로, 프로세서는 판독 전용 메모리 또는 랜덤 액세스 메모리 또는 둘 다로부터 명령어들 및 데이터를 수신할 것이다. 컴퓨터의 요소들은 명령어들을 실행하는 적어도 하나의 프로세서 및 명령어들 및 데이터를 저장하는 하나 이상의 메모리 장치들을 포함할 수 있다. 일반적으로, 컴퓨터는 데이터를 저장하는 하나 이상의 대량 저장 장치들, 예를 들어 자기, 자기-광 디스크들, 또는 광 디스크들을 포함할 수 있거나, 이것들로부터 데이터를 수신하거나 이것들에 데이터를 송신하거나 또는 양쪽으로 되도록 결합될 수도 있다. 컴퓨터 프로그램 명령어들 및 데이터를 구체화하는데 적절한 정보 캐리어들은 예로서 반도체 메모리 장치들, 예를 들어, 하드 디스크, 플로피 디스크 및 자기 테이프와 같은 자기 매체(Magnetic Media), CD-ROM(Compact Disk Read Only Memory), DVD(Digital Video Disk)와 같은 광 기록 매체(Optical Media), 플롭티컬 디스크(Floptical Disk)와 같은 자기-광 매체(Magneto-Optical Media), 롬(ROM, Read Only Memory), 램(RAM, Random Access Memory), 플래시 메모리, EPROM(Erasable Programmable ROM), EEPROM(Electrically Erasable Programmable ROM) 등을 포함한다. 프로세서 및 메모리는 특수 목적 논리 회로조직에 의해 보충되거나, 이에 포함될 수 있다.Processors suitable for processing a computer program include, for example, both general-purpose and special-purpose microprocessors, and any one or more processors of any type of digital computer. Typically, the processor will receive instructions and data from a read-only memory or a random access memory or both. Elements of the computer may include at least one processor for executing instructions and one or more memory devices for storing instructions and data. Typically, the computer may include, or be coupled to receive data from, transmit data to, or both, one or more mass storage devices for storing data, such as magnetic, magneto-optical disks, or optical disks. Information carriers suitable for embodying computer program instructions and data include, by way of example, semiconductor memory devices, magnetic media such as hard disks, floppy disks, and magnetic tape, optical media such as CD-ROMs (Compact Disk Read Only Memory) and DVDs (Digital Video Disk), magneto-optical media such as floptical disks, ROMs (Read Only Memory), RAMs (Random Access Memory), flash memory, EPROMs (Erasable Programmable ROM), EEPROMs (Electrically Erasable Programmable ROM), etc. The processor and memory may be supplemented by, or included in, special purpose logic circuitry.
또한, 컴퓨터 판독가능 매체는 컴퓨터에 의해 액세스될 수 있는 임의의 가용매체일 수 있고, 컴퓨터 저장매체 및 전송매체를 모두 포함할 수 있다.Additionally, the computer-readable medium can be any available medium that can be accessed by a computer, and can include both computer storage media and transmission media.
본 명세서는 다수의 특정한 구현물의 세부사항들을 포함하지만, 이들은 어떠한 발명이나 청구 가능한 것의 범위에 대해서도 제한적인 것으로서 이해되어서는 안되며, 오히려 특정한 발명의 특정한 실시형태에 특유할 수 있는 특징들에 대한 설명으로서 이해되어야 한다. 개별적인 실시형태의 문맥에서 본 명세서에 기술된 특정한 특징들은 단일 실시형태에서 조합하여 구현될 수도 있다. 반대로, 단일 실시형태의 문맥에서 기술한 다양한 특징들 역시 개별적으로 혹은 어떠한 적절한 하위 조합으로도 복수의 실시형태에서 구현 가능하다. 나아가, 특징들이 특정한 조합으로 동작하고 초기에 그와 같이 청구된 바와 같이 묘사될 수 있지만, 청구된 조합으로부터의 하나 이상의 특징들은 일부 경우에 그 조합으로부터 배제될 수 있으며, 그 청구된 조합은 하위 조합이나 하위 조합의 변형물로 변경될 수 있다.While this specification contains details of a number of specific implementations, these should not be construed as limitations on the scope of any invention or what may be claimed, but rather as descriptions of features that may be unique to particular embodiments of particular inventions. Certain features described herein in the context of separate embodiments may also be implemented in combination in a single embodiment. Conversely, various features described in the context of a single embodiment may also be implemented in multiple embodiments, either individually or in any suitable subcombination. Furthermore, although features may operate in a particular combination and may initially be described as being claimed as such, one or more features from a claimed combination may in some cases be excluded from that combination, and the claimed combination may be modified into a subcombination or variation of a subcombination.
마찬가지로, 특정한 순서로 도면에서 동작들을 묘사하고 있지만, 이는 바람직한 결과를 얻기 위하여 도시된 그 특정한 순서나 순차적인 순서대로 그러한 동작들을 수행하여야 한다거나 모든 도시된 동작들이 수행되어야 하는 것으로 이해되어서는 안 된다. 특정한 경우, 멀티태스킹과 병렬 프로세싱이 유리할 수 있다. 또한, 상술한 실시형태의 다양한 장치 컴포넌트의 분리는 그러한 분리를 모든 실시형태에서 요구하는 것으로 이해되어서는 안되며, 설명한 프로그램 컴포넌트와 장치들은 일반적으로 단일의 소프트웨어 제품으로 함께 통합되거나 다중 소프트웨어 제품에 패키징 될 수 있다는 점을 이해하여야 한다.Likewise, although operations are depicted in the drawings in a particular order, this should not be understood to imply that the operations must be performed in the particular order illustrated or in any sequential order to achieve a desirable result, or that all of the illustrated operations must be performed. In certain cases, multitasking and parallel processing may be advantageous. Furthermore, the separation of the various device components of the embodiments described above should not be understood to require such separation in all embodiments, and it should be understood that the program components and devices described may generally be integrated together in a single software product or packaged into multiple software products.
한편, 본 명세서와 도면에 개시된 본 발명의 실시 예들은 이해를 돕기 위해 특정 예를 제시한 것에 지나지 않으며, 본 발명의 범위를 한정하고자 하는 것은 아니다. 여기에 개시된 실시 예들 이외에도 본 발명의 기술적 사상에 바탕을 둔 다른 변형 예들이 실시 가능하다는 것은, 본 발명이 속하는 기술분야에서 통상의 지식을 가진 자에게 자명한 것이다.Meanwhile, the embodiments of the present invention disclosed in this specification and drawings are merely specific examples presented to help understanding, and are not intended to limit the scope of the present invention. It will be apparent to those skilled in the art to which the present invention pertains that other modified examples based on the technical idea of the present invention can be implemented in addition to the embodiments disclosed herein.
101 : 자원 할당 장치
102 : 네트워크
103 : 전체 자원
104, 105 : 사용자들101 : Resource Allocation Device
102 : Network
103 : Total resources
104, 105 : Users
Claims (20)
이전 타임 슬롯에서의 사용자 수와 현재 타임 슬롯에서의 사용자 수가 동일한지 여부를 판단하는 단계;
상기 이전 타임 슬롯에서의 사용자 수와 상기 현재 타임 슬롯에서의 사용자 수가 동일한 것으로 판단된 경우, 상기 이전 타임 슬롯에서 각 사용자가 할당 가능한 자원을 모두 사용하였을 때 획득 가능한 효용과 상기 현재 타임 슬롯에서 각 사용자가 할당 가능한 자원을 모두 사용하였을 때 획득 가능한 효용을 이용하여 변환 행렬을 생성하는 단계;
상기 생성된 변환 행렬과 상기 이전 타임 슬롯에서의 협상 해법의 곱을 통해 상기 현재 타임 슬롯에서의 합의 실패점을 도출하는 단계;
상기 도출된 합의 실패점에서의 각 인덱스(Index) 마다 상기 각 사용자가 합의 실패 시 갖게 되는 효용 함수의 역함수를 합산함으로써 상기 도출된 합의 실패점에서의 자원 총합을 결정하는 단계;
상기 결정된 합의 실패점에서의 자원 총합과 상기 현재 타임 슬롯에서 할당 가능한 자원에 기초하여 상기 현재 타임 슬롯에서의 협상 해법을 찾기 위한 축소된 탐색 공간을 설정하는 단계; 및
상기 축소된 탐색 공간 내에서 협상 해법을 연산함으로써 상기 현재 타임 슬롯 내의 사용자들에게 자원을 할당하는 단계
를 포함하는 자원 할당 방법.In a resource allocation method performed by a processor,
A step of determining whether the number of users in the previous time slot and the number of users in the current time slot are the same;
A step of generating a transformation matrix by using the utility obtainable when each user uses all allocatable resources in the previous time slot and the utility obtainable when each user uses all allocatable resources in the current time slot, when it is determined that the number of users in the previous time slot and the number of users in the current time slot are the same;
A step of deriving an agreement failure point in the current time slot by multiplying the generated transformation matrix and the negotiation solution in the previous time slot;
A step of determining the total resources at the derived agreement failure point by adding the inverse function of the utility function that each user will have when the agreement fails for each index at the derived agreement failure point;
A step of setting a reduced search space for finding a negotiation solution in the current time slot based on the total resources at the determined agreement failure point and the resources allocable in the current time slot; and
A step of allocating resources to users within the current time slot by computing a negotiation solution within the reduced search space.
A resource allocation method that includes:
상기 변환 행렬은,
상기 이전 타임 슬롯에서의 각 사용자가 할당 가능한 자원을 모두 사용하였을 때 획득 가능한 효용과 상기 현재 타임 슬롯에서의 각 사용자가 할당 가능한 자원을 모두 사용하였을 때 획득 가능한 효용의 비율을 대각선 원소로 하고, 상기 대각선 원소 이외의 나머지가 0의 값을 가지는 자원 할당 방법.In the first paragraph,
The above transformation matrix is,
A resource allocation method in which the ratio of the utility obtainable when each user in the previous time slot uses all allocatable resources and the utility obtainable when each user in the current time slot uses all allocatable resources is a diagonal element, and the remainder other than the diagonal elements have a value of 0.
상기 축소된 탐색 공간을 설정하는 단계는,
상기 결정된 합의 실패점에서의 자원 총합과 상기 현재 타임 슬롯에서 할당 가능한 자원 중 작은 값을 하한으로 설정하고, 큰 값을 상한으로 설정함으로써 상기 탐색 공간을 축소하는 자원 할당 방법.In the first paragraph,
The step of setting the reduced search space is as follows:
A resource allocation method for reducing the search space by setting a smaller value among the total resources at the above-determined agreement failure point and the resources allocable in the current time slot as a lower limit, and setting a larger value as an upper limit.
연속적인 복수의 타임 슬롯들 각각에 대한 사용자 수를 예측하여 상기 복수의 타임 슬롯들 각각에 대한 협상 해법을 미리 계산하는 단계;
이전 타임 슬롯에서의 사용자 수와 현재 타임 슬롯에서의 사용자 수가 다른 경우, 상기 예측된 현재 타임 슬롯에서의 예상 사용자 수와 실제 사용자 수가 동일한지 여부를 판단하는 단계; 및
상기 현재 타임 슬롯에서의 예상 사용자 수와 실제 사용자 수가 동일한 것으로 판단된 경우, 상기 현재 타임 슬롯에서 예상 사용자가 임의의 할당 가능한 자원을 모두 사용하였을 때 획득 가능한 효용과 상기 현재 타임 슬롯에서 실제 사용자가 할당 가능한 자원을 모두 사용하였을 때 획득 가능한 효용을 이용하여 변환 행렬을 생성하는 단계；
상기 생성된 변환 행렬과 상기 예상 사용자 수에 기초하여 미리 계산된 현재 시간 슬롯에서의 협상 해법의 곱을 통해 상기 현재 타임 슬롯에서의 합의 실패점을 도출하는 단계；
상기 도출된 합의 실패점에서의 각 인덱스(Index) 마다 상기 실제 사용자가 합의 실패 시 갖게 되는 효용 함수의 역함수를 합산함으로써 상기 도출된 합의 실패점에서의 자원 총합을 결정하는 단계;
상기 결정된 합의 실패점에서의 자원 총합과 상기 현재 타임 슬롯에서 할당 가능한 자원에 기초하여 상기 현재 타임 슬롯에서의 협상 해법을 찾기 위한 축소된 탐색 공간을 설정하는 단계; 및
상기 축소된 탐색 공간 내에서 협상 해법을 연산함으로써 상기 현재 타임 슬롯 내의 실제 사용자에게 자원을 할당하는 단계
를 포함하는 자원 할당 방법.In a resource allocation method performed by a processor,
A step of predicting the number of users for each of a plurality of consecutive time slots and pre-calculating a negotiation solution for each of the plurality of time slots;
If the number of users in the previous time slot is different from the number of users in the current time slot, a step of determining whether the expected number of users in the predicted current time slot and the actual number of users are the same; and
A step of generating a transformation matrix by using the utility obtainable when the expected number of users in the current time slot uses all allocatable resources and the utility obtainable when the actual user in the current time slot uses all allocatable resources, when it is determined that the expected number of users in the current time slot and the actual number of users in the current time slot are the same;
A step of deriving an agreement failure point in the current time slot by multiplying the generated transformation matrix and the negotiation solution in the current time slot calculated in advance based on the expected number of users;
A step of determining the total resource at the derived agreement failure point by adding the inverse function of the utility function that the actual user will have when the agreement fails for each index at the derived agreement failure point;
A step of setting a reduced search space for finding a negotiation solution in the current time slot based on the total resources at the determined agreement failure point and the resources allocable in the current time slot; and
A step of allocating resources to actual users within the current time slot by computing a negotiation solution within the reduced search space.
A resource allocation method that includes:
상기 변환 행렬은,
상기 예상 사용자 각각이 상기 현재 타임 슬롯에 대한 임의의 할당 가능한 자원을 모두 사용했을 때의 효용과 상기 실제 사용자 각각이 상기 현재 타임 슬롯에서 할당 가능한 자원을 모두 사용하였을 때의 효용의 비율을 대각선 원소로 하고, 상기 대각선 원소 이외의 나머지가 0의 값을 가지는 자원 할당 방법.In Article 6,
The above transformation matrix is,
A resource allocation method in which the ratio of the utility when each of the above expected users uses all of the allocatable resources for the current time slot and the utility when each of the above actual users uses all of the allocatable resources in the current time slot is a diagonal element, and the remaining elements other than the diagonal elements have a value of 0.
상기 축소된 탐색 공간을 설정하는 단계,
상기 결정된 합의 실패점에서의 자원 총합과 상기 현재 타임 슬롯에서 할당 가능한 자원 중 작은 값을 하한으로 설정하고, 큰 값을 상한으로 설정함으로써 상기 탐색 공간을 축소하는 자원 할당 방법.In Article 6,
The step of setting the reduced search space,
A resource allocation method for reducing the search space by setting a smaller value among the total resources at the above-determined agreement failure point and the resources allocable in the current time slot as a lower limit, and setting a larger value as an upper limit.
상기 자원 할당 장치는, 프로세서를 포함하고,
상기 프로세서는,
이전 타임 슬롯에서의 사용자 수와 현재 타임 슬롯에서의 사용자 수가 동일한지 여부를 판단하고, 상기 이전 타임 슬롯에서의 사용자 수와 상기 현재 타임 슬롯에서의 사용자 수가 동일한 것으로 판단된 경우, 상기 이전 타임 슬롯에서 각 사용자가 할당 가능한 자원을 모두 사용하였을 때 획득 가능한 효용과 상기 현재 타임 슬롯에서 각 사용자가 할당 가능한 자원을 모두 사용하였을 때 획득 가능한 효용을 이용하여 변환 행렬을 생성하며, 상기 생성된 변환 행렬과 상기 이전 타임 슬롯에서의 협상 해법의 곱을 통해 상기 현재 타임 슬롯에서의 합의 실패점을 도출하고, 상기 도출된 합의 실패점에서의 각 인덱스(Index) 마다 상기 각 사용자가 합의 실패 시 갖게 되는 효용 함수의 역함수를 합산함으로써 상기 도출된 합의 실패점에서의 자원 총합을 결정하며, 상기 결정된 합의 실패점에서의 자원 총합과 상기 현재 타임 슬롯에서 할당 가능한 자원에 기초하여 상기 현재 타임 슬롯에서의 협상 해법을 찾기 위한 축소된 탐색 공간을 설정하며, 상기 축소된 탐색 공간 내에서 협상 해법을 연산함으로써 상기 현재 타임 슬롯 내의 사용자들에게 자원을 할당하는 자원 할당 장치.In the resource allocation device,
The above resource allocation device comprises a processor,
The above processor,
A resource allocation device which determines whether the number of users in a previous time slot is the same as the number of users in a current time slot, and if it is determined that the number of users in the previous time slot is the same, generates a transformation matrix by using the utility obtainable when each user uses all allocatable resources in the previous time slot and the utility obtainable when each user uses all allocatable resources in the current time slot, derives an agreement failure point in the current time slot by multiplying the generated transformation matrix by a negotiation solution in the previous time slot, and determines the sum of resources at the derived agreement failure point by adding the inverse function of the utility function that each user will have when an agreement fails for each index at the derived agreement failure point, and sets a reduced search space for finding a negotiation solution in the current time slot based on the determined sum of resources at the agreement failure point and the resources allocatable in the current time slot, and allocates resources to the users in the current time slot by computing the negotiation solution within the reduced search space.
상기 변환 행렬은,
상기 이전 타임 슬롯에서의 각 사용자가 할당 가능한 자원을 모두 사용하였을 때 획득 가능한 효용과 상기 현재 타임 슬롯에서의 각 사용자가 할당 가능한 자원을 모두 사용하였을 때 획득 가능한 효용의 비율을 대각선 원소로 하고, 상기 대각선 원소 이외의 나머지가 0의 값을 가지는 자원 할당 장치.In Article 11,
The above transformation matrix is,
A resource allocation device in which a diagonal element is a ratio of a utility obtainable when each user in the previous time slot uses all allocatable resources and a utility obtainable when each user in the current time slot uses all allocatable resources, and all elements other than the diagonal element have a value of 0.
상기 프로세서는,
상기 결정된 합의 실패점에서의 자원 총합과 상기 현재 타임 슬롯에서 할당 가능한 자원 중 작은 값을 하한으로 설정하고, 큰 값을 상한으로 설정함으로써 상기 탐색 공간을 축소하는 자원 할당 장치.In Article 11,
The above processor,
A resource allocation device that reduces the search space by setting a smaller value among the total resources at the above-determined agreement failure point and the resources allocable in the current time slot as a lower limit, and setting a larger value as an upper limit.
상기 자원 할당 장치는, 프로세서를 포함하고,
상기 프로세서는,
연속적인 복수의 타임 슬롯들 각각에 대한 사용자 수를 예측하여 상기 복수의 타임 슬롯들 각각에 대한 협상 해법을 미리 계산하고, 이전 타임 슬롯에서의 사용자 수와 현재 타임 슬롯에서의 사용자 수가 다른 경우, 상기 예측된 현재 타임 슬롯에서의 예상 사용자 수와 실제 사용자 수가 동일한지 여부를 판단하며, 상기 현재 타임 슬롯에서의 예상 사용자 수와 실제 사용자 수가 동일한 것으로 판단된 경우, 상기 현재 타임 슬롯에서 예상 사용자가 임의의 할당 가능한 자원을 모두 사용하였을 때 획득 가능한 효용과 상기 현재 타임 슬롯에서 실제 사용자가 할당 가능한 자원을 모두 사용하였을 때 획득 가능한 효용을 이용하여 변환 행렬을 생성하고, 상기 생성된 변환 행렬과 상기 예상 사용자 수에 기초하여 미리 계산된 현재 시간 슬롯에서의 협상 해법의 곱을 통해 상기 현재 타임 슬롯에서의 합의 실패점을 도출하며, 상기 도출된 합의 실패점에서의 각 인덱스(Index) 마다 상기 실제 사용자가 합의 실패 시 갖게 되는 효용 함수의 역함수를 합산함으로써 상기 도출된 합의 실패점에서의 자원 총합을 결정하고, 상기 결정된 합의 실패점에서의 자원 총합과 상기 현재 타임 슬롯에서 할당 가능한 자원에 기초하여 상기 현재 타임 슬롯에서의 협상 해법을 찾기 위한 축소된 탐색 공간을 설정하며, 상기 축소된 탐색 공간 내에서 협상 해법을 연산함으로써 상기 현재 타임 슬롯 내의 실제 사용자에게 자원을 할당하는 자원 할당 장치.In the resource allocation device,
The above resource allocation device comprises a processor,
The above processor,
The number of users for each of a plurality of consecutive time slots is predicted, and a negotiation solution for each of the plurality of time slots is calculated in advance, and if the number of users in the previous time slot is different from the number of users in the current time slot, it is determined whether the predicted number of users in the predicted current time slot and the actual number of users are the same, and if it is determined that the predicted number of users in the current time slot and the actual number of users are the same, a transformation matrix is generated using the utility obtainable when the predicted user uses all of any allocatable resources in the current time slot and the utility obtainable when the actual user uses all of the allocatable resources in the current time slot, and the agreement failure point in the current time slot is derived by multiplying the generated transformation matrix and the negotiation solution in the current time slot calculated in advance based on the predicted number of users, and the sum of the resources at the derived agreement failure point is determined by adding up the inverse function of the utility function that the actual user has when the agreement fails for each index at the derived agreement failure point, and the negotiation in the current time slot is performed based on the determined sum of the resources at the determined agreement failure point and the allocatable resources in the current time slot. A resource allocation device that sets up a reduced search space for finding a solution and allocates resources to actual users within the current time slot by computing a negotiated solution within the reduced search space.
상기 변환 행렬은,
상기 예상 사용자 각각이 상기 현재 타임 슬롯에 대한 임의의 할당 가능한 자원을 모두 사용했을 때의 효용과 상기 실제 사용자 각각이 상기 현재 타임 슬롯에서 할당 가능한 자원을 모두 사용하였을 때의 효용의 비율을 대각선 원소로 하고, 상기 대각선 원소 이외의 나머지가 0의 값을 가지는 자원 할당 장치.In Article 16,
The above transformation matrix is,
A resource allocation device in which a diagonal element is a ratio of a utility when each of the above-mentioned expected users uses all of the allocatable resources for the current time slot and a utility when each of the above-mentioned actual users uses all of the allocatable resources for the current time slot, and all elements other than the diagonal element have a value of 0.
상기 프로세서는,
상기 결정된 합의 실패점에서의 자원 총합과 상기 현재 타임 슬롯에서 할당 가능한 자원 중 작은 값을 하한으로 설정하고, 큰 값을 상한으로 설정함으로써 상기 탐색 공간을 축소하는 자원 할당 장치.
In Article 16,
The above processor,
A resource allocation device that reduces the search space by setting a smaller value among the total resources at the above-determined agreement failure point and the resources allocable in the current time slot as a lower limit, and setting a larger value as an upper limit.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| KR1020210192985A KR102803930B1 (en) | 2021-12-30 | 2021-12-30 | Resource allocation method and apparatus using sequential parameter estimation |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| KR1020210192985A KR102803930B1 (en) | 2021-12-30 | 2021-12-30 | Resource allocation method and apparatus using sequential parameter estimation |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| KR20230102664A KR20230102664A (en) | 2023-07-07 |
| KR102803930B1 true KR102803930B1 (en) | 2025-05-07 |
Family
ID=87153780
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| KR1020210192985A Active KR102803930B1 (en) | 2021-12-30 | 2021-12-30 | Resource allocation method and apparatus using sequential parameter estimation |
Country Status (1)
| Country | Link |
|---|---|
| KR (1) | KR102803930B1 (en) |
Citations (7)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US20160219602A1 (en) | 2013-09-26 | 2016-07-28 | Nec Corporation | Radio base station apparatus and resource allocation method |
| CN106488570A (en) | 2016-12-26 | 2017-03-08 | 重庆邮电大学 | A kind of resource scheduling algorithm being applied to WIA PA industry wireless network |
| US20190069310A1 (en) | 2017-08-23 | 2019-02-28 | Qualcomm Incorporated | Predicting resource unit allocations in a wireless network |
| CN109479312A (en) | 2016-08-04 | 2019-03-15 | 高通股份有限公司 | Coordination of signaling and resource allocation in wireless networks using radio access technologies |
| CN106793128B (en) | 2017-03-23 | 2019-11-19 | 江苏中科羿链通信技术有限公司 | A kind of channel wireless radio multi Mesh network TDMA resource allocation methods |
| US20200090194A1 (en) | 2018-09-13 | 2020-03-19 | Bank Of America Corporation | Automated resource allocation based on predictive analysis |
| CN112291791A (en) | 2020-10-31 | 2021-01-29 | 国网河南省电力公司经济技术研究院 | Power communication mesh bandwidth resource allocation method based on 5G slice |
Family Cites Families (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| KR20110024582A (en) * | 2009-09-02 | 2011-03-09 | 경희대학교 산학협력단 | How to allocate resource optimally to multiple users in wireless network using bagging game |
| KR102717122B1 (en) * | 2020-04-14 | 2024-10-14 | 한국전자기술연구원 | Method and System for operating distributed resource based on load prediction correction technique using error between predicted load and actual load |
-
2021
- 2021-12-30 KR KR1020210192985A patent/KR102803930B1/en active Active
Patent Citations (7)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US20160219602A1 (en) | 2013-09-26 | 2016-07-28 | Nec Corporation | Radio base station apparatus and resource allocation method |
| CN109479312A (en) | 2016-08-04 | 2019-03-15 | 高通股份有限公司 | Coordination of signaling and resource allocation in wireless networks using radio access technologies |
| CN106488570A (en) | 2016-12-26 | 2017-03-08 | 重庆邮电大学 | A kind of resource scheduling algorithm being applied to WIA PA industry wireless network |
| CN106793128B (en) | 2017-03-23 | 2019-11-19 | 江苏中科羿链通信技术有限公司 | A kind of channel wireless radio multi Mesh network TDMA resource allocation methods |
| US20190069310A1 (en) | 2017-08-23 | 2019-02-28 | Qualcomm Incorporated | Predicting resource unit allocations in a wireless network |
| US20200090194A1 (en) | 2018-09-13 | 2020-03-19 | Bank Of America Corporation | Automated resource allocation based on predictive analysis |
| CN112291791A (en) | 2020-10-31 | 2021-01-29 | 国网河南省电力公司经济技术研究院 | Power communication mesh bandwidth resource allocation method based on 5G slice |
Non-Patent Citations (5)
| Title |
|---|
| 3GPP R3-206721 |
| 3GPP R3-213725 |
| 3GPP R3-215331 |
| J. Choi and H. Park, "Direction Vector-Based Algorithm for the Nash Bargaining Solution in Dynamic Networks," in IEEE Communications Letters, vol.22, no.7, pp.1342-1345(2018.07.) 1부.* |
| Lenovo et al., R3-213725, Discussion on traffic load prediction, 3GPP TSG RAN WG3 #113-E, 3GPP 서버공개일(2021.08.06.) 1부.* |
Also Published As
| Publication number | Publication date |
|---|---|
| KR20230102664A (en) | 2023-07-07 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US20240430695A1 (en) | Performance assurance and optimization for gaa and pal devices in a cbrs network for private enterprise environment | |
| EP3281359B1 (en) | Application driven and adaptive unified resource management for data centers with multi-resource schedulable unit (mrsu) | |
| US9665410B2 (en) | Processing of application programming interface traffic | |
| Piao et al. | A network-aware virtual machine placement and migration approach in cloud computing | |
| US11283860B2 (en) | Apparatus and method for adjusting resources in cloud system | |
| KR102382913B1 (en) | Method and Apparatus for Wireless Resource Scheduling with Guaranteed QoS in Mobile Communication System | |
| US9092259B2 (en) | Apparatus and method for controlling a resource utilization policy in a virtual environment | |
| US20170214634A1 (en) | Joint autoscaling of cloud applications | |
| US7085249B2 (en) | Dynamic QoS for integrated voice and data CDMA/1XRTT networks | |
| JP2004062911A (en) | System for managing allocation of computer resource | |
| CN105183565A (en) | Computer and service quality control method and device | |
| CN110661654B (en) | Network bandwidth resource allocation method, device, equipment and readable storage medium | |
| CN105824705B (en) | A task assignment method and electronic device | |
| JP2022540261A (en) | Method, base station and system for suppressing co-frequency interference of cells | |
| JP2018190355A (en) | Resource management method | |
| KR102803930B1 (en) | Resource allocation method and apparatus using sequential parameter estimation | |
| EP3804381B1 (en) | Cellular telecommunications network | |
| KR101932523B1 (en) | Method for dynamically increasing and decreasing the slots of virtual gpu memory allocated to a virtual machine and computing device implementing the same | |
| WO2017025795A1 (en) | Method and apparatus for controlling data packet transmission in a device-to-device communication | |
| KR101937558B1 (en) | Method for optimizing memory size and backhaul acllocation for cache-enbled base station and base station | |
| CN115878309A (en) | Resource allocation method, apparatus, processing core, device and computer readable medium | |
| JP2021141514A (en) | Frequency mapping device, frequency mapping method and computer program | |
| KR100447059B1 (en) | Traffic Handling Processor Block Assignment Method of RNC in Wireless Communication System | |
| JPWO2014115282A1 (en) | Computer system and computer resource allocation method | |
| EP4216504A1 (en) | Method for predicatively operating a communication network |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PA0109 | Patent application |
Patent event code: PA01091R01D Comment text: Patent Application Patent event date: 20211230 |
|
| PA0201 | Request for examination | ||
| PG1501 | Laying open of application | ||
| E902 | Notification of reason for refusal | ||
| PE0902 | Notice of grounds for rejection |
Comment text: Notification of reason for refusal Patent event date: 20240603 Patent event code: PE09021S01D |
|
| E701 | Decision to grant or registration of patent right | ||
| PE0701 | Decision of registration |
Patent event code: PE07011S01D Comment text: Decision to Grant Registration Patent event date: 20250228 |
|
| GRNT | Written decision to grant | ||
| PR0701 | Registration of establishment |
Comment text: Registration of Establishment Patent event date: 20250429 Patent event code: PR07011E01D |
|
| PR1002 | Payment of registration fee |
Payment date: 20250430 End annual number: 3 Start annual number: 1 |
|
| PG1601 | Publication of registration |