Advanced
D2D Advertisement Dissemination Algorism based on User Proximity and Density
D2D Advertisement Dissemination Algorism based on User Proximity and Density
Journal of the Korea Institute of Information and Communication Engineering. 2014. Oct, 18(10): 2403-2408
Copyright © 2014, The Korea 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 : June 10, 2014
  • Accepted : July 23, 2014
  • Published : October 31, 2014
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
본 논문에서는 사용자들의 인접성(Proximity)과 밀집도(Density) 정보를 기반으로 D2D 광고 확산 목표 지역을 설정하고, 이 지역들을 대상으로 광고 전송을 수행함으로써 기존의 D2D 광고 확산 알고리즘에서 특정 지역으로 광고 전송이 편중되고 광고 범위 중첩되는 광고 효율 저하 문제를 해결하고자 한다. 본 논문에서 제안하는 광고 확산 알고리즘은 광고 확산을 위해 설정된 목표지역을 기반으로 광고 확산 경로를 점차적 설정하여 확장해 나감으로써 D2D 광고 확산 효율 향상에 기여한다. 또한, 제안 방안의 D2D 광고 확산 범위에 대해서 수학적으로 분석하고. 시뮬레이션을 통하여 다양한 사용자 밀집도 환경에 대한 기존 방안과 제안 방안의 성능 결과를 비교·분석한다.
Keywords
I. 서 론
D2D(Device-to-Device) 통신 기술은 모바일 단말 간에 인접한 거리에 위치해 있더라도 데이터를 송수신하기 위해 기지국을 경유하여야 하는 기존의 통신 방법과는 다르게 인접한 거리에 위치한 모바일 단말 간에 직접적으로 통신을 하는 기술을 말한다. D2D 통신 기술은 인접한 단말들과 저전력으로 단거리 직접 통신을 수행함으로써 커버리지 확장, 배터리 절약 및 지연시간 감소 등과 같은 다양한 장점을 가진다 [1 - 3] . D2D 통신은 데이터 송수신 경로의 다양화를 통하여 무선자원의 재사용 효율을 증가시킴으로써 현재 이슈화 되고 있는 트래픽 급증 및 무선자원 고갈 문제에 대한 해결 방안들 중의 하나로써 그 연구가 활발히 이루어지고 있다 [4] .
이와 같이 인접성(Proximity)과 적시성(Timeliness)의 특징을 가지고 있는 D2D 통신을 이용하여 [5] 에서는 방대한 사용자들을 매개로 하는 온라인 공동구매방식의 전자상거래 [6] 인 소셜커머스 서비스(Social Commerce Service)가 결합된 D2D 광고 시나리오를 제안하고, 그에 따른 광고 확산 효과(Advertisement Dissemination Effect)에 대하여 분석하였다. [5] 에서는 광고 확산을 위해 릴레이 단말을 선택함에 있어서 광고를 전송하는 단말과 이 전송 반경 내에 위치한 단말의 상대적 거리만을 고려하여 선택함으로써 광고가 일정한 방향성 없이 무작위로 확산된다. 그러므로 광고가 특정지역으로 집중 되는 현상이 빈번히 발생하고, 그로 인해 광고 수신 영역 간의 중첩 영역이 많이 발생하고 불필요한 광고 전송이 증가함으로써 광고 전송 효율이 감소되었다.
본 논문에서는 사용자들의 인접성과 밀집도 정보를 고려하여 D2D AP(Access Point)가 광고 전송 목표 지역을 설정하고 이를 기반으로 릴레이 단말들을 점차적으로 설정해 나감으로써 특정 지역에 광고가 집중 되는 문제를 해결하는 동시에, 광고 확산 범위 간의 중첩을 감소시키는 알고리즘을 제안한다. 또한, 제안 방안의 광고 확산 범위에 대하여 수학적으로 분석하고, 시뮬레이션을 통해 그 분석의 정확성을 살펴보며, 제안 방안과 기존 방안의 성능 결과를 비교·분석해본다.
II. D2D 통신 기반 광고 확산 알고리즘
소셜커머스 서비스는 일정 수 이상의 사람이 모여야 파격적인 할인 가격의 제공이 가능하기 때문에 많은 사람들에게 광고가 확산 되는 것이 소비자들을 위하여 유리하다. 하지만 기존 방안 [5] 에서는 광고를 확산시키기 위해 릴레이 단말을 선택하는 과정에서 광고를 전송하는 단말의 위치를 기반으로 전송 반경 내에 최대한 멀리 위치한 단말들을 선택하였기 때문에 광고가 멀리 확산되기는 하였지만, 특정한 목적성이 없이 무작위로 확산된다.
그에 따라 그림 1 과 같이 특정 지역에 광고가 집중되는 현상이 빈번하게 발생하고, 광고 범위간의 중첩이 발생하여 불필요한 전송이 증감함으로써 광고 효율이 크게 감소되는 문제가 발생하였다 .
PPT Slide
Lager Image
기존방안 기반 광고 확산 결과 Fig. 1 Advertisement dissemination result based on conventional scheme
이와 같은 문제점을 해결하기 위해 본 논문에서는 사용자 밀집도( D )를 고려한 D2D 통신 기반 소셜커머스 광고 확산 알고리즘을 제안한다. 구체적 알고리즘은 다음과 같다.
  • ① 커피전문점의 D2D AP는D가 높은 인접한 지역을 1차 광고 목표지점(E1)으로 설정하고 유효 반경 내의 가장 멀리 떨어진D가 높은 지역을 최종 광고 목표지점(Ef)으로 설정하며 각 목표지점의 좌표 정보를 담고 있는 광고를 전송한다.
  • ② D2D AP는 섹터 반경 내에 위치한 단말 중 AP와 가장 먼 거리에 있는 단말을 1차 릴레이 단말(N1)로 선정한다.
  • ③N1은 D2D AP로부터 수신한 광고를 전송한다. 수신한 광고 안에 포함되어 있는 목표지점의 좌표 정보를 이용하여N1의 반경 내에 있는 단말 중E1에 가장 가까운 단말을 릴레이 단말(N2)로 선정한다.
  • ④ 에 광고를 전송 한 후E2,E3, ···,Ef(최종 목표지점)까지 광고를 확산하기 위해 필요한 릴레이 단말들을 점차적으로 선정하여 광고를 확산시킨다.
  • ⑤ 순차적인 릴레이 노드 선정 및 광고 전송으로 최종 목표지점(Ef)까지 광고를 효율적으로 전송 할 수 있다.
