STiCMAC: A MAC Protocol for Robust Space-Time Coding in Cooperative Wireless LANs

Relay-assisted cooperative wireless communication has been shown to have significant performance gains over the legacy direct transmission scheme. Compared with single relay based cooperation schemes, utilizing multiple relays further improves the reliability and rate of transmissions. Distributed space-time coding (DSTC), as one of the schemes to utilize multiple relays, requires tight coordination between relays and does not perform well in a distributed environment with mobility. In this paper, a cooperative medium access control (MAC) layer protocol, called \emph{STiCMAC}, is designed to allow multiple relays to transmit at the same time in an IEEE 802.11 network. The transmission is based on a novel DSTC scheme called \emph{randomized distributed space-time coding} (\emph{R-DSTC}), which requires minimum coordination. Unlike conventional cooperation schemes that pick nodes with good links, \emph{STiCMAC} picks a \emph{transmission mode} that could most improve the end-to-end data rate. Any station that correctly receives from the source can act as a relay and participate in forwarding. The MAC protocol is implemented in a fully decentralized manner and is able to opportunistically recruit relays on the fly, thus making it \emph{robust} to channel variations and user mobility. Simulation results show that the network capacity and delay performance are greatly improved, especially in a mobile environment.

fading environment. While utilizing multiple relays at the PHY layer greatly improves the reliability of transmissions, it remains unclear how such techniques can be employed to deliver significant network capacity gains for a loosely synchronized network such as the IEEE 802.11.
In this paper, we design a robust MAC layer protocol called STiCMAC (Space-Time coding for Cooperative MAC), which is compliant with the IEEE 802.11 standard and enables R-DSTC based cooperation. STiCMAC allows one to harvest cooperative diversity from multiple nodes in a decentralized manner. In this scheme, if a data packet from the source needs to be relayed, all potential relays listen to the transmission from the source and try to decode. Assuming error detection mechanisms such as cyclic redundancy check (CRC) are employed at the relays, only relays that successfully decode the packet forward to the destination in unison using R-DSTC. In order to do so, the handshaking procedure defined by the IEEE 802.11 standard is extended to allow relays be recruited in an opportunistic manner while ensuring that the transmissions from multiple relays are collision free.
The main contribution of this paper is that it fundamentally changes the way cooperation is established.
Instead of picking nodes with fast links or finding a fast path in the network, our scheme picks a transmission mode (modulation, channel coding and STC) that could most improve the end-to-end rate on the average. Relays decide to participate or not to participate independently based on whether they receive the packet or not. In fact, neither the source or destination station need to know who the relays are or where they are located. STiCMAC is an optimized PHY/MAC cross-layer scheme that can be implemented in a fully decentralized manner and is able to opportunistically recruit relays on the fly at minimum signaling cost for an infrastructure-based IEEE 802.11 network. We evaluate the system performance of STiCMAC, and employ cross-layer optimization to find suitable transmission parameters, i.e., per-hop rates and STC dimension, that maximize the end-to-end rate.
Optimization of transmission parameters is performed assuming either a complete knowledge of average channel statistics for both hops, or simply considering the number of stations in each WLAN cell. We call these two approaches STiCMAC with channel statistics (STiCMAC-CS) and STiCMAC with user count (STiCMAC-UC) respectively. We investigate the aggregated network throughput and the average delay for all stations in both a static and mobile environment. Our results suggest that both STiCMAC-CS and STiCMAC-UC have similar performance, especially for a large number of users. This outcome strongly supports our argument that the proposed scheme does not need a priori knowledge of channel conditions, as opposed to DSTC. Additionally, simulation results show that both types of STiCMAC significantly outperform DSTC in terms of throughput and delay, due to lower signaling cost, and also outperform CoopMAC and direct transmission due to increased diversity. While the performance of DSTC and CoopMAC significantly decreases under mobility, STiCMAC is more robust, and in particular STiCMAC-UC shows minimal performance degradation in a mobile environment. Finally, we conduct a study of the interference propagated to neighboring wireless LANs for all transmission schemes. Simulation results show that, for the same traffic load, the average interference generated by STiCMAC is similar to DSTC, and much less than CoopMAC and direct transmission.
A related work [8] proposes a MAC layer protocol that deploys DSTC in an ad hoc network to assist network layer routing. This allows cooperative transmissions from multiple relays, however, its performance and practicality for a mobile network are still limited due to the limitations of DSTC outlined above. Opportunistic routing [9] is a routing protocol for ad hoc networks that allows one node closest to the destination to forward in case multiple nodes receive from the previous hop. Compared with STiCMAC, which operates in MAC/PHY cross-layer, opportunistic routing operates in the network layer. The other difference is that STiCMAC allows an end-to-end multihop transmission within a single channel access and queuing is not necessary at the relays. STiCMAC also allows signals from multiple relays to be combined coherently in the PHY layer. Another use of the term "opportunistic" appears in the cooperative communications literature in [10], however, the notion there is to select relays based on instantaneous channel state. Generic MAC protocols for R-DSTC are designed in [11], [12], where transmission parameters are optimized given the bit error rate, assuming no channel coding is employed.
Without forward error correction coding, those schemes can cause error propagation by allow relays to forward even if erroneous packets are received. These papers mostly focus on the PHY layer characteristics that enable the use of randomized codes in realistic wireless networks, and do not explicitly investigate MAC layer details. STiCMAC is the first protocol derived from the IEEE 802.11 where practical MAC layer aspects of randomized cooperation are addressed.
We note that synchronization is an important issue for all transmission schemes that allow multiple stations to transmit at the same time on the same frequency. As demonstrated in [13], symbol level synchronization in DSTC based transmission is feasible on a software defined radio platform with commercially available IEEE 802.11 components and a customized FPGA. Thus we believe necessary synchronization for R-DSTC, which is more robust to synchronization errors than DSTC [14], can also be implemented.
The rest of this paper is outlined as follows. Section II introduces the PHY layer background for R-DSTC. In Section III, we present the STiCMAC protocol in detail. Section IV develops two opportunistic rate adaptation schemes for STiCMAC to optimize the transmission parameters. Section V presents the simulation results and the performance evaluation. Finally, in Section VI, we present conclusions.

II. R-DSTC PHYSICAL LAYER DESCRIPTION
An STC is designed to operate over several antennas at the same transmitter station. In contrast, DSTC employs an STC over multiple relays in a distributed manner. When these relays cooperatively forward a signal, each relay corresponds to a specific antenna element of the underlying STC, and transmits a predefined STC encoded stream. The advantage of DSTC lies in its capability to form a virtual MIMO system by using these relays and producing diversity gain, even if each station is only equipped with one antenna. The performance of DSTC and the diversity gain obtained has been studied in [3].
R-DSTC is introduced and examined in [5] as a novel form of DSTC. Like conventional DSTC, R-DSTC is deployed in a cooperative scenario with multiple relays along with a source and destination pair and operates over two hops. Although R-DSTC can be employed using relays with multiple antennas, we assume that each station is only equipped with a single antenna. The scenario with multiple antennas per station can be easily extended from the single-antenna case. Fig. 1 shows a single-antenna relay that employs a regular single-input and single output (SISO) decoder to decode the information sent by the source station in the first hop. Provided the information is decoded correctly, as determined by checking the CRC field, the relay is responsible for re-encoding the information bits and passing them to an STC encoder. Suppose the underlying space-time codeword has a dimension L × K, where L is the number of antennas and K is the block length transmitted by each antenna. The STC encoder generates an output of L parallel streams, each stream corresponding to an antenna. Unlike a regular DSTC where the jth relay simply transmits the stream j, in a R-DSTC system the jth relay transmits a linear weighted combination of all L streams. The weights of the L streams at the jth relay are denoted by a vector w j = [w j1 w j2 . . . w jL ]. Each element in w j is an independently generated random variable with zero mean and variance 1/L. As described in [5], a complex Gaussian distribution is adopted for the distribution of the weights since it has desirable properties in terms of PHY layer error rates. Assuming n relays simultaneously transmit in the second hop, the vector w j , where j = 1, 2, . . . n, represents the random weights at relay j and R = [w 1 , w 2 , . . . , w n ] T is the weight matrix for all these n relays. The destination station is assumed to have one antenna and is able to decode the received signal with a conventional STC decoder.
The physical layer fundamentals of R-DSTC is described in detail in [5], where it is shown that R-DSTC comes very close to the performance of DSTC in terms of PHY layer properties and can provide the full diversity order of L with at least L relays. A major advantage of the R-DSTC technique over DSTC lies in the fact that the source station does not need to specifically select its relays as well as to assign antenna indices to each relay. In R-DSTC, the source and destination remain unaware of which stations act as relays and which random weight vector has been used in relays. These features enable R-DSTC to be a fully decentralized scheme in a cooperative environment.

