Scheduling for indoor visible light communication based on graph theory

Yuyang Tao; Xiao Liang; Jiaheng Wang; Chunming Zhao

doi:10.1364/OE.23.002737

1. Introduction

Visible light communication (VLC), as a promising solution to indoor short-range wireless communication, has gained increasing attention in recent years. It has the advantages of free spectrum, natural confidentiality, low energy consumption and no electromagnetic radiation. Light-emitting diode (LED) is the key component in VLC systems. Having faster response rate than traditional lighting apparatuses, LEDs can be used to implement high-speed communication. So far, most research has focused on point-to-point transmitting and receiving technologies to achieve high data rates [1–3]. For example, a Gbps level data rate has been reported in [4–8].

One of the main benefits of VLC is that it can fulfill the functions of illumination and wireless communication simultaneously. In order to satisfy the illumination requirement in an indoor area, e.g., a meeting room, multiple sets of LEDs are installed on the ceiling. As a result of the indoor line-of-sight channel characteristic, the range of visible light signal propagation and the receiving range of photodetectors are often spatially confined. Thus high multiplexing ratio can be achieved, which means multiple users can be served simultaneously. This is a major advantage of VLC over traditional RF systems. In this scenario, controlled by a central station, several sets of LEDs can serve a common user simultaneously to achieve high transmitting diversity. Consequently, the strength of the received optical signal is greatly enhanced, and high-rate communication is possible. On the other hand, however, when multiple users are present, inter-user interference becomes a major factor seriously affecting system performance. Therefore, resource allocation and scheduling become vital issues in multiuser VLC systems. Appropriate scheduling schemes are needed to coordinate the inter-user interference in order to fully utilize the VLC resources.

So far, since the study of scheduling and resource allocation in multiuser VLC systems is still at initial stage, not many research works have been published on these topics, especially for multi-transmitter multi-receiver scenarios. In [9], color-based visible light channels are assigned to coordinate interference and reduce the dropping probability in IEEE 802.15.7 wireless personal area network (WPAN). A joint scheduling and resource allocation scheme with channel selection is proposed in [10] to increase the system throughput of IEEE 802.15.7 WPAN. In [11], hexagonal cell structure based on Red-Green-Blue (RGB) LEDs is used to avoid interference and improve system flexibility. The authors in [12] studied the higher layer protocol design and configuration issues in VLC settings, and proposed a framework scheduling LED-to-client transmissions with tunable beamwidths and beam-angles. Transmitter and subcarrier allocation is carried out in a heuristic manner in [13] to improve throughput in multiuser VLC systems using discrete multi-tone (DMT) modulation. Note that, most works endeavor to improve throughput without considering fairness among users.

In this paper, we investigate the scheduling problem for indoor multiuser VLC systems where multiple LED access points (APs) broadcast signals to multiple users. By assigning APs to users to coordinate the inter-user interference, our goal is to maximize the sum capacity while ensuring a certain degree of fairness. Compared with the existing works like [9, 12, 13], we focus on low-complexity schemes. To relieve processing burdens at the user receivers, we avoid inter-user interference by time and space scheduling. Employing graph theoretic approaches, we propose a novel interference graph model to analyze the inter-user interference. Compared with the conflict graph model used in [12], the scale of our graph is much smaller which greatly reduces computational complexity. In addition, our proposed scheme does not have mechanical requirements of LEDs [12].

With the interference graph we propose, the scheduling problem is transformed into a maximum weighted independent set problem (MWISP). A scheduling algorithm is proposed based on the greedy algorithm to solve the MWISP, aiming to achieve multiuser multiplexing and increase sum-rates. Under the principle of proportional fairness scheduling, users in conflict are scheduled with time-division multiplexing (TDM) to ensure fairness. Under different LED arrangements, simulations demonstrate our schemes outperform the existing methods in both capacity and fairness.

The rest of the paper is organized as follows. The system model and problem formulation are described in Section 2. The graph model and solutions to the scheduling problem are provided in Section 3. Simulation results and analyses are presented in Section 4. At last, Section 5 draws the conclusion.

2. System model and problem formulation

2.1. System model

In this paper we consider an indoor line-of-sight (LOS) VLC system with multiple LED access points and multiple users. An AP consists of several LED chips to enhance signal strength and meanwhile to satisfy the illumination requirements. In the first scenario, multiple APs are placed equidistantly on the ceiling of the room. The layout of the system is demonstrated in Fig. 1, where distance between adjacent APs is denoted by d, and the height from the ceiling to the horizontal plane on which receivers are placed is denoted by h.

Fig. 1 Layout of the indoor VLC system.

Download Full Size | PDF

Considering that the reflected signals are usually much weaker than the LOS signals [14], it is reasonable to focus on the optical signals that propagate directly from LEDs to the receivers. Since the data signals are superposed onto the light emitted by LEDs, the signals studied are the alternating data signals without DC bias. According to the Lambertian emission model, within the field of view (FOV) of a receiver, the channel gain of the optical link is given by [15]

H (0) = \frac{A (k + 1)}{2 π l^{2}} \cos^{k} (θ_{1}) \cos (θ_{2}),

