Minimum Power Route in a Wireless Network Considering Practical Codes

Minimum Power Route in a Wireless Network Considering Practical Codes

Towfik Jemal (Ph D)

Faculty of Electrical and Computer Engineering Jimma Institute of Technology

Abstract Finding the minimum power route in a wireless network is a crucial issue to be addressed. In this paper, Wireless broadcast advantage (WBA) and wireless cooperative advantage (WCA) are exploited separately and jointly for finding a cooperative route in a wireless network with minimum energy consumption considering practical coding and modulation schemes. It assumed that a multi-hop wireless network consisting of nodes with Omni-directional are capable of adjusting their transmit power. For a given route subject to a desired end-to-end throughput and outage probability constraints an optimization problem is formulated so as to allocate minimum sum power. During the resource allocation exploiting WBA and WCA are taken into account separately and together. Then after, optimal and suboptimal route selection is done using a classical Dijkstras algorithm. Turbo codes with iterative decoding algorithms are implemented with various QAM modulation schemes.

KeywordsBroadcasting; Beamforming; Minimum Energy; Turbo Codes

1. INTRODUCTION

   Because of the reason that nodes in a wireless mesh network are mostly driven by battery power, efficient utilization of energy is a crucial issue that needs to be addressed. It is obvious that significant energy savings can be achieved in a cooperative transmission scheme where multiple nodes transmit cooperatively in one time slot forming a virtual antenna array. To further increase this energy savings, the broadcast nature of the wireless medium is exploited. There exist several publications that propose optimal and suboptimal routing algorithms considering distributed beamforming (WCA) and the wireless broadcast advantage (WBA). However, all of the proposed routing algorithms exploit either distributed beamforming [1] – [4] or the wireless broadcast advantage [5], [6]. Moreover, ideal capacity achieving codes are always assumed. In this paper, the performance of an optimal algorithm that exploits both the wireless broadcast advantage (WBA) and distributed beamforming (WCA) is compared with the optimal algorithm that exploits either distributed beamforming [1]-[4] or the wireless broadcast advantage (WBA) [5], [6]. In this paper, the problem of minimum power cooperative routing in a wireless mesh network considering both distributed beamforming and wireless broadcast advantage for practical coding and modulation schemes is analyzed. Classical turbo codes with iterative decoding algorithm are used to generate the frame error rate (FER) curve for a single link from which the threshold SNR for the given code rate and the outage probability are obtained.

   The rest of this paper is organized as follows. System model is presented in Section 2. In Section 3, the exploited wireless nature is discussed. In section 4 the optimization problem is formulated. Optimal and suboptimal route selections are described in Section 5. Section 6 presents simulation results and discussion for the proposed algorithms. Finally, concluding remarks are given in Section 7.

2. SYSTEM MODEL

   In this paper, a set of N nodes V = 1, …,N equipped with a single omni-directional antenna and located in a square of unit width are considered. The source node 1 is positioned in the bottom-left corner at coordinate (0, 0), the destination node N is placed in the top-right corner at position (1, 1). The rest of the nodes are positioned randomly. An exemplary topology with N = 6 nodes is illustrated in 1. We assume that source node 1 wants to transmit messages to the destination node through a cooperative route that consumes minimum power. This paper investigates the benefits of transmitting to other nodes first and transmitting cooperatively to some further nodes afterwards until the message has been received successfully at the destination.

   Figure 1. Wireless Network Topology with N = 6

   A cooperative route r is defined by an ordered set T (r) N, where the first element of each route is always the source node. For every route r, there exists a set R (r) N which is complementary to T (r). Nodes from this set can be appended to the existing route to create a new one. The transmission

   along a route r is divided into L = |T(r)|1 equally long time slots and identical codes are applied in each time slot. Exclusive channel access is ensured by a Time Division Multiple Access (TDMA) scheme, i.e. all nodes transmit in individual time slots. We define the subset T (r) t T (r) containing the nodes which are transmitting in time slot t. Moreover, the transmission from source to destination is restricted such that no matter how many hops N(r) hops a route has, the overall throughput from source to destination is determined by

   (1)

   This shows that, the code rate R(r)c to be chosen on each link on route r depends on the number of hops and the throughput constraint th.

   The signal transmitted by node i on a route r and received at node j is given by

   (2)

   where hj;i is the channel coefficient between nodes i and j and given by hj,i ~CN(0,j,i-) for quasi-static Rayleigh fading. The variance depends on the distance of the link j,i and the path loss exponent . xi is the transmitted signal with unit power and nj ~N(0, 1) is AWGN at the receiver normalized to unit power. It is assumed that there is a perfect synchronization of overheard signals at the receiving nodes. Furthermore, it is assumed that the channel state information of the network are known by a central node responsible to determine the resource allocation of each node on a route and searching a cooperative route with minimal power consumption.