III. STIC MAC: A ROBUST COOPERATIVE MAC LAYER FRAMEWORK
While R-DSTC has been mainly studied in the PHY layer, an efficient MAC layer protocol is essential in order to enable its use in a real environment and to translate its PHY layer benefits to performance gain in the upper layers. This section presents a robust MAC layer protocol, called Space-Time coding in Cooperative MAC (STiCMAC), in support of R-DSTC in an IEEE 802.11 WLAN environment. In this paper, we consider a WLAN operating in the infrastructure mode, where an access point (AP) works as a central unit. The proposed MAC protocol is mainly composed of two parts: (1) a three-way handshake, which includes relay recruiting and acknowledgements; (2) cooperative two-hop data transmission. The three-way handshaking takes care of all signaling among the source, destination and relays. During the handshaking procedure, relays are recruited simultaneously and opportunistically according to each relay's instantaneous channel conditions, while no other stations, except for the selected relays, needs to know these channel conditions. Cooperative two-hop data transmission occurs when relays receive the necessary transmission parameters. The details of STiCMAC are explained in the rest of this section.

A. Wireless LAN Medium Access Control Overview
In the IEEE 802.11 WLAN standard [15], Distributed Coordination Function (DCF) is the mandatory MAC protocol. Since DCF is contention based, stations employ carrier sensing multiple access/collision avoidance (CSMA/CA) algorithm to resolve collisions. Under this scheme, each station can starts a packet transmission only if it senses the channel to be free. However, due to sensing range limitations, two stations could be sending to a common receiver simultaneously. This phenomena is referred to as the hidden node problem. In order to avoid such scenarios, virtual carrier sensing is employed, by means of the Request-to-Send (RTS) and Clear-To-Send (CTS) frames. These two control frames broadcast the duration for the upcoming data transmission so that stations that do not participate in this transmission withhold their own transmissions until the end of the ongoing packet transmission. In this paper, we focus on the DCF mode with RTS/CTS messaging and develop a cross-layer framework for a distributed cooperative system based on IEEE 802.11. STiCMAC with RTS/CTS turned off is presented in the appendix of this paper.

B. Protocol Design for R-DSTC in WLANs
In this subsection, we introduce the STiCMAC protocol that enables R-DSTC in an infrastructure-based WLAN under DCF mode. STiCMAC enables relay discovery and concurrent cooperative transmissions from all relays to the destination. Without loss of generality we consider that the source of a transmission is a station while the destination is the AP. A symmetric scheme with the same characteristics can be applied for the downlink transmission (from the AP to the stations).
In order to enable all relays to forward a packet in unison, the MAC layer needs to provide critical parameters for the cooperative transmission. The required transmission include the transmission rates for both hops, and the underlying space-time code for the second hop. Let us denote r 1 as the first-hop rate, r 2 as the second-hop rate, and L as the STC dimension. We assume that R-DSTC uses a class of underlying orthogonal STC's parameterized by the code dimension L. A proper joint selection of these parameters can optimize the MAC layer performance. Details of such an optimization will be provided in Section IV. Additionally, the MAC layer must also provide timing information for both hops, as a data packet undergoes a two-hop transmission. In STiCMAC, a three-way handshaking procedure is initiated by the source to disseminate these transmission parameters, followed by the data transmission. Fig. 2 illustrates how STiCMAC works for a single packet transmission, which consists of the following steps: a. The Three Way Handshaking Phase 1) The source station initiates the handshaking by transmitting a RTS frame at the base rate in compliance with the IEEE 802.11 protocol. The RTS frame reserves the channel for subsequent signaling and data messages. The source continues with the transmission of the second control frame, called Helper-Recruiting (HR) frame, a short inter-frame spacing (SIFS) period after the transmission of the RTS frame. This HR frame is transmitted at the chosen first-hop rate r 1 using a corresponding physical layer modulation level and channel coding rate. Only those stations that have a channel strong enough to decode the HR message are likely to receive the subsequent data packet correctly at the same rate. Thus, all stations receiving the HR frame correctly are recruited as relays for the current data packet forwarding. Since recruiting of the relays is conducted on the fly, this procedure is fully decentralized. The exact set of recruited relays may vary from packet to packet due to channel variations or mobility, enabling fully opportunistic use of relays. The HR frame contains the underlying STC dimension L and the hop-2 rate r 2 , which is characterized by a modulation scheme and channel coding rate.
2) A SIFS time after the HR frame, the recruited relays send in unison the helper-to-send (HTS) frame using R-DSTC. The transmission is at the second-hop rate r 2 , using an STC of size L. The HTS message is jointly transmitted by all relays that successfully decoded the HR message from the source station. Since a single STC is employed by all the relays, only a single HTS message is received and decoded by the destination station without causing a collision. The HTS frame is employed for the following reasons. Firstly, it is used as an acknowledgement to the source station that one or more relays have been recruited. Secondly, the destination station, as long as it receives the HTS frame correctly, can verify that those relays can indeed support a rate r 2 transmission to the destination, even though it doesn't explicitly know which stations act as relays. Thirdly, HTS frame helps to alert the hidden terminals around the relays and avoid a possible collision.
3) The destination responds with a CTS frame, which signals the end of the three-way handshaking among all participants. The above handshaking procedure reduces the likelihood of a data packet collision which is especially in the case of a long data packet.

b. Data Transmission Phase
1) In the data transmission stage, the source station proceeds with sending the data frame over the first hop, at rate r 1 . We call this frame Data-S frame.
2) The recruited relays cooperatively transmit the data frame over the second hop, at rate r 2 . We denote this frame as Data-R. The transmission employs an STC dimension of L.
3) The destination station finishes the procedure by sending back to the sender an Acknowledgement (ACK) message in order to confirm that the data packet is successfully received.
The above protocol is backward compatible with standard IEEE 802.11 WLAN protocol since RTS/CTS follows the same format as defined in standard WiFi. Legacy stations can read the Duration field and set their Network Allocation Vector (NAV), which indicates how long the surrounding nodes must defer from accessing the channel. Thus legacy stations can co-exist with STiCMAC stations, even though they cannot participate in the cooperative transmissions. The newly introduced HR and HTS messages do lead to some additional overhead, which is evaluated in Section V.

IV. RATE ADAPTATION
Rate adaptation refers to the adjustment of the values of the transmission parameters, e.g., for STiCMAC, the first hop rate r 1 , second hop rate r 2 and STC dimension L, based on the network conditions. In this section, we develop a rate adaptation mechanism to maximize the end-to-end user rate while meeting an acceptable error probability. Our rate adaptation scheme is subject to an end-to-end packet error rate (PER) threshold γ, before MAC layer retransmissions are initiated. The selection of γ affects the system performance. A high γ leads to too many retransmissions due to high packet loss at the MAC layer, while a low γ leads to an under-utilized bandwidth since the communication link could support higher modulation and coding rates. Rate adaptation also requires calibration in the physical layer [16] for a practical system. Considering that the main focus of this paper is the MAC protocol design, we do not address this issue in detail and assume that all stations have been calibrated.
We assume each station supports a set of transmission rates r ∈ {R 0 , R 1 , . . . , R p }, where R 0 is the base rate at which the stations exchange control information, i.e., RTS/CTS, and R 0 < R 1 < · · · < R p .
A given r is identified by the modulation level M r and the channel coding level C r . In addition, we denote the STC code rate as R c . We assume an additive white Gaussian noise (AWGN) channel with independent slow Rayleigh fading between each pair of stations and between the stations and the AP.
Each fading level is assumed to be longer than a packet duration. All stations have a symbol energy of E s and the power spectral density of noise signal is N 0 /2.
In order to present our rate adaptation scheme, we first formulate the PHY layer error rates, i.e.
per-hop bit error rate (BER), per-hop PER and end-to-end PER performance. Along with R-DSTC, we also calculate for comparison the PHY layer error rates for the direct transmission scheme, the two-hop single-relay (CoopMAC) scheme and the DSTC scheme.
The BER and PER for a direct connection between stations i and j are respectively denoted as P ij b (r, h ij ) and P ij p (r, h ij ) for a fixed rate r and instantaneous channel gain h ij between stations i and j. Let us denote i = s when station i is the source and j = d when station j is the destination.
Assuming the instantaneous channel gain vector from all relays to the destination is denoted as h (2) , where . . ], the BER and PER between relays and the destination for DSTC with space-time codeword dimension L are denoted by P DST C b,hop2 (r, L, h (2) ) and P DST C p,hop2 (r, L, h (2) ), respectively. Similarly, when the instantaneous channel gain vector h (2) weighted by the instantaneous random matrix R is defined as h (2) R, the BER and PER between relays and the destination for R-DSTC with space-time for a given r. When these instantaneous PHY layer error rates are averaged over channel fading levels, the average BER and PER rates can be obtained accordingly. Table I lists all parameters and notation used in this section. Based upon the analysis of PHY layer error rates, rate adaptation optimizes the transmission parameters for all transmission strategies with an objective to maximize the end-to-end rate for each station while ensure an end-to-end PER bounded by γ.

A. R-DSTC PHY Layer Per-hop BER Performance
In the suggested two-hop framework, note that the BER for the first hop between the source and a potential relay can be computed using the direct link formulation. We denote the second hop between all the relays and the destination as the cooperative R-DSTC link. This subsection formulates the BER performance for both links.

