Resource Allocation Scheme for Millimeter Wave-Based WPANs Using Directional Antennas
Resource Allocation Scheme for Millimeter Wave-Based WPANs Using Directional Antennas
ETRI Journal. 2014. Jun, 36(3): 385-395
Copyright © 2014, Electronics and Telecommunications Research Institute(ETRI)
  • Received : July 15, 2013
  • Accepted : November 27, 2013
  • Published : June 01, 2014
Export by style
Cited by
About the Authors
Meejoung, Kim
Yongsun, Kim
Wooyong, Lee

In this paper, we consider a resource allocation scheme for millimeter wave–based wireless personal area networks using directional antennas. This scheme involves scheduling the reservation period of medium access control for IEEE 802.15.3c. Objective functions are considered to minimize the average delay and maximize throughput; and two scheduling algorithms—namely, MInMax concurrent transmission and MAxMin concurrent transmission—are proposed to provide a suboptimal solution to each objective function. These are based on an exclusive region and two decision rules that determine the length of reservation times and the transmission order of groups. Each group consists of flows that are concurrently transmittable via spatial reuse. The algorithms appropriately apply two decision rules according to their objectives. A real video trace is used for the numerical results, which show that the proposed algorithms satisfy their objectives. They outperform other schemes on a range of measures, showing the effect of using a directional antenna. The proposed scheme efficiently supports variable bit rate traffic during the reservation period, reducing resource waste.
I. Introduction
It is envisioned that emerging multimedia applications, such as high-definition video streaming and fast data transfer, will be supported in high data-rate wireless personal area networks (WPANs). In pursuit of this, a great deal of attention has recently been given to spectrum utilization in the millimeter wave (mmWave) band range of 30 GHz to 300 GHz. There are three published standards for mmWave WPANs—namely, IEEE 802.15.3c, 802.11ad, and ECMA-387 [1] [3] . The former two are based on centralized networks, aiming for more than 2 Gbps and 7 Gbps, respectively, as target data rates, while the latter is based on distributed networks aiming for more than 7 Gbps as a target data rate.
The mmWave has the following unique characteristics: short wavelength, high frequency, large bandwidth, and high interaction with atmospheric constituents. Such characteristics are associated with many salient properties, such as a high data rate (multi-Gbps), as well as problems, such as a high path loss and short communication range, compared to other frequency bands. The mmWave signal is degraded significantly when it is passed through walls and over long distances, and it is highly susceptible to blockages attributed to its limited ability to diffract around obstacles. To compensate for these problems, the utilization of directional antennas is recommended.
There are two methods of medium access control (MAC): contention-based MAC and reservation-based MAC. As the reservation period is only available to allowed users, there is no unexpected interference between them. The period assigned to a flow is occupied by it in each superframe until the flow ends or the device (DEV) requests the channel release, or both. Therefore, applications that have to send data steadily over a fixed time interval or that have stringent quality of service (QoS), or both, must be scheduled to transmit during the reservation period to fulfill their needs. Owing to the characteristics of mmWaves, it is suitable for applications that require not only a high data rate but also a stringent QoS in terms of delay, jitter, and packet loss, such as IPTV and wireless high-definition multimedia interface. As traffic for such applications tends to be isochronous, it must be transmitted regularly and steadily over continuous superframes. Therefore, resource reservation is more relevant and effective than resource contention for transmitting these applications.
Resource allocation in the mmWave band is a challenging problem because of the complexity that arises when directional antennas are used. In this paper, a resource allocation scheme for WPANs based on IEEE 802.15.3c is considered. This scheme involves grouping the concurrently transmittable flows and scheduling the MAC reservation period, including the construction of reservation blocks. The transmission groups are determined by an exclusive region (ER)-based grouping algorithm, where each group consists of concurrently transmittable loads. Various methods can be used to construct reservation blocks according to resource allocation schemes and objective functions. We consider two objective functions: minimizing average delay and maximizing throughput. Two scheduling algorithms—namely, MInMax concurrent transmission (MIMCT) and MAxMin concurrent transmission (MAMCT)—are proposed to provide a suboptimal solution to each objective function. The scheduling algorithms are based on two decision rules, and each considers the effects of co-channel interference (CCI) and blockages.
The outline of this paper can be summarized as follows: a) From a set of flows, concurrently transmittable flows are grouped based on the ER. b) Characteristics of the mmWave band, such as its susceptibility to blockage and the effect of CCI, are considered. c) The method of constructing reservation blocks is involved in the scheduling algorithms. d) Characteristics of IEEE 802.15.3c, such as the path loss model and parameters, are used. e) The proposed scheduling schemes consider the objective functions. f) Simulations are performed using real video traffic.
Section II provides the concept of an ER. The objective functions are formulated in section III, and the scheduling algorithms are presented in section IV. We explicitly describe the performance measures in section V and present our numerical results in section VI. Finally, section VII concludes the paper.
II. Background and System Model
- 1. Related Work
Considerable research has been conducted on mmWave WPANs using directional antennas [4] [18] . In [4] [12] , the general issues of mmWave WPANs—namely, the degree of interference and diffraction effect at 60 GHz, modeling of the beacon period length, and the directional MAC protocols—were considered and analyzed. In particular, [13] [18] considered resource allocation algorithms for mmWave WPANs using directional antennas. The estimated signal-to-interference-plus-noise-ratio was primarily used as the criterion for concurrent transmission scheduling schemes [13] , [14] . Admission control and concurrent scheduling for IPTV traffic were considered over a mmWave—based WPAN in [14] . The concept of an ER was introduced in [15] . ER-based resource allocation schemes were considered for mmWave WPANs in [15] , [16] . The method of grouping concurrently transmittable flows by this ER-based criterion is similar to finding the maximal independent set in conflict graph-based scheduling schemes [17] , [19] . In [17] , a frame-based scheduling directional MAC protocol was developed based on a graph coloring-based scheduling algorithm. Its aim was to minimize the total transmission time with low complexity. Based on the space isolation caused by significant path loss of a mmWave, a deflection routing scheme [9] and a spatial time-slot scheduling algorithm [18] were proposed aiming to improve the throughput. Recently, a hybrid MAC-based resource management was proposed for mmWave WPANs that did not consider directional antennas [20] .
The resource allocation algorithms in these references were confined by some limitations. In [14] , the concurrent transmission of flows was covered; however, only the link test was considered in the scheduling scheme. The method of constructing the reservation blocks was not an issue. The system performance may vary depending on how the reservation blocks are constructed. For instance, if a longer packet is transmitted prior to a shorter packet, the shorter packet has to wait for a long time, eventually causing a longer average delay. In addition, factors such as the CCI and the existence of blockages may degrade the performance owing to the characteristics of the 60 GHz band. Therefore, resource allocation schemes should consider these factors to be more accurate and applicable in mmWave communication. Existing papers on concurrent transmission schemes considered neither the method of constructing reservation blocks nor the effect of the CCI and blockages.
- 2. Exclusive Region
We employ the cone-plus-circle model that considers the sidelobe effect for a two-dimensional scenario, assuming all DEVs lie in a plane. The antenna gains with the mainlobe and the sidelobe are then defined by G m = 10log 10 (2π ƞ / θ ) and G s = 10log 10 {2π(1− ƞ ) / (2π − θ )}, (unit: dBi) respectively, where ƞ and θ are the antenna radiation efficiency and mainlobe beamwidth, respectively.
If multiple transmissions can occur simultaneously without interference, these links can coexist in the same channel. That is, there exists a region where a transmitter-receiver pair can communicate without interference. This is called an ER. The ER with directional antennas is defined as follows: each flow consisting of a transmitter-receiver pair has an ER around the receiver, and the transmitters of all other flows sending simultaneously must be located outside this ER.
Figure 1 illustrates the shapes and radii of the ERs for four possible cases. The detailed explanations of Fig. 1 and the following ER radius for each case can be found in [8] (unit: m)
(1) r 1 = ( κ G TM G RM P T N 0 W ) 1/α ,   r 2 = ( κ G TS G RM P T N 0 W ) 1/α , r 3 = ( κ G TM G RS P T N 0 W ) 1/α ,  and  r 4 = ( κ G TS G RS P T N 0 W ) 1/α ,
where G TM ( G TS ) and G RM ( G RS ) are the antenna gain of the mainlobe (sidelobe) of a transmitter and a receiver, respectively. The transmission power, constant proportional to 10log 10 ( λ / 4π) 2 = −68.0048 dB, one-sided spectral density of the white Gaussian noise, channel bandwidth, and the path loss exponent are represented by P T , κ , N 0 , W , and α , respectively. The wavelength of the signal is λ , given by λ = c/ f (c is the speed of light, and f is the frequency of the signal, which in this case is 60 GHz).
Because the distance between a transmitter (T in Fig. 1 ) of another flow and a receiver (R in Fig. 1 ) of a tagged flow must be greater than the ER radius for concurrent transmission of the two different flows, we will use (1) as an ER criterion for concurrent transmission.
PPT Slide
Lager Image
Four different ER radii for directional antenna pairs.
III. Grouping Algorithm and Formulation of Objective Functions
Our work is focused on scheduling schemes that efficiently assign channel time allocations (CTAs) in the channel time allocation period (CTAP) of IEEE 802.15.3c, to minimize the average delay or maximize the throughput, or both. We consider schemes with a single channel and assume that each DEV is equipped with a directional antenna. It is assumed that the PNC has information of each DEV via a directional neighbor discovery (D-ND) process [21] , which was performed in the contention access period (CAP). Based on the information, the PNC can set the ER criterion for each flow. As the D-ND and the beamforming process between two DEVs is required (once in the initial setup using the same scheduling algorithm), the effect of these processes on performance is negligible in the steady state. Therefore, the antennas of all transmitter-receiver pairs are assumed to be directed toward their peers. It is also assumed that a DEV cannot transmit and receive simultaneously and that the mainlobe and sidelobe antenna gains and transmission power are the same for all DEVs. The time duration of a superframe and the CAP are fixed and denoted as T SF and T CAP , respectively. To simplify the analysis, we assume that each associated DEV within a piconet has a dedicated time slot in an MCTA period, which is used to send channel time request packets to the PNC. This gives the duration of the MCTA period as T MCTA = N req × t slot , where N req is the number of flows requesting the channel assignment in a piconet and t slot is the time duration of a slot. The modeling of traffic requiring a high data rate was considered in [14] , [22] , [23] . In [23] , a two-level Markov model was proposed to model bursty traffic with a high correlation among frames, such as in high density video. The accuracy of the model was validated by a simulation using real video traces.
It is assumed that all flows have the same level of importance and frame fragmentation is performed by each DEV if necessary. Therefore, each DEV can use several CTAs in a superframe. Although the remainder of the CTAP is insufficient to completely transmit a frame, the PNC will assign it to the frames. Owing to the use of a directional antenna, N req flows can be grouped in such a way that they can be transmitted concurrently in the same CTA block by spatial reuse. If n groups (where n N req ) are scheduled for transmission in a superframe, the duration of the CTAP, T CTAP , can be calculated as
(2) T CTAP = T MCTA + ∑ i=1 n ( T CTA i + T guard ) , 
where T guard is the guard time required to prevent transmission collisions between adjacent CTAs and T CTAi is the duration of the i th CTA block. Once a DEV is scheduled to use a CTA block, it uses that block in subsequent superframes for as long as it has frames to send or does not request CTA blocks to be changed, or both. In this paper, we distinguish between the groups of flows and groups of loads.
Description of notation.
Notation Description
ℑ(ℑs) Set of flows requesting channel (supported by min RRmin)
Φ(Φs) Load set of flows in ℑ(ℑs)
Fi(Gi) Set of concurrently transmittable flows (loads)
FC(GC) Set of flows (loads) contained in more than two Fi’s (Gi’s)
A(i)(A((i))) Ordered set of A(i)(A(i)) (Ai: Gi, Gi\GC)
{ l (i)j } j1 g(i) ( { l ((i))j } j1 g((i)) ) Elements of A(i)(A((i))) (Ai: Gi, Gi\GC)
Let ℑ = { fi : i = 1, … , N req } and Φ denote the set of flows that request the channel to transmit during the following superframe and the corresponding set of loads, respectively. Furthermore, let Fi and FC be the subsets of ℑ consisting of all concurrently transmittable flows and the flows contained in more than two Fi ’s, respectively, and let Gi and GC be the subsets of Φ consisting of the loads corresponding to the flows in Fi and FC , respectively. A description of this notation is summarized in Table 1 .
To generate Fi and FC , a grouping algorithm is proposed. The grouping algorithm is based on the ER criterion, and it allows us to obtain from ℑ(Φ), both Fi ( Gi ) and FC ( GC ). The procedure used to obtain the Fi ’s is similar to that for finding the maximal independent set in conflict graph–based scheduling schemes. The grouping algorithm is as follows:
       Algorithm 1 Grouping algorithm 1:  Initially set i =1 and generate F1 and FC as empty sets. 2:  PNC randomly selects a flow from ℑ. Insert the selected flow to Fi and remove it from ℑ. 3:  Select a new flow from ℑ. 4:  Check whether the newly selected flow satisfies the ER criterion with each flow in Fj, for all j,ji.     (i) If it satisfies the ER criterion, insert it into Fj and remove it from ℑ.     (ii) If it does not satisfy the ER criterion with one or more flows in Fj, for all j,ji generate Fi+1. Insert it into Fi+1 and remove it from ℑ. Set i to i +1. 5:  Repeat lines 3–4 until ℑ = ∅. 6:  Find the flows belonging to more than two Fj’s. Insert those into FC.
