Visible Light Communication (VLC) using Light Emitting Diodes (LEDs) within the existing lighting infrastructure can reduce the implementation cost and may gain higher throughput than radio frequency (RF) or Infrared (IR) based wireless systems. Current indoor VLC systems may suffer from poor downlink resource allocation problems and small system throughput. To address these two issues, we propose an algorithm called a conflict graph scheduling (CGS) algorithm, including a conflict graph and a scheme that is based on the conflict graph. The conflict graph can ensure that users are able to transmit data without interference. The scheme considers the user fairness and system throughput, so that they both can get optimum values. Simulation results show that the proposed algorithm can guarantee significant improvement of system throughput under the premise of fairness.
I. INTRODUCTION
As a new highcapacity shortrange wireless technology, visible light communications can meet the needs for lighting and communications
[1

3]
. In order to meet the needs of communication, multiple transmitters need to be installed on the ceiling. Because of the channel characteristics of visible light, transmitter coverage and reception range of a receiver are usually limited. In multiuser scenario, several transmitters are necessary in order to cover the whole communication area, which may cause severe interuser interference. Therefore, a proper scheduling algorithm is needed to address this problem. Other problems we are concerned with are user “fairness” and system throughput. A proper scheduling of users depends on the balance of them. One cannot always choose the user with the highest rate, because the users with lower rates would be starved. However, if the users with the lowest rate are chosen, the throughput would drop. The question is how to schedule the resource fairly. Fair scheduling would lower the throughput over the maximum possible, but it would provide more acceptable levels to lowrate users.
The research in the topic is scarce, since the study of scheduling on multiuser scenarios for indoor visible light communications is in an initial stage. Targeting at higher system throughput, a novel fullduplex selfadaptive minimum contention window (SACW) MAC protocol was designed for an indoor VLC star topology network system
[4]
. This protocol allowed concurrent sending and receiving of data frames between the central node and terminal nodes. It could achieve higher downlink throughput compared with halfduplex operation. A fairness tuning parameter might help balance user fairness and throughput. This goal was achieved through initiatively tuning the parameter in
[5]
. Ojemba Babatundi
et al
.
[6
,
7]
proposed a proportional fair sharing algorithm. They took the user rate and average user rate into consideration, which made them capable of achieving a balance between user fairness and throughput. In
[8]
, researchers presented a signaling scheme for user access and service setup. They proposed three lamp selection schemes distanceprior (DP), service aggregation (SA) and bandwidthbased (BB). These three schemes realized flexible user access and efficient resource allocation. The interference graph model was used to choose as many users as possible without interference in
[9]
. The model avoided interference but lost the advantage of transmitting diversity because all users were dealt with independently. Researchers
[10
,
11]
proposed a greedy weight minimum (GWMIN) algorithm. It considered the fairness and throughput. However, because the greedy algorithm converges locally, the obtained solution might not be globally optimal. A light fidelity access point (AP) provided high throughput while wireless fidelity offered basic coverage. In
[12]
, researchers proposed a scheme for dynamic allocation of resources to users. They proved that there was a tradeoff between the aggregate throughput and user fairness. Li
et al
.
[13]
investigated various VLC cell formation schemes. To solve the load balance problem, they invoked a centralized and distributed algorithms
In order to solve the problems we mentioned above, a conflict graphbased scheduling (CGS) algorithm is proposed in this paper. The algorithm consists of two parts. Based on the coverage of each AP, the conflict graph that is also employed to select user sets of noninterference is obtained. Using the conflict graph and the user sets, we design a scheduling scheme to choose the users to schedule for each time slot.
The rest of the paper is organized as follows. In Section 2, we give an overview of indoor VLC system and the problem formulation. We introduce the CGS algorithm in Section 3. The simulation and results are given in Section 4. Finally, we draw the conclusions in Section 5.
II. INDOOR VLC SYSTEM MODEL
According to
[14]
, compared with the direct received average power of the line of sight (LOS) path, the NLOSpower may be negligible. Therefore only LOSpower is considered as the desired received power for the reason of simplicity. There are several users in the room, their position is randomly distributed. Many APs are mounted on the ceiling, each one of them consists of many LED chips for the purpose of signal enhancement and illumination. A photon detector (PD) serves as a receiver to receive downlink signals. The sensitivity of the PD determines the received signal intensity. The light source is assumed to be Lambert pattern
[15]
. A typical indoor VLC system model is depicted as follows.
Indoor VLC system model. (a) Layout of APs, (b) Light downlink transmission sketch.
For a given transmitted optical power
P
_{t}
of each VLC AP, the optical power
P
_{r}
received by PD is given as
[14]
:
where
D
_{d}
is the distance between transmitter and receiver,
E
is the physical area of the detector in a VLC receiver,
T_{s}
(
ψ
) denotes the gain of the optical filter,
g
(
ψ
) is the gain of an optical concentrator,
Φ
is the angle of irradiance, and
ψ
is the angle of incidence. Parameter
m
, the order of Lambertian emission is given by the semiangle at half illumination of an LED
Φ
_{1/2}
as: m = ln2 / ln(cos(
ϕ
_{1/2}
)). In a common scenario, the
m
=1,
T_{s}
(
ψ
)=
T
_{s0}
,
g
(
ψ
)=
g
_{0}
, which are constant. Hence, if the sensitivity of the receiver
P
_{sens}
is given, the coverage of each AP can be obtained. Its definition is given as:
where
h
denotes the vertical distance between the receiver and AP. For an AP
L
_{i}
and its coordinate denotes as (
x
_{i}
,
y
_{i}
), we know whether a user
U
_{j}
(
x
_{j}
,
y
_{j}
) is within its coverage. Let
S
_{i}
denote the user set that
L
_{i}
covers then it should satisfy the following conditions:
There are
N
APs and
M
users within the VLC system. Time is divided into small scheduling intervals (called slots). In each interval several of the
N
users are chosen to transmit to its destination by a central scheduler
[8]
. Because of the inherent nature of visible light channels, it is appropriate to consider the interuser interferences as depicted in
Fig. 2
Demonstration of interferences between users.
The
L
x represents an AP and
U
x denotes a user in
Fig. 2
. For a given time slot as shown in
Fig. 2
on the left, assuming that
L
_{1}
is assigned to user
U
_{1}
for data transmission,
L
_{2}
is assigned to user
U
_{3}
for data transmission. Because
U
_{1}
and
U
_{3}
are in different coverage, there is no interference in this scenario. However, the scenario depicted in
Fig. 2
the right shows the interference case.
U
_{1}
chooses
L
_{1}
for data transmission and
U
_{2}
chooses
L
_{2}
for data transmission. Since there are two users in the coverage of
L
_{1}
, the interference occurs.
U
_{2}
would suffer severe interuser interference. Apparently, for a given time slot there can only be one user within a given coverage for the purpose of interference avoidance. Therefore we can formulate the problem as follows. Let Θ={
U
_{i}
 1, 2, ⋯,
N
} be the user set and T = {
L
_{i}

i
= 1, 2, ⋯,
M
} be the AP set. The user set that
L
_{i}
covers is denoted as
S
_{i}
as shown in Eq. (3). In order to avoid interference, for each AP
L
_{i}
we have:
where
if user
U
_{i}
is chosen at time slot
k
and is zero otherwise.
Our goal is to maximize the throughput of the system as well as take into consideration the quality of service (the user fairness), hence the problem formulation can be given as:
where ℜ is the rate region and
R
and
are the rate vector of all users and the average rate vector of user
U
_{j}
, respectively. Each
F_{j}
(
x
) is an increasing concave continuously differentiable function defined for x≥0. More discussions of this function can be found in
[6
,
7]
. If the scheduler always chooses the users with the highest rate, it is the maximum rate (MR) scheduling. It takes no consideration of interference or fairness. As a result, the user fairness may become very low and throughput very high.
III. CONFLICT GRAPH SCHEDULING DOWNLINK RESOURCE
From the previous analysis, we can draw the conclusion that there are three problems that we need to solve. They are interference between users, throughput and user fairness. A conflict graph is employed to solve the first probleminterference. The scheduling scheme is used to achieve the balance between fairness and throughput.
First, let us define the conflict graph. As shown in
Fig. 3
, there are several users within an AP coverage. They are not allowed to choose the same AP to transmit at the same time slot. Therefore, a dotted line is drawn between them, which means there is interference between them. When all the users are dealt with the same operation, the conflict graph is achieved. Obviously, if there is no dotted line between users, they can choose the same time slot to transmit without interference. Hence the conflict graph can be given as G = <
V
,
E
,
φ
> where V = {
U
_{1}
,
U
_{2}
, ⋯,
U
_{M}
}, E = {
e
_{1}
,
e
_{2}
, ⋯,},
e
_{x}
denotes the edge between users in the conflict graph. And
M
order matrix
A
=(
a
_{ij}
) is called user interference matrix where
a
_{ij}
is the number of edges whose starting point is
U
_{i}
and ending point is
U
_{j}
. According to Eq. (3), the definition of
a
_{ij}
is given as:
Demonstration of conflict graph.
After the conflict graph is obtained, the next step is to determine the users who are selected to transmit data at the current slot. However this is not an easy task. In order to solve it, the problem is divided into two phases: finding the user sets and choosing one from them.
Phase 1: find the users (we define these users as noninterference user set) who are able to transmit data without causing interferences and more than one set may be found. The goal of this phase is to find all the noninterference user sets. This operation is equal to finding all the maximal independent sets in graph
G
. It is a nondeterministic polynomial problem. In order to solve this problem, a noninterference user sets selection algorithm is proposed and its fake code is given in
Table 1
.
Process of finding noninterference user sets
Process of finding noninterference user sets
In
Table 1
,
Q
represents the users set of noninterference, and each
Q
consists of several users with no interference between them.
H
stands for the set of
Q
. We can use
Fig. 3
to illustrate the algorithm. In
Fig. 3
,
Q
_{1}
={
U
_{3}
},
Q
_{2}
={
U
_{4}
}
Q
_{3}
={
U
_{2}
,
U
_{5}
},
Q
_{4}
={
U
_{1}
,
U
_{5}
}, therefore H={
Q
_{1}
,
Q
_{2}
,
Q
_{3}
,
Q
_{4}
}.
Phase 2: in this phase, we focus on selecting a user set from
H
so that the central scheduler can decide which users are allowed to transmit data at the current slot. In other words, we can use
H
to calculate the users who have access to the APs at the current slot. Assuming that the end of each time slot is represented as
k
, and at time
k
for each user the possible rate for the next time slot is known as
R
_{i,k+1}
.
I
_{i, k+1}
indicates that the user
U
_{i}
is selected for data transmission at the time slot
k
+1, the average rate of user
U
_{i}
before slot
k
is given as:
For each
Q_{j}
∈H
, calculate the weight as
W
_{j}
:
where R
_{i,k+1}
is the rate at time slot
k
+1, when we decide the users who have the access to AP in time slot
k
, the users that satisfy the following condition is our preference:
where Γ is the element number in
W
. After the users are derived, we decide which APs provide service for the users. From Eq. (1), we know that the received power is inversely proportional to the square of distance between the user and the AP. For the purpose of maximizing the received power, the nearest AP is chosen, that is, the AP that serves the user satisfies the following condition:
where
D
(
U, L
) is the Euclidean distance between user
U
and AP
L
, it can be calculated by the coordinates of user and AP.
IV. SIMULATION AND ANALYSIS
We evaluate the performance of the proposed CGS algorithm from the perspective of the throughput and the user fairness. The scenario is based on a room of size 10 m × 10 m × 3 m. The APs in the room are uniformly distributed as 4 × 4 arrays. Their heights are 3 meters above the floor. All the APs transmit identical power. The height of the receiver is 1 meter. Detailed parameters are shown in
Table 2
.
Default parameters used in simulation
Default parameters used in simulation
Two parameters are simulated, the throughput and the SFI (Service Fairness Index) which represents the user fairness
[16]
. The SFI is defined as:
where
is the average throughput of
U
_{i}
. The smaller the SFI is, the higher the fairness is. On the contrary, the bigger the SFI is, the lower the fairness becomes. When SFI = 0, all the users have the same average throughput, which means absolutely fairness is achieved. The SFI under different numbers of users is shown in
Fig. 4
.
SFI by using different algorithms.
MR algorithm always chooses the maximum rate users without interference. This feature makes its throughput the highest of all algorithms, however its user fairness is the lowest. The meaning of the algorithm is that it reveals the maximum possible throughput. Algorithm1
[9]
always chooses the most users without interference. Because this algorithm takes neither throughput nor fairness into consideration, its fairness and throughput are the worst of all algorithms. GWMIN
[11]
stands for the minimum weight greedy algorithm. Because the greedy algorithm converges locally, the throughput and fairness may not reach its limitation.
From
Fig. 4
and
Fig. 5
we can see that proposed CGS has the highest user fairness and better throughput, because in phase 1 the conflict graph ensures that users can transmit data without interference, and in phase 2 the scheduling scheme takes the user rate and average user rate into account, which makes sure of the balance between throughput and user fairness. From Eq. (7) and Eq. (8), when the user rate increases or average user rate decreases, the weight of this user set increases, which makes the possibility of choosing this user set increase. As a result, throughput and user fairness increase; On the contrary, when the user rate decreases or average user rate increases, the weight of this user set decreases, which makes the possibility of choosing this user set decrease. As a result, throughput and user fairness increase. Doing these two operations repeatedly, the balance between the throughput and fairness is achieved.
Throughput by using different algorithms.
In order to prove the robustness of the proposed algorithm, we would like to increase the number of APs and enlarge the room size. In this configuration, the system environment deployed is an empty room with dimensions 10 m × 18 m × 3 m and there are 4×8 APs installed equidistantly on the ceiling. The vertical view of the layout is shown in
Fig. 6
. Again we compare the performance of our proposed algorithm with the other three algorithms mentioned earlier. The simulation results are depicted in
Fig. 7
and
Fig. 8
.
Vertical view of second AP arrangement.
SFI with different algorithms under the second configuration.
Throughput with different algorithms under the second configuration.
Similar to the results in the first configuration, our proposed algorithm has the highest user fairness and better throughput. Moreover, the advantages of our scheme are more obvious with more APs and larger room size. With these numerical results, we would like to demonstrate that the application of our scheme is not limited by the AP number or room size. Our scheduling algorithm is robust to arbitrary AP number or room size.
V. CONCLUSION
In this paper, we first give an overview of indoor VLC channel characteristics and the problem formulation. Under the principle of fairness scheduling, a conflict graphbased scheduling algorithm is proposed to improve the performance of downlink resource allocation. Simulations and results demonstrate that our algorithm can achieve the balance between the throughput and user fairness. And time division multiplexing is used to ensure that the algorithm can be applied for a variety of modulation methods.
Acknowledgements
This research was funded by the Scientific Research Fund of Chongqing Municipal Commission (KJ1400421), by National Nature Science Foundation of China (NSFC 61275077), Chongqing Research and Innovation Project of Graduate Students (CYS15172), and by the Basic and Frontier Research Program of Chongqing (CSTC 2015jcyjA40024, CSTC 2011jjA1361).
Suzuke K.
,
Asahi K.
,
Watanabe A.
(2015)
“Basic study on receiving light signal by LED for bidirectional visible light communications,”
Electronics and Communications in Japan
2
268 
274
Tao S.
,
Tang J.
,
Yin T.
,
Ping W.
,
Yu L.
(2015)
“Multiusers network model and the corresponding networking scheme for indoor VLC systems,”
Opt. Express
9
11600 
11618
Zhang J.
,
Wang H.
(2015)
“An improved SNR uniformity optimization scheme for VLC system,”
Journal of Chongqing University of Posts and Telecommunications (Natural Science Edition)
1
78 
82
Wang Z.
,
Liu Y. H.
,
Lin Y. P.
(2015)
“Fullduplex MAC protocol based on adaptive contention window for visible light communication,”
Optical Communications and Networking
3
164 
171
Babatundi O.
,
Lijun Q.
,
Julian C.
“Downlink scheduling in visible light communications,”
Proc. IEEE 2014 Sixth International Conference on Wireless Communications and Signal Processing (WCSP)
Heifei, China
Oct. 2014
1 
6
Borst S.
(2003)
“Userlevel performance of channelaware scheduling algorithms in wireless data networks,”
IEEE/ACM Transactions on Networking
3
636 
647
Kushner H. J.
,
Whiting P. A.
(2004)
“Convergence of proportionalfair sharing algorithms under general conditions,”
IEEE Transactions on Wireless Communications
4
1250 
1259
Huang Z. T.
,
Ji Y. F.
(2012)
“Efficient user access and lamp selection in LEDbased visible light communication network,”
Chin. Opt. Lett.
5
1 
5
Li Y. Y.
,
Wang L. J.
,
Ning J. X.
“VICO: A framework for configuring indoor visible light communication networks,”
Proc. IEEE 9th International Conference on MASS
Las Vegas, NV, USA
Oct. 2012
136 
144
Xin H.
,
Fu X. Q.
,
Xu W.
(2015)
“Incremental scheduling scheme for indoor visible light communication,”
Electron. Lett.
3
268 
270
Tao Y. Y.
,
Xiao L.
,
Wang J. H.
(2015)
“Scheduling for indoor visible light communication based on graph theory,”
Opt. Express
3
2737 
2752
Wang Y. L.
,
Haas H.
(2015)
“Dynamic load balancing with handover in hybrid lifi and wifi networks,”
IEEE J. Lightwave Technol.
22
4671 
4682
Li X.
,
Zhang R.
,
Hanzo L.
(2014)
“Cooperative load balancing in hybrid visible light communications and wifi,”
IEEE Transactions on Communications
4
1319 
1329
Komine T.
,
Nakagawa M.
(2004)
“Fundamental analysis for visible light communication system using LED lights,”
IEEE Transactions on Consumer Electronics
1
100 
107
Ding D. Q.
,
Ke X. Z.
(2010)
“Research on generalized mathematic radiation model for white LED,”
Acta Optica Sinica
9
2536 
2540
Bensaou B.
,
Chan K. T.
,
Tsang D. H. K.
1997
“CreditBased Fair Queueing(CBFQ): A simple and feasible scheduling algorithm for packet networks,”
Proc. IEEE ATM Workshop
Lisboa, Portugal
May 1997
589 
594