1) BER performance for a direct link:
In a direct link with an instantaneous channel gain h ij along with rate r (corresponding to modulation level M r , assuming square modulation) between stations i and j, the symbol error rate is given by with where If Gray coding is used in the constellation, the approximate BER is When station i is the source and station j is a relay, Eq. (3) describes the instantaneous BER performance from the source to a relay, since each relay decodes the source signal independently.
Additionally, Eq. (3) gives the per-hop BER performance for a CoopMAC system [6] for both hops, when a single relay is employed without combining the first and second hop signal at the receiver.
2) BER performance for the cooperative R-DSTC link: Assuming n relays, i.e., stations 1 . . . n, successfully decode the source signal, each relay forwards the signal over the cooperative R-DSTC link. Suppose the STC used by the relays has a dimension of L × K [17]. During symbol interval m, m = 1, 2, · · · , K, the forwarded signal from relay j is given by where j = 1, 2, · · · , n, and w j is the random vector at relay j, as described in Section II. Here, X(m) is the mth column of the STC. The received signal at the destination, during the mth symbol interval is given by, where w(m) denotes the AWGN at the mth symbol, and Z(m) = [z 1 (m) z 2 (m) . . . z n (m)] T . Hence, the destination station observes a space-time coded signal with equivalent channel gain vector h (2) R. The destination only needs to estimate h (2) R for STC decoding. By using the orthogonality of the underlying STC [17], the BER of the cooperative R-DSTC link using rate r, L and a fixed h (2) R , denoted by (r, L, h (2) , R), can be computed by replacing h ij with h (2) R in Eq. (3).
Note that for an orthogonal DSTC with a space time codeword dimension L, each of the L relays is assigned an antenna index. Hence, there is no randomization and R = I. Therefore, the BER of DSTC, denoted by P DST C b,hop2 (r, L, h (2) ), can also be determined from Eq. (3) by replacing h ij with h (2) .

B. End-to-End PER Performance for R-DSTC
We derive the average PER by simulations, using the BER formulation in Section IV-A along with the channel code. Each relay adopts a convolutional code C r for error correction, for a given rate r. In our simulation, for each hop we first produce the coded bits and then generate random errors according to the computed instantaneous BER. This bit stream is then fed into the convolutional decoder to produce the decoded bit sequence. The instantaneous PER for both hops is then obtained by comparing the output bit stream at the destination with the original bit stream.
Let us denote by RS the instantaneous set of relays that correctly decode the source signal in the first hop and jointly forward the signal over the second hop. In the first hop, the instantaneous channel gain vector is defined as h (1) including all h ij , j ∈ RS. Consequently, for a given r 1 , r 2 , L, the end-to-end instantaneous PER between station i and the destination for the R-DSTC scheme is given by where In Eq. (6) Following Eq. (6) for instantaneous end-to-end PER, the average end-to-end PER can be obtained by averaging over all first and second hop channel gains and the random weight vector R, and is given by

C. End-to-End PER Performance for Other Schemes
Below we formulate the end-to-end PER performance for the other schemes in order to provide comparison with the proposed R-DSTC scheme. For the direct transmission scheme, the average end-toend PER between the source station i and the destination can be found using the direct-link instantaneous PER, and is given by where the direct rate is r and P id p (r, h id ) denotes the instantaneous PER between source station i and the destination for a given h id and r.
For CoopMAC scheme, the average end-to-end PER performance of source station i also depends on the chosen single relay j, j ∈ S i and is given by where h ij and h jd denote the instantaneous channel gain for the first and second hops, respectively. P ij p (r 1 , h ij ) and P jd p (r 2 , h jd ) denote the instantaneous PER for the two hops, for a given h ij and h jd .
For DSTC, the instantaneous end-to-end PER between source i and destination d depends on a fixed and predefined relay set, denoted as RS i , and is formulated as In Eq. (11), P DST C p (r 1 , r 2 , L, RS i , h (1) , h (2) ) denotes the instantaneous end-to-end PER and is given by where RS ′ is an instantaneous subset of relays from RS i that participate in relaying and P DST C p,hop2 (r 2 , L, h (2) ) denotes the instantaneous PER between relays and the destination for fixed rate r 2 , STC dimension L and channel gains h (2) based on relays in RS ′ .

D. Optimizing end-to-end rate and the choice of transmission parameters
We now describe how to choose the optimal transmission parameters in order to maximize the endto-end transmission rate for each station, while ensuring the end-to-end average PER is bounded by γ.
Even though our emphasis is on R-DSTC, we also discuss direct transmission, CoopMAC and DSTC schemes. In our rate adaptation, every scheme relies on knowledge of the average channel statistics rather than the instantaneous channel gains, thus making it suitable for a WLAN where the average channel statistics change slowly. Assuming the WLAN channel is reciprocal, the source station can estimate the average channel statistics for direct transmission and relayed transmission by listening beacons from AP and overhearing transmissions of other stations. For WLAN systems are typically a stationary or low-mobility environment, the average channel statistics are measured and reported every few seconds, producing only negligible performance loss in throughput. We also discuss rate adaptation based only on number of users in the network.
The set of transmission parameters is different for each scheme and is discussed below. In this paper, all transmission parameters are computed at the source station, as opposed to the protocol in [12] that conducts the computation at the destination station. The maximum end-to-end rate of station i is achieved by minimizing the end-to-end transmission time for each scheme. In addition, we will also discuss the channel information assumed by each scheme for rate adaptation.

1) Direct transmission scheme:
When the source station i transmits to the destination directly, assuming the source station knows the channel statistics to the destination, the optimal transmission parameter is the transmission rate r and the optimum rate r * is given by where P direct p (r) is given by Eq. (9). Note that the optimal transmission rate r is modified whenever the source or destination move to a new location, since the average channel gain for the direct link changes.

2) Two-hop single-relay (CoopMAC) scheme:
We assume there is no signal combining at the destination. A practical MAC protocol for this scheme is CoopMAC [6]. Assuming the source knows the channel statistics between itself and all other stations and between other stations and the destination, the transmission parameters include r 1 , r 2 and the selected relay j. In CoopMAC [6], the optimum relay information is stored in a CoopTable at each source station. The optimum rates r * 1 , r * 2 and the best relay j * are selected by minimizing the end-to-end transmission time over two hops, and is formulated by where P coop p (r 1 , r 2 , j) is given by Eq. (10). When the network topology changes, e.g., the source, destination or any other station move to new locations, the optimal parameters are reselected using Eq. (15).
Hence, CoopMAC is more suitable for a stationary environment with low mobility. When the stations move rapidly, the demand for collecting the global channel knowledge leads to a large overhead for the system. An inaccurate estimation of the channel results in a non-optimal rate adaptation scheme and thus degrades the system performance, as further illustrated in Section V.
3) DSTC scheme: Assuming the available space-time codewords have dimensions denoted by T = {L 1 , L 2 , . . . , L max }, DSTC needs to select its relay set RS i consisting of L relays, where L ∈ T and L = |RS i |. Thus, the transmission parameters are rates r 1 , r 2 , L and RS i . Similar to CoopMAC, the source station is assumed to know the average channel statistics between itself and each stations and between other stations and the destination. The optimum transmission parameters can be obtained by, where P DST C p (r 1 , r 2 , L, RS i ) is given by Eq. (11), and R c is the rate of the orthogonal STC with dimension L. It is known that it is only possible to have full rate (R c = 1) orthogonal STC for L = 2, otherwise R c < 1 [17]. In order to reduce the complexity of relay selection, we propose a greedy algorithm and use it to evaluate DSTC performance in Section V. The basic idea is to sequentially add L relays to the optimal relay set. For each step, we find a single relay that, when combined with the relays selected in the previous steps, will maximize the end-to-end throughput if DSTC is used to assist transmissions from the source.
For the first relay, we choose the best relay from the N-1 stations that maximizes the end-to-end rate in a two-hop manner (single relay based CoopMAC [6]) and add it into the relay set. Then, the second relay is chosen from the remaining N-2 stations in such a way that it can achieve the maximal end-to-end rate along with the first selected relay, using DSTC. Such a selection is iterated until all L relays are picked and added to the relay set. Our simulation shows only 5% throughput difference between this greedy algorithm and exhaustive search when L=2 and N=10.
Like CoopMAC, DSTC need to reselect the transmission parameters whenever the network topology changes and incurs a large amount of channel estimation overhead especially in a mobile environment. • The STiCMAC-CS scheme is assumed to have the same channel knowledge of channel statistics as in DSTC and CoopMAC. That is, the source station i is assumed to know the channel statistics between itself and other stations and between other stations and the destination. The optimal transmission parameters r * 1 , r * 2 , L * are given by (r * 1 , r * 2 , L * ) = arg min where the end-to-end PEP for R-DSTC is given by Eq. For all rate adaptation schemes with full channel statistics, namely direct, CoopMAC, DSTC and STiCMAC-CS, we assume optimal parameters are recomputed whenever the channel statistics change.
For STiCMAC-UC, a two-dimensional look-up table can be pre-computed for the optimal transmission parameters and saved at each source, corresponding to the total number of stations, N, and the distance from the source to the AP in each cell. Once a station enters or leaves the WLAN cell, the BS will broadcast such user count information in its beacon frame to all stations and each station can update its optimal transmission parameters. Thus, STiCMAC-UC does not need real-time computation during network operation. Obviously, in all the relay-assisted schemes, if the end-to-end rate derived by the used rate adaptation scheme is lower than the direct transmission rate, the source station chooses the direct transmission mode instead of cooperation.

