Hybrid Polling Method for Direct Link Communication for IEEE 802.11 Wireless LANs

The direct link communication between STAtions (STAs) is one of the techniques to improve the MAC performance of IEEE 802.11 infrastructure networks. For the efficient direct link communication, in the literature, the simultaneous polling method was proposed to allow the multiple direct data communication to be performed simultaneously. However, the efficiency of the simultaneous polling method is affected by the interference condition. To alleviate the problem of the lower polling efficiency with the larger interference range, the hybrid polling method is proposed for the direct link communication between STAs in IEEE 802.11 infrastructure networks. By the proposed polling method, we can integrate the sequential and simultaneous polling methods properly according to the interference condition. Numerical examples are also presented to show the medium access control (MAC) performance improvement by the proposed polling method.


PCF protocol
The AP transmits the polling frames to grant the transmission opportunities to the STAs. After the beacon frame, the AP waits for one Short InterFrame Space (SIFS) period, and then transmits to an STA a polling frame on which a data frame destined for the STA can be piggybacked. The STA should respond to the polling frame by transmitting to the AP its data frame on which the ACK frame corresponding to the data frame transmitted by the AP can be piggybacked. After the reception of the data frame transmitted by the STA, the AP transmits to another STA a polling frame on which a data frame and the ACK frame corresponding to the previous data frame transmitted by the STA can be piggybacked. The STA responds to the polling frame by transmitting its data frame on which the ACK frame can be piggybacked. The STAs can respond to the polling frames by transmitting the null frames if the STAs do not have the data frames to transmit. If the STAs fail to respond to the polling frames within one SIFS period following the transmissions of the  Figure 1: Modified CFP structure in [7].
AP, for the error recovery, the AP transmits a polling frame to another STA after one PCF InterFrame Space (PIFS) period from the end of the previous transmission. In this manner, the process of the AP's polling and the STAs' responding continues until the contention-free period (CFP) ends.

CFP structure
According to the superframe structure in [1], a CFP during which the PCF polls the STAs to grant the transmission opportunities alternates with a contention period (CP) during which the DCF controls the data transfer. S will represent the set of the STAs to which the transmission opportunities should be granted during a CFP. To support the simultaneous polling method in [7], the original IEEE 802.11 CFP structure was modified so that each CFP is divided into the multiple subperiods (SPs), each of which is composed of a polling interval (PI) and a direct communication polling interval (DCPI) as shown in Figure 1.
In the PI, similarly to the PCF protocol, the AP grants the transmission opportunities to the STAs by transmitting the polling frames to the STAs in an order. In the DCPI, the direct link communication is actually performed using the simultaneous polling method. If one or more direct data transmission opportunities are actually granted in the DCPI, only one transmission opportunity is granted to each transmitting STA of the direct link communication and two transmission opportunities are granted each to the other STAs in the PI of the next SP. This is for providing a fair allocation of the wireless medium to the STAs.

