Advanced
Time-Slotted Scheduling Schemes for Multi-hop Concurrent Transmission in WPANs with Directional Antenna
Time-Slotted Scheduling Schemes for Multi-hop Concurrent Transmission in WPANs with Directional Antenna
ETRI Journal. 2014. Apr, 36(3): 374-384
Copyright © 2014, Electronics and Telecommunications Research Institute(ETRI)
  • Received : July 15, 2013
  • Accepted : November 05, 2013
  • Published : April 01, 2014
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Muhammad Bilal
Moonsoo Kang
Sayed Chhattan Shah
Shin-Gak Kang

Abstract
To achieve high-speed (giga-bit) connectivity for short-range wireless multimedia applications, the millimeter-wave (mmWave) wireless personal area networks with directional antennas are gaining increased interest. Due to the use of directional antennas and mmWave communications, the probability of non-interfering transmissions increases in a localized region. Network throughput can be increased immensely by the concurrent time allocation of non-interfering transmissions. The problem of finding optimum time allocation for concurrent transmissions is an NP-hard problem. In this paper, we propose two enhanced versions of previously proposed multi-hop concurrent transmission (MHCT) schemes. To increase network capacity, the proposed schemes efficiently make use of the free holes in the time-allocation map of the MHCT scheme; thus, making it more compact.
Keywords
I. Introduction
To achieve high-speed connectivity for short-range wireless multimedia applications, such as high-definition (HD) TVs, kiosk file servers, and HD audio, millimeter-wave (mmWave) wireless personal area networks with directional antennas are gaining increased interest. A number of standardization groups, such as IEEE 802.15.3 [1] and IEEE 802.11 VHT [2] , have developed specifications for mmWave communication systems in which mmWave communication with directional antennas at the unlicensed 60 GHz band was adopted. Since this spectrum can achieve multi-gigabit link speeds (conceivably 3.5 Gbps) [3] , it can fulfill the multi-Gbps requirements of emerging short-range wireless multimedia applications. Due to the important characteristics of high propagation loss over distance in mmWave communications, spatial usability becomes very high [4] , [5] . Since the overlapped transmission area of directional antennas is smaller than that of omni-directional antennas, further spatial reusability can be achieved using directional antennas. In addition, the performance at 60 GHz is highly dependent upon obstructions between the source and destination nodes. Therefore, maintaining a line of sight (LOS) is another key factor in achieving a higher data rate [6] [8] .
The network throughput enhancement schemes for mmWave WPANs have been discussed in literature [9] [12] . In [9] , authors have developed an exclusive region (ER)-based resource management scheme and analytically derived the optimal ER sizes to explore the spatial multiplexing gain of mmWave WPANs with directional antenna. Based on numerical analysis, in [10] , authors found that there is an optimum beamwidth that maximizes the performance of concurrent transmission. In [11] , the authors suggested a joint use of low-rate omni-directional and high-rate mmWave-beamformed directional antennas. In case of connection loss in high-rate directional communications mode, the omni-directional communication mode works as a backup. Thus, J. Qio and others [12] proposed a multi-hop concurrent transmission (MHCT) scheduling algorithm. MHCT identifies and groups all non-interfering hop transmissions into concurrent groups so that candidates of each group can transmit concurrently.
In this paper, we analyzed MHCT and found that its time-allocation map of non-interfering concurrent transmissions is not fully compact and that free holes exist within the time-allocation map. Further improvement in channel reusability and network throughput is possible by utilizing these holes. Hence, we extended the MHCT [12] and proposed two new schemes: a) enhanced multi-hop concurrent transmission with expandable group size (EMHCT-E) and b) enhanced multi-hop concurrent transmission with fixed group size (EMHCT-F). The proposed schemes give a more compact time-allocation map by span overlapping of concurrent groups. The span overlapping procedure discovers intra- and inter-group collisions among hop-transmission requests by means of using more flexible conditions for hop transmissions to coexist in the same concurrent group. Due to the high path-loss factor in mmWave, it is suitable to transform long-distance transmission into short-distance multi-hop transmission by selecting suitable relay nodes. The multi-hop conversion also helps to maintain the LOS link. We introduce more efficient conditions for selecting relay nodes. The priority scheme of transmission selection has a great impact upon fairness. To prevent the starvation condition and to improve fairness, a new priority scheme is adapted for the proposed scheduling algorithms. In addition, we introduce a concurrency gain to find the theoretical bound of the network throughput using a water-filling algorithm. Finally, we make a fairness comparison of the proposed schemes using the Jain’s fairness index.
The remainder of this paper is organized as follows. In section II, we formally discuss a network system model. In section III, we describe our analysis of the MHCT and present the proposed algorithms (EMHCT-E/F). In section IV, the simulation parameters and performance metrics are defined, and extensive simulation results are presented to compare the proposed algorithm with the MHCT and the water-filling theoretical bound. Finally, we provide concluding remarks in section V.
II. System Model
We consider an indoor single-hop WPAN with 50 wireless terminal nodes and a piconet controller (PNC). Each wireless terminal node is equipped with multiple steerable directional antennas. As the network size in WPAN is small and has low levels of mobility, we assume that during a random access period a PNC can receive the location information of each node.
- 1. Notations
The following notations are used throughout the rest of this paper.
  • Ri=ith transmission request.
  • n(i) = time-slot requirement byith transmission request.
  • hkRi=kh hop ofith transmission request.
  • n(I,K) = time-slot requirement bykth hop ofith transmission request.
  • d(i,j) = distance betweenith andjth nodes.
  • w(i,j) = link weight betweenith andjth nodes.
  • F(j) = workload ofjth node.
  • Gi=ith group of concurrent hop transmissions.
  • n(Gi) = time-slot requirement byith groupGi.
  • MAXSLOTS= number of time slots in a superframe.
  • Nslots= available slots in a superframe.
  • PNC = piconet controller.