where A is the area of photodiode detector, l is the distance between the AP and the receiver, θ₁ is the angle of irradiance, and θ₂ is the angle of incidence. k is the order of Lambertian emission, and can be calculated as

k = - \frac{\ln 2}{\ln (\cos ϕ_{\frac{1}{2}}))},

where

ϕ_{\frac{1}{2}}

is the semi-angle at half power of the transmitter. The received optical power is

P_{o r} = {\begin{matrix} H (0) P_{o t,} & θ_{2} \leq θ_{FOV} \\ 0, & θ_{2} > θ_{FOV} \end{matrix},

where P_ot is the transmitted optical power. Thus the received electric power P_er is

P_{e r} = {(P_{o r} R)}^{2},

where R is the responsivity of the photodiode.

The noise at the receiver is mostly made up of shot noise and thermal noise. Their variances are given respectively by [16]

σ_{s}^{2} = 2 q R P_{o r} B + 2 q I_{b g} I_{2} B,

σ_{t}^{2} = \frac{8 π k_{B} T_{K} η_{C} A I_{2} B^{2}}{G} + \frac{16 π^{2} k_{B} T_{K} Γ A^{2} η_{C}^{2} B^{3} I_{3}}{g_{m}},

where q is the electronic charge constant, B is the equivalent noise bandwidth, I_bg is the background current, I₂ is the noise bandwidth factor, k_B is the Boltzmann’s constant, η_C is the fixed capacitance of the photo detector per unit area, T_K is the absolute temperature, G is the open-loop voltage gain, Γ is the FET channel noise factor, g_m is the FET transconductance, and I₃ is 0.0868. Hence, the signal-to-noise ratio (SNR) γ of the received signal at a receiver from a single AP is given by

γ = \frac{{(H (0) P_{o t} R)}^{2}}{σ_{s}^{2} + σ_{t}^{2}} .

Suppose there are K users and N APs in a square area. We refer to the set of users $U$ and the set of APs $A$ , where $U = {u_{i} | i = 1,2, \dots, K}$ and $A = {A P_{i} | i = 1,2, \dots, N}$ . signal power of APs is assumed to be fixed. For convenience we also restrict that each AP can only serve at most one single user in a time slot. To make full use of the system resources, we utilize the concept of virtual cell [17]. Specifically, for an active user u_k, several APs from $A$ are chosen to form a virtual cell $V C_{k}$ . Controlled by a central station, APs in $V C_{k}$ send identical signals to u_k simultaneously to enhance transmitting diversity. Since the system has to employ intensity modulation and direct detection (IM/DD), the signals are mixed together at the receiver. Consequently, for any active user, the receiving SNR γ is expressed as follows

γ = \frac{{(\sum_{j} h_{j} P_{o t} R)}^{2}}{σ_{s}^{2} + σ_{t}^{2}},

where j denotes APs within the receiving range and h_j denotes the channel gain from AP_j. Clearly, the receiving SNR is enhanced with the help of virtual cells.

Because of the inherent nature of visible light channels, as depicted in Eq. (1) and Eq. (3), the channel characteristic is mainly determined by the positions of the transmitter and the receiver. The signal strength attenuates as it propagates further. Also, the receiving range of the receiver is limited due to its FOV. These features lead to high potential multiplexing ratio, meaning that more users can be served simultaneously if they are spatially separated in the area. They also provides possibilities to avoid inter-user interference by arranging non-overlapped links between APs and users. Thus, to achieve good performances, e.g., high sum rate, proper resource allocation and scheduling are necessary.

2.2. Problem formulation

Our aim is to find good scheduling schemes which maximize the sum rate of the system, and take into account the quality of service (QoS) requirements as well. With these considerations, we define

\sum_{i = 1}^{K} U_{i} (\bar{r_{i, k}}),

as the aggregate utility [18, 19], where U_i(·) is an increasing concave utility function and measures the satisfaction of u_i based on its throughput.

\bar{r_{i, k}}

is the average throughput for u_i calculated at time slot k. The current available rate vector r_k is defined as

r_{k} = {[r_{1, k}, r_{2, k}, \dots, r_{K, k}]}^{T},

where r_i,k is the current available rate for u_i at time slot k. According to the gradient-based scheduling framework, the goal of the scheduling is to choose r_k which has the maximum projection onto the gradient of Eq. (9). Therefore, the scheduling goal is

\max \sum_{i = 1}^{K} U_{i}^{'} (\bar{r_{i, k}}) r_{i, k} .

Consider the commonly used iso-elastic utility functions [20] as

U_{i} (\bar{r_{i, k}}) = {\begin{matrix} α^{- 1} {\bar{r_{i, k}}}^{α}, & α \leq 1, α \neq 0 \\ \log (\bar{r_{i, k}}), & α = 0 \end{matrix},

where α is a fairness parameter. Then Eq. (11) is converted into

\max \sum_{i = 1}^{K} {\bar{r_{i, k}}}^{α - 1} r_{i, k} .

Clearly, the result of Eq. (13) is influenced by the fairness parameter α. Different values of α represent different fairness criterions. In order to meet the fairness requirements, we set α = 0, and Eq. (13) can be rewritten as

\max \sum_{i = 1}^{K} \begin{matrix} \underline{r_{i, k}} \\ \bar{r_{i, k}} \end{matrix} .

This leads to proportional fairness scheduling (PFS), which is able to maintain fairness in the long run [21]. To further formulate Eq. (14), we define a K×N channel information matrix H, whose (i, j)th element h_ij is the channel gain from AP_j to u_i. We assume that the central station has full knowledge of channel information between any transmitters and receivers, provided by perfect feedback channels. The scheduling problem can be formulated as

\max \sum_{i = 1}^{K} \begin{matrix} 1 \\ \bar{\bar{r_{i, k}}} \end{matrix} \log_{2} (1 + \frac{{(\begin{matrix} \sum \\ {AP}_{j} \in {V ℂ}_{i} \end{matrix} h_{i j} P_{o t} R)}^{2}}{σ^{2} + I_{i}})

s . t . {V ℂ}_{i} \cap {V ℂ}_{j} = ϕ, i, j = 1, \dots, K, i \neq j

\cup_{i = 1}^{K} {V ℂ}_{i} \subset A .

I_i in Eq. (15) is the interference received by u_i, which is calculated as

I_{i} = {\sum_{m = 1, m \neq i}^{K} (\begin{matrix} \sum \\ {AP}_{n} \in {V ℂ}_{m} \end{matrix} h_{i n} P_{o t} R)}^{2} .

For this discrete optimization problem, the acquisition of optimal solution is extremely hard. To simplify the problem, we are apt to mitigate the effect of interference I_i. Due to the high SNR nature of VLC systems [22], the existence of inter-user interference in multi-transmitter multi-receiver scenarios will greatly reduce the receiving signal-to-interference-plus-noise ratio (SINR), leading to the degradation of system performance [11]. To describe the potential interference among users, we use the channel information matrix H to generate a K×N connection matrix C. Suppose that if h_ij ≠ 0, u_i can have a link with AP_j. The element of C is defined as

c_{i j} = {\begin{matrix} 1, & h_{i j} \neq 0 \\ 0, & h_{i j} = 0 \end{matrix} .

Then a K × K neighboring matrix N can be generated based on C, where

n_{i j} = {\begin{matrix} \max {c_{i k} c_{j k}, k = 1, \dots, N}, & i \neq j \\ 0, & i = j \end{matrix} .

Note that, if n_ij = 1, users i and j can both receive signals from a common AP. Because each AP is assumed to serve only one user in a time slot, at least one of users i and j will suffer from interference if they are both active. Therefore, the neighboring matrix N manifests the conflicts among users.

To avoid the degradation of performance caused by inter-user interference and also to simplify implementation at the receivers, we restrict that interference should be avoided by the time and space scheduling process. The problem formulation Eqs. (15)–(17) can then be written as

\max \sum_{i = 1}^{K} \begin{matrix} 1 \\ \bar{\bar{r_{i, k}}} \end{matrix} \log_{2} (1 + \frac{{(\begin{matrix} \sum \\ {AP}_{j} \in {V ℂ}_{i} \end{matrix} h_{i j} P_{o t} R)}^{2}}{σ^{2}})

s . t . I_{i} = 0

{V ℂ}_{i} \cap {V ℂ}_{j} = ϕ, i, j = 1, \dots, K, i \neq j

\cup_{i = 1}^{K} {V ℂ}_{i} \subset A .

The constraint Eq. (22) indicates that when a user is scheduled, all APs within its receiving range will form up its virtual cell. At each time slot, the scheduling process is to pick up active users without conflict and assign APs to them. We will show in the next section that the problem of Eqs. (21)–(24) can be intuitively mapped onto the graph model.

3. Problem solutions

In this section we investigate the problems raised in Section 2. Since the global optimal solutions of the discreet optimization problem Eqs. (21)–(24) is still difficult to acquire, we are more interested in fast and efficient methods to obtain good results. In the following subsections we show how to build a graph model to analyze the inter-user interference, and pick active users while avoiding interference.

3.1. Graph model

Because of the close relation between channel conditions and positions of users and APs, it is natural to use topological methods to model the scenario. A conflict graph was proposed to model the interference in wireless communication systems [23, 24], and was used in [12] to describe the effects of interference in a VLC system. However, in our scenario the number of links need to be considered in the conflict graph is very large, which makes it unsuitable to use due to high complexity. Therefore, we introduce a new graph model to describe the inter-user interference, and to help us solve the problems.

Let us define some notations. G(V,E) is a graph with vertex set V(G) and edge set E(G). We use v_i to denote a vertex in V(G) and N(v_i) to denote neighboring vertices of v_i. d(v_i) is the degree of v_i, which is equal to the number of vertices in N(v_i). We use G⁽^w⁾(V,E) to represent a weighted graph.

For any layout of APs and users, we can generate a corresponding undirected graph G(V,E) called the interference graph. The vertices set V(G) of the graph is the user set U. The edge set E(G) is decided by the neighboring matrix N. If n_{i j} = 1, there is an edge between vertex i and j. Otherwise the two vertices are not connected. The existence of an edge means the existence of potential interference.

To demonstrate the graph model more clearly, we project the APs and receivers onto the horizontal plane. Their positions are shown in Fig. 2(a), where the APs are represented by ’○’ and the receivers are represented by ’★’. We use dashed lines to represent potential links (corresponding to c_ij = 1) between the APs and receivers. Figure 2(b) is the interference graph generated from Fig. 2(a).

Fig. 2 (a) Layout of APs and receivers projected on horizontal plane. (b) The corresponding interference graph and one of its MIS.

Download Full Size | PDF

As the solution to the scheduling problem, the scheduled users should maximize Eq. (21) and generate no interference to each other. To deal with it, we upgrade the interference graph G(V,E) into a weighted graph G⁽^w⁾(V,E) by assigning a weight to each vertex. The weight of v_i is set according to Eq. (14), which also corresponds to proportional fairness scheduling. PFS utilizes the current achievable rate of each user against past average throughput to calculate priority. At time slot k, the user scheduled has the maximum priority factor p_i,k, which is given by

p_{i, k} = \begin{matrix} \underline{r_{i, k}} \\ \bar{r_{i, k}} \end{matrix} .

Here $\bar{r_{i, k}}$ is the average throughput of user i over a past time of length T_C, and is refreshed by

\bar{r_{i, k}} = {\begin{matrix} (1 - \frac{1}{T_{C}}) \bar{r_{i, k - 1}} + \frac{1}{T_{C}} r_{i, k - 1}, & i_{k - 1}^{*} = i \\ (1 - \frac{1}{T_{C}}) \bar{r_{i, k - 1}}, & i_{k - 1}^{*} \neq i \end{matrix},

where

i_{k - 1}^{*}

is the user scheduled at time slot k − 1. T_C determines the tradeoff between throughput and fairness. In our scenario, multiple users can be scheduled in the same time slot, and

\bar{r_{i, k}}

is refreshed based on whether u_i is scheduled in the last time slot. The priority factor p_i,k is used as the weight for v_i at time slot k.

Though PFS can achieve a certain degree of fairness, latency is also an important factor to be considered in scheduling. Thus proportional fairness scheduling with the exponential rule was developed [25]. Define D_i,k as the latency of user i at time slot k, $\bar{{D^{'}}_{i, k}}$ as the average latency of all other users, which is calculated as

\bar{{D^{'}}_{i, k}} = \frac{1}{K - 1} \sum_{j = 1, j \neq i}^{K} D_{j, k} .

The priority factor of PFS with the exponential rule is given by

p_{i, k} = {(\begin{matrix} \underline{r_{i, k}} \\ \bar{r_{i, k}} \end{matrix})}^{s} \exp (\frac{D_{i, k} - \bar{{D^{'}}_{i, k}}}{1 + \sqrt{\bar{{D^{'}}_{i, k}}}}) .

The exponential term is used to reduce user latencies, with the parameter s providing a tradeoff between throughput and latencies.

The scheduling problem can now be transformed into another problem in the weighted interference graph: find a set of vertices with the maximum sum weight and ensure that no edge exists between any two of them. This is actually a maximum weighted independent set problem (MWISP). The relevant definitions are shown as follows:

Independent Set

An independent set is a subset of vertices in a graph. Any two vertices in the independent set are not connected by an edge.

Maximal Independent Set (MIS)

An independent set is maximal when adding any other vertex will make it no longer an independent set.

Maximum Independent Set (MaxIS)

Among all MIS of a graph, any set with most vertices is a maximum independent set. In Fig. 2(b), a MaxIS of this graph is shown with its vertices circled.

Maximum Weighted Independent Set (MWIS)

A maximum weighted independent set is the independent set of a weighted graph with largest sum weight.

Therefore, the problem is to find the MWIS of the interference graph. However, the MWISP is NP-complete thus cannot be solved within acceptable running time. Greedy algorithm is one of the simple and efficient heuristic algorithms for MWISP [26]. Two commonly used greedy algorithms in the Maximum Independent Set Problem (MISP) are called MIN and MAX respectively. It was proved that the MIN algorithm has a better performance than MAX [26], so we adopt the MIN algorithm in this paper. Based on the MIN algorithm, a GWMIN algorithm was proposed [27] to deal with MWISP. In the next subsection, we devise our scheduling algorithm based on GWMIN.

3.2. Scheduling algorithm

As a greedy algorithm, the basic idea of the MIN algorithm is that, a vertex with higher degree has more neighboring vertices, which makes it less likely to be in a maximum independent set. When using the MIN algorithm, each time we add the vertex with minimum degree into the MIS, then remove it along with its neighboring vertices from the whole vertex set. After that we update the remaining graph and repeat this process until no vertex remains. As for the GWMIN algorithm, the weights of vertices are taken into consideration. Its procedure is described in Algorithm 1.

Algorithm 1. GWMIN algorithm

View Table | View all tables in this article

Once the MWIS has been generated, the active users are decided. For each active user, all APs within its receiving range (with c_ij ≠ 0) will form a virtual cell that broadcasts identical signals. Moreover, to fully utilize the AP resources, we check that if there are any remaining idle APs whose signals can only be received by one single user. Since they are not able to cause interference to the picked users, we allocate them to their sole user in range. This can increase the throughput of some idle users (who are not chosen into the MWIS by Algorithm 1). For instance, in Fig. 2, assuming that u₁, u₃, u₄ and u₇ are chosen by Algorithm 1 (as they are circled as a MIS of the interference graph). Their neighboring APs are assigned to form virtual cells of each user. While keeping the assignment of these APs unchanged, the other users, if become active, will suffer from interference. Nevertheless, some of the unpicked users still have chance to gain some throughtput. Take u₁₀ as an example. Though the AP to its upper-right is assigned to u₃ and will cause interference, the other two APs to its left can be assigned to it without interfering with any other users. In this way, if we utilize these idle APs, more users can be served simultaneously while not causing degradation to the throughput of the picked users in the MWIS. To summarize, the steps of the scheduling performed by the central station at every time slot are provided in Algorithm 2.

Algorithm 2. Scheduling algorithm

View Table | View all tables in this article

With the scheduling algorithm, the central station picks active users at each time slot. Since we have introduced proportional fairness into the scheduling, users in conflict are multiplexed with time-division multiplexing (TDM), which can be easily realized in practice.

4. Numerical results

In this section, we provide some numerical results to demonstrate our algorithms proposed in Section 3. We consider two different LED arrangements where APs are installed regularly and irregularly, respectively. The specific parameters used in the simulation are listed in Table 1.

Table 1. Parameters used in the simulation

View Table | View all tables in this article

In practice, LEDs are often regularly installed. Therefore, in the first LED arrangement, we consider a square area with 8 × 8 APs installed equidistantly and d = 2m. The vertical view of the layout is shown in Fig. 3(a). Assuming all APs transmit identical signals and the receivers have a FOV of 50 degrees, the distribution of receiving SNR is shown in Fig. 3(b). Though SNR is high enough for high-rate communications, there exists large SNR fluctuation throughout the area. The edge area, especially the corners, is covered by less APs, so SNR at these locations is much lower. Specifically, the SNR fluctuation in the whole area is 14.12dB. While the SNR fluctuation in the central 12m×12m area is only 2.24dB, in the following simulations a certain number of users are randomly placed in the whole area. The simulation results are averaged over 5000 independent tests. We set the time parameter in PFS T_C = 25, and each test runs for 50 consecutive time slots. The sum capacity in one time slot is calculated by

s u m_c a p a c i t y = \sum_{i = 1}^{K} \log_{2} (1 + \frac{{(\begin{matrix} \sum \\ {AP}_{j} \in {V ℂ}_{i} \end{matrix} h_{i j} P_{o t} R)}^{2}}{σ^{2} + I_{i}}),

where I_i is calculated according to Eq. (18). I_i is included in Eq. (29) because additional users under interference are picked and served according to Step 3 of Algorithm 2. We also use service fairness index (SFI) [28] to indicate the degree of fairness, which is defined as

S F I = \max_{i, j} | \bar{r_{i}} - \bar{r_{j}} | / (\frac{1}{k} \sum_{l = 1}^{K} \bar{r_{l}})

where

\bar{r_{i}}

is the average throughput of u_i. Apparently lower SFI means better fairness. If SFI = 0, the absolute fairness is achieved.

Fig. 3 (a) Vertical view of APs layout. (b) Receiving SNR in the area.

Download Full Size | PDF

First we compare the performance of our proposed scheme with two existing scheduling schemes. In the first scheme, each AP is allocated to the user with the highest channel gain. The second scheme is from [12], where the conflict graph model is used to choose as many links as possible without interference. Actually, this is also a MISP but was not specifically pointed out in [12]. We still use the MIN algorithm in this scheme. The simulation results are depicted in Fig. 4(a) and Fig. 4(b).

Fig. 4 (a) Sum capacity by using different schemes. (b) SFI by using different schemes.

Download Full Size | PDF

Figure 4(a) shows the sum capacity of all users. In the first scheme, the users suffer from interference from each other. In the second scheme, the conflict graph model avoids interference but loses the advantage of transmitting diversity because all links are processed independently. Thus the second scheme has no significant improvement on the sum capacity. In contrast, our scheme avoids interference and forms virtual cells around users. It fully utilizes the available resources and leads to a higher sum capacity. Moreover, as shown in Fig. 4(b), by employing PFS, the SFI of our scheme is much lower than those of the other two schemes, indicating that better fairness is achieved.

For the aspects of complexity, we compare our proposed scheduling scheme with other existing works from two perspectives: hardware complexity and computing complexity.

Hardware complexity: in our work, we avoid inter-user interference by time and space scheduling. Compared with the existing works [9–11, 13], our scheme has no assumption on the form of modulation or multiple access techniques such as orthogonal frequency division multiple access (OFDMA) or code division multiple access (CDMA). Furthermore, compared with [12], our work does not require real-time adjustments of the position, angle, or any other mechanical structures of lighting apparatuses. These advantages lead to low hardware complexity and make our scheme easy to implement.

Computing complexity: on the computing complexity of our scheme over the existing works, we mainly consider the scheme proposed in [12], since [12] studied the multi-transmitter multi-receiver VLC and also employed the graph theocratical approach. [12] utilized the conflict graph model, whose scale in the multiuser VLC scenarios is much larger than the interference graph we proposed. Specifically, Algorithm 1 (GWMIN algorithm) has a complexity of O(n²) [29], where n is the number of vertices in the graph. Thus, the complexity of our scheme based on interference graph is O(K²), while the complexity of the scheme based on conflict graph in [12] is O((KN)²). Considering N is much bigger than K in most cases, our scheme can significantly reduce the computing complexity.

Next we illustrate the effects of FOV on the performance of our scheduling algorithm. Figure 5(a) shows the sum capacity when up to 16 users are present. With more users, higher sum rates can be achieved. Meanwhile the sum capacity is also affected by FOV. A large FOV enables the receiver to collect signals from more APs, but also brings more potential interference. As a consequence, a larger FOV will result in less active users to be chosen in the MWIS, as we show in Fig. 5(b). Thus the sum capacity decreases when the FOV is too large. On the other hand, although a smaller FOV may lead to less interference, the strength of the received optical signals becomes weaker. If the FOV is too small, the receivers in some positions might have no chance to access APs. Thus, with the decrease of FOV, the number of the active users also decrease, which leads to lower sum capacity as well. Figure 5(c) shows SFI with different FOV. Generally better fairness is achieved when more users are simultaneously active.

Fig. 5 (a) Sum capacity with different FOV. (b) Average active user number with different FOV. (c) SFI with different FOV.

Download Full Size | PDF

The above results indicate that scheduling is greatly affected by FOV, which in fact decides the amount of potential interference. This result confirms that inter-user interference constitutes the major factor limiting the system performance. The optimal value of FOV is manipulated by the parameters of system layout. The simulation results show that the optimal value is near $\tan^{-}^{1} (\frac{\sqrt{2} d}{2 h})$ , which corresponds to the minimum FOV required by the receiver to guarantee access to the APs. In the scenario we considered, the optimal value of FOV is around 35 degrees, at which the higher sum capacity and better fairness are achieved.

We also examine whether the PFS priority factor p_i,k with the exponential rule can reduce the latency effectively in our scenario. In this test p_i,k is calculated in three different forms: the original form in Eq. (25), the modified form with exponential rule in Eq. (28) and s = 1, and the similar modified form with s = 2. We set the FOV of receivers to be 35 degrees, which is near the optimal value in this scenario. In Fig. 6 we evaluate the sum capacity, SFI and average latencies respectively. It shows that PFS with exponential rule slightly reduces average latencies, while at the same time bringing little degradation to the sum capacity and SFI. All three forms show similar throughput and fairness performance. This means that in multiuser VLC systems it is not beneficial to use p_i,k with the exponential rule owing to its extra computing complexity. Furthermore, it also confirms that our scheduling scheme achieves high multiplexing ratio in multiuser VLC scenarios since the average latencies are already small and can hardly be further reduced with the exponential rule.

Fig. 6 (a) Sum capacity with different priority factors. (b) SFI with different priority factors. (c) Average latencies with different priority factors.

Download Full Size | PDF

It is also worth noting that if we set α = 1 in Eq. (13), it becomes

\max \sum_{i = 1}^{K} r_{i, k},

i.e., maximizing the sum rate. It can be treated as a special case of Eq. (14), by replacing

\begin{matrix} \underline{r_{i, k}} \\ \bar{r_{i, k}} \end{matrix}

with r_i,k. Still, the GWMIN algorithm is employed as a heuristic algorithm to obtain suboptimal solutions. In Fig. 7 we illustrate the comparison of the sum capacity and SFI between maximum throughput scheduling and PFS, where the FOV is set to be 35 and 50 degrees, respectively. The simulation result indicates that PFS only slightly degrades the throughput performance while achieving much better fairness.

Fig. 7 (a) Sum capacity of maximum throughput scheduling and PFS. (b) SFI of maximum throughput scheduling and PFS.

Download Full Size | PDF

We would like to emphasize that our proposed scheduling scheme can be applied to arbitrary topologies. To show this, we consider an irregular LED arrangement provided by [30] to reduce SNR fluctuation. In this arrangement, LEDs are divided into circled-LEDs and cornered LEDs. The vertical view of the LED arrangement is illustrated in Fig. 8(a) for a 5m×5m area with h = 2.2m. By applying the approach presented in [30], one can find when the radius of the LEDs-circle is 2.01m and the distance between the cornered-LEDs and their nearest wall is 0.0796m, the minimum SNR fluctuation is achieved. The power of each circled-LED and cornered-LED is 34.45W and 72.5W, respectively. The acquired SNR fluctuation is 2.63dB (the SNR distribution is shown in Fig. 8(b)), which is significantly lower than that in the previous scenario. Again we compare the performance of our proposed scheme with the other two schemes mentioned earlier. The simulation results are depicted in Fig. 9(a) and Fig. 9(b).

Fig. 8 (a) Vertical view of the second LED arrangement. (b) The corresponding SNR distribution.

Download Full Size | PDF

Fig. 9 (a) Sum capacity with different schemes under the second LED arrangement. (b) SFI with different schemes under the second LED arrangement.

Download Full Size | PDF

Similar to the results in the first LED arrangement, our proposed scheme performs better than the other two scheduling schemes. Higher sum rates and better fairness are achieved in this irregular LED arrangement. Moreover, the advantages of our scheme is more obvious with more users, which confirms its benefits in multiuser scenarios. With these numerical results, we would like to demonstrate that the application of our scheme is not limited by the layout of the VLC systems. Our scheduling algorithm is applicable to arbitrary topologies with not only regular but also irregular LED arrangements.

5. Conclusion

In this paper, we have studied the scheduling problem for indoor visible light communication systems. We established a novel interference graph model to analyze inter-user interference. The problem was then transformed into a MWISP in the graph theory. With the proportional fairness scheduling, a greedy GWMIN algorithm was utilized to solve the MWISP. Multiple users were time-division multiplexed with high multiplexing ratio. The simulation results show that higher sum capacity and better fairness can be achieved compared with the existing works. Our algorithm achieves good performance with low hardware and computing complexity.

Acknowledgments

This work is supported by 973 Program (2013CB329204 and 2013CB336600), National Natural Science Foundation of China ( 61201174), Natural Science Foundation of Jiangsu Province ( BK2012325), the Fundamental Research Funds for the Central Universities, and Major Program of National Natural Science Foundation of China ( 61223001). The authors acknowledge research support from the Jiangsu Talent Introduction Project and Jiangsu Creativity Promotion Program.

References and links

1. J. Vučić, C. Kottke, S. Nerreter, K.-D. Langer, and J. W. Walewski, “513 Mbit/s Visible Light Communications Link Based on DMT-Modulation of a White LED,” J. Lightwave Technol. 28(24), 3512–3518 (2010).

2. J. F. Li, Z. T. Huang, R. Q. Zhang, F. X. Zeng, M. Jiang, and Y. F. Ji, “Superposed pulse amplitude modulation for visible light communication,” Opt. Express 21(25), 31006–31011 (2013). [CrossRef]

3. Y. Wang, Y. Wang, N. Chi, J. Yu, and H. Shang, “Demonstration of 575-Mb/s downlink and 225-Mb/s uplink bidirectional SCM-WDM visible light communication using RGB LED and phosphor-based LED,” Opt. Express 21(1), 1203–1208 (2013). [CrossRef] [PubMed]

4. A. H. Azhar, T.-A. Tran, and D. O’Brien, “A Gigabit/s Indoor Wireless Transmission Using MIMO-OFDM Visible-Light Communications,” IEEE Photonics Technol. Lett. , 25(2), 171–174 (2013). [CrossRef]

5. C. Kottke, J. Hilt, K. Habel, J. Vučić, and K.-D. Langer, “1.25 Gbit/s visible light WDM link based on DMT modulation of a single RGB LED luminary,” in European Conference and Exhibition on Optical Communication (Optical Society of America, 2012), paper We.3.B.4. [CrossRef]

6. S. Zhang, S. Watson, J. J. McKendry, D. Massoubre, A. Cogman, E. Gu, R. K. Henderson, A. E. Kelly, and M. D. Dawson, “1.5 Gbit/s Multi-Channel Visible Light Communications Using CMOS-Controlled GaN-Based LEDs,” J. Lightwave Technol. 31(5), 1211–1216 (2013).

7. Y. Wang, N. Chi, Y. Wang, R. Li, X. Huang, C. Yang, and Z. Zhang, “High-speed quasi-balanced detection OFDM in visible light communication,” Opt. Express 21(23), 27558–27564 (2013). [CrossRef]

8. G. Cossu, A. Khalid, P. Choudhury, R. Corsini, and E. Ciaramella, “3.4 Gbit/s visible optical wireless transmission based on RGB LED,” Opt. Express 20(26), B501–B506 (2012). [CrossRef] [PubMed]

9. R. K. Mondal, M. Z. Chowdhury, N. Saha, and Y. M. Jang, “Interference-aware Optical Resource Allocation in Visible Light Communication,” in Proc. 2012 International Conference on ICT Convergence (ICTC) (IEEE, 2012), pp. 155–158.

10. R. K. Mondal, N. Saha, and Y. M. Jang, “Joint Scheduling and Rate Allocation for IEEE 802.15.7 WPAN System,” in Ubiquitous and Future Networks (ICUFN) (IEEE, 2013), pp. 691–695.

11. S.-H. Yang, H.-S. Kim, Y.-H. Son, and S.-K. Han, “Reduction of optical interference by wavelength filtering in RGB-LED based indoor VLC system,” in OptoeElectronics and Communications Conference (OECC) (2011), pp. 551–552.

12. Y. Li, L. Wang, J. Ning, K. Pelechrinis, S. V. Krishnamurthy, and Z. Xu, “VICO: A framework for configuring indoor visible light communication networks,” in Mobile Adhoc and Sensor Systems (MASS) (IEEE, 2012), pp. 136–144.

13. D. Bykhovsky and S. Arnon, “Multiple access resource allocation in visible light communication systems,” J. Lightwave Technol. 32(8), 1594–1600 (2014). [CrossRef]

14. J. R. Barry, J. M. Kahn, W. J. Krause, E. A. Lee, and D. G. Messerschmitt, “Simulation of multipath impulse response for indoor wireless optical channels,” IEEE J. Sel. Areas Commun. 11(3), 367–379 (1993). [CrossRef]

15. J. M. Kahn and J. R. Barry, “Wireless infrared communications,” Proc. IEEE 85(2), 265–298 (1997). [CrossRef]

16. T. Komine and M. Nakagawa, “Fundamental analysis for visible-light communication system using LED lights,” IEEE Trans. Consum. Electron. 50(1), 100–107 (2004). [CrossRef]

17. L. Dai, S. Zhou, and Y. Yao, “Capacity analysis in CDMA distributed antenna systems,” IEEE Trans”, Wireless Commun. 4(6), 2613–2620 (2005). [CrossRef]

18. T. Jiang, L. Song, and Y. Zhang, Orthogonal Frequency Division Multiple Access Fundamentals and Applications (Auerbach Publications, 2010).

19. R. Agrawal, A. Bedekar, R. La, and V. Subramanian, “Class and Channel Condition Based Weighted Proportional Fair Scheduler” in,” Proceedings of the International Teletraffic Congress (ITC) (2001) 17, pp. 553–565.

20. J. Mo and J. Walrand, “Fair end-to-end window-based congestion control,” IEEE/ACM Trans”, Networking 8(5), 556–567 (2000). [CrossRef]

21. T. Girici, C. Zhu, J. R. Agre, and A. Ephremides, “Proportional fair scheduling algorithm in OFDMA-based wireless systems with QoS constraints,” J. Commun. Networks 12(1), 30–42 (2010). [CrossRef]

22. L.-H. Azizan, M.S. Ab-Rahman, and K. Jumiran, “Analytical approach on SNR performance of visible light communication for modern lighting layout,” in,” Innovation Management and Technology Research (ICIMTR) (2012), pp. 332–336.

23. K. Jain, J. Padhye, V. N. Padmanabhan, and L. Qiu, “Impact of Interference on Multi-hop Wireless Network Performance,” Wireless Networks 11(4), 471–487 (2005). [CrossRef]

24. E. Gelal, K. Pelechrinis, T.-S. Kim, I. Broustis, S. V. Krishnamurthy, and B. Rao, “Topology Control for Effective Interference Cancellation in Multi-User MIMO Networks,” in Proc. IEEE INFOCOM (2010).

25. M. O. Sunay and A. Eksim, “Wireless multicast with multi-user diversity,” in Vehicular Technology Conference (VTC) (2004) 3, pp. 1584–1588.

26. M. M. Halldórsson and J. Radhakrishnan, “Greed is Good: Approximating Independent Sets in Sparse and Bounded-Degree Graphs,” Algorithmica 18(1), 145–163 (1997). [CrossRef]

27. S. Sakai, M. Togasaki, and K. Yamazaki, “A note on greedy algorithms for the maximum weighted independent set problem,” Discrete Appl. Math. 126, (2)313–322 (2003). [CrossRef]

28. B. Bensaou, D. H. Tsang, and K. T. Chan, “Credit-based fair queueing (CBFQ): a simple service-scheduling algorithm for packet-switched networks,” IEEE/ACM Trans. Networking 9, (5)591–604 (2001). [CrossRef]

29. H. A. Mara’beh and A. Suleiman, “Heuristic Algorithm for Graph Coloring Based on Maximum Independent Set,” Journal of Applied Computer Science & Mathematics (13), pp. 6 (2012).

30. Z. Wang, C. Yu, W.-D. Zhong, J. Chen, and W. Chen, “Performance of a novel LED lamp arrangement to reduce SNR fluctuation for multi-user visible light communication systems,” Opt. Express 20(4), 4564–4573 (2012). [CrossRef] [PubMed]

1:	Update the weighted interference graph G^(w)(V,E) according to the channel information matrix.
2:	Use the GWMIN algorithm to decide the active users in this time slot.
3:	Check if any remaining idle APs can be utilized.

Parameter	Value	Parameter	Value
h	2.2[m]	P_ot	4.25×25[W]
A	0.785[mm²]	T_K	300[K]
$ϕ_{\frac{1}{2}}$	70[deg.]	η_C	1.12 × 10⁻⁶[F/m²]
R	0.54[A/W]	G	10
$I_{b_{g}}$	5.1×10⁻³[A]	Γ	1.5
I₂	0.562	I₃	0.0868
B	100[MHz]	g_m	0.03[S]

1:	Update the weighted interference graph G^(w)(V,E) according to the channel information matrix.
2:	Use the GWMIN algorithm to decide the active users in this time slot.
3:	Check if any remaining idle APs can be utilized.

Parameter	Value	Parameter	Value
h	2.2[m]	P_ot	4.25×25[W]
A	0.785[mm²]	T_K	300[K]
$ϕ_{\frac{1}{2}}$	70[deg.]	η_C	1.12 × 10⁻⁶[F/m²]
R	0.54[A/W]	G	10
$I_{b_{g}}$	5.1×10⁻³[A]	Γ	1.5
I₂	0.562	I₃	0.0868
B	100[MHz]	g_m	0.03[S]

Scheduling for indoor visible light communication based on graph theory

Abstract

1. Introduction

2. System model and problem formulation

2.1. System model

2.2. Problem formulation

3. Problem solutions

3.1. Graph model

Independent Set

Maximal Independent Set (MIS)

Maximum Independent Set (MaxIS)

Maximum Weighted Independent Set (MWIS)

3.2. Scheduling algorithm

4. Numerical results

5. Conclusion

Acknowledgments

References and links

Cited By

Figures (9)

Tables (3)

Equations (31)

Optics Express