3. EXPLOITATIN OF WIRELESS NATURE

   This paper tried to exploit the exiting nature of wireless communication in order to minimize total consumed power for transmission. Two techniques namely called wireless broadcast advantage and distributed beamforming analyzed.

   1. Exploiting Distributed Beamforming (WCA)

      t

      In distributed beamforming, multiple nodes along the path are allowed to simultaneously transmit to the next hop in order to reach the desired/required SNR with lower power consumption. The received signal at a node j from all transmitting nodes i T (r) can be determined by

      (3)

      To correct phase rotation at the transmitter by the pre-coding factor j,i including transmit power at node i in time slot t, it is assumed that channel coefficient is known at the transmitter.. From 3 the SNR increment j,t (r) is given by

      (4)

      t

      In 3 and in 5 the WCA is exploited due to the superposition of all transmit signals from nodes i T (r) . However, the simple case of applying no beamforming is also included if the number of transmitting nodes in a time slot is restricted to one.

   2. Exploiting Wireless Broadcast Advantage (WBA)

      In general, we assume that all nodes are able to store received signals from previous time slots and, thus, exploit the WBA. Owing to the wireless medium all nodes overhear all the transmissions even if a particular node is not the addressed receiver. Thus, the so far overheard signals at node j is given by

      (5)

      Hence, due to repetition coding maximum ratio combining (MRC) can be applied, that is, the SNR from different time slots simply sums up. The SNR increments j,t(r) correspond to an overheard transmission at node j in time slot t. Then,

      (6)

      is the so far overheard and accumulated SNR at node j after time slot t.

   4. Exploiting WCA and WBA Jointly

      If the wireless broadcast advantage (WBA) and distributed beamforming (WCA) are exploited jointly, the overheard signals due to the simultaneous transmission of multiple nodes

      are needed. Thus, the overheard signals in time slot t at node j due to the simultaneous transmissions by all nodes i Tt(r) to an intended node l is given by

      With

      and its corresponding incremental SNR as

      (7)

      (8)

      The only difference of (7) and (8) to (5) and (6) is that the pre-coding factor is not adjusted to the channel coefficient, and thus, (9) cannot be simplified.

   5. Practical Scenario

   out

   Due to (1), the code rate for each link is given by the number of hops on the route. From information theory it is well known that a successful transmission with Rc = Cj,i is possible with capacity achieving codes, where Cj,i = log2(1 + th) is the capacity of a link between nodes i and j. Thus, a specific threshold SNRth is directly given by the code rate. However, practical codes with finite lengths do not achieve the channel capacity, and thus, a residual error probability remains. For a given route, the outage probability of a route r, P (r) is defined as the probability that the transmission over a route

   transmitted over an AWGN channel to get the received sequence y. From the sequence y a demapper generates log- likelihood ratios for a BCJR decoder embedded in a serial turbo decoder which decides the information sequence u after 8 iterations. By comparing u and u after 4000 transmissions an average FER can be computed.

