LAUSR

One viable and low-cost method of accommodating the explosive growth of mobile broadband traffic is to introduce small cells for next-generation cellular networks. However, static small cells cannot be flexibly placed to meet the demand of time/space-varying traffic, and idle or under-utilized cells would result in a waste of resources and system performance degradation. This study adopts the mobile small-cell concept and seeks to optimize the deployment of mobile small cells to maximize service time. Service time maximization exhibits an interesting tradeoff between user density and the travel time of mobile small cells. We prove that our target problem is $\mathcal {\text{NP}}$-hard and cannot be approximated in polynomial time with a ratio better than $(1 - \frac{1}{e})$ , unless $\mathcal {P} = \mathcal {\text{NP}}$ . To solve the problem, we propose a polynomial time $(1 - \frac{1}{e})$-approximation algorithm, and the proposed algorithm is one of the best approximation algorithms based on the inapproximability ratio. We also construct a series of simulations with realistic parameter settings to evaluate the performance of our proposed algorithm and to provide useful insights into mobile small-cell deployment.