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.

Figures/Tables 14

Figure 1 Problem description of billboard advertising, where the advertiser has only one kind of product

Figure 2 Problem description of billboard advertising, when the advertiser has multiple products

Table 1 An example for removing and inserting billboards

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

Figure 3 Performances on the roma/taxi trace set, when all billboards have the same cost

Figure 4 Performances on the epfl trace set, when all billboards have the same cost

Figure 5 Performances on the geolife trace set, when all billboards have the same cost

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 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

Figure 6 Performances on the roma/taxi trace set, when all billboards have different costs

Figure 7 Performances on the epfl trace set, when all billboards have different costs

Figure 8 Performances on the geolife trace set, when all billboards have different costs

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 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

Figure 9 Performances on the roma/taxi trace set, when the advertiser has multiple products

Figure 10 Performances on the epfl trace set, when the advertiser has multiple products

Figure 11 Performances on the geolife trace set, when the advertiser has multiple products

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 URL
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 URL
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 URL
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 URL
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 URL
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 URL
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 URL
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 URL
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 URL
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 URL
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 URL
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 URL
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 URL
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 URL
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 URL
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 URL
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 URL
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 URL
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 URL
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 URL
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 URL
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 URL
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 URL

[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

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 14

References 31

Related Articles 2

Recommended Articles

Metrics