III. 제안 방안의 광고 커버리지 분석
그림 2 는 제안 방안을 적용하는 경우에 대하여 유효반경 내에 광고가 확산된 결과를 보여준다. 그림 2 에서와 같이 D2D AP는 섹터를 3개로 나누어 광고를 전송하며, D 가 높은 지역을 목표지점( E 1 , E 2 , ···, Ef )으로 설정하여 광고를 점차적으로 확산시킨다. E 1 을 시작으로 E 2 , E 3 , ···, Ef 까지 점차적으로 광고가 확산되며 Ef 에 광고 전송 시 광고 전송을 종료한다.
PPT Slide
Lager Image
제안방안 기반 광고 확산 결과 Fig. 2 Advertisement dissemination result based on proposed scheme
각 릴레이 단말을
PPT Slide
Lager Image
로 정의하며,
PPT Slide
Lager Image
와 전송범위가 중첩되는 릴레이 단말들의 전송 범위를
PPT Slide
Lager Image
로 정의한다. t 는 섹터의 번호를 의미하며 k 는 한 섹터 안에 분산된 광고경로의 번호를 의미하고, i 는 광고경로 내에 릴레이 단말 번호를 의미한다. 예를 들어 1섹터의 1번 광고경로는 그림 2 에서
PPT Slide
Lager Image
으로 구성되어있다.
PPT Slide
Lager Image
PPT Slide
Lager Image
와 중첩된 릴레이 단말의 수와 중첩 조건에 따라 구할 수 있으며, 이를 통해 한 섹터 내의 광고경로의 범위
PPT Slide
Lager Image
는 다음과 같이 구할 수 있다 [5] .
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
의 중첩되는 범위를 의미하고
PPT Slide
Lager Image
t 번째 섹터에서 k 번째 광고 확산 경로의 릴레이 단말 수를 의미한다. 또한, k 개의 광고 확산 경로로 분산된 한 섹터 내의 광고 범위( St )는 섹터 내의 모든 광고 범위의 합과 각 광고 중첩 범위를 이용하여 다음과 같이 구한다.
PPT Slide
Lager Image
PPT Slide
Lager Image
는 광고경로
PPT Slide
Lager Image
PPT Slide
Lager Image
의 중첩되는 범위를 의미하며 zt t 번째 섹터에서 광고 확산 경로의 수를 의미한다. 여기서, 식 (2)를 기반으로 나누어진 섹터의 수( d )를 통해 전체 광고 확산 범위( Stotal )는 각 섹터의 범위들의 합으로 다음과 같이 구할 수 있다.
PPT Slide
Lager Image
IV. 성능 평가 결과 분석
시뮬레이션 시, 유효 광고 범위 반경은 1000 m , AP와 릴레이 단말의 전송 반경은 각각 200 m 와 80 m 로 가정하였다. D 가 높은 지점은 그림 3 과 같이 서울 중구 을지로 입구역 주변의 롯데백화점을 기준으로 직장인구밀도분석 자료를 [7] 통해 임의로 9개의 광고 목표지점을 정하였다. 인구밀집 지역 및 그에 관한 정보들은 통계적인 자료로써 AP가 사전에 알고 있다고 가정한다. 이에 따라 광고 확산 경로는 그림 3 과 같이 설정된다. Density ratio( Dratio = Dh / Dl )는 사용자 밀집도가 낮은 지역의 인구밀도( Dl ) 대비 높은 지역의 인구밀도( Dh ) 비율을 의미하며, Dratio 를 고려하지 않은 상황과 Dratio 증가에 따른 결과를 분석하기 위해 그림 3 에서 같이 지정된 목표지점(고밀도 지역)의 반경 100 m 와 임의의 저밀도 지역반경 100 m 내의 인구 비율을 1, 3 ,5로 가정하였다. 본 시뮬레이션을 통해 유효 광고 범위 내에서 광고 확산 효과로 인해 확산된 정규 D2D 광고 범위와 전송한 광고 패킷의 수 , 사용자 수에 따른 광고 효율 및 전송한 광고 패킷의 수에 따른 광고 효율에 대해 분석한다.
PPT Slide
Lager Image
서울 중구 을지로역 인근 직장인 인구밀도 분포 Fig. 3 User density around Eulji-ro station
- 4.1. 정규 D2D 광고 범위
그림 4 는 무작위로 배치한 단말의 개수(Number of Users) 대비 AP 및 모든 릴레이 단말들이 광고를 전송한 정규 D2D 광고 범위(Normalized Overall D2D Coverage)를 나타낸다.
PPT Slide
Lager Image
유저 수에 따른 정규 D2D 광고 범위 Fig. 4 Normalized Overall D2D Coverage vs. Number of users
PPT Slide
Lager Image
일반적으로 사용자 수가 증가 하면 정규 D2D 광고 범위는 증가하다 일정 수준에서 포화된다. Dratio 가 클 경우 사용자들이 D 가 높은 지역에 집중되어 있으므로 이외의 지역에 분포되어 있는 사용자의 수가 적어 광고 확산에 영향을 준다. 이에 따라 Dratio 가 클 경우 포화 상태에 이르기까지 더 많은 수의 사용자가 필요하다는 결과를 확인 할 수 있다. 제안 방안(Pro.)은 설정된 목표지역에 광고 전송 후 최종 목표지역까지 광고 전송을 위해 적응적으로 릴레이 단말을 선택하기 때문에 기존 방안(Con.)에 비해 광고 범위가 확산되고 이에 따라 정규 D2D 광고 범위가 더 크게 나타난다. 실선은 시뮬레이션을 통해 얻은 정확한 결과를 나타내며, 기호는 수학적 분석에 의한 결과를 나타낸다. 기존 방안에서는 광고 범위 간의 불필요한 중첩 및 섹터 간 광고 범위의 중첩이 발생하기 때문에 복잡한 환경에 대한 수학적 분석에 한계가 있어 오차가 크지만 제안 방안은 불필요한 중첩이 최소화됨으로써 수학적 분석의 오차도 상대적으로 적게 발생한다.
- 4.2 평균 광고 전송 수
그림 5 의 결과 값은 단말의 개수 대비 평균 광고 전송 수(Average Number of packet transmissions)를 나타낸다. 선정된 릴레이 단말 당 광고를 한번만 전송하기 때문에 총 릴레이 단말 수와 평균 광고 전송 수는 동일하다. 일반적으로 사용자의 수가 증가 할 경우 릴레이 단말의 수는 증가한다. 사용자의 수가 충분할 경우 그림 3 의 각 목표지점에 광고 확산 경로와 유사하게 최단거리로 광고가 확산이 되므로 릴레이 수는 일정해진다.
PPT Slide
Lager Image
유저 수에 따른 평균 광고 전송 수 Fig. 5 Average Number of packet transmissions vs. Number of users
하지만 사용자의 수가 충분하지 않을 경우 최단 경로에 단말이 존재 하지 않아 최단 경로를 벗어나는 경우가 발생하여 릴레이 단말의 수가 포화된 값보다 커지는 결과가 나타난다. 제안 방안의 경우 설정된 목표지점의 수에 따라 선택되는 릴레이 단말의 수가 적응적으로 변화하기 때문에 기존 방안에 비해 상대적으로 릴레이 단말의 수가 많다.
- 4.3. 광고 효율
그림 6 은 단말의 개수 대비 광고 효율(Transmission Efficiency)을 나타낸다.
PPT Slide
Lager Image
유저 수에 따른 광고 효율 Fig. 6 Transmission Efficiency vs. Number of users
PPT Slide
Lager Image
그림 5 에서 사용자 수가 일정 수준 이상이 되면 평균 광고 전송 수는 포화되는 반면 광고 범위 내에 사용자 수는 계속해서 증가하기 때문에 사용자 수가 증가함에 따라 광고 효율은 계속해서 증가하는 결과를 그림 6 에서 나타낸다. 제안 방안은 효율성이 높은 광고 전달을 위하여 D 가 큰 지역을 목표지점으로 설정한다. 이에 따라 D 가 큰 지역이 광고 확산 경로에 포함되어 있어 Dratio 에 영향을 받게 된다. Dratio 가 클수록 광고가 확산되는 경로에 많은 사용자들이 밀집되어 있기 때문에 전송한 광고 당 수신한 사용자의 수가 증가하여 전송 효율이 증가한다. 반면, 기존 방안은 사용자 밀집도에 상관없이 광고를 확산하기 때문에 Dratio 에 관계없이 거의 비슷한 결과를 나타낸다.
그림 7 은 평균 광고 전송 수 대비 광고 효율을 나타낸다. 제안 방안은 기존 방안에 비해 평균 광고 전송 수와 광고 효율이 큰 폭으로 증가한다. 그림 7 의 ①은 사용자 수가 적을 경우 각 릴레이 단말의 반경 내에 단말이 존재 하지 않기 때문에 평균 광고 전송 수가 작다. 그에 따라 광고 효율 또한 좋지 않다. 사용자의 수가 증가하면 광고 확산 효과로 인해 평균 광고 전송 수가 증가하며 광고 효율 또한 증가한다. 사용자의 수가 충분히 많을 경우에는 그림 5 에서와 같이 평균 광고 전송 수가 더 이상 증가하지 않고 일정하게 유지된다. 하지만 이 경우에는 광고 범위 내에 존재하는 단말들은 사용자의 수에 따라 계속해서 증가하기 때문에 광고 효율은 계속해서 증가한다. 그림 7 의 ②는 기존 방안에서 사용자가 충분해지면서 평균 광고 전송 수가 감소하고 수신한 광고 수에 따라 광고 효율이 좋아지는 것을 나타내며 ③은 제안 방안에서 사용자가 충분해지면서 평균 광고 전송 수가 감소하고 수신한 광고 수에 따라 광고 효율이 좋아진다. 제안 방안이 릴레이 단말의 수가 더 많기 때문에 평균 광고 전송 수 또한 크며 광고 확산 경로에 D 가 큰 지역이 포함되어 있어 광고 효율이 더 좋다.
PPT Slide
Lager Image
평균 광고 전송 수에 따른 광고 효율 Fig. 7 Transmission Efficiency vs. Average Number of packet transmissions
V. 결 론
본 논문에서는 D2D AP가 사용자 인접성과 밀집도 정보를 기반으로 광고 전송을 위한 목표지역을 설정함으로써 광고가 확산되는 방향성을 가져 특정 지역에 광고가 집중 되는 문제 해결 및 광고 범위 간의 중첩 발생 현상도 감소되는 것을 광고 확산 결과 그림을 통해 알 수 있다. 또한 기존 방안에서의 수학적 분석과 시뮬레이션 결과는 광고 범위 간의 수많은 중첩에 따른 수학적 분석의 한계에 따라 큰 오차가 발생한다. 하지만 제안 방안에서 중첩현상을 감소시킴으로써 오차가 거의 발생하지 않는다. 또한, 사용자가 일정 지역에 밀집되어 있는 환경에서 사용자 밀집 지역을 광고 목표지역으로 설정할 경우 광고 확산 경로에 사용자 밀집 지역이 포함되기 때문에 광고 효율이 함께 증가하게 된다. 시뮬레이션을 통하여 제안방안을 사용할 경우 기존방안 대비 사용자 밀집 지역이 많을수록 광고 효율이 증가하며, 평균 광고 전송 수에 따른 광고 효율 또한 증가함을 확인하였다. 향후에는, 일반적인 환경에서 광고가 확산될 수 있는 알고리즘에 대해 연구하며, 또한 D2D 통신의 핵심 이슈인 릴레이 수행에 따라 발생하는 전력 소모 감소 방안과 릴레이 수행 횟수에 따른 광고 범위 최적화에 대한 연구를 진행할 계획이다.
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. , et al. 2014 “Five Disruptive Technology Directions for 5G,” IEEE Communications Magazine et al. 52 (2) 74 - 80
Corson M. S. , et al. 2010 “Toward Proximity-Aware Internet-working,” IEEE Wireless Communications et al. 17 (6) 26 - 33
Fodor G. , et al. 2012 “Design aspects of network assisted device-to-device communications,” IEEE Communications Magazine et al. 50 (3) 170 - 177
2010 “Cisco Visual Networking Index: Global Mobile Data Traffic Forecast Update 2009-2014,”
Kim J. S. , Lee H. 2013 “Coverage Analysis of D2D Communications for Social Commerce Services” KICS 2013 Fall Conference 656 - 657
Park K. 2010 “A Study on the Factory of Design Influencing Purchase Decision-making Factors at Social Commerce Sites,” SDPM The J. of Digital Policy and Mgmt. 10 (9) 101 - 110
SEMAS Marketing Area Analysis System http://sg.kmdc.or.kr/main.sg#/main