  Caching popular files at user equipments (UEs) provides an effective way to
alleviate the burden of the backhaul networks. Generally, popularity-based
caching is not a system-wide optimal strategy, especially for user mobility
scenarios. Motivated by this observation, we consider optimal caching with
presence of mobility. A cost-optimal caching problem (COCP) for
device-to-device (D2D) networks is modelled, in which the impact of user
mobility, cache size, and total number of encoded segments are all accounted
for. Compared with the related studies, our investigation guarantees that the
collected segments are non-overlapping, takes into account the cost of
downloading from the network, and provides a rigorous problem complexity
analysis. The hardness of the problem is proved via a reduction from the
satisfiability problem. Next, a lower-bounding function of the objective
function is derived. By the function, an approximation of COCP (ACOCP)
achieving linearization is obtained, which features two advantages. First, the
ACOCP approach can use an off-the-shelf integer linear programming algorithm to
obtain the global optimal solution, and it can effectively deliver solutions
for small-scale and mediumscale system scenarios. Second, and more importantly,
based on the ACOCP approach, one can derive the lower bound of global optimum
of COCP, thus enabling performance benchmarking of any suboptimal algorithm. To
tackle large scenarios with low complexity, we first prove that the optimal
caching placement of one user, giving other users' caching placements, can be
derived in polynomial time. Then, based on this proof, a mobility aware
user-by-user (MAUU) algorithm is developed. Simulation results verify the
effectivenesses of the two approaches by comparing them to the lower bound of
global optimum and conventional caching algorithms.