V. PERFORMANCE EVALUATION
In order to evaluate the performance of the proposed STiCMAC scheme, we developed a detailed simulation model using OPNET modeler. We compare STiCMAC with direct transmission, CoopMAC and DSTC MAC for both stationary and mobile environments. Additionally, all schemes use the rate adaptation algorithm described in Section IV. The comparison and evaluation was done on a typical single-cell WLAN.

A. Network Topology and Configuration
We assume that the considered wireless LAN complies with the IEEE 802.11g standard and the cell radius is 100 meters. Independent Rayleigh slow fading among each pair of stations and additive white Gaussian noise is adopted as the channel model. The simulated system consists of one AP at the center of a cell and N mobile stations. According to [17], both for DSTC and R-DSTC, a full-rate orthogonal STC is employed for L = 2 with R c = 1, while a R c = 3/4 rate orthogonal STC is employed for L = 3, 4. Each AP or mobile station is equipped with a single omnidirectional antenna. Our simulations are conducted on the uplink from the mobile stations to the AP, with the parameters shown in Table. II. The simulation results display 90% confidence intervals.

B. Mobility Model
Our simulations are performed for both stationary and mobile scenarios. In the stationary scenario, all stations are uniformly distributed within the cell coverage. In the mobile scenario, the stations are assumed to move across the cell using the random walk with reflection (RWkRlc) model [18]. The RWkRlc model is widely adopted to characterize the movement of mobile stations. The RWkRlc model initially deploys stations randomly according to a uniform distribution over the cell. Then, it assigns a random speed to each station that is uniformly distributed in the range [V min , V max ]. Each station picks a random travel duration uniformly distributed in the range [T min , T max ] and a uniformly distributed random direction.
Once a station has walked for the selected duration of time, it may dwell for a random amount of time T d based upon a uniform distribution before it reselects a new travel duration, speed and direction. In contrast to the classic Random Walk model [19], the RWkRlc-governed model includes reflection as an additional feature. Namely, whenever a station reaches the cell boundary during its walk, it will be reflected by the boundary in a similar way that a ray of light reflects off a mirror. This reflection functionality will ensure that the random walk is bounded within a given cell coverage. Accordingly, the RWkRlc model produces a uniform spatial distribution of all stations across the cell and thus enables us to make a fair comparison with the static scenario. The typical parameters of the RWkRlc model we used are shown in Table II. As the distance to the AP grows, all the two-hop schemes outperform the direct transmission, since two high-speed hops provide a higher end-to-end throughput than a low-speed direct transmission, especially as the stations get closer to the cell edge. For large distances, STiCMAC-CS and STiCMAC-UC schemes show the highest per-station throughput gains, followed by the DSTC and CoopMAC. for each relay) from all these relays before every packet transmission is initiated, as is described in [8].

C. Simulation Results
The more relays are recruited by DSTC, the higher the overhead. As the number of stations increases, STiCMAC shows a significant throughput gain over the other schemes (up to 50% gain over direct) due to the following reasons: a) A large number of stations lead to a larger probability of finding more relays, which results in higher diversity and power gain over the second hop. b) Compared to the DSTC MAC [8], STiCMAC needs substantially reduced signaling overhead and handshaking. Also, the overhead of STiCMAC is constant and independent of the number of relays, while the DSTC overhead increases as the number of relays increases. It is also noted that the aggregate throughput of STiCMAC-UC is only slightly lower than STiCMAC-CS. This is because a sufficiently large number of stations supplies enough potential relays and thus eliminates the need for a global knowledge of node locations. This validates our argument that STiCMAC operates efficiently without a global knowledge of channel statistics. in medium access delay for all schemes due to the increased delay before successful access to the channel. However, STiCMAC achieves the lowest delay compared to direct transmission, CoopMAC and the DSTC, since R-DSTC supports a higher end-to-end rate for each connection, and therefore decreases the end-to-end transmission time.
In addition to throughput and delay performance, STiCMAC also reduces the interference generated to neighboring cells when loaded with traffic at the same level. This is because STiCMAC supports a higher average data rate per packet transmission and thus needs reduced air time to deliver the same amount of data on an end-to-end basis, as compared to the other schemes. Consequently, the average transmission power emanating from the reference cell is reduced, even though more relays have been recruited. Fig.   8 shows the interference in a mobile scenario where the average interference power generated by a cell is calculated assuming N=24 users in each cell. The average interference power is illustrated in Fig. 8 and measured in units of dBm at a distance of (100 -300 m) away from the AP of the reference cell.  Instantaneous channel gain between stations i and j h (1) Instantaneous channel gain vector between source and relays h (2) Instantaneous channel gain vector between relays and destination RS i Deterministic relay set of source station i for DSTC RS Instantaneous relay set of source station i for R-DSTC P ij b (r, h ij ) BER for a direct connection between stations i and j for given r and h ij . P ij p (r, h ij ) PER for a direct connection between stations i and j for given r and h ij .
BER for R-DSTC between relays and destination for given r, L, h (2) and R.
PER for R-DSTC between relays and destination for given r, L, h (2) and R. P DST C b,hop2 (r, L, h (2) ) BER for DSTC between relays and destination for given r, L and h (2) . P DST C p,hop2 (r, L, h (2) ) PER for DSTC between relays and destination for given r, L and h (2) . P id p (r, h id ) End-to-end PER for a direct transmission for given r and h id .
End-to-end PER for DSTC for given r 1 , r 2 , L, RS i , h (1) and h (2) . P R−DST C p (r 1 , r 2 , L, h (1) , h (2) , R) End-to-end PER for R-DSTC for given r 1 , r 2 , L, h (1) , h (2) and R. P direct p (r) Average end-to-end PER for a direct transmission for given r. P coop p (r 1 , r 2 , j) Average end-to-end PER for CoopMAC for given r 2 , r 2 and relay j.
Average end-to-end PER for R-DSTC for given r 1 , r 2 and L. P DST C p (r 1 , r 2 , L, RS i ) Average end-to-end PER for DSTC for given r 1 , r 2 , L and RS i . The available rate set for both the first hop (r 1 ) and the second hop (r 2 ) is {R 1 , R 2 , ..., R P }, and the set of available orthogonal STC dimensions for R-DSTC is L, where L ∈ {L 1 , L 2 , ..., L max }. Initialize R * = 0. 2: for Each possible set of transmission parameters {r 1 , r 2 , L} do 3: Find P R−DST C p (r 1 , r 2 , L) for R-DSTC using Eq.(8). 4: if P R−DST C p (r 1 , r 2 , L) < γ and for All possible locations of other stations do 4: Find P R−DST C p (r 1 , r 2 , L) for R-DSTC transmission using Eq. (8) and average over all these locations using χ.


extfieldsofstudy:
Computer Science
Mathematics

text:
Optimal Energy Allocation for Wireless Communications with Energy Harvesting Constraints

We consider the use of energy harvesters, in place of conventional batteries with fixed energy storage, for point-to-point wireless communications. In addition to the challenge of transmitting in a channel with time selective fading, energy harvesters provide a perpetual but unreliable energy source. In this paper, we consider the problem of energy allocation over a finite horizon, taking into account channel conditions and energy sources that are time varying, so as to maximize the throughput. Two types of side information (SI) on the channel conditions and harvested energy are assumed to be available: causal SI (of the past and present slots) or full SI (of the past, present and future slots). We obtain structural results for the optimal energy allocation, via the use of dynamic programming and convex optimization techniques. In particular, if unlimited energy can be stored in the battery with harvested energy and the full SI is available, we prove the optimality of a water-filling energy allocation solution where the so-called water levels follow a staircase function.

