We study the problem of disseminating videos to mobile users by using a hybrid cellular and ad hocnetwork. In particular, we formulate the problem of optimally choosing the mobile devices that will serve as gateways from the cellular to the ad hoc network, the ad hoc routes from the gateways to individual devices, and the layers to deliver on these ad hoc routes. We develop a Mixed Integer Linear Program (MILP)-based algorithm, called POPT, to solve this optimization problem. We then develop a Linear Program (LP)-based algorithm, called MTS, for lower time complexity.

While the MTS algorithm achieves close-to-optimum video quality and is more efficient than POPT in terms of time complexity, the MTS algorithm does not run in real time for hybrid networks with large numbers of nodes. We, therefore, propose a greedy algorithm, called THS, which runs in real time even for large hybridnetworks. We conduct extensive packet-level simulations to compare the performance of the three proposed algorithms. We found that the THS algorithm always terminates in real time, yet achieves a similar video quality to MTS. Therefore, we recommend the THS algorithm for video dissemination over hybrid cellular and ad hoc networks.