KR20190065803A - Method and apparatus for coding index in user equipment with limited memori state information and wireless communication method - Google Patents

Abstract

Disclosed are a method and an apparatus for index coding in an environment where memory storage information of a user terminal is limited, and a wireless communications method. The method for index coding for a plurality of user terminals belonging to a base station in a network environment where memory storage information of a user terminal changes over times, comprises the following steps of: determining an index code to be used for index coding based on memory storage information of a user terminal estimated by the base station, from an index code set including decodable index codes; selecting an index code different from the index code determined from the index code set; comparing the determined index code with the selected different index code to determine an optimal index code; and transmitting a file requested in a corresponding terminal to at least one user terminal corresponding to the determined optimal index code, wherein the index code may indicate a user group grouped based on the requested file among the user terminals.

Description

BACKGROUND OF THE INVENTION 1. Field of the Invention [0001] The present invention relates to a method and apparatus for index encoding in an environment where memory storage information of a user terminal is limited, and a wireless communication method.

The present invention relates to a technique for providing a multicast transmission based on index coding in a network environment in which a base station does not accurately know memory state information (MSI) of a user terminal.

Wireless data traffic has exploded in recent years due to text, voice messages, video streaming, and so on. Such an increase trend is expected to become even more serious due to services such as virtual reality, augmented reality, and hologram. While wireless data traffic has unique characteristics such as preference for popular content, predictable demand, current wireless communication systems have increased efficiency through additional wireless communication resources without reflecting the unique characteristics. However, the use of wireless communication resources has reached a certain limit and new technologies are needed. As one of the new technologies, caching has been introduced in which a user of the network stores some video data in memory.

Caching is known to significantly reduce overall network traffic. Conventional caching algorithms process the requested data in a multicast manner in a situation where a user (i.e., a user terminal carried by the user) receives the same data by utilizing a cache memory. However, when users request different data, they have to solve them one by one in a unicast manner.

Non-Patent Document [1] MA Maddah- Alli, and U. Niesen , Fundamental limits of caching. IEEE Transactions on Information Theory Vol . 60, pg . 2856-2867 (May 2014) , and [2] US . Appl . No. US 9535837 B2, Decentralized online cache management for digital content conveyed over shared network connections based on cache fullness and cache eviction policies, filed 2013.11.19 introduces a new caching algorithm that effectively reduces transmission time when users request different data . That is, it is possible to combine data of a plurality of users through multicast using index coding, thereby reducing transmission time considerably. Non-Patent Document [3] KR Son, JH Lee and W. Choi, User-cache Aided Transmission with Index Coding for Minimum Outage Probability in K-User Downlink channels. IEEE Transactions on Wireless Communications. Submitted. Proposed an index encoding based transmission scheme that utilizes user 's stored information in a network environment that reflects radio channel characteristics such as radio channel fading and mutual interference.

However, the conventional caching method assumes an unrealistic situation in which the base station knows all memory states (i.e., memory storage information) of the user terminal. That is, it is assumed that the base station correctly knows the contents (i.e., memory storage information, MSI) stored in the cache memory of the user terminal.

However, since the user's request file and the memory storage information of the user change instantaneously, it is realistic that the base station can not accurately know the memory storage information. As described above, when the base station does not know the memory storage information of the terminal exactly like an actual environment, an error occurs in the multicast transmission using the index encoding.

Accordingly, there is a demand for an index encoding transmission technique capable of obtaining optimum performance even when the user's requested file is not accurate regardless of the file length. That is, in a network environment in which memory storage information of a terminal changes according to time, there is a need for an index encoding transmission technique capable of obtaining optimum performance even if the base station does not know the memory storage information of the terminal correctly.

Korean Patent Laid-Open No. 10-2010-00048130 relates to a cluster-based distributed storage system and an operation method thereof, and discloses a technique of multicasting data into a cluster after distributing data to a cache.

 [1] M. A. Maddah-Ali, and U. Niesen, Fundamental limits of caching. IEEE Transactions on Information Theory Vol. 60, pg. 2856-2867 (May 2014). [2] U.S. Appl. No. US 9535837 B2, Decentralized online cache management for digital content conveyed over shared network connections based on cache fullness and cache eviction policies, filed 2013.11.19. [3] K. R. Son, J. H. Lee and W. Choi, User-cache Aided Transmission with Index Coding for Minimum Outage Probability in K-User Downlink channels. IEEE Transactions on Wireless Communications. Submitted.

In a network environment in which a request file and memory state information (MSI) of a user terminal belonging to a base station change with time, even when the base station does not know the memory storage information of the user terminal accurately, The present invention relates to a technique for performing optimal index coding for transmission. That is, an optimal user group that maximizes the total sum of successful transmission of each user terminal is determined using incorrect memory storage information (i.e., memory storage information of the terminal estimated by the base station).