I. INTRODUCTION
In conventional wireless communication systems, the communication devices have access to a fixed power supply, or are powered by replaceable or rechargeable batteries to enable user mobility. In these cases, the transmissions are limited by power constraints for safety reasons, or by the sum energy constraint so as to prolong operating time for battery-powered devices. In other communication systems, however, a fixed power supply is not readily available, and even replacing the batteries periodically may not be a viable option if the replacement is considered to be too inconvenient (when thousands of senor nodes are scattered throughout the building), too dangerous (the devices may be located in toxic environments) or even impossible (when the devices are embedded in building structures or inside human bodies). In such situations, the use of energy harvesting for wireless communications appears appealing or sometimes even essential. Examples of energy that can be harvested include solar energy, piezoelectric energy and thermal energy, etc.
For transmitters that are powered by energy harvesters, the energy that can potentially be harvested is unlimited. Typically, energy is replenished by the energy harvester, while expended for communications or other processing; any unused energy is then stored in an energy storage, such as a rechargeable battery.
However, unlike conventional communication devices that are subject only to a power constraint or a sum energy constraint, transmitters with energy harvesting capabilities are, in addition, subject to other energy harvesting constraints. Specifically, in every time slot, each transmitter is constrained to use at most the amount of stored energy currently available, although more energy may become available in the future slots. Thus, a causality constraint is imposed on the use of the harvested energy.
Several contributions in the literature have considered using energy harvester as an energy source, in particular based on the technique of dynamic programming [1]. In [2], the problem of maximizing a reward that is linear with the energy used is studied. In [3], the discounted throughput is maximized over an infinite horizon, where queuing for data is also considered. In [4], adaptive duty cycling is employed for throughput maximization and implemented in practical systems. In [5], an information-theoretic approach is considered where the energy is harvested at the level of channel uses. In [6], and the references therein, optimal approaches are also considered for throughput maximization over AWGN or fading channels.
In this work, we consider the problem of maximizing the throughput via energy allocation over a finite horizon of K time slots. The channel signal-to-noise ratios (SNRs) and the amount of energy harvested change over different slots. Our aim is to study the structure of the maximum throughput and the corresponding optimal energy allocation solution, such as concavity and monotonicity. These results may be useful for developing heuristic solutions, since the optimal solutions are often complex to obtain in practice. We consider two types of side information (SI) available to the transmitter: • causal SI, consisting of past and present channel conditions, in terms of SNR, and the amount of energy harvested in the past slots, or • full SI, consisting of past, present and future channel conditions and amount of energy harvested.
The case of full SI may be justified if the environment is highly predictable, e.g., the energy is harvested from the vibration of motors that are turned on only during fixed operating hours and line-of-sight is available for communications.
Our contributions are as follows. Given causal SI, and assuming that the variations in the channel conditions and energy harvested are modeled by a first-order Markov process, we obtain the optimal energy allocation solution by dynamic programming, which can be computed offline and stored in a lookup table for implementation. Moreover, we obtain structural results to characterize the optimal solution. Given full SI, we obtain a closed-form solution for K = 2 slots. We also obtain the structure of this optimal solution for arbitrary K with unlimited energy storage. The optimal solution then has a water-filling interpretation, as in [7]. However, instead of a single water level, there are multiple so-called water levels that are nondecreasing over time, i.e., the water levels follow a staircase-like function. Finally, we propose a heuristic scheme that uses only causal SI. Compared to a naive scheme, the proposed scheme performs relatively close to the optimal throughput obtained with full SI in our numerical studies. This paper is organized as follows. Section II gives the system model. Then, Section III considers optimal schemes with availability of causal SI of the channel conditions and harvested energy. Section IV considers optimal schemes with availability of full SI with a constraint on the maximum amount of energy that can be stored on the battery, while Section V considers the specific case where this constraint is removed. Section VI shows numerical results for the various schemes. Finally, Section VII concludes the paper.  Fig. 1. Block diagram of a transmitter powered by an energy harvester. Energy is replenished by an energy harvester but is drawn for transmission.

II. SYSTEM MODEL
For simplicity, each packet transmission is performed in one time slot. Each time slot allows n symbols to be transmitted, where n is assumed to be sufficiently large for reliable decoding. We index time by the slot index k ∈ K {1, · · · , K}. We assume that there is always back-logged data available for transmission. In slot k, a message W k ∈ {1, · · · , 2 nR k } is sent, where the rate R k ≥ 0 in bits per symbol can be selected.
We consider a point-to-point, flat-fading, single-antenna communication system. As shown in Fig. 1, the transmitter is powered by an energy harvester that takes in harvested energy as input, that is then stored in an energy storage. The bits to be sent are encoded by an encoder, then sent by a power amplifier that uses the stored energy. Energy is measured on a per symbol (or channel use) basis, hence we use the terms energy and power interchangeably.
Consider slot k ∈ K. At time instant k − , which denotes the time instant just before slot k, the battery has available B k ≥ 0 amount of stored energy per symbol. For transmission, the message W k is first encoded as data symbols X n k [X 1k , · · · , X nk ] of length n, where we normalize n i=1 |X ik | 2 /n = 1.
Then the transmitter transmits packet k in slot k as √ T k X n k , where 0 ≤ T k ≤ B k is the energy per symbol used by the power amplifier. Except for transmission, we assume the other circuits in the transmitter consume negligible energy.

1) Mutual Information:
We assume the channel is quasi-static for every slot k ∈ K with SNR γ k . The maximum reliable transmission rate in slot k is then given by the mutual information I(γ k , T k ) ≥ 0 in bits per symbol [8]. In general, we assume that I(γ, T ) is concave in T given γ, and is increasing in T for all γ. For example, we may employ Gaussian signalling for transmission over a complex Gaussian channel [8], which gives 2) Battery Dynamics: In general, let us denote a vector of length k as Y k = [Y 1 , · · · , Y k ], e.g., the battery energy from slot 1 to slot k is given by B k = [B 1 , · · · , B k ]. While transmitting packet k, the energy harvester collects an average energy of H k ≥ 0 per symbol, which is then stored in the battery.
At time instant (k + 1) − , the energy stored is updated in general as where the function f depends on the battery dynamics, such as the storage efficiency and memory effects.
Intuitively, we expect B k+1 to increase (or remains the same) if B k or H k increases, or if T k decreases. As a good approximation in practice, we assume the stored energy increases and decreases linearly provided the maximum stored energy in the battery B max is not exceeded, i.e., We assume the initial stored energy B 1 is known, where 0 ≤ B 1 ≤ B max . Thus, {B k } follows a deterministic first-order Markov model that depends only on the immediate past random variables.

3) Channel and Harvest Dynamics:
To model the unpredictable nature of energy harvesting and the wireless channel over time, we model 1 H K−1 and γ K jointly as a random process described by their joint distribution. The exact distribution depends on the energy harvester used and the wireless channel environment.
In most typical operating scenarios, both the wireless channels and the harvested energy vary slowly over time. To account for these variations, the SNR γ k is assumed to be constant in each slot and follow a first-order stationary Markov model over time k, see e.g. similar assumptions in [9]. Also, the harvested energy H k is modeled as first-order stationary Markov model over time k, where the accuracy of this model is justified by empirical studies when solar energy is harvested [10]. Given H 0 =Ĥ 0 and γ 1 =γ 1 , the joint pdf of H K−1 and γ K thus becomes where p H k (·|·) and p γ k (·|·) are independent of k. In (3), we have also assumed that the harvested energy and the SNR are independent, which is reasonable in most practical scenarios. In this paper, we assume that the joint distribution (3) is known, which may be obtained via long-term measurements in practice.

4) Overall Dynamics:
Let us denote the state s k = (γ k , H k−1 , B k ), k ∈ K, or simply s if the index k is arbitrary. Let the accumulated states be s k (s 1 , · · · , s k ), k ∈ K.
We assume the initial state s 1 (γ 1 , H 0 , B 1 ) to be always known at the transmitter, which may be obtained causally prior to any transmission. From (2) and (3), given s 1 =ŝ 1 , the states thus follow a first-order Markov model: In particular, (4) includes the special cases where the states are independent, i.e., p s k (s k |s k−1 ) = p s k (s k ), or where the states are deterministic rather than random, i.e., p s k (s k |s k−1 ) = δ(s k −ŝ k ), where δ(·) is the Dirac delta function.
In the next three sections, we consider the problem of maximizing the throughput subject to energy harvesting constraints, given either causal SI or full SI.

A. Problem Statement
We first consider the case of causal SI, in which the transmitter is given knowledge 2 of s k before packet k is transmitted, where k ∈ K. That is, at slot k the transmitter only knows the present channel SNR γ k , past harvested energy H k and present energy stored in the battery B k . In practice, for instance, the receiver feeds back γ k shortly before transmission, while the transmitter infers H k−1 and B k from its 2 It can be shown that having knowledge of previous states s k−1 does not improve throughput, due to the Markovian property of the states in (4). energy storage device. We say that causal SI is available as future states are not a priori known. Thus, this allows us to model and treat the unpredictable nature of the wireless channel and harvesting environment.
The causal SI is used to decide the amount of energy T k for transmitting packet k. We want to maximize the throughput, i.e., the expected mutual information summed over a finite horizon of K time slots, by choosing a deterministic power allocation policy π = {T k (s k ), ∀s k , k = 1, · · · , K}. The policy can be optimized offline and implemented in real time via a lookup table that is stored at the transmitter.
A policy is feasible if the energy harvesting constraints 0 ≤ T k (s k ) ≤ B k is satisfied for all possible s k and all k ∈ K; we denote the space of all feasible policies as Π. Mathematically, given s 1 , the maximum throughput is where In (6), the kth summation term represents the throughput of packet k (after expectation); its expectation is performed over all (relevant) random variables given initial state s 1 and policy π.
For example, if K = 2 and a given policy, (6) simplifies as subject to 0 ≤ T 1 ≤ B 1 for the first term and 0 ≤ T 2 ≤ B 2 = min{B 1 − T 1 + H 1 , B max } for the second term. Clearly, the transmission energy T 1 in the first slot affects the stored energy B 2 available in the second slot, which in turn affects the energy T 2 to be allocated.
In general the optimization of {T k } cannot be performed independently due to the energy harvesting constraints, as shown also in the above example. Instead, for the above example, we can first optimize T 2 given all possible T 1 (and hence all possible B 2 ), then optimize for T 1 with T 2 replaced by the optimized value (as a function of T 1 ). This approach, as will be suggested by dynamic programming in the general case, will be shown to be optimal.

