## 1 Introduction  
Underwater acoustic sensor networks are extensively used in marine exploration, disaster warning, sea area surveillance, etc. With the progress of sensor technology and the arousal of marine rights and interests of numerous countries, UASN technology has attracted more and more attention from researchers [1, 2, 3, 4]. However, due to the disadvantages of high propagation delay, low bandwidth and low communication rate brought by the high complexity of underwater acoustic channel [5], transmitting/receiving with a traditional half duplex omni-directional transducer will cause serious packet collision. In fact, many studies [6, 7] indicate that a large portion of packet losses are rooted in data conflict, including transmitting/receiving conflict and receiving/receiving conflict [8], which wastes a lot of the very limited energy and reduces the network lifetime.  
Some recent works [9] show that using directional technology can greatly improve network performance; this is because the directional transducer [10] is able to radiate toward a certain direction so as to reach farther at the same power, compared with transducer radiating energy omni-directionally. What is more, a long time pursuit for network spatial reuse is achieved by reducing interference between non-communicating nodes in the network, which benefits from the focusing ability of directional transducer. Eventually, it improves the network lifetime as well as the network traffic.  
In spite of the huge advantages brought by directional technology, new challenges arise. The first and foremost one is the problem of determining the beam direction to make the total network symmetrically connected [11]. A large number of researchers put forward many different optimization goals with the network connectivity as a constraint, such as the minimum latency data aggregation problem [12], network coverage maximization problem [13], power assignment problem [14], etc. In addition, some authors also make many extraordinary creative works to prove their NP property.  
This paper focuses on the challenges that UASNs face with, for example, sound signals attenuate seriously in an underwater environment [15; 16], and nodes of UASNs always have limited energy and are almost impossible to be recharged underwater [17]. Studying the problem of maximizing the network lifetime under the connectivity constraint, we intend to orientate the nodes to be connected with minimum energy consumption, which is formulated to a minimum network cost transducer orientation (MNCTO) problem. The problem is reduced from a Hamiltonian path in a hexagonal grid graph problem (HPHGG) [18] that was proved to be NP-complete.  
The main contributions of our work are as follows:  
1. Based on the tri-modal transducer model, the optimal beamwidth of UASNs stochastically distributed near \(\pi/3\) is analyzed.
2. For UASNs equipped with \(\pi/3\) beamwidth directional transducer, the problem of MNCTO is formulated, which is the first attempt, to the best of our knowledge.
3. The problem of MNCTO is proved to be NP-complete by a reduction from HPHGG.
4. A volume model is introduced to denote the energy radiation, especially for omni-directional and directional models.
5. An \(O(n^{2})\) complexity heuristic greedy algorithm is elaborated to solve the MNCTO problem.  
The rest of the paper is organized as follows: in Section 2, some inspiring related works are introduced; in Section 3, the system model is expounded, including the theoretical analysis of the optimal beamwidth of UADSNs as well as the network model that nodes use to communicate. Then, the problem of MNCTO is formulated, and the NP-complete proof is provided in Section 4; an excellent heuristic algorithm to solve the problem is also elaborated. Next, in Section 5, the simulation evaluations and comparisons are conducted. Finally, the paper is concluded in Section 6.