Note that the total time that is needed by the PNC to set the ER criterions of all flows is less than T CAP (the duration of CAP), which was shown in [21] . Furthermore, the complexity of Algorithm 1 is O( N req log N req ).
Assume that
{ F i } i=1 k
{ G i } i=1 k
, for k N req , are generated by Algorithm 1. Let lij and
l ij C
be the loads of flow j in Gi \ GC and
G i ∩ G C
, respectively. Here, Gi \ GC is
G i ∩ G C com
, where “com” denotes the complement.
Let , gi , ci and c be the number of loads in Gi \ GC ,
G i ∩ G C
, and GC , respectively. Then, Gi \ GC = { l i1 ,…, ligi },
G C ={ l i c 1 C ,   ...   , l i c i C :i=1,   ...   ,k,   ∑ i=1 k c i =c
with some ci = 0 },
G i ={ l i1 ,   ...   , l i g i , l i1 C ,   ...   , l i c i C },
∑ i=1 k g i +c= N req .
That is,
∑ j=1 g i l ij + ∑ j=1 c i l ij C
loads can be transmitted in the same CTA block. For illustration, we consider an example.
Example 1. Let the number of flows that PNC has to schedule for the next superframe be N = 10 with f 1 (3), f 2 (2), f 3 (2), f 4 (4), f 5 (1), f 6 (6), f 7 (10), f 8 (7), f 9 (8), and f 10 (9). The values in parentheses denote the load of the corresponding flow. Assume that these 10 flows are grouped according to Algorithm 1 to obtain the following sets: F 1 = { f 1 , f 4 , f 6 , f 8 , f 10 }, F 2 = { f 2 , f 3 , f 4 , f 7 }, F 3 = { f 1 , f 4 , f 5 }, F 4 = { f 8 , f 9 , f 10 }, and FC = { f 1 , f 4 , f 8 , f 10 }. Then, the values defined above are given by G 1 = {3, 4, 6, 7, 9}, G 2 = {2, 2, 4, 10}, G 3 = {1, 3, 4}, G 4 = {7, 8, 9}, G C = {3, 4, 7, 9}, G 1 \ G C = {6}, G 2 \ G C = {2, 2, 10}, G 3 \G C = {1}, g 1 = 1, g 2 = 3, g 3 = 1, g 4 = 1, and c = 4.
I s l ( I s g ) and  I ns l ( I ns g )
denote the index sets consisting of the indices of flows (groups) that are scheduled and not scheduled for transmission in the following superframe, respectively. Then,
| I s l |+| I ns l |= N req  and | I s g |+| I ns g |=k
, where | A | is the number of elements in A . In this paper, we assume that the data rate Ri of the DEV with flow i must satisfy the relation R min Ri R max for transmission. The minimum and maximum data rates supported by the underlying technology are R min and R max .
Given that the objective of our scheduling procedure is to minimize the average delay for a frame, E ( D ), which is called optimal delay (OPD), and to maximize the throughput in the CTAP, Th CTAP , which is called optimal throughput (OPT), we consider the following two objective formulas:
(3) OPD:        min E( D ) = min ( WT+ST )           
(4) OPT:   maxT h CTAP               =max( ∑ i∈ I s l ,transmitted l i T SF −( T beacon +2 T guard + T CAP + T MCTA ) ),
where WT and ST are the waiting and service times of a frame, respectively. The load amounts that are scheduled and successfully transmitted is denoted by
∑ i∈ I s l ,transmitted l i .
The two objective functions must be solved under the following condition:
(5) T beacon  +2 T guard  + T CAP  + T MCTA  + ∑ i∈ I s g ( T CTA i  + T guard ) ≤ T SF .
IV. Concurrent Transmission Scheduling Schemes
As the optimal scheduling problem is NP-hard (for the proof, see Appendix in [16] ), we propose heuristic scheduling algorithms for the two objective formulas: MIMCT for OPD and MAMCT for OPT. The algorithms are based on the grouping algorithm and two decision rules that determine the CTA block sizes and the group transmission order. Two main factors are considered to determine the transmission order of the groups: minimizing the total transmission time and maximizing the number of transmitted flows (loads) in a given period. Obviously, transmitting a group with a shorter processing time first will reduce the overall transmission delay, whereas transmitting a group with more flows (loads) first will increase the throughput. The following two propositions encapsulate these basic ideas.
Proposition 1. Suppose there are N frames with loads { l 1 , …, lN } and that these are assumed to be transmitted via TDMA. To minimize the average transmission delay of the frames, they must be transmitted in the order of the shortest processing time—termed the “shortest processing time first” algorithm.
Proposition 2. Assume that several frames can be transmitted simultaneously by spatial reuse. That is, they can be transmitted via spatial division multiple access. Let { Gi } i=1 k be a set of groups, where each group Gi consists of frame loads that can be transmitted simultaneously. To transmit as many frames as possible in a fixed period, the groups must be transmitted in order of decreasing | Gi |.
The proofs of the two propositions are self-explanatory and as such are not presented here.
The use of an ordered set of specific values in a scheduling scheme, such as transmission times or number of flows, is well known. However, determining the values that have to be ordered for scheduling is another issue, and the performance can vary depending on how these values are determined. The values may depend on the environment and the objective of the scheme. In addition, to attain more adequate and applicable resource assignment schemes in mmWave communications, it is better to consider the characteristics of mmWave and environmental factors that may change the link quality. There are several such factors: blocking by humans and furniture, reflections from objects, movements of DEVs, temporal changes of channels, and CCI by adjacent piconets using the same channel. We consider the link quality to vary owing to two main factors: blockages and CCI, which can occur simultaneously during transmission. With the consideration of these factors, the data rate of a frame for concurrent transmissions of several frames that was given in [8] must be modified. Let P cci be the probability of channel degradation caused by CCI. As a DEV knows whether it is influenced by CCI from adjacent piconets using the same channel and gi + ⌈ c / k ⌉ flows will be transmitted concurrently (on average) using Algorithm 1, the data rate for load lij and Rij , can be rewritten as follows:
(6) R ij = κ 1 W log 2 [ κ G T G R P T r j,j −α / {( g i +⌈ c/k ⌉) N 0 W+CI⋅ χ C I j }+1 ],
where χ and CI are the indicator function and the degraded power due to CCI, respectively, and CIj is the event that flow j is affected by CCI. It should be noted that CI and P cci take the values 10 dB and 0.4, respectively, in line-of-sight [24] .
MIMCT and MAMCT are determined by applying the two propositions in a different order. In MIMCT, the transmission order is as follows: transmit groups with the minimum transmission time (MIN) first. If there are groups that require the same number of time slots for transmission, select those containing more concurrently transmittable flows (loads) and transmit them prior to those with fewer flows (loads) (MAX). That is, apply proposition 1 first and then apply proposition 2. Conversely, in MAMCT, we apply proposition 2 first and then proposition 1. Because comparing the load amounts requires additional computational tasks, the number of flows rather than the load amounts is used in both MIMCT and MAMCT.
We apply Algorithm 1 for all flows requesting the channel and compute Rij with (6). If the computed Rij is less than R min , the corresponding DEV cannot transmit; thus, the PNC will not assign any CTAs to those DEVs in the following superframe. Let ℑ S be the subset of ℑ that can be transmitted by a data rate greater than R min , and let Φ S be the subset of Φ consisting of loads corresponding to flows in ℑ S . Let N (with N N req ) be the number of flows in ℑ S . In the following algorithm, A (i) and A ((i)) represent the ordered set of A and A (i) , respectively. The loads (that require the maximum transmission time in groups Gi \ GC ) and the transmission times (of mi ) are represented by mi and ti , respectively. details MIMCT—a suboptimal solution of OPD.
        Algorithm 2 MInMax concurrent transmission scheduling algorithms for OPD: MIMCT 1:  Apply Algorithm 1 to N flows and obtain { F i } i=1 k ,  F C ,  { G i } i=1 k , and Gc, kN. 2:  Compute the data rate of each flow: Rij, i=1, … , k, j=1, … , gi+ci, using (6) and replacing ⌈c/k⌉ with ci. 3:  Find { m i } i=1 k in groups { G i \ G C } i=1 k and the corresponding { t i } i=1 k That is t i m i / R ij , for some j. 4:  Order { t i } i=1 k : t(1)≤⋯≤t(k). 5:  Set the length of CTAi: |CTAi|= ⌈t(i)⌉ (min. time first). 6:  Find the maximum n: i=1 n | CTA i |   T CTAP T MCTA n T guard . 7:  if nk, CTAs are assigned to all k groups and | I s g |=k . 8:  else  | I s g |=n , T remain T CTAP T MCTA n T guard i=1 n | CTA i | . 9:  end (line 7 if)       Lines 10–13 determine the order of transmission for groups with the same transmission time. Groups with greater loads are scheduled prior to the groups with lesser loads (max. load first). Let i be the number of groups that are assigned CTA blocks. Initially, set i = 1. 10:  Check whether there are groups that require the same transmission time. Find j: t(i) =⋯= t(i+j). 11:  if  j > 0, reorder G(i)s according to |G(i) \ GC|s, assign CTAi+a to G((i+ja)), 0 ≤ aj. 12:  else  j ←0, assign CTAi to G(i). 13:  end (line 11 if)             CTA blocks are assigned to the first i+j groups up to this line. To assign CTA blocks to the remaining groups, increase i. 14:  if  i + j < | I s g | , ii + j + 1, go to line 10. 15:  end  (line 14 if)          Completely transmittable groups are scheduled up to this line. The purpose of lines 16–25 is to reduce the loads in subsequent superframes, assigning the remaining resources to the loads in the remaining groups { G (n+r) \ G C } r=1 kn . 16:  if n < k, set r = 1, e = 0. 17:      if  Tremain > 0, rr + 1. 18:          if  there exist loads in G(n+r)\GC that can complete their transmissions within Tremain, set |CTAn+r| as the maximal time required for these loads, | I s g | | I s g | + 1, TremainTremain – | CTAn+re |. 19:           else 20:                if  r = kn, |CTA n+1| = Tremain, | I s g | = n + 1, go to line 17. 21:                else  ee + 1, go to line 17. 22:                end (line 20 if) end (line 18 if) 23:      else  (line 17 if) | I s g | = n, go to line 26. 24:      end  (line 17 if) 25:  else  (line 16 if) end (line 16 if) As loads in GC may belong to more than two Gi’s, lines 26–37 schedule the loads. 26:  if  there exists l G C G (n+ r 1 ) for some r1(r1 =1, …, r, r > 0). 27:      if  l can be completely transmitted in CTAi+a, 0 ≤ aj, go to line 38. 28:      else 29:       if  Tremain > 0, perform lines 4–5 with loads in ( G (i) G C ) re, from i=1 to i=n+r. ( G (i) G C ) re is the set of loads in G (i) G C that cannot be transmitted in the previously assigned CTAs. c1 CTAs are newly assigned for loads in ( G (i) G C ) re, with length |CTA k+r+i|, i=1, …, c1. | I s g | | I s g | +c1, TremainTremain i=1 c 1 | CTAk+r+i |. 30:        end  (line 29 if) 31:        Go to line 39. 32:       end  (line 27 if) 33:  else  (line 26 if) 34:        if  Tremain > 0, perform lines 4–5 with loads in Gc \ G(n+r1), r1 =1, …, r. c2 CTAs are newly assigned for loads in Gc \ G(n+r1) with length | CTAk+r+c1+i|, i = 1, …, c2. | I s g | | I s g | +c2, TremainTremain i=1 c 2 | CTAk+r+c1+i |.                 Go to line 38. 35:        else 36:             It cannot be assigned in the following superframe. Go to line 38. 37:        end (line 34 if) end (line 26 if) 38:  Transmit the flows in the assigned CTAs
