# Efficient Wireless Broadcasting through Joint Network Coding and Beamforming

Authors: Monchai Lertsutthiwong; Thinh Nguyen; Bechir Hamdaoui
Journal: International Journal of Digital Multimedia Broadcasting
 (2012)

---

## Abstract

We develop a framework that exploits network coding (NC) and multiple-input/multiple-output (MIMO) techniques, jointly together, to improve throughput of downlink broadcast channels. Specifically, we consider a base station (BS) equipped with multiple transmit antennas that serves multiple mobile stations (MSs) simultaneously by generating multiple signal beams. Given the large number of MSs and the small number of transmit antennas, the BS must decide, at any transmission opportunity, which group of MSs it should transmit packets to, in order to maximize the overall throughput. We propose two algorithms for grouping MSs that take advantage of NC and the orthogonality of user channels to improve the overall throughput. Our results indicate that the proposed techniques increase the achievable throughput significantly, especially in highly lossy environments.


---

## Body

## 1. Introduction

In recent years, multiple-input/multiple-output (MIMO) has been recognized as a key enabling technology for improving the performance of wireless communication systems. Unlike traditional communications, MIMO techniques rely on multiple antennas to transmit and/or receive signals. The number of antennas that a device can be equipped with can be limited due to spatial constraints. For example, in a cellular network, while there may be no limit on the number of antennas that the base station (BS) can be equipped with, there is a limit on that number when it comes to mobile station (MS) due to size and/or cost constraints. MIMO capabilities can be exploited to enable the spatial division multiple access (SDMA) technique, which basically allows multiple simultaneous transmissions from the BS to multiple MSs, thereby achieving higher overall data throughput [1–3]. Specifically, the BS exploits MIMO to generate radiation patterns that simultaneously target different groups of MSs [4, 5]; this is known as beamforming (BF). Mathematically, the signal beam from each antenna is coded and multiplied independently by a BF weight vector to control its shape and direction. A BF weight vector is determined by MSs locations as well as the characteristics of channels between the BS and MSs. Assuming that the BF weight vectors are available, an optimal SDMA scheme consists then of selecting the set of MSs whose signal-to-interference plus noise ratios (SINRs) are maximized.A BS withM transmit antennas can form and transmit a signal with at most M beams [6, 7]. Therefore, assuming that one beam is allocated for each MS, when the number of MSs, K, exceeds the number of transmit antennas, M, the BS selects the best M MSs, that is, those whose SINRs are maximized [8]. An efficient scheduling algorithm is then required at the BS to map the MSs with these beams. For example, given 10 MSs (z1,z2,…,z10) and one BS equipped with 2 antennas, an efficient scheduler may select (z2,z4) in the first time slot for transmission, (z1,z5) in the second time slot, (z7,z9) in the third time slot, and so on. After five time slots, the BS completes then transmitting all packets to their intended MSs. The key challenge in designing these scheduling algorithms lies in grouping the MSs in such a way that interference among MSs is minimized; that is, a transmitted beam intended for one MS should create no or minimal interference to any other MSs in the group. One way to achieve this objective is to group together MSs whose channel vectors are somewhat orthogonal to one another.Network coding (NC) is another effective technique that is also well recognized for its great network throughput potentials and has received a considerable attention due to its practical simplicity [9]. In single-hop wireless networks, such as cellular networks, NC can be used to significantly reduce the number of transmission/retransmission attempts required to successfully deliver data packets [10]. Consider the example of Figure 1 for the purpose of illustration. Instead of immediately retransmitting a lost packet a1 for an MS, for example, z1, the BS waits until there is another lost packet a2 for another MS, for example,  z2. Due to spatial proximity of z1 and z2, it is possible that a1, although intended for z1, may be received and cached successfully by z2; likewise, a2 may also be cached successfully by z1. In that case, the BS only needs to retransmit a single packet a1⊕a2, which is a bitwise exclusive-OR (XOR) of packets a1 and a2. (Here, all packets are assumed to have the same bit length so as to be able to perform the XOR operation.) If this packet is successfully received by both z1 and z2, then z1 can recover a1 as a2⊕(a1⊕a2)=a1 and z2 can recover a2 as a1⊕(a1⊕a2)=a2. Thus, one retransmission allows both MSs to recover their lost packets, resulting in a reduced number of retransmissions or, equivalently, in an increased throughput efficiency.Figure 1
Illustrative example of NC technique.In this paper, we develop scheduling algorithms that exploit NC and BF techniques jointly together to maximize the overall throughput achievable on a wireless broadcast downlink channel. Specifically, we consider a BS with multiple transmit antennas that simultaneously serves multiple MSs by generating multiple signal beams with well-defined beamforming weight vectors, where each MS corresponds to a particular beam. Given a large number of MSs and a small number of transmit antennas, the BS must decide, at any transmission opportunity, which group of MSs it should transmit packets to, in order to maximize the overall throughput. In this work, we prove that the group formation problem is NP-hard and propose two scheduling heuristics that take advantage of NC capabilities and the orthogonality of user channels to improve the overall throughput on broadcast transmissions. Our simulation results show that the proposed techniques achieve greater throughput than that achievable under existing techniques, especially in highly lossy environments.The outline of our paper is as follows. First, we present a literature review in Section2. Then, we overview NC techniques and discuss our joint BF-NC framework in Sections 3 and 4, respectively. In Section 5, we describe our proposed joint BF-NC-based scheduling algorithms. We show the simulation results for the proposed techniques in Section 6 and conclude the paper in Section 7.


## 2. Related Work

Simultaneous service support of multiple MSs through BF techniques can be very challenging due to interference incurred by different active signal beams. Therefore, several efficient scheduling algorithms and proper BF strategies have been proposed to reduce interference among multiple beams. To maximize the sum capacity, the scheduled MSs are typically selected through an exhaustive search, which can be very costly or even infeasible for a large MS pool. For example, Shad et al. [11] proposed an algorithm for selecting the MSs for each time slot over SDMA/TDMA networks by considering the largest SINR margin of scheduled MSs with respect to some SINR thresholds. Choi et al. [12] provided a scheduling algorithm, which relies on the feedback from MSs during each time slot to determine a subset of MSs in such a way to maximize the sum capacity. Ravindran et al. [13] studied the performance of zero-forcing BF techniques under limited channel feedback in line of sight (LOS) channels. Their results show that a zero-forcing BF technique performs well especially when the system has reliable channel state information (CSI) from MSs. Furthermore, Yoo and Goldsmith [7] considered the orthogonality of CSIs among the MSs to schedule the MSs while minimizing the overall interference. In particular, their technique greedily selects a set of MSs while assuming that the BS knows CSIs of all MSs in the system.Another traditional technique, yet efficient, is to use a BF codebook containing a set of all possible coefficients (or codewords) to form a BF beam. In general, the codebook is generated offline and consists of a fixed number of codewords, which do not depend on statistical characteristics of channel conditions [14]. Most codebooks are fixed and designed for a specific transmitter. For example, Love and Heath [15] proposed a way to generate a codebook that cannot adaptively change as the channel changes. By using their technique, both BS and MSs have full knowledge of a codebook. Amiri et al. [16] provided an efficient algorithm to adaptively change a codebook based on new feedback information at the BS. However, their technique is complex because the BS needs to frequently evaluate new feedback information, and, hence, the technique may not be suitable for systems with a large number of MSs. Huang et al. [17] showed the performance of orthogonal BF techniques by selecting a codeword for each MS in such a way to reduce the interference among all active beams. More specifically, their technique consists of finding a set of codewords from a fixed codebook for all active beams by relying on MSs CSIs.Most of these reported works consider associating/allocating one BF beam for each intended MS. However, MSs within a close proximity often experience similar channel conditions and have similar SINR levels. Therefore, considering grouping and associating these MSs together under one BF beam not only allows to support more MSs but also enables effective use of NC techniques, thus improving throughput even further. This work proposes a framework that takes into consideration the proximity in SINRs and CSI orthogonality when grouping MSs and forming BF beams. We first prove that the group formation problem is NP-hard (the proof is given in  the appendix) and then propose two heuristic techniques: a greedy-selection-based technique and a codebook-based technique, which are described later in Section5.


