  Motivated by the regular service requirements of video applications for
improving Quality-of-Experience (QoE) of users, we consider the design of
scheduling strategies in multi-hop wireless networks that not only maximize
system throughput but also provide regular inter-service times for all links.
Since the service regularity of links is related to the higher-order statistics
of the arrival process and the policy operation, it is highly challenging to
characterize and analyze directly. We overcome this obstacle by introducing a
new quantity, namely the time-since-last-service (TSLS), which tracks the time
since the last service. By combining it with the queue-length in the weight, we
propose a novel maximum-weight type scheduling policy, called Regular Service
Guarantee (RSG) Algorithm. The unique evolution of the TSLS counter poses
significant challenges for the analysis of the RSG Algorithm.
  To tackle these challenges, we first propose a novel Lyapunov function to
show the throughput optimality of the RSG Algorithm. Then, we prove that the
RSG Algorithm can provide service regularity guarantees by using the
Lyapunov-drift based analysis of the steady-state behavior of the stochastic
processes. In particular, our algorithm can achieve a degree of service
regularity within a factor of a fundamental lower bound we derive. This factor
is a function of the system statistics and design parameters and can be as low
as two in some special networks. Our results, both analytical and numerical,
exhibit significant service regularity improvements over the traditional
throughput-optimal policies, which reveals the importance of incorporating the
metric of time-since-last-service into the scheduling policy for providing
regulated service.