4. PROBLEM FORMULATION

   In this section, an optimization problem for resource allocation is formulated. The objective here is to allocate minimum power for each node on a route r in time slot t considering the wireless broadcast advantage (WBA) or wireless cooperative advantage (WCA) or both. Thus, the optimization problem is formulated as

   (11)

   is

   (12)

   fails. The outage probability of a link e on a route r, P

   (r,e) out

   defined as the probability that a transmission over that link fails. From the given outage probability of a route, the outage probability of a link e is derived from

   (9)

   It is assumed that the outage probability of each channel is the same. This assumption is reasonable because power will

   (13)

   (14)

   j,t-1

   where Pout is the maximum outage probability. Constraint 14 ensures that the outage probability of a route is below the maximum outage probability. This optimization problem can be used for the case where WCA or WBA or both are considered to address the problem of minimum power allocation except that constraint 13 has to be modified for

   be allocated later for the channels based on their channel

   WCA such that the term

   (r) is set to zero. Furthermore, the

   coefficients. Furthermore, this assumption simplifies the

   term

   (r) in time slot t is known when WBA and

   j,t-1

   mathematical analysis associated with outage probability of a link. Thus, the outage probability of a link is given by

   (10)

   Next, we have chosen the well-known third rate Turbo Code which is used in UMTS and LTE [7] to determine the FER curves where the threshold SNRth(r) for a route r is obtained from. Threshold SNRth(r) is defined as a minimum SNR required for successful transmission. Threshold SNRth(r) is obtained from the FER curves using the code rate (1) and the outage probability of a link (10). According to (1) routes with different number of hops requires different code rate for fixed end-to-end throughput th. To get a variety of different symbol rates, we have combined 8 different code rates Rc applying puncturing with different regular QAM modulation schemes up to m = 6 bits per symbol. For all combinations, Monte Carlo simulations have been carried out with the following parameters.

   First, a 8640 bit long information sequence u is generated and encoded. Afterwards, puncturing is applied to achieve the different code rates Rc. The used puncturing patterns can be found in table 2 of [8] in the last row. Finally, the encoded sequence c is mapped on the symbol sequence x and

   WBAWCA are considered.

   The resource allocation for the considered WBA, WCA, and WBA-WCA is described next. If WCA is exploited, the optimal power allocations for the above convex optimization problem is determined by applying the Lagrangian multiplier technique [1]. Accordingly the optimal power allocation for WCA is computed as

   (15)

   For the case where WBA is considered, a transmitting node in one time slot allocates power for the missing SNR at the target receiving node. Thus, the power allocation is computed by

   (16)

   j,t-1

   Where (th(r) – (r)) is the missing SNR at node j. If both WBA and WCA are considered, the minimum power allocation is done according to

   (21)

   (17)