## 3. Network Coding and Broadcasting

For notational convenience, throughout this paper, uppercase boldface letters are used for matrices and lowercase boldface letters are used for vectors, andX*, XT, X̃, |X|, and ∥X∥ denote conjugate transpose, transpose, normalized, size or magnitude, and L-2 norm of X, respectively.In this section, we briefly describe the use of NC technique over wireless broadcast channels. We considerK MSs (as receivers) and one BS (as the sender). Without loss of generality, we assume that each data packet can be transmitted in one time slot (all time slots are of a fixed duration). We also assume that MSs use either positive or negative acknowledgements (ACK/NAK) to let the BS know about the status of receiving each packet. Traditionally, an MS immediately sends a NAK if the packet is not successfully received. When using an XOR NC technique, instead of immediately retransmitting a lost packet to a certain MS right after receiving a NAK, the BS waits for a fixed interval of time (in time slots) before retransmitting starts. With NC enabled, the BS then retransmits an XOR-coded packet for each set of multiple lost packets. For this to happen, the BS maintains a list of all lost packets as well as their corresponding MSs for some time (i.e., waiting period) during retransmission phase. The number of lost packets that can be coded at once is then at most equal to the number of MSs, K, one lost packet from each MS. Any successful packets received by any of the K MSs will not be included in the coded packet to be retransmitted. The BS keeps retransmitting coded packets of lost packets until all MSs receive all packets successfully.Consider a broadcast transmission example of a cellular network, where all BS packet transmissions are assumed to reach all MSs. For a system with two MSs, that is,z1 and z2, we consider the pattern of lost packets shown in Figure 2 as an example, where a cross X and an oval O, respectively, represent a lost and a coded packet. Since K=2, the coded packets generated by the BS and intended for the two MSs, z1 and z2, are (a1⊕a2), (a3⊕a4), and a5. Packet a6 is only intended for MS z2 because MS z1 has already received it successfully. Note that if some coded packets cannot be correctly received by any of the intended MSs, the BS will update the lost packet table and determine the best coded packet for the next retransmission opportunity.Figure 2
An example of a pattern of lost packets at MSsz1 and z2.Without loss of generality, for a system withK MSs, we assume that PERi≤PERj if i≤j for any i,j∈{1,2,…,K} where PERi is the packet error rate for MS zi. Recall that the BS will generate a coded packet combining as many lost packets as possible, and the MS with the highest PER dominates the performance of the system. Let zK be this MS. Let Xi be a random variable representing the number of lost packets of MS zi after a certain number N, transmissions. When N approaches infinity and each transmission follows a Bernoulli trial, Xi will follow the Binomial random variable. Therefore, we have(1)E[max⁡i∈{1,2,…,K}{Xi}]≈E[XK].
With N transmitted packets to K MSs, the expected number of transmissions can be written as(2)N+E[XK]=N+N×max⁡i∈{1,2,…,K}{PERi}1-max⁡i∈{1,2,…,K}{PERi}=N1-max⁡i∈{1,2,…,K}{PERi}.
Note that the NC technique described in this section considers that packets will be broadcast to all MSs. Thus, packets sent by the BS can be heard either by all MSs or by none.


## 4. Joint Beamforming and Network Coding