Connectivity and interference information
The simultaneous polling method is based on the connectivity and interference information among the STAs. We want to explain briefly the method for the APs collecting the connectivity and interference information among the STAs in the PI. Each STA i maintains the sets, S i and T i which are the sets of STAs of which the transmission signal can be heard by STA i, and can interfere with the data reception of STA i, respectively. STA i can obtain the MAC address of STA j ( / =i) from the polling frame transmitted by the AP before the transmission of STA j. For this purpose, the polling frames should be received by the STAs. When STA i hears the transmission signal of other STA j not in S i , STA i adds STA j to S i . When STA i has not heard the transmission signal of other STA j in S i during recent three PIs, STA i deletes STA j from S i . In this manner, each STA can maintain the set, S i . STA i can also maintain the set, T i as follows. When STA i finds the reception power level of the transmission signal of Woo-Yong Choi 3 other STA j not in T i to be above that of the background noise, STA i adds STA j to T i . When STA i has not found the power level of the transmission signal of other STA j in T i to be above that of the background noise during recent three PIs, STA i deletes STA j from T i . Actually, each STA i can piggyback the MAC addresses of the STAs that are deleted from or added to S i and T i on the response null or data frames transmitted to the AP. Considering the case when transmission errors occur, we modified the method in [7] for the APs collecting the connectivity and interference information to wait for three PIs before deleting STA j from S i or T i .
With the asymmetric connectivity and interference condition, the AP needs two PIs to collect the connectivity and interference information among the STAs when no transmission error occurs. In order for STA i to obtain the connectivity and interference information between STA i and STA j ( / =i), the following two events should sequentially occur in a PI: (i) the polling frame destined for STA j is successfully received by STA i and STA j; (ii) the response frame transmitted by STA j is successfully received by STA i when STA i is within the transmission range of STA j. STA i can detect the interference by the reception power level of the response frame transmitted by STA j when STA i is within the interference range of STA j.
Denoting the probabilities that the two events occur in a PI by p 1 and p 2 , we can compute the probability that STA i can successfully obtain the connectivity and interference information between STA i and STA j within three PIs as P = 1−(1 − p 1 p 2 ) 3 . When the failure probabilities of the two events are less than or equal to 0.05, that is, p 1 and p 2 ≥ 0.95, P > 0.999, therefore, we can infer that it is quite reasonable to wait for three PIs before deleting STA j from S i or T i . In the PI, after the four-step process of establishing the direct link connection in [5], each STA can request at most one direct data transmission opportunity by piggybacking the MAC address of the recipient of the direct data transmission on the response null or data frames transmitted to the AP. Based on the connectivity information, the AP can determine whether the direct link connection can be established to serve the direct link communication. After the successful four-step connection establishment process, each STA can optionally transmit its data frame directly to the recipient by writing the MAC address of the recipient in the recipient address (RA) field of the MAC header of the data frame transmitted when it is granted the transmission opportunity in the PI. The constants, C i, j and I i, j for i and j ∈ S, and i / = j and d(i) for i ∈ S, which are collected in the PI to specify the connectivity and interference information, and the information of the STAs' requests for the direct link communication, respectively, are defined as follows: (iii) d(i): the MAC address of the recipient of the direct data transmission that STA i requested on a packet basis in the recent PI. If STA i did not request the direct data transmission, d(i) = 0.

Simultaneous polling method
The simultaneous polling method is the multipolling method that allows the AP to poll a group of The efficiency (or the number of simultaneous direct transmissions) of the simultaneous polling method depends on the interference range of STAs. In cases where the simultaneous polling method is not effective due to the large interference range, the simultaneous polling method needs to be enhanced to alleviate the problem of the lower polling efficiency with the larger interference range.

HYBRID POLLING METHOD
The real-time services such as VoIP do not usually require the ACK frame transmission. We assume that the ACK frame transmission can be omitted. When an STA, having one or more established direct link connections, malfunctions, is just switched off or moves out of the transmission range, without the ACK transmission, the AP can detect that the direct link connections are broken using the connectivity information that will be collected in the next PIs. With the proposed polling method that is used to grant the requested direct transmission opportunities to the STAs in the DCPI, the AP transmits a multipolling frame to the STAs in the sequence G S = {STA U 1 , STA U 2 , . . . , STA U M } and the group G P = {STA W 1 , STA W 2 , . . . , STA W N }. The STAs in the sequence G S transmit their frames sequentially after the multipolling frame is received. An SIFS period after receiving the multipolling frame, STA U 1 first attempts to transmit its frame. An SIFS period after sensing the end of the transmission of STA U 1 , STA U 2 attempts to transmit its frame. STA U 3 attempts to transmit its frame an SIFS period after sensing the end of the transmission of STA U 2 . In this manner, the STAs transmit their frames sequentially. An SIFS period after sensing the end of the transmission of STA U M , the STAs in the group G P transmit their frames  (1), the following connectivity condition should be satisfied for the proposed polling method: If an STA in G S fails to respond to the multipolling frame or the transmission of the previous STA in the sequence within an SIFS period following the transmission of the AP or the previous STA, for the error recovery the AP will transmit the multipolling frame to repoll the next STAs in the sequence G S and the group G P after a PIFS period, which is an SIFS period plus a slot time, from the end of the previous transmission. The format of the multipolling frame is shown in Figure 2.
In Figure 2, U 1 , U 2 , . . . , and U M indicate the MAC addresses of the STAs in the sequence G S , W 1 , W 2 , . . . , and W N the MAC addresses of the STAs in the group G P , and M and N are the numbers of the STAs in the sequence G S and the group G P , respectively. The other fields are from [1]. We can omit G S or G P . When G S (or G P ) is omitted in the multipolling frame, the simultaneous (or sequential) polling method is only specified.
When all direct data transmission opportunities are granted, the AP initiates the next PI by transmitting a polling frame to an STA an SIFS period after the response transmissions from the STAs are completed or can initiate the next PI after the wireless medium is determined to be idle during a PIFS period.