- 2. Antenna Model
We considered an ideal flat-top antenna model for directional antenna [13]
(1) G(∅)={ sin( Nπsin∅ 2 π) Nsin( πsin∅ 2 π) ,     |∅|  ≤   Δ∅ 2 ; ≪1,                      otherwise,
where Δ∅ = 2π / N is the antenna beamwidth when every node is equipped with an antenna with N beams. Thus, if a receiver is directed within the antenna beamwidth of the transmitter —that is,
|∅|  ≤   Δ∅ 2
— the antenna gain of the transmitters and receivers is
G t =  G r = sin( Nπsin∅ 2 ) Nsin( πsin∅ 2 )
dBi [13] , while Gt = Gr ≪ 1, if the node resides outside of the transmitter beamwidth. In addition, in a LOS-room case, the received power is mainly a directed wave [14] . Hence, the transmission interference outside the antenna beam is small enough to allow concurrent transmissions.
- 3. Data Rate and Time-Slot Calculation
An indoor environment is less dynamic compared to an outdoor environment, and also throughput in IEEE 802.15.3 mainly depends on the scheduling scheme rather than transmission power control [15] . We can assume that all nodes can transmit with constant maximum power ( Pt ). The achievable data rate, according to Shannon’s theory, is given by
(2) R=W log 2 [ 1+ p r ( N o + ∑ p r i )W r n ],
where W is the system bandwidth; N o and
I=Σ P r i
are the one-side power spectral density with white Gaussian noise and interference, respectively; Pr is the received signal power;
P r i
is the received signal power from an interfering transmission. In (3) below, Gr and Gt are the antenna gain of a receiver and transmitter, respectively; λ is the wavelength; r is the transmission distance between the transmitter and receiver; and n is the path-loss exponent whose value is usually between 2 and 6 for an indoor environment [16] . According to the Friis free space equation
(3) P r = P t λ 2 G t G r (4π) 2 r n .
From (1) and (2) we get
(4) R=W log 2 [ 1+ P t G t G r λ 2 16 π 2 ( N o + ∑ ​ P t ' G t ' G r λ 2 /16 π 2 r n )W r n ],
where
P t '
and
G t '
are the transmission power and antenna gain of other transmitting nodes, respectively.
According to the antenna model (described in section II, sub section 2),
G t ' ≪1
for non-interfering transmissions. Therefore, the interfering term
(Σ P t ' G t ' G r λ 2 /16 π 2 r n )
in (4) is insignificant for concurrent scheduling of non-interfering transmissions.
The time-slot requirement n ( I , J ) for a transmission request from
h k−1 R m
to
h k R m
with a P Mb/s data payload is given below
(5) n(I,J)= P R t ts ,
where tts is the duration of a single time slot.
- 4. Directional MAC Structure
The IEEE 802.15.3 superframe structure in Fig. 1 is used for directional MAC. Directional MAC applies the same logic as MAC, except it gives access control on a per-antenna basis.
A superframe is composed of a beacon period, random access period, and transmission period. During a beacon period, the PNC broadcasts the synchronization and scheduling information. The scheduling information includes: the start time and duration of the transmission period and the direction of the steering beam. During a random access period, nodes willing to transmit data send transmission requests to the PNC. The transmission request includes the topology information used to determine the transmitter’s antenna direction and the node’s work load. During the transmission period, only scheduled nodes are allowed to send their data for the duration of the allocated time slots; that is, channel time allocations.
PPT Slide
Lager Image
IEEE 802.15.3 MAC.
III. Time-Slot Allocation for Concurrent Transmission
The time-slot allocation and scheduling of a concurrent transmission is equivalent to an optimization of the packing problem, where each transmission request can be considered an item having a variable width with interfering and conflicting dimensions. Let [ Ri , n ( i )] denote each transmission request arriving at a PNC during the random access period. Then, transmission request Ri can be transformed into multi-hop transmissions using the following hop selection metric used in [12] :
(6) w(i,j)= d 2 (i,j) D 2 ¯ +  F(j) F ¯ .
Let {[
h k R i
, n ( I , k )], k = 1, 2, …, m and i = 1, 2, …, N } denote an ordered sequence representing a multi-hop transmission for Ri , and let m be a number between 1 and n ( n −1)/2, where n is the number of nodes. For a
h j R i
hop transmission, n ( I , J ) represents the required number of time slots from the i th to j th node transmission. The optimization problem of a time-slot allocation within a superframe for a concurrent transmission can then be formulated as follows:
(7) P1: max ∑ i=1 n f R i  , 
(8) s.t   ∑ i=1 n f ∑ k=1 n h i n (i,k) To solve this problem, the optimum result leads to NP-hard [17] . Therefore, instead of solving the problem for the optimum result, a practical sub-optimum result is possible using a Heuristic approach.
- 1. Time-Slot Allocation Process in MHCT
In an MHCT scheme, once direct transmissions are converted into multi-hop transmissions, a PNC sorts the hop-transmission requests in decreasing order according to the number of time-slot requirements n ( I , J ). After sorting the hop-transmission requests, the PNC checks for the concurrent hop transmissions in hop sequence order and forms group Gi , consisting of all non-interfering hop transmissions. If the next hop of Ri is to be scheduled in the next superframe, the PNC recalculates multi-hop transmissions from the current hop transmission to the final destination node. This process continues until one of the following conditions is satisfied:
  • a) ∑i=1ngn(Gi)