5. OPTIMAL AND SUBOPTIMAL ROUTE SELECTION

   If the minimum power allocation for each node in each time slot t is done according to 16 for WCA, according to 17 for WBA and according to 18 for WCA-WBA, then the total power consumed by a route r is computed as

   (18)

   for WBA and as

   Abbreviation	Description
   OptNonCoop	Optimal non-cooperative
   OptCR	Optimal route that exploit WCA
   OptBR	Optimal route that exploit WBA
   OptCBR	Optimal route that exploit WBA and WCA
   SubOptCBR(Non Coop)	Suboptimal with WBA and WCA OptNoncoop
   SubOptCBR(W CA)	Suboptimal with WBA and WCA OptCR
   SubOptCBR(W BA)	Suboptimal with WBA and WCA OptBR

   (19)

   TABLE I. LIST OF ABBREVIATION OF ALGORITHMS

   for WCA and WCA-WBA. Once the total power consumed by a route is known 19 and 20, Dijkstra algorithm [9] is implemented to exhaustively search the optimal cooperative route between a given source and destination nodes. Hence, we have defined three optimal algorithms in addition to the optimal non-cooperative routing algorithm (OptNonCoop): OptBR is an algorithm that selects the optimal route if WBA is considered, OptCR is an algorithm that searches an optimal route if WCA is considered, and OptCBR is an algorithm for finding the optimal route if both WBA and WCA are considered. Furthermore, suboptimal algorithms are proposed with reduced computational complexity. WBA and WCA applied on the optimal route exhaustively searched by OptNonCoop, OptBR, and OptCR to obtain a sub-optimal route SubOptCBR(NonCoop), SubOptCBR(WBA), and Sub- OptCBR(WCA), respectively.

   1. RESULT AND DISCUSSION

      This section presents the numerical results of the proposed optimal and suboptimal algorithms. The performance of all the algorithms will be measured relative to the optimal noncooperative route power and it is given by

      where alg represent optimal and suboptimal algorithms described in the previous sections. It is assumed that the noise variance is set to 2 = 1. The simulation is performed in a network environment where the path loss exponent is = 2 and = 4. It is assumed that the outage probability of a route is set to Pout = 0:1 and the end-to-end throughput is set to th = 0.85. These assumptions are made in such a way that the required curves can be found on the FER. Figure 3 and Figure 4 show the simulation result of the optimal and suboptimal routing algorithms with path loss exponent = 2 and

      N

      = 4, respectively. As it can be observed from both figures, the gain obtained from an algorithm that exploits both WBA and WCA is the highest compared to the optimal non- cooperative route. The gain difference between OptBR and OptCR indicate that an array gain obtaine by distributed beamforming is superior in terms of power saving compared to energy collection due to broadcasting. It can also be observed that the optimal OptCR route in most cases is the same as the optimal route obtained by OptCBR. This observation is drawn from the figure that, if WBA is applied on the optimal OptCR route, a result close to the optimal OptCBR algorithm is obtained. Thus, it is not reasonable to spend an increased effort for a route search that considers both WBA-WCA since applying WBA on the optimal OptCR route provides a result close to the optimal OptCBR algorithm. Furthermore, in most of the case the optimal non-cooperative route is not the shortest path in the wireless mesh network.

      The simulation result on Figure 2 shows the position of relay node where which algorithm is beneficial in terms of power consumption. As can be seen from the figure, for a bad channel between relay and destination node compared to source-relay channel, distributed beamforming provides an array gain which is superior to MRC of a noisy signals. That is, the energy collected by the destination node due to the broadcast transmission of source node to relay node is minimal as compared an array gained obtained by distributed beam forming. However, if the relay-destination channel is good as compared to source-relay channel, collecting energy by exploiting WBA with MRC performs better.

      Figure 2. Performance of OptCR and OptBR for a three node network

      Figure 3. Average power gain for practical codes with

      = 2

      Figure 4. Average power gain for practical codes with

      = 4

      Figure 3 and Figure 4 show the simulation result of the optimal and suboptimal routing algorithms with path loss exponent = 2 and = 4, respectively. As it can be observed from both figures, the gain obtained from an algorithm that exploits both WBA and WCA is the highest compared to the optimal non-cooperative route. The gain difference between OptBR and OptCR indicate that an array gain obtained by distributed beamforming is superior in terms of power saving compared to energy collection due to broadcasting. It can also be observed that the optimal OptCR route in most cases is the same as the optimal route obtained by OptCBR. This observation is drawn from the figure that, if WBA is applied on the optimal OptCR route, a result close to the optimal OptCBR algorithm is obtained. Thus, it is not reasonable to spend an increased effort for a route search that considers both WBA-WCA since applying WBA on the optimal OptCR route provides a result close to the optimal OptCBR algorithm. Furthermore, in most of the case the optimal non-cooperative route is not the shortest path in the wireless mesh network.

      Figure 5. Average power gain for practical and ideal codes with = 2

      Figure 6. Average power gain for practical and ideal codes with = 4

      Figure 5 and Figure 6 depict the simulation results of the optimal routing algorithms for practical and ideal coding schemes for a path loss exponent of = 2 and = 4, respectively. The dashed lines show the simulation results for ideal coding scheme while the solid lines show results for practical coding and modulation scheme. As it is expected the performance of the algorithms for practical network scenario is lower than the ideal coding scheme.

   2. CONCLUSIONS

This paper addresses the problem of finding a cooperative route with minimal power consumption in a wireless mesh network where practical coding and modulation schemes are used. The potential of distributed beamforming and wireless broadcast advantage in reducing power consumption is analyzed.