SCHEDULING ALGORITHMS
In this section, we propose two scheduling algorithms applicable to the hybrid polling method: the packet-level and the connection-level scheduling algorithms. By performing the packet-level scheduling algorithm at the beginning of DCPIs, the AP can schedule efficiently the direct data transmissions requested on a packet basis. The connectionlevel scheduling algorithm derives the polling sequence for granting the transmission opportunities to the transmitting STAs of all existing established direct link connections. When polling the STAs in DCPIs, by a simple method, the AP modifies the polling sequence derived by the connectionlevel scheduling algorithm considering the information of the STAs' requests for the direct link communication. The connection-level scheduling algorithm is suitable for the case when the AP cannot perform the packet-level scheduling algorithm quickly enough to reflect exactly the STAs' new requests for the direct link communication in the next DCPI. However, in the cases where the connectivity and interference information and the information of the STAs' requests for the direct link communication do not change for a period of time during which the AP can derive the polling sequence by the packet-level scheduling algorithm or a small number of STAs actually request the direct link communication, the packet-level scheduling algorithm should be applied for the efficient use of the wireless bandwidth. Note that when no STA requests the direct link communication, the next DCPI will be skipped.

Packet-level scheduling algorithm
In the DCPI, the AP needs to schedule efficiently the requested direct data transmissions based on the connectivity and interference information among the STAs and the information of the STAs' requests for the direct link communication. Let V be the set of STAs that requested the direct data transmissions, which are determined to be feasible using the connectivity information, in the recent PI. Then V can be obtained as follows: We propose a two-phase scheduling algorithm for granting the direct transmission opportunities to the STAs in V using the proposed polling method.
In the first phase of the algorithm, we handle the problem of grouping the STAs in V with as few groups as possible in such a way that no two STAs, i and j with I i,d( j) = 1 or I j,d(i) = 1, are in the same group. Note that the connectivity and interference conditions as shown in (1) are satisfied for each group. Therefore, the AP can grant the simultaneous direct transmission opportunities to the STAs in each group using the simultaneous polling method. This grouping problem can be formulated as graph coloring problem (GCP), where the STAs in V are vertices and two STAs, i and j in V , are connected only when I i,d( j) = 1 or I j,d(i) = 1. We can use the simple heuristic for GCP, which is based on the degree-descending order of the vertices [9, page 14]. The set of the groups obtained by the heuristic is denoted by [9, page 14]. We need L polling frame transmissions to poll the STAs in the groups in G using the simultaneous polling method. The first phase of the algorithm was considered in the simultaneous polling method in [7].
In the second phase of the algorithm, we try to further reduce the number of polling frame transmissions by applying the sequential polling method to the groups in G.
Woo-Yong Choi 5 The AP can poll the STAs in the groups in the sequence for i / = j by transmitting a multipolling frame, the format of which is as shown in Figure 2, to the STAs when only one STA exists in H(i) for i = 1, 2, . . . , K − 1, and the following connectivity condition is satisfied: where C H(i),H(i+1) = 1 indicates that the STAs in H(i + 1) can hear the transmission of the STA in H(i). We will call such a polling sequence satisfying the condition of (4) sequentially connected. For convenience of explanation, we will also call the sequence H having only one group sequentially connected. When some of the groups in G have only one STA, that is, the simultaneous polling method cannot be actually applied to some of the groups, we can further reduce the number of polling frame transmissions by finding the sequentially connected polling sequences and applying the proposed polling method to the sequentially connected polling sequences. The problem of finding the optimal polling sequence of the groups in G that minimizes the multipolling frame transmissions can be formulated as the asymmetric traveling salesman problem (TSP), where the groups in G are L cities, and the distance, Let us denote the sequence as a solution of the TSP by H * = {H * (1), H * (2), . . . , H * (L)}, and the corresponding total distance by Z * . If Z * = 0, that is, H * is sequentially connected, only one multipolling frame transmission is sufficient to grant the direct transmission opportunities to the STAs in the groups in G. If Z * = 1, we can cyclically reorder the groups in H * to obtain the sequentially connected polling sequence, H 1 , and only one multipolling frame transmission is sufficient to poll the STAs in the groups in G. If Z * = 2, we can cyclically reorder the groups in H * to obtain two sequentially connected polling sequences, H 1  To solve the asymmetric TSP, we can use the following dynamic search algorithm. = 1 μs)).