B. Optimal Solution
The optimization problem (5) is solved by dynamic programming in Lemma 1.
Lemma 1: Given initial state s 1 = (γ 1 , H 0 , B 1 ), the maximum throughput T ⋆ is given by J 1 (s 1 ), which can be computed recursively based on Bellman's equations, starting from J K (s K ), J K−1 (s K−1 ), and so on until J 1 (s 1 ): In (9),H denotes the harvested energy in the present slot given the harvested energy H in the past slot, andγ denotes the SNR in the next slot given the SNR γ in the present slot. An optimal policy is denoted is the optimal T that solves (8).
In (8a), the optimal maximization is trivial: the interpretation is that we use all available energy for transmission in slot K. We can interpret the maximization in (8b) as a tradeoff between the present and future rewards. This is because the mutual information I(·, ·) represents the present reward, whileJ k+1 , commonly known as the value function, is the expected future mutual information accumulated from slot k + 1 until slot K.
Next, we obtain structural properties of the maximum throughput T ⋆ in (5) and the corresponding optimal policy π ⋆ in Theorems 1 and 2. The proofs are given in the Appendix.
Theorem 1: Suppose that I(γ, T ) is concave in T given γ. Given γ and H, then Thus, Theorem 2: Suppose that I(γ, T ) is concave in T given γ. Given γ and H, then the optimal power The structural properties in Theorems 1 and 2 simplify the numerical computation of the optimal power allocation solution in Lemma 1, as shown in the next subsection.

C. Numerical Computations
From (8a), we get the optimal solution for slot K as T ⋆ K (s K ) = B K . Now, consider the problem of finding the optimal T ⋆ k (s k ) to obtain J k (s k ), k ∈ {1, · · · , K − 1}. Let us fix the SNR and harvested energy as γ, H, respectively, and drop these arguments when possible to simplify notations. Consider the unconstrained maximization over all T ≥ 0, i.e., not subject to any energy harvesting constraint: where we denote due to Theorem 1, the objective function g(T ) is concave. Thus, the maximization over all T gives a unique solution T † k , easily solved using numerical techniques such as a bisection search [11]. Also, Theorem 2 helps to reduce the search space by restricting the search to be in one direction for different B. Alternatively, if g(T ) is differentiable and available in closed-form, T † k is given by solving g ′ (T ) = 0.
Finally, we get the optimal solution for (8b) by restricting the maximization in (10) to be over 0 ≤ T ≤ B to give This is because if T † k ≤ 0, the (concave) objective function g(T ) must be decreasing for the objective function must be increasing for T ≤ B.

D. I.I.D. SNR and Harvested Energy
We consider the i.i.d. SI scenario where both γ k and H k are independent and identically distributed (i.i.d.) over k for analytical tractability. Even with i.i.d. SI, the optimization problem in Lemma 1 is not decoupled as it still depends on the past harvested energy H k−1 . Intuitively, this is because the present transmission energy T k (whose maximum allowable depends on H k−1 ) will still affect the future storage If we assume a Rayleigh fading channel with expected SNR given byγ, i.e., the statistics of the SNR is p γ (γ) = 1/γ exp(−γ/γ), γ ≥ 0, the expected mutual information evaluates as where the exponential integral is defined as E 1 (x) = ∞ x exp(−t)/t dt. Instead, if we assume an AWGN channel where the channel is time-invariant with γ k =γ for all k, then the expected mutual information is simplyĪ In AWGN channels, by inspection J k (γ, H, B) in Lemma 1 is independent of γ for all k, but still dependent on H. Hence, the optimization problem for each J k (γ, H, B) still has to be solved recursively, rather than as decoupled optimization problems.

IV. FULL SIDE INFORMATION: ARBITRARY B max
The initial battery energy B 1 is always known by the transmitter. We say that full SI is available if the transmitter also has priori knowledge of the harvest power H K−1 and SNR γ K before any transmission begins. This corresponds to the ideal case of a predictable environment where the harvest power and channel SNR are both known in advance, and also gives an upper bound to the maximum throughput T ⋆ for any distribution (3).
In this section, we consider the general case where B max may be finite. Corollary 1, as a consequence of Lemma 1, gives the optimal throughput T ⋆ for the same problem (5) but with full SI available.
Proof: All side information are a priori known and hence the SI is deterministic rather than random.
Corollary 1 thus follows immediately from Lemma 1, by replacing the pdfs in (4) by Dirac delta functions accordingly.
In general, power may be allocated via these modes: • greedy (G): use all stored energy whenever available; • conservative (C): save as much stored energy as possible (without wasting any harvested energy) to the last slot; • balanced (B): stored energy is traded among slots accordingly to channel conditions.
For the last slot, or if K = 1 where there is only one slot, from (15a) it is optimal to allocate all power for transmission. For the case K = 2, Corollary 2 obtains the optimal power allocation for the first slot.
The proof is given in the Appendix.
Corollary 2: Consider K = 2 slots. Suppose that the mutual information function is given by (1).
Given full SI {B 1 , H 1 , γ 1 , γ 2 }, the optimal transmission energy for slot 1 is given by (corresponding to the G, B, C modes, respectively) where we denote [x] + max(0, x) and and we also let In Corollary 2, the power allocation (16) is interpreted to be in G, B, or C mode, respectively. As an example, suppose b > 0. Then all modes can be active: power allocation is greedy if the energy to be harvested is large or the stored energy is small (a < 0 or B 1 < b); power allocation is conservative if the energy to be harvested is small and the stored energy is large (a ≥ 0 and B 1 > c); otherwise, the allocation depends on the SI.
is increasing in B 1 , as stated in Theorem 2 for the general case. From (17), the optimal power allocation is thus given by half of the battery energy B 1 /2 plus (or minus) a correction term that depends on the SNRs and harvested energy; this observation will be exploited to obtain a heuristic scheme in Section VI-A.
Although we can derive a closed-form result for larger K, the expression becomes unwieldy and less intuitive. To make progress, in the next section we assume the case of infinite B max , which gives the highest possible achievable throughput and thus provides an upper bound for any practical implementation. The assumption is also reasonable if the storage buffer is selected to be large enough. We shall show that for any K we can obtain a closed-form result that is a variation of the water-filling power allocation policy [7], which is somewhat suggested by Remark 2.

V. FULL SIDE INFORMATION: INFINITE B max
The previous section considers the general case of arbitrary B max . To develop more insights, in this section we consider that the mutual information function is given by (1) and B max → ∞. Then from (2), the battery stored at slot k + 1, where k ∈ K, is given by A non-negative power allocation is feasible if and only if B k+1 ≥ 0, k ∈ K. The throughput maximization problem solved in Corollary 1 can then be formulated as follows:

A. Water-Filling Algorithm
Before we consider the general case where the constraint (19b) is imposed for all k ∈ K, we impose the constraint (19b) only for the last slot, i.e., only for k = K. This then corresponds to the conventional problem of maximizing the sum throughput with a sum energy constraint of Since less constraints are imposed, the maximum throughput in (20) is no smaller than that of (19). It is well known that the optimal solution for (20) is given by (see e.g. [8], [11]) 13 This optimal solution is implemented by the water-filling algorithm, where the water-level (WL) ν ≥ 0 is chosen such that (20b) holds with equality by using the optimal power allocation in (21). For completeness, an implementation of the water-filling algorithm, which gives the maximum T to within a tolerance of ǫ, is given below as Algorithm 1.

B. Staircase Water-Filling Algorithm
We now proceed to solve our original problem (19) with additional energy harvesting constraints in (19b). It turns out that the conventional water-filling algorithm is no longer optimal. Instead it is necessary to use a generalized type of water-filling where the water level is a staircase-like function.

