Maximum-Profit Advertising Strategy Using Crowdsensing Trajectory Data

doi:10.12142/ZTECOM.202102005

ZTE Communications ›› 2021, Vol. 19 ›› Issue (2): 29-43.doi: 10.12142/ZTECOM.202102005

• Special Topic • Previous Articles Next Articles

Maximum-Profit Advertising Strategy Using Crowdsensing Trajectory Data

LOU Kaihao¹(), YANG Yongjian¹, YANG Funing¹, ZHANG Xingliang²

^1.Jilin University, Changchun 130012, China
^2.China Mobile Group Jilin Co. , Ltd. , Changchun 130021, China

Received:2021-03-11 Online:2021-06-25 Published:2021-07-27
About author:LOU Kaihao (loukh20@mails.jlu.edu.cn) received the B.E. degree in software engineering from Jilin University, China in 2017, M.S. degree in computer science and technology from Jilin University in 2020. He is currently pursuing the Ph.D. degree in computer science and technology at Jilin University. His current research focuses on mobile crowdsensing and multi-agent reinforcement learning.|YANG Yongjian received his B.E. degree in automatization from Jilin University of Technology, China in 1983, M.E. degree in computer communication from Beijing University of Post and Telecommunications, China 1991, and Ph.D. in software and theory of computer from Jilin University, China in 2005. He is currently a professor and a Ph.D. supervisor at Jilin University, the Vice Dean of the Software College of Jilin University, Director of Key lab under the Ministry of Information Industry, Standing Director of the Communication Academy, and a member of the Computer Science Academy of Jilin Province. His research interests include network intelligence management, wireless mobile communication and services, and wireless mobile communications.|YANG Funing received her B.E. degree in software engineering from Jilin University, China in 2010 and master’s degree from the school of computer science, Beijing University of Posts and Telecommunications, China in 2013. She is currently a teacher at Jilin University, China. Her current research interests include management, mobile crowdsensing, integration and mining of massive traffic data|ZHANG Xingliang received his B.E. degree in software engineering from Jilin University, China in 2010. He is currently an engineer at the Network Management Center of China Mobile Group Jilin Co., Ltd. His current research interests include mobile communication data analysis and big data analysis of 5G.
Supported by:
Jilin Science and Technology Department Key Technology Project(20190304127YY);the National Natural Science Foundations of China(1772230);Natural Science Foundations of Jilin Province(20190201022JC);National Science Key Lab Fund Project(61421010418);Innovation Capacity Building Project of Jilin Province Development and Reform Commission(2020C017-2);Changchun Science and Technology Development Project(18DY005);Key Laboratory of Defense Science and Technology Foundations(61421010418);Jilin Province Young Talents Lifting Projec(3D4196993421);A conference version of the paper appeared in Proceedings of SocialSec^[2]

Abstract

Abstract:

Out-door billboard advertising plays an important role in attracting potential customers. However, whether a customer can be attracted is influenced by many factors, such as the probability that he/she sees the billboard, the degree of his/her interest, and the detour distance for buying the product. Taking the above factors into account, we propose advertising strategies for selecting an effective set of billboards under the advertising budget to maximize commercial profit. By using the data collected by Mobile Crowdsensing (MCS), we extract potential customers’ implicit information, such as their trajectories and preferences. We then study the billboard selection problem under two situations, where the advertiser may have only one or multiple products. When only one kind of product needs advertising, the billboard selection problem is formulated as the probabilistic set coverage problem. We propose two heuristic advertising strategies to greedily select advertising billboards, which achieves the expected maximum commercial profit with the lowest cost. When the advertiser has multiple products, we formulate the problem as searching for an optimal solution and adopt the simulated annealing algorithm to search for global optimum instead of local optimum. Extensive experiments based on three real-world data sets verify that our proposed advertising strategies can achieve the superior commercial profit compared with the state-of-the-art strategies.

Key words: billboard advertising, mobile Crowdsensing, probabilistic set coverage problem, simulated annealing, optimization problem

LOU Kaihao, YANG Yongjian, YANG Funing, ZHANG Xingliang. Maximum-Profit Advertising Strategy Using Crowdsensing Trajectory Data[J]. ZTE Communications, 2021, 19(2): 29-43.

Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks

Figures/Tables 14

Figure 1

Figure 2

Table 1

Figure 3

Figure 4

Figure 5

Table 2

Simulation results on epfl, when all billboards have the same cost"

Algorithm	Deadline
Algorithm	500	510	520	530	540	550
Optimal	37.06	37.27	37.71	37.85	37.87	37.91
$1 - 1 e ?$ Optimal	23.42	23.56	23.84	23.92	23.94	23.96
ASFCC	35.34	35.39	35.42	35.48	35.52	35.54

Table 2

Figure 6

Figure 7

Figure 8

Table 3

Simulation results on epfl, when all billboards have different costs"

Algorithm	Deadline
Algorithm	500	510	520	530	540	550
Optimal	37.38	37.41	37.59	37.62	38.02	38.71
$(1 - 1 e) ?$ Optimal	23.63	23.65	23.76	23.78	24.03	24.47
ASFCC	35.37	35.40	35.44	35.45	35.47	35.54

