(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...,
n_{f}
} 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 $\tilde{l}=i\times k,$ and sort the set {(ρ)} such that ρ_{i} are in decreasing order ${\rho}_{i}^{-1}>{\rho}_{i+1}^{-1}$ (define ${\rho}_{l}^{-1}=0).$ 2. If ${\rho}_{\tilde{l}}{\rho}_{\tilde{l}+1}$ and $g({\rho}_{\tilde{l}})$ then accept, and go to step 3. Otherwise, reject form new one by setting $\tilde{l}=\tilde{l}-1,$ and go to step 2. 3. Find water level $\in ({\rho}_{\tilde{l}},{\rho}_{\tilde{l+1}})|g(\mu )=0,$ obtain numerical solution as $n(i,k)={(\mu -{\rho}_{i}^{-1})}^{+}$ for $\{i=1,\mathrm{2...},{n}_{f}\}\text{\hspace{0.17em}},\text{\hspace{0.17em}}\{k=1,\mathrm{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
.
Throughputs for a beamwidth of 20°.
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
.
Throughputs for a beamwidth of 90°.
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.
Throughput of MHCT, EMHCT-F/E, and water filling.
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
(
G_{i}
)); hence, fairness increases with more compact time allocation.
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.
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