1) Structural Properties:
The optimization problem in (19) is convex and so can be solved by the dual problem [11]. The Lagrangian associated to the primal problem (19) is where T k ≥ 0 is the power allocation for the kth slot and λ k ≥ 0 is the Lagrangian multiplier for the kth constraint in (19b), k ∈ K. Then the necessary and sufficient conditions for λ K and T K to be both primal and dual optimal are given by the Karush-Kuhn-Tucker (KKT) optimality conditions: for k ∈ K. From (22b), and imposing the constraints (22c) and (22e) via similar arguments to obtain (21) in [8], [11], we obtain the optimal power allocation as ≥ 0, and the λ i 's satisfy the KKT conditions (22).
Analogous to the problem in (20) with only power constraint (20b), we say ν k is the WL for slot k.
Also, we say slot t ∈ K is a transition slot (TS) if the water level changes after slot t, i.e., ν t = ν t+1 . We define the last slot k = K also as a TS (say by defining ν K+1 to be infinity); hence there is at least one TS. We collect all TSs as the set S = {t 1 , t 2 , · · · , t |S| }, where t i < t j for i < j and t |S| = K.
From the result in (23), we obtain the following structural properties for the optimal power allocation in Theorem 3. Fig. 2 gives an example of the optimal power allocation. In general the optimal WLs {ν k } depend on the slot indices and there can be multiple optimal TSs, while in the conventional water-filling slot k Structure of optimal power allocation T ⋆ k with full SI and infinite Bmax. We assume two optimal TSs and hence three distinct water levels for ν k . Here, the SNRs {γ k } are arbitrary.
algorithm, the optimal WL is the same for all slot indices and thus there is no TS (except for the trivial one at slot K).

Theorem 3:
The optimal power allocation in (23) satisfy these properties:

P1:
The WL is non-decreasing over slots, i.e., ν 1 ≤ · · · ≤ ν K . We say that the optimal power allocation performs staircase water-filling over slots, since the WL is a staircase-like function (see e.g. Fig. 2).
P2: If slot t is a TS, then the battery storage is empty, i.e., (22a) holds with equality if k ∈ S.
Proof: Since λ k ≥ 0, it follows that ν k ≥ 0 and also that ν k is non-decreasing with k. This proves property P1.
Suppose slot t is an TS, i.e., t ∈ S and so ν t = ν t+1 . Since by definition ν k = (ln 2 K i=k λ i ) −1 , we get λ t = 0. From (22c), we get λ t > 0. It then follows from the complementary slackness condition (22d) (with k replaced by t) that (22a) holds with equality for k = t. This proves property P2.

Corollary 3:
If the SNR is non-decreasing over slots, then the optimal power allocation is non-decreasing over slots.
Proof: This follows immediately from (23) and property P1, which implies that T l ≤ T k if γ l ≤ γ k for l < k.
An example that illustrates Corollary 3 is given in Fig. 3, where we see that the inverse of the SNR is non-increasing. It is easy to see that the converse of Corollary 3 is not true in general. That is, if the SNR slot k T k γ −1 k ν k Fig. 3. Structure of optimal power allocation T k with full SI and infinite Bmax, with increasing SNR γ k , i.e, decreasing γ −1 k , over slot k.
In this case, T ⋆ k must increase over slot k.
is non-increasing, then the optimal power allocation may not be non-increasing over slots (in particular for the slot immediately after the TS). In conventional water-filling, however, both Corollary 3 and its converse hold, i.e., the optimal power allocation is non-decreasing over slots if and only if the SNR is non-decreasing over slots.
We give an intuitive understanding of Corollary 3, and why the converse does not hold, to shed some light on how the energy harvesting constraints lead to a different optimal power allocation. First, let us consider the AWGN channel where the SNR is constant over slots. If all the harvested energy is already available in the first slot, i.e., there is only a single sum-power constraint, a uniform power allocation is optimal for the AWGN channel. However, in an energy harvesting system, maintaining a uniform power allocation may not be always possible due to the causal arrival of the harvested energy. Due to this nonuniform availability of harvested energy over slots, more energy only becomes available for transmission in the latter slots. Intuitively, we also expect more energy to be allocated for transmission in the latter slots such that the energy harvesting constraints in (19b) are satisfied. This type of strategy is optimal from Corollary 3, which applies since the SNR is constant and hence also non-decreasing. Next, consider the case where the SNR is non-decreasing over slots. From the water-filling algorithm under a single sum-power constraint, to achieve the maximum throughput it is optimal to allocate more power to the latter slots that have higher SNRs. This is consistent with the earlier observation that more power should be allocated to the latter slots such that the constraints in (19b) are satisfied. Hence, it is also optimal to allocate more power to the latter slots. In general if the SNR is arbitrary, however, the high-SNR slots may not correspond to the latter slots; hence intuitively the converse of Corollary 3 may not hold in general.
2) Efficient Implementation: Based on the structural properties, we now develop an efficient algorithm to implement the staircase water-filling.
Some definitions are in order. For convenience, let t 0 = 0. We refer to the ith slot interval, where i = 1, · · · , |S|, as the slots between the ith and (i + 1)th TS, specifically in the TS setS i {t i−1 + 1, · · · , t i }.
Thus, iS i = K andS i ∩S j = ∅ for i = j. The optimal set of TSs corresponding to an optimal power allocation is denoted as

Corollary 4:
The optimal power allocation performs staircase water-filling as follows: for every ith slot interval, where i = 1, · · · , |S ⋆ |, conventional water-filling is performed subject to the sum power constraint of P (i) k∈S i H k−1 , where we denote H 0 = B 1 for notational simplicity.
Proof: From property P2, all the harvested energy available in the ith slot interval, namely P (i), is used during the ith slot interval. This follows by induction for i = 1, · · · , |S|. Moreover, the optimal power allocation in (23) is equivalent to conventional water-filling. To maximize throughput, the optimal power allocation must then be to use conventional water-filling with sum power constraint of P (i) for every ith slot interval.
From Corollary 4, without loss of optimality the staircase water-filling solution comprises of multiple conventional water-filling solutions, one for each slot interval. The original optimization problem (19) can thus be reduced to a search for the optimal TS set S ⋆ that has a size from 1 to at most K: subject to the power allocation P (1), · · · , P (|S|) satisfying the constraints in (19b). A brute force search based on (24) is of a high computational complexity. Nevertheless, it turns out that it is optimal to simply employ a forward-search procedure, starting with the search of the optimal t ⋆ 1 , then of the optimal t ⋆ 2 , and so on until the last optimal TS t ⋆ |S ⋆ | equals K, at which point the optimal size |S ⋆ | is also obtained.
The first optimal TS t ⋆ 1 can be found in Lemma 2 given below; by induction, the search of the subsequent optimal TSs will follow similarly. Lemma 2 requires the following feasible-search procedure for a given optimization problem (19): 1) Initialize S 1 as an empty set.
2) For t 1 = 1, · · · , K, obtain the optimal power allocation from slot 1 to slot t 1 by using a water-filling algorithm (such as Algorithm 1) assuming that all harvested energy is available, i.e., the sum power 3) Admit t 1 in the set S 1 if the corresponding optimal power allocation satisfies the constraint (19b) for k = 1, · · · , t 1 .
The set S 1 is non-empty; it contains at least the element t 1 = 1, as the constraint (19b) in Step 3 is equivalent to the sum power constraint in Step 2. Moreover, the set S 1 includes all possible candidates for the optimal t ⋆ 1 ; the only candidates that are not included are those where at least one of the constraint in (19b) is not satisfied for slot k = 1, · · · , t ⋆ 1 .
Lemma 2: Let S 1 be the feasible set of t 1 obtained by the feasible-search procedure. Then the optimal TS is given by the largest element in S 1 , i.e., Proof: If |S 1 | = 1, then that only t 1 must be optimal. Henceforth, assume |S 1 | ≥ 2. Consider two TSs Denote their respective optimal WLs obtained from the water-filling algorithm as ν ′ , ν ′′ . Then ν ′ ≥ ν ′′ . Otherwise if ν ′ < ν ′′ , more power is allocated for each time slot k = 1 · · · , t ′ , if the WL ν ′′ is used, compared to the case where the WL ν ′ is used. But since the power allocation with WL ν ′ has used all available power at slot t ′ due to property P2 in Theorem 3, the power allocation with WL ν ′′ is infeasible and thus cannot be optimal.
We now show that t ′ cannot be the optimal t ⋆ 1 by contradiction. Suppose that t ⋆ 1 = t ′ , i.e., water-filling is used from slot 1 to slot t ′ with WL ν ′ . The WL for the power allocation must then subsequently decrease at some slot t ′ < k ≤ t ′′ , otherwise the sum power allocated from slots 1 to slot t ′′ will be more than the sum power allocated with the (constant) WL ν ′′ , which violates the sum power constraint. But from property P1 in Theorem 3, the optimal WL is non-decreasing. Thus, t ⋆ 1 = t ′ by contradiction. By induction, all elements in S 1 , except for the largest one, are suboptimal. The only candidate left, namely the largest element, must then be optimal.
We now propose Algorithm 2 below to solve (24), which is optimal according to Theorem 4 below.
Briefly, Algorithm 2 performs a forward-search procedure (starting from slot 1) in each of the outer performed via a backward-search procedure, starting from slot t ⋆ i−1 , t ⋆ i−1 − 1, · · · , until slot 1.

