[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

KR20190065803A - 사용자 단말의 메모리 저장 정보가 제한된 환경에서의 인덱스 부호화 방법 및 장치, 그리고 무선 통신 방법 - Google Patents

사용자 단말의 메모리 저장 정보가 제한된 환경에서의 인덱스 부호화 방법 및 장치, 그리고 무선 통신 방법 Download PDF

Info

Publication number
KR20190065803A
KR20190065803A KR1020170165330A KR20170165330A KR20190065803A KR 20190065803 A KR20190065803 A KR 20190065803A KR 1020170165330 A KR1020170165330 A KR 1020170165330A KR 20170165330 A KR20170165330 A KR 20170165330A KR 20190065803 A KR20190065803 A KR 20190065803A
Authority
KR
South Korea
Prior art keywords
index
index code
code
user terminal
optimal
Prior art date
Application number
KR1020170165330A
Other languages
English (en)
Other versions
KR102043510B1 (ko
Inventor
최완
손경락
이정훈
Original Assignee
한국과학기술원
Priority date (The priority date 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 date listed.)
Filing date
Publication date
Application filed by 한국과학기술원 filed Critical 한국과학기술원
Priority to KR1020170165330A priority Critical patent/KR102043510B1/ko
Publication of KR20190065803A publication Critical patent/KR20190065803A/ko
Application granted granted Critical
Publication of KR102043510B1 publication Critical patent/KR102043510B1/ko

Links

Images

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L1/00—Arrangements for detecting or preventing errors in the information received
    • H04L1/0001—Systems modifying transmission characteristics according to link quality, e.g. power backoff
    • H04L1/0015—Systems modifying transmission characteristics according to link quality, e.g. power backoff characterised by the adaptation strategy
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L12/00—Data switching networks
    • H04L12/02—Details
    • H04L12/16—Arrangements for providing special services to substations
    • H04L12/18—Arrangements for providing special services to substations for broadcast or conference, e.g. multicast
    • H04L12/185—Arrangements for providing special services to substations for broadcast or conference, e.g. multicast with management of multicast group membership
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L49/00—Packet switching elements
    • H04L49/90—Buffering arrangements
    • H04L49/9063—Intermediate storage in different physical parts of a node or terminal
    • H04L49/9078—Intermediate storage in different physical parts of a node or terminal using an external memory or storage device

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Quality & Reliability (AREA)
  • Mobile Radio Communication Systems (AREA)

Abstract

사용자 단말의 메모리 저장 정보가 제한된 환경에서의 인덱스 부호화 방법 및 장치, 그리고 무선 통신 방법이 개시된다. 사용자 단말의 메모리 저장 정보가 시간에 따라 변화하는 네트워크 환경에서, 기지국에 속하는 복수의 사용자 단말들을 대상으로 인덱스 부호화(index coding) 하는 방법에 있어서, 복호화가 가능한(decodable) 인덱스 코드들을 포함하는 인덱스 코드 집합에서, 상기 기지국이 추정하고 있는 사용자 단말의 메모리 저장 정보에 기초하여 인덱스 부호화에 이용될 인덱스 코드를 결정하는 단계, 상기 인덱스 코드 집합에서 결정된 상기 인덱스 코드와는 다른 인덱스 코드를 선택하는 단계, 결정된 상기 인덱스 코드와 선택된 상기 다른 인덱스 코드를 비교하여 최적 인덱스 코드를 결정하는 단계, 및 결정된 상기 최적 인덱스 코드에 해당하는 적어도 하나의 사용자 단말을 대상으로 해당 단말에서 요청한 파일을 전송하는 단계를 포함하고, 상기 인덱스 코드는, 상기 복수의 사용자 단말들 중 요청된 파일에 기초하여 그룹화된 사용자 그룹을 나타낼 수 있다.

Description

사용자 단말의 메모리 저장 정보가 제한된 환경에서의 인덱스 부호화 방법 및 장치, 그리고 무선 통신 방법{METHOD AND APPARATUS FOR CODING INDEX IN USER EQUIPMENT WITH LIMITED MEMORI STATE INFORMATION AND WIRELESS COMMUNICATION METHOD}
본 발명은 기지국이 사용자 단말의 메모리 저장 정보(Memory State Information, MSI)를 정확히 알지 못하는 네트워크 환경에서 인덱스 부호화에 기반한 멀티캐스트 전송을 제공하는 기술에 관한 것이다.
무선 데이터 트래픽은 최근 몇 년 동안, 텍스트, 음성 메시지, 비디오 스트리밍 등으로 인해 폭발적으로 증가하고 있다. 이러한 증가 추세는 가상현실, 증강현실, 홀로그램 등과 같은 서비스로 인해 더욱더 커질 것으로 예상되고 있다. 무선 데이터 트래픽은 유명 컨텐츠에 대한 선호도, 예측 가능한 수요와 같은 독특한 특성을 가지고 있지만, 현재의 무선 통신 시스템은 상기 독특한 특성을 반영하지 않은 채 추가적인 무선 통신 자원을 통해 효율을 높여 왔다. 하지만 무선 통신 자원들을 활용하는 방법은 어느 정도 한계에 이르렀으며 새로운 기술이 필요한 상황이다. 새로운 기술 중 하나로서, 네트워크의 사용자가 메모리에 일부 비디오 데이터를 저장하는 캐싱(caching)이 등장하였다.
캐싱(caching)은 전체 네트워크 트래픽을 상당히 줄일 수 있는 것으로 알려져 있다. 기존의 캐싱 알고리즘들은 캐시 메모리(cache memory)를 활용하여 사용자(즉, 사용자가 소지한 사용자 단말)들이 동일한 데이터를 받는 상황에서 요청한 데이터를 멀티캐스트(Multicast)로 처리한다. 그러나, 사용자가 서로 다른 데이터를 요구할 경우, 유니캐스트(Unicast) 방식으로 하나씩 해결할 수밖에 없다.
아래의 비특허 문헌 [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. US9535837 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에서는 사용자들이 서로 다른 데이터를 요구할 경우에도 효과적으로 전송 시간을 줄일 수 있는 새로운 캐싱 알고리즘을 개시하고 있다. 즉, 인덱스 부호화(Index coding)를 활용한 멀티캐스트를 통해 여러 사용자의 데이터를 합쳐서 전송할 수 있어 전송 시간을 크게 줄이고 있다. 아래의 비특허 문헌 [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.에서는 무선 채널 페이딩, 상호 간섭 등의 무선 채널 특성이 반영된 네트워크 환경에서 사용자의 저장 정보를 활용한 인덱스 부호화 기반 전송 기법을 제시하고 있다.
그러나, 기존의 캐싱 방법은 모두 기지국이 사용자 단말의 모든 메모리 상태(즉, 메모리 저장 정보)를 알고 있는 비현실적인 상황을 가정하였다. 즉, 기지국이 사용자 단말의 캐시 메모리에 저장하고 있는 콘텐츠(즉, 메모리 저장 정보, MSI)를 정확히 알고 있음을 가정한다.
그러나, 사용자의 요청 파일, 사용자의 메모리 저장 정보는 시시각각 변화기 때문에 실제로 기지국은 메모리 저장 정보를 정확히 알 수 없는 경우가 현실적이다. 이처럼, 실제 환경과 같이, 기지국에서 단말의 메모리 저장 정보를 정확히 알지 못하는 경우, 인덱스 부호화를 활용한 멀티캐스트 전송 시 오류가 발생하게 된다.
이에 따라, 파일의 길이에 관계없이 사용자의 요구 파일이 정확하지 않은 경우에도 최적의 성능을 얻을 수 있는 인덱스 부호화 전송 기술이 요구된다. 즉, 시간에 따라 단말의 메모리 저장 정보가 변화하는 네트워크 환경에서, 기지국이 단말의 메모리 저장 정보를 정확히 모르더라도 최적의 성능을 얻을 수 있는 인덱스 부호화 전송 기술이 요구된다.
한국공개특허 제10-2010-00048130호는 클러스터 기반의 분산형 스토리지 시스템 및 동작 방법에 관한 것으로, 캐시에 데이터를 분산 저장한 후 클러스터로 멀티캐스팅하는 기술을 기재하고 있다.
[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. US9535837 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.
본 발명은 기지국에 속하는 사용자 단말의 요구 파일 및 메모리 저장 정보(Memory state information, MSI)가 시간에 따라 변화하는 네트워크 환경에서, 기지국이 사용자 단말의 메모리 저장 정보를 정확히 알지 못하는 경우에도 파일을 멀티캐스트 전송하기 위한 최적의 인덱스 부호화를 수행하는 기술에 관한 것이다. 즉, 부정확한 메모리 저장 정보(즉, 기지국이 추정한 단말의 메모리 저장 정보)를 이용하여 각 사용자 단말의 성공적인 전송량의 총합을 최대화하는 최적의 사용자 그룹을 결정하고자 한다.
사용자 단말의 메모리 저장 정보가 시간에 따라 변화하는 네트워크 환경에서, 기지국에 속하는 복수의 사용자 단말들을 대상으로 인덱스 부호화(index coding) 하는 방법에 있어서, 복호화가 가능한(decodable) 인덱스 코드들을 포함하는 인덱스 코드 집합에서, 상기 기지국이 추정하고 있는 사용자 단말의 메모리 저장 정보에 기초하여 인덱스 부호화에 이용될 인덱스 코드를 결정하는 단계, 상기 인덱스 코드 집합에서 결정된 상기 인덱스 코드와는 다른 인덱스 코드를 선택하는 단계, 결정된 상기 인덱스 코드와 선택된 상기 다른 인덱스 코드를 비교하여 최적 인덱스 코드를 결정하는 단계, 및 결정된 상기 최적 인덱스 코드에 해당하는 적어도 하나의 사용자 단말을 대상으로 해당 단말에서 요청한 파일을 전송하는 단계를 포함하고, 상기 인덱스 코드는, 상기 복수의 사용자 단말들 중 요청된 파일에 기초하여 그룹화된 사용자 그룹을 나타낼 수 있다.
일측면에 따르면, 상기 최적 인덱스 코드로 결정하는 단계는, 상기 결정된 인덱스 코드와 상기 선택된 다른 인덱스 코드의 성공 전송량의 총합을 비교하는 단계, 상기 비교를 통해 성공 전송량의 총합이 큰 인덱스 코드를 상기 최적 인덱스코드로 설정하는 단계, 및 상기 인덱스 코드 집합에 포함된 모든 인덱스 코드들 중 상기 결정된 인덱스 코드와 상기 선택된 다른 인덱스 코드를 제외한 인덱스 코드들을 대상으로 선택된 어느 하나의 인덱스 코드의 성공 전송량의 총합과 설정된 최적 인덱스 코드의 성공 전송량의 총합을 비교하여 상기 최적 인덱스 코드를 갱신하는 단계를 포함할 수 있다.
다른 측면에 따르면, 상기 파일을 전송하는 단계는, 갱신된 상기 최적 인덱스 코드에 해당하는 적어도 하나의 사용자 단말을 대상으로 파일을 전송할 수 있다.
또 다른 측면에 따르면, 상기 최적 인덱스 코드로 결정하는 단계는, 상기 인덱스 코드 집합에 포함된 모든 인덱스 코드들을 대상으로, 브루트-포스(Brute-Force) 알고리즘에 기초하여 성공 전송량의 총합이 최대인 인덱스 코드를 상기 최적 인덱스 코드를 결정할 수 있다.
또 다른 측면에 따르면, 상기 최적 인덱스 코드는, 상기 기지국이 추정하고 있는 사용자 단말의 메모리 저장 정보와 해당 사용자 단말의 실제 메모리 정보 간의 상관성(correlation)에 기초하여 변경될 수 있다.
또 다른 측면에 따르면, 상기 파일을 전송하는 단계는, 상기 상관성이 미리 정의된 제1 기준값 이하로 낮은 경우, 상기 최적 인덱스 코드에 해당하는 적어도 하나의 사용자 단말을 대상으로, 해당 단말에서 요청한 파일을 유니캐스트(unicast)로 전송하는 단계를 포함할 수 있다.
또 다른 측면에 따르면, 상기 파일을 전송하는 단계는, 상기 상관성이 미리 정의된 제2 기준값 이상으로 높은 경우, 상기 최적 인덱스 코드에 해당하는 적어도 하나의 사용자 단말을 대상으로, 해당 단말에서 요청한 파일을 멀티캐스트(multicast)로 전송하는 단계를 포함할 수 있다.
또 다른 측면에 따르면, 상기 상관성은 상기 기지국과 사용자 단말 간의 주변 환경 정보 및 시간에 따라 변화할 수 있다.
사용자 단말의 메모리 저장 정보가 시간에 따라 변화하는 네트워크 환경에서, 복수의 사용자 단말들을 대상으로 인덱스 부호화(index coding)하는 장치에 있어서, 복호화가 가능한(decodable) 인덱스 코드들을 포함하는 인덱스 코드 집합에서, 인덱스 부호화 장치가 추정하고 있는 사용자 단말의 메모리 저장 정보에 기초하여 인덱스 부호화에 이용될 인덱스 코드를 결정하는 인덱스 코드 결정부, 상기 인덱스 코드 집합에서 결정된 상기 인덱스 코드와는 다른 인덱스 코드를 선택하고, 결정된 상기 인덱스 코드와 선택된 상기 다른 인덱스 코드를 비교하여 최적 인덱스 코드를 결정하는 최적 인덱스 코드 결정부, 및 결정된 상기 최적 인덱스 코드에 해당하는 적어도 하나의 사용자 단말을 대상으로 해당 단말에서 요청한 파일을 전송하는 전송 제어부를 포함하고, 상기 인덱스 코드는, 상기 복수의 사용자 단말들 중 요청된 파일에 기초하여 그룹화된 사용자 그룹을 나타낼 수 있다.
일측면에 따르면, 상기 최적 인덱스 코드 결정부는, 상기 결정된 인덱스 코드와 상기 선택된 다른 인덱스 코드의 성공 전송량의 총합을 비교하고, 상기 비교를 통해 성공 전송량의 총합이 큰 인덱스 코드를 상기 최적 인덱스코드로 설정하고, 상기 인덱스 코드 집합에 포함된 모든 인덱스 코드들 중 상기 결정된 인덱스 코드와 상기 선택된 다른 인덱스 코드를 제외한 인덱스 코드들을 대상으로 선택된 어느 하나의 인덱스 코드의 성공 전송량의 총합과 설정된 최적 인덱스 코드의 성공 전송량의 총합을 비교하여 상기 최적 인덱스 코드를 갱신할 수 있다.
다른 측면에 따르면, 상기 전송 제어부는, 갱신된 상기 최적 인덱스 코드에 해당하는 적어도 하나의 사용자 단말을 대상으로 파일을 전송할 수 있다.
또 다른 측면에 따르면, 상기 최적 인덱스 코드 결정부는, 상기 인덱스 코드 집합에 포함된 모든 인덱스 코드들을 대상으로, 브루트-포스(Brute-Force) 알고리즘에 기초하여 성공 전송량의 총합이 최대인 인덱스 코드를 상기 최적 인덱스 코드를 결정할 수 있다.
또 다른 측면에 따르면, 상기 최적 인덱스 코드는, 상기 인덱스 부호화 장치가 추정하고 있는 사용자 단말의 메모리 저장 정보와 해당 사용자 단말의 실제 메모리 정보 간의 상관성(correlation)에 기초하여 변경될 수 있다.
또 다른 측면에 따르면, 상기 전송 제어부는, 상기 상관성이 미리 정의된 제1 기준값 이하로 낮은 경우, 상기 최적 인덱스 코드에 해당하는 적어도 하나의 사용자 단말을 대상으로, 해당 단말에서 요청한 파일을 유니캐스트(unicast)로 전송할 수 있다.
또 다른 측면에 따르면, 상기 전송 제어부는, 상기 상관성이 미리 정의된 제2 기준값 이상으로 높은 경우, 상기 최적 인덱스 코드에 해당하는 적어도 하나의 사용자 단말을 대상으로, 해당 단말에서 요청한 파일을 멀티캐스트(multicast)로 전송할 수 있다.
또 다른 측면에 따르면, 상기 상관성은 상기 기지국과 사용자 단말 간의 주변 환경 정보 및 시간에 따라 변화할 수 있다.
본 발명의 실시예들에 따르면, 기지국이 추정한 사용자 단말의 메모리 저장 정보와 실제 사용자 단말의 메모리 저장 정보 간의 상관성(correlation)을 기반으로 인덱스 코드(index code)를 결정하고, 결정된 인덱스 코드에 해당하는 사용자 그룹을 대상으로 파일을 멀티캐스트 전송함으로써,각 사용자 단말의 성공 전송량의 총합을 최대화할 수 있다.
도 1은 본 발명의 일실시예에 있어서, 기지국에서 사용자 단말의 메모리 저장 정보를 정확히 알지 못하는 경우에 다운링크 모델을 도시한 도면이다.
도 2는 본 발명의 일시예에 있어서, 인덱스 부호화 방법을 도시한 흐름도이다.
도 3은 본 발명의 일실시예에 있어서, 인덱스 부호화 장치의 내부 구성을 도시한 블록도이다.
도 4는 본 발명의 일실시예에 있어서, 기지국에 속하는 사용자 단말이 4개인 경우의 메모리 저장 정보를 나타낸 도면이다.
도 5는 본 발명의 일실시예에 있어서, 상관성(p)에 따른 성능을 도시한 그래프이다.
이하, 본 발명의 실시 예를 첨부된 도면을 참조하여 상세하게 설명한다.
본 발명은 기지국에 속하는 사용자 단말의 캐시 메모리에 파일 또는 파일의 일부를 저장해두었다가 사용자 단말의 요청 시, 사용자 단말의 캐시 메모리에 저장된 파일을 기반으로 요청 파일을 제공하는 캐싱 기술에서, 기지국이 사용자 단말의 메모리 저장 정보를 정확히 알지 못하는 경우에 멀티캐스트 전송 시 오류를 최소화하는(즉, 성공적인 전송률을 최대화/높이는) 인덱스 부호화 전송 기술에 관한 것이다.
본 실시예들에서, 인덱스 부호화 장치는 기지국(Base Station)을 나타내고, 사용자 단말(User Equipment)는 기지국에 해당하는 셀(cell) 내에 위치하는 것으로서, 기지국에 속하는 사용자 단말은, 스마트폰, 태블릿 PC, 노트북 등을 포함할 수 있다. 이외에, 사용자 단말은 기지국과 사용자 단말 간의 중계 역할을 하는 게이트웨이 등의 중계 장치를 포함할 수도 있으며, 각 사용자 단말은 캐시(cache) 메모리를 구비할 수 있다. 이때, 캐시 메모리의 크기는 제한될 수 있으며, 캐시 메모리는 기지국에 저장된 복수의 파일들 중 적어도 하나의 파일 또는 파일의 일부인 파일 조각(즉, 패킷)을 저장하고 있을 수 잇다. 예컨대, 사용자 단말에서 요청하는 하나의 파일 전체의 크기보다 작도록 제한될 수 있다.
본 실시예들에서, "메모리 저장 정보(Memory State Information, MSI)"는 사용자 단말의 메모리 상태를 나타내는 것으로서, 사용자 단말의 캐시 메모리에 저장하고 있는 콘텐츠(즉, 파일, 파일 조각) 정보를 나타낼 수 있다. 예를 들어, 사용자 단말 1의 캐시 메모리에 파일 1의 첫 번째 파일 조각 및 파일 4의 두 번째 파일 조각이 저장되어 있는 경우, 사용자 단말 1의 메모리 저장 정보는 파일 1의 파일 조각 1, 파일 4의 파일 조각 2를 포함할 수 있다. 이에 따라, 사용자 단말 1에서 요청한 파일(즉, 요구 파일)을 기지국 및 다른 사용자 단말들, 또는 적어도 하나로부터 수신함에 따라, 캐시 메모리에 저장된 파일이 시간에 따라 누적 저장되어, 사용자 단말 1의 메모리 저장 정보는 시간에 따라 변화할 수 있으며, 본 발명은 메모리 저장 정보가 변화하더라도 최적의 성능을 얻을 수 있는 인덱스 부호화 전송 기술을 제공하고자 한다.
도 1은 본 발명의 일실시예에 있어서, 기지국에서 사용자 단말의 메모리 저장 정보를 정확히 알지 못하는 경우에 다운링크 모델을 도시한 도면이다.
도 1에서는 기지국에 속하는 사용자 단말이 3개인 경우를 도시하였으나, 이는 실시예에 해당되며, 사용자 단말의 개수는 3개 미만일 수도 있고, 3개보다 많을 수도 있다.
도 1에서, 기지국인 인덱스 부호화 장치(100)는 하나의 안테나를 가지며, 단일 안테나를 갖는 K개(예컨대, 3개)의 사용자 단말들(101, 102, 103)을 지원할 수 있다.
기지국인 인덱스 부호화 장치(100)는 N개의 파일을 라이브러리(Library)로 가지고 있을 수 있으며,
Figure pat00001
로 표현될 수 있다. 여기서, 각 파일의 크기
Figure pat00002
는 B bit일 수 있다.
Figure pat00003
는 k번째 사용자 단말에서 요청한 요구 파일을 나타내고,
Figure pat00004
는 k번째 사용자 단말의 캐시 메모리에 저장되어 있는 파일을 나타낼 수 있다. 이때, 사용자 단말들 각각은 자신의 캐시 메모리에 저장되어 있는 파일을 요청하지 않는 것을 가정한다(즉,
Figure pat00005
). 도 1 내지 도 5에서는 명확성을 위하여 채널과 잡음(noise)으로 인한 에러(error)가 없는 채널 환경(error-free)을 대상으로 인덱스 부호화하는 방법을 설명하나, 이는 실시예에 해당하며, 에러가 존재하는 채널 환경으로 인덱스 부호화를 확장할 수 있다.
다시 도 1을 참고하면, 기지국인 인덱스 부호화 장치(100)는 K개의 사용자 단말들(101, 102, 103)에게 총 K개의 시간대(time slot)을 사용하여 파일을 멀티캐스트로 전송할 수 있다. 이때, 총 사용자 단말의 수 K는 총 파일 개수인 N보다 작을 수 있다. 이처럼, 멀티캐스트로 전송 시, K개의 서로 다른 사용자 집합은
Figure pat00006
로 정의될 수 있으며,
Figure pat00007
는 i번째 시간대(즉, 타임 슬롯)에 서비스할 사용자들의 집합을 나타낼 수 있다. 이때, 상기 사용자 집합들은
Figure pat00008
과
Figure pat00009
을 만족해야 할 수 있다. 그리고, 사용자 인덱스를 받았을 때 해당 사용자의 그룹 인덱스를 나타내는 그룹 인덱스 지표(group index indicator)
Figure pat00010
는 아래의 수학식 1과 같이 표현될 수 있다.
[수학식 1]
Figure pat00011
수학식 1에서, 사용자 그룹이
Figure pat00012
(
Figure pat00013
로 표기)로 정의되어 있을 때, 인덱스 부호화 가정은 다음과 같을 수 있다. 기지국인 인덱스 부호화 장치(100)는 그룹
Figure pat00014
에 속해 있는 원소들을 인덱스로 가지는 파일들에 대해 배타적 논리합(exclusive or, XOR)을 수행하여 부호화된 파일을 생성할 수 있다. 그러면, n번째 파일에 해당하는 전송될 부호화된 파일
Figure pat00015
은 아래의 수학식 2와 같이 표현될 수 있다.
[수학식 2]
Figure pat00016
수학식 2에서,
Figure pat00017
는 0으로만 구성된 B 비트 파일을 나타내고,
Figure pat00018
는 XOR 연산자를 나타낼 수 있다.
기지국인 인덱스 부호화 장치(100)가 위의 수학식 2와 같이 표현된 파일
Figure pat00019
을 K개의 타임 슬롯에 걸쳐 전송한 경우, k번째 사용자 단말은
Figure pat00020
번째 시간대에 자신이 요청한 파일(즉, 요구 파일)을 수신할 수 있다. 이때, 아래의 수학식 3과 같이, 사용자 단말이
Figure pat00021
에 속한 원소들의 파일을 자신의 캐시 메모리에 저장하고 있는 경우, 해당 사용자 단말은 아래의 수학식 4에 기초하여 자신이 요청한 파일을 복원할 수 있다.
[수학식 3]
Figure pat00022
[수학식 4]
Figure pat00023
위의 수학식 1 내지 수학식 4와 같이 기지국이 전송한 파일, 기지국에 속하는 사용자 단말들의 캐시 메모리에 저장된 파일을 기반으로 특정 파일을 요청한 사용자 단말에서 자신이 요청한 파일(즉, 요구 파일)을 복원할 수 있는 시스템 환경에서, 요구 파일과 단말의 메모리 저장 정보(MSI)가 시간에 따라 변화하는 경우, 기지국은 기지국에서 추정한 메모리 저장 정보를 기반으로 인덱스 부호화를 수행할 수 있다.
이때, 기지국이 사용자 단말의 메모리 저장 정보를 명확히 알지 못하는 경우(즉, 부정확한 정보를 가지고 있는 경우), 추정된 메모리 저장 정보와 실제 메모리 저장 정보 간의 상관성(correlation)을 고려하여 인덱스 부호화를 수행함으로써, 최적의 성능(즉, 성공적인 전송률의 합을 최대화)을 얻을 수 있다. 즉, 도 1을 참고하면, 기지국(100)에 속하는 각 사용자 단말들(101, 102, 103)의 캐시 메모리에 저장된 파일과 기지국(100)이 알고 있는 각 사용자 단말들(101, 102, 103)의 캐시 메모리에 저장되어 있는 파일이 상이할 수 있다. 즉, 기지국(100)이 추정하고 있는 단말의 메모리 저장 정보(MSI)와 단말의 실제 메모리 저장 정보(MSI)가 다를 수 있다. 예컨대, 사용자 단말 1(101)의 캐시 메모리에는 파일 3 및 파일 7이 저장되어 있는데, 기지국(100)은 사용자 단말 1(101)의 메모리 저장 정보(MSI)를 파일 1 및 파일 4로 추정하고 있을 수 있다. 마찬가지로, 사용자 단말 2(102)의 실제 메모리 저장 정보(MSI)는 파일 1 및 파일 9를 포함하고 있는데, 기지국(100)은 사용자 단말 2(102)와 관련하여 MSI 정보가 파일 2 및 파일 4를 포함하고 있는 것으로 추정할 수 있다. 이러한 기지국(100)이 추정하고 있는 MSI 정보와 실제 MSI 정보 간의 상관성을 고려하여 인덱스 부호화를 수행함으로써, 최적의 성능을 얻을 수 있다. 이하에서는 도 2 내지 도 5를 참고하여, 상관성을 고려하여 인덱스 부호화를 하는 동작, 즉, 최적의 성능을 얻기 위한 인덱스 코드를 결정하고, 상관성을 고려하여 멀티캐스트(multicast) 또는 유니캐스트(unicast)로 전송하는 동작에 대해 설명하기로 한다.
도 2는 본 발명의 일시예에 있어서, 인덱스 부호화 방법을 도시한 흐름도이고, 도 3은 본 발명의 일실시예에 있어서, 인덱스 부호화 장치의 내부 구성을 도시한 블록도이다.
도 3을 참고하면, 기지국인 인덱스 부호화 장치(300)는 인덱스 코드 결정부(310), 최적 인덱스 코드 결정부(320), 및 전송 제어부(330)를 포함할 수 있다. 그리고, 도 2의 각 단계들(210 내지 240 단계)은 도 3의 인덱스 코드 결정부(310), 최적 인덱스 코드 결정부(320), 및 전송 제어부(330)에 의해 수행될 수 있다.
도 2 및 도 3에서, 기지국에 속하는 각 사용자 단말의 메모리 저장 정보는 시간에 따라 변화함에 따라, 기지국인 인덱스 부호화 장치(300)는 각 사용자 단말의 메모리 저장 정보(MSI)를 정확히 알지 못하는 네트워크 환경을 고려할 수 있다.
210 단계에서, 인덱스 코드 결정부(310)는 사용자 단말에서 복호화가 가능한(decodable) 인덱스 코드들을 포함하는 인덱스 코드 집합에서, 기지국이 추정하고 있는 사용자 단말의 메모리 저장 정보(MSI)에 기초하여 인덱스 부호화에 이용될 인덱스 코드를 결정할 수 있다. 여기서, 인덱스 코드는 기지국에 속하는 복수의 사용자 단말들 중 요구 파일과 메모리 저장 정보에 기초하여 한번에 전송하기 위해 XOR 연산된 파일들의 집합으로서, 각 파일은 XOR하는 파일 인덱스들과 일대일 대응이므로 상기 인덱스 코드는 해당 파일 인덱스를 요구하는 사용자 그룹의 집합으로 표현될 수 있다. 즉, 인덱스 코드는 적어도 하나의 사용자 그룹을 포함할 수 있다. 예컨대, 사용자 A가 파일 XA를 요구하고 사용자 B가 XB를 요구하는 경우, 기존의 전송 방식에서는 총 2번(파일 XA와 파일 XB를 각각) 전송하여야 하지만, 사용자가 서로의 요구 파일을 메모리에 저장하고 있는 경우(사용자 A가 파일 XB를 메모리에 갖고 있고, 사용자 B가 파일 XA를 메모리에 갖고 있는 경우), 기지국에서 각 사용자가 메모리에 파일을 저장하고 있는 메모리 저장 정보(MSI)를 파악하여 파일 XA와 파일 XB를 XOR 연산으로 부호화한 파일(XAXB) 하나만 전송하면 각 사용자에서는 각자 가지고 있는 메모리를 활용하여 요구 파일을 복호화할 수 있다. 이때 파일 XA와 파일 XB를 하나의 그룹({A, B})으로 볼 수 있으며 인덱스 코드를 구성하는 하나의 원소로 볼 수 있다.
220 단계에서, 최적 인덱스 코드 결정부(320)는 인덱스 코드 집합에서 상기 결정된 인덱스 코드와는 다른 인덱스 코드를 선택할 수 있다. 예컨대, 인덱스 코드 집합에 포함된 인덱스 코드들 중 상기 결정된 인덱스 코드를 제외한 인덱스 코드들 중에서 어느 하나의 인덱스 코드가 선택될 수 있다.
230 단계에서, 최적 인덱스 코드 결정부(320)는 결정된 인덱스 코드와 상기 선택된 다른 인덱스 코드를 비교하여 최적 인덱스 코드를 결정할 수 있다. 예를 들어, 최적 인덱스 코드 결정부(320)는 상기 결정된 인덱스 코드의 성공 전송률의 총합과 상기 선택된 다른 인덱스 코드의 성공 전송률의 총합을 비교하여 최적 인덱스 코드를 결정할 수 있다. 이때, 최적 인덱스 코드 결정부(320)는 브루트-포스(Brute-Force) 알고리즘에 기초하여, 인덱스 코드 집합에 포함된 모든 인덱스 코드들을 대상으로 각 코드 별 성공 전송률의 총합을 비교함으로써, 최적 인덱스 코드를 설정할 수 있다. 그리고, 비교를 통해 마지막으로 설정된 최적 인덱스 코드를 최종적으로 최적 인덱스 코드로 결정할 수 있다.
240 단계에서, 전송 제어부(330)는 결정된 최적 인덱스 코드에 해당하는 적어도 하나의 사용자 단말을 대상으로, 해당 단말에서 요청한 파일을 전송할 수 있다. 예컨대, 전송 제어부(330)는 최적 인덱스 코드에 해당하는 사용자 그룹에 속하는 사용자 단말들을 대상으로 요구 파일을 멀티캐스트 전송할 수 있다.
위의 210 단계에서, 기지국이 추정하고 있는 사용자 단말의 메모리 정보(MSI)는
Figure pat00024
로 표현될 수 있다. 즉,
Figure pat00025
는 k번째 사용자 단말의 캐시 메모리에 저장하고 있을 것으로 추정되는 파일 인덱스들의 집합을 나타낼 수 있다. 그리고, 복호화가 가능한(decodable) 모든 인덱스 코드들을 포함하는 인덱스 코드 집합은
Figure pat00026
로 표현될 수 있다. 상기 인덱스 코드 집합은 주어진 메모리 저장 정보(MSI)
Figure pat00027
(1번째부터 k번째 사용자 단말의 파일 인덱스를 한번에 표기한 것)에 따라 아래의 수학식 5와 같이 표현될 수 있다.
[수학식 5]
Figure pat00028
기지국인 인덱스 부호화 장치(300)는 아래의 수학식 6과 같이, 자신이 추정하고 있는 사용자 단말의 메모리 저장 정보(MSI)
Figure pat00029
에 기초하여 전송 가능한 인덱스 코드(즉, 전송 가능한 사용자 그룹)을 결정할 수 있다.
[수학식 6]
Figure pat00030
즉, 수학식 6에 따르면, 상기 추정하고 있는 사용자 단말의 메모리 저장 정보(MSI)
Figure pat00031
에 기초하여 K개의 타임 슬롯 별로 전송 가능한 인덱스 코드(즉, 전송 가능한 사용자 그룹)가 결정될 수 있다.
이때, 사용자 단말의 메모리 저장 정보는 시간에 따라 변화하므로, 기지국인 인덱스 부호화 장치(300)가 추정하고 있는 메모리 저장 정보(MSI)와 실제 메모리 저장 정보가 상이할 수 있으며, 상기 추정하고 있는 메모리 저장 정보(MSI)와 실제 메모리 저장 정보 간의 상관성(correlation)은 아래의 수학식 7과 같이 표현될 수 있다.
[수학식 7]
Figure pat00032
수학식 7과 같이 표현되는 상기 상관성은 기지국과 사용자 단말의 주변 환경 정보(예컨대, 잡음, 페이딩 등의 채널 환경), 시간 등에 따라 값이 달라질 수 있다. 이에 따라, 문제의 명확성을 위해 위의 수학식 7과 같이 표현되는 상관성을 아래의 수학식 8과 같이 가정할 수 있다.
[수학식 8]
Figure pat00033
수학식 8에 따르면, p가 1인 경우 실제 메모리 정보와 추정한 메모리 정보가 동일할 수 있다. 이때, 사용자 단말들 각각은 상기 상관성에 해당하는 값을 미리 알고 있음을 가정할 수 있다. 그러면, 전송 제어부(330)는 상관성을 기반으로 결정된 사용자 그룹에 속하는 사용자 단말들을 대상으로 파일 전송을 제어할 수 있다.
기지국에서,
Figure pat00034
의 사용자 그룹으로 인덱스 코드를 구성하여 전송하는 경우를 고려하면, 전송한 파일이 단위 파일로 크기가 1이라고 가정하면, i번째 그룹 내에 속하는 사용자 단말들 각각은 자신을 제외한 다른 사용자 단말들에 대해 명확한 메모리 저장 정보를 가지고 있는 경우에만 요구 파일을 제대로 수신할 수 있으므로,
Figure pat00035
만큼 수신할 수 있다. 이때, i번째 멀티캐스트 전송을 통해서 총
Figure pat00036
의 사용자 그룹에 속하는 사용자 단말들이 한 번에 파일을 수신할 수 있으므로,
Figure pat00037
만큼 파일을 수신하게 되고, 모든 사용자 그룹에 대해 합하게 되면 전송량의 총합은 아래의 수학식 9와 같을 수 있다.
[수학식 9]
Figure pat00038
이때, 사용자 그룹이 공집합이 아닌 경우를 표현하기 위해,
Figure pat00039
에 대한 크기(cardinality) 함수를 아래의 수학식 10과 같이 표현할 수 있다.
[수학식 10]
Figure pat00040
여기서, 함수
Figure pat00041
는 ()안의 값이 맞으면 1, 틀리면 0을 나타내는 함수에 해당할 수 있다. 이에 따라, 단위 시간당 전송 횟수는 아래의 수학식 11과 같이 표현될 수 있다.
[수학식 11]
Figure pat00042
기지국이 각 사용자 단말의 메모리 저장 정보(MSI)를 정확히 알지 못하는 경우(즉, 기지국이 추정한 부정확한 메모리 저장 정보를 이용하는 경우), 각 사용자 단말의 성공적인 전송량의 총합을 최대화하는 최적의 사용자 그룹들(즉, 인덱스 코드)을 결정하는 문제(P1)는 아래의 수학식 12와 같이 표현될 수 있다.
[수학식 12]
Figure pat00043
위의 수학식 12에서, 메모리 고정 정보(MSI)가 고정되어 있는 경우, 상관성(correlation)이 낮으면(즉, 위의 수학식 7의 p가 제1 기준값 이하로 낮으면), 멀티캐스트로 전송 시 특정 사용자 단말에 해당하는 파일과 다른 사용자 단말에 해당하는 파일이 섞여 있으므로, 특정 사용자 단말은 자신이 요청한 요구 파일을 제대로 수신하지 못하게 되어 성능 저하가 발생할 수 있다. 이에 따라, 기지국인 인덱스 부호화 장치(300)는 상관성이 제1 기준값 이하로 낮은 경우, 인덱스 코드를 변경하여 파일을 보낼 수 있다. 여기서, 인덱스 코드를 변경하는 것은 사용자 그룹뿐만 아니라 전송 방식도 변경하는 것을 나타낼 수 있다.
즉, 1개의 인덱스 코드는 여러 개의 사용자 그룹을 포함하며, 각 사용자 그룹은 해당 그룹의 크기에 따라 멀티캐스트로 전송될 수도 있고, 유니캐스트로 전송될 수도 있다. 이에 따라, 하나의 인덱스 코드는 멀티캐스트와 유니캐스트 전송이 복합되어 포함하고 있으며, 인덱스 코드가 변경되면 사용자 그룹이 변경되고, 변경된 사용자 그룹에 해당하는 방식으로 전송 방식이 변경될 수 있다. 그러면, 모든 사용자 단말들이 하나의 그룹으로 멀티캐스트되는 경우가 성능이 가장 좋은 상황에 해당하고, 각 사용자 단말들이 서로 다른 그룹으로 되어 있어 각각 유니캐스트 전송하는 경우가 가장 안 좋은 상황에 해당할 수 있다.
일례로, 사용자 단말이 6개이고, 각 사용자 단말들을 {1,2,3,4,5,6}으로 표현한 경우, {1,2,3}, {4,5}, {6}은 하나의 인덱스 코드에 포함되는 것으로 표현될 수 있다. 즉, 상기 인덱스 코드는 3번의 전송으로 모든 사용자 단말들을 지원할 수 있다. 예컨대, 사용자 그룹 {1,2,3}과 사용자 그룹 {4,5}는 멀티캐스트로 전송되고, 사용자 그룹{6}은 유니캐스트 전송으로 지원될 수 있다.
이때, 상관성을 고려하여 기지국에서 인덱스 코드를 변경하여 파일을 전송하는 문제를 해결하는 알고리즘은 아래의 표 1과 같을 수 있다.
Figure pat00044
표 1에 나타난 인덱스 코드를 결정(즉, 검색)하는 알고리즘은 브루트-포스(Brute-force) 알고리즘에 기초하여 인덱스 코드 집합에 포함된 모든 인덱스 코드들을 대상으로 최적 인덱스 코드를 결정하는 알고리즘에 해당할 수 있다.
표 1에 따르면, 인덱스 코드 결정부(310)는 기지국이 추정하고 있는 사용자 단말의 MSI 정보에 기초하여 인덱스 코드 집합에 포함된 복호화 가능한(decodable) 인덱스 코드 중 어느 하나를 선택할 수 있다.
그러면, 최적 인덱스 코드 결정부(320)는 인덱스 코드 집합에 포함된 복호화 가능한 인덱스 코드들 중 상기 선택된 인덱스 코드를 제외한 인덱스 코드들 중에서, 어느 하나를 선택할 수 있다. 즉, 최적 인덱스 코드 결정부(320)는 상기 인덱스 코드 집합에서 상기 선택된 인덱스 코드와는 다른 인덱스 코드를 선택할 수 있다.
일례로, 도 4를 참고하면, 도 4의 네트워크 환경은 사용자 단말의 개수가 4개이고, 요구 파일과 각 사용자 단말이 메모리에 저장하는 있는 정보가 나타나 있는(즉, MSI가 결정되어 있는) 하나의 상황을 나타낼 수 있다. 이때, 복호화 가능한 인덱스 코드는 여러가지 존재할 수 있는 데, 많은 경우의 수 중 2가지를 예로 들면, 복호화 가능한 인덱스 코드로서 ({1,2,3},{4}), ({1},{2},{3},{4})이 존재할 수 있다. 이때, ({1,2},{3,4})의 경우, 사용자 단말 3이 F[4]를 갖고 있지 않기 때문에 복호 가능한 인덱스 코드에 속하지 않을 수 있다. 이러한 방식으로, 가능한 모든 인덱스 부호 중에서 하나가 선택될 수 있다.
그리고, 최적 인덱스 코드 결정부(320)는 상기 선택된 인덱스 코드와 상기 다른 인덱스 코드의 성공 전송량의 총합을 비교할 수 있다. 예를 들어, 최적 인덱스 코드 결정부(320)는 위의 수학식 9에 기초하여 상기 인덱스 코드의 성공 전송량의 총합을 계산하고, 상기 다른 인덱스 코드의 성공 전송량의 총합을 계산할 수 있다. 그리고, 계산된 각 총합을 비교할 수 있다.
이어, 최적 인덱스 코드 결정부(320)는 상기 비교를 통해 둘 중에 성공 전송량의 총합이 큰 인덱스 코드를 최적 인덱스 코드로 설정할 수 있다. 이처럼, 최적 인덱스 코드 결정부(320)는 인덱스 코드의 전송량의 총합을 계산하고, 계산된 총합을 상기 설정된 최적 인덱스 코드의 성공 전송량의 총합과 비교하는 동작을 인덱스 코드 집합에 포함된 복호화 가능한 모든 인덱스 코드들을 대상으로 수행할 수 있다. 그리고, 모든 복호화 가능한 인덱스 코드들을 대상으로 상기 총합을 비교하는 동작을 반복함으로써, 둘 중 상대적으로 더 큰 성공 전송량의 총합을 가진 인덱스 코드로 상기 최적 인덱스 코드는 갱신될 수 있다. 예컨대, 인덱스 코드 1이 최적 인덱스 코드로 설정된 상태에서, 인덱스 코드 3의 성공 전송량의 총합이 최적 인덱스 코드로 설정된 인덱스 코드 1의 성공 전송량의 총합보다 큰 경우, 최적 인덱스 코드는 인덱스 코드 3으로 설정이 갱신/변경될 수 있다. 그러면, 모든 복호화 가능한 인덱스 코드들을 대상으로 상기 총합을 비교하는 동작을 수행한 경우, 최적 인덱스 코드로 마지막에 설정된 인덱스 코드가 최종적으로 최적 인덱스 코드로 결정될 수 있다.
도 4는 본 발명의 일실시예에 있어서, 기지국에 속하는 사용자 단말이 4개인 경우의 메모리 저장 정보를 나타낸 도면이고, 도 5는 본 발명의 일실시예에 있어서, 상관성(p)에 따른 성능을 도시한 그래프이다.
도 4의 네트워크 환경은 기지국인 인덱스 부호화 장치(400)에 속한 사용자 단말들(410, 420, 430, 440) 각각에서 파일 1(401), 파일 2(402), 파일 3(403), 및 파일 4(404)를 요청한 다운링크 모델을 나타낼 수 있다.
이때, 사용자 단말 1(410)의 캐시 메모리(cached memory)에는 파일 2 및 파일 3(
Figure pat00045
)이 저장되어 있고, 사용자 단말 2(420)의 캐시 메모리에는 파일 1 및 파일 3(
Figure pat00046
)이 저장되어 있고, 사용자 단말 3(430)의 캐시 메모리에는 파일 1 및 파일 2(
Figure pat00047
)가 저장되어 있고, 사용자 단말 4(440)의 캐시 메모리에는 파일 2 및 파일 3(
Figure pat00048
)이 저장되어 있을 수 있다. 즉, 각 사용자 단말은 자신의 캐시 메모리에 저장되어 있지 않은 파일을 기지국(400)으로 요청할 수 있다. 이때, 사용자 단말들 각각의 메모리 저장 정보(MSI)와 기지국(400)에서 추정하고 있는(즉, 알고 있는) 각 사용자 단말의 메모리 저장 정보(MSI)가 상이할 수 있다. 예컨대, 기지국(400)은 사용자 단말 1(410)의 캐시 메모리에 파일 4 및 파일 3이 저장되고, 사용자 단말 2(420)의 캐시 메모리에 파일 2 및 파일 3이 저장되어 있는 것으로 알고 있을 수 있다. 이처럼, 기지국(400)이 추정하고 있는 메모리 저장 정보와 사용자 단말의 실제 저장 정보 간의 관련도를 나타내는 상관성(correlation, p)을 고려하여 상기 결정된 최적 인덱스 코드에 해당하는 사용자 단말들을 대상으로 요구 파일을 전송할 수 있다.
일례로, 전송 제어부(330)는 상관성(p)이 미리 정의된 제1 기준값 이하로 낮은 경우, 최적 인덱스 코드에 해당하는 사용자 단말들을 대상으로, 요구 파일을 유니캐스트로 전송할 수 있다. 즉, 해당 사용자 그룹에 속하는 사용자 단말들 각각으로 각 단말에서 요청한 파일을 따로 전송할 수 있다. 예컨대, 도 5를 참고하면, 상관성(p)=0인 경우, 요구 파일을 사용자 단말들 각각으로 개별적으로 전송하는 유니캐스트 전송(510)이 멀티캐스트 전송보다 효율적임을 확인할 수 있다.
다른 예로, 전송 제어부(330)는 상관성(p)이 미리 정의된 제2 기준값 이상으로 높은 경우, 최적 인덱스 코드에 해당하는 사용자 단말들을 대상으로, 요구 파일을 멀티캐스트로 전송할 수 있다. 즉, 해당 사용자 그룹에 속하는 사용자 단말들이 요구한 파일을 동시에 사용자 단말들로 전송할 수 있다(이때, 사용자 단말들이 요구한 파일은 동일한 파일에 해당할 수 있다). 예컨대, 도 5를 참고하면, 상관성(p)=1인 경우, 사용자 그룹이 2개인 경우에 최적임을 확인할 수 있다. 즉, 표 1의 알고리즘 1에 기초하여 크기가 1과 3인 2개의 사용자 그룹 (1,3)과 크기가 2와 2인 2개의 사용자 그룹 (2,2) 중 어느 하나가 최적으로 선택될 수 있다. 결국, 상관성이 적을수록 유니캐스트로 전송하는 것이 멀티캐스트로 전송하는 것보다 상대적으로 성능(throughput)이 우수하고, 상관성이 높을수록 유니캐스트보다 멀티캐스트로 전송하는 것이 상대적으로 성능(throughput)이 우수함을 확인할 수 있다. 이때, 사용자 단말의 개수가 많아질수록,
Figure pat00049
의 개수가 많아지므로 최적 인덱스 코드를 결정(즉, 검색)하기 위한 계산 복잡도가 증가할 수 있다.
도 5에서, (1,3), (2,2)과 같이 ( )안의 값이 의미하는 것은 각 사용자 그룹의 크기(cardinality)를 나타낼 수 있다. 즉, (1,3)은 하나의 인덱스 코드가 2개의 사용자 그룹으로 구성되어 있을 때, 각 사용자 그룹의 크기가 1과 3인 경우를 나타내고, (2, 1, 1)은 하나의 인덱스 코드가 3개의 사용자 그룹으로 구성되어 있을 때 각 사용자 그룹의 크기가 각각 2, 1, 1인 경우를 나타낼 수 있다. 도 5의 ( )의 값을 도 4와 매칭하여 설명하면, (1,3)은 도 4의 복호화 가능한 인덱스 코드 ({4},{1,2,3})에 해당할 수 있다. 그리고, 도 5의 (2,2)는 도 4에서는 복호화 가능한 인덱스 코드가 없으며, 다른 MSI인 경우, 인덱스 코드 ({1,2},{3,4})에 해당할 수 있다. 도 5의 (2,1,1)는 인덱스 코드 ({1,2},{3},{4}), ({1,2},{3},{4}), ({1,3},{2},{4})에 해당하고, 도 5의 (1,1,1,1)는 인덱스 코드 ({1},{2},{3},{4})에 해당할 수 있다.
실시예에 따른 방법은 다양한 컴퓨터 수단을 통하여 수행될 수 있는 프로그램 명령 형태로 구현되어 컴퓨터 판독 가능 매체에 기록될 수 있다. 상기 컴퓨터 판독 가능 매체는 프로그램 명령, 데이터 파일, 데이터 구조 등을 단독으로 또는 조합하여 포함할 수 있다. 상기 매체에 기록되는 프로그램 명령은 실시예를 위하여 특별히 설계되고 구성된 것들이거나 컴퓨터 소프트웨어 당업자에게 공지되어 사용 가능한 것일 수도 있다. 컴퓨터 판독 가능 기록 매체의 예에는 하드 디스크, 플로피 디스크 및 자기 테이프와 같은 자기 매체(magnetic media), CD-ROM, DVD와 같은 광기록 매체(optical media), 플롭티컬 디스크(floptical disk)와 같은 자기-광 매체(magneto-optical media), 및 롬(ROM), 램(RAM), 플래시 메모리 등과 같은 프로그램 명령을 저장하고 수행하도록 특별히 구성된 하드웨어 장치가 포함된다. 프로그램 명령의 예에는 컴파일러에 의해 만들어지는 것과 같은 기계어 코드뿐만 아니라 인터프리터 등을 사용해서 컴퓨터에 의해서 실행될 수 있는 고급 언어 코드를 포함한다.
이상과 같이 실시예들이 비록 한정된 실시예와 도면에 의해 설명되었으나, 해당 기술분야에서 통상의 지식을 가진 자라면 상기의 기재로부터 다양한 수정 및 변형이 가능하다. 예를 들어, 설명된 기술들이 설명된 방법과 다른 순서로 수행되거나, 및/또는 설명된 시스템, 구조, 장치, 회로 등의 구성요소들이 설명된 방법과 다른 형태로 결합 또는 조합되거나, 다른 구성요소 또는 균등물에 의하여 대치되거나 치환되더라도 적절한 결과가 달성될 수 있다.
그러므로, 다른 구현들, 다른 실시예들 및 특허청구범위와 균등한 것들도 후술하는 특허청구범위의 범위에 속한다.

Claims (16)

  1. 사용자 단말의 메모리 저장 정보가 시간에 따라 변화하는 네트워크 환경에서, 기지국에 속하는 복수의 사용자 단말들을 대상으로 인덱스 부호화(index coding) 하는 방법에 있어서,
    복호화가 가능한(decodable) 인덱스 코드들을 포함하는 인덱스 코드 집합에서, 상기 기지국이 추정하고 있는 사용자 단말의 메모리 저장 정보에 기초하여 인덱스 부호화에 이용될 인덱스 코드를 결정하는 단계;
    상기 인덱스 코드 집합에서 결정된 상기 인덱스 코드와는 다른 인덱스 코드를 선택하는 단계;
    결정된 상기 인덱스 코드와 선택된 상기 다른 인덱스 코드를 비교하여 최적 인덱스 코드를 결정하는 단계; 및
    결정된 상기 최적 인덱스 코드에 해당하는 적어도 하나의 사용자 단말을 대상으로 해당 단말에서 요청한 파일을 전송하는 단계
    를 포함하고,
    상기 인덱스 코드는, 상기 복수의 사용자 단말들 중 요청된 파일에 기초하여 그룹화된 사용자 그룹을 나타내는 것
    을 특징으로 하는 인덱스 부호화 방법.
  2. 제1항에 있어서,
    상기 최적 인덱스 코드로 결정하는 단계는,
    상기 결정된 인덱스 코드와 상기 선택된 다른 인덱스 코드의 성공 전송량의 총합을 비교하는 단계;
    상기 비교를 통해 성공 전송량의 총합이 큰 인덱스 코드를 상기 최적 인덱스코드로 설정하는 단계; 및
    상기 인덱스 코드 집합에 포함된 모든 인덱스 코드들 중 상기 결정된 인덱스 코드와 상기 선택된 다른 인덱스 코드를 제외한 인덱스 코드들을 대상으로 선택된 어느 하나의 인덱스 코드의 성공 전송량의 총합과 설정된 최적 인덱스 코드의 성공 전송량의 총합을 비교하여 상기 최적 인덱스 코드를 갱신하는 단계
    를 포함하는 인덱스 부호화 방법.
  3. 제2항에 있어서,
    상기 파일을 전송하는 단계는,
    갱신된 상기 최적 인덱스 코드에 해당하는 적어도 하나의 사용자 단말을 대상으로 파일을 전송하는 것
    을 특징으로 하는 인덱스 부호화 방법.
  4. 제1항에 있어서,
    상기 최적 인덱스 코드로 결정하는 단계는,
    상기 인덱스 코드 집합에 포함된 모든 인덱스 코드들을 대상으로, 브루트-포스(Brute-Force) 알고리즘에 기초하여 성공 전송량의 총합이 최대인 인덱스 코드를 상기 최적 인덱스 코드를 결정하는 것
    을 특징으로 하는 인덱스 부호화 방법.
  5. 제1항에 있어서,
    상기 최적 인덱스 코드는, 상기 기지국이 추정하고 있는 사용자 단말의 메모리 저장 정보와 해당 사용자 단말의 실제 메모리 정보 간의 상관성(correlation)에 기초하여 변경되는 것
    을 특징으로 하는 인덱스 부호화 방법.
  6. 제5항에 있어서,
    상기 파일을 전송하는 단계는,
    상기 상관성이 미리 정의된 제1 기준값 이하로 낮은 경우, 상기 최적 인덱스 코드에 해당하는 적어도 하나의 사용자 단말을 대상으로, 해당 단말에서 요청한 파일을 유니캐스트(unicast)로 전송하는 단계
    를 포함하는 인덱스 부호화 방법.
  7. 제5항에 있어서,
    상기 파일을 전송하는 단계는,
    상기 상관성이 미리 정의된 제2 기준값 이상으로 높은 경우, 상기 최적 인덱스 코드에 해당하는 적어도 하나의 사용자 단말을 대상으로, 해당 단말에서 요청한 파일을 멀티캐스트(multicast)로 전송하는 단계
    를 포함하는 인덱스 부호화 방법.
  8. 제5항에 있어서,
    상기 상관성은 상기 기지국과 사용자 단말 간의 주변 환경 정보 및 시간에 따라 변화하는 것
    을 특징으로 하는 인덱스 부호화 방법.
  9. 사용자 단말의 메모리 저장 정보가 시간에 따라 변화하는 네트워크 환경에서, 복수의 사용자 단말들을 대상으로 인덱스 부호화(index coding)하는 장치에 있어서,
    복호화가 가능한(decodable) 인덱스 코드들을 포함하는 인덱스 코드 집합에서, 인덱스 부호화 장치가 추정하고 있는 사용자 단말의 메모리 저장 정보에 기초하여 인덱스 부호화에 이용될 인덱스 코드를 결정하는 인덱스 코드 결정부;
    상기 인덱스 코드 집합에서 결정된 상기 인덱스 코드와는 다른 인덱스 코드를 선택하고, 결정된 상기 인덱스 코드와 선택된 상기 다른 인덱스 코드를 비교하여 최적 인덱스 코드를 결정하는 최적 인덱스 코드 결정부; 및
    결정된 상기 최적 인덱스 코드에 해당하는 적어도 하나의 사용자 단말을 대상으로 해당 단말에서 요청한 파일을 전송하는 전송 제어부
    를 포함하고,
    상기 인덱스 코드는, 상기 복수의 사용자 단말들 중 요청된 파일에 기초하여 그룹화된 사용자 그룹을 나타내는 것
    을 특징으로 하는 인덱스 부호화 장치.
  10. 제9항에 있어서,
    상기 최적 인덱스 코드 결정부는,
    상기 결정된 인덱스 코드와 상기 선택된 다른 인덱스 코드의 성공 전송량의 총합을 비교하고, 상기 비교를 통해 성공 전송량의 총합이 큰 인덱스 코드를 상기 최적 인덱스코드로 설정하고, 상기 인덱스 코드 집합에 포함된 모든 인덱스 코드들 중 상기 결정된 인덱스 코드와 상기 선택된 다른 인덱스 코드를 제외한 인덱스 코드들을 대상으로 선택된 어느 하나의 인덱스 코드의 성공 전송량의 총합과 설정된 최적 인덱스 코드의 성공 전송량의 총합을 비교하여 상기 최적 인덱스 코드를 갱신하는 것
    을 특징으로 하는 인덱스 부호화 장치.
  11. 제10항에 있어서,
    상기 전송 제어부는,
    갱신된 상기 최적 인덱스 코드에 해당하는 적어도 하나의 사용자 단말을 대상으로 파일을 전송하는 것
    을 특징으로 하는 인덱스 부호화 장치.
  12. 제9항에 있어서,
    상기 최적 인덱스 코드 결정부는,
    상기 인덱스 코드 집합에 포함된 모든 인덱스 코드들을 대상으로, 브루트-포스(Brute-Force) 알고리즘에 기초하여 성공 전송량의 총합이 최대인 인덱스 코드를 상기 최적 인덱스 코드를 결정하는 것
    을 특징으로 하는 인덱스 부호화 장치.
  13. 제9항에 있어서,
    상기 최적 인덱스 코드는, 상기 인덱스 부호화 장치가 추정하고 있는 사용자 단말의 메모리 저장 정보와 해당 사용자 단말의 실제 메모리 정보 간의 상관성(correlation)에 기초하여 변경되는 것
    을 특징으로 하는 인덱스 부호화 장치.
  14. 제13항에 있어서,
    상기 전송 제어부는,
    상기 상관성이 미리 정의된 제1 기준값 이하로 낮은 경우, 상기 최적 인덱스 코드에 해당하는 적어도 하나의 사용자 단말을 대상으로, 해당 단말에서 요청한 파일을 유니캐스트(unicast)로 전송하는 것
    을 특징으로 하는 인덱스 부호화 장치.
  15. 제13항에 있어서,
    상기 전송 제어부는,
    상기 상관성이 미리 정의된 제2 기준값 이상으로 높은 경우, 상기 최적 인덱스 코드에 해당하는 적어도 하나의 사용자 단말을 대상으로, 해당 단말에서 요청한 파일을 멀티캐스트(multicast)로 전송하는 것
    을 특징으로 하는 인덱스 부호화 장치.
  16. 제13항에 있어서,
    상기 상관성은 상기 인덱스 부호화 장치와 사용자 단말 간의 주변 환경 정보 및 시간에 따라 변화하는 것
    을 특징으로 하는 인덱스 부호화 장치.
KR1020170165330A 2017-12-04 2017-12-04 사용자 단말의 메모리 저장 정보가 제한된 환경에서의 인덱스 부호화 방법 및 장치, 그리고 무선 통신 방법 KR102043510B1 (ko)

Priority Applications (1)

Application Number Priority Date Filing Date Title
KR1020170165330A KR102043510B1 (ko) 2017-12-04 2017-12-04 사용자 단말의 메모리 저장 정보가 제한된 환경에서의 인덱스 부호화 방법 및 장치, 그리고 무선 통신 방법

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
KR1020170165330A KR102043510B1 (ko) 2017-12-04 2017-12-04 사용자 단말의 메모리 저장 정보가 제한된 환경에서의 인덱스 부호화 방법 및 장치, 그리고 무선 통신 방법

Publications (2)

Publication Number Publication Date
KR20190065803A true KR20190065803A (ko) 2019-06-12
KR102043510B1 KR102043510B1 (ko) 2019-12-02

Family

ID=66846127

Family Applications (1)

Application Number Title Priority Date Filing Date
KR1020170165330A KR102043510B1 (ko) 2017-12-04 2017-12-04 사용자 단말의 메모리 저장 정보가 제한된 환경에서의 인덱스 부호화 방법 및 장치, 그리고 무선 통신 방법

Country Status (1)

Country Link
KR (1) KR102043510B1 (ko)

Citations (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR20140127007A (ko) * 2013-04-24 2014-11-03 삼성전자주식회사 네트워크 코딩을 지원하는 시스템에서 패킷을 관리하는 방법 및 장치

Patent Citations (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR20140127007A (ko) * 2013-04-24 2014-11-03 삼성전자주식회사 네트워크 코딩을 지원하는 시스템에서 패킷을 관리하는 방법 및 장치

Non-Patent Citations (3)

* Cited by examiner, † Cited by third party
Title
[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. US9535837 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.

Also Published As

Publication number Publication date
KR102043510B1 (ko) 2019-12-02

Similar Documents

Publication Publication Date Title
Peng et al. Backhaul-aware caching placement for wireless networks
CN113612585B (zh) 用于优化多路径数据传输的负载的系统和方法
KR101952490B1 (ko) 비직교 무선 통신들을 용이하게 하기 위한 디바이스들 및 방법들
KR102173084B1 (ko) 무선 통신 시스템에서 데이터 패킷 송수신 방법 및 장치
KR101130591B1 (ko) 무선 네트워크에서 코딩된 스케줄링을 갖는 기회적 멀티캐스팅을 위한 방법 및 장치
JP2020519161A (ja) データ送信方法、基地局、及び端末デバイス
CN113114410A (zh) 数据处理方法、配置方法及通信设备
CN113055285B (zh) 基于mptcp与网络编码的自适应数据传输方法
WO2014056131A1 (zh) 一种数据传输控制方法和装置
KR20150045346A (ko) 이동 통신 시스템에서 멀티미디어 데이터 송수신 방법 및 장치
JP2010514336A (ja) Ｏｆｄｍ技術を利用する通信システムにおいてシンボルをマッピングする方法及び構成
US10523790B2 (en) System and method of header compression for online network codes
CN109565353B (zh) 数据处理方法、终端设备和网络设备
US20100103882A1 (en) Early termination of low data rate traffic in a wireless network
US20230422093A1 (en) Communication Method and Communication Participant
KR102043510B1 (ko) 사용자 단말의 메모리 저장 정보가 제한된 환경에서의 인덱스 부호화 방법 및 장치, 그리고 무선 통신 방법
CN113115233B (zh) 机会式noma协作多播中继选择方法
US20050195849A1 (en) Early termination of low data rate traffic in a wireless network
CN116405741A (zh) 基于多条传输路径的视频传输的调度方法、设备及介质
CN113037356B (zh) 卫星通信系统中码块组大小自适应调整的harq方法
CN110798295A (zh) 用于确定物理共享信道传输数据的方法和设备
CN109005011B (zh) 一种用于水声网络的数据传输方法、系统及可读存储介质
Mahmoodi et al. Low-Complexity Multi-Antenna Coded Caching Using Location-Aware Placement Delivery Arrays
EP3753229B1 (en) Devices and methods for coded caching
Li et al. Random network coding based on adaptive sliding window in wireless multicast networks

Legal Events

Date Code Title Description
A201 Request for examination
E701 Decision to grant or registration of patent right
GRNT Written decision to grant