1. A method for index coding a plurality of user terminals belonging to a base station in a network environment in which memory storage information of a user terminal changes with time, the method comprising the steps of: index code including index codes capable of being decodable; Determining, in the set, an index code to be used for index encoding based on memory storage information of a user terminal estimated by the base station; selecting an index code different from the index code determined in the index code set; Comparing the index code with the selected other index code to determine an optimal index code, and transmitting the requested file to the at least one user terminal corresponding to the determined optimal index code, The index code includes And may indicate a group of users grouped based on the requested one of the plurality of user terminals.

According to an aspect of the present invention, the determining with the optimal index code may include comparing a sum of the successive transmission amounts of the determined index code and the selected other index codes, And setting a sum of success transmission amounts of any one of the index codes selected for the index codes other than the determined index code and the selected other index codes among all the index codes included in the set of index codes, And updating the optimal index code by comparing the sum of success transmission amounts of the optimal index codes.

According to another aspect, the step of transmitting the file may transmit the file to at least one user terminal corresponding to the updated optimal index code.

According to another aspect of the present invention, the step of determining with the optimum index code is a step of determining, based on a brute-force algorithm, all index codes included in the index code set, The index code can determine the optimal index code.

According to another aspect, the optimal index code can be changed based on a correlation between memory storage information of a user terminal estimated by the base station and actual memory information of the corresponding user terminal.

According to another aspect of the present invention, the step of transmitting the file includes the step of, when the correlation is lower than a predefined first reference value, determining a file requested by the corresponding terminal to the at least one user terminal corresponding to the optimal index code To the unicast.

According to another aspect of the present invention, the step of transmitting the file includes the step of, when the correlation is higher than a predetermined second reference value, the file requested by the corresponding terminal for at least one user terminal corresponding to the optimum index code And transmitting the multicast data to the mobile station.

According to another aspect, the correlation may be changed according to the surrounding information and the time between the base station and the user terminal.

There is provided an apparatus for performing index coding on a plurality of user terminals in a network environment in which memory storage information of a user terminal varies with time. In an index code set including index codes that are decodable, An index code determination unit for determining an index code to be used for index encoding based on memory storage information of a user terminal estimated by the index encoding apparatus, an index code different from the index code determined in the index code set, An optimum index code determining unit for comparing the index code with the selected other index code to determine an optimal index code, and a transmission unit for transmitting the requested file to the at least one user terminal corresponding to the determined optimal index code, Including a control unit , The index code, and may refer to the group group of users based on a request file of the plurality of user terminals.

According to an aspect of the present invention, the optimum index code determination unit compares the sum of the successive transmission amounts of the determined index code and the selected other index codes, and sets an index code having a larger sum of success transmission amounts as the optimal index code The sum of the success transmission amounts of any one of the index codes selected for the index codes other than the determined index code and the selected other index codes among all the index codes included in the index code set, And the optimal index code can be updated.

According to another aspect, the transmission control unit may transmit a file to at least one user terminal corresponding to the updated optimal index code.

According to another aspect of the present invention, the optimal index code determination unit may determine, based on a brute-force algorithm, all index codes included in the index code set, The optimal index code can be determined.

According to another aspect, the optimal index code may be changed based on a correlation between memory storage information of a user terminal estimated by the index encoding device and actual memory information of the corresponding user terminal.

According to another aspect of the present invention, when the correlation is lower than a predefined first reference value, the transmission control unit transmits a file requested by the corresponding terminal to at least one user terminal corresponding to the optimal index code, unicast).

According to another aspect of the present invention, when the correlation is higher than a predetermined second reference value, the transmission control unit multicasts a file requested by the corresponding terminal to at least one user terminal corresponding to the optimal index code multicast).

According to another aspect, the correlation may be changed according to the surrounding information and the time between the base station and the user terminal.

According to embodiments of the present invention, an index code is determined based on a correlation between memory storage information of a user terminal estimated by a base station and memory storage information of an actual user terminal, The user can maximize the sum of success traffic of each user terminal by multicasting the file to the user group.

1 is a diagram illustrating a downlink model in a case where the base station does not know the memory storage information of the user terminal accurately in an embodiment of the present invention.
2 is a flowchart showing an index encoding method in a temporal example of the present invention.
3 is a block diagram illustrating an internal structure of an index encoding apparatus according to an embodiment of the present invention.
4 is a diagram illustrating memory storage information in the case where there are four user terminals belonging to a base station in the embodiment of the present invention.
FIG. 5 is a graph showing performance according to correlation p in an embodiment of the present invention. FIG.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS Hereinafter, embodiments of the present invention will be described in detail with reference to the accompanying drawings.

In a caching technology for storing a file or a portion of a file in a cache memory of a user terminal belonging to a base station and providing a request file based on a file stored in a cache memory of the user terminal when the user terminal requests it, The present invention relates to an index encoding transmission technique that minimizes errors in multicast transmission (i.e., maximizes / increases a successful transmission rate) when the memory storage information of the multicast transmission is not known accurately.