Proof:
The ith outer iteration of Algorithm 2 finds the optimal t ⋆ i . Consider i = 1. From Lemma 2, we can determine the optimal t ⋆ 1 by finding the largest feasible t 1 . Without loss of optimality, we can modify the feasible-search procedure such that the search (in Step 2) starts from the largest slot index to the smallest, and (Step 3) terminates to give the optimal t ⋆ 1 once a feasible t 1 is found. These modifications lead to the inner iteration in Algorithm 2.
From Property P2 in Theorem 3, in the first TS interval all the power available would be used. Since no power is available for subsequent slot intervals given t ⋆ 1 , the power allocation for subsequent slot intervals can be optimized independent of the actual power allocated in the first slot interval. The throughput maximization problem from slot t ⋆ 1 + 1 onwards can be solved similarly as before (after removing time slots 1, · · · , t ⋆ 1 ). Thus, we apply the inner iteration again to determine t ⋆ 2 , similarly for t ⋆ 3 and so on, as reflected in the outer iteration of Algorithm 2. The iteration ends when the optimal TS equals K, which is the largest possible value as stated in optimization problem in (24).

3) Update Algorithm when New Slots Become Available:
Suppose that we have obtained the optimal S ⋆ based on Algorithm 2 for a K-slot system. Now, a new slot becomes available for our use where its SI is known. We wish to obtain the new optimal solution for this (K + 1)-slot system, say S ⋆ new = {t ⋆ 1,new , t ⋆ 2,new , · · · }. Instead of implementing Algorithm 2 afresh, we can obtain an update of S ⋆ new from S ⋆ as follows: • Consider i = 1 in the outer iteration of Algorithm 2. We only need to execute k = K + 1 in the inner iteration. If the constraints (19b) are satisfied, then we have obtained t ⋆ 1,new = K + 1, hence ,new } and Algorithm 2 terminates. Otherwise, since we already know that t ⋆ 1 in the largest element in S ⋆ , we obtain immediately t ⋆ 1,new = t ⋆ 1 .
• The subsequent iterations are executed similarly. For the ith outer iteration, where i = 2, 3, · · · , we only execute k = K + 1 in the inner iteration. If the constraints (19b) are satisfied, then t ⋆ i,new = K + 1 and Algorithm 2 terminates; otherwise t ⋆ i,new = t ⋆ i .
Hence, for every outer iteration, only one additional inner iteration is executed until the constraints (19b) are satisfied. Since there are at most K outer iterations, we need to execute at most K inner iterations in total. In cases when the number of available slots can increase dynamically in a multi-user system, say when other users give up their slots and is assigned to our energy harvesting system, the above proposed update algorithm allows an efficient way to update S ⋆ .

VI. NUMERICAL RESULTS
To obtain numerical results, we assume that the SNR γ k and the harvested energy H k are i.i.d. over time slot k and the channel is either an AWGN or Rayleigh fading channel, as described in Section III-D.
We assume the initial stored energy B 1 and the harvested energy H k takes a value in {0, 0.5, 1} with equal probability and B max → ∞. To measure the performance of various schemes, we plotted the throughput per slot, i.e., the sum throughput divided by the number of slots K, as the average SNRγ is increased.
If causal SI is available, the optimal policy is obtained recursively by applying Lemma 1. Specifically, we first obtainJ K (B) in (9) via the closed-form results in Section III-D; we drop the γ and H arguments due to the i.i.d. assumption. Then we obtain J K−1 (γ, B) in (8b), say by an iterative bisection method. The throughput are averaged over 10 4 independent realizations of γ and H to giveJ K−1 (B). This procedure is performed for different B, discretized in step size of 0.01, and stored to be used for the next recursion. The iteration is repeated for k = K − 2, · · · , 1. If instead full SI is available, the optimal policy is obtained by Algorithm 2; we have verified that our proposed algorithm is significantly faster but is equivalent to solving the problem via a standard optimization software. The throughput per slot is obtained from averaging the results from 10 4 independent Monte Carlo runs.
The results are shown in Fig 4 for AWGN channels and in Fig. 5 for Rayleigh fading channels. The throughput in both cases, when either full SI or causal SI is available, is the same for K = 1, because any SI cannot be exploited for future slots. However, in both cases the throughput per slot increases as K increases. The increment is more substantial when full SI is available, intuitively because the SI can then be much better exploited. The incremental improvement as K increases is significant when K is small, but becomes less significant when K is large. The throughput with either full SI or causal SI does not differ significantly, possibly because the SI that can be further exploited from full SI is limited in our i.i.d. scenario.

A. Heuristic Schemes with Causal SI
Next, we consider two heuristic schemes that use causal SI yet can be easily implemented in practice, namely the naive scheme and the power-halving scheme.
In the naive scheme, all stored energy B k is used in every slot k, i.e., T k = B k . This is equivalent to the case of K = 1 in our optimization problem regardless of whether causal SI is available (see Lemma 1) or full SI is available (see Theorem 4). In both cases, it is optimal to use all stored energy. As seen earlier, the case of K = 1 performs significantly worse than the optimal schemes for K > 2 in both cases. To obtain further improvement in the per-slot throughput, we need to further exploit the causal SI available.
In the power-halving scheme, all stored power is used for transmission in the last slot, while for all other slots half of the stored energy is used, i.e., T k = w k B k where w k = 1 if k = K and w k = 1/2 otherwise. This scheme is simple to implement. Intuitively, the present throughput is traded equally with the future throughput by splitting the battery energy B k into two halves. We note that this scheme also implicitly exploits causal information of the harvested energy (which accumulates as the stored energy B k ). Moreover, the power-halving scheme satisfies the following characteristics and thus likely improves the throughput when causal SI is only available: 1) T k increases with B k , in accordance with Theorem 2 in the causal SI case.
2) From Remark 2, if K = 2, the optimal power allocation is given by half of the battery energy B 1 /2 and a correction term that depends on the SNRs and harvested energy. Ignoring this correction term (which is not known due to the lack of full SI) then leads to the power-halving scheme for K = 2.
3) More stored energy is deferred to be used in the latter slots, thus resembling the optimal policy with staircase WLs in the full SI case. Fig. 6 shows the throughput per slot obtained by averaging the numerical results from 2×10 4 independent runs of Monte Carlo simulations, for both AWGN channels and Rayleigh fading channels. We fix the SNR at 20 dB. As benchmarks, we also plot the optimal throughput when full SI is available. This is because the computational complexity in solving the Bellman's equations in Lemma 1 when causal SI is available becomes prohibitive for large K; moreover we observed earlier that the performance with causal SI is close to the performance with full SI. The results show that the power-halving scheme is able to improve on the per-slot throughput as K is increased, and is only within about 0.2 bits away from the case when full SI is available. Moreover, we see that at small K, the gap is even closer, as suggested by the second characteristic mentioned above. Similar results are obtained at lower SNR, with an even smaller throughput degradation compared to the case when full SI is available. Further performance gain may also be obtained by optimizing this tradeoff by considering the channel conditions explicitly.

VII. CONCLUSION
We considered a communication system where the energy available for transmission varies from slot to slot, depending on how much energy is harvested from the environment and expended for transmission in the previous slot. We studied the problem of maximizing the throughput via power allocation over a finite horizon of K slots, given either causal SI or full SI. We obtained structural results for the optimal power allocation in both cases, which allows us to obtain efficient computation of the optimal throughput. Finally,  With γ, H fixed, we prove by induction that J k (γ, H, B) andJ k+1 (γ, H, x) are concave in B and x, respectively, for decreasing k = K, · · · , 1.
Consider k ∈ {1, · · · , K−1}. Suppose that J k+1 (γ, H, B) is concave in B. We note that J k+1 (γ, H, min{B max , x+ H}) is concave in x, as it is the minimum of J k+1 (γ, H, B max ) (a constant independent of x) and the concave function J k+1 (γ, H, x + H). It follows thatJ k+1 (γ, H, x) is concave in x, since expectation preserves concavity. From (8b), J k is a supremal convolution of two concave functions in B, namely I and J k+1 (with γ, H fixed). It follows that J k is concave in B, since the infimal convolution of convex functions is convex [12,Theorem 5.4]. To complete the proof by induction, we note that J K (γ, H, B) = I(γ, B) is concave in B by assumption on the mutual information function I(·, ·).
Suppose H 1 > B max . Then min{B max , B 1 − T + H 1 } = B max given T ≤ B 1 . The optimal T that solves (27) is then Suppose H 1 ≤ B max . Assume that 0 ≤ T ≤ B 1 + H 1 − B max . Then min{B max , B 1 − T + H 1 } = B max , and so the optimal T to maximize g(T ) subject to 0 ≤ T ≤ B if H 1 ≤ B max . Now if T ≥ [B 1 +H 1 −B max ] + , we have g(T ) = log 2 (1+γ 1 T )+log 2 (1+γ 2 (B 1 −T +H 1 )), which is differentiable and concave. Observe that T in (17) solves the equation g ′ ( T ) = 0, i.e., T is the optimal solution for the unconstrained optimization problem max g(T ). By concavity of g(T ), we can then obtain (29) as if H 1 ≤ B max . By re-writing the above conditions in terms of B 1 and combining the result with (28), we then obtain T ⋆ 1 as stated in Corollary 2.