Algorithm 1 (DYNAMIC SEARCH (Time Limit
Step 1. Set Bounding Cost = R (the number of the groups having two or more STAs in G).
Step 2. Start to search the enumeration tree with Bounding Cost.
Step 3. If a solution with the cost less than or equal to Bounding Cost is found using the branch and bound technique based on the depth-first search method within Time Limit, the solution is the result of the algorithm and the algorithm is terminated. Otherwise, update Bounding Cost : Bounding Cost ← Bounding Cost + 1, and go to Step 2.
When R is the number of the groups having two or more STAs in G, at least R multipolling frame transmissions are needed to poll the STAs in the groups in G. The preceding algorithm first tries to obtain the solution with Z * = R. If the algorithm does not succeed to get the solution within time of Time Limit, the algorithm relaxes the constraint for the cost of the solution by increasing Bounding Cost by 1 and tries to get the solution with Z * = R + 1. If the algorithm fails again, the algorithm again increases Bounding Cost by 1 and tries to get the solution with Z * = R + 2. In this manner, the algorithm continues until the solution with Z * = Bounding Cost is obtained. By the branch and bound techniques, if a part of tour has a cost higher than or equal to the current optimal cost or higher than Bounding Cost, all tours including this part of tour are skipped.

Connection-level scheduling algorithm
Let Y be the set of existing simplex direct link connections. A duplex connection can be realized by two simplex connections. We propose a two-phase scheduling algorithm for granting the direct transmission opportunities to the transmitting STAs of the direct link connections in Y . We will denote the transmitting and receiving STAs of direct link connection, q in Y by T(q) and R(q), respectively.
In the first phase of the algorithm, we handle the problem of grouping the connections in Y with as few groups as possible in such a way that no two connections, q1 and q2 with I T(q1),R(q2) = 1 or I T(q2),R(q1) = 1, are in the same group. This grouping problem can be also formulated as GCP, where the connections in Y are vertices and two connections, q1 and q2 in Y , are connected only when I T(q1),R(q2) = 1 or I T(q2),R(q1) = 1. We can use the simple heuristic for GCP, which is based on the degree-descending order of the vertices [9, page 14]. The simultaneous polling method can be actually applied to the groups with two or more connections [9, page 14]. We will call such groups with two or more connections and the groups with only one connection the simultaneous polling groups and the nonsimultaneous polling groups, respectively.
Generally, a transmitting STA can have two or more established direct link connections. However, we want to grant at most one direct transmission opportunity to each STA. For this purpose, when a nonsimultaneous polling group obtained by the heuristic consists of a connection with a transmitting STA, we need to remove the other connections with the transmitting STA from other groups before we go to the second phase of the algorithm. Generally, 6 EURASIP Journal on Wireless Communications and Networking we can say that the connections with a transmitting STA cannot be in the same simultaneous polling group due to the interference. Actually, we want to avoid the case that two or more connections with a transmitting STA are separately in the nonsimultaneous polling groups, and the case that two or more connections with a transmitting STA are scattered in both the simultaneous and nonsimultaneous polling groups. Note that we allow the case that two or more connections with a transmitting STA are individually in the different simultaneous polling groups. When two or more connections with a transmitting STA are individually in the different simultaneous polling groups, the STA should choose only one connection to transmit its direct data frame when polled by the AP. The set of the groups obtained by the first phase of the algorithm is denoted by G C = {G C (1), G C (2), . . . , G C (L C )} for L C ≥ 1. We need L C polling frame transmissions to poll the transmitting STAs of the connections in the groups in G C using the simultaneous polling method.
In the second phase of the algorithm, we try to further reduce the number of polling frame transmissions by applying the sequential polling method to the groups in G C . The AP can poll the transmitting STAs of the connections in the groups in the sequence by transmitting a multipolling frame, the format of which is as shown in Figure 2, to the STAs when only one connection exists in H C (i) for i = 1, 2, . . . , K C − 1, and the following connectivity condition is satisfied: C T(HC(i)),T(HC(i+1)) = 1 for i = 1, 2, . . . , K C − 1, (6) where C T(HC(i)),T(HC(i+1)) = 1 indicates that the transmitting STAs of the connections in H C (i + 1) can hear the transmission of the transmitting STA of the connection in H C (i). We will call such a polling sequence satisfying the condition of (6) sequentially connected.
When some of the groups in G C have only one connection, that is, the simultaneous polling method cannot be actually applied to some of the groups, we can further reduce the number of polling frame transmissions by finding the sequentially connected polling sequences and applying the proposed polling method to the sequentially connected polling sequences. The problem of finding the optimal polling sequence of the groups in G C that minimizes the multipolling frame transmissions can be also formulated as the asymmetric TSP, where the groups in G C are L cities, and the distance, D GC(i),GC( j) from G C (i) to G C (i), is binary valued: Let us denote the sequence as a solution of the TSP by H C * = {H C * (1), H C * (2), . . . , H C * (L C )}, and the corresponding total distance by Z C * . If Z C * = 0, that is, H C * is sequentially connected, only one multipolling frame transmission is sufficient to grant the direct transmission opportunities to the transmitting STAs of the connections in the groups in G C . If Z C * > 0, we can cyclically reorder H C * to obtain Z C * sequentially connected polling sequences, H C 1 , H C 2 , . . . , and H C Z * , and Z C * multipolling frame transmissions are sufficient to grant the direct transmission opportunities to the transmitting STAs of the connections in the groups in G C . To solve the asymmetric TSP, we can employ a dynamic search algorithm similar to the one of the packet-level scheduling algorithm with Time Limit of 10 seconds.
When a group in H C * consists of a single connection, the transmitting STA of the connection can transmit its direct data frame to any receiving STA of the established direct link connections in its transmission range when polled by the AP. When the transmitting STA of the connection has no direct data frame to transmit, the STA should use the granted transmission opportunity to transmit its null or data frame to the AP when polled by the AP. The AP can optionally modify the derived polling sequence to insert the AP's polling frame transmissions before the transmissions of the nonsimultaneous polling groups when the AP has the data frames, which are actually piggybacked on the polling frames, destined for the nonsimultaneous polling groups. When no direct link communication through the connections in a simultaneous polling group in H C * was requested, the AP will modify the derived polling sequence to remove the group from the polling sequence that is actually delivered to the STAs. This is for avoiding wasting the wireless bandwidth. When all connections with a transmitting STA are separately in the different simultaneous polling groups, the STA can choose only one connection to transmit its direct data frame when polled by the AP. Note that the first phase of the algorithm avoided the case that two or more connections with a transmitting STA are separately in the nonsimultaneous polling groups, and the case that two or more connections with a transmitting STA are scattered in both the simultaneous and nonsimultaneous polling groups.

SIMULATION RESULTS
To show the MAC performance improvement by the proposed hybrid polling method, for each number of STAs, |S| = 20, 30, and 40, we generated ten IEEE 802.11a wireless LANs, where the APs are located at the centers of the circular service areas, and twenty, thirty, or forty STAs are randomly located in the service areas, including the one consisting of one AP and thirty STAs in Figure 3. Each wireless LAN serves one or more simultaneous full-duplex VoIP traffic streams between STA i and STA |S| − i + 1. B will denote the number of simultaneous full-duplex VoIP traffic streams between two STAs of each pair. The STAs perform a good uplink power control in PIs so that the null or data frames transmitted by each STA can be received by the STAs including the AP in the circular transmission range with the radius r of the distance between the STA and the AP, and the STAs out of the transmission range cannot hear the transmission signal of the STA.
In Figure 3, the eleven STAs indicated by the shaded circles can transmit the VoIP traffic streams directly to their  From the uplink power control, we can obtain the connectivity information among the STAs. The transmission and interference ranges are mainly determined by transmission power, radio propagation properties, and signal-to-noise ratio (SNR) threshold. In practice, the interference range is larger than the transmission range. We consider five cases of the interference range with the radius R in each wireless LAN [10]. The connectivity information remains the same in all five cases. In the first case, R = r, that is, the interference ranges are set to the same as the transmission ranges. R is set to 1.3 r, 1.5 r, and 1.8 r in the second, third, and fourth cases, respectively. According to [10], the corresponding SNR threshold values of the second, third, and fourth cases are approximately 2.9, 5.1, and 10.5, respectively. Finally, the interference ranges are set to be large enough for the data transmission of each STA to interfere with the data receptions of all other STAs in the last case.
For convenience of simulation analysis, we assume that the connectivity and interference information do not change over time. When the connectivity and interference information change, only the change of the connectivity and interference information is actually delivered to the AP. For example, if five MAC addresses per second, which are actually piggybacked on the response null or data frames transmitted to the AP, need to be delivered to report the change of the connectivity and interference information among the STAs, only the data rate of 5 * 6 bytes/second = 240 bps is required for this overhead.
As the result of the first phase of the packet-level and the connection-level scheduling algorithms applied to the five cases when the eleven STAs, 1, 4, 7, 8, 14, 15, 16, 23, 25, 27, and 30 request the direct data transmission opportunity on a packet basis, we obtained the following groups, each of which consists of the STAs that can be simultaneously polled using the simultaneous polling method:   For convenience of simulation analysis, we assume that the CP does not exist, and only the CFP exists. The burst and idle periods of each VoIP traffic stream are 1.5 seconds and 1 second, respectively. The length of the user payload of each VoIP data frame is 88 bits [11]. When the improved multiband excitation (IMBE) speech coder is used, the total number of VoIP data frames generated in a burst period by each VoIP traffic stream is 4.8 Kbps * 1.5 seconds/88 bits = 82, where 4.8 Kbps is the speech coding rate of the IMBE speech coder [11]. A VoIP data frame consists of the user datagram protocol (UDP), internet protocol (IP) and MAC layer headers, and the user payload. The lengths of the UDP, IP, and MAC layer headers are 16 bits, 224 bits, and 224 bits, respectively [1,11]. One SIFS period of 16 microseconds, one PIFS period of 25 microseconds, and the physical layer header transmission time of 24 microseconds are used [1,2]. We assume that all data, polling and multipolling frames are transmitted with the peak rate, 54 Mbps. It is assumed that the ACK frame transmission for the VoIP traffic streams can be omitted. We also assume that a PCF polling frame and Woo-Yong Choi   a polling frame transmitted in PIs can optionally have two recipient MAC addresses, one indicating the polled STA and one indicating the recipient of the data frame piggybacked on the polling frame. When the polled STA and the recipient of the piggybacked data frame are the same, the polling frame will have only one recipient MAC address.
The maximum delay bound for each combination of wireless LANs, interference conditions, and traffic loads was obtained by computer simulation during about 3 * 10 7 time slots using the specialized simulator developed in C code by the author. One slot time is 9 microseconds in IEEE 802.11a wireless LANs. In Figures 4,5,6,7,8,9,10,11, and 12, we present the simulation results of the maximum delay bounds of IEEE 802.11a wireless LAN with the conventional PCF polling method with the direct link communication technique in [5], the simultaneous polling method in [7], and the hybrid polling method in Section 3. The results of the mean delay bounds, which are encountered by at least 99% of the VoIP data frames transmitted in wireless LAN, were obtained for the five interference conditions, the three traffic loads and the three numbers of STAs in a wireless LAN. It is  assumed that the VoIP data or polling frames are transmitted erroneously with probability of 0.001.
As can be seen in Figures 4 to 12, the increase of the interference range negatively influences the performances of the simultaneous polling method and the hybrid polling method. Note that the interference range does not influence the performance of the PCF polling method. Comparing the results of the simultaneous polling method and the proposed polling method, we can see that the hybrid polling method copes with the increase of the interference range better than the simultaneous polling method. The performance of the simultaneous polling method decreases sharply after the interference condition of R = r, and becomes the same as that of the PCF polling method under the severe interference condition of R = ∞. However, with the hybrid polling method, the decrease in the MAC performance is relatively small even in the interference conditions of R = 1.8 r and ∞. Compared with the simultaneous polling method, the hybrid polling method decreases the mean delay bound by about 7.6%, 11.0%, 18.5%, 27.8%, and 40.5% under the interference conditions of R = r, 1.4 r, 1.5 r, 1.8 r, and ∞, respectively. Compared with the PCF polling method, the hybrid polling method decreases the mean delay bound by about 58.8%, 45.1%, 39.1%, 38.0%, and 38.9% under the interference conditions of R = r, 1.4 r, 1.5 r, 1.8 r, and ∞, respectively. From the simulation results, we can see that the hybrid polling method outperforms both the PCF protocol and the simultaneous polling method in maximum delay especially under the severe interference condition.
For a bandwidth-efficient direct link communication, we need to reduce the number of polling frame transmissions in DCPIs because the transmissions of the polling frames on which the data frames are not usually piggybacked for the direct link communication are the scheduling overhead in the simultaneous and hybrid polling methods. While with the simultaneous polling method the AP should transmit the separate polling frames to poll the STAs for the direct link communication under the severe interference condition, with the hybrid polling method, the AP can reduce significantly the number of polling frame transmissions using the connectivity among the STAs. The hybrid polling method can improve the MAC performance by reducing the scheduling overhead.

CONCLUSIONS
In this paper, we proposed the hybrid polling method for supporting direct link communication between STAs in IEEE 802.11 wireless LANs. Compared with the simultaneous polling method proposed in the literature, the proposed polling method can improve the MAC performance by reducing the number of polling frame transmissions using the connectivity among the STAs. Simulation results show that the proposed polling method is useful especially when the interference range is large.