In the present embodiment, the index encoding apparatus represents a base station and the user equipment is located in a cell corresponding to the base station. The user terminal belonging to the base station may be a smart phone, a tablet PC , Notebooks, and the like. In addition, the user terminal may include a relay device such as a gateway acting as a relay between the base station and the user terminal, and each user terminal may have a cache memory. At this time, the size of the cache memory may be limited, and the cache memory may be storing at least one file among a plurality of files stored in the base station, or a file fragment (i.e., packet) that is a part of the file. For example, it may be limited to be less than the size of one file requested by the user terminal.

In the present embodiment, "memory state information (MSI)" indicates the memory status of the user terminal, and it can indicate the contents (i.e., file, file fragment) information stored in the cache memory of the user terminal have. For example, if the first file fragment of the file 1 and the second file fragment of the file 4 are stored in the cache memory of the user terminal 1, the memory storage information of the user terminal 1 is stored in the file fragment 1, File fragment 2 can be included. Accordingly, as the file requested by the user terminal 1 (i.e., the request file) is received from the base station and the other user terminals or at least one of them, the files stored in the cache memory are cumulatively accumulated over time, The information may change with time, and the present invention is to provide an index encoding transmission technique capable of obtaining optimum performance even when memory storage information changes.

1 is a diagram illustrating a downlink model in a case where the base station does not know the memory storage information of the user terminal accurately in an embodiment of the present invention.

Although FIG. 1 shows a case where there are three user terminals belonging to the base station, this corresponds to the embodiment, and the number of user terminals may be less than three or more than three.

1, an index encoding apparatus 100 as a base station has one antenna and can support K (e.g., three) user terminals 101, 102, and 103 having a single antenna.

로 표현될 수 있다. 여기서, 각 파일의 크기

는 B bit일 수 있다.

는 k번째 사용자 단말에서 요청한 요구 파일을 나타내고,

는 k번째 사용자 단말의 캐시 메모리에 저장되어 있는 파일을 나타낼 수 있다. 이때, 사용자 단말들 각각은 자신의 캐시 메모리에 저장되어 있는 파일을 요청하지 않는 것을 가정한다(즉,

). 도 1 내지 도 5에서는 명확성을 위하여 채널과 잡음(noise)으로 인한 에러(error)가 없는 채널 환경(error-free)을 대상으로 인덱스 부호화하는 방법을 설명하나, 이는 실시예에 해당하며, 에러가 존재하는 채널 환경으로 인덱스 부호화를 확장할 수 있다.The index encoding apparatus 100, which is a base station, may have N files as a library,

. ≪ / RTI > Here, the size of each file

Can be a B bit.

Denotes a request file requested by the k-th user terminal,

May represent a file stored in the cache memory of the kth user terminal. At this time, it is assumed that each of the user terminals does not request a file stored in its cache memory (i.e.,

). In FIGS. 1 to 5, for clarity, a method of performing index encoding on a channel environment (error-free) that is free of errors due to a channel and noise is described. However, Index encoding can be extended to existing channel environments.

로 정의될 수 있으며,

는 i번째 시간대(즉, 타임 슬롯)에 서비스할 사용자들의 집합을 나타낼 수 있다. 이때, 상기 사용자 집합들은

과

을 만족해야 할 수 있다. 그리고, 사용자 인덱스를 받았을 때 해당 사용자의 그룹 인덱스를 나타내는 그룹 인덱스 지표(group index indicator)

는 아래의 수학식 1과 같이 표현될 수 있다.Referring again to FIG. 1, the index encoding apparatus 100, which is a base station, can transmit a file in multicast using K time slots to K user terminals 101, 102, and 103. At this time, the total number K of user terminals may be smaller than the total number N of files. Thus, in multicast transmission, K different sets of users

, ≪ / RTI >

May represent a set of users to serve in the i < th > time zone (i.e., timeslot). At this time,

and

. ≪ / RTI > When a user index is received, a group index indicator indicating a group index of the corresponding user,

Can be expressed by the following equation (1).

[Equation 1]

(

로 표기)로 정의되어 있을 때, 인덱스 부호화 가정은 다음과 같을 수 있다. 기지국인 인덱스 부호화 장치(100)는 그룹

에 속해 있는 원소들을 인덱스로 가지는 파일들에 대해 배타적 논리합(exclusive or, XOR)을 수행하여 부호화된 파일을 생성할 수 있다. 그러면, n번째 파일에 해당하는 전송될 부호화된 파일

은 아래의 수학식 2와 같이 표현될 수 있다.In Equation (1), the user group

(

Quot;), the index encoding assumption may be as follows. The index encoding device 100, which is a base station,

(Exclusive or XOR) on files having indexes belonging to the indexed files to generate an encoded file. Then, the encoded file to be transmitted corresponding to the n-th file

Can be expressed by the following equation (2).

&Quot; (2) "

