Resource Allocation Scheme for Millimeter Wave–Based WPANs Using Directional Antennas

ETRI Journal.
2014.
Apr,
36(3):
385-395

- Received : July 15, 2013
- Accepted : November 27, 2013
- Published : April 01, 2014

Download

PDF

e-PUB

PubReader

PPT

Export by style

Share

Article

Metrics

Cited by

TagCloud

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.
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)
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.
Four different ER radii for directional antenna pairs.
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
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.

Let ℑ = {
f_{i}
:
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
F_{i}
and
F_{C}
be the subsets of ℑ consisting of all concurrently transmittable flows and the flows contained in more than two
F_{i}
’s, respectively, and let
G_{i}
and
G_{C}
be the subsets of Φ consisting of the loads corresponding to the flows in
F_{i}
and
F_{C}
, respectively. A description of this notation is summarized in
Table 1
.
To generate
F_{i}
and
F_{C}
, a grouping algorithm is proposed. The grouping algorithm is based on the ER criterion, and it allows us to obtain from ℑ(Φ), both
F_{i}
(
G_{i}
) and
F_{C}
(
G_{C}
). The procedure used to obtain the
F_{i}
’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
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
k
≤
N
_{req}
, are generated by Algorithm 1. Let
l_{ij}
and
j
in
G_{i}
\
G_{C}
and
G_{i}
\
G_{C}
is
g_{i}
,
c_{i}
and
c
be the number of loads in
G_{i}
\
G_{C}
,
G_{C}
, respectively. Then,
G_{i}
\
G_{C}
= {
l
_{i1}
,…,
l_{igi}
},
c_{i}
= 0 },
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
F_{C}
= {
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.
Let
A
| is the number of elements in
A
. In this paper, we assume that the data rate
R_{i}
of the DEV with flow
i
must satisfy the relation
R
_{min}
≤
R_{i}
≤
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:
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
Proposition 1.
Suppose there are
N
frames with loads {
l
_{1}
, …,
l_{N}
} 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 {
G_{i}
}
_{i=1}
^{k}
be a set of groups, where each group
G_{i}
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 |
G_{i}
|.
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
g_{i}
+ ⌈
c
/
k
⌉ flows will be transmitted concurrently (on average) using Algorithm 1, the data rate for load
l_{ij}
and
R_{ij}
, can be rewritten as follows:
χ
and
CI
are the indicator function and the degraded power due to CCI, respectively, and
CI_{j}
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
R_{ij}
with (6). If the computed
R_{ij}
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
G_{i}
\
G_{C}
) and the transmission times (of
m_{i}
) are represented by
m_{i}
and
t_{i}
, respectively. details MIMCT—a suboptimal solution of OPD.
Algorithm 2 MInMax concurrent transmission scheduling algorithms for OPD: MIMCT
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
Algorithm 3 MAxMin concurrent transmission scheduling algorithms for OPT: MAMCT
It should be noted that |
G
_{((i))}
\
G_{C}
| = |
G
_{((i+1))}
\
G_{C}
| 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
F_{j}
. If it belongs to only one of the
F_{j}
’s, insert it into the group to which it belongs. If it belongs to more than two
F_{j}
’s, insert it into
F_{C}
. If it does not belong to any one of the
F_{j}
’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,
R_{ij}
= 1, for all
i
and
j
. For MIMCT, the
m_{i}
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}.
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}
, … ,
l_{igi}
/
R_{igi}
is
g_{i}
(
g_{i}
−1 )/2. Therefore, the complexity of finding
N
log
N
). In addition, additional O(
k
log
k
) and O(
k
−
n
) computations are required to find
_{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
).
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))}
,…,
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
≤
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
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
i
are represented by
D
_{th,i}
and
Q_{i}
, 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
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
l_{i}
in
R_{i}
. 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
P
_{loss}
, is thus given by
ρ
(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
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}
R_{b}
+
N_{F}
, where
KT
,
R_{b}
, and
N_{F}
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.
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.
Comparison of throughput and service rate.
Comparison of average transmission delay per frame and jitter.
Comparison of loss probability.
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).
meejkim@korea.ac.kr
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.
doori@etri.re.kr
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.
wylee@etri.re.kr
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.

Resource management
;
millimeter wave
;
directional antenna
;
exclusive region
;
objective functions

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
(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
PPT Slide

Lager Image

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
(2) T CTAP = T MCTA + ∑ i=1 n ( T CTA i + T guard ) ,

where
Description of notation.

Notation | Description |
---|---|

ℑ(ℑ_{s}) | Set of flows requesting channel (supported by min _{min}) |

Φ(Φ_{s}) | Load set of flows in ℑ(ℑ_{s}) |

_{i}_{i} | Set of concurrently transmittable flows (loads) |

_{C}_{C} | Set of flows (loads) contained in more than two _{i}_{i} |

_{(i)}(_{((i))}) | Ordered set of _{(i)}(_{(i)}) (_{i}_{i}_{i}_{C} |

Elements of _{(i)}(_{((i))}) (_{i}_{i}_{i}_{C} |

{ F i } i=1 k

and
{ G i } i=1 k

, for
l ij C

be the loads of flow
G i ∩ G C

, respectively. Here,
G i ∩ G C com

, where “com” denotes the complement.
Let ,
G i ∩ G C

, and
G C ={ l i c 1 C , ... , l i c i C :i=1, ... ,k, ∑ i=1 k c i =c

with some
G i ={ l i1 , ... , l i g i , l i1 C , ... , l i c i C },

and
∑ 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.
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 |
(3) OPD: min E( D ) = min ( WT+ST )

and
(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
∑ 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.
(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
{ G (n+r) \ G C } r=1 k−n

.
Algorithm 3 details MAMCT, which is a suboptimal solution of OPT.
PPT Slide

Lager Image

{ m i } i=1 k

is O(
{ m (i) } i=1 k

and |CTA
V. Performance Measures

For simplicity of notation, if the second ordering is unnecessary, we set
G | I s g | = G ((| I s g |)) .

. Let
| I s g |

.
The average transmission delay
(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 ={ 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},

and
(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
(10) L block = ∑ l i ∈ ∪ i=1 | I s g | G ((i)) P block E( T dur ) R i ,

where
∪ i=1 | I s g | G ((i))

obtained by (6) is represented by
(11) L CCI = ∑ l i ∈Φ\ Φ S l i .

The loss probability,
(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
(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:
PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

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.
Acknowledgements

The authors would like to thank the associate editor and the anonymous reviewers for their constructive and valuable comments.

BIO

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.

,

Citing 'Resource Allocation Scheme for Millimeter Wave–Based WPANs Using Directional Antennas
'

@article{ HJTODO_2014_v36n3_385}
,title={Resource Allocation Scheme for Millimeter Wave–Based WPANs Using Directional Antennas}
,volume={3}
, url={http://dx.doi.org/10.4218/etrij.14.0113.0691}, DOI={10.4218/etrij.14.0113.0691}
, number= {3}
, journal={ETRI Journal}
, publisher={Electronics and Telecommunications Research Institute}
, author={Kim, Meejoung
and
Kim, Yongsun
and
Lee, Wooyong}
, year={2014}
, month={Apr}