PPT Slide
Lager Image
Time-slot allocation map of MHCT.
After finishing scheduling, we may obtain the transmission scheduling map, such as in Fig. 2 . Each group Gi , comprises hop transmissions that can transmit concurrently. The size of group Gi is determined by the hop transmission
h j R i
with the highest number of time-slot requirements n ( i , j ).
The total consumption of time slots by the MHCT allocation map is given below
(9) ∑ i=1 n g n ( G i ), ∀ G i {i=1,2…., n g }. 
Higher bandwidth efficiency will be achieved with a smaller value of (9).
- 2. Weaknesse in MHCT
A. Imperfection in Time Allocation of MHCT
In the time-slot allocation process, the MHCT does not consider inter-collisions among concurrent groups. Consequently, in the MHCT conflicting/interfering transmissions cannot coexist in one group. Through scheduling the conflicting/interfering transmissions within a group in non-overlapping time, a further compact mapping can be achieved.
B. Condition for Multi-hop Conversion
After a multi-hop conversion, the transmission graph becomes more complex and few bottleneck links can emerge. Therefore, multi-hop conversion is not always beneficial. Furthermore, removing the bottleneck at the beginning of each superframe will introduce significant complexity into the system. To reduce the complexity and to obtain the full benefit of hop conversion, direct transmission ( Ri ) is only converted into a multi-hop transmission (
h k R i
) if
(10) ∑ i=1 n ∑ j=1 n h i [ h j R i  ,n(i,j) ]< ∑ i=1 n [ R i ,n(i)].
C. Starvation Problem in the Priority Scheme
Under an MHCT priority scheme, if nodes are very unevenly distributed or in cases of enormous transmission requests, starvation may occur. To resolve the starvation problem, we used an aging policy to increase the priority of a suffering transmission request by 25% on each miss; thus,
(11) P new =0.25 M count P prev ,
where P new is a new priority, P prev is a previous priority, and M count is a counter incremented by “1” on each miss.
- 3. Time-Slot Allocation Process in Proposed Scheme
To overcome the shortcomings of MHCT discussed in the previous section, we proposed two schemes: EMHCT-F and EMHCT-E. The main objective is the identification and grouping of hop transmissions so that two or more conflicting/interfering hop transmissions can coexist in the same group; if and only if, they satisfy the following conditions:
  • a) Conflicting and interfering transmissions should not overlap in time when they are in the same group.
  • b) They should followhop sequence orderof each transmission.
  • c) For EMHCT-F, time-slots requirementn(I,J) should satisfy condition 1 (below), and for EMHCT-E, it should satisfy condition 2 (below).
  • 1.n(I,J) should be less than or equal to the difference of the largest time-slot requirement of conflicting hop transmissions and time-slot requirement of groupn(G).•n(I,J) ≤n(G) − max[nc(I,J)].
  • 2.n(I,J) should be less than or equal to the sum of the remaining time slots in the superframe and the time-slot requirement of groupn(G).•n(I,J) ≤Nslots+n(G) − max[nc(I,J)], whereNslotsis the available time slots in a superframe.
            Algorithm 1: EMHCT-F 1.  BEGIN:2.  PNC receives a request h j R i for n(I, J) time slots. 3.  Sort all hops according to priority policy 4.  Start a new group G(k) with n(k) = max[n(I, J)] 5.  while Nslots ≥ min[n(I, J)] or all h j R i scheduled 6.     if h j R i does not conflict with existing hops in Gb then 7.        if n(b) ≥ n(I, J) then 8.            Update Gb = Gb { h j R i } ; 9.            Sort all hops according to priority policy. 10.        else 11.            if Nslots ≥ min[n(I, J)] then 12.            Start a new group G(k) with n(k) = max[rest of n(I, J)] 13.            end if 14.        end if 15.     end if 16.   end while 17.  for all non-empty group (Gi! = Null) , {i = 1, 2,…, b–1} do 18.       if h j R i is in conflict with few of existing hops in Gi 19.             Gc = Identify conflicting hops, where GcGi 20.             n(c) = Maximum n(I, J) in Gc 21.             for all h j R i in Gc do 22.                   if n(I, J) ≤ n(i) – n(c) 23.                         Update Gi = Gii; { h j R i }, position at n(c); 24.                   end if 25.             end for 26.       else 27.             Update Gi = Gii; { h j R i } 28.       end if 29.  end for 30.  if Nslots ≥ min[rest of n(I, J)] 31.       go to line 5 32.  end if 33.  END;
            Algorithm 2: EMHCT-E 1.  BEGIN: 2.  PNC receives a request h j R i for n(I, J) time slots. 3.  Sort all hops according to priority policy 4.  Start a new group G(k) with n(k) = max[n(I, J)] 5.  while Nslots ≥ min[n(I, J)] or all h j R i scheduled 6.     if h j R i does not conflict with existing hops in Gb then 7.        if n(b) ≥ n(I, J) then 8.            Update Gb = Gb { h j R i } ; 9.            Sort all hops according to priority policy. 10.        else 11.            if Nslots ≥ min[n(I, J)] then 12.            Start a new group G(k) with n(k) = max[rest of n(I, J)] 13.            end if 14.        end if 15.     end if 16.   end while 17.  for all non-empty group (Gi! = Null) , {i = 1, 2,…, b–1} do 18.       if h j R i is in conflict with few of existing hops in Gi 19.             Gc = Identify conflicting hops, where GcGi 20.             n(c) = Maximum n(I, J) in Gc 21.             for all h j R i in Gc do 22.                   if n(I, J) ≤ Nslots + n(i) – n(c) 23.                         Update Gi = Gii; { h j R i }, position at n(c); 24.                            if n(I, J) ≥ n(i) 25.                               Update n(i) = n(I, J); 26.                            end if 27.                   end if 28.             end for 29.       else 30.             Update Gi = Gii; { h j R i } 31.       end if 32.  end for 33.  if Nslots ≥ min[rest of n(I, J)] 34.       go to line 5 35.  end if 36.  END;