는 0으로만 구성된 B 비트 파일을 나타내고,

는 XOR 연산자를 나타낼 수 있다. In Equation (2)

Represents a B-bit file composed of only 0,

Can represent an XOR operator.

을 K개의 타임 슬롯에 걸쳐 전송한 경우, k번째 사용자 단말은

번째 시간대에 자신이 요청한 파일(즉, 요구 파일)을 수신할 수 있다. 이때, 아래의 수학식 3과 같이, 사용자 단말이

에 속한 원소들의 파일을 자신의 캐시 메모리에 저장하고 있는 경우, 해당 사용자 단말은 아래의 수학식 4에 기초하여 자신이 요청한 파일을 복원할 수 있다.The index encoding apparatus 100, which is a base station, decodes a file represented by Equation (2)

Is transmitted over K time slots, the kth user terminal

(I.e., a request file) in the second time zone. At this time, as shown in Equation (3) below,

The user terminal can restore the file requested by the user based on Equation (4) below.

&Quot; (3) "

&Quot; (4) "

(I.e., a request file) requested by a user terminal requesting a specific file based on the file transmitted by the base station and the file stored in the cache memory of the user terminals belonging to the base station, as shown in Equations 1 through 4 above The BS can perform index coding based on the memory storage information estimated by the BS when the MSI of the request file and the MSI changes with time in the system environment.

At this time, if the base station does not know the memory storage information of the user terminal clearly (that is, if it has incorrect information), index coding is performed considering the correlation between the estimated memory storage information and the actual memory storage information , It is possible to obtain optimal performance (i.e., maximize the sum of the successful bit rates). 1, a file stored in the cache memory of each of the user terminals 101, 102, 103 belonging to the base station 100 and the user terminals 101, 102, 103 known to the base station 100, The file stored in the cache memory of FIG. That is, the memory storage information (MSI) of the terminal estimated by the base station 100 may differ from the actual memory storage information (MSI) of the terminal. For example, the file 3 and the file 7 are stored in the cache memory of the user terminal 1 101. The base station 100 estimates the memory storage information (MSI) of the user terminal 1 101 as the file 1 and the file 4 . Similarly, the actual memory storage information (MSI) of user terminal 2 102 includes file 1 and file 9, where the MSI information is associated with file 2 and file 4 with respect to user terminal 2 (102) It can be assumed that it includes. By performing index coding considering the correlation between the MSI information estimated by the base station 100 and the actual MSI information, optimal performance can be obtained. Hereinafter, referring to FIG. 2 to FIG. 5, it is assumed that index coding is performed in consideration of correlation, that is, an index code for obtaining an optimal performance is determined, and multicast or unicast is performed considering the correlation. Will now be described.

FIG. 2 is a flowchart illustrating an index encoding method in a temporal example of the present invention, and FIG. 3 is a block diagram illustrating an internal configuration of an index encoding apparatus according to an embodiment of the present invention.

3, the index encoding apparatus 300 as a base station may include an index code determining unit 310, an optimum index code determining unit 320, and a transmission controlling unit 330. [ 2 may be performed by the index code determination unit 310, the optimal index code determination unit 320, and the transmission control unit 330 of FIG. 3.

2 and 3, as the memory storage information of each user terminal belonging to the base station changes with time, the index encoding device 300, which is a base station, transmits the memory storage information (MSI) of each user terminal to the network environment Can be considered.

In step 210, the index code determining unit 310 determines whether or not the index encoding is performed based on the memory storage information (MSI) of the user terminal, which is estimated by the base station, in the index code set including the index codes that can be decoded in the user terminal Can be determined. Here, the index code is a set of files XOR-operated to be transmitted at one time based on the request file and the memory storage information among a plurality of user terminals belonging to the base station, and each file corresponds one-to-one with file indexes to XOR, Can be represented as a set of user groups requiring the corresponding file index. That is, the index code may include at least one user group. For example, when the user A requests the file X _A and the user B requests the X _B , a total of 2 times (the files X _A and X _B respectively) must be transmitted in the existing transmission scheme. However, Is stored in the memory (when the user A has the file X _B in the memory and the user B has the file X _A in the memory), the base station stores the memory storage information MSI), and transferring only one file (X _A X _B ) obtained by XORing the file X _A and the file X _B , each user can decode the request file by utilizing the memory he owns. At this time, the file X _A and the file X _B can be regarded as one group ({A, B}) and can be regarded as one element constituting the index code.

In operation 220, the optimum index code determining unit 320 may select an index code different from the determined index code in the index code set. For example, any one of the index codes excluding the determined index code among the index codes included in the index code set can be selected.

In operation 230, the optimal index code determiner 320 may determine an optimal index code by comparing the determined index code with the selected other index code. For example, the optimal index code determining unit 320 may determine an optimal index code by comparing the sum of the success rate of the determined index code and the success rate of the selected other index code. At this time, the optimum index code determining unit 320 compares the sum of the success rate of each code with respect to all the index codes included in the index code set based on the Brute-Force algorithm, You can set the code. Finally, the optimum index code set finally through the comparison can be finally determined as the optimum index code.

