## 1 Introduction  
Underwater wireless communication and networking have attracted considerable attentions in recent years [1; 2; 3]. They are widely needed in the applications of marine research, oceanography, marine commercial exploitation, mine reconnaissance, tsunami warning, offshore oil industry, defense, etc. [1; 2]. Because acoustic waves are the only known media that can propagate long distances in the water, most of the current underwater wireless communication and networking techniques are based on acoustic signals. However, underwater acoustic channels, which are characterized by limited bandwidth, high and variable propagation delay, time-varying multi-path and fading, and large Doppler spread shift, resulting in high bit error rates and temporary losses of connectivity, creates great challenges for underwater acoustic networking [3]. Because the bandwidth of the underwater acoustic channel is narrow, the transmission rate between two nodes is usually very low in underwater acoustic networks. Therefore, increasing the transmission parallelism among network nodes is one of the most effective ways to improve the underwater acoustic network performance. Three types of parallel transmission opportunities often occur in underwater environments. The first is the time domain parallel transmission opportunity which is caused by the large propagation delay among network nodes. Because the links in the underwater acoustic network usually have large and different delays, multiple packets can be transmitted and propagate in the same channel without interfering with each other at their receivers if their transmission time is carefully scheduled. The second is the space domain parallel transmission opportunity, which is relative to the network topology. Two parts of the networks can send packets simultaneously when they are all located out of the interference regions of each other. The third is the multi-channel parallel transmission opportunity, where the sources and destinations can communicate using multiple parallel channels created by code division multiple access (CDMA) [4] or frequency division multiple access (FDMA) [5]. Usually, parallel transmission is implemented by the medium access control (MAC) techniques. In the contention-free MAC protocols, because CDMA and FDMA can provide each node an independent channel, which means that nodes can send data packets whenever needed, the researches on parallel transmission were mostly focused on time division multiple access (TDMA). Time and space domain parallel transmission opportunities were often used to optimize the TDMA time slot allocation [6; 7; 8; 9; 10; 11; 12]. Because no control information is needed in TDMA, the design of parallel transmission is simplified to the question of static communication resource allocation, which can be efficiently solved by many mathematical tools and methods. In the contention-based MAC protocols, the communication resources are allocated dynamically, so designing a parallel transmission protocol should consider not only the communication resource allocation, but also the control information exchange process. In the single channel contention-based MAC protocol [13; 14; 15; 16; 17; 18; 19; 20; 21], parallel transmission was mainly implemented in time and space domain since there was only one channel. In the multi-channel contention-based MAC protocol [22; 23; 24; 25; 26; 27], parallel transmission can be implemented through multiple channels and most of the attentions were attracted to the channel negotiation mechanism, while time and space domain parallelism were seldom considered. Handshaking is a common technique to reserve the channel for data transmission in contented-based MAC protocols. To implement parallel transmission, the MAC protocol should support multiple successful handshakes in a transmission cycle. In previous research, some handshaking mechanisms have been proposed to handle this problem for the single channel MAC protocols.