Advanced
Performance Evaluation of D2D Advertisement Dissemination Algorithms with Maximum Distance and Transmission Efficiency Based Relay Selections
Performance Evaluation of D2D Advertisement Dissemination Algorithms with Maximum Distance and Transmission Efficiency Based Relay Selections
Journal of the Korea Institute of Information and Communication Engineering. 2015. Feb, 19(2): 287-292
Copyright © 2015, The Korean Institute of Information and Commucation Engineering
This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License(http://creativecommons.org/li-censes/by-nc/3.0/) which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.
  • Received : December 18, 2014
  • Accepted : January 19, 2015
  • Published : February 28, 2015
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
준선 김
Department of Electrical, Electronic and Control Engineering, Hankyong National University, Anseong 456-749, Korea
호원 이
Department of Electrical, Electronic and Control Engineering, & IITC, Hankyong National University, Anseong 456-749, Korea
hwlee@hknu.ac.kr

Abstract
본 논문에서는 사용자들의 밀집도 정보를 기반으로 설정된 목표지역과 릴레이 단말의 수를 제한한 환경에서 광고 확산을 위한 최대 거리 기반 릴레이 단말 선택 알고리즘과 최대 효율 기반 릴레이 단말 선택 알고리즘의 성능을 비교 분석하였다. 최대 거리 기반 릴레이 단말 선택 알고리즘은 단말간의 거리 정보만을 이용하여 릴레이 단말을 선택하고, 최대 효율 기반 릴레이 단말 선택 알고리즘은 설정된 목표지역들을 활용하여 최대 광고 효율을 위한 광고 확산 루트를 설정하였다. 시뮬레이션을 통해 광고를 섹터 수의 변화에 따른 성공적으로 수신한 전체 사용자 수와 전송 효율에 대한 성능을 비교하여, 최대 거리 기반 릴레이 단말 선택 알고리즘 보다 최대 효율 기반 릴레이 단말 선택 알고리즘 성능의 우수성에 대해 분석하였다.
Keywords
Ⅰ. 서 론
최근 모바일 단말들과 트래픽이 급증함에 따라 트래픽 과부하 및 무선자원 고갈 등의 문제로 기존의 셀룰러 네트워크의 기지국 중심 통신 구조에 많은 문제점이 발생한다 [1 , 2] . D2D(Device-to-Devicee) 통신은 인접한 단말간에 기지국 없이 직접 통신하는 기술로써 기지국의 트래픽 부하를 감소시켜주며, 기지국과 동일한 주파수 자원을 동시에 사용할 수 있어 주파수 자원의 재사용률을 증가시킬 수 있다 [3 , 4] . 이와 같이 주파수 자원의 효율을 향상시키는 측면에서 D2D통신의 연구가 활발하게 진행되고 있으며, D2D 통신을 이용한 다양한 use-case들도 연구되고 있다 [5 - 10] . 또한 D2D 통신에서 는 인접성을 기반으로 높은 데이터 전송률, 저지연 통신 그리고 저전력 통신이 가능하다 [1 , 3 , 4] .
D2D 통신과 온라인 공동구매 방식의 소셜커머스 서비스의 결합을 통한 광고 시나리오 및 알고리즘에 대해 [11 , 12] 에서 제안하였고, 최대 거리 기반 릴레이 단말 선택 알고리즘을 통한 성능을 분석하였다. 거리 정보만을 이용하여 릴레이 단말을 선정하는 최대 거리 기반 릴레이 단말 선택 알고리즘은 방향성 없이 무작위로 광고가 확산 된다. 그래서 광고가 특정 지역에 집중 되는 현상이 발생 할 뿐만 아니라 릴레이 단말 간의 중첩 되는 현상이 발생하여 비효율적으로 광고가 확산된다.
기존의 TV, 라디오, 옥외광고와 같은 값비싼 광고 매체들은 소상공인들이 이용하는데 비용적인 면에서 어려움이 많았다. 하지만 제안한 시나리오는 소셜커머스와 D2D 통신의 특징에 따라 저비용 고효율의 광고가 가능하다. 소셜커머스는 일정 수 이상의 사람들이 구입을 결정할 경우 대폭 할인된 가격으로 상품 및 서비스를 구입할 수 있는 공동구매 특징이 있다. 그리고 소셜커머스 서비스의 할인 조건을 충족시키기 위해 인접한 단말과 D2D 통신을 통해 자발적으로 광고를 확산 할 수 있다.
본 논문에서는 사용자들이 특정 지역에 밀집해 있고 릴레이 단말의 전송 수를 제한한 환경에서, 최대 거리 기반 릴레이 단말 선택 알고리즘과 최대 효율 기반 릴레이 단말 선택 알고리즘의 성능을 비교·분석한다.
Ⅱ. 소셜커머스 서비스를 위한 D2D통신 기반 광고 확산 알고리즘
광고 전송을 시작하는 D2D Access Point (AP) 는 광고를 확산하기 위해 릴레이 단말들을 선정해야 한다. D2D AP의 전송 반경 내에 있는 모든 단말들은 AP로부터 전송된 광고를 수신하고, 선정된 릴레이 단말은 자신의 통신 범위 내에 있는 단말 중에서 다음 차례의 릴레이 단말을 선정함으로써 광고가 점차적으로 확산되게 된다. D2D AP는 광고 전송을 시작 할 때, 광고의 원활한 확산을 위하여 통신 범위를 임의의 섹터 수로 나눌 수 있다. 각 섹터 당 하나의 릴레이 단말을 선정한다고 가정하면 섹터의 수가 많을 경우 동시에 광고가 확산되는 수가 많아진다. 광고를 한번이라도 수신한 사용자는 더 이상 광고를 수신하지 않으며 릴레이 단말이 될 수 없다. 일반적으로 사용자들은 균일하게 분포되어 있지 않고 특정 지역에 밀집되어 있는 분포를 따른다. 고밀도 지역은 광고 확산의 효율을 향상시키기 위하여 우선적인 광고 전달 목표 지역으로 설정 할 수 있다. 최대 효율 기반 릴레이 단말 선택 알고리즘에서 D2D AP는 통계적인 자료를 통해 사전에 사용자 밀집도가 높은 지역의 좌표 정보를 알고 있다고 가정한다. 광고 확산을 위한 최대 거리 기반 릴레이 단말 선택 알고리즘은 그림 1 과 같이 목표지역을 고려하지 않고, 최대 효율 기반 릴레이 단말 선택 알고리즘은 그림 2 와 같이 통계적인 자료로써 사전에 알고 있는 목표지역을 고려하는 것으로 구체적인 알고리즘은 다음과 같다.
PPT Slide
Lager Image
섹터 수가 3 이고 릴레이 수의 제한이 없을 때, 최대 거리 기반 릴레이 단말 선택 알고리즘을 이용한 광고 확산 Fig. 1 Advertisement dissemination using the maximum distance based relay selection when the number of sectors is 3 without the limit for the number of relays
PPT Slide
Lager Image
섹터의 수가 3 이고 릴레이 전송 수의 제한이 없을 때, 최대 효율 기반 릴레이 단말 선택 알고리즘을 이용한 광고 확산 Fig. 2 Advertisement dissemination using the maximum efficiency based relay selection when the number of sectors is 3 without the limit for the number of relays
- 2.1. 최대 거리 기반 릴레이 단말 선택 알고리즘 (MDRSA : The Maximum Distance based Relay Selection Algorithm)
  • ➀ D2D AP의 통신 범위를 임의의 섹터 수로 분할한다.
  • ➁ 각 섹터 별로 D2D AP와 가장 멀리 있는 단말을 릴레이 단말(R1)로 선정한다.
  • ➂R1의 통신 범위 안에 있는 단말 중R1과의 거리가 가장 멀리 있는 단말을 다음 릴레이 단말(R2)로써 선정한다.
  • ➃ ➁~➂의 과정을 반복적으로 수행하여 최종 릴레이 단말(Rn)까지 순차적으로 선정하여 광고를 확산한다.
- 2.2. 최대 효율 기반 릴레이 단말 선택 알고리즘 (MERSA : The Maximum Efficiency based Relay Selection Algorithm)
  • ➀ D2D AP의 통신 범위를 임의의 섹터 수로 분할한다.
  • ➁ D2D AP를 기준으로 목표지역들의 각도를 계산하고 나누어진 섹터의 각도 범위에 해당되는 섹터에 목표지역을 할당한다. 섹터의 각도 범위는 다음과 같다.
PPT Slide
Lager Image
  • sk는k번째 섹터의 각도 범위를 나타내며Ns는 분할 된 섹터의 수를 의미한다.
  • ➂ 각 섹터 별로 할당된 목표지역들을 이용해 최대광고 효율을 위한 광고 확산 루트를 설정한다.
  • - 광고 확산을 위한 첫 번째 목표지역(t1)을 처음으로 할당된 목표지역으로 선정한다.
  • -t1과 가장 가까운 목표지역을 광고 확산을 위한 두번째 목표지역(t2)으로 선정한다.
  • - 위와 같은 과정을 반복하여 광고 확산을 위한 최종 목표지역(tm)까지 선정하면서 광고 확산 루트를 설정한다.
  • ➃ D2D AP는 섹터 당 설정된t1과 가장 가까운 단말을 릴레이 단말(R1)로 선정한다.
  • ➄R1의 통신 범위 안에 있는 단말 중t1과 가장 가까운 단말을 다음 릴레이 단말(R2)로써 선정한다.R2의 통신 범위 안에t1이 존재 한다면 첫 번째 목표지역에 광고를 확산하였기 때문에 다음 목표지역인t2를 기준으로 릴레이 단말을 선정한다.
  • ➅ ➄의 반복적인 과정을 통해 순차적으로 최종 릴레이 단말인Rn까지 선정하면서 최종 목표지역인tm까지 광고를 확산한다.
  • ➆ ➂에서 광고 확산을 위한t1을 두 번째로 할당된 목표지역부터 마지막으로 할당된 목표지역까지 설정 하면서, ➂~➅의 과정을 반복한다. 다양한 광고 확산루트를 통해 얻은 광고 효율 결과들을 비교하여 최대 광고 효율을 결정한다.
Ⅲ. 성능 평가 및 결과 분석
시뮬레이션 시, 유효 광고 범위의 반경은 100 m , D2D AP와 릴레이 단말의 전송 반경은 각각 200 m , 80 m 로 가정하고, 유효 범위 내에 5000개의 단말과 반경이 100 m 인 9개의 목표지역을 임의로 분포시켰다. Dratio 는 사용자 밀집도가 높은 지역과 낮은 지역의 비율을 의미하는 것으로 4, 8, 12로 가정하였다. 현실적으로 많은 릴레이를 이용하여 광고를 확산하는 것은 어려움이 있어, 전체 릴레이 수( Ncell )와 섹터 당 릴레이의 수( Nsct )를 30, 10으로 각각 가정하여 시뮬레이션을 수행한다. 위와 같은 환경에서 최대 거리 기반 릴레이 단말 선택 알고리즘 및 최대 효율 기반 릴레이 단말 선택 알고리즘의 시뮬레이션을 수행한 광고 확산 결과는 그림 3 , 4 와 같다.
PPT Slide
Lager Image
섹터 수가 3, 전체 릴레이 수가 30, 섹터 당 릴레이 단말수가 10 일 때, 최대 거리 기반 릴레이 단말 선택 알고리즘을 이용한 광고 확산 Fig. 3 Advertisement dissemination using the maximum distance based relay selection algorithm when number of sectors, total relays and relays per sector is 3, 30 and 10, respectively
PPT Slide
Lager Image
섹터 수가 3, 전체 릴레이 수가 30, 섹터 당 릴레이 단말수가 10 일 때, 최대 효율 기반 릴레이 단말 선택 알고리즘을 이용한 광고 확산 Fig. 4 Advertisement dissemination using the maximum efficiency based relay selection algorithm when number of sectors, total relays and relays per sector is 3, 30 and 10, respectively
섹터의 수( Ns )에 따라 최대 거리 기반 릴레이 단말 선택 알고리즘과 최대 효율 기반 릴레이 단말 선택 알고리즘을 통해 광고를 성공적으로 수신한 사용자들의 수(Total Number of Successfully Received Users : Nuser )는 그림 5 와 같다. 최대 거리 기반 릴레이 단말 선택 알고리즘의 경우 목표지역을 고려하지 않고, 단말간의 거리 정보만을 이용하여 릴레이 단말을 선정하기 때문에 방향성 없이 무작위로 광고가 확산 된다. 그래서 릴레이 단말 간의 중첩 및 광고가 특정 지역에 집중 되는 현상이 발생하여 Nuser 가 최대 효율 기반 릴레이 단말 선택 알고리즘에 비하여 적다. Dratio 가 클수록 목표지역에 집중되는 사용자의 수는 증가하기 때문에 목표지역에 광고를 확산하는 최적 방안은 Nuser 의 증가폭이 크다. 각 섹터 당 전송 할 수 있는 릴레이 단말의 수가 많을수록 각 섹터에 할당된 모든 목표지역에 광고를 확산할 기회가 증가한다. 하지만 섹터 당 전송 할 수 있는 릴레이 단말의 수가 적어질수록 목표지역까지 광고를 확산하기 전에 광고가 종료되어 효율적으로 광고가 확산 되지 않는다. 즉, Ns 가 3 보다 클 경우 Ncell 의 제한 때문에 각 섹터 당 릴레이 단말의 수가 감소하여 Nsct 를 만족할 수 없다. 이 때문에 목표지역에 광고를 확산할 확률이 줄고 사용자가 집중되어 있지 않은 곳에 주로 광고가 확산되어 Nuser 가 감소한다. 주로 저밀도 지역에 광고를 확산하기 때문에 Dration 에 따른 Nuser 의 영향이 감소하며, Ns 가 6일 경우 거의 유사해진다. Ns 가 3일 경우 각 광고를 확산하는 릴레이 단말의 수가 Nsct Ncell 를 만족하기 때문에 Nuser 가 가장 크다. Ns 가 3보다 작을 경우 섹터의 수는 적고 Nsct 의 제한 때문에 Ns 가 3 이상일 경우 보다 전체 릴레이 수( Nrelay )가 감소하여 Nuser 가 감소한다.
PPT Slide
Lager Image
섹터 수에 따른 광고를 성공적으로 수신한 사용자 수 Fig. 5 Total Number of Successfully Received Users vs. Number of Sectors
Nuser 와 광고를 확산하기 위한 Nrelay 를 통해 광고 효율(Transmission Efficiency = Nuser / Nrelay )을 구할 수 있다. Nrelay Ncell Nsct 의 제한을 초과 할 수 없기 때문에 최대 거리 기반 릴레이 단말 선택 알고리즘과 최대 효율 기반 릴레이 단말 선택 알고리즘의 Nrelay 는 동일하다. 하지만 최대 효율 기반 릴레이 단말 선택 알고리즘이 최대 거리 기반 릴레이 단말 선택 알고리즘에 비해 Nuser 가 많기 때문에 최대 효율 기반 릴레이 단말 선택 알고리즘의 광고 효율이 더 좋은 것을 그림 6 에서 볼 수 있다. D2D AP의 전송 반경은 200 m 이고 릴레이 단말의 전송 반경은 80 m 이기 때문에 처음에 D2D AP가 광고를 확산 할 때 가장 많은 사용자들이 광고를 수신하게 된다. 그 이후로 릴레이 단말에 의하여 광고를 수신하는 사용자들의 수는 상대적으로 작기 때문에 광고 효율은 Ns 가 1일 경우 가장 크다. Ns 가 증가 할수록 결정된 광고 확산 루트들의 광고 효율은 모두 동일하지 않고 감소하게 된다. 또 Ns 가 3 이상일 경우 Nuser 는 감소하는 경향을 가지고 있기 때문에 광고 효율은 Ns 가 증가함에 따라 감소하는 경향을 보인다.
PPT Slide
Lager Image
섹터 수에 따른 광고 효율 Fig. 6 Transmission Efficiency vs. Number of Sectors
Ⅳ. 결 론
일반적으로 사용자들은 특정 지역에 밀집되어 있는 경향이 크고, 특별한 이득 없이 릴레이를 수행하는 것을 선호하지 않기 때문에 성능분석에서 릴레이 단말의 수를 제한하였다. 이러한 환경에서 소셜커머스 서비스와 D2D 통신의 결합을 통한 최대 거리 기반 릴레이 단말 선택 알고리즘 및 최대 효율 기반 릴레이 단말 선택 알고리즘의 광고를 성공적으로 수신하는 사용자의 수와 광고 효율을 비교 분석하였다. 릴레이 단말 수 제한에 따라 최대 거리 기반 릴레이 단말 선택 알고리즘 및 최대 효율 기반 릴레이 단말 선택 알고리즘의 광고 확산을 위한 릴레이 단말의 수는 섹터의 수가 3일 때, 최대 30으로 동일하다. 하지만 최대 거리 기반 릴레이 단말 선택 알고리즘은 목표지역을 고려하지 않아 광고가 무작위로 확산되어 광고를 성공적으로 수신하는 사용자의 수가 섹터의 수가 3일 때, 최대 570개의 단말로써 상대적으로 적어 광고 효율이 19%로 좋지 않다. 반면에 최대 효율 기반 릴레이 단말 선택 알고리즘은 사용자 밀집도가 높은 목표지역을 고려하여 광고를 확산하기 때문에 섹터의 수가 3일 때, 최대 1100개의 단말이 성공적으로 광고를 수신하여 광고 효율 34%로 최대 거리 기반 릴레이 단말 선택 알고리즘보다 약 15%로 더 좋다.
섹터의 수 및 제한된 릴레이 단말의 수, 사용자 밀집도의 비율, 결정된 광고 확산 루트 등의 여러 가지 환경에 따라 광고를 수신하는 사용자의 수 및 광고 효율이 달라진다. 이와 같이 여러 가지 환경에 따라 매개 변수를 적절히 설정해야 광고를 좀 더 효율적으로 확산 할 수 있다.
Acknowledgements
이 논문은 2014년도 정부(미래창조과학부)의 재원으로 한국연구재단의 지원을 받아 수행된 기초연구사업임(No. 2014R1A1A1008705)
BIO
김준선(JunSeon Kim)
2014년 국립한경대학교 전자공학과 학사
2014년 ~ 현재 국립한경대학교 전기전자제어공학과 석사과정
※관심분야 : D2D 통신, 최적 CSMA
이호원(Howon Lee)
2009년 KAIST 전기및전자공학과 박사
2009년 ~ 2010년 KAIST IT융합연구소 선임연구원
2010년 ~ 2012년 KAIST IT융합연구소 팀장/연구조교수
2012년 ~ 현재 국립한경대학교 전기전자제어공학과 조교수
2012년 ~ 현재 KAIST IT융합연구소 겸직교수
※관심분야 : 차세대 이동통신 시스템, D2D 통신, 최적 CSMA, 지식융합기술 등
References
Boccardi F. 2014 “Five Disruptive Technology Directions for 5G,” IEEE Communications Magazine 52 (2) 74 - 80    DOI : 10.1109/MCOM.2014.6736746
Cisco VNI Forecast 2014 “Cisco Visual Networking Index: Global Mobile data Traffic Forecast Update 2013-2018,” Cisco Public Information
Fodor G. 2012 “Design aspects of network assisted device-to-device communications,” IEEE Communications Magazine 50 (3) 170 - 177    DOI : 10.1109/MCOM.2012.6163598
Corson M. S. “Towards Proximity-Aware Internetworking,” IEEE Wireless Communications Dec. 2010 26 - 33
Kaufman B. , Aazhang B. “Cellular networks with an overlaid device to device network,” in Proceedings of Asilomar Conference on Signals, Systems and Computers Oct. 2008 1537 - 1541
Doppler K. 2009 “Device-to-device communication as an underlay to LTE-advanced networks,” IEEE Communications Magazine 47 (12) 42 - 49    DOI : 10.1109/MCOM.2009.5350367
Doppler K. “Device-to-device communications; functional prospects for LTE-Advanced networks,” in Proceedings of IEEE ICC Workshops Jun. 2009 1 - 6
Osseiran A. “Advances in device-to-device communications and network coding for IMT-Advanced,” ICT Mobile Summit Jun. 2009
Peng T. “Interference avoidance mechanisms in the hybrid cellular and device-to-device systems,” in Proceedings of IEEE PIMRC Sep. 2009 617 - 621
Lei L. , Zhong Z. , Lin C. , Shen X. 2012 “Operator controlled device-to-device communications in LTE-advanced networks,” IEEE Wireless Communications Magazine 19 (3) 96 - 104    DOI : 10.1109/MWC.2012.6231164
Kim J. S. , Lee H. 2014 “Advertisement Coverage Analysis of Social Commerce Service with D2D Communications,” JKIICE 18 (7) 1547 - 1556
Kim J. S. , Lee H. 2014 “D2D Advertisement Dissemination Algorism based on User Proximity and Density,” JKIICE 18 (10) 2403 - 2408