In step 240, the transmission control unit 330 may transmit the requested file to the at least one user terminal corresponding to the determined optimal index code. For example, the transmission control unit 330 may multicast a request file to user terminals belonging to a user group corresponding to an optimal index code.

로 표현될 수 있다. 즉,

는 k번째 사용자 단말의 캐시 메모리에 저장하고 있을 것으로 추정되는 파일 인덱스들의 집합을 나타낼 수 있다. 그리고, 복호화가 가능한(decodable) 모든 인덱스 코드들을 포함하는 인덱스 코드 집합은

로 표현될 수 있다. 상기 인덱스 코드 집합은 주어진 메모리 저장 정보(MSI)

(1번째부터 k번째 사용자 단말의 파일 인덱스를 한번에 표기한 것)에 따라 아래의 수학식 5와 같이 표현될 수 있다. In step 210, the memory information (MSI) of the user terminal estimated by the base station is

. ≪ / RTI > In other words,

May represent a set of file indexes that are presumed to be stored in the cache memory of the kth user terminal. And, the index code set containing all the index codes that can be decodable is

. ≪ / RTI > The set of index codes includes a given memory storage information (MSI)

(The index of the file index of the kth user terminal from the first one), as shown in Equation (5) below.

&Quot; (5) "

에 기초하여 전송 가능한 인덱스 코드(즉, 전송 가능한 사용자 그룹)을 결정할 수 있다. The index encoding apparatus 300, which is a base station, calculates the memory storage information MSI of the user terminal,

(I.e., a group of users that can be transferred) based on the index code.

&Quot; (6) "

에 기초하여 K개의 타임 슬롯 별로 전송 가능한 인덱스 코드(즉, 전송 가능한 사용자 그룹)가 결정될 수 있다.That is, according to Equation (6), the memory storage information (MSI)

(I. E., A transmittable user group) can be determined for each K time slots.

Since the memory storage information of the user terminal varies with time, the memory storage information (MSI) estimated by the index encoding apparatus 300, which is a base station, may differ from the actual memory storage information, The correlation between the MSI and the actual memory storage information can be expressed by Equation (7) below.

&Quot; (7) "

The correlation expressed by Equation (7) may vary depending on the surrounding information of the base station and the user terminal (e.g., channel environment such as noise, fading, etc.), time, and the like. Accordingly, for the sake of clarity of the problem, the correlation represented by Equation (7) can be assumed as Equation (8) below.

&Quot; (8) "

According to Equation (8), when p is 1, the actual memory information and the estimated memory information may be the same. At this time, it can be assumed that each of the user terminals knows a value corresponding to the correlation. Then, the transmission control unit 330 can control the file transmission to the user terminals belonging to the user group determined based on the correlation.

의 사용자 그룹으로 인덱스 코드를 구성하여 전송하는 경우를 고려하면, 전송한 파일이 단위 파일로 크기가 1이라고 가정하면, i번째 그룹 내에 속하는 사용자 단말들 각각은 자신을 제외한 다른 사용자 단말들에 대해 명확한 메모리 저장 정보를 가지고 있는 경우에만 요구 파일을 제대로 수신할 수 있으므로,

만큼 수신할 수 있다. 이때, i번째 멀티캐스트 전송을 통해서 총

의 사용자 그룹에 속하는 사용자 단말들이 한 번에 파일을 수신할 수 있으므로,

만큼 파일을 수신하게 되고, 모든 사용자 그룹에 대해 합하게 되면 전송량의 총합은 아래의 수학식 9와 같을 수 있다.At the base station,

It is assumed that the transmitted file is a unit file having a size of 1, each of the user terminals belonging to the i-th group has a clear Since the request file can be received correctly only when it has memory storage information,

As shown in FIG. At this time, i

The user terminals belonging to the user group of the user terminal can receive the file at one time,

The sum of the transmission amounts may be expressed by Equation (9) below. &Quot; (9) "

&Quot; (9) "

에 대한 크기(cardinality) 함수를 아래의 수학식 10과 같이 표현할 수 있다. At this time, in order to express the case where the user group is not an empty set,

The cardinality function for the cardinality can be expressed as Equation 10 below.

&Quot; (10) "

는 ()안의 값이 맞으면 1, 틀리면 0을 나타내는 함수에 해당할 수 있다. 이에 따라, 단위 시간당 전송 횟수는 아래의 수학식 11과 같이 표현될 수 있다.Here,

Can be a function representing 1 if the value in parentheses is correct, and 0 if it is wrong. Accordingly, the number of transmissions per unit time can be expressed by Equation (11) below.

&Quot; (11) "

If the base station does not know exactly the memory storage information (MSI) of each user terminal (i.e., if it uses incorrect memory storage information estimated by the base station), the optimal user groups (I. E., The index code) can be expressed as < EMI ID = 12.0 >

