In this study, we consider a relay network, with two transceivers and r relay nodes. We assume that each of relays and the two transceivers have a single antenna. For establishing the connection between these two transceivers, we propose a two-way relaying scheme which takes three phases (time slots) to accomplish the exchange of two information symbols between the two transceivers. In the first and second phases, the transceivers, transmit their signals, toward the relays, one after other. The signals that are received by relays are noisy versions of the original signals. Each relay, multiplies its received signal by a complex beamforming coefficient to adjust the phase and amplitude of the signal. Then in the third phase, each relay transmits the summation of so-obtained signals to both transceivers. Our goal is to find the optimal values of transceivers’ transmit powers and the optimal values of the beamforming coefficients by minimizing the total transmit power subject to quality of service constraints. In our approach, we minimize the total transmit power under two constraints. These two constraints are used to guarantee that the transceivers’ receive Signal-to-Noise Ratios (SNRs) are above given thresholds. To solve the underlying optimization problem, we develop two techniques. The first technique is a combination of a two-dimensional search and Second-Order Convex Cone Programming (SOCP). More specifically, the set of feasible values of transceivers’ transmit powers is quantized into a sufficient fine grid. Then, at each vertice of this grid, an SOCP problem is solved to obtain the beamforming coefficients such that for the given pair of transceivers’ transmit powers, the total transmit power is minimized. The pair of the transceivers’ transmit powers, which result in the smallest possible value of the total transmit power, leads us to the solution of the problem. This approach requires a two-dimensional search and solving an SOCP problem at each point of the corresponding two-dimensional grid. Thus, it can be prohibitively expensive in terms of computational complexity. As a second method, we resort to a gradient based steepest descent technique. Our simulation results show that this second technique performs very close to the optimal two-dimensional search based algorithm. Finally we compare our technique with multi-relay distributed beamforming schemes, previously developed in literature and show that our three-phase two-way relaying scheme requires less total power as compared to the two-phase two-way relaying method. On the other hand, the two-phase two-way relaying achieves higher data rates when compared with three-phase two-way relaying for the same total transmit power. Also, we observe that the three-phase scheme has more degrees of freedom while multi-relay distributed beamforming schemes, previously developed in literature appears to be more bandwidth efficient. / UOIT