A. EMHCT-E/F Algorithms
Algorithms 1 and 2 are the enhanced versions of MHCT, which consider inter- and intra-group collisions to schedule hop-transmission requests. A brief stepwise explanation is given below.
a) STEP 1: Execute MHCT with an improved multi-hop conversion condition according to (10), and adjust the priorities using the improved version according to (11).
b) STEP 2: Start span-overlapping process from G 2 against G 1 . After finishing span overlapping between G 2 and G 1 , apply same procedure to G 3 against G 2 and so on. Start the span overlapping of G 2 from the first hop transmission of G 2 , and check if this hop transmission or the span-overlapping candidate causes a collision with the hop transmissions in G 1 , one by one, until meeting a hop transmission with a collision or a hop transmission belonging to the same transmission request. If a span-overlapping candidate finds a collision or hop transmission from the same transmission request, EMHCT-F checks conditions a), b) and c)1, whereas in the case of EMHCT-E, it checks conditions a), b) and c) 2, in section III, subsection 3.
c) STEP 3: If a hop-transmission candidate satisfying the above conditions is found through the lookup in STEP 2, the allocated time slots of the span-overlapping candidate move back-to-back at the end of interfering/conflicting hop transmissions. The same procedure in STEP 2 is then performed for the next hop transmission of G 2 . After finishing a span overlapping of all hop transmissions in G 2 , the hop transmissions of G 3 start the span-overlapping procedure described in STEP 2 and STEP 3. The span-overlapping procedure will continue until the last group.
EMHCT-E and EMHCT-F both outperform MHCT for different beamwidths. However, the performance of EMHCTE is better than EMHCT-F for a large beamwidth, whereas the EMHCT-E performance is better than EMHCT-F for a small beamwidth.
For a large antenna beamwidth, each transmission occupies a larger area with a large dimension of interference. Therefore, without altering the size of a group, it becomes difficult to place a new transmission request in pre-existing groups. The expansion of a group, which should satisfy condition 2 in (c). Increases the probability of placing new transmission requests in existing groups. Hence, EMHCT-E has better performance compared to EMHCT-F. For a smaller beamwidth, each transmission occupies a smaller area with a small dimension of interference. Therefore, without altering the size of a group, we can place a new transmission request in already existing groups, which should satisfy condition 1 in (c). Hence, EMHCT-F has better performance compared to EMHCT-E.
In a general pictorial form, EMHCT-E and EMHCT-F both provide the same time-slot allocation map for concurrent transmissions, as given in Fig. 3 . In EMHCT-F/E, each group holds more hop-transmission requests compared to MHCT, and hence the number of groups will be reduced for the same number of hop-transmission requests. The size of each group will be nearly the same because the size of a group is determined by the hop transmission
h j R i
with highest time-slots requirement n ( i , j ). This implies the following inequality:
∑ i=1  EMHCT-E/F n g n( G i ) < ∑ i=1  MHCT n g n( G i  ) < ∑ i=1 i   ∑ k=1 n h i  [ h j R i ,n(i,j)] < ∑ i=1 i [ R i ,n(i)] .
In Fig. 3 , hop transmission
h 2 R2
in G 1 has interference with
h 1 Rm
, and the previous hop transmission
  h 1 R2
also already exists in G 1 . Because n (2,2) is less than [ n (1,1)−( n ( m ,1)+ n (2,1))],
h 2 R2
is placed in G 1 so that it does not overlap with
h 1 Rm
and is scheduled after
  h 1 R2
. Similarly,
  h 3 R1