In this work, we consider broadcast transmissions in a downlink channel of a cellular network, where data packets sent by the BS are intended for and reach all MSs in the network. When data packet transmission is not successful, the BS keeps retransmitting until the lost/unsuccessful packet is delivered to all MSs successfully. We assume that the BS needs to broadcastD packets to the MSs.After the first transmission, one or more MSs may not receive the packets. When this happens, one simple way to ensure successful delivery of packets is for the BS to retransmit/broadcast each lost packet to all MSs again (e.g., Figure3(a)). Another retransmission technique is to use beamforming to retransmit the lost packets only to those MSs that did not receive the packets. In this paper, we investigate and develop techniques that rely on MIMO to form BF beams so as to direct transmission towards a set of MSs only, that is, those MSs that did not receive the packets (e.g., Figure 3(b)). In addition to BF techniques, our proposed techniques rely on and incorporate network coding (NC) to further improve throughput performances of broadcast channels.NC example.
(a)
Without beamforming(b)
With beamformingSimply broadcasting lost packets to all MSs, instead of using BF technique, can be very inefficient for the following reasons. First, MSs are often located at different positions with various distances from the BS, leading to high variations of MSs received signal strengths. With this, different MSs are likely to experience different packet success rates. Second, without directing the transmitted signals, power could be wasted when signals are sent in directions/regions that happen to have no MSs. Let us consider the example shown in Figure3, where there are 3 groups of MSs: {z1,z2}, {z3}, and {z4}. In this example, transmitting packets to a location that does not contain any of the groups will be a waste of energy resources. By using a BF technique as in Figure 3(b), the BS can direct BF beams in such a way to increase the signal quality reaching the intended MSs. Note that the BS may use multiple time slots for transmitting a packet to everyone if all MSs are located apart from each other. The challenge as well as the novelty of the proposed BF technique lies in grouping all MSs into multiple clusters each corresponding to one beam in such a way to enhance broadcast throughput while minimizing power consumption.We now describe how to combine NC and BF to further improve broadcast network throughput. Figures4(a) and 4(b) illustrate the use of NC to broadcast a stream of packets in the network, respectively, shown in Figure 3(a) (without beamforming) and Figure 3(b) (with beamforming). In this example, there are 4 MSs (i.e., z1,z2,z3,z4). The BS needs to deliver 7 packets (i.e., a1,a2,…,a7) to all MSs and can generate at most 3 beams at once. Recall that the best strategy to generate a coded packet is to maximize the number of lost packets that can be coded at once. Therefore, we use 3 time slots to generate and send coded packets. In the first time slot, when not using a BF technique, the coded packet to be sent to all MSs is (a1⊕a2⊕a3⊕a4), whereas, when using a BF technique, the three coded/uncoded packets, (a1⊕a2), a3, and a4, are to be sent on beams 1, 2, and 3, respectively. In the second time slot, the BS generates coded packets that combine the lost packets a5 and a6 and sends them to MSs z1, z2, and z4. When not using a BF technique, the coded packet (a5⊕a6) is then to be sent to all MSs. Whereas, when using a BF technique, the coded packet (a5⊕a6) and uncoded packet a6 are to be transmitted through beams 1 (for z1 and z2) and 3 (for z4), respectively. In the third time slot, the BS needs to transmit only packet a7 to MS z4. In this case, it is obvious that there is no need to broadcast a packet a7 to everyone. Hence, when using a BF technique, the signal quality sent to MS z4 can be improved by allocating all transmit power to beam 3, thereby increasing the packet success rate and/or reducing energy consumption.Retransmission techniques.
(a)
Without beamforming(b)
With beamformingIn the first time slot, note that the coded packet combining the first 4 lost packets (i.e., without BF) when sent to all MSs exactly suffices as it enables each of the 4 MSs to recover its lost packet (i.e.,ai for zi). Thus, this may seem to be the best strategy. Likewise, the BF technique also suffices; that is, sending (a1⊕a2), a3, and a4 on three different beams 1, 2, and 3, respectively, also enables all MSs to recover their lost packets. The difference between the two techniques lies, however, on the fact that the BF technique can make received signals stronger, thus decreasing the packet error rates by increasing the chance of correctly decoding received packets.Note that there is a tradeoff in grouping MSs when using a BF technique. Grouping a large number of MSs under the same beam may reduce the number of coded packets but this would also lead to lesser chances of successfully receiving coded packets by an intended MS. Let us consider the example with 4 MSs as shown in Figure5. As can be seen in Figure 5(a), with one beam, the BS can simply use one coded packet for all 4 intended MSs. On the other hand, forming multiple groups of MSs (e.g., 2 MSs per beam as in this example) requires generating more coded packets, but MSs are more likely to receive higher signal quality, resulting in higher chances to successfully receive coded packets. Referring to Figure 5(b) again for illustration, the BS uses 2 coded packets: one for MSs z1 and z2 and the other for MSs z3 and z4. Note that the BS here can transmit 2 coded packets at the same time or at two successive time slots. One strategy to determine the sizes/groups of MSs for BF techniques is to minimize the variance of MSs lost packets in each group. This would allow the BS to efficiently generate coded packets while all MSs in each group can successfully receive all required packets at the same time. Therefore, efficient grouping algorithms that can determine the best sizes/groups are needed. In this paper, we develop and propose two efficient algorithms for grouping MSs.Example of MS grouping.
(a)
Without one BF beam(b)
With two BF beamsWe assume that the BS is equipped with multiple antenna systems that enable it to simultaneously generate multiple transmitted beams. We also assume that the BS knows all channel vectorshi associated with each MS zi for all i through feedback channels. Let Pi be the power allocated to beam i by the BS. For each beam i, we assign a group of MSs Vi where Vi⊆V, Vi∩Vj=∅ for any i,j∈{1,2,…,M}, and V is a set of all MSs. Groups are formed in such a way that all MSs belonging to the same group are likely to experience the same packet losses, reducing then the number of transmissions at the BS via bitwise XOR operations.The objective is to minimize the timeT for the BS to successfully deliver all D packets to each MS. Note that minimizing the time T is equivalent to maximizing the overall throughput under some fairness constraints. However, if a particular MS is far away from the BS such that it cannot receive packets, then clearly T=∞. In this work, we do not consider this degenerated case, and such an MS is likely to be serviced by a neighboring BS. Furthermore, we assume that the BS uses a round-robin transmission style and the channels at MSs are stationary. Thus, each MS will receive a fair share of transmission packets and the expected achievable throughput would reflect the performance of the considered system.Recall that the signal quality at MSs can be assessed/quantified via SINR. In particular,SINRij for MS zj in beam i can be computed as(3)SINRij=Pi|hjwi|2∑k=1(k≠i)MPk|hjwk|2+σ2,
where Pi, wi, hj, σ2, and M are transmit power, weight vector for beam i, channel vector for MS zj, noise power, and number of beams, respectively. If all transmitted beams are pairwise orthogonal such that |wiwk|2=0 and |h̃jwi|2=1 (assume that hj is normalized as h̃j so as to check its orthogonality), where zj∈Vi∖Vk, then |hjwk|2=0. Thus, (3) would reduce to SINRij=Pi|hjwi|2/σ2 (signal-to-noise ratio (SNR)). If all scheduled MSs have high SINR (or SNR), the equal power allocation is close to an optimal water-filling method [17]. Thus, the allocated transmit powers for all beams are all equal. Given a fixed total transmit power ℙ at the BS, this implies that the transmit power allocated for each beam j is Pj=ℙ/M where M is the number of active beams during that time.Letnj be a set of lost packets for MS zj. The number of transmissions for broadcast schemes over a group Vi depends on the combination of all lost packets from all MSs in Vi. Therefore, a set of coded and uncoded lost packets in Vi can be considered as NVi=∪∀jnj, where nj belongs to zj and zj∈Vi. Each group Vi is independent of any other group Vj for i≠j. This implies that the combination process of group Vi is totally independent of that of group Vj. Within each beam, the MS with the highest packet error rate would dominate the performance of that beam. For each beam i, the expected number of transmissions can be formulated as(4)NVi1-max⁡j{x(i,j)PERij},
where NVi is a set of coded/uncoded lost packets based on the NC technique applied to beam i, PERij is packet error rate for MS zj in beam i, and x(i,j) is an assignment binary variable for MS zj in beam i defined as(5)x(i,j)={1ifMSzjisinbeami,0otherwise.Furthermore, each MS can only belong to one beam; that is,∑ix(i,j)=1. For simplicity of analysis, we do not use any error correcting code. Therefore, PERij can be computed in terms of bit error rate (BERij) such that PERij=1-(1-BERij)α, where α is a packet size in bits. Assume BPSK is used. Thus, (6)BERij=0.5[1-erf⁡(SINRij)],whereerf(γ)≈(2/Π)[γ-(γ3/3)+(γ5/10)] and γ=SINRij [18]. The expected number of transmissions for this system is the time that the BS spends until all MSs successfully receive all of their required packets.Without lost of generality, (4) can be written as(7){NVi1-max⁡j{x(i,j)PERij}}lq,
where lq is the index of sets of BF beams. For each set lq, the BS requires to successfully transmit all lost packets over a set of all BF beams before moving forward to the next set of BF beams, that is, lq+1. Assume there are Q sets of BF beams to be used at the BS. By taking into account all Q sets of BF beams, our goal is then to minimize the total number of transmissions; that is,(8)minimize∑q{max⁡i{NVi1-max⁡j{x(i,j)PERij}}lq},s.t.∑ix(i,j)=1,x(i,j)∈{0,1},
where q={1,2,…,Q}. The solution to this optimization problem will be x(i,j) assignments that minimize the total number of transmissions. However, we prove that this assignment problem is NP-hard (we provide the proof of NP-hardness in the appendix), and, instead, we propose two heuristics/techniques that solve this group formation problem by taking advantage of NC capabilities and the orthogonality of user channels. One proposed technique uses greedy selection based on SINR levels, whereas the other technique uses a predefined codebook to generate a set of orthogonal BF beams. Let L={l1,l2,…,lQ} denote the Q sets of M orthogonal beams. For example, li=1 means the BS uses the ith set of M orthogonal beams in a codebook, otherwise li=0. Next, we describe our two proposed scheduling techniques.


## 5. Proposed Scheduling Algorithms

Because our assignment problem is NP-hard, we propose to use two techniques to design heuristic algorithms that efficiently solve it. The first technique schedules and groups MSs based on their SINRs, and the second one uses a predefined codebook that first generates multiple sets of orthogonal BF beams and then assigns each MS to the beam whose SINR is maximized. The details of the proposed techniques will be described next.


### 5.1. Technique 1: Greedy-Selection-Based Scheduler

We first describe and formulate the group formation problem, which basically tries to find the optimal set of MSs that maximizes the overall throughput and then proposes a scheduling algorithm that solves it. The scheduling algorithm improves overall throughput through joint exploitation of both BF and NC techniques. Given anM-transmit antenna BS and K one-receive antenna MSs located within the communication range of the BS, the BS can choose to transmit packets to a selected set of MSs that are located far apart from each other and whose quality levels are above a certain threshold. Note that the use of linear, equally spaced antenna arrays limits the number of concurrent signal beams to a certain number. We denote this number by Mopt, where Mopt≤M.When the number of MSs,K, exceeds Mopt, the BS chooses the best Mopt (or fewer) MSs with the highest SINRs. We consider spatial separation among MSs by using the orthogonality in channel vectors, described in [7]. Below, we describe our greedy-selection-based scheduling algorithm.The details of our proposed algorithm are described as follows: in step 1,𝒯i is a set of all available MSs and 𝒮 is a set of scheduled MSs where i represents the current iteration number. Thus, 𝒮 is initially empty and 𝒯i is equal to {1,2,…,K}. In step 2, we compute gk, the component of channel vector hk for each k in 𝒯i, orthogonal to previously determined subspace spanned by {g1,…,gi-1}. Note that when i=1, we assume gk=hk for each MS k. In step 3, we select the MS, denoted by π(i), whose norm ∥gk∥ is maximized (i.e., best MS) over each k∈𝒯i. After that we update the values of 𝒮, hi, and gi, consecutively. In step 4, after finding the best MS π(i), we further determine a cluster of MSs whose SINRs are greater than some threshold Ω. We denote this cluster by 𝒢(π(i)). Note that the value of Ω depends on MSs channel gain as well as their spatial distribution within a BS coverage area. Finally, in step 5, we determine 𝒯i+1 for next iteration by eliminating all MSs in 𝒢(π(i)) and all MSs whose channel vectors are not semiorthogonal to π(i) within a certain threshold α. If 𝒯i+1 is not an empty set and |𝒮|<Mopt, then go to step 2. Otherwise, the algorithm terminates and returns a set of π(i) with their corresponding cluster 𝒢(π(i)).Note that Algorithm1 requires two thresholds Ω and α. In practice, one can try multiple thresholds in order to select/determine the one that minimizes the number of total transmissions. We now propose our second technique.Algorithm 1:Greedy-selection-based algorithm.
step 1: Initializationi=1𝒯i={1,2,…,K}𝒮=∅(emptyset)step 2: For each MS k∈𝒯i, compute gk where gk is determined by hk semiorthogonal to the subspace{g1,…,gi-1}gk=hk(I-∑j=1i-1gj*gj/∥gj∥2){Note that wheni=1, assume gk=hk}step 3: Select the ith MS such thatπ(i)=argmaxk∈𝒯i∥gk∥𝒮:=𝒮∪{π(i)}hi=hπ(i)gi=gπ(i)step 4: Find a cluster of MSs whose SINRs are greater than some threshold Ω.  We denote that clusterby𝒢(π(i)) where π(i)∈𝒢(π(i)) and 𝒢(π(i))⊂𝒯istep 5: If |𝒮|<Mopt, compute 𝒯i+1 as follows:𝒯i+1:={k}wherek∈𝒯i,k∉𝒢(π(i)), and |hkhi*|∥hk∥∥hi∥≤αi=i+1{Note that if𝒯i+1≠∅ and |𝒮|<Mopt then go to step 2. Otherwise, the algorithm terminates andreturns a set of scheduled MSs}


### 5.2. Technique 2: Codebook-Based Scheduler

The second technique, as described in the pseudocode shown below, uses two algorithms: Algorithm2, which determines the best beam for each MS whose SINR is maximized and Algorithm  3, which further minimizes the number of transmissions. The outcome will be a set of MSs in V1,V2,…,VQ×M, an optimized codebook L, and the expected number of transmissions TQ. Pseudocode for technique 2V={z1,z2,…,zK}V1=V2=⋯=VQ×M=∅(emptyset)beginRun Algorithm2{determine the best beam for each MS}Run Algorithm3{further minimize the number of transmissions}endreturn a set of MSs in V1,V2,…,VQ×M, an optimized codebook L, and the expected number of transmissions TQ.Algorithm 2: Codebook-based allocation algorithm.
step 1: InitializationV={z1,z2,…,zK}V1=V2=⋯=VQ×M=∅(emptyset)step 2: For each MS zj in V, compute SINRij over all possible Q×M beams. Then, assign MS zjto beami* that maximizes SINRij such thati*=argmaxi{SINRij}{Note that if MSzj is assigned to beam i* in set lq of a codebook,  the interference will come fromall other beams in setlq, except beam i*}step 3: UpdateV=V-{zj}Vi*=Vi*∪{zj}step 4: If V≠∅ then go to step 2. Otherwise, the algorithm terminates and returns a set of MSs inV1,V2,…,VQ×M.Algorithm 3: Optimized codebook algorithm.
step 1: InitializationL={l1,l2,…,lQ}GivenV1,V2,…,VQ×McomputeTQstep 2: For each set lq of a codebook where q∈{1,2,…,Q}, compute the maximum value of PERsover all MSs assigned to a setlq such thatXlq=maxi{maxj{PERij}}lqstep 3: Eliminate a set lq* over all existing sets such thatlq*=argminlq{Xlq}step 4: For each MS zj in a set lq*, compute SINRij over all existing beams i except all beams ina setlq*. Then, assign MS zj to beam i* that maximizes SINRij such thati*=argmaxi{SINRij}step 5: Compute TQ-1step 6: If TQ-1≤TQ,updateV1,V2,…,V(Q-1)×ML=L-{lq*}Q=Q-1then go to step 2step 7: The algorithm terminates, then returns a set of MSs in V1,V2,…,VQ×M, an optimized codebookL, and the expected number of transmissions TQ.Algorithm2 is described as follows: in step 1, V represents the set of all K MSs and Q×M represents the number of all possible beams in a codebook. Vi is the set of all assigned MSs in beam i and is initially empty where i∈{1,2,…,Q×M}. In step 2, we select beam i* for MS zj whose SINR is maximized (the best assigned beam) over all possible beams. In step 3, we update the value of V and Vi*. Finally, in step 4, if V is not an empty set, then go to step 2. Otherwise, the algorithm terminates, and returns a set of MSs in V1,V2,…,VQ×M. If some set of MSs (e.g., Vi for beam i) is an empty set, this implies that the BS will not transmit any packets over that beam whose power allocation is zero. Note that Algorithm 2 minimizes the variance of SINRs of all MSs in each beam.Using allQ sets, a codebook may not be the best solution. In other words, using a large number of sets of a codebook implies that the BS spends an amount of time to successfully retransmit all lost packets while all MSs most likely have high SINR levels. However, when we lower SINR values for a certain set of MSs by eliminating some sets of a codebook and assigning these MSs to the remaining sets, the overall number of transmissions can be reduced. Therefore, we propose an algorithm to further minimize the number of transmissions as shown in Algorithm  3.Algorithm3 works as follows: in step 1, we have the original sets of a codebook L={l1,l2,…,lQ} and the groups of MSs in each V1,V2,…,VQ×M. Then, we compute the expected number of transmissions TQ where Q is the number of sets of a codebook. In step 2, we determine the maximum PER over all MSs assigned to each set lq of a codebook denoted by Xlq. The best set of a codebook (lq*), that is, the set that has the lowest value of the maximum PERs among all sets of a codebook, is determined in step 3. Because the set with the highest value of maximum PERs dominates the transmission performance in the system, when we eliminate the set lq*, the number of transmissions is likely to decrease. Then, we assign all MSs in the set lq* to all other existing sets as done in step 4. In step 5, we compute the expected number of transmissions TQ-1 after eliminating the set lq*. In step 6, if TQ-1≤TQ, then we go to step 2 for further codebook optimization. Otherwise, the algorithm returns the optimized codebook together with a set of MSs in V1,V2,…,VQ×M and the expected number of transmissions TQ as described in step 7.


## 5.1. Technique 1: Greedy-Selection-Based Scheduler

We first describe and formulate the group formation problem, which basically tries to find the optimal set of MSs that maximizes the overall throughput and then proposes a scheduling algorithm that solves it. The scheduling algorithm improves overall throughput through joint exploitation of both BF and NC techniques. Given anM-transmit antenna BS and K one-receive antenna MSs located within the communication range of the BS, the BS can choose to transmit packets to a selected set of MSs that are located far apart from each other and whose quality levels are above a certain threshold. Note that the use of linear, equally spaced antenna arrays limits the number of concurrent signal beams to a certain number. We denote this number by Mopt, where Mopt≤M.When the number of MSs,K, exceeds Mopt, the BS chooses the best Mopt (or fewer) MSs with the highest SINRs. We consider spatial separation among MSs by using the orthogonality in channel vectors, described in [7]. Below, we describe our greedy-selection-based scheduling algorithm.The details of our proposed algorithm are described as follows: in step 1,𝒯i is a set of all available MSs and 𝒮 is a set of scheduled MSs where i represents the current iteration number. Thus, 𝒮 is initially empty and 𝒯i is equal to {1,2,…,K}. In step 2, we compute gk, the component of channel vector hk for each k in 𝒯i, orthogonal to previously determined subspace spanned by {g1,…,gi-1}. Note that when i=1, we assume gk=hk for each MS k. In step 3, we select the MS, denoted by π(i), whose norm ∥gk∥ is maximized (i.e., best MS) over each k∈𝒯i. After that we update the values of 𝒮, hi, and gi, consecutively. In step 4, after finding the best MS π(i), we further determine a cluster of MSs whose SINRs are greater than some threshold Ω. We denote this cluster by 𝒢(π(i)). Note that the value of Ω depends on MSs channel gain as well as their spatial distribution within a BS coverage area. Finally, in step 5, we determine 𝒯i+1 for next iteration by eliminating all MSs in 𝒢(π(i)) and all MSs whose channel vectors are not semiorthogonal to π(i) within a certain threshold α. If 𝒯i+1 is not an empty set and |𝒮|<Mopt, then go to step 2. Otherwise, the algorithm terminates and returns a set of π(i) with their corresponding cluster 𝒢(π(i)).Note that Algorithm1 requires two thresholds Ω and α. In practice, one can try multiple thresholds in order to select/determine the one that minimizes the number of total transmissions. We now propose our second technique.Algorithm 1:Greedy-selection-based algorithm.
step 1: Initializationi=1𝒯i={1,2,…,K}𝒮=∅(emptyset)step 2: For each MS k∈𝒯i, compute gk where gk is determined by hk semiorthogonal to the subspace{g1,…,gi-1}gk=hk(I-∑j=1i-1gj*gj/∥gj∥2){Note that wheni=1, assume gk=hk}step 3: Select the ith MS such thatπ(i)=argmaxk∈𝒯i∥gk∥𝒮:=𝒮∪{π(i)}hi=hπ(i)gi=gπ(i)step 4: Find a cluster of MSs whose SINRs are greater than some threshold Ω.  We denote that clusterby𝒢(π(i)) where π(i)∈𝒢(π(i)) and 𝒢(π(i))⊂𝒯istep 5: If |𝒮|<Mopt, compute 𝒯i+1 as follows:𝒯i+1:={k}wherek∈𝒯i,k∉𝒢(π(i)), and |hkhi*|∥hk∥∥hi∥≤αi=i+1{Note that if𝒯i+1≠∅ and |𝒮|<Mopt then go to step 2. Otherwise, the algorithm terminates andreturns a set of scheduled MSs}


## 5.2. Technique 2: Codebook-Based Scheduler

The second technique, as described in the pseudocode shown below, uses two algorithms: Algorithm2, which determines the best beam for each MS whose SINR is maximized and Algorithm  3, which further minimizes the number of transmissions. The outcome will be a set of MSs in V1,V2,…,VQ×M, an optimized codebook L, and the expected number of transmissions TQ. Pseudocode for technique 2V={z1,z2,…,zK}V1=V2=⋯=VQ×M=∅(emptyset)beginRun Algorithm2{determine the best beam for each MS}Run Algorithm3{further minimize the number of transmissions}endreturn a set of MSs in V1,V2,…,VQ×M, an optimized codebook L, and the expected number of transmissions TQ.Algorithm 2: Codebook-based allocation algorithm.
step 1: InitializationV={z1,z2,…,zK}V1=V2=⋯=VQ×M=∅(emptyset)step 2: For each MS zj in V, compute SINRij over all possible Q×M beams. Then, assign MS zjto beami* that maximizes SINRij such thati*=argmaxi{SINRij}{Note that if MSzj is assigned to beam i* in set lq of a codebook,  the interference will come fromall other beams in setlq, except beam i*}step 3: UpdateV=V-{zj}Vi*=Vi*∪{zj}step 4: If V≠∅ then go to step 2. Otherwise, the algorithm terminates and returns a set of MSs inV1,V2,…,VQ×M.Algorithm 3: Optimized codebook algorithm.
step 1: InitializationL={l1,l2,…,lQ}GivenV1,V2,…,VQ×McomputeTQstep 2: For each set lq of a codebook where q∈{1,2,…,Q}, compute the maximum value of PERsover all MSs assigned to a setlq such thatXlq=maxi{maxj{PERij}}lqstep 3: Eliminate a set lq* over all existing sets such thatlq*=argminlq{Xlq}step 4: For each MS zj in a set lq*, compute SINRij over all existing beams i except all beams ina setlq*. Then, assign MS zj to beam i* that maximizes SINRij such thati*=argmaxi{SINRij}step 5: Compute TQ-1step 6: If TQ-1≤TQ,updateV1,V2,…,V(Q-1)×ML=L-{lq*}Q=Q-1then go to step 2step 7: The algorithm terminates, then returns a set of MSs in V1,V2,…,VQ×M, an optimized codebookL, and the expected number of transmissions TQ.Algorithm2 is described as follows: in step 1, V represents the set of all K MSs and Q×M represents the number of all possible beams in a codebook. Vi is the set of all assigned MSs in beam i and is initially empty where i∈{1,2,…,Q×M}. In step 2, we select beam i* for MS zj whose SINR is maximized (the best assigned beam) over all possible beams. In step 3, we update the value of V and Vi*. Finally, in step 4, if V is not an empty set, then go to step 2. Otherwise, the algorithm terminates, and returns a set of MSs in V1,V2,…,VQ×M. If some set of MSs (e.g., Vi for beam i) is an empty set, this implies that the BS will not transmit any packets over that beam whose power allocation is zero. Note that Algorithm 2 minimizes the variance of SINRs of all MSs in each beam.Using allQ sets, a codebook may not be the best solution. In other words, using a large number of sets of a codebook implies that the BS spends an amount of time to successfully retransmit all lost packets while all MSs most likely have high SINR levels. However, when we lower SINR values for a certain set of MSs by eliminating some sets of a codebook and assigning these MSs to the remaining sets, the overall number of transmissions can be reduced. Therefore, we propose an algorithm to further minimize the number of transmissions as shown in Algorithm  3.Algorithm3 works as follows: in step 1, we have the original sets of a codebook L={l1,l2,…,lQ} and the groups of MSs in each V1,V2,…,VQ×M. Then, we compute the expected number of transmissions TQ where Q is the number of sets of a codebook. In step 2, we determine the maximum PER over all MSs assigned to each set lq of a codebook denoted by Xlq. The best set of a codebook (lq*), that is, the set that has the lowest value of the maximum PERs among all sets of a codebook, is determined in step 3. Because the set with the highest value of maximum PERs dominates the transmission performance in the system, when we eliminate the set lq*, the number of transmissions is likely to decrease. Then, we assign all MSs in the set lq* to all other existing sets as done in step 4. In step 5, we compute the expected number of transmissions TQ-1 after eliminating the set lq*. In step 6, if TQ-1≤TQ, then we go to step 2 for further codebook optimization. Otherwise, the algorithm returns the optimized codebook together with a set of MSs in V1,V2,…,VQ×M and the expected number of transmissions TQ as described in step 7.


## 6. Performance Evaluation

We consider a downlink channel consisting of one BS and multiple MSs. The BS and each MS are, respectively, equipped with 4-transmit antenna elements and a 1-receive antenna element. The system parameters are set as follows: maximum number of concurrent signal beams isMopt=3; operation frequency is 5 GHz; antenna array spacing at the BS is Δx=λ/2 where λ is the wavelength; noise power is σ2=1; packet size is 1000 Bytes; number of transmitted packets per MS is 100 packets; modulation technique is BPSK. To be fair to all MSs, we assume that the BS adopts the round-robin transmission scheduling policy. The simulation is implemented with MATLAB.In broadcast scenarios, the BS transmits a packet to all MSs at once. One example of broadcast transmissions is digital TV broadcasting, where all MSs watch the same TV channel at the same time. Therefore, the BS needs only to transmit data packets omnidirectionally, which makes them reach all MSs. We assume that the BS uses one antenna to do so, and there is no need for applying BF techniques during data transmissions.For the purpose of evaluating the performance of our proposed scheduling algorithms, we consider evaluating four retransmission schemes: 1-Omni ARQ (i.e., traditional retransmission technique), 1-Omni NC (i.e., traditional with NC only), BF-ARQ (i.e., BF with traditional retransmission technique), BF-NC with SINR (proposed technique 1: greedy-selection-based scheduler), and BF-NC with codebook (proposed technique 2: codebook-based scheduler). Both 1-Omni ARQ- and 1-Omni NC-based retransmission schemes use one transmit antenna element, and retransmissions of lost packets are respectively done with ARQ and NC techniques only. BF-ARQ-based retransmission scheme is to use BF to retransmit lost packets to a group of MSs with ARQ techniques. The group formation for BF-ARQ is based on technique 1 (Algorithm1). The proposed BF-NC-based retransmission schemes use either technique 1 (Algorithm  1) or technique 2 (Algorithms  2 and 3). A graphical illustration of these schemes is given in Figure 6.Figure 6
Broadcast transmission/retransmission schemes.


### 6.1. Uniform MS Distribution on a Circle

First, we study the broadcast scenario shown in Figure7(a), where there are 120 uniformly distributed MSs, all having the same channel gain.Simulated network topology scenarios with different MS distributions.
(a)
Uniform distribution(b)
3-cluster distribution(c)
Random distributionRecall that the BS uses one transmit antenna during the data transmission phase, making signals/packets (transmitted omnidirectionally) reach all MSs. In Figure8(a), we show the average loss rate of packet transmissions during these omnidirectional transmissions as a function of the transmit power. Figures 8(b) and 8(c) show the total number of transmitted packets and throughput gain, respectively, as a function of power for all simulated retransmission schemes.Simulation results for network topology scenario of Figure7(a) with 120 uniformly distributed MSs.
(a)
Average packet loss rate(b)
Number of transmissions under proposed schemes(c)
Throughput gainFigure8(b) shows that 1-Omni NC-based retransmission scheme performs the best in this network scenario when compared with all the other retransmission schemes, followed by the BF-NC with codebook, the BF-NC with SINR, the 1-Omni ARQ, and then the BF-ARQ. The achieved performances of the 1-Omni NC scheme are expected in this network topology, since all MSs experience the same channel gain and signal strength. We will see later that this is no longer the case when considering more realistic scenarios where MSs may experience different gains. For the BF-NC with SINR (i.e., with greedy selection) scheme, SINR thresholds are set to 3 levels (6.75, 7.25, and 8.00) for grouping MSs in each beam. For completeness and to assess the impact of incorporating the NC technique, we also measure and plot in Figure 8(c) the throughput gains of the 1-Omni NC, the BF-ARQ, the BF-NC with SINR, and the BF-NC with codebook over the 1-Omni ARQ-based retransmission scheme. In all figures, a throughput gain of ratio 1 means that both retransmission schemes use the same number of total transmissions. The figure shows that the 1-Omni NC- and the BF-NC-based retransmission schemes reach throughput gains of ratio 2.2 (i.e., 120% gain) and 1.5 (i.e., 50% gain), respectively. Even though both of the proposed BF-NC-based retransmission schemes have similar results, we lean towards the codebook-based one since it does not require multiple levels of SINR thresholds while still achieving similar performances.


### 6.2. Clustered MS Distribution on a Circle

In this section, we consider studying a network topology with a clustered MS distribution. Specifically, we consider the network topology scenario of Figure7(b), where 60 MSs are grouped into 3 clusters each having 20 MSs.All MSs in each cluster are close to one another, and the channel gains for all MSs belonging to the same cluster are the same (or close). Figure9(a) shows the average loss rate of omnidirectional packet transmissions (without including retransmissions) as function of the transmit power. In Figure 9(b), we show the number of total transmissions (including retransmissions) under each of the studied retransmission schemes as function of the transmit power. First, observe that unlike the case when MSs are uniformly distributed (as illustrated in Section 6.1), when MSs are not uniformly distributed, the proposed retransmission schemes (both BF-NC with SINR and BF-NC with codebook) outperform not only the traditional retransmission scheme (i.e., 1-Omni ARQ and BF-ARQ), but also the traditional scheme with NC (i.e., 1-Omni NC scheme). The total number of transmissions needed under the proposed schemes is substantially lesser than that needed under the 1-Omni ARQ and the 1-Omni NC, especially for low transmit power levels. This is because the BS can now efficiently allocate the power to a set of active BF beams instead of spreading the power in all directions, strengthening then the signals received at intended MSs, and as a consequence, increasing MSs SINRs.Simulation results for network topology scenario of Figure7(b) with 60 MSs formed into 3 clusters.
(a)
Average packet loss rate(b)
Number of transmissions under proposed schemes(c)
Throughput gainThe second observation that we can draw from the figure is that both proposed techniques achieve very similar performances in terms of the total number of transmissions. This is because when all MSs in the same cluster have similar channel gain, each coded packet most likely comes from all MSs whose packet loss rates are similar. In other words, this maximizes the number of lost packets to be coded at once.We now plot the throughput gains of the proposed schemes and the 1-Omni NC scheme when compared with the traditional scheme (i.e., 1-Omni ARQ). As shown in Figure9(c), the throughput gains for the 1-Omni NC- and the BF-NC-based retransmission schemes can reach up to 120% (ratio of 2.2) and 175% (ratio of 2.75), respectively. Note that the incorporation of NC into the 1-Omni scheme results in almost halving the number of total transmissions, whereas the incorporation of these same NC techniques into BF-based schemes (whether SINR or codebook based) reduces the number of total transmissions by almost a third.


### 6.3. Random MS Distribution inside the Circle

Finally, we study a network topology with a random MS distribution. In particular, we consider the network topology scenario of Figure7(c), where 120 MSs are randomly distributed at distances from the base station such that their channel gains are uniformly distributed between 0.7 and 1.3. Furthermore, the angles are normally distributed with the mean of 90 and standard deviation of 30 degrees. Any station located outside the range of [0,180] degrees ignored.The average loss rate of packet transmissions during these omnidirectional transmissions is shown in Figure10(a). The performance of BF-based retransmission schemes in this case is under that of the 1-Omni NC scheme as in Figure 10(b). Specifically, the 1-Omni NC scheme has the best result followed by NC-based retransmissions (i.e., BF-NC with SINR or codebook), the 1-Omni ARQ, and the BF-ARQ, respectively. Finally, Figure 10(c) shows the throughput gain with respect to the 1-Omni ARQ scheme. This is intuitively plausible as when mobile stations are dispersed too much, beamforming becomes less effective. In this case, omnitransmission makes sense and NC provides additional benefit with fewer retransmissions. Thus, 1-Omni NC transmission scheme performs the best.Simulation results for network topology scenario of Figure7(c) with 120 randomly distributed MSs inside a circle.
(a)
Average packet loss rate(b)
Number of transmissions under proposed schemes(c)
Throughput gain


### 6.4. Impact of Number of MSs

In this section, we want to study the impact of the number of MSs on the performance behaviors. In this simulation, we use the network topology of Figure7(a), where the number of MSs is varied from 120 to 300. In all scenarios, all MSs have the same channel gains. Figure 11(a) shows how the number of transmissions changes as the number of MSs is varied for each of the proposed retransmission schemes. As expected, when increasing the number of MSs, the BS tends to spend more time to successfully retransmit all lost packets to all corresponding MSs. The number of transmissions when using the BF-NC with codebook retransmission scheme is less than that of the BF-NC with greedy selection (with SINR) retransmission scheme. Note that the number of MSs affects the throughput gain of both BF-NC-based retransmission schemes; this is shown in Figure 11(b). The higher the number of MSs, the higher the chances of combining more lost packets before retransmitting, thus leading to higher throughput gains (lesser transmissions).Simulation results for network topology scenario of Figure7(a) when varying the number of MSs.
(a)
Number of transmissions under proposed schemes.(b)
Throughput gain


## 6.1. Uniform MS Distribution on a Circle

First, we study the broadcast scenario shown in Figure7(a), where there are 120 uniformly distributed MSs, all having the same channel gain.Simulated network topology scenarios with different MS distributions.
(a)
Uniform distribution(b)
3-cluster distribution(c)
Random distributionRecall that the BS uses one transmit antenna during the data transmission phase, making signals/packets (transmitted omnidirectionally) reach all MSs. In Figure8(a), we show the average loss rate of packet transmissions during these omnidirectional transmissions as a function of the transmit power. Figures 8(b) and 8(c) show the total number of transmitted packets and throughput gain, respectively, as a function of power for all simulated retransmission schemes.Simulation results for network topology scenario of Figure7(a) with 120 uniformly distributed MSs.
(a)
Average packet loss rate(b)
Number of transmissions under proposed schemes(c)
Throughput gainFigure8(b) shows that 1-Omni NC-based retransmission scheme performs the best in this network scenario when compared with all the other retransmission schemes, followed by the BF-NC with codebook, the BF-NC with SINR, the 1-Omni ARQ, and then the BF-ARQ. The achieved performances of the 1-Omni NC scheme are expected in this network topology, since all MSs experience the same channel gain and signal strength. We will see later that this is no longer the case when considering more realistic scenarios where MSs may experience different gains. For the BF-NC with SINR (i.e., with greedy selection) scheme, SINR thresholds are set to 3 levels (6.75, 7.25, and 8.00) for grouping MSs in each beam. For completeness and to assess the impact of incorporating the NC technique, we also measure and plot in Figure 8(c) the throughput gains of the 1-Omni NC, the BF-ARQ, the BF-NC with SINR, and the BF-NC with codebook over the 1-Omni ARQ-based retransmission scheme. In all figures, a throughput gain of ratio 1 means that both retransmission schemes use the same number of total transmissions. The figure shows that the 1-Omni NC- and the BF-NC-based retransmission schemes reach throughput gains of ratio 2.2 (i.e., 120% gain) and 1.5 (i.e., 50% gain), respectively. Even though both of the proposed BF-NC-based retransmission schemes have similar results, we lean towards the codebook-based one since it does not require multiple levels of SINR thresholds while still achieving similar performances.


## 6.2. Clustered MS Distribution on a Circle

In this section, we consider studying a network topology with a clustered MS distribution. Specifically, we consider the network topology scenario of Figure7(b), where 60 MSs are grouped into 3 clusters each having 20 MSs.All MSs in each cluster are close to one another, and the channel gains for all MSs belonging to the same cluster are the same (or close). Figure9(a) shows the average loss rate of omnidirectional packet transmissions (without including retransmissions) as function of the transmit power. In Figure 9(b), we show the number of total transmissions (including retransmissions) under each of the studied retransmission schemes as function of the transmit power. First, observe that unlike the case when MSs are uniformly distributed (as illustrated in Section 6.1), when MSs are not uniformly distributed, the proposed retransmission schemes (both BF-NC with SINR and BF-NC with codebook) outperform not only the traditional retransmission scheme (i.e., 1-Omni ARQ and BF-ARQ), but also the traditional scheme with NC (i.e., 1-Omni NC scheme). The total number of transmissions needed under the proposed schemes is substantially lesser than that needed under the 1-Omni ARQ and the 1-Omni NC, especially for low transmit power levels. This is because the BS can now efficiently allocate the power to a set of active BF beams instead of spreading the power in all directions, strengthening then the signals received at intended MSs, and as a consequence, increasing MSs SINRs.Simulation results for network topology scenario of Figure7(b) with 60 MSs formed into 3 clusters.
(a)
Average packet loss rate(b)
Number of transmissions under proposed schemes(c)
Throughput gainThe second observation that we can draw from the figure is that both proposed techniques achieve very similar performances in terms of the total number of transmissions. This is because when all MSs in the same cluster have similar channel gain, each coded packet most likely comes from all MSs whose packet loss rates are similar. In other words, this maximizes the number of lost packets to be coded at once.We now plot the throughput gains of the proposed schemes and the 1-Omni NC scheme when compared with the traditional scheme (i.e., 1-Omni ARQ). As shown in Figure9(c), the throughput gains for the 1-Omni NC- and the BF-NC-based retransmission schemes can reach up to 120% (ratio of 2.2) and 175% (ratio of 2.75), respectively. Note that the incorporation of NC into the 1-Omni scheme results in almost halving the number of total transmissions, whereas the incorporation of these same NC techniques into BF-based schemes (whether SINR or codebook based) reduces the number of total transmissions by almost a third.


## 6.3. Random MS Distribution inside the Circle

Finally, we study a network topology with a random MS distribution. In particular, we consider the network topology scenario of Figure7(c), where 120 MSs are randomly distributed at distances from the base station such that their channel gains are uniformly distributed between 0.7 and 1.3. Furthermore, the angles are normally distributed with the mean of 90 and standard deviation of 30 degrees. Any station located outside the range of [0,180] degrees ignored.The average loss rate of packet transmissions during these omnidirectional transmissions is shown in Figure10(a). The performance of BF-based retransmission schemes in this case is under that of the 1-Omni NC scheme as in Figure 10(b). Specifically, the 1-Omni NC scheme has the best result followed by NC-based retransmissions (i.e., BF-NC with SINR or codebook), the 1-Omni ARQ, and the BF-ARQ, respectively. Finally, Figure 10(c) shows the throughput gain with respect to the 1-Omni ARQ scheme. This is intuitively plausible as when mobile stations are dispersed too much, beamforming becomes less effective. In this case, omnitransmission makes sense and NC provides additional benefit with fewer retransmissions. Thus, 1-Omni NC transmission scheme performs the best.Simulation results for network topology scenario of Figure7(c) with 120 randomly distributed MSs inside a circle.
(a)
Average packet loss rate(b)
Number of transmissions under proposed schemes(c)
Throughput gain


## 6.4. Impact of Number of MSs

In this section, we want to study the impact of the number of MSs on the performance behaviors. In this simulation, we use the network topology of Figure7(a), where the number of MSs is varied from 120 to 300. In all scenarios, all MSs have the same channel gains. Figure 11(a) shows how the number of transmissions changes as the number of MSs is varied for each of the proposed retransmission schemes. As expected, when increasing the number of MSs, the BS tends to spend more time to successfully retransmit all lost packets to all corresponding MSs. The number of transmissions when using the BF-NC with codebook retransmission scheme is less than that of the BF-NC with greedy selection (with SINR) retransmission scheme. Note that the number of MSs affects the throughput gain of both BF-NC-based retransmission schemes; this is shown in Figure 11(b). The higher the number of MSs, the higher the chances of combining more lost packets before retransmitting, thus leading to higher throughput gains (lesser transmissions).Simulation results for network topology scenario of Figure7(a) when varying the number of MSs.
(a)
Number of transmissions under proposed schemes.(b)
Throughput gain


## 7.  Conclusion

This paper proposes two joint BF/NC-based scheduling algorithms for wireless broadcast downlink channels. The first algorithm relies on greedy selection of MSs based on their SINRs, whereas the second algorithm uses codebook to group and schedule MSs. The greedy selection approach consists of using MSs orthogonality and their physical locations to maximize their signal quality over a wireless network. The codebook-based approach, on the other hand, uses a predefined codebook to generate multiple sets of orthogonal beams.Our results show that both of the proposed techniques/algorithms increase the overall throughput by minimizing the number of transmission attempts.Our simulations indicate that our techniques reduce the number of retransmission attempts significantly, resulting in achieving high throughput gain of up to 175% of broadcast transmissions when compared to that of traditional ARQ retransmission approaches.



---

*Source: 342512-2012-03-18.xml*