Exploiting the wireless broadcast advantage and distributed beamforming jointly provides a gain better than exploiting distribute beamforming [1] and the wireless broadcast advantage [6] separately. Furthermore, it is reasonable to use the suboptimal solution obtained by applying both WBA and WCA on the optimal route that exploits WCA only. This is because a result very close to the optimal WCA-WBA route is obtained with reduced computational effort.

REFERENCES

1. A. E. Khandani, E. Modiano, L. Zheng, and J. Abounadi, Cooperative routing in static wireless networks, IEEE Transactions on Communications, vol. 55, No. 11, pp. 2185- 2192, November 2007.

2. F. Li, K. Wu, and A. Lippman, Energy-efficient cooperative routing in multi-hop wireless ad hoc networks, in Proc. IEEE International Performance, Computing, and Communications Conference, pp. 215- 222, April 2006.

3. A. Ibrahim, Z. Han, and K. Liu, istributed Energy-Efficient cooperative routing in wireless networks, in Global Telecommunications Conference, 2007. GLOBCOM 07. IEEE, pp. 4413-4418, November. 2007.

4. A. M. Akhtar, M. R. Nakhai, and A. H. Aghvami, Power Aware Co- operative Routing in Static Wireless Networks, Communications Letter, vol. 16, pp. 670-673, 2012.

5. J. Wieselthier, G. Nguyen, and A. Ephremides, Algorithm for Energy Efficient Multicasting in Ad Hoc Wireless Networks, in Military Communications Conference Proceedings. MILCOM 1999. IEEE, vol. 2, pp. 1414-1418, 1999.

6. I. Maric and R. Yates, CooperativeMultihop Broadcast for Wireless Networks, IEEE Journal on Selected Areas in Communication, vol. 22, No. 6, pp. 1080-1088, August 2004.

7. A. Neubauer, J. Freudenberger, and V. Kuehn, Coding theory: Algorithms, Architectures and Applications, John Wiley and Sons, November 2007, ISBN-10: 0470028610.

8. J. Li, Q. Chen, S. Gao, Z. Ma and P. Fan, The Optimal Puncturing Pattern Design for Rate-Compatible Punctured Turbo Codes, International Conference on Wireless Communications and Signal Processing. WCSP 2009, November 2009.

9. E. W. Dijkstra, A Note on Two Problems in Connection with Graphs, Numerische Mathematik 1, pp. 269271, 1959.

10. T. J. Ali, V. Kuehn, Exploiting Wireless Broadcast Advantage for Routing in Static Networks, 9th International ITG Conference on Systems, Communications and Coding (SCC2013), Munich, Germany, January 2013.

11. A. Ibrahim, Z. Han, and K.Liu, Distributed energy-efficient cooperative routing in wireless networks., In Global Telecommunications Conference, 2007. GLOBECOM 07., November 2007.

12. C. Pandana, W. P. Siriwongpairat, T. Himsoon, and K. J. R. Liu , Distributed cooperative routing algorithms to maximizing network lifetime, In Proc. IEEE Wireless Communications and Networking Conference (WCNC06), volume 1, 2006.

13. E. Liu, Q. Zhang, and K. Leung , Residual energy-aware cooperative transmission (react) in wireless networks, In in Wireless and Optical Communications Conference (WOCC), 2010 19th Annual, page 16, May 2010.

Towfik Jemal received B.Sc. degree in electrical engineering from Bahirdar University, Bahirdar, Ethiopia, in 2001 and the M.Sc. degree in computer engineering from Delhi University, New Delhi, India, in 2005, and the Ph.D. degree in wireless communication engineering from Rostock University, Rostock, Germany, in 2014. Since 2001, he has been with the department of Electrical and Computer Engineering, Jimma University, Jimma, Ethiopia. He is also currently working as a directorate of Research and publication office of Jimma Institute of Technology, Jimma University. His research interests include wireless communication, information theory, resource optimization for wireless networks, routing protocols, sensor networks, and AD HOC networks.