TANG AND WANG:MAC FOR EFFICIENT COEXISTENCE BETWEEN FULL AND HALF-DUPLEX COMMUNICATIONS 587 A called deficit.The value of deficit for Client k at round n. denoted by T(n).is updated as (AP) T(n)quantum+Tx (n -1)I(n-1). (8) (B the packet in the p empty,and quantum is a constant number.If the deficit() Fig.6.An example of the faimess issue. chent k.ther the AP turns (n)is en a packet is sent.the transmission time is deducted from( This process is repeated until the deficit T)is insufficient for When selecting a client for the downlink of dual-link setup. sending anoth the AP pr nts tha thave more hidden nodesre clos to the AP which example,when the AP finishes its transmission to Client A.it gives thedo D.which Ap dual-lin ink ch link setup,as selecting Client B does not satisfy the condtio of capture effect.Thus,the deficit round robin D gets the channel,only half duplex link is allowed,i.e..the nt to s algorith ing pro leads a)When the AP contends the channel succ ssfully it follows the deficit round robin scheme to send a packet.After On the other hand,for each chance the throughput improve each transmission,it needs to find and record the nex ding to the For am when B ge Suppose the ent on if the inks Howe r.since Client D is very close to the AP and has ugh to packet.stl recorded s the higher SIR than Client C.more thr be a eved if the AP choc nt D The sa a pa As resu Client D is the best choice to get the chance each time,which makes the fairness worse.Thus,there exists a tradeoff between repeated until a client with enough deficit is found and is the AP in differe needs to select hy conside In this paper,it is evaluated on the channel access time 7..e. the channel access time of a downlink is expected to be equal effect.In this case,it does not follow the order of deficit e fairness,tw s the internal queueing system gives a higher priority to clients that the capture condition.After the downlink transmission ave a lower ch the deficit is deducted by the time that is needed when and B in ha conducted when to clients that have a lower chance of being selected for dual h link setup.To fulfill the above two mechanisms,the AP needs will give more opportunities to other client o look i o the dual-link s client and the ncluding etup c nces for eac e chances. tho arucipate in asymn an appropriate client for downlink transmission. a).In this situation.the AP needs to find a new next client in the similar way as lone in case a). 18 eve fa It should he noted that the Ap in notaclient can get a chance is determined by a time parameter if the deficit is enough to transmit the packet,so the deficit TANG AND WANG: MAC FOR EFFICIENT COEXISTENCE BETWEEN FULL- AND HALF-DUPLEX COMMUNICATIONS 5877 Fig. 6. An example of the fairness issue. V. FAIRNESS: THE VIRTUAL DEFICIT ROUND ROBIN ALGORITHM When selecting a client for the downlink of dual-link setup, the AP prefers clients that have more hidden nodes or are closer to the AP, which favors throughput improvement. However, a fairness issue arises. An example is shown in Fig. 6, where there are 4 clients in the network. When Clients A or B gets the channel (for uplink transmission), the AP can establish dual links with Client C or D, which is called a dual-link chance. When Client C gets the channel, the AP can establish the downlink with any of three other nodes. However, when Client D gets the channel, only half duplex link is allowed, i.e., the AP cannot select any other client to set up the downlink for dual-link setup. As a result, Client D has more chances of receiving packets from the AP, which leads to unfairness in downlink. On the other hand, for each chance the throughput improve￾ment is also different. For example, when Clients A or B gets the channel, the AP can select either Client C or D for dual links. However, since Client D is very close to the AP and has higher SIR than Client C, more throughput improvement can be achieved if the AP choose Client D for dual links. The same situation can occur when Client C gets the channel. As a result, if the AP wants to achieve higher throughput improvement, Client D is the best choice to get the chance each time, which makes the fairness worse. Thus, there exists a tradeoff between fairness and throughput. Fairness in channel access can be defined in different ways. In this paper, it is evaluated on the channel access time [7], i.e., the channel access time of a downlink is expected to be equal for all clients. In order to improve fairness, two mechanisms are considered. First, when the AP accesses a channel for data transmission, its internal queueing system gives a higher priority to clients that have a lower chance of being selected for dual-link setup, e.g., Clients A and B in Fig. 6. Second, when the AP establishes a downlink during dual-link setup, it also gives a higher priority to clients that have a lower chance of being selected for dual￾link setup. To fulfill the above two mechanisms, the AP needs to look into the dual-link setup chances for each client and then balance the utilization of these chances. To this end, a virtual deficit round robin algorithm is developed for the AP to select an appropriate client for downlink transmission. For a network with variable packet transmission time, the deficit round robin algorithm [18] can achieve fairness with low complexity. More specifically, during round robin, whether or not a client can get a chance is determined by a time parameter called deficit. The value of deficit for Client k at round n, denoted by Tk(n), is updated as Tk(n) = quantum + Tk(n − 1) I(n − 1), (8) where I(n − 1) is 1 if the deficit is not enough to transmit the packet in the previous round or 0 if the queue becomes empty, and quantum is a constant number. If the deficit Tk(n) is insufficient to send a packet from the AP to Client k, then the AP turns to Client k + 1. If the deficit Tk(n) is enough to transmit a packet, then Client k can be selected in round n. After a packet is sent, the transmission time is deducted from Tk(n). This process is repeated until the deficit Tk(n) is insufficient for sending another packet. However, due to capture effect, the above algorithm is not applicable to client selection for downlink transmission. For example, when the AP finishes its transmission to Client A, it gives the downlink chance to Client B according to round robin. However, if Client A gets the channel successfully, then the AP can only give the downlink chance to Client C or D for dual￾link setup, as selecting Client B does not satisfy the condition of capture effect. Thus, the deficit round robin scheme is not working in this case. To this end, a virtual deficit round robin algorithm is developed. It works with the following procedures: a) When the AP contends the channel successfully, it follows the deficit round robin scheme to send a packet. After each transmission, it needs to find and record the next client according to the deficit. Suppose the Client k is the recorded next client in deficit round robin. After this packet transmission, if the remaining deficit is enough to send another packet, Client k is still recorded as the next client. Otherwise, the deficit round robin goes to Client k + 1. If the deficit of Client k + 1 is enough for a packet, Client k + 1 is recorded as the next client. If the deficit is insufficient, Client k + 2 is considered. This process is repeated until a client with enough deficit is found and is recorded as the next client. b) If a client wins the channel access, the AP needs to select a client for downlink transmission by considering capture effect. In this case, it does not follow the order of deficit round robin, but it still relies on the deficit to select a client. More specifically, the AP selects the client that has the maximum deficit among all clients that satisfy the capture condition. After the downlink transmission, the deficit is deducted by the time that is needed when half-duplex communication is conducted. The reason for deducting such a time is to make sure the deficit is updated consistently with case a). As a result, winning a downlink transmission in full duplex communications by a client will give more opportunities to other clients including those that cannot participate in asymmetrical dual links. It is possible that the client selected by the AP is the one recorded as the next client in case a). In this situation, the AP needs to find a new next client in the similar way as done in case a). It should be noted that the AP in case b) does not check if the deficit is enough to transmit the packet, so the deficit