is placed in G 2 , along with conflicting hop
h 2 Rm
and the previous hop transmission
h 2 R1
, as this satisfies all conditions necessary to avoid a collision during concurrent transmissions.
PPT Slide
Lager Image
Time-slot allocation map of EMHCT-F/E.
IV. Simulation and Performance Evaluation
- 1. Simulation Settings
Thirty nodes were randomly deployed in a room 16 m × 16 m in size. Each node has multiple antennas. The number of antennas depends on the beamwidth used and is given by
(12) No.   of  Antennas= 360 Beamwidth in degrees .
We considered 7 GHz of bandwidth for our simulations (IEEE 802.15.3c defines the use of 9 GHz of bandwidth (57 GHz to 66 GHz); however, 7 GHz of bandwidth is available in Korea, the USA, and Japan). The rest of the parameters were selected according to [12] and [15] .
The simulation was carried out in Matlab using its standard functions. The nodes were randomly deployed and simulated for different numbers of active traffic flows, each data-traffic flow varying from 50 Mb to 350 Mb. The number of active traffic flows varied from 1 to 50, and for each simulation run, traffic-flow pair selection was also conducted randomly using 10 different seed values. For each beamwidth selection, a total of 700 simulations were carried out; the results were taken by averaging all of the simulation runs for each beamwidth selection. In our simulation, the computational cost of the antenna selection was not taken as a parameter. If we consider the computational cost of the antenna selection, there will be an upper bound to the number of antennas required to obtain the highest throughput.
Simulation parameters.
Parameters Value
Bandwidth 7,000 MHz
Transmission power 0.1 mW
Antenna gain 12 dBi
Background noise −134 dBm/MHz
Path-loss exponent 3 to 6
Antennas 18, 8, 4, and 2
Bandwidth 7,000 MHz
- 2. Performance Parameters
To compare and determine performance of our algorithm, we considered the following performance parameters.
a) Throughput: we calculated network throughput (the total volume of data traffic through the network) to check the bandwidth-efficiency achievement across the network using the proposed algorithms.
b) Fairness: a greedy network system, which is designed to achieve a higher network throughput, usually leads to unfair resource sharing. Hence, from a user perspective, few users (with satisfactory channel conditions) receive a very high data rate. Our capacity-gaining algorithm takes care of this problem and provides high throughput with acceptable fairness. We used the Jain’s fairness index to measure the fairness of the proposed schemes.
c) Concurrency gain: is defined as a ratio between network throughput achieved by concurrent transmission and corresponding network throughput by direct transmission, or a ratio between the time-slots requirement by direct transmission to the time-slots requirement by concurrent transmission.
Concurrency gain determines the aggregate improvement achieved by concurrency, compared to a direct transmission under the same network configuration. The concurrency gain is given as
(13) ρ=  n d ( i ) n c ( i ) = R i c R i d ,
where nd ( i ) is the time-slot requirement for a direct transmission, nc ( i ) is the time-slot requirement for a concurrent transmission,
R i c
is the data rate achieved for concurrent scheduling, and
R i d
is the data rate achieved for a direct transmission.
- 3. Optimality Comparison (Water Filling)
A water-filling solution is a well-known algorithm used to provide the theoretical bound for the capacity-gaining constrained optimization problem. A generalized and simple algorithm for the water-filling problem is presented in [18] . The solution is provided under a power constraint with the objective of optimization of power transmission within a single frame. However, with minor changes and assumptions, a water-filling solution can be used as a theoretical bound for an optimization of the time-allocation process. If we reconsider the objective function of optimization problem P1 (defined in section-III) and redefine according to the form of the constraint optimization problem discussed in [18] , then we can obtain a water-filing result to calculate the optimum capacity gain using . The objective of the following problem P2 is log concave, which ensures proportional fairness with optimum throughput [19] :
(14) P2:max ∑ i=1 n f log(1+ R i  ρ i ),         s.t   ∑ i=1 n f ∑ k=1 n h i n ( i,k ) where { i =1, 2..., nf } and
{k=1,2..., n h i },
, is given by;
(15) n(i,k)= (μ−  ρ i −1 ) + ,
where (∝) + selects the maximum value for n ( i , k ), i × k is the total number of hop-transmission requests
h k R i
, and μ is the water level, which is chosen such that
∑ i=1 n f ∑ k=1 n h i n ( i,k )=MAXSLOTS.
Once μ is selected, the depth from the water level depends upon concurrency gain ρ . The value of μ deepens if the concurrency gain ρ is high. This means that the hop-transmission requests
h k R i
will obtain a higher data rate with a low water level.
provides a water-filling solution with the worst case complexity of i × k iterations. In , constraint function g satisfies the constraint condition; that is,
g( μ )=  ∑ i=1 n f ∑ k=1 n h i n (i,k) μ −MAXSLOTS.
This constraint function makes the value of n ( i , k ) dependent upon water level μ . In this way, the hop-transmission requests (
h k R i
) with high concurrency gains ( ρ ) receive a higher allocation of time resources.
         Algorithm 3: Water-filling solution Input: Set of concurrency gain {(ρ)} and constraint function g. Output: Numerical solution {n(i, k)} and water level. 1.  Set l ˜ =i×k, and sort the set {(ρ)} such that ρi are in decreasing order ρ i 1 > ρ i+1 1 (define ρ l 1 =0). 2.  If ρ l  ˜ < ρ l  ˜ +1 and g( ρ l  ˜ ) then accept, and go to step 3. Otherwise, reject form new one by setting l ˜ = l ˜ 1, and go to step 2. 3.  Find water level ( ρ l  ˜ , ρ l+1 ˜ )|g(μ)=0, obtain numerical solution as n(i,k)= (μ ρ i 1 ) + for {i=1,2..., n f },  {k=1,2..., n h i }. 4.  Undo sorting done at step 1 and finish.