Table 3

Figure 9

Figure 10

Figure 11

References 31

1	QUINN P. Global digital OOH media revenues pacing up 13% in 2017, US DOOH advertising expands 10%: PQ media [EB/OL]. (2017⁃09⁃06) [2020⁃01⁃01].
2	LOU K H, LI S Q, YANG F N, et al. Advertising strategy for maximizing profit using Crowdsensing trajectory data [C]// Security and Privacy in Social Networks and Big Data. Singapore: Springer Singapore, 2020: 395–406. DOI: 10.1007/978-981-15-9031-3_35 doi: 10.1007/978-981-15-9031-3_35
3	NIGAM S, ASTHANA S, GUPTA P. IoT based intelligent billboard using data mining [C]//International Conference on Innovation and Challenges in Cyber Security (ICICCS⁃INBUSH). Greater Noida, India: IEEE, 2016: 107–110
4	LIU D Y, WENG D, LI Y H, et al. SmartadP: visual analytics of large⁃scale taxi trajectories for selecting billboard locations [J]. IEEE transactions on visualization and computer graphics, 2017, 23(1): 1–10. DOI: 10.1109/TVCG.2016.2598432 doi: 10.1109/TVCG.2016.2598432
5	HUANG M, FANG Z X, XIONG S L, et al. Interest⁃driven outdoor advertising display location selection using mobile phone data [J]. IEEE access, 2019, 7: 30878–30889. DOI: 10.1109/ACCESS.2019.2903277 doi: 10.1109/ACCESS.2019.2903277
6	WANG L, YU Z W, YANG D Q, et al. Efficiently targeted billboard advertising using crowdsensing vehicle trajectory data [J]. IEEE transactions on industrial informatics, 2020, 16(2): 1058–1066. DOI: 10.1109/TII.2019.2891258 doi: 10.1109/TII.2019.2891258
7	ZHENG H Y, WU J. Placement optimization for advertisement dissemination in smart City [J]. IEEE transactions on network science and engineering, 2020, 7(1): 239–252. DOI: 10.1109/TNSE.2018.2805768 doi: 10.1109/TNSE.2018.2805768
8	GANTI R K, YE F, LEI H. Mobile crowdsensing: current state and future challenges [J]. IEEE communications magazine, 2011, 49(11): 32–39. DOI: 10.1109/MCOM.2011.6069707 doi: 10.1109/MCOM.2011.6069707
9	LIU J W, SHEN H Y, ZHANG X. A survey of mobile crowdsensing techniques: a critical component for the Internet of Things [C]//25th International Conference on Computer Communication and Networks (ICCCN). Waikoloa, USA: IEEE, 2016: 1–6. DOI: 10.1109/ICCCN.2016.7568484 doi: 10.1109/ICCCN.2016.7568484
10	CAPPONI A, FIANDRINO C, KANTARCI B, et al. A survey on mobile crowdsensing systems: challenges, solutions, and opportunities [J]. IEEE communications surveys & tutorials, 2019, 21(3): 2419–2465. DOI: 10.1109/COMST.2019.2914030 doi: 10.1109/COMST.2019.2914030
11	KARALIOPOULOS M, KOUTSOPOULOS I, TITSIAS M. First learn then earn: optimizing mobile crowdsensing campaigns through data⁃driven user profiling [C]//Proceedings of the 17th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc ’16). New York, USA: ACM, 2016: 271–280
12	BRACCIALE L, BONOLA M, LORETI P, et al. CRAWDAD dataset roma/taxi [EB/OL]. (2014⁃07⁃17) [2020⁃01⁃01].
13	PIORKOWSKI M, SARAFIJANOVIC⁃DJUKIC N, GROSSGLAUSER M. CRAWDAD dataset epfl/mobility [EB/OL]. (2009⁃02⁃24)[2020⁃01⁃01].
14	ZHENG Y, ZHANG L, XIE X, et al. Mining interesting locations and travel sequences from GPS trajectories [C]//Proceedings 13 of the 18th International Conference on World Wide Web (WWW’09). New York, USA: ACM, 2009: 791–800
15	KRISHNA O, AIZAWA K. Billboard saliency detection in street videos for adults and elderly [C]//25th IEEE International Conference on Image Processing (ICIP). Athens, Greece: IEEE, 2018: 2326–2330
16	AN T T, CHANG C P, LI Y H, et al. Fog computing architecture⁃based Wi⁃Fi union mechanism for Internet advertising system [C]//International Conference on Applied System Innovation (ICASI). Sapporo, Japan: IEEE, 2017: 1024–1027. DOI: 10.1109/ICASI.2017.7988110 doi: 10.1109/ICASI.2017.7988110
17	ZHANG Y P, LI Y C, BAO Z F, et al. Optimizing impression counts for outdoor advertising [C]//Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. New York, USA: ACM, 2019: 1205–1215. DOI: 10.1145/3292500.3330829 doi: 10.1145/3292500.3330829
18	ARIYA SANJAYA I M, SUPANGKAT S H, SEMBIRING J. Citizen reporting through mobile crowdsensing: a smart city case of bekasi [C]//International Conference on ICT for Smart Society (ICISS). Semarang, Indonesia: IEEE, 2018: 1–4. DOI: 10.1109/ICTSS.2018.8549976 doi: 10.1109/ICTSS.2018.8549976
19	CHEUNG M H, HOU F, HUANG J W. Delay⁃sensitive mobile crowdsensing: Algorithm design and economics [J]. IEEE transactions on mobile computing, 2018, 17(12): 2761–2774. DOI: 10.1109/TMC.2018.2815694 doi: 10.1109/TMC.2018.2815694
20	CAO B, XIA S C, HAN J W, et al. A distributed game methodology for crowdsensing in uncertain wireless scenario [J]. IEEE transactions on mobile computing, 2020, 19(1): 15–28. DOI: 10.1109/TMC.2019.2892953 doi: 10.1109/TMC.2019.2892953
21	GONG W, ZHANG B X, LI C. Location⁃based online task assignment and path planning for mobile crowdsensing [J]. IEEE transactions on vehicular technology, 2019, 68(2): 1772–1783. DOI: 10.1109/TVT.2018.2884318 doi: 10.1109/TVT.2018.2884318
22	MARJANOVIĆ M, ANTONIĆ A, ŽARKO I P. Edge computing architecture for mobile crowdsensing [J]. IEEE access, 2018, 6: 10662–10674. DOI: 10.1109/ACCESS.2018.2799707 doi: 10.1109/ACCESS.2018.2799707
23	ZHENG Y F, DUAN H Y, YUAN X L, et al. Privacy⁃aware and efficient mobile crowdsensing with truth discovery [J]. IEEE transactions on dependable and secure computing, 2020, 17(1): 121–133. DOI: 10.1109/TDSC.2017.2753245 doi: 10.1109/TDSC.2017.2753245
24	WANG L, YU Z W, ZHANG D Q, et al. Heterogeneous multi⁃task assignment in mobile crowdsensing using spatiotemporal correlation [J]. IEEE transactions on mobile computing, 2019, 18(1): 84–97. DOI: 10.1109/TMC.2018.2827375 doi: 10.1109/TMC.2018.2827375
25	WANG J T, WANG Y S, ZHANG D Q, et al. PSAllocator: multi⁃task allocation for participatory sensing with sensing capability constraints [C]//Proceedings of the 2017 ACM Conference on Computer Supported Cooperative Work and Social Computing. New York, USA: ACM, 2017: 1139–1151. DOI: 10.1145/2998181.2998193 doi: 10.1145/2998181.2998193
26	LIN M, W⁃J HSU, LEE Z Q. Predictability of individuals’ mobility with high⁃resolution positioning data [C]//Proceedings of the 2012 ACM Conference on Ubiquitous Computing (UbiComp ’12). New York, USA: ACM, 2012: 381–390
27	WANG E, YANG Y J, WU J, et al. An efficient prediction⁃based user recruitment for mobile crowdsensing [J]. IEEE transactions on mobile computing, 2018, 17(1): 16–28. DOI: 10.1109/TMC.2017.2702613 doi: 10.1109/TMC.2017.2702613
28	YUAN Q, CARDEI I, WU J. An efficient prediction⁃based routing in disruption⁃tolerant networks [J]. IEEE transactions on parallel and distributed systems, 2012, 23(1): 19–31. DOI: 10.1109/TPDS.2011.140 doi: 10.1109/TPDS.2011.140
29	YANG Y J, LIU W B, WANG E, et al. A prediction⁃based user selection framework for heterogeneous mobile Crowdsensing [J]. IEEE transactions on mobile computing, 2019, 18(11): 2460–2473. DOI: 10.1109/TMC.2018.2879098 doi: 10.1109/TMC.2018.2879098
30	YANG Y J, XU Y B, WANG E, et al. Exploring influence maximization in online and offline double⁃layer propagation scheme [J]. Information sciences, 2018, 450: 182–199. DOI: 10.1016/j.ins.2018.03.048 doi: 10.1016/j.ins.2018.03.048
31	KHULLER S, MOSS A, NAOR J S. The budgeted maximum coverage problem [J]. Information processing letters, 1999, 70(1): 39–45. DOI: 10.1016/s0020-0190(99)00031-9 doi: 10.1016/s0020-0190(99)00031-9

	Billboard A	Billboard B
Advertisement 1	200	300
Advertisement 2	300	200
Advertisement 3	400	100

[1]	LIU Junyu, YANG Yongjian, WANG En. BPPF: Bilateral Privacy-Preserving Framework for Mobile Crowdsensing [J]. ZTE Communications, 2021, 19(2): 20-28.
[2]	LIAO Lingxia, Victor C. M. Leung, LAI Chin-Feng. Evolutionary Algorithms in Software Defined Networks: Techniques, Applications, and Issues [J]. ZTE Communications, 2017, 15(3): 20-36.

Maximum-Profit Advertising Strategy Using Crowdsensing Trajectory Data

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 14

References 31

Related Articles 2

Recommended Articles

Metrics

Comments