&Quot; (12) "

In the above equation (12), when the memory fixing information MSI is fixed, if the correlation is low (that is, if p in the above equation (7) is lower than the first reference value) Since a file corresponding to a specific user terminal is mixed with a file corresponding to another user terminal, a specific user terminal can not properly receive a request file requested by the user terminal, and performance may be degraded. Accordingly, when the correlation is lower than the first reference value, the index encoding device 300, which is a base station, can transmit the file by changing the index code. Here, changing the index code may indicate that not only the user group but also the transmission scheme is changed.

That is, one index code includes a plurality of user groups, and each user group may be transmitted in multicast or unicast according to the size of the group. Accordingly, one index code includes a combination of multicast and unicast transmission. When the index code is changed, the user group is changed and the transmission mode can be changed in a manner corresponding to the changed user group. In this case, all the UEs are multicasted into one group, which is the best situation, and each user terminal is in a different group, so that it is the worst case to perform each unicast transmission .

For example, when there are six user terminals and each user terminal is expressed as {1,2,3,4,5,6}, {1,2,3}, {4,5}, and {6} It can be expressed as being included in the index code. That is, the index code can support all user terminals in three transmissions. For example, user group {1,2,3} and user group {4,5} can be transmitted in multicast, and user group {6} can be supported in unicast transmission.

In this case, considering the correlation, the algorithm for solving the problem of changing the index code and transmitting the file may be as shown in Table 1 below.

The algorithm for determining (i.e., searching) the index code shown in Table 1 corresponds to an algorithm for determining the optimal index code for all the index codes included in the index code set based on the brute-force algorithm can do.

According to Table 1, the index code determining unit 310 can select any one of the decodable index codes included in the index code set based on the MSI information of the user terminal estimated by the base station.

Then, the optimum index code determining unit 320 can select any one of the index codes excluding the selected index code among the index codes capable of decoding included in the index code set. That is, the optimum index code determining unit 320 can select an index code different from the selected index code in the index code set.

For example, referring to FIG. 4, the network environment shown in FIG. 4 includes four user terminals, one request file and one user terminal storing information in memory (i.e., MSI is determined) It can indicate the situation. At this time, there are various types of index codes that can be decoded. For example, when two of the numbers are used, ({1,2,3}, {4}), { }, {3}, {4}. At this time, in the case of ({1,2}, {3,4}), since the user terminal 3 does not have F [4], it may not belong to a decodable index code. In this way, one of all possible index codes can be selected.

Then, the optimum index code determining unit 320 may compare the sum of the successive transmission amounts of the selected index code and the other index codes. For example, the optimum index code determining unit 320 may calculate the sum of the succeeding transmission amounts of the index codes based on Equation (9) above, and calculate the sum of the succeeding transmission amounts of the other index codes. Then, the calculated totals can be compared.

Then, the optimum index code determiner 320 may set an index code having a larger total sum of the success transmission amounts as the optimal index code through the comparison. As described above, the optimum index code determining unit 320 calculates the sum of the transmission amounts of the index codes, and compares the calculated sum with the sum of the success transmission amounts of the optimal index codes, You can do this with code. Then, by repeating the operation of comparing the sum with all decodable index codes, the optimal index code can be updated with an index code having the sum of the relatively larger success transmission amount. For example, in a state where the index code 1 is set to the optimum index code, when the sum of the success transmission amounts of the index code 3 is larger than the sum of the success transmission amounts of the index code 1 set to the optimum index code, the optimum index code is set to the index code 3 Updated / changed. Then, when the operation of comparing the sum with all decodable index codes is performed, the last set index code with the optimum index code can be finally determined as the optimum index code.

FIG. 4 is a diagram illustrating memory storage information in the case where there are four user terminals belonging to a base station in an embodiment of the present invention. FIG. 5 is a diagram illustrating performance of the correlation p according to an embodiment of the present invention. FIG.

The network environment shown in FIG. 4 includes a file 1 401, a file 2 402, a file 3 403, and a file 340 in each of the user terminals 410, 420, 430, and 440 belonging to the index- 4 404 in the downlink.

)이 저장되어 있고, 사용자 단말 2(420)의 캐시 메모리에는 파일 1 및 파일 3(

)이 저장되어 있고, 사용자 단말 3(430)의 캐시 메모리에는 파일 1 및 파일 2(

)가 저장되어 있고, 사용자 단말 4(440)의 캐시 메모리에는 파일 2 및 파일 3(

)이 저장되어 있을 수 있다. 즉, 각 사용자 단말은 자신의 캐시 메모리에 저장되어 있지 않은 파일을 기지국(400)으로 요청할 수 있다. 이때, 사용자 단말들 각각의 메모리 저장 정보(MSI)와 기지국(400)에서 추정하고 있는(즉, 알고 있는) 각 사용자 단말의 메모리 저장 정보(MSI)가 상이할 수 있다. 예컨대, 기지국(400)은 사용자 단말 1(410)의 캐시 메모리에 파일 4 및 파일 3이 저장되고, 사용자 단말 2(420)의 캐시 메모리에 파일 2 및 파일 3이 저장되어 있는 것으로 알고 있을 수 있다. 이처럼, 기지국(400)이 추정하고 있는 메모리 저장 정보와 사용자 단말의 실제 저장 정보 간의 관련도를 나타내는 상관성(correlation, p)을 고려하여 상기 결정된 최적 인덱스 코드에 해당하는 사용자 단말들을 대상으로 요구 파일을 전송할 수 있다.At this time, in the cached memory of the user terminal 1 (410), file 2 and file 3