This greedy, yet proportional, fair approach increases the overall throughput of the network to provide the optimum result.
- 4. Results
A. Beamwidth Effect
The effect of beamwidth on aggregate concurrent transmissions is significant. With a small antenna beamwidth, the chance of a concurrent transmission increases due to the small coverage area per transmission. In addition, the antenna gain of small beamwidth is high; thus, the network throughput increases. Figs. 4 7 show the throughput comparison of MHCT, EMHCT-F, and EMHCT-E with different beamwidth selections. In all cases, EMHCT-F and EMHCT-E perform better than MHCT because both provide more compact time-allocation maps compared to MHCT. EMHCT-E provides a better throughput for large beamwidths ( Figs. 6 and 7 ), but increments in the performance with respect to a reduction of beamwidth are slower as compared to EMHCT-F. Hence, EMHCT-F performs better for a beamwidth smaller than 45° ( Fig. 4 ). For an antenna beamwidth of 45°, EMHCT-E’s and EMHCT-F’s performance is almost the same, as shown in Fig. 5 .
PPT Slide
Lager Image
Throughputs for a beamwidth of 20°.
PPT Slide
Lager Image
Throughputs for a beamwidth of 45°.
The reason for this behavior is obvious because EMHCT-F has a tendency to provide more opportunities for hop-transmission requests
hk R i
with fewer time-slot requirements n ( i , k ). For a small antenna beamwidth, the probability of an interference is reduced, and the number of hop-transmission requests
hk R i
with fewer time-slot requirements n ( i , k ) increases. Hence, if the group size is fixed, the hop-transmission requests
hk R i
with fewer time-slot requirements n ( i , k ) receives more opportunities to be scheduled by finding small rooms in previously created groups (without altering the size of the group). Therefore, EMHCT-F outperforms EMHCT-E for a smaller antenna beamwidth, as shown in Fig. 4 .
In contrast, for a large antenna beamwidth, the probability of interference increases, and the number of hop-transmission requests
hk R i
with more time-slot requirements n ( i , k ) increases. Hence, if the group size is fixed, the hop-transmission requests
hk R i
have fewer opportunities to be scheduled in a previously created fixed-sized group, which then degrades the performance of EMHCT-F. However, for EMHCT-E, a previously created group size is expandable during the span overlapping of groups. Therefore, EMHCT-E has a tendency to provide more opportunities for hop-transmission requests
hk R i
with higher time-slot requirements n ( i , k ). Through a group expansion, the probability to schedule transmission requests
hk R i
increases, which leads to a better performance of EMHCTE for a large antenna bandwidth, as shown in Figs. 6 and 7 .
PPT Slide
Lager Image
Throughputs for a beamwidth of 90°.
PPT Slide
Lager Image
Throughputs for a beamwidth of 180°.
B. Optimum Bound and Concurrency Gain
From the above results, it is clear that a small antenna beamwidth provides a better throughput for all schemes. Therefore, a network throughput comparison of MHCT, EMHCT-F/E, and the optimum results of the water-filling solution (shown in Fig. 8 ), was conducted for a beamwidth of 20°. EMHCT-F has the highest concurrency gain ρ compared to MHCT and EMHCT-E. Therefore, to obtain the upper bound of the optimum result for the water-filling solution, we used the concurrency gain ρ of EMHCT-F. It is clear that EMHCT-F and EMHCT-E are better sub-optimum solutions compared to MHCT, since both schemes provide more compact time-allocation maps compared to MHCT.
PPT Slide
Lager Image
Throughput of MHCT, EMHCT-F/E, and water filling.
PPT Slide
Lager Image
Concurrency gain ρ of MHCT and EMHCT-F/E.
The concurrency gains ρ of MHCT, EMHCT-F, and EMHCT-E are shown in Fig. 9 . EMHCT-F and EMHCT-E achieve a higher concurrency gain compared to MHCT. It is obvious since EMHCT-E and EMHCT-F have more compact time-allocation maps compared to MHCT, which allow a higher number of transmissions to be scheduled concurrently. MHCT attained a constant concurrency gain ρ after 20 flows, while EMHCT-E and EMHCT-F approached a constant concurrency gain ρ after 45 flows. We call it the saturation point of the scheduling algorithm. Once saturation occurs, the network throughput also approaches a constant value.
C. Flow Throughput Fairness
Our proposed schemes have provision to avoid starvation conditions by using an aging policy in priority schemes; hence, guaranteeing a better fairness compared to MHCT. Furthermore, in EMHCT-F/E, each group holds more hop-transmission requests compared to MHCT; hence, we get more compact and dense time-allocation maps. The size of each group will also be nearly the same because the size of a group is determined by the hop transmission
hk R i
with highest time-slot requirement n ( i , j ). This implies the majority of hop transmissions receive the same time allocation (that is, n ( Gi )); hence, fairness increases with more compact time allocation.
PPT Slide
Lager Image
Fairness of MHCT vs. EMHCT-F/E.
- 5. Algorithm Complexity of MHCT and EMHCT-F/E
We took the worst case scenarios to determine the complexity of the algorithms. Let us consider N number of traffic flows with a maximum of P number of hops in a path. A path can have a maximum of P = n − 1 hops, where n is the total number of nodes. A PNC therefore has to perform a sorting (merge sorting with maximum computational time of N log N ) of N elements for N × ( n − 1) number of times, and it has to make N number of comparisons for N × ( n − 1) number of times. It means that under the worst condition, to schedule one hop-transmission MHCT requires a computational time of N log 2 ( N )+ N +1. Therefore, to schedule all hop requests, the total computational time is N × ( n − 1) × ( N log 2 ( N )+ N +1). If n −1 nodes are kept constant, the computational complexity of MHCT is O( N 2 ).
The method to determine the worst-case complexity of EMHCT-F/E is the same as for MHCT, except for the scheduling of each hop, the number of comparisons under a worst case scenario is N × ( n −1). It means that scheduling a single one-hop transmission for EMHCT-F/E requires N log 2 N +( N × ( n −1)+1) computational time steps. To schedule all hop-transmission requests, the total computational time is N × ( n −1) × ( N log 2 N + ( N × ( n −1) + 1). If n −1 nodes are kept constant, the computational complexity of EMHCT-F/E is also O( N 2 ).
V. Conclusion
This paper analyzed the process of multi-hop concurrent transmission for mmWave communication considering WPAN in a single room. Based on the analysis of the proposed algorithm, a margin of improvement was found when we considered the relationship of collisions between hop transmissions in concurrent groups. Thus, for better bandwidth efficiency, we proposed two enhanced schemes of group span overlapping to reduce the total number of allocated time slots during a transmission period for given transmission requests. In addition, we explicitly showed through a simulation that span overlapping is beneficial. However, in the comparison phase EMHCT-F/E included some extra computational time steps. In the worst case, MHCT has to make N comparisons, while EMHCT-F/E has to make N × ( n −1) comparisons to schedule one hop transmission. Typically, WPAN has a small number of nodes to be served by a PNC; consequently, with current state-of- the-art hardware there is a negligible effect upon overall system performance. The performances of MHCT, EMHCT-E, and EMHCT-F were also compared with the water-filling solution. From the performance comparison of EMHCT-F/E and the ideal curve from water-filling, it is clear that there is still a possibility for additional improvement. In addition to the further improvement of the scheduling algorithm, the throughput can also be increased through other techniques. For instance, performance is highly dependent upon the node density in a localized region because a high density leads to a reduction in the average distance between nodes. However, we can predict that the performance will keep increasing until the average distance between nodes approaches the radioactive near field. We assumed that all nodes can transmit with maximum transmission power P . With high transmission power, a hop transmission occupies a large transmission area, causes more interference to other transmissions, and reduces the probability of concurrent transmission. Hence, with optimum-transmission power allocation the probability of concurrent transmission can further be increased.
This work was conducted as a part of the master’s degree program of Muhammad Bilal at Chosun University under the supervision of Dr. Moonsoo Kang. The enhanced research was supported by the ICT Standardization program of MSIP (Ministry of Science, ICT & Future Planning).
BIO
mbilal@etri.re.kr
Muhammad Bilal received his BS in computer systems engineering from the University of Engineering and Technology, Peshawar, Pakistan and his MS in computer engineering from Chosun University, Gwangju, Rep. of Korea. Currently, he is a PhD student at the University of Science and Technology, Rep. of Korea, at the Electronics and Telecommunication Research Institute, Daejeon, Rep. of Korea. His main research interests are design and analysis of network protocols, network architecture, and future internet.
mskang@chosun.ac.kr
Moonsoo Kang received his BS in computer science from the Korea Advanced Institute of Science and Technology, Daejeon, Rep. of Korea, in 1998 and his MS and PhD in engineering from the Information and Communications University, Daejeon, Rep. of Korea, in 2000 and 2007, respectively. Since 2007, he has been with the Department of Computer Engineering, Chosun University, Gwangju, Rep. of Korea, where he is now an associate professor. His research interests are various network protocols on ad hoc networks such as sensor, mesh, and vehicular networks
shah@hufs.ac.kr
Sayed Chhattan Shah is an assistant professor of computer science in the Department of Information and Communications Engineering at Hankuk University of Foreign Studies, Yongin, Rep. of Korea. His research interests lie in the fields of parallel and distributed computing systems, mobile computational grids, and ad hoc networks. He received his PhD in computer science from Korea University, Seoul, Rep. of Korea, in 2012 and his MS in computer science from the National University of Computer and Emerging Sciences, Karachi, Pakistan, in 2008. Prior to joining Hankuk University of Foreign Studies, he was a senior researcher at the Electronics and Telecommunications Research Institute, Daejeon, Rep. of Korea and an engineer at the National Engineering and Scientific Commission, Islamabad, Pakistan. Shah is an associate editor for the Journal of Telecommunications Systems and is on the editorial board for the Computer Communication and Collaboration Journal. He has served as a conference chair and has been on program committees of various international conferences. He is a member of IEEE, IEEE Communications Society, Korean GNSS Society, and International Association of Engineers.
sgkang@etri.re.kr
Shin-Gak Kang received his BS and MS in electronics engineering from Chungnam National University, Daejeon, Rep. of Korea, in 1984 and 1987, respectively and his PhD in information communication engineering from Chungnam National University, Rep. of Korea, in 1998. Since 1984, he has been working at the Electronics and Telecommunications Research Institute, Daejeon, Rep. of Korea, where he is now director of the Media Application Standards Research Section. From 2008, he has been a professor at the Department of Broadband Network Technology, University of Science and Technology, Daejeon, Rep. of Korea. He is actively participating in various international standard bodies as a vice-chairman of ITU-T SG11, convener of JTC 1/SC 6/WG 7, etc. His research interests include multimedia communications, contents networking, and future networks.
References
IEEE 802.15 WPAN Millimeter Wave Alternative PHY TaskGroup 3c (TG3c) http://www.ieee802.org/15/pub/TG3c.html
IEEE 802.11 VHT Study Group. http://www.ieee802.org/11/Reports/vht_update.htm
Lee J. , Chen Y. , Huang Y. 2010 “A Low-Power Low-Cost Fully-Integrated 60-GHz Transceiver System with OOK Modulationand on-Board Antenna Assembly,” IEEE J. Solid-State Circuits 45 (2) 264 - 275    DOI : 10.1109/JSSC.2009.2034806
Cai L.X. “Efficient Resource Management for mmWaveWPANs,” IEEE Wireless Commun. Netw. Conf., Kowloon, HongKong Kowloon, HongKong Mar. 11–15, 2007 3816 - 3821
Park M. , Gopalakrishnan P. 2009 “Analysis on Spatial Reuse andInterference in 60-GHz Wireless Networks,” IEEE J. SelectedAreas Commun. 27 (8) 1443 - 1452    DOI : 10.1109/JSAC.2009.091014
Yildirim F. , Liu H. 2009 “A Cross-Layer Neighbor-DiscoveryAlgorithm for Directional 60-GHz Networks,” IEEE Trans. Veh.Technol. 58 (8) 4598 - 4604    DOI : 10.1109/TVT.2009.2022532
Park M. “Millimeter-Wave Multi-gigabit WLAN:Challenges and Feasibility,” IEEE Int. Symp. PIMRC, Cannes,France Sept. 15–18, 2008 1 - 5
Zheng G. , Hua C. , Zheng R. “A Robust Relay Placement Framework for 60 GHz mmWave Wireless Personal AreaNetworks,”
Kim M. 2013 “Analysis of Resource Assignment for DirectionalMultihop Communications in mm-Wave WPANs,” ETRI J. 35 (1) 120 - 130    DOI : 10.4218/etrij.13.1812.0033
Cai L.X. “Spatial Multiplexing Capacity Analysis ofmmWave WPANs with Directional Antenna,” IEEEGLOBECOM, Washington, DC, USA Nov. 26-30, 2007 4744 - 4748
Maltsev A. 2013 Techniques for mmWave WPANCommunications with High-directional Steerable AntennasCombining Omni-directional Transmission with BeamformingTraining US Patent 20130130624 A1 filed Dec. 20, 2012
Qiao J. 2011 “Enabling Multi-hop Concurrent Transmission in60 GHz Wireless Personal Area Networks,” IEEE Trans. WirelessCommun. 10 (11) 3824 - 3833    DOI : 10.1109/TWC.2011.092711.102104
Mudumbai R. , Singh S. , Madhow U. “Medium AccessControl for 60 GHz Outdoor Mesh Networks with HighlyDirectional Links,” IEEE INFOCOM Rio de Janerio, Brazi Apr.19–25, 2009 2871 - 2875
Geng S.Y. 2009 “Millimeter-Wave Propagation Channel Characterization for Short-Range Wireless Communications,” IEEE Trans. Veh. Technol. 58 (1) 3 - 13    DOI : 10.1109/TVT.2008.924990
Yang Z. , Cai L. , Lu W.-S. “Practical Scheduling Algorithmsfor Concurrent Transmissions in Rate-Adaptive WirelessNetworks,” IEEE INFOCOM San Diego, CA, USA Mar. 14–19, 2010 1 - 9
Collonge S. , Zaharia G. , El Zein G. 2004 “Influence of theHuman Activity on the Propagation Characteristics of the 60 GHzIndoor Channel,” IEEE Trans. Wireless Commun. 3 (6) 2396 - 2406    DOI : 10.1109/TWC.2004.837276
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
Palomar D.P. , Fonollosa J.R. 2005 “Practical Algorithms for aFamily of Waterfilling Solutions,” IEEE Trans. Signal Process. 53 (2) 686 - 695    DOI : 10.1109/TSP.2004.840816
Li W. 2014 “AP Association for Proportional Fairness in MultirateWLANs,” IEEE/ACM Trans. Netw. 22 (1) 191 - 202    DOI : 10.1109/TNET.2013.2245145