Wireless communications over water may suffer from serious multipath fading due to strong specular reflections from conducting water surfaces. Cognitive radios enable dynamic spectrum access over a large frequency range, which can be used to mitigate this problem. In this paper, we study how to leverage cognitive radios for effective communications in wireless networks over water. We formally define the studied problem as the OVErwater Radio-Time Scheduling (OVERTS) problem which seeks a radio channel with time schedule such that the total of assigned eligible time slots, in which a " good " communication link is maintained between every Mobile Station (MS) and the Base Station (BS), satisfies the time slots requirement of each MS. Two effective heuristic algorithms are presented for the OVERTS problem. Simulation results are presented to justify the performance and efficiency of our proposed scheduling algorithms.