, And the cache memory of the user terminal 2 (420) stores the file 1 and the file 3 (

), And the cache memory of the user terminal 3 (430) stores file 1 and file 2

, And the cache memory of the user terminal 4 (440) stores the file 2 and the file 3 (

May be stored. That is, each user terminal can request a file not stored in its own cache memory to the base station 400. At this time, the memory storage information (MSI) of each user terminal may be different from the memory storage information (MSI) of each user terminal estimated by the base station 400 (that is, known). For example, the base station 400 may know that files 4 and 3 are stored in the cache memory of the user terminal 1 (410), and files 2 and 3 are stored in the cache memory of the user terminal 2 (420) . In this way, considering the correlation (p, p) indicating the degree of association between the memory storage information estimated by the base station 400 and the actual stored information of the user terminal, the request file for the user terminals corresponding to the determined optimal index code Lt; / RTI >

For example, when the correlation p is lower than a predefined first reference value, the transmission control unit 330 may transmit the request file unicast to user terminals corresponding to the optimal index code. That is, each user terminal belonging to the corresponding user group can separately transmit a file requested by each terminal. For example, referring to FIG. 5, it can be seen that in case of correlation (p) = 0, unicast transmission 510, which individually transmits the request file to each of the user terminals, is more efficient than multicast transmission.

의 개수가 많아지므로 최적 인덱스 코드를 결정(즉, 검색)하기 위한 계산 복잡도가 증가할 수 있다.As another example, when the correlation p is higher than a predetermined second reference value, the transmission control unit 330 may transmit the request file to the user terminals corresponding to the optimal index code by multicast. That is, the user terminals belonging to the user group can simultaneously transmit the requested file to the user terminals (the files requested by the user terminals may correspond to the same file). For example, referring to FIG. 5, it can be confirmed that the correlation (p) = 1 is optimal when there are two user groups. That is, based on the algorithm 1 of Table 1, it is possible to select either one of two user groups (1, 3) of size 1 and 3 and two user groups (2, 2) of size 2 and 2 have. As a result, the smaller the correlation, the higher the throughput than the multicast transmission, and the higher the correlation, the better the multicast transmission than the unicast. can confirm. At this time, as the number of user terminals increases,

The computational complexity for determining (i.e., searching) the optimal index code may increase.

In FIG. 5, values in () such as (1,3) and (2,2) may indicate the cardinality of each user group. That is, (1, 3) represents a case where the size of each user group is 1 and 3 when one index code is composed of two user groups, and (2, 1, 1) When three user groups are composed, the size of each user group is 2, 1, and 1, respectively. The values of () in FIG. 5 are matched with those of FIG. 4, and (1, 3) can correspond to decodable index codes ({4}, {1,2,3}) in FIG. In FIG. 5 (2, 2), there is no decodable index code in FIG. 4, and in the case of another MSI, it corresponds to the index codes ({1,2}, {3,4}). 5, (2, 1, 1) in FIG. 5 shows the index codes ({1,2}, {3}, {4}), ({1,2}, {3} (1, 1, 1, 1) in FIG. 5 correspond to the index codes ({1}, {2}, {3}, and {4}). have.

The method according to an embodiment may be implemented in the form of a program command that can be executed through various computer means and recorded in a computer-readable medium. The computer-readable medium may include program instructions, data files, data structures, and the like, alone or in combination. The program instructions to be recorded on the medium may be those specially designed and configured for the embodiments or may be available to those skilled in the art of computer software. Examples of computer-readable media include magnetic media such as hard disks, floppy disks and magnetic tape; optical media such as CD-ROMs and DVDs; magnetic media such as floppy disks; Magneto-optical media, and hardware devices specifically configured to store and execute program instructions such as ROM, RAM, flash memory, and the like. Examples of program instructions include machine language code such as those produced by a compiler, as well as high-level language code that can be executed by a computer using an interpreter or the like.

While the present invention has been particularly shown and described with reference to exemplary embodiments thereof, it is to be understood that the invention is not limited to the disclosed exemplary embodiments. For example, it is to be understood that the techniques described may be performed in a different order than the described methods, and / or that components of the described systems, structures, devices, circuits, Lt; / RTI > or equivalents, even if it is replaced or replaced.

Therefore, other implementations, other embodiments, and equivalents to the claims are also within the scope of the following claims.

Claims (16)

A method of performing index coding on a plurality of user terminals belonging to a base station in a network environment in which memory storage information of a user terminal changes with time,
Determining an index code to be used for index encoding based on memory storage information of a user terminal that the base station is estimating, in an index code set including index codes that are decodable;
Selecting an index code different from the index code determined in the index code set;
Comparing the determined index code with the selected other index code to determine an optimal index code; And
Transmitting a file requested by the corresponding terminal to at least one user terminal corresponding to the determined optimal index code
Lt; / RTI >
Wherein the index code indicates a group of users grouped based on a requested file among the plurality of user terminals
The index coding method comprising the steps of: The method according to claim 1,
Wherein the step of determining with the optimal index code comprises:
Comparing the determined index code with a successive transmission amount of the selected other index code;
Setting an index code having a larger total sum of success traffic through the comparison as the optimal index code; And
The sum of the successive transmission amounts of any one of the index codes selected for the index codes excluding the determined index code and the selected other index codes among all the index codes included in the index code set, And updating the optimal index code
/ RTI > 3. The method of claim 2,
The method of claim 1,
Transmitting a file to at least one user terminal corresponding to the updated optimal index code
The index coding method comprising the steps of: The method according to claim 1,
Wherein the step of determining with the optimal index code comprises:
Determining the optimal index code as an index code having a maximum sum of success transmission amounts based on a Brute-Force algorithm for all the index codes included in the index code set,
The index coding method comprising the steps of: The method according to claim 1,
The optimal index code is changed based on a correlation between memory storage information of the user terminal estimated by the base station and actual memory information of the corresponding user terminal
The index coding method comprising the steps of: 6. The method of claim 5,
The method of claim 1,
When the correlation is lower than a predefined first reference value, transmitting a file requested by the corresponding terminal to unicast for at least one user terminal corresponding to the optimal index code
/ RTI > 6. The method of claim 5,
The method of claim 1,
When the correlation is higher than a predefined second reference value, multicasting a file requested by the corresponding terminal to at least one user terminal corresponding to the optimal index code
/ RTI > 6. The method of claim 5,
The correlation may vary depending on the surrounding environment information and the time between the base station and the user terminal
The index coding method comprising the steps of: An apparatus for performing index coding on a plurality of user terminals in a network environment in which memory storage information of a user terminal varies with time,
An index code determining unit for determining an index code to be used for index encoding based on memory storage information of a user terminal estimated by the index encoding apparatus, in an index code set including index codes capable of being decoded;
An optimal index code determining unit for selecting an index code different from the index code determined in the set of index codes and comparing the determined index code with the selected another index code to determine an optimum index code; And
A transmission controller for transmitting a file requested by the corresponding terminal to at least one user terminal corresponding to the determined optimal index code,
Lt; / RTI >
Wherein the index code indicates a group of users grouped based on a requested file among the plurality of user terminals
And an index encoding unit for decoding the encoded data. 10. The method of claim 9,
Wherein the optimal index code determination unit comprises:
Comparing the sum of the successive transmission quantities of the determined index codes with the successive transmission amounts of the selected other index codes, setting an index code having a larger sum of success transmission amounts as the optimal index code, The optimum index code is updated by comparing the sum of the successive transmission amounts of any one of the index codes selected for the index codes excluding the determined index code and the selected other index codes and the success transmission amount of the set optimal index code that
And an index encoding unit for decoding the encoded data. 11. The method of claim 10,
The transmission control unit,
Transmitting a file to at least one user terminal corresponding to the updated optimal index code
And an index encoding unit for decoding the encoded data. 10. The method of claim 9,
Wherein the optimal index code determination unit comprises:
Determining the optimal index code as an index code having a maximum sum of success transmission amounts based on a Brute-Force algorithm for all the index codes included in the index code set,
And an index encoding unit for decoding the encoded data. 10. The method of claim 9,
The optimal index code is changed based on a correlation between memory storage information of the user terminal estimated by the index encoding device and actual memory information of the corresponding user terminal
And an index encoding unit for decoding the encoded data. 14. The method of claim 13,
The transmission control unit,
When the correlation is lower than a predefined first reference value, transmitting a file requested by the corresponding terminal to unicast for at least one user terminal corresponding to the optimal index code
And an index encoding unit for decoding the encoded data. 14. The method of claim 13,
The transmission control unit,
When the correlation is higher than a predetermined second reference value, multicast transmission of a file requested by the corresponding terminal to at least one user terminal corresponding to the optimal index code
And an index encoding unit for decoding the encoded data. 14. The method of claim 13,
The correlation may vary depending on the surrounding environment information between the index encoding apparatus and the user terminal and the time
And an index encoding unit for decoding the encoded data.

Images