The purpose of lines 16–20 is to reduce the loads in subsequent superframes, assigning the remaining resources to the loads in the remaining groups
{ G (n+r) \ G C } r=1 k−n
Algorithm 3 details MAMCT, which is a suboptimal solution of OPT.
          Algorithm 3 MAxMin concurrent transmission scheduling algorithms for OPT: MAMCT All lines are the same as those in Algorithm 2, except for the following. 3:  Order { g i } i=1 k : g(1) ≤ ⋯ ≤ g(k).        Denote the group corresponding to g(k+1−i) by G(i)\GC and its elements by l(i)1, ⋯, l(i)g(i). (max. load first) 4:  Find { m (i) } i=1 k in the corresponding set of group { G (i) \ G C } i=1 k . 5:  Set the length of CTAi: CTAi |=⌈ti⌉.        Lines 10–13 determine the order of transmission for groups with the same number of flows. Groups with smaller transmission times are scheduled prior to groups with longer transmission times (min. time first). 10:  Check whether there are groups with the same number of flows. Find j:g(i)= ⋯ = g(i+j) 11:  If  j > 0, reorder { G (i+a) } a=0 j according to { t i+a } a=0 j : t(i)≤⋯≤t(i+j), assign CTAi+a to G((i+a)).
It should be noted that | G ((i)) \ GC | = | G ((i+1)) \ GC | and t (i) = t (i+1) are possible in line 11 of Algorithms 2 and 3. In either case, additional scheduling factors, such as the variance of transmission completion times of the loads in each group, can be considered to use the channel more efficiently. However, we do not consider this here.
In addition to MIMCT and MAMCT, we consider an algorithm in which the first concurrently transmittable group to be constituted transmits first. That is, in Algorithm 2, lines 10–13 are not considered, but the remaining procedure is carried out. As the first flow is selected randomly when Algorithm 1 is applied, the order of groups generated by Algorithm 1 can be considered random. From this viewpoint, the algorithm is called random concurrent transmission using remaining CTAs (RANCTRC). However, when Algorithm 1 is applied to ℑ S , the groups constituted first usually contain more flows—that is, F 1 may contain more flows than F 2 , and so on. Therefore, RANCTRC will transmit groups with more flows prior to others with high probability.
For the newly generated flows, we apply the following algorithm: Check whether it satisfies the ER criterion with each flow in Fj . If it belongs to only one of the Fj ’s, insert it into the group to which it belongs. If it belongs to more than two Fj ’s, insert it into FC . If it does not belong to any one of the Fj ’s, assign a CTA block in the following superframe as long as T remain > 0.
Figure 2 illustrates Algorithms 2 and 3 with the flows from example 1. For simplicity, we assume that all DEVs have the same data transmission rate of 1; that is, Rij = 1, for all i and j . For MIMCT, the mi of the four groups are 6, 10, 1, and 8 such that t (1) = 1, t (2) = 6, t (3) = 8, and t (4) = 10. G (i) or G ((i)) are given by G (1) = G 3 = {1, 3, 4}, G (2) = G 1 = {3, 4, 6, 7, 9}, G (3) = G 4 = {7, 8, 9}, and G (4) = G 2 = {2, 2, 4, 10}. We consider two cases: the length of the CTA period is sufficient (Case 1), and the length of the CTA is insufficient (Case 2) for assignment to all groups. In case 1, n = 4 and all loads are scheduled for transmission and can be transmitted completely. Therefore, CTA i = t (i) , where i = 1, 2, 3, 4. In case 2, n = 3 and CTA i = t (i) , where i = 1, 2, 3. We set CTA 4 = T remain because 0 < T remain < t (4) . As the time requirements of f 2 and f 3 are less than T remain , f 2 and f 3 can be transmitted in CTA 4 , while f 7 is partially transmitted in this superframe. In this example, there is no group with the same transmission time. Therefore, it is unnecessary to reorder { G (i) \ G C : i = 1, … , 4}.
PPT Slide
Lager Image
Illustration of Algorithms 2 and 3: (a) MIMCT and (b) MAMCT.
The complexity of the proposed algorithm is as follows: in line 1, the complexity of the grouping algorithm with N flows is O( N 2 log N ). In line 3, the required number of comparisons of l i1 / R i1 , … , ligi / Rigi is gi ( gi −1 )/2. Therefore, the complexity of finding
{ m i } i=1 k
is O( N log N ). In addition, additional O( k log k ) and O( k n ) computations are required to find
{ m (i) } i=1 k
and |CTA k+i |, i = 1, …, r + c 1 + c 2 . Hence, the complexity of the proposed algorithm, including the grouping algorithm, is O( N 2 log N ).
V. Performance Measures
For simplicity of notation, if the second ordering is unnecessary, we set G ((j)) G (j) . In any algorithm, the CTA block is then assigned in the following order: G ((1)) , G ((2)) ,…, G ((|n|)) , G n+1 = G ((n+1)) ,…,
G | I s g | = G ((| I s g |)) .
. Let t ((i)) , g ((i)) , l ((i)),j , and m ((i)) be the corresponding transmission time, the number of loads, the actual loads, and the load requiring the longest transmission time of G ((i)) \ G C , respectively, for 1 ≤ j g ((i)) , 1 ≤ i
| I s g |
The average transmission delay E ( D ) and throughput Th CTAP represented in OPD and OPT can be used to calculate those measures of the proposed algorithms. As the total transmission time of flows in ℑ S and the waiting times of flows that are not scheduled and flows in ℑ \ ℑ S are involved in the calculation of E ( D ), it can be written explicitly as
(7) E(D)= 1 N+|ℑ\ ℑ S | [ ∑ i=0 | I s g |−1 ( | I s g |−i )⋅| CTA i+1 | +{ T SF −( T beacon +2 T guard + T CAP + T MCTA ) }    ⋅{ ∑ i=1 | I ns g | { g ((i)) + c ((i)) } +|ℑ\ ℑ S | } ].
In addition, a service rate (defined as the total successfully transmitted load divided by the time used for it) is given as follows:
(8) S= ∑ i∈ I s l ,transmitted l i / ∑ i=1 | I s g | | CTA i |
There are three types of losses: (a) Loads that are scheduled but not transmitted until its delay threshold ( L s ), and loads that are not scheduled in the next superframe ( L ns ). (b) Loss during the periods of blockage ( L block ). (c) Loss from low data rates owing to CCI ( L CCI ). For case (a), the amount of loads lost will probabilistically be the same for each superframe, given by
L s ={ l loss,i : l loss,i =   | D th,i −( l i / R i + Q i )|⋅ R i ,   l i ∈ ∪ i=1 | I s g | G (i) , | D th,i −( l i / R i + Q i )|  >0},
(9) L ns ={ l i : l i ∈ ∪ i=| I s g |+1 k G (i) }.
The delay threshold and the waiting time before frame transmission in flow i are represented by D th,i and Qi , respectively. For case (b), the penalized link budget of a blockage is known to be 20 dB to 30 dB [7] . As the blockage significantly degrades the channel condition, the load amount transmitted during the blockage will be considered as lost. Such loss is given by
(10) L block = ∑ l i ∈ ∪ i=1 | I s g | G ((i)) P block E( T dur ) R i ,
where P block and E ( T dur ) are the probability of a blockage occurring during transmission and the average duration of a blockage, respectively. The data rate corresponding to li in
∪ i=1 | I s g | G ((i))
obtained by (6) is represented by Ri . For case (c), the data rate of a DEV influenced by CCI becomes low. As the load of a DEV with the data rate less than R min will be considered lost, it gives
(11) L CCI = ∑ l i ∈Φ\ Φ S l i .
The loss probability, P loss , is thus given by
(12) P loss = | L s |+| L ns |+| L block |+| L CCI | ∑ i=1 k ∑ j=1 g i l ij + ∑ i=1 | F C | l i + ∑ l i ∈Φ\ Φ S l i .
Finally, the channel-occupancy rate ρ (defined as the sum of the length of CTAs used for the scheduled flows divided by the total usable time for scheduling in a CTAP), is given by
(13) ρ= ∑ i=1 | I s g | | CTA i | T SF −( T beacon +2 T guard + T CAP + T MCTA ) .
VI. Numerical Results
In this section, we present the results of our numerical simulations. We used Matlab 7.7 for the simulator, and the procedure involved 1,000 consecutive superframes. The path loss model of IEEE 802.15.3c is used [8] , [25] . The set of parameters based on the IEEE 802.15.3c standard are as follows: T SF = 65,535, T CAP = 6,553, T MCTA = 10, T beacon = 50, T SIFS = 2.5, t slot = 6.5, T guard = 1.6×10 −1 (unit: μs), W = 1,728 MHz, and P T = 10 mW. We used a value of −91.9 dB for N 0 , which was computed by KT +10log 10 Rb + NF , where KT , Rb , and NF are the Gaussian thermal noise, the physical layer service access point (PHY-SAP) payload bit rate, and the noise figure, respectively. We set R min , R max , and κ 1 to 25.8 Mbps, 5.28 Gbps, and unity, respectively. All assumptions and other parameters described in sections II–IV are used. There are N req flows randomly distributed in an L × L square room with L = 10 m. mMaxSubframeNum is 8 and mMaxSubframeSize is 10,478,575 bytes, according to the IEEE 802.15.3c standard for the standard aggregation mode. Therefore, the maximal supportable load is 83,828,600 bytes.
PPT Slide
Lager Image
Used data from sample video (From Mars to China).
We use a real video source “From Mars to China” (Mars) in HDTV format (1,920 × 1,080i) obtained in [26] for the numerical results. As the inter-frame interval is fixed to 1/30 s for this sample stream, the variation of video frame sizes within a GoP and between GoPs leads to the high burstiness of video traffic. Figure 3 shows the collected sample video stream as time passes, and this is used in the simulation.
Three other transmission schemes—namely, random concurrent transmission (RANCT), non-concurrent transmissions NCTR, and NCT—are considered to compare the performance. RANCT is a scheme in which the first concurrently transmittable group to be constituted transmits first, but lines 16–37 in Algorithm 2 are not executed. Because the scheduling scheme proposed in [11] does not consider the transmission order of groups, they can be considered as RANCT. The other transmission schemes, NCTR and NCT, do not use a directional antenna. Therefore, flows are not grouped and only one flow is transmitted in one CTA block. When T remain is insufficient to transmit a frame of a flow completely, NCTR assigns, while NCT does not assign, the channel to the flow. In the following figures, MA, MI, RARC, and RA are used to denote MAMCT, MIMCT, RANCTRC, and RANCT, respectively, to simplify the figures.
According to the characteristics of the algorithms, we derive the following conclusions: MIMCT transmits more concurrently transmittable groups with fewer flows, MAMCT transmits fewer groups with more flows, and RANCTRC has a high probability of transmitting groups with more flows prior to groups with fewer flows. If T remain is not used, the difference in characteristics will appear as a difference in performance. However, as T remain is fully utilized in the algorithms and MIMCT and MAMCT can be considered to be special cases of RANCTRC, we may conjecture that differences in performance between the three algorithms are not large enough to differentiate their characteristics and that the performance of RANCTRC lies in between MIMCT and MAMCT. Numerical results show that our conjecture holds for many cases. The effect of using T remain can be seen in the difference between RANCTRC (NCTR) and RANCT (NCT). In the simulation, we used ƞ = 0.9, two beamwidths of 10° and 30°, and two pairs of probabilities for CCI and blockage: (a) P cci = 0, P block = 0; (b) P cci = 0.4, P block = 0.2; and E ( T dur ) is set to 3 ms. Numerical results show that case (a) performs better than case (b), as expected. In addition, θ = 10° performs better than θ = 30°, owing to spatial reuse. It should be noted that figures with case (b) exhibit more fluctuations than those with case (a). In Figs. 4 6 , sub-figure (a) shows the case P cci = 0, P block = 0 and sub-figure (b) shows the case P cci = 0.4, P block = 0.2.
Figure 4 compares the throughput and service rate of the algorithms. It shows that higher throughput is achieved with a smaller θ and lower blockage probability and CCI for any concurrent transmission algorithm. The throughput increases with N req until ρ reaches the value of one. Moreover, as the variance of the load amounts decreases with an increase in N req , more loads can be transmitted in each CTA block. This will cause an increment in throughput, even in the case when the channel is fully utilized. The service rates of the three algorithms are almost the same with that of the NCT being the lowest. Figure 5 compares the average frame delay and average jitter of the algorithms. Jitter is defined as the variance in one-way latency and is calculated on the basis of the sending and receiving times of consecutive frames. The average delays for the algorithms increase with N req . This shows that the average delay for MIMCT is the smallest among all algorithms, under all conditions. Even though the average jitter for MIMCT is greater than those for MAMCT and RANCTRC, the difference is negligible. Jitter becomes constant with an increase in N req . The average jitter is the largest for NCT, as expected. Figure 6 compares the loss probability of loads. As the QoS is not considered in this paper, we assumed the delay threshold to be T CTAP , given in (2), for all frames. In all algorithms, if ρ < 1, a loss will only occur owing to a blockage or CCI, or both. Therefore, the loss probabilities of the three algorithms are almost the same, as shown in Fig. 6 (a) . If ρ approaches the value of one, frames may not be completely transmitted or may not even be unscheduled. Hence, the amount of load lost may depend on the algorithms, and the gaps in the loss probabilities between algorithms may increase. As shown in Fig. 6 , more flows will be lost in MAMCT, because the group with more flows is transmitted prior to the group with fewer flows and a group with more flows may need a longer transmission time. Since the lengths of transmitted frames for NCT have a higher probability of being longer when N req is large, few frames will be completely transmitted for such N req . Therefore, the loss probability for NCT approaches the value of one as N req increases.
PPT Slide
Lager Image
Comparison of throughput and service rate.
PPT Slide
Lager Image
Comparison of average transmission delay per frame and jitter.
PPT Slide
Lager Image
Comparison of loss probability.
VII. Conclusion
In this paper, we considered a resource allocation scheme for mmWave–based WPANs using directional antennas. Two objective functions were considered, and an algorithm for each objective function was proposed. In the two proposed algorithms, the transmission order is determined by the reservation time and number of concurrently transmittable flows to use resources efficiently. The numerical results show that each algorithm is adequate for its objective and that the generalized algorithm provides almost the same performance requiring fewer computational tasks.
In future work, we will consider a QoS metric and priorities for various applications under the resource allocation scheme. The algorithms will be generalized to suit more realistic situations including movements of devices, temporal changes of channels, and reflections from objects. Furthermore, the restrictions imposed here, such as equal antenna beamwidths and power, and line-of-sight path, will be removed.
This work was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea Government (MEST, MSIP) (NRF-2010-0022282, 2013R1A2A2 A01067452).
The authors would like to thank the associate editor and the anonymous reviewers for their constructive and valuable comments.
Meejoung Kim received her BS in mathematics from Korea University, Seoul, Rep. of Korea, in 1986; an MS in mathematics from both Korea University and the University of Minnesota, Twin Cities, Minneapolis, MN, in 1988 and 1993, respectively; and her PhD in mathematics from Korea University in 1996. From 1993 to 1999, she worked as a lecturer and research fellow in the Department of Mathematics at Korea University. From 2000 to 2004, she worked as a research fellow and an assistant professor with Brain Korea 21 Information Technology. Since 2004, she has been a professor in the Research Institute for Information and Communication Technology, Korea University. She teaches probability theory and complex analysis. Her research interests include mm-wave WPANs, wireless communication systems, wireless security, and white noise analysis.
Yongsun Kim received his BS, MS, and PhD both in electrical and computer engineering from Korea University, Seoul, Rep. of Korea, in 1997, 1999, and 2011, respectively. In 1999, he joined ETRI, Daejeon, Rep. of Korea, where he has worked on development and standardization for wireless LAN and wireless PAN as a senior member of the engineering staff. His research interests include nextgeneration mobile radio communication systems, ubiquitous sensor networks, and the Internet of Things convergence—with an overall emphasis on medium access control layer design and performance analysis.
Wooyong Lee received his BS in electronics engineering from Korea University, Seoul, Rep. of Korea, in 1989 and his MS and PhD in electrical and electronics engineering from Korea Advanced Institute of Science and Technology, Daejeon, Rep. of Korea, in 1991 and 1997, respectively. Upon completion of his graduate studies, he joined ETRI, Daejeon, Rep. of Korea, where he worked on research and development of high-speed wireless local and personal area networks systems. Currently, he is a team head of the super-speed wireless communication research team in the Mobile Telecommunication Research Division at ETRI. His research and development activities are focused on transmission technologies for the next-generation wireless personal-area network and multigigabit wireless communication systems.
2009 IEEE 802 Part 15.3: Wireless Medium Access Control (MAC) and Physical Layer (PHY) Specifications for High Rate WirelessPersonal Area Networks (WPANs). Amendment 2: Millimeterwavebased Alternative Physical Layer Extension
2013 IEEE P802.11ad, Part 11: Wireless LAN Medium Access Control5 (MAC) and Physical Layer (PHY) Specifications. Amendment3: Enhancements for Very High Throughput in the 60 GHz Band
2010 Standard ECMA-387 2nd Edition: High Rate 60GHz PHY, MAC and HDMI PAL
M. Park , P. Gopalakrishana 2009 “Analysis of Spatial Reuse and Interference in 60-GHz Wireless Networks,” IEEE J. Sel. Areas Commun. 27 (8) 1443 - 1452    DOI : 10.1109/JSAC.2009.091014
Yiu C. , Singh S. 2009 “Empirical Capacity of mmWave WLAN,” IEEE J. Sel. Areas Commun. 27 (8) 1479 - 1487    DOI : 10.1109/JSAC.2009.091017
Maltsev A. 2009 “Experimental Investigations of 60 GHz WLANSystems in Office Environment,” IEEE J. Sel. Areas Commun. 27 (8) 1488 - 1499    DOI : 10.1109/JSAC.2009.091018
Singh S. 2009 “Blockage and Directivity in 60 GHz Wireless Personal Area Networks: From Cross-Layer Model to Multihop MAC Design,” IEEE J. Sel. Areas Commun. 27 (8) 1400 - 1413    DOI : 10.1109/JSAC.2009.091010
Kim M. , Kim Y.S. , Lee W. 2012 “Performance Analysis of Directional CSMA/CA for IEEE 802.15.3c under Saturation Environments,” ETRI J. 34 (1) 24 - 34    DOI : 10.4218/etrij.12.0111.0136
Lan Z. 2009 “Relay with Deflection Routing for Effective Throughput Improvement in Gbps Millimeter-Wave WPAN Systems,” IEEE J. Sel. Areas Commun. 27 (8) 1453 - 1465    DOI : 10.1109/JSAC.2009.091015
Kim M. , Hong S.-E. , Kim J. 2012 “Analysis of Directional Communication via Relaying Devices in mmWave WPANs,” IEEE Commun. Lett. 16 (3) 342 - 345    DOI : 10.1109/LCOMM.2011.122211.112196
Park H. 2012 “An Adaptive Allocation Algorithm Using Directional CSMA/CA over mmWave Wireless Personal Area Networks,” Int. J. Advanced Robot. Syst. 1 - 10    DOI : 10.5772/50914
Ajorloo H. , Manzuri-Shalmani M.T. 2013 “Modeling Beacon Period Length of the UWB and 60-GHz mmWave WPANs Based on ECMA-368 and ECMA-387 Standards,” IEEE Trans. Mobile Comput. 12 (6) 1201 - 2013    DOI : 10.1109/TMC.2012.91
An X. , Hekmat R. “A QoS-Aware Fair Resource Allocation Scheme for WPANs,” CCNC, Las Vegas, NV, USA Jan. 10–13,2009 903 - 907
Cai L.X. 2009 “Resource Management and QoS Provisioning for IPTV over mmWave-Based WPANs with Directional Antenna,” Mobile Netw. Appl. 14 (2) 210 - 219    DOI : 10.1007/s11036-008-0134-5
Cai L.X. 2010 “REX: A Randomized Exclusive Region Based Scheduling Scheme for mmWave WPANs with Directional Antenna,” IEEE Trans. Wireless Commun. 9 (1) 113 - 121    DOI : 10.1109/TWC.2010.01.070503
Liu K.-H. , Cai L. , Shen X. 2008 “Exclusive-Region-Based Scheduling Algorithms for UWB WPAN,” IEEE Trans.Wireless Commun. 7 (3) 933 - 942    DOI : 10.1109/TWC.2008.060707
Son I.K. “On Frame-Based Scheduling for Directional mmWave WPANs,” INFOCOM Orlando, FL, USA Mar. 25–30, 2012 2149 - 2157
Lan Z. “Directional Relay with Spatial Time Slot Scheduling for mmWave WPAN Systems VTC Taipei, Taiwan May 16–19, 2010 1 - 5
Li H. “Multi-dimensional Conflict Graph Based Computingfor Optimal Capacity in MR-MC Wireless Networks,” ICDCS,Genova, Italy Genova, Italy June 21–25, 2010 774 - 783
Xu Y. “Hybrid MAC Based Resource Management Scheme for Kiosk Service in 802.15.3c WPAN,” IWCMCC Istanbul, Turkey July 4–8, 2011 516 - 521
Kim M. , Kim Y.S. , Lee W. 2013 “Analysis of Directional Neighbour Discovery Process in Millimeter Wave Wireless Personal Area Networks,” IET Netw. 2 (2) 92 - 101    DOI : 10.1049/iet-net.2012.0095
Seeling P. , Reisslein M. 2005 “Evaluating Multimedia Networking Mechanisms Using Video Traces,” IEEE Potentials 24 (4) 21 - 25    DOI : 10.1109/MP.2005.1549754
Wan F. , Cai L. , Gulliver T.A. “A Simple, Two-Level Markovian Traffic Model for IPTV Video Sources,” GLOBECOM New Orleans, LO, USA NNov. 30 - Dec. 4, 2008 1 - 5
Sum C.S. “A Synchronization-Frame-Aided Interference Mitigation Mechanism for Millimeter-Wave WPAN,” PIMRC Tokyo, Japan Sept. 13-16, 2009 380 - 384
Yong S.-K. 2007 IEEE 802.15.3c Channel Modeling Subcommittee Report, IEEE P802.15 Wireless Personal Area Netw.