Connection is power: Near optimal advertisement infrastructure placement for vehicular fogs

Mobile advertisement infrastructure (MAI) becomes popular but is still subjected to the relatively high deployment cost. Previous studies overlook the effective placement of MAIs where the geographical distances among them should be fully respected. In this work, we optimize the placement of MAIs where the maximum distances between MAIs are incorporated, which could be regarded as a kind of connectivity constraint. Vehicular users form a virtual fog to get the mobile advertisements when approaching the MAIs. We investigated the interplay between the connected MAIs and vehicular fogs. We found that such kind of deployment could effectively maximize the number of covered vehicular users, which could be modeled with a submodular set function. Unfortunately, the investigated deployment problem is more complicated than traditional maximum submodular set function problem, e.g. the maximum coverage problem. Because it requires all the MAIs could be “virtually connected” to each other and thereby form a connected network. To address aforementioned challenges, this paper introduces a near optimal algorithm, which incorporates an \(O(\sqrt k)\)-approximation algorithm, where k is the number of mobile advertisement infrastructures. To this end, we make extensive experimental studies using synthetic data. Our results show that the proposed algorithm achieves an improved performance, i.e., 40% for typical multi-hop case (e.g. 4 to 8 hops), than the baseline scheme where random selection is applied. In addition, our results show very close performance comparing with the global optimal results achieved by exhaustive search method.