  This paper investigates optimal scheduling for a cognitive multi-hop
underwater acoustic network with a primary user interference constraint. The
network consists of primary and secondary users, with multi-hop transmission
adopted for both user types to provide reliable communications. Critical
characteristics of underwater acoustic channels, including significant
propagation delay, distance-and-frequency dependent attenuation, half-duplex
modem, and inter-hop interference, are taken into account in the design and
analysis. In particular, time-slot allocation is found to be more effective
than frequency-slot allocation due to the underwater channel model. The goal of
the network scheduling problem is to maximize the end-to-end throughput of the
overall system while limiting the throughput loss of primary users. Both
centralized and decentralized approaches are considered. Partially Observable
Markov Decision Processes (POMDP) framework is applied to formulate the
optimization problem, and an optimal dynamic programming algorithm is derived.
However, the optimal dynamic programming solution is computationally
intractable. Key properties are shown for the objective function, enabling the
design of approximate schemes with significant complexity reduction. Numerical
results show that the proposed schemes significantly increase system throughput
while maintaining the primary throughput loss constraint. Under certain traffic
conditions, the throughput gain over frequency-slot allocation schemes can be
as high as 50%.
